首页 > 代码库 > LeetCode——LRU Cache

LeetCode——LRU Cache

2024-07-03 04:14:01   222人阅读

LRU Cache

 

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.

思路：
最常用的数据结构实现方式是map和Double-Linked List，map只是为了实现键值key-value对应，这样就避免了每次寻找特定值都要在双线链表里面顺序查找，服务器是没办法负担这种低效率的查找方法的。

set流程讲解：

  1. 在map中查找key，如果找到，说明这个节点已经存在，那么将该节点的的位置排在链表头部；
  2. 如果没找到，要进行第二个判断“是否已经达到了max_size”，如果已经达到了，将原来链表最后一个节点删除，然后将对应的map中的key-value删除，然后再加入新节点，并在map中加入对应的key-value，如果没有达到max-size，那么分配新地址给这个节点，同时加入到list和对应的map中。
get比较简单

代码：
class LRUCache {
public:
	LRUCache(int capacity) {
		_cache_map.clear();
		_cache_list.clear();
		_max_size = capacity;
	}

	int get(int key) {
		map<int, list<pair<int, int> >::iterator>::iterator p = _cache_map.find(
				key);
		if (p != _cache_map.end()) {
			_cache_list.splice(_cache_list.begin(), _cache_list, p->second);
			p->second = _cache_list.begin();
			return (p->second)->second;
		}
		return -1;
	}
	void set(int key, int value) {
		map<int, list<pair<int, int> >::iterator>::iterator p = _cache_map.find(
				key);
		//已经存在key
		if (p != _cache_map.end()) {
			((p->second))->second = value;
			_cache_list.splice(_cache_list.begin(), _cache_list, p->second);
			p->second = _cache_list.begin();
		} else {//key不存在
			if (_cache_map.size() >= _max_size) {//判断是否达到maxsize
				_cache_map.erase(_cache_list.rbegin()->first);
				_cache_list.pop_back();
			}
			_cache_list.push_front(pair<int, int>(key, value));
			_cache_map[key] = _cache_list.begin();
		}
	}
private:
	map<int, list<pair<int, int> >::iterator> _cache_map;
	list<pair<int, int> > _cache_list;
	int _max_size;
};

附：splice是移动链表元素的方法
splice实例代码：
#include<iostream>
#include<list>
using namespace std;
int main() {
	list<int> mylist1, mylist2;
	list<int>::iterator it;
	// set some initial values:
	for (int i = 1; i <= 4; i++)
		mylist1.push_back(i);      // mylist1: 1 2 3 4
	for (int i = 1; i <= 3; i++)
		mylist2.push_back(i * 10);   // mylist2: 10 20 30
	it = mylist1.begin();
	++it;                         // points to 2
	mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
								 // mylist2 (empty)
								 // "it" still points to 2 (the 5th element)

	mylist2.splice(mylist2.begin(), mylist1, it);
	// mylist1: 1 10 20 30 3 4
	// mylist2: 2
	// "it" is now invalid.
	it = mylist1.begin();
	advance(it, 3);                // "it" points now to 30
	mylist1.splice(mylist1.begin(), mylist1, it, mylist1.end());
	// mylist1: 30 3 4 1 10 20
	cout << "mylist1 contains:";
	for (it = mylist1.begin(); it != mylist1.end(); it++)
		cout << " " << *it;
	cout << "\nmylist2 contains:";
	for (it = mylist2.begin(); it != mylist2.end(); it++)
		cout << " " << *it;
	cout << endl;
	return 0;
}


 


联系
我们