题目来源
题目的意思就是说给定大小固定的空间，然后要实现get，put操作，假如容量满了，那么根据最近最少使用原则来进行删除，两个操作都用O(1)的时间完成。
这道题我在之前京东面试的时候碰到了，然后当时想了挺久，没想出来。
看了看讨论区，实际上也不是很难，总的想法和我原来想的差不多，不过我对那些基本数据结构的了解不够透彻。
实际上就是需要一个哈希表以及一个双链表，哈希表中key存的是就是key，value存的是双链表的iterator，指向双链表中存放对应key的位置。
然后双链表中存放值。
get操作，因为哈希表，所以是O(1)的，get操作后需要将对应节点移到队首。
然后复杂一点是put操作，首先需要考虑这个key在双链表中是否已经存在，存在的话就把双链表的那个节点移到队首来。假如不存在，首先需要判断容量是否已满，假如已经满了，就把队尾删掉。假如不满，那么直接往队首插入一个值即可。
其中比较复杂的操作实际上就是这个双链表怎么移动，怎么把某个元素移到队首，写起来比较复杂。但是！STL已经把你做好了，用splice操作直接来实现。
代码如下：
class LRUCache {
public:
LRUCache(int capacity) : m_capacity(capacity) {}
int get(int key) {
auto found_iter = m_map.find(key);
if (found_iter == m_map.end())
return -1;
m_list.splice(m_list.begin(), m_list, found_iter->second);
return found_iter->second->second;
}
void put(int key, int value) {
auto found_iter = m_map.find(key);
if (found_iter != m_map.end()) {
found_iter->second->second = value;
m_list.splice(m_list.begin(), m_list, found_iter->second);
return;
}
if (m_map.size() == m_capacity) {
int del_key = m_list.back().first;
m_list.pop_back();
m_map.erase(del_key);
}
m_list.emplace_front(key, value);
m_map[key] = m_list.begin();
}
private:
size_t m_capacity;
unordered_map<int, list<pair<int, int>>::iterator> m_map;
list<pair<int, int>> m_list;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
