Cache满载的LRU置换

LRU（Least Recently Used，最近最少使用）是一种常见的操作系统内存页面置换算法，核心思想是：当缓存满载时，优先淘汰最近最少被访问的数据。

以下是一个基于链表的 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;
                }