本文是 https://my.oschina.net/kkkkkkkkkkkkk/blog/710261 的改进版本，将时间复杂度优化为 O(1)，底层采用双向链表与哈希表实现。
采用哈希表实现时，不适合存储大量数据；若数据量较大，需改用 std::map，时间复杂度将退化为 O(log n)。
/*
* Author: caoshanshan
* Email: me@dreamyouxi.com
LRU for manage cache
*/
#pragma once
#include "global_def.h"
#include <iostream>
#include <unordered_map>
#include <vector>
#include "base/memory.h"
#include <assert.h>
#if _DEBUG
//debug check
void LRUIncNodeRefCount();
void LRUDecNodeRefCount();
void LRUIncRefCount();
void LRUDecRefCount();
void LRUCheckRefCount();
#endif
/**
* @brief LRU for cache ,you can use this to manage your cache-data
* @note do not copy this
*/
//内部结构采用 std::unordered_map 不适用于 数量特别大的 结构
//大的结构需要用std::map 了 std::map 后面有需要的时候 再加吧
template<typename Key>
class LRUHashMap
{
//double-linked list for LRU
class delist_node
{
public:
delist_node()
{
#if _DEBUG
LRUIncNodeRefCount();
#endif
}
delist_node(const delist_node&other) = delete;
~delist_node()
{
#if _DEBUG
LRUIncNodeRefCount();
#endif
}
delist_node *pre = nullptr;
delist_node*next = nullptr;
Key data;
};
public:
LRUHashMap()
{
#if _DEBUG
LRUIncRefCount();
#endif
}
//disallow copy ctor
LRUHashMap(const LRUHashMap&other) = delete;
~LRUHashMap()
{
#if _DEBUG
Check();
LRUDecRefCount();
#endif
while (DeleteTail() > 1);
//head may be is equal to tail
if (head && head != tail)
{
delete head;
}
if (tail)
{
delete tail;
}
}
/**
* @brief use one element key
* @return elements's count in the LRU
*/
int Use(const Key & key)
{
#if _DEBUG
Check();
#endif
auto it_node = lru.find(key);
if (it_node == lru.end())
{
//has not find
auto node = new delist_node();
node->data = key;
node->next = head;
if (head)
{
head->pre = node;
}
head = node;
if (tail == nullptr)
{
tail = head;
}
lru[key] = node;
#if _DEBUG
Check();
#endif
return lru.size();
}
int size = lru.size();
delist_node *node = it_node->second;
//case 1
if (size == 1)
{
assert(head == tail);
assert(head->next == nullptr && head->pre == nullptr);
head = node;
tail = node;
assert(node->pre == nullptr);
assert(node->next == nullptr);
node->next = nullptr;
node->pre = nullptr;
}
//case 2
else if (size == 2)
{
assert(head != tail);
assert(head->next == tail);
assert(tail->pre == head);
assert(head->pre == nullptr && tail->next == nullptr);
if (head == node)
{
//use is head
assert(node->pre == nullptr);
}
else if (node == tail)
{
//use is tail
assert(node->next == nullptr);
assert(tail != head);
assert(head->next == tail);
assert(head->pre == nullptr);
assert(tail->pre == head);
assert(tail->next == nullptr);
auto tmp = head;
head = tail;
tail = tmp;
head->next = head->pre;
head->pre = nullptr;
tail->pre = tail->next;
tail->next = nullptr;
}
else
{
assert(false);
}
}
//case 3
else
{
if (node == head)
{
//use is head
}
else if (node == tail)
{
//use is tail
assert(node->next == nullptr);
assert(node->pre != nullptr);
auto tmp = tail;
tail = tail->pre;
tail->next = nullptr;
head->pre = tmp;
tmp->pre = nullptr;
tmp->next = head;
head = tmp;
}
else
{
assert(node->next);
assert(node->pre);
assert(node->next != node->pre);
node->next->pre = node->pre;
node->pre->next = node->next;
node->pre = nullptr;
head->pre = node;
node->next = head;
head = node;
}
}
#if _DEBUG
Check();
#endif
return lru.size();
}
/**
* @brief delete key use
*/
void Delete(const Key & key)
{
#if _DEBUG
Check();
#endif
int size = lru.size();
if (size == 0)
{
assert(head == nullptr);
assert(tail == nullptr);
head = nullptr;
tail = nullptr;
return;
}
else if (size == 1)
{
assert(head == tail);
assert(head->next == nullptr);
assert(head->pre == nullptr);
assert(tail->next == nullptr);
assert(tail->pre == nullptr);
if (head->data == key)
{
delete lru.begin()->second;
lru.clear();
head = nullptr;
tail = nullptr;
}
#if _DEBUG
Check();
#endif
return;
}
auto it_node = lru.find(key);
if (it_node == lru.end())
{
//this key is not exist ignore it
}
else
{
//has been exist
delist_node *node = it_node->second;
if (size == 2)
{
assert(head->pre == nullptr);
assert(tail->next == nullptr);
assert(head != tail);
if (head->data == key)
{
//delete is head
lru.erase(it_node);
delete head;
head = tail;
tail->pre = nullptr;
}
else if (tail->data == key)
{
//delete is tail
lru.erase(it_node);
delete tail;
tail = head;
head->next = nullptr;
}
else
{
assert(false);
}
}
else
{
//case 1
if (node == head)
{
//delete is head
assert(head->next);
assert(head->pre == nullptr);
auto new_head = head->next;
delete head;
head = new_head;
head->pre = nullptr;
lru.erase(it_node);
}
else if (node == tail)
{
//delete is tail
assert(node->next == nullptr);
assert(node->pre);
auto new_tail = node->pre;
delete tail;
lru.erase(it_node);
tail = new_tail;
tail->next = nullptr;
}
else
{
node->next->pre = node->pre;
node->pre->next = node->next;
delete node;
lru.erase(it_node);
}
}
}
#if _DEBUG
Check();
#endif
}
int Size()
{
return lru.size();
}
int DeleteTail()
{
#if _DEBUG
Check();
#endif
if (tail)
{
assert(lru.find(tail->data) != lru.end());
assert(tail->next == nullptr);
if (tail->pre)
{
assert(tail->pre->next == tail);
assert(lru.size() > 1);
lru.erase(tail->data);
auto new_tail = tail->pre;
new_tail->next = nullptr;
delete tail;
tail = new_tail;
}
else
{
assert(lru.size() == 1);
delete tail;
lru.clear();
tail = nullptr;
head = nullptr;
}
}
else
{
assert(lru.size() == 0);
lru.clear();
if (head)
{
assert(false);
delete head;
}
tail = nullptr;
head = nullptr;
}
#if _DEBUG
Check();
#endif
return lru.size();
}
bool HasTail()
{
return tail != nullptr;
}
/**
* @brief please call this after HasTail() == true
*/
const Key & GetTail()
{
if (tail)
{
return tail->data;
}
return Key();
}
#if _DEBUG
void Check()
{
if (lru.size() == 0)
{
assert(head == nullptr);
assert(tail == nullptr);
}
else if (lru.size() == 1)
{
assert(head&&head == tail);
assert(head->next == nullptr);
assert(head->pre == nullptr);
}
else if (lru.size() == 2)
{
assert(head != tail);
assert(head->next == tail);
assert(head->pre == nullptr);
assert(tail->next == nullptr);
assert(tail->pre == head);
}
else
{
//check head can reach tail
{
int loop = lru.size() + 3;
auto node = head;
while (node != tail)
{
--loop;
if (loop < 0)
{
assert(false);
}
node = node->next;
}
}
//check tail can reach head
{
int loop = lru.size() + 3;
auto node = tail;
while (node != head)
{
--loop;
if (loop < 0)
{
assert(false);
}
node = node->pre;
}
}
}
}
//------------------------------------------------------test case
void AutoTest()
{
Use(1);
Use(1);
Use(2);
Use(2);
Use(1);
for (int i = 0; i < 1000; i++)
{
Use(rand() % 10000 + 1);
if (rand() % 3 == 2)
{
Delete(rand() % 20000);
}
if (rand() % 10 == 3)
{
DeleteTail();
}
}
while (DeleteTail());
for (int i = 0; i < 3; i++)
{
Use(rand() % 10 + 1);
}
}
void PrintStatus()
{
std::vector <Key> _data;
{
auto node = head;
while (node)
{
// std::cout << node->data << std::endl;
_data.push_back(node->data);
node = node->next;
}
// std::cout << " 111 " << std::endl;
}
std::vector<Key>_data2;
_data2.resize(_data.size());
int index = _data.size();
{
auto node = tail;
while (node)
{
// std::cout << node->data << std::endl;
_data2[--index] = node->data;
node = node->pre;
}
// std::cout << " 222 " << std::endl;
}
{
//检查 乱序否
int id = _data2.size();
for (int i = 0; i < _data2.size(); i++)
{
assert(_data2[i] == _data[i]);
}
}
}
#endif
private:
std::unordered_map<Key, delist_node*> lru;
delist_node *head = nullptr;//least use
delist_node*tail = nullptr;// has long time not use
};