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

class Solution {
public:
 Solution(int capacity){
 // write code here
    capacity_ = capacity;
 }
 
 int get(int key) {
 // write code here
    auto it = mp_.find(key);
    if (it == mp_.end()) {
        return -1;
    }
    int v = (it->second)->second;
    value_.erase(it->second);
    mp_.erase(key);
    value_.push_front({key, v});
    mp_[key] = value_.begin();

    return v;
 }
 
 void set(int key, int value){
 // write code here
    auto it = mp_.find(key);
    if (it == mp_.end()) {
        if (value_.size() < capacity_) {
            value_.push_front({key, value});
            mp_[key] = value_.begin();
        } else {
            auto it = value_.back();
            mp_.erase(it.first);
            value_.pop_back();
            
            value_.push_front({key, value});
            mp_[key] = value_.begin();
        }
    } else {
        value_.erase(it->second);
        value_.push_front({key, value});
        mp_[key] = value_.begin();
    }
 }

private:
    int capacity_ = 0;
    std::map<int, std::list<std::pair<int, int>>::iterator> mp_;
    std::list<std::pair<int, int>> value_;
};

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