LRU算法代码

// 最近最少缓存算法（key,value）
class LRUCache
{
private:
    // 1、list双向链表
    std::list<std::pair< int, int> > _list;

    // 2、使用unordered_map
    // 由于需要快速定位链表的结点，故在map中使用value字段来存储链表的结点，这里是使用了迭代器。
    std::unordered_map< int, std::list<std::pair<int, int>>::iterator > _map;
    unsigned int _capacity; 
public:
    LRUCache(unsigned int capacity):_capacity(capacity)
    {
    }
    // 获取
    int get(int key);
    // 设置
    void set(int key, int value);
};


// 设置
void LRUCache::set(int key, int value)
{
    // 1、查询是否在缓存中
    auto iteramap = _map.find(key);
    if(iteramap != _map.end()){
        // 2、在缓存中，需要在链表中擦除。
        _list.erase(iteramap->second);
        // 3、把数据放到链表头
        _list.push_front(std::pair<int, int>(key, value));
        _map[key] = _list.begin();
    }else{
        if(_map.size() >= _capacity){
            // 4、缓存已经满了
            // 4.1 hash处要删除
            _map.erase(_list.back().first);
            // 4.2 链表也要删除尾巴部分
            _list.pop_back(); 
        }
        // 5、双向链表首结点插入
        _list.push_front(std::pair<int, int>(key, value));
        // 6、在hash中增加
        _map[key] = _list.begin();
    }   
}


// 获取:根据key，获取缓存的value
int LRUCache::get(int key)
{
    // 1、先从hash中查找
    auto iteramap = _map.find(key);
    if(iteramap == _map.end()){
        // 没找到,TODO
        return -1;
    }
    // 2、如果在缓存中，需要把数据放到链表头部。
    _list.push_front(std::pair<int, int>(key,  iteramap->second->second));
    _list.erase(iteramap->second);
    
    // 3、hash原来存储的失效，需要重新设置
    _map[key] = _list.begin();
    
    // 4、返回value值
    return iteramap->second->second;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

最近最少使用算法LFU:

#include<iostream>
#include<unordered_map>

using namespace std;

class LFUCache
{
public:
	LFUCache(int cap):capacity(cap),size(0){}
	int get(int key)
	{
		if(m.count(key)==0) return -1;
		//get使得fre+1,将原来fre对应的节点删除，插入到fre+1的list中
		hash_fre[m[key].second].erase(hash_node[key]);
		m[key].second++;
		hash_fre[m[key].second].push_back(key);
		hash_node[key]=--hash_fre[m[key].second].end();
		if(hash_fre[min_fre].size()==0) min_fre++;
		return m[key].first;
	}

	void put(int key,int value)
	{
		if(capacity<=0) return;
		if(get(key)!=-1)
		{	
			m[key].first=value;
			return;
		}
		//容量已满，删除最不常用的key
		if(size>=capacity)
		{
			m.erase(hash_fre[min_fre].front());
			hash_node.erase(hash_fre[min_fre].front());
			hash_fre[min_fre].pop_front();
		}
		//插入key
		m[key]={value,1};
		hash_fre[1].push_back(key);
		hash_node[key]=--hash_fre[1].end();
		min_fre=1;
		if(size<cap) size++;
	}

private:
	int capacity;//缓存容量
	int size;//当前缓存大小
	int min_fre;//最小访问频率
	unordered_map<int,pair<int,int>> m;//key与{value,fre}之间的映射
	unordered_map<int,list<int>> hash_fre;//fre与list之间的映射（节点为key）
	unordered_map<int,list<int>::iterator> hash_node;//key与list节点之间的映射
};
————————————————
版权声明：本文为CSDN博主「半梦半醒间幸运_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43086349/article/details/107780080
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55