[LeetCode] LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

解题思路

Cache(高速缓存)，需实现随机存取操作和高效的插入删除操作。

• vector可以高效的随机存取，但是在插入删除会造成内存块的拷贝。另外，当内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。
• list可以高效的插入删除，但是不支持随机存取。
• deque支持随机存取，但是只能在两端进行插入删除操作。

因此采用双向链表来实现插入删除操作，同时采用哈希表来实现高效的随机存取。在unordered_map<key, value>中，key表示键值，value存储该键值在链表中所对应的结点位置。

实现代码1

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/16 17:52
    *  @Status   : Accepted
    *  @Runtime  : 176 ms
******************************************************************/
#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

struct cacheNode
{
    int key;
    int value;
    cacheNode(int k, int v) : key(k), value(v) {}
};
class LRUCache{
public:
    LRUCache(int capacity) {
        size = capacity;
    }

    int get(int key) {
        if (cacheMap.find(key) != cacheMap.end())
        {
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
            return cacheList.begin()->value;
        }
        else
        {
            return -1;
        }
    }

    void set(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end())
        {
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
            cacheList.begin()->value = value;
            cacheMap[key] = cacheList.begin();
        }
        else
        {
            if (cacheList.size() == size)
            {
                cacheMap.erase(cacheList.back().key);
                cacheList.pop_back();
            }
            cacheList.push_front(cacheNode(key, value));
            cacheMap[key] = cacheList.begin();
        }
    }
public:
    int size;
    list<cacheNode> cacheList;
    unordered_map<int, list<cacheNode>::iterator> cacheMap;
};

void print(LRUCache cache)
{
    for (auto it = cache.cacheList.begin(); it != cache.cacheList.end(); it++)
    {
        cout<<"key:"<<it->key<<"\tvalue:"<<it->value<<endl;
    }
    cout<<endl;
}

int main()
{
    LRUCache cache(4);
    cache.set(1,2);
    cache.set(2,3);
    cache.set(3,4);
    cache.set(4,5);

    print(cache);
    cache.set(2,5);
    cache.set(3,100);
    cache.set(10,45);
    cache.set(10,456);
    print(cache);

    return 0;
}

琢摸着感觉上述代码效率还是偏低，于是把cache结点由一个struct结构体改为了一个pair，但是经过测试效果相当。以下是第二个版本的代码：

实现代码2

class LRUCache{
public:
    LRUCache(int capacity) {
        size = capacity;
    }

    int get(int key) {
        if (cacheMap.find(key) != cacheMap.end())
        {
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
            return cacheList.begin()->second;
        }
        else
        {
            return -1;
        }
    }

    void set(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end())
        {
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
            cacheList.begin()->second = value;
            cacheMap[key] = cacheList.begin();
        }
        else
        {
            if (cacheList.size() == size)
            {
                cacheMap.erase(cacheList.back().first);
                cacheList.pop_back();
            }
            cacheList.push_front(make_pair(key, value));
            cacheMap[key] = cacheList.begin();
        }
    }
private:
    int size;
    list<pair<int, int>> cacheList;
    unordered_map<int, list<pair<int,int>>::iterator> cacheMap;
};