[#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]`.

//-