最近最少使用数据结构(LRU)

抛开算法刷题的角度，LRU数据结构可根据访问时间远近自动排序，在有些场景下还是很有用的，如统计用户活跃度，API调用热力图分析，缓存块管理等。下面基于c++模板提供一个通用的LRU类，以供参考。

#include <functional>
#include <list>
#include <unordered_map>
#include <utility>template<typename Key, typename Val>
class LRUCache {
public:using value_deinit_callback = std::function<void(Key, Val)>;static void value_release_handle(Key k, Val v){}//如果Val是指针类型，可在func中指定指针清理动作LRUCache(int capacity, const value_deinit_callback& func = value_release_handle) :m_capacity(capacity), m_value_deinit(func){}~LRUCache(){for (auto pairs : m_cached_list){if (m_value_deinit.operator bool())m_value_deinit(pairs.first, pairs.second);}m_hash_table.clear();m_cached_list.clear();}Val get(const Key& key) {auto iter = m_hash_table.find(key);if (iter == m_hash_table.end())return Val{};auto& liter = iter->second;auto pairs = *liter;m_cached_list.erase(liter);liter = m_cached_list.insert(m_cached_list.end(), pairs);return liter->second;}void put(Key key, Val val) {auto iter = m_hash_table.find(key);if (iter != m_hash_table.end()){auto pairs = *iter->second;pairs.second = val;m_cached_list.erase(iter->second);iter->second = m_cached_list.insert(m_cached_list.end(),pairs);}else{if (m_cached_list.size() >= m_capacity){auto& pairs = m_cached_list.front();auto& fkey = pairs.first;auto& fval = pairs.second;auto it = m_hash_table.find(fkey);if (it != m_hash_table.end()){m_value_deinit(fkey, fval);m_hash_table.erase(it);}m_cached_list.pop_front();}m_hash_table.insert(std::make_pair(key, m_cached_list.insert(m_cached_list.end(), std::make_pair(key, val))));}}
private:int m_capacity;value_deinit_callback m_value_deinit;std::unordered_map<Key, typename std::list<std::pair<Key, Val>>::iterator> m_hash_table;std::list<std::pair<Key, Val>> m_cached_list;
};