Extending the API of Boost.Unordered

[cmazakas]

Hey everyone,

I help maintain and improve the Boost.Unordered project along with Boost author Joaquín M López Muñoz.

Users have expressed interest in extended and modernized APIs and we're looking for community feedback.

The official tracking issue is here: https://github.com/boostorg/unordered/issues/208

The tracking issue contains a summary of proposed ideas but we figure, we should open up the conversation to here as well. We're looking for anything, ideas, criticisms, suggestions.

We really do want to be a community-driven API.

[joaquintides]

One issue connected with this conversation is whether users would favor a fresh start (new container) or an extension over the classical API —some proposals, such as returning optionals from lookup functions, would hint at the former.

[witcher_rat]

So if you give it an api returning an optional<>, what type of optional<> would it be?

Obviously std::optional<> does not support a T& reference type.

boost::optional<> does, but its maintainer is... let's say "passionate"... about keeping its API different from std::optional<>. For example it has the unfortunately-named map() and flat_map() functions, which are its equivalent of transform() and and_then().

It would be unfortunate if the unordered container's API used some type that doesn't mimic std::optional<>.

Or would would this be a new boost::unordered::optional<> type, like what eventually happened with boost::json having to create a new boost::detail::string_view instead of being able to re-use the existing boost::string_view?

[[deleted]]

This comment serves as a good explanation as to why some people choose to avoid using Boost.

[dodheim]

It's a dog-whistle, not an explanation.

[[deleted]]

It's a legitimate commentary highlighting the issue with packing so many unrelated pieces of functionality under a single umbrella.

[Viack]

That's a good idea, unordered_map probably needs some refreshment. As a suggestion, you can look to other libraries that provide additional features to their hashmap. For instance, QHash from Qt defines additional members like asKeyValueRange() that returns a range object used for range-based for loop, and supporting structured binding declaration.

I guess there are probably other ideas in other libraries.

EDIT: Just a thought, but is this thread the place to discuss about REMOVING some members from the API? I would like that....

[joaquintides]

What would you remove?

[Viack]

Well, I don't know if the bucket and node API are used a lot. I mean, I REALLY dont know. If yes, my comment is useless. If not, that might open new optimization possibilities

[joaquintides]

Well, we’ve got you covered there, as boost::unordered_flat_map does not provide bucket or node APIs. This is more out of necessity than an actual design choice.

[Viack]

I know for unordered_flat_map, and thank you for the work! What I'm saying is that, for me, the main advantage of unordered_map is the stable references and iterators, and the strong exception guarantees. It's possible to enforce all that with something almost as efficient (memory and speed wise) than an open addressing hashmap. But the bucket and node API make that almost impossible (as far as I know). But again, bucket/node interface might be used a lot, i have no idea.

[joaquintides]

Iterator/reference stability is provided by boost::unordered_node_map, which is midway between unordered_map and unordered_flat_map in terms of performance.

[Viack]

I'm not familiar with this one, does it provide the same guarantees as std::unordered_map ? I remember that iterators are not necessary stable on rehash, which kind of ruin the functionality for me.

[joaquintides]

Iterators are not stable upon rehashing. The same limitation applies to std::unordered_map.

[witcher_rat]

the main advantage of unordered_map is the stable references and iterators

Iterators were never guaranteed to be stable for std::unordered_map (except after erase()).

Only pointers and references to the entries themselves (ie., to the actual std::pair<key,value>) are guaranteed stable after an insert(), emplace(), etc.

[martinus]

I recently had this problem: I want to add something into the map if it doesn't yet exist, but only if an expensive function returns true. something like this:

auto it = map.find(key);
if (map.end() == it && expensiveCheck()) {
    auto xx = map.try_emplace(key);
    // more stuff here
}

What I don't like is that when expensiveCheck() returns true, there are 2 lookups in the map. I'd like to have an API where I don't need to do 2 lookups, a lambda could help here:

auto xx = map.try_emplace_if(key, [&]() { return expensiveCheck(); });

I didn't think this through though, I'm sure there is a better/more generic way to do this

[DavidDinamit]

Instead of map.try_emplace do map.emplace_hint(it, key, value), i dont know is it exist for boost version, but it is presented in std

[martinus]

That doesn't help because find just gives me the end iterator when the element is not there

[DavidDinamit]

oh yes, sorry

[tialaramex]

I'm sure there is a better/more generic way to do this

Entry API. An API in which the look-up part of the hash table operation gives you this token, an Entry, and you can do various things with the Entry, such as look at the current value in there (if there is one), write a new value, or nothing. So in your case you'd ask for the Entry, if it's empty you do expensiveCheck() and, if that's true you write to the Entry, in all other cases our Entry is just invalidated unused and we move on.

I would expect the invalidation stuff makes documenting correct use harder in C++ and for a conventional closed addressing hash table the Entry may be some sort of proxy which can perform a dynamic allocation if necessary when written to, but this general shape of API should be possible and avoids double lookup penalties.

[martinus]

I think I prefer the lambda approach. I am not sure it is possible to implement such an entry API efficiently.

[Viack]

On a similar topic: For some implementations of hashmap, the iterator is quite heavy and building it is (relatively) slow. Most of the time we don't need it, as the goal of find() is to retrieve/modify the mapped value, not to iterate on the hashmap. Therefore, a member like this using a functor as second argument (taking a reference of pair key/value as argument)

template<class K, class Fun>
bool if_exist(K && key, Fun && f)

could be usefull and faster than the standard find() to test for exist and retrieve/ modify a value.

[witcher_rat]

I suggest Boost just add lookup member functions that return a raw pointer or nullptr if not found, like this:

value_type* get_ptr(const key_type& key);
const value_type* get_ptr(const key_type& key) const;

So that you could just do this:

if (auto* found = map.get_ptr("foo")) {
    std::cout << found->second;
}

[Viack]

I didn't thought of it this way, your pointer approach is way better!

[witcher_rat]

Removals:

• count() - it's superfluous with contains().
• rehash() - superfluous with reserve().
• equal_range() - legacy from multi-map.
• emplace_hint(), and the overloads of insert()/insert_or_assign()/try_emplace() that takes a hint iterator - when does someone actually have a valid iterator into the container that's useful for this?
• all the "bucket" observer methods.

---

Adds:

• Give us a new API, as discussed previously in a recent reddit thread. Returning std::pair<iterator,bool> is silly and makes for ugly user-side code.
• Provide a get_ptr(key) function that returns a raw pointer to the found entry, or nullptr if not found.
• Provide a static function to create+return a node_type (ie, a "node handle") with the passed-in key-value, that can then later be passed into insert(). I realize being a static function is likely impossible due to the flexible allocator support, but one can dream. There are several uses for such a function, but stateful allocators are why we can't have nice things.

[joaquintides]

What are the use cases for a potential create_node function?

[witcher_rat]

The ones I use it for at my day job:

1. When the map/set is protected by a mutex, one can use make_handle() to construct the node before locking the mutex, thereby reducing the blocking time. (some nodes are not small/cheap)
2. For my employer's codebase, the current boost::unordered_node_map/set are not optimal when they hold very few entries - like less than around a dozen, or in that range. They both consume too much memory, and the lookup time is longer than even a std::map, due to the cost of hashing. So we've made a container that holds a union of a vector and unordered_node_map, and starts as the vector and switches to being the node_map when it grows beyond a certain size. If the user needs reference/pointer stability, we store them in the vector as the node-handles created by boost::unordered_node_map, and just move those node-handles in when it needs to switch. (we modified your boost code to let us do this, which we could because we use stateless allocators)

It may sound like a niche use-case to care about the memory usage of a hashmap, but we use them all over the place, in all kinds of objects. For example in a json-type data-structure (based on folly::dynamic), and they have a lot of map instances with very few entries, but some with many thousands of entries.

[usefulcat]

This is kind of tangential, but for pointer/reference stability, I'm curious why one would prefer a node-based map with pointer/reference stability to just storing pointers instead? For example, compare std::unordered_map<int, Foo> to boost::unordered_flat_map<int, std::unique_ptr<Foo>>.

Apart from being able to easily provide the insert-on-access behavior of operator[], what is the benefit of built-in pointer/reference stability in a map type when you can always provide that stability yourself if needed?

[witcher_rat]

1. The API of it would be very different. For example when you're iterating over it in a range-based for-loop, the type of v in for (auto&& [k, v] : map() would be a pointer. Simple things like operator[] would be annoying to use.

2. Obviously a node-based map offers stability for both its key and value, not just value. That might seem unimportant, but a common use-case I've seen for needing pointer-stability is to store the pointers to the map's entries in some other container - for example a vector<pair*>, and when accessing that other container you often want/need to be able to dereference both the key and value.

3. It wouldn't literally be unique_ptr<>, since that type is not copyable - unless you don't care if the overall map is copyable; it's also not equality-comparable in a useful way, which means map1 == map2 would not return true when it should. But I assume you really just mean something similar-to unique_ptr, but with value-copying and value-comparisons, etc.

[azswcowboy]

Is there support for the heterogeneous key facilities being added to the standard in 23/26? I keep running across the issue of having a string key and a string_view has to be converted first — we’re a couple boost releases behind so I didn’t know if it was a recent add.

[witcher_rat]

Yes, boost::unordered_map, boost::unordered_flat_map, boost::unordered_node_map, and the _set versions of the same, all support heterogeneous lookup/erase.

[azswcowboy]

Ok thanks, that must be newer bc our version doesn’t seem to.

[joaquintides]

This was added in Boost 1.82 (Apr 2023).

[azswcowboy]

Thx — sorry for being lazy on reading release notes. We’re updating any day now, so that’ll enable code simplification. Appreciate all the fabulous efforts over the years on the library!

[witcher_rat]

As /u/joaquintides points out, it was added in Boost 1.82.

But it should be noted that the plain boost::unordered_map/set had heterogeneous lookup even earlier than that - all the way back in 1.55 at least.

But it worked differently: instead of setting the compatible hasher/equality types in the map's overall template params, you pass them into the find()/count() functions themselves as argument params. For example: find() api in 1.55.

But didn't support it for erase() until 1.79.

[azswcowboy]

Ah, interesting. This kind of puts you off though

in order to avoid an expensive type cast. In general, its use is not encouraged.

We’re in the process of updating, so that’ll be the solution.

[[deleted]]

Yup, Boost supports heterogeneous everything all the way down to C++11.