LRU 实现
LRU:
Least recently used, 最近最少(least)使用: 对于当前所有缓存, 后续使用时, 缓存满的时候,
最近使用的缓存被移除的概率最小(最后被移除)! .. 即缓存满的时候最先移除最近最少使用的!
(Discards the least recently used items first, i.e. once a cache used, then it least likely to be removed when caches full!!)
参考: https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU
C++ 实现: 使用双链表存储缓存以及使用 hash map 查找缓存!
See also:
template<typename K, typename V>
class LruCache {
public:
/// Internal cache type.
using Cache = std::tuple<K, V>;
/// Cache datas type.
using Caches = DoublyLinkedList<Cache>;
/// Key to cache iterator type.
using KeyCaches = std::unordered_map<K, typename Caches::Iterator>;
/// Default ctor.
LruCache() noexcept;
/// Dtor
~LruCache() noexcept;
/// @return caches capacity.
inline int32_t getCapacity() const noexcept;
/// @return current caches size.
inline int32_t getSize() const noexcept;
/// Check whether this caches empty.
inline bool isEmpty() const noexcept;
/**
* Set cache capacity.
* @param capacity the capacity to set, NOTE: should >= current caches
* and > 0.
* @return true when set success, otherwise false.
*/
inline bool setCapacity(const int32_t capacity) noexcept;
/**
* Set or update cache of key.
* @param key the key to set.
* @param value the value to set.
*/
void set(K&& key, V&& value) noexcept;
void set(const K& key, V&& value) noexcept;
void set(K&& key, const V& value) noexcept;
void set(const K& key, const V& value) noexcept;
/// Check whether has cache of key.
inline bool has(const K& key) const noexcept;
/**
* Get cache of key.
* @param key the key to get cache.
* @return the cache of key.
* @return true when success otherwise false.
*/
bool get(const K& key, V& value) const noexcept;
/**
* Get cache of key, if not exists, value is default.
* @param key the key to get cache.
* @return the cache of key.
* @sa
* - has
* - get
* - set
*/
V& operator[](const K& key) noexcept;
/// @throw std::logic_error when no such key.
const V& operator[](const K& key) const;
/// @return caches.
inline const Caches& getCaches() const noexcept;
/// Clear all caches.
inline void clear() noexcept;
private:
mutable Caches caches;///< The cache datas.
KeyCaches keyCaches;///< { key, cacheIterator }.
int32_t capacity{ 16 };///< The capacity of cache(max caches), default 16.
};
template<typename K, typename V>
LruCache<K, V>::LruCache() noexcept {}
template<typename K, typename V>
LruCache<K, V>::~LruCache() noexcept {}
template<typename K, typename V>
inline int32_t LruCache<K, V>::getCapacity() const noexcept
{
return this->capacity;
}
template<typename K, typename V>
inline int32_t LruCache<K, V>::getSize() const noexcept
{
return this->caches.size();
}
template<typename K, typename V>
inline bool LruCache<K, V>::isEmpty() const noexcept
{
return this->caches.empty();
}
template<typename K, typename V>
bool LruCache<K, V>::setCapacity(const int32_t capacity) noexcept
{
if (capacity < 1) {
return false;
}
if (uint32_t(capacity) < this->caches.size()) {
return false;
}
this->capacity = capacity;
return true;
}
template<typename K, typename V>
void LruCache<K, V>::set(K&& key, V&& value) noexcept
{
const auto kCIt = this->keyCaches.find(key);
if (kCIt != this->keyCaches.end()) {
auto& cacheIt = kCIt->second;
std::get<1>(*cacheIt) = std::move(value);
this->caches.rewire_to_front(cacheIt);
} else {
if (int32_t(this->keyCaches.size()) >= this->capacity) {
auto const& back = this->caches.back();
this->keyCaches.erase(std::get<0>(back));
this->caches.pop_back();
}
this->caches.push_front(Cache{ key, std::move(value) });
this->keyCaches[std::move(key)] = this->caches.begin();
}
}
template<typename K, typename V>
void LruCache<K, V>::set(const K& key, V&& value) noexcept
{
const auto kCIt = this->keyCaches.find(key);
if (kCIt != this->keyCaches.end()) {
auto& cacheIt = kCIt->second;
std::get<1>(*cacheIt) = std::move(value);
this->caches.rewire_to_front(cacheIt);
} else {
if (int32_t(this->keyCaches.size()) >= this->capacity) {
auto const& back = this->caches.back();
this->keyCaches.erase(std::get<0>(back));
this->caches.pop_back();
}
this->caches.push_front(Cache{ key, std::move(value) });
this->keyCaches[key] = this->caches.begin();
}
}
template<typename K, typename V>
void LruCache<K, V>::set(K&& key, const V& value) noexcept
{
const auto kCIt = this->keyCaches.find(key);
if (kCIt != this->keyCaches.end()) {
auto& cacheIt = kCIt->second;
std::get<1>(*cacheIt) = value;
this->caches.rewire_to_front(cacheIt);
} else {
if (int32_t(this->keyCaches.size()) >= this->capacity) {
auto const& back = this->caches.back();
this->keyCaches.erase(std::get<0>(back));
this->caches.pop_back();
}
this->caches.push_front(Cache{ key, value });
this->keyCaches[std::move(key)] = this->caches.begin();
}
}
template<typename K, typename V>
void LruCache<K, V>::set(const K& key, const V& value) noexcept
{
const auto kCIt = this->keyCaches.find(key);
if (kCIt != this->keyCaches.end()) {
auto& cacheIt = kCIt->second;
std::get<1>(*cacheIt) = value;
this->caches.rewire_to_front(cacheIt);
} else {
if (int32_t(this->keyCaches.size()) >= this->capacity) {
auto const& back = this->caches.back();
this->keyCaches.erase(std::get<0>(back));
this->caches.pop_back();
}
this->caches.push_front(Cache{ key, value });
this->keyCaches[key] = this->caches.begin();
}
}
template<typename K, typename V>
inline bool LruCache<K, V>::has(const K& key) const noexcept
{
return this->keyCaches.find(key) != keyCaches.end();
}
template<typename K, typename V>
bool LruCache<K, V>::get(const K& key, V& value) const noexcept
{
const auto kCIt = this->keyCaches.find(key);
if (kCIt == this->keyCaches.end()) {
return false;
}
const auto& cacheIt = kCIt->second;
this->caches.rewire_to_front(cacheIt);
value = std::get<1>(*cacheIt);
return true;
}
template<typename K, typename V>
V& LruCache<K, V>::operator[](const K& key) noexcept
{
auto kCIt = this->keyCaches.find(key);
if (kCIt == this->keyCaches.end()) {
this->set(key, V{});
kCIt = this->keyCaches.find(key);
}
auto& cacheIt = kCIt->second;
this->caches.rewire_to_front(cacheIt);
return std::get<1>(*cacheIt);
}
template<typename K, typename V>
const V& LruCache<K, V>::operator[](const K& key) const
{
const auto kCIt = this->keyCaches.find(key);
if (kCIt == this->keyCaches.end()) {
throw std::logic_error("no such key");
}
const auto& cacheIt = kCIt->second;
this->caches.rewire_to_front(cacheIt);
return std::get<1>(*cacheIt);
}
template<typename K, typename V>
inline const typename LruCache<K, V>::Caches&
LruCache<K, V>::getCaches() const noexcept
{
return this->caches;
}
template<typename K, typename V>
inline void LruCache<K, V>::clear() noexcept
{
this->caches.clear();
this->keyCaches.clear();
}
template<typename K, typename V>
std::ostream& operator<<(
std::ostream& os, const LruCache<K, V>& lruCache) noexcept
{
const auto& caches = lruCache.getCaches();
os << "capacity " << lruCache.getCapacity();
const int32_t size = lruCache.getSize();
os << ", size " << size;
if (size > 0) {
os << ": ";
}
for (const auto& cache : caches) {
os << '(' << std::get<0>(cache) << ',' << std::get<1>(cache) << ") ";
}
return os;
}