题解 | 设计LRU缓存结构

#include <unordered_map>
#include <list>

class Solution {
  public:
    Solution(int capacity) {
        // write code here
        m_capacity = capacity;
    }

    int get(int key) {
        // write code here
        auto mapIter = m_map.find(key);
        if (mapIter != m_map.end()) {
            m_list.splice(m_list.begin(), m_list, mapIter->second);
            return mapIter->second->second;
        }
        return -1;
    }

    void set(int key, int value) {
        // write code here
        auto mapIter = m_map.find(key);
        if (mapIter != m_map.end()) {
            m_list.erase(mapIter->second);
        } else if (m_map.size() == m_capacity) {
            m_map.erase(m_list.back().first);
            m_list.pop_back();
        }
        m_list.emplace_front(key, value);
        m_map[key] = m_list.begin();
    }

  private:
    using KeyValuePair = std::pair<int, int>;
    using ListType = std::list<KeyValuePair>;
    using ListIterator = ListType::iterator;
    using MapType = std::unordered_map<int, ListIterator>;
    int m_capacity;
    ListType m_list;
    MapType m_map;
};

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