LeeCcode: 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.

The original problem is here.

The original code is here.

My Solution

I solve this problem in C++, as below:

*LRU Cache
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
using namespace std;

class LRUCache{
    LRUCache(int capacity) {
        this->capacity = capacity;
    int get(int key) {
        if(cacheMap.find(key) == cacheMap.end())
            return -1;
        cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
        cacheMap[key] = cacheList.begin();
        return cacheMap[key]->value;
    void set(int key, int value) {
        if(cacheMap.find(key) == cacheMap.end()){
            if(capacity == cacheList.size()){
            CacheNode node(key,value);
            cacheMap[key] = cacheList.begin();
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
            cacheMap[key] = cacheList.begin();
            cacheMap[key]->value = value;
    struct CacheNode{
        int key;
        int value;
        CacheNode(int k, int v):key(k), value(v){}
    int capacity;
    list<CacheNode> cacheList;
    map<int, list<CacheNode>::iterator> cacheMap;


To solve the problem, a bidirector list and a hashmap are needed. For every operation, put the visited node to the head of the list.