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::tuple
s instead.
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
andboost::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
.