Standard Compliance

Closed-addressing Containers

boost::unordered_[multi]set and boost::unordered_[multi]map provide a conformant implementation for C++11 (or later) compilers of the latest standard revision of C++ unordered associative containers, with very minor deviations as noted. The containers are fully AllocatorAware and support fancy pointers.

Deduction Guides

Deduction guides for class template argument deduction (CTAD) are only available on C++17 (or later) compilers.

Piecewise Pair Emplacement

In accordance with the standard specification, boost::unordered_[multi]map::emplace supports piecewise pair construction:

boost::unordered_multimap<std::string, std::complex> x;

x.emplace(
    std::piecewise_construct,
    std::make_tuple("key"), std::make_tuple(1, 2));

Additionally, the same functionality is provided via non-standard boost::unordered::piecewise_construct and Boost.Tuple:

x.emplace(
    boost::unordered::piecewise_construct,
    boost::make_tuple("key"), boost::make_tuple(1, 2));

This feature has been retained for backwards compatibility with previous versions of Boost.Unordered: users are encouraged to update their code to use std::piecewise_construct and std::tuples instead.

Swap

When swapping, Pred and Hash are not currently swapped by calling swap, their copy constructors are used. As a consequence, when swapping an exception may be thrown from their copy constructor.

Open-addressing Containers

The C++ standard does not currently provide any open-addressing container specification to adhere to, so boost::unordered_flat_set/unordered_node_set and boost::unordered_flat_map/unordered_node_map take inspiration from std::unordered_set and std::unordered_map, respectively, and depart from their interface where convenient or as dictated by their internal data structure, which is radically different from that imposed by the standard (closed addressing).

Open-addressing containers provided by Boost.Unordered only work with reasonably compliant C++11 (or later) compilers. Language-level features such as move semantics and variadic template parameters are then not emulated. The containers are fully AllocatorAware and support fancy pointers.

The main differences with C++ unordered associative containers are:

  • In general:

    • begin() is not constant-time.

    • erase(iterator) does not return an iterator to the following element, but a proxy object that converts to that iterator if requested; this avoids a potentially costly iterator increment operation when not needed.

    • There is no API for bucket handling (except bucket_count).

    • The maximum load factor of the container is managed internally and can’t be set by the user. The maximum load, exposed through the public function max_load, may decrease on erasure under high-load conditions.

  • Flat containers (boost::unordered_flat_set and boost::unordered_flat_map):

    • value_type must be move-constructible.

    • Pointer stability is not kept under rehashing.

    • There is no API for node extraction/insertion.

Concurrent Containers

There is currently no specification in the C++ standard for this or any other type of concurrent data structure. The APIs of boost::concurrent_flat_set/boost::concurrent_node_set and boost::concurrent_flat_map/boost::concurrent_node_map are modelled after std::unordered_flat_set and std::unordered_flat_map, respectively, with the crucial difference that iterators are not provided due to their inherent problems in concurrent scenarios (high contention, prone to deadlocking): so, Boost.Unordered concurrent containers are technically not models of Container, although they meet all the requirements of AllocatorAware containers (including fancy pointer support) except those implying iterators.

In a non-concurrent unordered container, iterators serve two main purposes:

  • Access to an element previously located via lookup.

  • Container traversal.

In place of iterators, Boost.Unordered concurrent containers use internal visitation facilities as a thread-safe substitute. Classical operations returning an iterator to an element already existing in the container, like for instance:

iterator find(const key_type& k);
std::pair<iterator, bool> insert(const value_type& obj);

are transformed to accept a visitation function that is passed such element:

template<class F> size_t visit(const key_type& k, F f);
template<class F> bool insert_or_visit(const value_type& obj, F f);

(In the second case f is only invoked if there’s an equivalent element to obj in the table, not if insertion is successful). Container traversal is served by:

template<class F> size_t visit_all(F f);

of which there are parallelized versions in C++17 compilers with parallel algorithm support. In general, the interface of concurrent containers is derived from that of their non-concurrent counterparts by a fairly straightforward process of replacing iterators with visitation where applicable. If for regular maps iterator and const_iterator provide mutable and const access to elements, respectively, here visitation is granted mutable or const access depending on the constness of the member function used (there are also *cvisit overloads for explicit const visitation); In the case of boost::concurrent_flat_set, visitation is always const.

One notable operation not provided by boost::concurrent_flat_map/boost::concurrent_node_map is operator[]/at, which can be replaced, if in a more convoluted manner, by try_emplace_or_visit.