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

    int get(int key) {
        auto it = m.find(key);
        if (it == m.end()) return -1;
        l.splice(l.begin(), l, it->second);
        //transfers only the element pointed by it->second from l into the l.begin() position.
        return it->second->second;
    }

    void set(int key, int value) {
        auto it = m.find(key);
        if (it != m.end()) l.erase(it->second);
        //it 这里是一个Map iterator it->second 是list<pair<int, int>
        l.push_front(make_pair(key, value));
        m[key] = l.begin();
        if (m.size() > cap) {
            int k = l.rbegin()->first;
            //rbegin == last item in container
            l.pop_back();
            m.erase(k);
        }
    }

private:
    int cap;
    list<pair<int, int> > l;
    unordered_map<int, list<pair<int, int> >::iterator> m;
};

class LRUCache {
private:
    int capacity;
    list<int> recent;
    unordered_map<int, int> cache;
    unordered_map<int, list<int>::iterator> pos;
    void use(int key) {
        if (pos.find(key) != pos.end()) {
            recent.erase(pos[key]);
        } else if (recent.size() >= capacity) {
            int old = recent.back();
            recent.pop_back();
            cache.erase(old);
            pos.erase(old);
        }
        recent.push_front(key);
        pos[key] = recent.begin();
    }
public:
    LRUCache(int capacity): capacity(capacity) {}
    int get(int key) {
        if (cache.find(key) != cache.end()) {
            use(key);
            return cache[key];
        }
        return -1;
    }
    void set(int key, int value) {
        use(key);
        cache[key] = value;
    }
};

class LRUCache {
public:
    LRUCache(int capacity) : _capacity(capacity) {}

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;
        touch(it);
        return it->second.first;
    }

    void set(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) touch(it);
        else {
            if (cache.size() == _capacity) {
                cache.erase(used.back());
                used.pop_back();
            }
            used.push_front(key);
        }
        cache[key] = { value, used.begin() };
    }

private:
    typedef list<int> LI;
    typedef pair<int, LI::iterator> PII;
    typedef unordered_map<int, PII> HIPII;

    void touch(HIPII::iterator it) {
        int key = it->first;
        used.erase(it->second.second);
        used.push_front(key);
        it->second.second = used.begin();
    }

    HIPII cache;
    LI used;
    int _capacity;
};

class LRUCache{
    size_t m_capacity;
    unordered_map<int,  list<pair<int, int>>::iterator> m_map; //m_map_iter->first: key, m_map_iter->second: list iterator;
    list<pair<int, int>> m_list;                               //m_list_iter->first: key, m_list_iter->second: value;
public:
    LRUCache(size_t capacity):m_capacity(capacity) {
    }
    int get(int key) {
        auto found_iter = m_map.find(key);
        if (found_iter == m_map.end()) //key doesn't exist
            return -1;
        m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
        return found_iter->second->second;                         //return value of the node
    }
    void set(int key, int value) {
        auto found_iter = m_map.find(key);
        if (found_iter != m_map.end()) //key exists
        {
            m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
            found_iter->second->second = value;                        //update value of the node
            return;
        }
        if (m_map.size() == m_capacity) //reached capacity
        {
           int key_to_del = m_list.back().first; 
           m_list.pop_back();            //remove node in list;
           m_map.erase(key_to_del);      //remove key in map
        }
        m_list.emplace_front(key, value);  //create new node in list
        m_map[key] = m_list.begin();       //create correspondence between key and node
    }
};

// LinkedHashMap
   import java.util.LinkedHashMap;
    public class LRUCache {
        private LinkedHashMap<Integer, Integer> map;
        private final int CAPACITY;
        public LRUCache(int capacity) {
            CAPACITY = capacity;
            map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
                protected boolean removeEldestEntry(Map.Entry eldest) {
                    return size() > CAPACITY;
                }
            };
        }
        public int get(int key) {
            return map.getOrDefault(key, -1);
        }
        public void set(int key, int value) {
            map.put(key, value);
        }
    }

class Node {
int key;
int value;
Node pre;
Node next;

public Node(int key, int value) {
    this.key = key;
    this.value = value;
}
}
public class LRUCache {

HashMap<Integer, Node> map;
int capicity, count;
Node head, tail;

public LRUCache(int capacity) {
    this.capicity = capacity;
    map = new HashMap<>();
    head = new Node(0, 0);
    tail = new Node(0, 0);
    head.next = tail;
    tail.pre = head;
    head.pre = null;
    tail.next = null;
    count = 0;
}

public void deleteNode(Node node) {
    node.pre.next = node.next;
    node.next.pre = node.pre;
}

public void addToHead(Node node) {
    node.next = head.next;
    node.next.pre = node;
    node.pre = head;
    head.next = node;
}

public int get(int key) {
    if (map.get(key) != null) {
        Node node = map.get(key);
        int result = node.value;
        deleteNode(node);
        addToHead(node);
        return result;
    }
    return -1;
}

public void set(int key, int value) {
    if (map.get(key) != null) {
        Node node = map.get(key);
        node.value = value;
        deleteNode(node);
        addToHead(node);
    } else {
        Node node = new Node(key, value);
        map.put(key, node);
        if (count < capicity) {
            count++;
            addToHead(node);
        } else {
            map.remove(tail.pre.key);
            deleteNode(tail.pre);
            addToHead(node);
        }
    }
}
}

REF:

LRU

results matching ""

No results matching ""