最近最少使用置换算法：当缓存满时，移除最近最少使用的数据 算法思路：利用哈希链表的有序性，将数据按最后使用时间排序

    • 使用哈希表存储数据，实现查找和插入数据的时间复杂度都为O(1)
    • 使用双向链表来实现算法逻辑
      • 当数据被访问时，移动该数据到链表头部
      • 缓存满时，删除链表尾部数据

    image.png

    1. #include <iostream>
    2. #include <list>
    3. #include <unordered_map>
    4. using namespace std;
    6. #define PII pair<int, int>
    8. class LRUCache {
    9. public:
    10.     LRUCache(int n) : capacity(n) {}
    11.     int get(int key) {
    12.         /*
    13.             当数据被访问时，将数据移动到链表头部
    14.                 - 在map中查找，如有，根据it将PII移动到list首部
    15.         */
    16.         auto it_mp = mp.find(key);
    17.         if (it_mp == mp.end()) return -1;
    18.         auto it_list = it_mp->second;
    19.         // 拷贝被访问的PII到链表头部
    20.         PII tmp {it_list->first, it_list->second};
    21.         cache.push_front(tmp);
    22.         // 删除原有PII，更新map中的it
    23.         cache.erase(it_list);
    24.         mp.erase(it_mp);
    25.         mp.emplace(key, cache.begin());
    27.         return tmp.second;
    28.     }
    29.     int put(int key, int value) {
    30.         /*
    31.             if原有key -> 删除原有数据，将新数据插入链表头部
    32.             if新数据 -> 将数据插入链表头部
    33.                 - if容量满，删除尾部数据
    34.         */
    35.         auto it_mp = mp.find(key);
    36.         if (it_mp != mp.end()) {
    37.             cache.erase(it_mp->second);
    38.             mp.erase(it_mp);
    39.         }
    40.         PII tmp {key, value};
    41.         cache.push_front(tmp);
    42.         mp.emplace(key, cache.begin());
    44.         if (cache.size() > capacity) {
    45.             // 先清map中数据
    46.             mp.erase(cache.back().first);
    47.             cache.pop_back();
    48.         }
    49.     }
    50. private:
    51.     size_t capacity;
    52.     /*
    53.         双向链表实现算法逻辑
    54.             - 最近访问的数据移动到链表头部
    55.             - 缓存满时，删除链表尾部数据
    56.     */
    57.     list<PII> cache;
    58.     // 哈希表存储数据，实现查找和插入效率O(1)
    59.     unordered_map<int, list<PII>::iterator> mp;
    60. };
    62. int main() {
    63.     LRUCache *lru = new LRUCache(2);
    64.     lru->put(1, 1);
    65.     lru->put(2, 2);
    66.     cout << lru->get(1) << endl;
    67.     lru->put(3, 3);
    68.     cout << lru->get(2) << endl;  // -1
    69.     lru->put(4, 4);
    70.     cout << lru->get(1) << endl;  // -1
    71.     cout << lru->get(3) << endl;
    72.     cout << lru->get(4) << endl;
    73.     delete lru;
    75.     return 0;
    76. }