LRU.h#pragma once #include cassert #include functional #include list #include map #include utility namespace cpv { /** * A cache type that keeps up to given number of least recently used values. * * Notice: * Its not thread safe, dont use it across threads without mutex. */ template class Key, class Value, class List std::liststd::pairKey, Value, // use ordered map and std::less by default for heterogeneous lookup class Map std::mapKey, typename List::iterator, std::less class LRUCache { public: /** Associate value with key, remove finally not used value if size is over */ template class TKey, class TValue void set(TKey keyForMap, TKey keyForList, TValue value) { assert(keyForMap keyForList); auto it map_.find(keyForMap); if (it ! map_.end()) { list_.erase(it-second); map_.erase(it); } list_.emplace_front( std::forwardTKey(keyForList), std::forwardTValue(value)); map_.emplace(std::forwardTKey(keyForMap), list_.begin()); if (map_.size() maxSize_) { map_.erase(list_.back().first); list_.pop_back(); } } /** Associate value with key, remove finally not used value if size is over */ template class TKey, class TValue void set(const TKey key, TValue value) { set(TKey(key), TKey(key), std::forwardTValue(value)); } /** Associate value with key, remove finally not used value if size is over */ void set(Key keyForMap, Key keyForList, Value value) { assert(keyForMap keyForList); setKey, Value(std::move(keyForMap), std::move(keyForList), std::move(value)); } /** Associate value with key, remove finally not used value if size is over */ void set(const Key key, Value value) { setKey, Value(Key(key), Key(key), std::move(value)); } /** Get pointer of value associated with key or return nullptr */ template class TKey Value* get(TKey key) { auto it map_.find(std::forwardTKey(key)); if (it map_.end()) { return nullptr; } else { list_.splice(list_.begin(), list_, it-second); return it-second-second; } } /** Get pointer of value associated with key or return nullptr */ Value* get(const Key key) { return getconst Key(key); } /** Erase value associated with key, return whether key was exists */ template class TKey bool erase(TKey key) { auto it map_.find(std::forwardTKey(key)); if (it map_.end()) { return false; } else { list_.erase(it-second); map_.erase(it); return true; } } /** Erase value associated with key, return whether key was exists */ bool erase(const Key key) { return eraseconst Key(key); } /** Erase all values in cache */ void clear() { list_.clear(); map_.clear(); } /** Get the number of values in cache */ std::size_t size() const { return map_.size(); } /** Get the maximum number of values allow to keep in cache */ std::size_t maxSize() const { return maxSize_; } /** Return whether the cache is empty */ bool empty() const { return map_.empty(); } /** Construct with max number of values allow to keep in cache */ LRUCache(std::size_t maxSize) : list_(), map_(), maxSize_(maxSize) { } private: List list_; Map map_; std::size_t maxSize_; }; }#include LRU.h #include assert #include string void test() { cpv::LRUCacheint, std::string cache(3); cache.set(1, a); cache.set(2, b); cache.set(3, c); cache.set(100, abc); std::string* result cache.get(1); assert(result nullptr); }注意此LRU只实现了最近访问优先缓存LFU高频访问时需自行扩展list的访问次数GitHub - mohaps/lrucache11: A header only C11 LRU Cache template class that allows you to define key, value and optionally the Map type. uses a double linked list and a std::unordered_map style container to provide fast insert, delete and update No dependencies other than the C standard library. This is a C11 remake of my earlier LRUCache project (https://github.com/mohaps/lrucache) The goal was to create a fast LRUCache header only library and to avoid any dependencies like boost.创作不易小小的支持一下吧