IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> 【C++】【缓存替换策略】【LRU】【LFU 】【FIFO】LRU算法C++实现，并测试； -> 正文阅读

[C++知识库]【C++】【缓存替换策略】【LRU】【LFU 】【FIFO】LRU算法C++实现，并测试；

目录

一、置换算法分类

  1. 先进先出算法 FIFO ；先进缓存的先被替换
  2. 最不经常使用算法 LFU ；淘汰最不常使用的字块；额外空间记录字块使用频率；
  3. 最近最少使用算法 LRU ； 优先淘汰一段时间内没使用的字块；一般使用双链表实现；把当前访问的节点放在表头（淘汰链表尾部）；

二、使用双向链表，实现置换算法

1、实现双向链表：

  1. 存放key-value、上一个节点指针、下一个节点指针；
  2. 接口：头部尾部增加节点；弹出头部、尾部节点；删除、增加任意节点；

template<typename Key, typename Value>
class Node {
public:
	Key key;
	Value val;
	Node *prev;
	Node *next;
public:
	Node(Key key, Value val)
	{
		this->key = key;
		this->val = val;
		this->next = nullptr;
		this->prev = nullptr;
	}
	Node()
	{

		this->next = nullptr;
		this->prev = nullptr;
	}
	Node(Key key, Value val, Node *prev, Node *next)
	{
		this->key = key;
		this->val = val;
		this->next = next;
		this->prev = prev;
	}
	//template<typename Key, typename Value>
	//friend ostream &operator<<(ostream &os, DoubleLinkedList<Key, Value>::Node &temp);

};
template<typename Key, typename Value>
class DoubleLinkedList {

public:
	
	DoubleLinkedList()
	{
		this->size = 0;
		this->head = nullptr;
		this->tail = nullptr;
	}


	pair<Key, Value> pop_front()
	{
		return removeHead();
	}
	pair<Key, Value> pop_back()
	{
		return removeTail();
	}
	pair<Key, Value> remove(Node<Key, Value>* node_)
	{
		return _remove(node_);
	}	
	Node<Key, Value>* append_back(Key key, Value val)
	{
		return addTail(key,val);
	}
	Node<Key, Value>* append_front(Key key, Value val)
	{
		return addHead(key, val);
	}

private:


	template<typename Key, typename Value>
	friend	ostream &operator<<(ostream &os, DoubleLinkedList<Key, Value> &temp);

	Node<Key,Value> *head;
	Node<Key, Value> *tail;
	int size;
	template<typename Key, typename Value>
	friend class Fifocache;

	Node<Key, Value> * addHead(Key key, Value val)
	{
		if (head == nullptr)
		{
			head = new Node<Key, Value>(key, val);
			tail = head;

		}
		else
		{
			Node<Key, Value> *temp = new Node<Key, Value>(key, val, nullptr, head);
			head->prev = temp;
			head = temp;

		}
		size++;
		return head;
	}
	Node<Key, Value> * addTail(Key key, Value val)
	{
		if (tail == nullptr)
		{
			head = new Node<Key, Value>(key, val);
			tail = head;

		}
		else
		{
			Node<Key, Value> *temp = new Node<Key, Value>(key, val, tail, nullptr);
			tail->next = temp;
			tail = temp;

		}
		size++;
		return tail;
	}

	pair<Key, Value> removeTail()
	{
		if (!tail) return { 0,0 };
		Key temp_k = tail->key;
		Value temp_v = tail->val;
		Node<Key, Value>* node_del = tail;
		if (tail->prev)
		{
			tail = tail->prev;
			tail->next = nullptr;
		}
		else
		{
			head = nullptr;
			tail = nullptr;
		}

		delete node_del;
		size--;
		return { temp_k ,temp_v };


	}
	pair<Key, Value> removeHead()
	{
		if (!head) return { 0,0 };
		Key temp_k = head->key;
		Value temp_v = head->val;
		Node<Key, Value>* node_del = head;
		if (head->next)
		{
			head = head->next;
			head->prev = nullptr;
		}
		else
		{
			head = nullptr;
			tail = nullptr;
		}

		delete node_del;
		size--;

		return { temp_k ,temp_v };


	}
	pair<Key, Value> _remove(Node<Key, Value>* node_)
	{
		if (node_)
		{
			if (node_ == tail) return removeTail();
			else if (node_ == tail) return removeHead();
			else
			{
				Key temp_k = node_->key;
				Value temp_v = node_->val;
				Node<Key, Value>* node_del = node_;
				node_->prev->next = node_->next;
				node_->next->prev = node_->prev;


				delete node_del;
				size--;
				return { temp_k ,temp_v };
			}
		}
		return { 0,0 };
	}


};

template<typename Key, typename Value>
ostream &operator<<(ostream &os, DoubleLinkedList<Key, Value> &temp)
{


	Node<Key, Value>  *head_ = temp.head;

	while (head_)
	{
		os << head_->key << " : " << head_->val << " -> ";
		head_ = head_->next;
	}
	os << endl;
	return os;

}
//template<typename Key, typename Value>
//ostream &operator<<(ostream &os, pair<Key, Value> &temp)
//{
//	os << temp.first << " : " << temp.second<<endl;
//	return os;
//}

void main()
{
	DoubleLinkedList<char, string > temp2;

	temp2.append_front('1', "asda");

	temp2.append_front('2', "abs");
	temp2.append_back('3', "assd");
	cout << temp2;
	temp2.pop_front();
	cout << temp2;
	temp2.pop_back();
	cout << temp2;

}

2、实现FIFO缓存置换算法：

较上部分双链表改了一些


template<typename Key, typename Value>
class Node {
public:
	Key key;
	Value val;
	Node *prev;
	Node *next;
public:
	Node(Key key, Value val)
	{
		this->key = key;
		this->val = val;
		this->next = nullptr;
		this->prev = nullptr;
	}
	Node()
	{

		this->next = nullptr;
		this->prev = nullptr;
	}
	Node(Key key, Value val, Node *prev, Node *next)
	{
		this->key = key;
		this->val = val;
		this->next = next;
		this->prev = prev;
	}
	//template<typename Key, typename Value>
	//friend ostream &operator<<(ostream &os, DoubleLinkedList<Key, Value>::Node &temp);

};
template<typename Key, typename Value>
class DoubleLinkedList {

public:
	
	DoubleLinkedList()
	{
		this->size = 0;
		this->head = nullptr;
		this->tail = nullptr;
	}


	pair<Key, Value> pop_front()
	{
		return removeHead();
	}
	pair<Key, Value> pop_back()
	{
		return removeTail();
	}
	pair<Key, Value> remove(Node<Key, Value>* node_)
	{
		return _remove(node_);
	}	
	Node<Key, Value>* append_back(Key key, Value val)
	{
		return addTail(key,val);
	}
	Node<Key, Value>* append_front(Key key, Value val)
	{
		return addHead(key, val);
	}

private:


	template<typename Key, typename Value>
	friend	ostream &operator<<(ostream &os, DoubleLinkedList<Key, Value> &temp);

	Node<Key,Value> *head;
	Node<Key, Value> *tail;
	int size;
	template<typename Key, typename Value>
	friend class Fifocache;

	Node<Key, Value> * addHead(Key key, Value val)
	{
		if (head == nullptr)
		{
			head = new Node<Key, Value>(key, val);
			tail = head;

		}
		else
		{
			Node<Key, Value> *temp = new Node<Key, Value>(key, val, nullptr, head);
			head->prev = temp;
			head = temp;

		}
		size++;
		return head;
	}
	Node<Key, Value> * addTail(Key key, Value val)
	{
		if (tail == nullptr)
		{
			head = new Node<Key, Value>(key, val);
			tail = head;

		}
		else
		{
			Node<Key, Value> *temp = new Node<Key, Value>(key, val, tail, nullptr);
			tail->next = temp;
			tail = temp;

		}
		size++;
		return tail;
	}

	pair<Key, Value> removeTail()
	{
		if (!tail) return { 0,0 };
		Key temp_k = tail->key;
		Value temp_v = tail->val;
		Node<Key, Value>* node_del = tail;
		if (tail->prev)
		{
			tail = tail->prev;
			tail->next = nullptr;
		}
		else
		{
			head = nullptr;
			tail = nullptr;
		}

		delete node_del;
		size--;
		return { temp_k ,temp_v };


	}
	pair<Key, Value> removeHead()
	{
		if (!head) return { 0,0 };
		Key temp_k = head->key;
		Value temp_v = head->val;
		Node<Key, Value>* node_del = head;
		if (head->next)
		{
			head = head->next;
			head->prev = nullptr;
		}
		else
		{
			head = nullptr;
			tail = nullptr;
		}

		delete node_del;
		size--;

		return { temp_k ,temp_v };


	}
	pair<Key, Value> _remove(Node<Key, Value>* node_)
	{
		if (node_)
		{
			if (node_ == tail) return removeTail();
			else if (node_ == tail) return removeHead();
			else
			{
				Key temp_k = node_->key;
				Value temp_v = node_->val;
				Node<Key, Value>* node_del = node_;
				node_->prev->next = node_->next;
				node_->next->prev = node_->prev;


				delete node_del;
				size--;
				return { temp_k ,temp_v };
			}
		}
		return { 0,0 };
	}


};

template<typename Key, typename Value>
ostream &operator<<(ostream &os, DoubleLinkedList<Key, Value> &temp)
{


	Node<Key, Value>  *head_ = temp.head;

	while (head_)
	{
		os << head_->key << " : " << head_->val << " -> ";
		head_ = head_->next;
	}
	os << endl;
	return os;

}
//template<typename Key, typename Value>
//ostream &operator<<(ostream &os, pair<Key, Value> &temp)
//{
//	os << temp.first << " : " << temp.second<<endl;
//	return os;
//}

template<typename Key, typename Value>
class Fifocache {
private:
	int capacity;
	int size;
	unordered_map<Key, Node<Key, Value>*> _hash;
	DoubleLinkedList<Key, Value> _list;

public:
	Fifocache(int cap): capacity(cap), size(0){}

	Value get(Key key)
	{
		if (_hash.find(key) != _hash.end())
			return _hash[key]->val;
		else
			return NULL;
	}

	void put(Key key, Value val)
	{
		if (_hash.find(key) != _hash.end())
		{
			_list.remove(_hash[key]);
			_hash[key] = _list.append_back(key, val);
			
		}
		else
		{
			if (size == capacity)
			{
				auto [key1,_] = _list.pop_front();
				_hash.erase(key1);
				size--;
			}
			_hash[key] = _list.append_back(key, val);
			size++;
		}
	}




};





void main()
{
	DoubleLinkedList<char, string > temp2;

	temp2.append_front('1', "asda");

	temp2.append_front('2', "abs");
	temp2.append_back('3', "assd");
	cout << temp2;
	temp2.pop_front();
	cout << temp2;
	temp2.pop_back();
	cout << temp2;

	Fifocache<char, string> temp3(4);
	temp3.put('2', "abs");
	cout<<temp3.get('2');
}

3、LRU缓存置换算法（最近最少使用算法）

即将使用的块，链接到头部，新插入的块插在头部，并把尾部删除；尾部是使用最少的。
在这里插入图片描述


template<typename Key, typename Value>
class Node {
public:
	Key key;
	Value val;
	Node *prev;
	Node *next;
public:
	Node(Key key, Value val)
	{
		this->key = key;
		this->val = val;
		this->next = nullptr;
		this->prev = nullptr;
	}
	Node()
	{

		this->next = nullptr;
		this->prev = nullptr;
	}
	Node(Key key, Value val, Node *prev, Node *next)
	{
		this->key = key;
		this->val = val;
		this->next = next;
		this->prev = prev;
	}
	//template<typename Key, typename Value>
	//friend ostream &operator<<(ostream &os, Node &temp);

};
template<typename Key, typename Value>
class DoubleLinkedList {

public:
	
	DoubleLinkedList()
	{
		this->size = 0;
		this->head = nullptr;
		this->tail = nullptr;
	}


	pair<Key, Value> pop_front()
	{
		return removeHead();
	}
	pair<Key, Value> pop_back()
	{
		return removeTail();
	}
	pair<Key, Value> remove(Node<Key, Value>* node_)
	{
		return _remove(node_);
	}	
	Node<Key, Value>* append_back(Key key, Value val)
	{
		return addTail(key,val);
	}
	Node<Key, Value>* append_front(Key key, Value val)
	{
		return addHead(key, val);
	}

private:


	template<typename Key, typename Value>
	friend	ostream &operator<<(ostream &os, DoubleLinkedList<Key, Value> &temp);

	Node<Key,Value> *head;
	Node<Key, Value> *tail;
	int size;
	template<typename Key, typename Value>
	friend class Fifocache;

	Node<Key, Value> * addHead(Key key, Value val)
	{
		if (head == nullptr)
		{
			head = new Node<Key, Value>(key, val);
			tail = head;

		}
		else
		{
			Node<Key, Value> *temp = new Node<Key, Value>(key, val, nullptr, head);
			head->prev = temp;
			head = temp;

		}
		size++;
		return head;
	}
	Node<Key, Value> * addTail(Key key, Value val)
	{
		if (tail == nullptr)
		{
			head = new Node<Key, Value>(key, val);
			tail = head;

		}
		else
		{
			Node<Key, Value> *temp = new Node<Key, Value>(key, val, tail, nullptr);
			tail->next = temp;
			tail = temp;

		}
		size++;
		return tail;
	}

	pair<Key, Value> removeTail()
	{
		if (!tail) return { 0,0 };
		Key temp_k = tail->key;
		Value temp_v = tail->val;
		Node<Key, Value>* node_del = tail;
		if (tail->prev)
		{
			tail = tail->prev;
			tail->next = nullptr;
		}
		else
		{
			head = nullptr;
			tail = nullptr;
		}

		delete node_del;
		size--;
		return { temp_k ,temp_v };


	}
	pair<Key, Value> removeHead()
	{
		if (!head) return { 0,0 };
		Key temp_k = head->key;
		Value temp_v = head->val;
		Node<Key, Value>* node_del = head;
		if (head->next)
		{
			head = head->next;
			head->prev = nullptr;
		}
		else
		{
			head = nullptr;
			tail = nullptr;
		}

		delete node_del;
		size--;

		return { temp_k ,temp_v };


	}
	pair<Key, Value> _remove(Node<Key, Value>* node_)
	{
		if (node_)
		{
			if (node_ == tail) return removeTail();
			else if (node_ == head) return removeHead();
			else
			{
				Key temp_k = node_->key;
				Value temp_v = node_->val;
				Node<Key, Value>* node_del = node_;
				node_->prev->next = node_->next;
				node_->next->prev = node_->prev;


				delete node_del;
				size--;
				return { temp_k ,temp_v };
			}
		}
		return { 0,0 };
	}


};

template<typename Key, typename Value>
ostream &operator<<(ostream &os, DoubleLinkedList<Key, Value> &temp)
{
	Node<Key, Value>  *head_ = temp.head;

	while (head_)
	{
		os << head_->key << " : " << head_->val << " -> ";
		head_ = head_->next;
	}
	os << endl;
	return os;

}
//template<typename Key, typename Value>
//ostream &operator<<(ostream &os, Node<Key, Value> &temp)
//{
//	os << temp.key << " : " << temp.val<<endl;
//	return os;
//}

template<typename Key, typename Value>
class LruCache {
private:
	int capacity;
	int size;
	unordered_map<Key, Node<Key, Value>*> _hash;
	DoubleLinkedList<Key, Value> _list;
	template<typename Key, typename Value>
	friend ostream &operator<<(ostream &os, LruCache<Key, Value> &temp);
public:
	LruCache(int cap): capacity(cap), size(0){}

	Value get(Key key)
	{
		if (_hash.find(key) != _hash.end())
		{
			Value tmp = _hash[key]->val;
			_list.remove(_hash[key]);
			_hash[key] = _list.append_front(key, tmp);

			return tmp;
		}
		else
			return NULL;
	}

	void put(Key key, Value val)
	{
		if (_hash.find(key) != _hash.end())
		{
			_list.remove(_hash[key]);
			_hash[key] = _list.append_front(key, val);
			
		}
		else
		{
			if (size == capacity)
			{
				auto [key1,_] = _list.pop_back();
				_hash.erase(key1);
				size--;
			}
			_hash[key] = _list.append_front(key, val);
			size++;
		}
	}




};
template<typename Key, typename Value>
ostream &operator<<(ostream &os, LruCache<Key, Value> &temp)
{
	os << temp._list << endl;
	return os;
}

void main()
{
	LruCache<char, char> temp3(2);
	temp3.put('1', 'a');
	cout << temp3;
	temp3.put('2', 'b');
	cout << temp3;
	temp3.put('3', 'c');
	cout << temp3;
	cout << "temp3.get('2')" << temp3.get('2') << endl<<endl;
	cout << temp3;
	cout << "temp3.get('3')" << temp3.get('3') << endl << endl;;
	cout << temp3;

}

三、LRU算法实现效果

  1. 我们新插入的，将会放在头部；
  2. 插入大于容量的，将会插入头部，并将尾部数据弹出；
  3. 我们新访问过的，将会放在头部；

下面实现可以看出，已经实现了相应逻辑效果

1 : a ->

2 : b -> 1 : a ->

3 : c -> 2 : b ->

temp3.get('2')b

2 : b -> 3 : c ->

temp3.get('3')c

3 : c -> 2 : b ->
  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现（C语言)
C++PrimerPlus 第七章 函数-C++的编程模块（
Problem C: 算法9-9~9-12：平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇（六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2021-07-04 21:12:22  更:2021-07-04 21:13:26 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年5日历 -2024/5/4 10:51:45-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码