Thanks for the simple and efficient implementation!
Here is my solution based on your work.
#pragma once
#ifndef LEVIDB_LRU_CACHE_H
#define LEVIDB_LRU_CACHE_H
/*
* Original File: lrucache.hpp
* Original Author: Alexander Ponomarev
*/
#include <list>
#include <unordered_map>
#include <utility>
namespace levidb {
template<typename K, typename V, size_t MAX>
class LRUCache {
private:
typedef typename std::pair<K, V> key_value_pair_t;
typedef typename std::list<key_value_pair_t>::iterator list_iterator_t;
std::list<key_value_pair_t> cache_items_list_;
std::unordered_map<K, list_iterator_t> cache_items_map_;
public:
template<typename T>
void Add(const K & k, T && v) {
auto it = cache_items_map_.find(k);
if (it == cache_items_map_.end()) {
if (size() >= MAX) {
auto last = cache_items_list_.end();
--last;
#if defined(__cpp_lib_node_extract)
auto nh = cache_items_map_.extract(last->first);
nh.key() = k;
cache_items_map_.insert(std::move(nh));
last->first = k;
last->second = std::forward<T>(v);
cache_items_list_.splice(cache_items_list_.begin(), cache_items_list_, last);
return;
#else
cache_items_map_.erase(last->first);
cache_items_list_.pop_back();
#endif
}
cache_items_list_.emplace_front(k, std::forward<T>(v));
cache_items_map_[k] = cache_items_list_.begin();
} else {
it->second->second = std::forward<T>(v);
cache_items_list_.splice(cache_items_list_.begin(), cache_items_list_, it->second);
}
}
bool Get(const K & k, V * v) const {
auto it = cache_items_map_.find(k);
if (it == cache_items_map_.cend()) {
return false;
} else {
const_cast<LRUCache *>(this)->
cache_items_list_.splice(cache_items_list_.begin(), cache_items_list_, it->second);
*v = it->second->second;
return true;
}
}
bool Exists(const K & k) const {
return cache_items_map_.find(k) != cache_items_map_.cend();
}
size_t size() const {
return cache_items_map_.size();
}
};
}
#endif //LEVIDB_LRU_CACHE_H
Thanks for the simple and efficient implementation!
Here is my solution based on your work.