7
\$\begingroup\$

I’m implementing a templated LRU cache in C++17 and C++20. High-level design:

Recency: std::list<Key> (most-recent at the front).

Lookup: std::unordered_map<Key, std::pair<Value, std::list<Key>::const_iterator>>.

Behavior: promote on access/update; evict from tail on insert when full. Target: O(1) average for all ops.

Public API (simplified):

insertKeyValuePair(Key key, Value value) — insert or update, promote to most-recent

getValueFromKey(const Key& key) — return the value and promote on hit

getMostRecentKey() const — peek the most-recent key (no reordering)

Could you please review this code for simplicity, efficiency, and the best way to signal “empty / key not found” without unnecessary copies?

I’d also appreciate guidance on alternative return mechanisms (e.g., exceptions vs. std::optional vs. pointer)

https://godbolt.org/z/aE7EE3j5W

#include <cassert>
#include <list>
#include <cstddef>
#include <stdexcept>
#include <iostream>
#include <optional>
#include <unordered_map>
#include <print>


template <typename Key, typename Value, typename Hash = std::hash<Key>>
class LRUCache {
public:
    using size_type = std::size_t;
    using key_type = Key;
    using value_type = Value;

    explicit LRUCache(size_type capacity)
        : m_capacity(capacity > 0 ? capacity : throw std::invalid_argument("capacity must be > 0"))
    {
        assert(m_capacity > 0 && "capacity must be > 0");
        m_lookup.reserve(m_capacity);
    }

    /************************getMostRecentKey***************************************/
    // Q: are universal references better choice?
    void insertKeyValuePair(key_type key, value_type value) {

        if (auto it = m_lookup.find(key); it != m_lookup.end()) {
            m_cache.splice(m_cache.begin(), m_cache, it->second.second);
            it->second.first = std::move(value);
            return;
        }
        else if (!m_lookup.empty() && m_lookup.size() == m_capacity) {
            m_lookup.erase(m_cache.back());
            m_cache.pop_back();
        }
        m_cache.push_front(key);
        // Q emplace or insert?
        m_lookup.emplace(std::move(key), std::make_pair(std::move(value), m_cache.begin()));

    }

    /************************getMostRecentKey****************************************/
    [[nodiscard("use the key or handle the exception")]] const key_type&
        getMostRecentKey() const {
        if (m_cache.empty()) {
            throw std::runtime_error("Cache is empty.");
        }
        return m_cache.front();
    }

    /************************getValueFromKey****************************************/
    [[nodiscard]] decltype(auto)
        getValueFromKey(const key_type& key) {
        if (m_lookup.empty()) {
            throw std::runtime_error("Cache is empty.");
        }

        if (auto it = m_lookup.find(key); it != m_lookup.end()) {
            m_cache.splice(m_cache.begin(), m_cache, it->second.second);
            return it->second.first;
        }
        throw std::runtime_error("Key not found.");
    }
    /************************size()****************************************/

    size_type size() const noexcept {
        return m_lookup.size();
    }
    size_type capacity() const noexcept {
        return m_capacity;
    }
#if 0 // Alternatives
    [[nodiscard]] std::optional<key_type>
        getMostRecentKey_() const noexcept {
        if (m_keysByRecency.empty()) {
            return std::nullopt;
        }
        return m_keysByRecency.front();
    }

    [[nodiscard]] const key_type*
        getMostRecentKey__() const noexcept {
        return m_keysByRecency.empty() ? nullptr : &m_keysByRecency.front();
    }
#endif
    // Data--------------------------------------------------------------
private:
    size_type       m_capacity;
    using Cache   = std::list<key_type>;
    using NodeIt  = Cache::const_iterator;
    using Node    = std::pair<value_type, NodeIt>;
    using Lookup  = std::unordered_map<key_type, Node,Hash>;
    Lookup m_lookup;
    Cache m_cache;
};
\$\endgroup\$
4
  • \$\begingroup\$ I’m voting to close this question because the code presented doesn't compile under C++17 with the presented compiler (GCC 15.2). <print> is a c++23 library, annotated [[nodiscard(string_literal)]] is a C++20 feature, and contextual implicit typename is a C++20 feature. \$\endgroup\$ Commented Nov 14 at 22:48
  • \$\begingroup\$ what do you mean by "the presented compiler"? I’m not sure where you ran the code, but the Compiler Explorer link in my post is already set to C++23, and it compiles there without issues. I included that link specifically so no one would need to copy the code into a local IDE. It looks like the link may have been overlooked, which might explain the confusion. Also, I can’t set the question title to “C++23” just because I used printf; that’s not a C++23-specific feature, so it wouldn’t be an accurate title. \$\endgroup\$ Commented Nov 15 at 2:28
  • \$\begingroup\$ This is stated as intended to compile in C++17. \$\endgroup\$ Commented Nov 15 at 16:07
  • 2
    \$\begingroup\$ @DavislorI think I should be able to edit my post BEFORE any responses are posted. I did not change anything about my code after responses were posted, which is the case here! \$\endgroup\$ Commented Nov 16 at 3:02

3 Answers 3

Reset to default
5
\$\begingroup\$

Copy the interface of std::unordered_map

An LRU cache is basically an unordered map, with the only differences being a limited capacity and a replacement policy when trying to add more elements than its capacity. So I would recommend you implement the exact same interface that std::unordered_map has. This will have some benefits:

  • C++ programmers are already familiar with this interface
  • It will be a drop-in replacement for std::unordered_map
  • You can use lots of other standard library features that work with unordered maps on your LRU

To get access to the elements in the LRU order, I would make sure begin(), end() and related functions use the underlying std::list, and you could add front() and back() as well.

So then your API will become:

  • insert(const std::pair<Key, Value>&), emplace(auto&&... args), try_emplace(const Key&, auto&&... args) etc. instead of insertKeyValuePair()
  • at(const Key&), operator[](const Key&) and find(const Key&) instead of getValueFromKey()
  • *begin() and front() instead of getMostRecentKey()

Efficiency

With std::unordered_map and std::list you have \$O(1)\$ time complexity, but there can be quite a bit of overhead because every node in the map and the list will be allocated separately. It would be more efficient if you could just allocate one block of memory for the map and the list. You could implement something like std::flat_map but augmented to maintain the priority list as well.

Using std::optional

Unfortunately std::optional was very late to the game, so the standard containers have used different ways of signaling whether an element could be retrieved or not. However, if you do want that, I suggest just creating a stand-alone function that gives you the desired interface but which can work on any container, for example:

template<typename Container, typename Key>
std::optional<Container::mapped_type> get(const Container& container, const Key& key) {
    if (auto it = container.find(key); it != container.end()) {
        return it->second;
    } else {
        return std::nullopt;
    }
}

Pick one version of C++

I’m implementing a templated LRU cache in C++17 and C++20.

That doesn't make much sense. You want to pick one version of C++ and stick with that. Either you pick a very recent version because you get a lot of nice features, or you pick an older version to allow for more compatibility. For libraries that are potentially going to be used by many other projects, I would choose the latter.

Allow capacity to be zero

Instead of disallowing the capacity to be zero, just handle it. It's a simple change in the check for a full cache:

…
else if (m_lookup.size() == m_capacity) {
    if (m_capacity == 0) [[unlikely]] {
        return;
    } else {
        m_lookup.erase(m_cache.back());
        m_cache.pop_back();
    }
}
\$\endgroup\$
6
  • 1
    \$\begingroup\$ “… pick an older version to allow for more compatibility … I would choose the latter.” Eeeh…. Far too often I see people trying to make new stuff compatible with ancient C++ versions for the misguided notion of ”potential widespread use”, but that almost never actually makes sense. A 10 year-old project built on a legacy C++ version is very unlikely to be interested in extending it with code written yesterday, but not interested in moving to a newer C++ version. 1/3 \$\endgroup\$ Commented Nov 15 at 16:36
  • 1
    \$\begingroup\$ If it’s a legacy project, either a) they want new stuff, and thus are probably interested in moving to a newer C++ version; or b) they need stability, so they're hardly likely to trust code that hasn’t been vetted and tested for years. Obviously this is a generalization, but realistically speaking, the likelihood that you are writing code that is so fantasti-fuckingly-awesome that long-established projects with conservative upgrade policies will embrace it is microscopic. 2/3 \$\endgroup\$ Commented Nov 15 at 16:36
  • 2
    \$\begingroup\$ On the flip side, if you write really good modern code, new projects that are in development will be much more likely to be interested. Plus your code will be better, and more future proof, and you’ll be learning and exercising C++ skills that will be useful in the future, rather than the past. That’s why I recommend always writing to the most recent version, unless you have a SPECIFIC reason why you can’t. All new code will be widely-supported legacy code in time anyway, so by the time your code becomes widely-adopted (if that happens), widespread support will be a non-issue. 3/3 \$\endgroup\$ Commented Nov 15 at 16:36
  • 3
    \$\begingroup\$ BTW, the sticking point isn’t so much lack of optional<T> as it is lack of optional<T&>. Without optional references, using std::optional requires spurious copies where you really just want to check for a value, but not take it… such as in querying a set. I would recommend, in decreasing order: 1) targeting C++26 and using std::optional<T&>; 2) using boost::optional<T&>; 3) using T*; 4) making your own optional<T&>. \$\endgroup\$ Commented Nov 15 at 16:37
  • \$\begingroup\$ "If it’s a legacy project, either a) they want new stuff […] or b) they need stability" Nope, they want both, however incompatible those notions are. But other than that I definitely agree with you :) \$\endgroup\$ Commented Nov 15 at 16:59
6
\$\begingroup\$

Choose your trade-off:

  • Best software-engineering practice is to use an option type. This allows you to write fluent or railway-oriented code, and catches any bug where you forget to check for errors at compile time.
  • The most efficient solution is to encode keys as 64-bit fields, where negative values (or some other bit pattern that cannot represent valid data, for example a non-canonical or misaligned pointer) represent Nil/error, often called ssize_t. In the common case where you have either a pointer or a single error code, that could be a null pointer.
  • The best-of-both-worlds solution is to wrap the efficient representation in an option-type interface. (Rust can do this automatically in some cases.) You could in theory write your own MaybeKey class that contains only a 64-bit value and implements (partially) an interface like std::optional. That’s more complexity in C++ than it’s probably worth, though.
  • Many implementations will have the decency to crash immediately if you dereference a null pointer, and they are built into the language.
\$\endgroup\$
10
  • 1
    \$\begingroup\$ That leaves 63 bits to hold a pointer Not if the most significant bit of a 64-bit pointer is set. \$\endgroup\$ Commented Nov 16 at 14:24
  • \$\begingroup\$ @AndrewHenle There’s no guarantee a future target will not use all 64 bits of a pointer, but there are no architectures that support that much memory. You might, though, need to do some more complicated bit-twiddling than just setting or masking the sign bit. On x86-64, valid pointers are supposed to be in a “canonical form” where the upper 16 bits are set the same as the next-lower bit. So on that architecture, invalid pointer representations should be non-canonical values easy to check, such as for example setting the upper byte to 0x80. \$\endgroup\$ Commented Nov 16 at 17:18
  • \$\begingroup\$ You might encode a pointer or error (or even errors with a pointer to a data structure) in a 64-bit field on x86-64 by checking byte 7, and if that upper byte indicate that the sum type holds a pointer, copying byte 6 over byte 7 to recover the pointer in canonical form. Not portable, of course. \$\endgroup\$ Commented Nov 16 at 17:24
  • \$\begingroup\$ @AndrewHenle Since your point is well-taken, added a parenthetical note acknowledging it. \$\endgroup\$ Commented Nov 16 at 21:33
  • \$\begingroup\$ How does one "encode keys as 64-bit fields" when there are clearly more than 2⁶⁴ possible values for many key types? At some point you need to perform a == comparison, unless you have a fixed set of keys and have arranged a perfect hash function. \$\endgroup\$ Commented Nov 20 at 16:47
2
\$\begingroup\$

Unnecessary includes

We don't need either of these (large) headers:

#include <iostream>
#include <print>

Naming

The member function names are unconventional and uncomfortable. Use the same names as standard library containers when functionality is the same (e.g. insert_or_assign(), at()).

Throwing

In normal use, we tend to ask caches for values they don't have. To me, that suggests we should not be throwing when the requested key is not present - remember the principle that exceptions should be used for exceptional, not normal, behaviour. I recommend returning a std::optional instead, so we can return std::nullopt in that case (including when the cache contains no keys - no need for a specific test).

Copying (keys)

We store two copies of every key we add - one in the map, and one in the list. When the key type is large, that's wasteful. We can reduce storage by storing just the one in the list (which is never moved) and using a std::reference_wrapper as key in the map. As a side-benefit, that would also allow use of non-copyable keys, which is currently not possible.

A clever implementation could choose between making copies and references automatically.

Copying (caches)

BUG: The defaulted copy constructor and assignment operators are incorrect for this class, because the copied map contains iterators into the source object's list. We need to provide our own copy functions that re-generate these iterators from the new list.

Const

There are choices to be made regarding use of const with caches. We could consider lookup either to be a const operation (meaning we'd need to use mutable specifier for the LRU list) or to be a mutating operation, as we have done here. There are good arguments for both approaches, but it would be worth having a comment that shows why this choice was preferred here.

Strange assertion

We normally use assert() to document non-obvious invariants. But this one doesn't really add any understanding, given the immediately-preceding throw:

explicit LRUCache(size_type capacity)
    : m_capacity(capacity > 0 ? capacity : throw std::invalid_argument("capacity must be > 0"))
{
    assert(m_capacity > 0 && "capacity must be > 0");

Comment question

// Q: are universal references better choice?
void insertKeyValuePair(key_type key, value_type value) {

I'd say no here. Universal references (in standard terms, forwarding references) are useful when we want to forward possibly-reference arguments perfectly, and less so when we intend to take ownership. Here, we always need a key_type object and a value_type object, so probably better for any conversion to be performed (perhaps implicitly) in the calling code; that usually gives better error messages, for one thing.

Missing functionality

There's quite a lot we still need to provide. It's probably worthwhile to provide some sort of "peek" function that allows lookup of a key without moving it to the front of the LRU list.

Consider enabling transparent comparison of keys so that (for example) a user doesn't need to construct a std::string object from a string-view or C-style raw string.

Consider adding the following container functions (in no particular order):

  • swap()
  • clear()
  • erase()
  • empty()
  • count()
  • operator[]() (for default-constructible values)
  • try_emplace()
  • merge()

Making the collection implement a Range (perhaps in LRU order) might be worthwhile, too. For a variant using plain std::map, we might consider two Range views - one in LRU order and one in the map's preferred order.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You might also be interested in this review and this one; in both of those I demonstrate caches that store just one Key per mapping. \$\endgroup\$ Commented Nov 20 at 17:00
  • \$\begingroup\$ Thank you so much for the detailed explanations. I'll definitely check those links. \$\endgroup\$ Commented Nov 26 at 17:35

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.