文章目录

一、定义二、LRU模拟实现二、代码实现

一、定义

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。 Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。

二、LRU模拟实现

146.LRU缓存

下面我们就借力扣的这道题来简单实现一个

题目中要求我们以O（1）的时间复杂度来完成，查找的话我们首先肯定会想到哈希表，但又涉及一个问题，我们查找完之后还需要更新一下刚刚查找数据的位置，将这个数据置为是新的数据，我们如何解决查找完改变数据的标识也做到O（1）呢？

要保持高效实现O(1)的put和get，那么使用双向链表和 哈希表的搭配是最高效和经典的。使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，使用哈希表是因为哈希表的增删查改也是O(1)。

需要注意：这里最巧的设计就是将unordered_map的value type放成list>::iterator，因为这样，当get一个已有的值以后，就可以直接找到key在list中对应的iterator，然后将这个值移动到链表的头部，保持LRU。

二、代码实现

#define _CRT_SECURE_NO_WARNINGS 1

#include

#include

#include

using namespace std;

class LRUCache {

public:

LRUCache(int capacity)

:_capacity(capacity)

{}

int get(int key) {

auto ret = _hashMap.find(key);

//在hash中找到了key存的地方

if (ret != _hashMap.end()) {

LtIter it = ret->second;

//将it移动到_LRUList的头部

_LRUList.splice(_LRUList.begin(), _LRUList, it);

return it->second;

}

else {

return -1;

}

}

void put(int key, int value) {

auto ret = _hashMap.find(key);

//原来没有key的数据则添加

if (ret == _hashMap.end()) {

//LRU满了，删除最近最少使用的就是链表尾部

if (_capacity == _hashMap.size()) {

pairback = _LRUList.back();

_hashMap.erase(back.first);//删哈希里面

//链表里面k存的和哈希的是同一个key

_LRUList.pop_back();//删链表尾部

}

//放入新的数据到链表头部

_LRUList.push_front(make_pair(key, value));

//哈希表中添加

_hashMap[key] = _LRUList.begin();

}

//原来有key的数据则更新

else {

LtIter it = ret->second;

it->second = value;

//将这个位置移到链表头部

_LRUList.splice(_LRUList.begin(), _LRUList, it);

}

}

private:

//链表存kv结构

//k为key值，v为我们要更新的数据

typedef list>::iterator LtIter;//重命名链表迭代器

int _capacity; // 容量大小，超过容量则换出，保持LRU

//_LRUList假设链表头部为最近使用的，尾部为最近最少使用

list> _LRUList;

//hash中存放的是key值与对应链表迭代器的的映射关系

unordered_map_hashMap;

};

精彩内容

评论可见，请评论后查看内容，谢谢！！！
 您阅读本篇文章共花了：