题解 | 设计LRU缓存结构 C++/简单STL

class Solution {
private:
int cap;
map<int,int> mp;
list<int> ls;

public:
 Solution(int capacity){
    cap = capacity;
 }
 
 void updateList(int key) {
    if (!mp[key]) {
        ls.push_front(key);
    } else {
        for(auto it = ls.begin();it!=ls.end();it++) {
            if (*it == key) {
                ls.erase(it);
                break;
            }
        }
        ls.push_front(key);
    }
    if(ls.size()>cap) {
        int dlkey = ls.back();
        mp.erase(dlkey);
        ls.pop_back();
    }
 }

 int get(int key) {
    if (mp.count(key)) {
        updateList(key);
        return mp[key];
    }
    else {
        return -1;
    }
 }
 
 void set(int key, int value){
    mp[key] = value;
    updateList(key);
 }
};