The Associative Container API

When it comes to a hash table, there are basically only two interesting operations from an API perspective: lookup and insertion ¹. The standard library containers are all very consistent in how these operations are provided, across all the associative containers (maps and sets both, but I’ll just focus on maps):

template <class Key, class Value /* and other parameters */>
struct associative {
    // lookup
    auto find(Key const&) -> iterator;
    auto find(Key const&) const -> const_iterator;
    template <class K> auto find(K const&) -> iterator;
    template <class K> auto find(K const&) const -> const_iterator;

    auto at(Key const&) -> Value&;
    auto at(Key const&) const -> Value const&;

    auto operator[](Key const&) -> Value&;
    auto operator[](Key&&) -> Value&;

    // insertion
    auto insert(pair<Key const, Value> const&) -> pair<iterator, bool>;
    auto insert(pair<Key const, Value>&&) -> pair<iterator, bool>;
    template <class P> auto insert(P&&) -> pair<iterator, bool>;

    template <class... Args>
    auto emplace(Args&&...) -> pair<iterator, bool>;

    template <class... Args>
    auto try_emplace(Key const&, Args&&...) -> pair<iterator, bool>;
    template <class... Args>
    auto try_emplace(Key&&, Args&&...) -> pair<iterator, bool>;
};

That’s not the complete API for lookup or insertion, there’s some other functions for lookup (like equal_range and, finally, contains) and insertion (like other overloads that also take an iterator), but these are the crux of the API that everyone uses all the time.

On the plus side, the standard library containers are very consistent. They all offer the same API. Many user-defined containers have followed suit and also offer the same API. This is a big benefit, since it allows abseil’s hashtables to not even bother documenting their interface - you probably already know what it is ².

On the minus side, I find more and more that this API is pretty lacking in both ergonomics and functionality.

The goal of this post is to argue what’s missing the lookup and insertion APIs, and what we can hopefully improve upon.

Improving find()

There are three flavors of lookup in the standard container API:

• find() takes a Key and returns an iterator or const_iterator, which might be end() on lookup failure
• operator[] takes a Key, potentially default-initializes a new element at that key, and returns a Value& to it
• at() takes a Key and either returns a Value& (or Value const&) to that element or throws an exception

Now, of these, find() is the only conditional lookup. map[key] always ends up with an element for that key, whether you had one before or not. And map.at(key) throws if the key isn’t there, but otherwise is nice to use. find() is the only choice for actually checking anything.

Meanwhile, find() returns an iterator. That is just how the standard library works. But returning an iterator is… very rarely the optimal choice for everyday problems. After all, how often do you actually iterate that iterator? For ordered maps like std::map, iterating might make some sense, but for hash tables, iterating probably isn’t even sensible. Most uses will end up doing something like this:

auto it = map.find(key);
if (it != map.end()) {
    // do something with *it
} else {
    // maybe do something here
}

The lookup and the check for success have to be independent. This is because there is no iterator API in general for an iterator to check if it itself is the sentinel. So you have to do this two-step.

Even the simplest case of wanting to return the value or -1… that’s not a single expression, that’s two:

auto it = map.find(key);
return it != map.end() ? it->second : -1;

Is there something we could do that would be more useful? This is a blog post, so you know the answer is yes.

One return choice, which gives you all the same conditional access to the element, but in a way that you can check the result itself for truthiness, would be this:

auto find(Key const&) -> Optional<pair<Key const, Value>&>;
auto find(Key const&) const -> Optional<pair<Key const, Value> const&>;

See my previous writing about why Optional<T&> is superior to T*. This now allows writing a check that starts:

if (auto elem = map.find(key)) { ... }

And further allows building on the Optional by using continuation operations.

This is a lot better, but it’s still not quite ideal. Heterogeneous lookup in associative containers is an important piece of functionality, so you might not know the Key and it might be useful for it to be returned back to you. But most of the time your lookup is heterogeneous because you’re using something like a std::string_view to lookup into a map whose key is std::string, so it’s not like you really need the std::string anyway. So… why bother getting in back?

Additionally, while Optional supports continuation operations, something like value_or() still wants to give you back a pair<K, V> - and that’s typically not what you’re looking to get back when you’re reaching for value_or().

In that world, a more ergonomic API still would be to just return the value rather than the whole item:

auto find(Key const&) -> Optional<Value&>;
auto find(Key const&) const -> Optional<Value const&>;

This API now very cleanly allows for the “value or -1” use case I mentioned earlier: that’s now just map.find(key).value_or(-1). Which you can still do if you get the whole element, it’s just that you’d first do map.find(key).transform(get<1>).value_or(-1) ³.

To me, find() returning an Optional<Value&> is nearly always the most useful choice. I rarely actually need the iterator or the full std::pair back. I’m doing a map lookup because I want the value. Just the value. And note also that one of the uses for having an iterator is to be able to pass to erase() - but the reference to the Value should be sufficient for these needs as well ⁴.

There’s actually one more layer to peel off here, which is a much more narrow use-case. While Optional<Value&> is really the most useful choice for find(), in very particular circumstances it is more expensive than necessary. If Value is just an integral type, and you know that 0 is an invalid value for that type, then you don’t want to bother with a pointer - you really want find() to just return a Value for you, or 0 on failure. This isn’t always a valid choice, and it doesn’t always make sense from a performance perspective. But sometimes… it does.

To summarize, there are basically four options for what find could return:

auto find(Key const&) -> iterator;
auto find(Key const&) -> Optional<pair<Key const, Value>&>;
auto find(Key const&) -> Optional<Value&>;
auto find(Key const&) -> Value;

Which do we pick?

Naming

What’s interesting about these four algorithms is that they’re not actually four different algorithms. It’s really the same algorithm in all four cases - the only difference is:

• what is the value we return on success?
• what is the value we return on failure?

All the rest of the logic is identical. The choice of return type is very much just a parameter of find(). You can imagine providing a policy classes like:

struct return_element {
    template <input_iterator I>
    static auto from_value(I const& it) -> Optional<iter_reference_t<I>> {
        return *it;
    }

    template <input_iterator I>
    static auto from_end(I const&) -> Optional<iter_reference_t<I>> {
        return {};
    }
};

struct return_value {
    template <input_iterator I>
    static auto from_value(I const& it) -> Optional<decltype(it->second)> {
        return it->second;
    }

    template <input_iterator I>
    static auto from_end(I const&) -> Optional<decltype(it->second)> {
        return {};
    }
};

struct return_value_or_zero {
    template <input_iterator I>
    static auto from_value(I const& it) -> decltype(auto(it->second))
        return it->second;
    }

    template <input_iterator I>
    static auto from_end(I const&) -> decltype(auto(it->second))
        return {};
    }
};

And then passing them in as a template parameter:

auto a = map.find(key);                        // iterator
auto b = map.find<return_element>(key);        // Optional<pair<Key const, Value>&>
auto c = map.find<return_value>(key);          // Optional<Value&>
auto d = map.find<return_value_or_zero>(key);  // Value

To date, the only place that I’ve ever seen this used was ThinkCell’s library, as presented at multiple different C++ conferences. I think it’s a pretty compelling pattern. This might be a little verbose, but it avoids having to come up with multiple different names for the same algorithm, and the pattern isn’t unique to map::find() either.

Note that in this model, contains() is also just a different policy version of find(): return_bool. We just return true in one case and false in the other.

Now, these could be different named algorithms in the API. try_at() might be a good name for the return_value version. contains() is certainly a much more user-friendly spelling than find<return_bool>.

Either way, the point is - there are more user-friendly flavors of find() out there that associative containers really should provide. iterator isn’t really it. Optional<Value&> is probably what you want most of the time. While consistency with the standard library containers is, of course, a good thing - this is one situations where I’d be okay straying a little bit. I really don’t actually want an iterator often enough for the nicer named function (find() is a pretty nice name for lookup) to take the more useful return type, but at the very least providing a try_at() that returns an Optional<Value&> would be wonderful.

Improving insert()

While I find find() to be unergonomic, I find the insert() and emplace() family to be much more lacking.

Let’s say we have a situation where we want to look up a given key and, if absent, insert a new element into the map with value value. If we already have a value present, that’s straightforward:

auto [iter, success] = map.emplace(key, value);

I wish this function were also spelled insert() since how often do you actually have, specifically, a pair<Key const, Value> lying around to insert into the map? Approximately never? But okay, that’s kind of just nit-picking.

Otherwise, this API is pretty reasonable - you get back an iterator pointing to either the existing or newly added element and a bool telling you if the insertion happened. As above, iterator isn’t the best choice.

What if you don’t have a value lying around, and it’s something you need to construct? We could write this:

auto [iter, success] = map.emplace(key, acquire_value());

But this approach is pretty wasteful - acquire_value() isn’t always necessary to call. If the key is already present in the map, then you don’t want to waste the cycles acquiring a value that you don’t need. It’ll just immediately be thrown away.

We definitely don’t want to “fix” this by writing:

auto it = map.find(key);
bool success = false;
if (it == map.end()) {
    it = map.emplace(key, acquire_value());
    success = true;
}

Now we’re only conditionally invoking acquire_value(), which is good, but we’re doing two map lookups instead of one, which is bad. Maybe the lookup is cheaper enough than the cost of acquire_value() that we come out ahead anyway, but that seems underwhelming.

There is a conditional insert API available to us, but it only comes in this form:

auto try_emplace(Key const&, auto&&...) -> pair<iterator, bool>;
auto try_emplace(Key&&, auto&&...) -> pair<iterator, bool>;

Which… is great if acquire_value() is actually a constructor call spelled Value(a, b, c), but that really isn’t typical. We can work around this by providing a lazy evaluation primitive:

template <class F>
struct lazy_call {
    F f;

    template <class T> operator T() { return f(); }
};

#define LAZY(expr) lazy_call{[&]{ return expr; }}

which allows us to write:

auto [iter, success] = map.try_emplace(key, LAZY(acquire_value()));

Now, we only call acquire_value() if the key isn’t in the map, and we’re still only doing a single lookup. Great! I mean… pretty clunky, but it does get the job done. So far.

Let me throw another wrench in the mix: what if acquire_value() can fail? That is, what if we want to lookup a key in our map and, if it’s not there, do some work to then find what the value of the key should be. If that work succeeds, insert the new value. Otherwise, bail.

You can… definitely hack that together:

try {
    auto [iter, success] = map.try_emplace(key, lazy_call{[&]{
        Optional<Value> result = try_to_acquire_value();
        if (result) {
            return *result;
        } else {
            throw Something{};
        }
    }});
} catch (Something ) {
    // I dunno?
}

try_emplace can’t… really fail. It has no mechanism for this - so our only bet is to keep extending this lazy initialization hack by now throwing an exception out of it. An exception which we’re using exclusively for control flow, because we’re in a situation that simply doesn’t allow for any other control flow.

This is particularly cumbersome since we have to introduce another scope in order to catch this exception. We want to localize this catch as tightly as possible around the try_emplace() - but then we also probably want to use the returned iterator later, so do we declare it uninitialized earlier? But doing so requires spelling out the type of the iterator?

There’s not a lot of good answers here. Can we do better?

Enter: the entry API

Let’s say we had the following API:

Entry e = map.entry(key);

Where entry() returns an object that is either occupied (and you can access the element there, same as with an iterator) or vacant (but retaining the location of the key would be inserted, were that the desired behavior - a more useful choice than end()).

If we just want to insert a default value and get a reference to the result, there’s a function for that:

// similar to map[key], except explicitly choosing the new value
// which would not necessarily require default construction
// also more obviously inserts an element - avoiding the not uncommon bug where
// users intend to simply lookup 'key' and accidentally insert it too
Value& v = map.entry(key).or_insert(new_value);

If we want to insert a default value that we get from a function call, as we tried to hack around earlier with the lazy initialization mechanism, there’s a function for that too:

// this is what we did earlier with
// map.try_emplace(key, LAZY(acquire_value()))
Value& v = map.entry(key).or_insert_with(acquire_value);

And we can even fairly straightforwardly handle the situation where acquire_value() is fallible, without resorting to using exceptions for artificial control flow:

auto entry = map.entry(key);
if (entry.is_vacant()) {
    if (auto result = try_to_acquire_value()) {
        entry.insert(*result);
    } else {
        // handle this case
    }
}

// now entry is occupied

All of the above examples have fairly easy-to-follow control flow, only do a single map lookup, offer convenient and efficient solutions for a variety of problems.

Incidentally, this is the API for Rust’s HashMap.

Retiring insert()

It’s not just that insert() is unsatisfying and try_emplace() is lacking, it’s also that insert() is kind of just a bad API. I mentioned earlier that insert() is unsatisfying because you never really just have a pair<Key const, Value> lying around, so it fails to be convenient. But it’s worse than simply not being convenient.

What actually happens on these three lines for a node-based map (so that you don’t have to worry about move existing elements around):

map.insert({key, val});          // #1
map.insert(std::pair(key, val)); // #2
map.emplace(key, val);           // #3

Let’s go through these in order. Let’s also assume that key and val are rvalues, for simplicity.

In #1, we call the overload that takes a pair<Key const, Value>&&. This first requires constructing that object, which moves key and val. We then have to std::move that element into place. But std::move-ing a std::pair<Key const, Value>, while it does move the Value, actually copies the Key. Because const. So this incurs 2 moves of val and 1 move and 1 copy of key.

In #2, we call the overload that takes a P&&, here with P being a pair<Key /* not const */, Value>. So again, we have to construct that object, incurring a move of each. But then we’re constructing a pair<Key const, Value> from an rvalue pair<Key, Value>, so we can actually move the key here too! As a result, 2 moves each.

This is a particularly odd situation, since in insert, getting the type of the pair wrong (not being const) is actually an optimization. On the other hand, in a range-based for loop, getting the type of the pair wrong is a pessimization:

// oops: compiles, but we're copying every element
for (pair<Key, Value> const& elem : map) { ... }

In #3, we’re calling an overload that just takes Args&&... and are using it to directly construct the element. This is just a single move of each of key and val.

To summarize:

This is very much unlike the situation with something like std::vector<T>, where vec.push_back(elem); and vec.emplace(elem); actually do the same thing - either both copy or both move. Here map.insert() is just a strict pessimization of map.emplace(). But the problem is that emplace() also does… more than you want, some of the time. For instance, this compiles:

map<std::chrono::nanoseconds, std::chrono::milliseconds> m;
m.emplace(1, 2);

But it kind of defeats the purpose of std::chrono::duration being explicitly constructible if you’re not explicit about it.

In addition to the missing entry() API, the associative containers are missing the correct spelling of insert(): one that takes the Key and Val as two parameters:

auto insert(Key const&, Value const&) -> std::pair<iterator, bool>;
auto insert(Key const&, Value&&) -> std::pair<iterator, bool>;
auto insert(Key&&, Value const&) -> std::pair<iterator, bool>;
auto insert(Key&&, Value&&) -> std::pair<iterator, bool>;

Yes, this is tedious, and I’m working on a better answer for this (spoiler alert: I have found several bad solutions so far), but until then, I think this would be a significant improvement over status quo. It’s less typing than the typical use of insert today, while also being more efficient, and safer than emplace().

Probably a good enough alternative to the above is:

template <convertible_to<Key> K=Key, convertible_to<Value> V=Value>
auto insert(K&&, V&&) -> std::pair<iterator, bool>;

insert() here would also benefit from the same kind of Policy approach that find() would - since iterator isn’t always what you want returned.

What’s up with std::pair anyway?

There are several places in the associative container APIs that std::pair shows up:

• std::pair<Key const, Value> is the container’s value_type and reference that you see for all range operations
• insert() takes a std::pair<Key const, Value>, or something convertible to it
• all the insertion functions return a std::pair<iterator, bool>

The first two of these are at least somewhat justifiable by the fact that std::pair is generally easier to generically program around today that a struct with two members, and I made a longer version of this argument when talking about views::enumerate. But some of those arguments don’t really apply here - since our container really is a container of these objects, so we could just have:

struct value_type { Key key; Value value; };
using reference = value_type&;
using const_reference = value_type const&;

At this point the primary advantage of std::pair is just… legacy code. Code that uses one hash table could easily switch to another hash table by just changing the declaration, and things just work.

As much as I can’t stand all the it->first and it->second everywhere.

But even with that argument, the insertion functions returning a std::pair is awful. Since C++17, I basically always write the kind of code I’ve written throughout this post:

auto [iter, success] = map.emplace(key, value);

Because any sensible name for the iterator and the bool is better than first and second. And the use of this particular type tends to be pretty local to the insertion site, so would be pretty easy to change. Even when I only need the iterator, I still use structured bindings, because I’d rather write:

auto [it, _] = map.try_emplace(key, LAZY(acquire_value()));

than

auto it = map.try_emplace(key, LAZY(acquire_value())).first;

but if there were sensible names, I’d probably prefer:

auto it = map.try_emplace(key, LAZY(acquire_value())).iterator;

In an ideal world it’d be great to drop all the std::pairs, but at least in the world we live in, we can probably drop some of them.

Conclusion

There is a common standard library API for associative containers, that most associative containers implement for consistency. The consistency is a good user experience in of itself, but the API for lookup and insertion is lacking.

For lookup, the most useful result in most contexts is an Optional<Value&>, but the API we have just gives us an iterator. This inhibits continuation and chaining, requiring us to declare the result iterator on its own line and accessing the value with the cryptic-yet-unfortunately-familiar it->second. It would be nice to provide multiple different flavors of find() so that the users can choose the one that they want. At the very least, providing:

auto find(Key const&) -> iterator;
auto try_at(Key const&) -> Optional<Value&>;
template <class Policy> auto find(Policy, Key const&) -> Policy::type;

For insertion, we can hack around the lack of conditional insertion API - but only to a certain extent. The API is still built around the specific case of wanting to insert a Value that we already have, not around a Value that we still need to compute, and definitely not around a Value whose computation is fallible. An entry()-based API would allow for a clean way of solving this problem. Additionally, the existing insert() API is inefficient, and leads to people using the less safe emplace() API - it’d be better to provide a two-parameter version of insert() for people to use.

And if we can’t drop all the std::pairs, at least we can have all the insertion APIs return a struct with named members instead of a std::pair<iterator, bool>.

Perhaps this is something to lobby for the new Boost.Unordered, which Joaquín M. López Muñoz recently spoke about at using::cpp: More than a rehash.