深信服题目_深信服pt2题库

typedef struct Elem{
 int key;
 int value;
}Elem;

#include <iostream>
#include <list>
#include <map>
using namespace std;
 
typedef struct Elem{
 int key;
 int value;
}Elem;
 
typedef list<Elem> myList;
typedef map<int, myList::iterator> myMap;
 
 
class LRU{
public:
 LRU(int s) :_size(s){}
 int get(int key){
  auto it = myMap1.find(key);
  if (it == myMap1.end())return -1;
  else{
   auto list_it = myMap1[key];
   int value = list_it->value;
   Elem elem;
   elem.key = key;
   elem.value = value;
   myList1.erase(list_it);
   myList1.push_front(elem);
   myMap1[key] = myList1.begin();
   return myList1.begin()->value;
  }
 }
 void put(int key, int value){
  auto it = myMap1.find(key);
  if (it == myMap1.end()){ //直接插入
   if (myList1.size() == _size){ //容量达到限制
    int key = myList1.back().key;
    myMap1.erase(key);
    myList1.pop_back();
   }
   Elem elem;
   elem.key = key;
   elem.value = value;
   myList1.push_front(elem);
   myMap1[key] = myList1.begin();
  }
  else{
   auto list_it = myMap1[key];
   Elem ee;
   ee.key = key;
   ee.value = value;
   *list_it = ee;
  }
 }
 
private:
 int _size;
 myList myList1;
 myMap myMap1;
};
 
int main() {
 int n;
 cin >> n;
 LRU lru(n);
 char ch;
 int _1, _2;
 while (cin >> ch) {
  if (ch == 'p') {
   if (n <= 0)continue;
   cin >> _1 >> _2;
   lru.put(_1, _2);
  }
  else if (ch == 'g') {
   cin >> _1;
   cout << lru.get(_1) << endl;
  }
 }
 return 0;
}

typedef list<Elem> myList;
typedef map<int, myList::iterator> myMap;

class LRU{
public:
 LRU(int s) :_size(s){}
 int get(int key){
  auto it = myMap1.find(key);
  if (it == myMap1.end())return -1;
  else{
   auto list_it = myMap1[key];
   int value = list_it->value;
   Elem elem;
   elem.key = key;
   elem.value = value;
   myList1.erase(list_it);
   myList1.push_front(elem);
   myMap1[key] = myList1.begin();
   return myList1.begin()->value;
  }
 }
 void put(int key, int value){
  auto it = myMap1.find(key);
  if (it == myMap1.end()){ //直接插入
   if (myList1.size() == _size){ //容量达到限制
    int key = myList1.back().key;
    myMap1.erase(key);
    myList1.pop_back();
   }
   Elem elem;
   elem.key = key;
   elem.value = value;
   myList1.push_front(elem);
   myMap1[key] = myList1.begin();
  }
  else{
   auto list_it = myMap1[key];
   Elem ee;
   ee.key = key;
   ee.value = value;
   *list_it = ee;
  }
 }

private:
 int _size;
 myList myList1;
 myMap myMap1;
};

int main() {
 int n;
 cin >> n;
 LRU lru(n);
 char ch;
 int _1, _2;
 while (cin >> ch) {
  if (ch == 'p') {
   if (n <= 0)continue;
   cin >> _1 >> _2;
   lru.put(_1, _2);
  }
  else if (ch == 'g') {
   cin >> _1;
   cout << lru.get(_1) << endl;
  }
 }
 return 0;
}