This is a simple and robust LRUCache implementation using doubly linked list and unordered map. It supports .get()
, .put()
, and .has()
operations in constant time.
I want to know if my code conforms to the best practices. Any suggestions or feedback are appreciated!
#pragma once
#include <list>
#include <unordered_map>
namespace cache {
template <typename KeyType,
typename ValueType,
typename KeyHash = std::hash<KeyType>,
typename KeyEqual = std::equal_to<KeyType>>
class LRUCache {
private:
using KeyValuePair = std::pair<KeyType, ValueType>;
using ListIterator = typename std::list<KeyValuePair>::iterator;
const size_t maxSize_;
std::unordered_map<KeyType, ListIterator> hashmap_;
std::list<KeyValuePair> itemsList_;
void promoteItemWithKey(const KeyType& key)
{
ListIterator keyIterator = hashmap_[key];
if (std::next(keyIterator) == itemsList_.end()) {
return;
}
std::iter_swap(keyIterator, std::next(keyIterator));
hashmap_[key] = std::next(keyIterator);
hashmap_[keyIterator->first] = keyIterator;
}
void removeItemWithKey(const KeyType& key)
{
itemsList_.erase(hashmap_[key]);
hashmap_.erase(key);
}
public:
LRUCache(size_t maxSize)
: maxSize_(maxSize) {};
bool has(const KeyType& key) const
{
return hashmap_.find(key) != hashmap_.end();
}
ValueType get(const KeyType& key)
{
if (!this->has(key))
throw std::range_error("The key doesn't exist in the cache.");
this->promoteItemWithKey(key);
return hashmap_[key]->second;
}
void put(const KeyType& key, const ValueType& value)
{
if (this->has(key)) {
this->removeItemWithKey(key);
}
if (itemsList_.size() == maxSize_) {
hashmap_.erase(itemsList_.begin()->first);
itemsList_.pop_front();
}
itemsList_.emplace_back(std::pair<KeyType, ValueType>(key, value));
hashmap_[key] = std::next(itemsList_.end(), -1);
}
size_t size() const
{
return itemsList_.size();
}
size_t capacity() const noexcept
{
return maxSize_;
}
};
}
main()
that shows this class in use? \$\endgroup\$