Leetcode LRU Cache-白红宇

Leetcode LRU Cache

阅读量：4984 次

发布时间：2019-06-12

本文共 2214 字，大约阅读时间需要 7 分钟。

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.

LRU是近期最少使用算法，其一个例子为：

假设序列为 4 3 4 2 3 1 4 2

物理块有3个则

首轮 4调入内存 4

次轮 3调入内存 3 4

之后 4调入内存 4 3

之后 2调入内存 2 4 3

之后 3调入内存 3 2 4

之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）

之后 4调入内存 4 1 3（原理同上）

最后 2调入内存 2 4 1

对于

set(key, value) ，

如果不存在该cache

　　如果cache已经达到了它的容量，则把最近最少使用的cache删除，然后插入新的cache

　　否则直接插入新的cache

如果存在该cache

　　将该cache移动到前面，表示刚被使用

对于get(key)，

如果不存在该cache，则返回-1

否则将该cache移动到前面，表示刚被使用

由于涉及到查找，由于hash_map的查找时间复杂度为O(1)，故考虑用hash_map

由于涉及到插入和删除，由于链表的插入删除时间复杂度为O(1)，故考虑用list

故将hash_map和list相结合

class LRUCache{public:    typedef pair
      
        CacheItem;    typedef list
       
        ::iterator CacheItemIterator;    typedef unordered_map
        
         
          ::iterator > CacheMap;    typedef CacheMap::iterator CacheMapIterator;        LRUCache(int capacity){        m_capacity = capacity;    }        int get(int key){        if(m_map.find(key) == m_map.end()) return -1;        else{            moveToFirst(key);            return m_map[key]->second;        }    }        void set(int key, int value){        if(m_map.find(key) == m_map.end()){            if(m_cache.size() >= m_capacity){                m_map.erase(m_cache.back().first);                m_cache.pop_back();            }            m_cache.push_front(CacheItem(key,value));            m_map[key]=m_cache.begin();                    }else{            m_map[key]->second = value;            moveToFirst(key);        }    }        void moveToFirst(int key){        CacheItemIterator itemIter = cacheMap[key];        m_cache.erase(itemIter);        m_cache.push_front(*itemIter);        m_map[key] = m_cache.begin();        }    private:    int m_capacity;    CacheMap m_map;    list
          
            m_cache;    };