LRU Cache in C++11

Question

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_;
 }
};
}

• Toby Speight: Do you have some tests, or at least a simple main() that shows this class in use?

Answer 1

Headers

We're missing some headers. I'm guessing that your platform happens to include these as a side-effect of including <list> and <unordered_map>, but that's not a portable assumption.

#include <algorithm> // for std::iter_swap
#include <cstddef> // for std::size_t
#include <functional> // for std::equal_to and std::hash
#include <iterator> // for std::next
#include <stdexcept> // for std::range_error
#include <utility> // for std::pair

Size member

We've consistently misspelt std::size_t (as just size_t). Again, another portability problem.

We might want to check that we are not given a zero size; doing so will break the code's assumptions in put(). We could test and throw, or we could use std::min to ensure it's at least 1, for example.

The accessor capacity() is fairly pointless - we could simply make the maxSize_ member public (which is safe, because it's declared const).

Strange promotion isn't LRU

Despite the name, this cache doesn't discard the least-recently used item to make space, as promoteItemWithKey only swaps the used item with the next one in the list. True LRU means moving the accessed item to the end of the queue; I think you might be able to use the list's splice() method to achieve this more efficiently than std::rotate.

Unnecessary explicit this

The redundant this-> dereference can make code harder to read:

 if (this->has(key)) {
 this->removeItemWithKey(key);
 }

It's rare that we need to explicitly write this-> (usually only if we have name conflicts, or call a non-dependent template function), and we can write with much less clutter:

 if (has(key)) {
 removeItemWithKey(key);
 }

That said, I would prefer us to directly overwrite (and promote) the found element, rather than removing it and constructing a new one - that saves on memory allocation. In fact, the same applies when removing a stale item to insert a new one -

Unnecessary construction

Here, we have an unwieldy constructor that we don't need:

 itemsList_.emplace_back(std::pair<KeyType, ValueType>(key, value));

The point of emplace_back() is to call the constructor for us:

 itemsList_.emplace_back(key, value);

Consider passing by value

If we put() with an rvalue for value, it's copied unnecessarily. It's probably better to push any copying to the caller (which may be able to elide it), and then std::move the value:

void put(const KeyType& key, ValueType value)
{
 // ...
 itemsList_.emplace_back(key, std::move(value));