Cache满载的LRU置换

• #include <iostream>
• #include <list>
• #include <string>
• #include <algorithm>
• using namespace std;
• class Node
• {
• public:
• string _data;
• string _key;
• Node(string key, string data)
• {
• this->_data = data;
• this->_key = key;
• }
• void release(){ delete this; }
• Node(){}
• };
• /*
• LRU = Least Recently Used的缩写，即最近最少使用的操作系统内存页面置换算法，利用该思想设计一个缓存
• 如果缓存满载后，把最近最少使用的从缓存中移除
• 基本思想：
• 用链表来维护，每次使用一个 缓存数据时吧该节点放到链表头部，
• 链表头到尾使用顺序依次递减，所以链表尾部是当前整个链表最少使用的。
• 利用链表的顺序来标记，使用情况，避免了用诸如使用时间来标记，性能大大提升。
• 添加缓存：吧添加的放到链表尾部，维护当前队列大小，如果满载，那么移除最少使用的
• 返回缓存：负责吧目标数据移到链表头部，表示当前使用的，
• */
• #define MAX_SIZE 3
• class LRU_Cache
• {
• public:
• Node*getValue(const string & key)
• {
• Node* target = nullptr;
• // 查找，目标Node
• auto iter = this->_list.begin();
• while (iter != this->_list.end())
• {
• if ((*iter)->_key == key)
• {//查找成功，从链表中移除，然后添加到头部
• target = *iter;
• this->_list.erase(iter);
• _list.push_front(target);
• return target;
• break;
• }
• iter++;
• }
• return nullptr;
• }
• void addValue(const string & key, string data)
• {
• auto iter = this->_list.begin();
• while (iter != this->_list.end())
• {
• if ((*iter)->_key == key)
• {//已经存在
• return;
• }
• iter++;
• }
• if (this->_curr_size == MAX_SIZE)
• {
• //满载 ,移除最近最少使用 （链表尾部）
• this->_curr_size--;
• this->_list.remove(_list.back());
• }
• _list.push_front(new Node(key, data));
• this->_curr_size++;
• cout << __FUNCTION__ << "Curr Size" << _curr_size << endl;
• }
• void print()
• {
• auto iter = this->_list.begin();
• while (iter != this->_list.end())
• {
• cout << "Key:" << (*iter)->_key << " Value:" << (*iter)->_data << endl;
• iter++;
• }
• }
• std::list <Node*> _list;
• unsigned int _curr_size = 0;
• };
• int main()
• {
• LRU_Cache*cache = new LRU_Cache;
• cache->addValue("111111", "data");
• cache->addValue("22222", "data");
• cache->addValue("333333", "data");
• cache->getValue("333333");
• cache->addValue("444444", "data");
• cout << cache->_curr_size;
• cache->print();
• system("pause");
• return 0;
• }

#include <iostream>
#include <list>
#include <string>
#include <algorithm>
using namespace std;




class Node
{
public:
	string _data;
	string _key;
	Node(string key, string data)
	{
		this->_data = data;
		this->_key = key;
	}
	void release(){ delete this; }
	Node(){}
};




/*
LRU = Least Recently Used的缩写，即最近最少使用的操作系统内存页面置换算法，利用该思想设计一个缓存

如果缓存满载后，把最近最少使用的从缓存中移除

基本思想：
用链表来维护，每次使用一个 缓存数据时吧该节点放到链表头部，
链表头到尾使用顺序依次递减，所以链表尾部是当前整个链表最少使用的。
利用链表的顺序来标记，使用情况，避免了用诸如使用时间来标记，性能大大提升。

添加缓存：吧添加的放到链表尾部，维护当前队列大小，如果满载，那么移除最少使用的
返回缓存：负责吧目标数据移到链表头部，表示当前使用的，

*/

#define  MAX_SIZE  3

class LRU_Cache
{

public:

	Node*getValue(const string & key)
	{

		Node* target = nullptr;

		// 查找，目标Node
		auto iter = this->_list.begin();

		while (iter != this->_list.end())
		{

			if ((*iter)->_key == key)
			{//查找成功，从链表中移除，然后添加到头部
				target = *iter;
				this->_list.erase(iter);
				_list.push_front(target);
				return target;
				break;

			}
			iter++;
		}

		return nullptr;

	}

	void addValue(const string & key, string data)
	{

		auto iter = this->_list.begin();

		while (iter != this->_list.end())
		{
			if ((*iter)->_key == key)
			{//已经存在
				return;

			}
			iter++;
		}

		if (this->_curr_size == MAX_SIZE)
		{
			//满载 ,移除最近最少使用 （链表尾部）
			this->_curr_size--;
			this->_list.remove(_list.back());
		}

		_list.push_front(new Node(key, data));
		this->_curr_size++;
		cout << __FUNCTION__ << "Curr Size" << _curr_size << endl;
	}

	void print()
	{
		auto iter = this->_list.begin();


		while (iter != this->_list.end())
		{

			cout << "Key:" << (*iter)->_key << "  Value:" << (*iter)->_data << endl;
			iter++;
		}


	}

	std::list <Node*> _list;

	unsigned int _curr_size = 0;

};




int main()
{
	LRU_Cache*cache = new LRU_Cache;
	cache->addValue("111111", "data");
	cache->addValue("22222", "data");
	cache->addValue("333333", "data");



	cache->getValue("333333");

	cache->addValue("444444", "data");


	cout << cache->_curr_size;
	cache->print();



	system("pause");
	return 0;
}