https://leetcode-cn.com/problems/lru-cache

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

标准解法（STL）

hash+双向链表（存key）

struct ValueData {
    int value;
    list<int>::iterator iter;

    ValueData(int v, list<int>::iterator it): value(v), iter(it) {}
};

class LRUCache {
public:
    LRUCache(int capacity) {
        _capacity = capacity;
        _hash.reserve(capacity * 2); //减少rehash
    }

    int get(int key) {
        std::unordered_map<int, ValueData>::iterator iter = _hash.find(key);
        if (iter != _hash.end()) { //找到了
            //将该链表节点移动到链表头节点
            _list.splice(_list.begin(), _list, iter->second.iter);

            return iter->second.value;
        } else {
            return -1;
        }
    }

    void put(int key, int value) {

        std::unordered_map<int, ValueData>::iterator iter = _hash.find(key);
        if (iter != _hash.end()) {//找到了
            //将该链表节点移动到链表头节点
            _list.splice(_list.begin(), _list, iter->second.iter);

            iter->second.value = value;
        } else {//没找到
            if (_hash.size() == _capacity) {//缓存满了 
                //缓存淘汰           
                _hash.erase(_list.back()); //hash删除该尾结点的键值对
                _list.pop_back(); //删除尾结点
            }
            _list.push_front(key); //在链表头插入新节点
            ValueData v(value, _list.begin());
            _hash.emplace(key, v); //hash插入
        }
    }

private:
    unordered_map<int, ValueData> _hash;
    list<int> _list;
    int _capacity;
};

学习到了list的splice函数用法： http://www.cplusplus.com/reference/list/list/splice/

void splice (iterator position, list& x);
void splice (iterator position, list& x, iterator i);
void splice (iterator position, list& x, iterator first, iterator last);

对于前两个重载都能O(1)时间完成。

The first version (1) transfers all the elements of x into the container.

The second version (2) transfers only the element pointed by i from x into the container.

The third version (3) transfers the range [first,last) from x into the container.

guodongxiaren / OJ

LeetCode 146: LRU缓存机制 #47

标准解法（STL）