题解 | #设计LRU缓存结构#

class Solution {
public:
 Solution(int capacity){
 // write code here
 cap = capacity;
 }
 
 int get(int key) {
 // write code here
 if(ky.find(key) != ky.end()){
    for(auto it=order.begin(); it!=order.end(); ++it){
        if(*it==key) {order.erase(it); break;}
    }
    order.push_front(key);
    return ky[key];
 }

 else return -1;
 }
 
 void set(int key, int value){
 // write code here
 if(ky.find(key)!=ky.end()){
    ky[key] = value;
    for(auto it=order.begin(); it!=order.end(); ++it){
        if(*it==key) {order.erase(it); break;}
    }
    order.push_front(key);
 }
 else{
    if(ky.size() == cap) {
        ky.erase(order.back());
        order.pop_back();
    }
    ky[key] = value;
    order.push_front(key);
 }
 }

 private:
 map<int,int> ky;
 list<int> order;
 int cap;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */