Cache满载的LRU置换

用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;
}