mirror of
https://github.com/boostorg/unordered.git
synced 2025-05-11 05:23:58 +00:00
151 lines
6.3 KiB
Plaintext
151 lines
6.3 KiB
Plaintext
[#compliance]
|
|
= Standard Compliance
|
|
|
|
:idprefix: compliance_
|
|
|
|
:cpp: C++
|
|
|
|
== Closed-addressing Containers
|
|
|
|
`boost::unordered_[multi]set` and `boost::unordered_[multi]map` provide a conformant
|
|
implementation for {cpp}11 (or later) compilers of the latest standard revision of
|
|
{cpp} unordered associative containers, with very minor deviations as noted.
|
|
The containers are fully https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^]
|
|
and support https://en.cppreference.com/w/cpp/named_req/Allocator#Fancy_pointers[fancy pointers^].
|
|
|
|
=== Deduction Guides
|
|
|
|
Deduction guides for
|
|
https://en.cppreference.com/w/cpp/language/class_template_argument_deduction[class template argument deduction (CTAD)^]
|
|
are only available on {cpp}17 (or later) compilers.
|
|
|
|
=== Piecewise Pair Emplacement
|
|
|
|
In accordance with the standard specification,
|
|
`boost::unordered_[multi]map::emplace` supports piecewise pair construction:
|
|
|
|
[source,c++]
|
|
----
|
|
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:
|
|
|
|
[source,c++]
|
|
----
|
|
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.
|
|
|
|
=== 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 https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^]
|
|
and support https://en.cppreference.com/w/cpp/named_req/Allocator#Fancy_pointers[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
|
|
https://en.cppreference.com/w/cpp/named_req/Container[Container^], although
|
|
they meet all the requirements of https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^]
|
|
containers (including
|
|
https://en.cppreference.com/w/cpp/named_req/Allocator#Fancy_pointers[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:
|
|
|
|
[source,c++]
|
|
----
|
|
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:
|
|
|
|
[source,c++]
|
|
----
|
|
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:
|
|
|
|
[source,c++]
|
|
----
|
|
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
|
|
`xref:reference/concurrent_flat_map.adoc#concurrent_flat_map_try_emplace_or_cvisit[try_emplace_or_visit]`.
|
|
|
|
//-
|