﻿[#concurrent_flat_map]
== Class Template concurrent_flat_map

:idprefix: concurrent_flat_map_

`boost::concurrent_flat_map` — A hash table that associates unique keys with another value and
allows for concurrent element insertion, erasure, lookup and access
without external synchronization mechanisms.

Even though it acts as a container, `boost::concurrent_flat_map`
does not model the standard C++ https://en.cppreference.com/w/cpp/named_req/Container[Container^] concept.
In particular, iterators and associated operations (`begin`, `end`, etc.) are not provided.
Element access and modification are done through user-provided _visitation functions_ that are passed
to `concurrent_flat_map` operations where they are executed internally in a controlled fashion.
Such visitation-based API allows for low-contention concurrent usage scenarios.

The internal data structure of `boost::concurrent_flat_map` is similar to that of
`boost::unordered_flat_map`. As a result of its using open-addressing techniques,
`value_type` must be move-constructible and pointer stability is not kept under rehashing.

=== Synopsis

[listing,subs="+macros,+quotes"]
-----
// #include <boost/unordered/concurrent_flat_map.hpp>

namespace boost {
  template<class Key,
           class T,
           class Hash = boost::hash<Key>,
           class Pred = std::equal_to<Key>,
           class Allocator = std::allocator<std::pair<const Key, T>>>
  class concurrent_flat_map {
  public:
    // types
    using key_type             = Key;
    using mapped_type          = T;
    using value_type           = std::pair<const Key, T>;
    using init_type            = std::pair<
                                   typename std::remove_const<Key>::type,
                                   typename std::remove_const<T>::type
                                 >;
    using hasher               = Hash;
    using key_equal            = Pred;
    using allocator_type       = Allocator;
    using pointer              = typename std::allocator_traits<Allocator>::pointer;
    using const_pointer        = typename std::allocator_traits<Allocator>::const_pointer;
    using reference            = value_type&;
    using const_reference      = const value_type&;
    using size_type            = std::size_t;
    using difference_type      = std::ptrdiff_t;

    // constants
    static constexpr size_type xref:#concurrent_flat_map_constants[bulk_visit_size] = _implementation-defined_;

    // construct/copy/destroy
    xref:#concurrent_flat_map_default_constructor[concurrent_flat_map]();
    explicit xref:#concurrent_flat_map_bucket_count_constructor[concurrent_flat_map](size_type n,
                                 const hasher& hf = hasher(),
                                 const key_equal& eql = key_equal(),
                                 const allocator_type& a = allocator_type());
    template<class InputIterator>
      xref:#concurrent_flat_map_iterator_range_constructor[concurrent_flat_map](InputIterator f, InputIterator l,
                          size_type n = _implementation-defined_,
                          const hasher& hf = hasher(),
                          const key_equal& eql = key_equal(),
                          const allocator_type& a = allocator_type());
    xref:#concurrent_flat_map_copy_constructor[concurrent_flat_map](const concurrent_flat_map& other);
    xref:#concurrent_flat_map_move_constructor[concurrent_flat_map](concurrent_flat_map&& other);
    template<class InputIterator>
      xref:#concurrent_flat_map_iterator_range_constructor_with_allocator[concurrent_flat_map](InputIterator f, InputIterator l,const allocator_type& a);
    explicit xref:#concurrent_flat_map_allocator_constructor[concurrent_flat_map](const Allocator& a);
    xref:#concurrent_flat_map_copy_constructor_with_allocator[concurrent_flat_map](const concurrent_flat_map& other, const Allocator& a);
    xref:#concurrent_flat_map_move_constructor_with_allocator[concurrent_flat_map](concurrent_flat_map&& other, const Allocator& a);
    xref:#concurrent_flat_map_move_constructor_from_unordered_flat_map[concurrent_flat_map](unordered_flat_map<Key, T, Hash, Pred, Allocator>&& other);
    xref:#concurrent_flat_map_initializer_list_constructor[concurrent_flat_map](std::initializer_list<value_type> il,
                        size_type n = _implementation-defined_
                        const hasher& hf = hasher(),
                        const key_equal& eql = key_equal(),
                        const allocator_type& a = allocator_type());
    xref:#concurrent_flat_map_bucket_count_constructor_with_allocator[concurrent_flat_map](size_type n, const allocator_type& a);
    xref:#concurrent_flat_map_bucket_count_constructor_with_hasher_and_allocator[concurrent_flat_map](size_type n, const hasher& hf, const allocator_type& a);
    template<class InputIterator>
      xref:#concurrent_flat_map_iterator_range_constructor_with_bucket_count_and_allocator[concurrent_flat_map](InputIterator f, InputIterator l, size_type n,
                          const allocator_type& a);
    template<class InputIterator>
      xref:#concurrent_flat_map_iterator_range_constructor_with_bucket_count_and_hasher[concurrent_flat_map](InputIterator f, InputIterator l, size_type n, const hasher& hf,
                          const allocator_type& a);
    xref:#concurrent_flat_map_initializer_list_constructor_with_allocator[concurrent_flat_map](std::initializer_list<value_type> il, const allocator_type& a);
    xref:#concurrent_flat_map_initializer_list_constructor_with_bucket_count_and_allocator[concurrent_flat_map](std::initializer_list<value_type> il, size_type n,
                        const allocator_type& a);
    xref:#concurrent_flat_map_initializer_list_constructor_with_bucket_count_and_hasher_and_allocator[concurrent_flat_map](std::initializer_list<value_type> il, size_type n, const hasher& hf,
                        const allocator_type& a);
    xref:#concurrent_flat_map_destructor[~concurrent_flat_map]();
    concurrent_flat_map& xref:#concurrent_flat_map_copy_assignment[operator++=++](const concurrent_flat_map& other);
    concurrent_flat_map& xref:#concurrent_flat_map_move_assignment[operator++=++](concurrent_flat_map&& other) ++noexcept(
      (boost::allocator_traits<Allocator>::is_always_equal::value ||
       boost::allocator_traits<Allocator>::propagate_on_container_move_assignment::value) &&
       std::is_same<pointer, value_type*>::value);++
    concurrent_flat_map& xref:#concurrent_flat_map_initializer_list_assignment[operator++=++](std::initializer_list<value_type>);
    allocator_type xref:#concurrent_flat_map_get_allocator[get_allocator]() const noexcept;


    // visitation
    template<class F> size_t xref:#concurrent_flat_map_cvisit[visit](const key_type& k, F f);
    template<class F> size_t xref:#concurrent_flat_map_cvisit[visit](const key_type& k, F f) const;
    template<class F> size_t xref:#concurrent_flat_map_cvisit[cvisit](const key_type& k, F f) const;
    template<class K, class F> size_t xref:#concurrent_flat_map_cvisit[visit](const K& k, F f);
    template<class K, class F> size_t xref:#concurrent_flat_map_cvisit[visit](const K& k, F f) const;
    template<class K, class F> size_t xref:#concurrent_flat_map_cvisit[cvisit](const K& k, F f) const;

    template<class FwdIterator, class F>
      size_t xref:concurrent_flat_map_bulk_visit[visit](FwdIterator first, FwdIterator last, F f);
    template<class FwdIterator, class F>
      size_t xref:concurrent_flat_map_bulk_visit[visit](FwdIterator first, FwdIterator last, F f) const;
    template<class FwdIterator, class F>
      size_t xref:concurrent_flat_map_bulk_visit[cvisit](FwdIterator first, FwdIterator last, F f) const;

    template<class F> size_t xref:#concurrent_flat_map_cvisit_all[visit_all](F f);
    template<class F> size_t xref:#concurrent_flat_map_cvisit_all[visit_all](F f) const;
    template<class F> size_t xref:#concurrent_flat_map_cvisit_all[cvisit_all](F f) const;
    template<class ExecutionPolicy, class F>
      void xref:#concurrent_flat_map_parallel_cvisit_all[visit_all](ExecutionPolicy&& policy, F f);
    template<class ExecutionPolicy, class F>
      void xref:#concurrent_flat_map_parallel_cvisit_all[visit_all](ExecutionPolicy&& policy, F f) const;
    template<class ExecutionPolicy, class F>
      void xref:#concurrent_flat_map_parallel_cvisit_all[cvisit_all](ExecutionPolicy&& policy, F f) const;

    template<class F> bool xref:#concurrent_flat_map_cvisit_while[visit_while](F f);
    template<class F> bool xref:#concurrent_flat_map_cvisit_while[visit_while](F f) const;
    template<class F> bool xref:#concurrent_flat_map_cvisit_while[cvisit_while](F f) const;
    template<class ExecutionPolicy, class F>
      bool xref:#concurrent_flat_map_parallel_cvisit_while[visit_while](ExecutionPolicy&& policy, F f);
    template<class ExecutionPolicy, class F>
      bool xref:#concurrent_flat_map_parallel_cvisit_while[visit_while](ExecutionPolicy&& policy, F f) const;
    template<class ExecutionPolicy, class F>
      bool xref:#concurrent_flat_map_parallel_cvisit_while[cvisit_while](ExecutionPolicy&& policy, F f) const;

    // capacity
    ++[[nodiscard]]++ bool xref:#concurrent_flat_map_empty[empty]() const noexcept;
    size_type xref:#concurrent_flat_map_size[size]() const noexcept;
    size_type xref:#concurrent_flat_map_max_size[max_size]() const noexcept;

    // modifiers
    template<class... Args> bool xref:#concurrent_flat_map_emplace[emplace](Args&&... args);
    bool xref:#concurrent_flat_map_copy_insert[insert](const value_type& obj);
    bool xref:#concurrent_flat_map_copy_insert[insert](const init_type& obj);
    bool xref:#concurrent_flat_map_move_insert[insert](value_type&& obj);
    bool xref:#concurrent_flat_map_move_insert[insert](init_type&& obj);
    template<class InputIterator> size_type xref:#concurrent_flat_map_insert_iterator_range[insert](InputIterator first, InputIterator last);
    size_type xref:#concurrent_flat_map_insert_initializer_list[insert](std::initializer_list<value_type> il);

    template<class... Args, class F> bool xref:#concurrent_flat_map_emplace_or_cvisit[emplace_or_visit](Args&&... args, F&& f);
    template<class... Args, class F> bool xref:#concurrent_flat_map_emplace_or_cvisit[emplace_or_cvisit](Args&&... args, F&& f);
    template<class F> bool xref:#concurrent_flat_map_copy_insert_or_cvisit[insert_or_visit](const value_type& obj, F f);
    template<class F> bool xref:#concurrent_flat_map_copy_insert_or_cvisit[insert_or_cvisit](const value_type& obj, F f);
    template<class F> bool xref:#concurrent_flat_map_copy_insert_or_cvisit[insert_or_visit](const init_type& obj, F f);
    template<class F> bool xref:#concurrent_flat_map_copy_insert_or_cvisit[insert_or_cvisit](const init_type& obj, F f);
    template<class F> bool xref:#concurrent_flat_map_move_insert_or_cvisit[insert_or_visit](value_type&& obj, F f);
    template<class F> bool xref:#concurrent_flat_map_move_insert_or_cvisit[insert_or_cvisit](value_type&& obj, F f);
    template<class F> bool xref:#concurrent_flat_map_move_insert_or_cvisit[insert_or_visit](init_type&& obj, F f);
    template<class F> bool xref:#concurrent_flat_map_move_insert_or_cvisit[insert_or_cvisit](init_type&& obj, F f);
    template<class InputIterator,class F>
      size_type xref:#concurrent_flat_map_insert_iterator_range_or_visit[insert_or_visit](InputIterator first, InputIterator last, F f);
    template<class InputIterator,class F>
      size_type xref:#concurrent_flat_map_insert_iterator_range_or_visit[insert_or_cvisit](InputIterator first, InputIterator last, F f);
    template<class F> size_type xref:#concurrent_flat_map_insert_initializer_list_or_visit[insert_or_visit](std::initializer_list<value_type> il, F f);
    template<class F> size_type xref:#concurrent_flat_map_insert_initializer_list_or_visit[insert_or_cvisit](std::initializer_list<value_type> il, F f);

    template<class... Args> bool xref:#concurrent_flat_map_try_emplace[try_emplace](const key_type& k, Args&&... args);
    template<class... Args> bool xref:#concurrent_flat_map_try_emplace[try_emplace](key_type&& k, Args&&... args);
    template<class K, class... Args> bool xref:#concurrent_flat_map_try_emplace[try_emplace](K&& k, Args&&... args);

    template<class... Args, class F>
      bool xref:#concurrent_flat_map_try_emplace_or_cvisit[try_emplace_or_visit](const key_type& k, Args&&... args, F&& f);
    template<class... Args, class F>
      bool xref:#concurrent_flat_map_try_emplace_or_cvisit[try_emplace_or_cvisit](const key_type& k, Args&&... args, F&& f);
    template<class... Args, class F>
      bool xref:#concurrent_flat_map_try_emplace_or_cvisit[try_emplace_or_visit](key_type&& k, Args&&... args, F&& f);
    template<class... Args, class F>
      bool xref:#concurrent_flat_map_try_emplace_or_cvisit[try_emplace_or_cvisit](key_type&& k, Args&&... args, F&& f);
    template<class K, class... Args, class F>
      bool xref:#concurrent_flat_map_try_emplace_or_cvisit[try_emplace_or_visit](K&& k, Args&&... args, F&& f);
    template<class K, class... Args, class F>
      bool xref:#concurrent_flat_map_try_emplace_or_cvisit[try_emplace_or_cvisit](K&& k, Args&&... args, F&& f);

    template<class M> bool xref:#concurrent_flat_map_insert_or_assign[insert_or_assign](const key_type& k, M&& obj);
    template<class M> bool xref:#concurrent_flat_map_insert_or_assign[insert_or_assign](key_type&& k, M&& obj);
    template<class K, class M> bool xref:#concurrent_flat_map_insert_or_assign[insert_or_assign](K&& k, M&& obj);

    size_type xref:#concurrent_flat_map_erase[erase](const key_type& k);
    template<class K> size_type xref:#concurrent_flat_map_erase[erase](const K& k);

    template<class F> size_type xref:#concurrent_flat_map_erase_if_by_key[erase_if](const key_type& k, F f);
    template<class K, class F> size_type xref:#concurrent_flat_map_erase_if_by_key[erase_if](const K& k, F f);
    template<class F> size_type xref:#concurrent_flat_map_erase_if[erase_if](F f);
    template<class ExecutionPolicy, class  F> void xref:#concurrent_flat_map_parallel_erase_if[erase_if](ExecutionPolicy&& policy, F f);

    void      xref:#concurrent_flat_map_swap[swap](concurrent_flat_map& other)
      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
               boost::allocator_traits<Allocator>::propagate_on_container_swap::value);
    void      xref:#concurrent_flat_map_clear[clear]() noexcept;

    template<class H2, class P2>
      size_type xref:#concurrent_flat_map_merge[merge](concurrent_flat_map<Key, T, H2, P2, Allocator>& source);
    template<class H2, class P2>
      size_type xref:#concurrent_flat_map_merge[merge](concurrent_flat_map<Key, T, H2, P2, Allocator>&& source);

    // observers
    hasher xref:#concurrent_flat_map_hash_function[hash_function]() const;
    key_equal xref:#concurrent_flat_map_key_eq[key_eq]() const;

    // map operations
    size_type        xref:#concurrent_flat_map_count[count](const key_type& k) const;
    template<class K>
      size_type      xref:#concurrent_flat_map_count[count](const K& k) const;
    bool             xref:#concurrent_flat_map_contains[contains](const key_type& k) const;
    template<class K>
      bool           xref:#concurrent_flat_map_contains[contains](const K& k) const;

    // bucket interface
    size_type xref:#concurrent_flat_map_bucket_count[bucket_count]() const noexcept;

    // hash policy
    float xref:#concurrent_flat_map_load_factor[load_factor]() const noexcept;
    float xref:#concurrent_flat_map_max_load_factor[max_load_factor]() const noexcept;
    void xref:#concurrent_flat_map_set_max_load_factor[max_load_factor](float z);
    size_type xref:#concurrent_flat_map_max_load[max_load]() const noexcept;
    void xref:#concurrent_flat_map_rehash[rehash](size_type n);
    void xref:#concurrent_flat_map_reserve[reserve](size_type n);
  };

  // Deduction Guides
  template<class InputIterator,
           class Hash = boost::hash<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>>,
           class Pred = std::equal_to<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>>,
           class Allocator = std::allocator<xref:#concurrent_flat_map_iter_to_alloc_type[__iter-to-alloc-type__]<InputIterator>>>
    concurrent_flat_map(InputIterator, InputIterator, typename xref:#concurrent_flat_map_deduction_guides[__see below__]::size_type = xref:#concurrent_flat_map_deduction_guides[__see below__],
                        Hash = Hash(), Pred = Pred(), Allocator = Allocator())
      -> concurrent_flat_map<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>, xref:#concurrent_flat_map_iter_mapped_type[__iter-mapped-type__]<InputIterator>, Hash,
                             Pred, Allocator>;

  template<class Key, class T, class Hash = boost::hash<Key>,
           class Pred = std::equal_to<Key>,
           class Allocator = std::allocator<std::pair<const Key, T>>>
    concurrent_flat_map(std::initializer_list<std::pair<Key, T>>,
                        typename xref:#concurrent_flat_map_deduction_guides[__see below__]::size_type = xref:#concurrent_flat_map_deduction_guides[__see below__], Hash = Hash(),
                        Pred = Pred(), Allocator = Allocator())
      -> concurrent_flat_map<Key, T, Hash, Pred, Allocator>;

  template<class InputIterator, class Allocator>
    concurrent_flat_map(InputIterator, InputIterator, typename xref:#concurrent_flat_map_deduction_guides[__see below__]::size_type, Allocator)
      -> concurrent_flat_map<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>, xref:#concurrent_flat_map_iter_mapped_type[__iter-mapped-type__]<InputIterator>,
                             boost::hash<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>>,
                             std::equal_to<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>>, Allocator>;

  template<class InputIterator, class Allocator>
    concurrent_flat_map(InputIterator, InputIterator, Allocator)
      -> concurrent_flat_map<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>, xref:#concurrent_flat_map_iter_mapped_type[__iter-mapped-type__]<InputIterator>,
                             boost::hash<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>>,
                             std::equal_to<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>>, Allocator>;

  template<class InputIterator, class Hash, class Allocator>
    concurrent_flat_map(InputIterator, InputIterator, typename xref:#concurrent_flat_map_deduction_guides[__see below__]::size_type, Hash,
                        Allocator)
      -> concurrent_flat_map<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>, xref:#concurrent_flat_map_iter_mapped_type[__iter-mapped-type__]<InputIterator>, Hash,
                             std::equal_to<xref:#concurrent_flat_map_iter_key_type[__iter-key-type__]<InputIterator>>, Allocator>;

  template<class Key, class T, class Allocator>
    concurrent_flat_map(std::initializer_list<std::pair<Key, T>>, typename xref:#concurrent_flat_map_deduction_guides[__see below__]::size_type,
                        Allocator)
      -> concurrent_flat_map<Key, T, boost::hash<Key>, std::equal_to<Key>, Allocator>;

  template<class Key, class T, class Allocator>
    concurrent_flat_map(std::initializer_list<std::pair<Key, T>>, Allocator)
      -> concurrent_flat_map<Key, T, boost::hash<Key>, std::equal_to<Key>, Allocator>;

  template<class Key, class T, class Hash, class Allocator>
    concurrent_flat_map(std::initializer_list<std::pair<Key, T>>, typename xref:#concurrent_flat_map_deduction_guides[__see below__]::size_type,
                        Hash, Allocator)
      -> concurrent_flat_map<Key, T, Hash, std::equal_to<Key>, Allocator>;

  // Equality Comparisons
  template<class Key, class T, class Hash, class Pred, class Alloc>
    bool xref:#concurrent_flat_map_operator[operator==](const concurrent_flat_map<Key, T, Hash, Pred, Alloc>& x,
                    const concurrent_flat_map<Key, T, Hash, Pred, Alloc>& y);

  template<class Key, class T, class Hash, class Pred, class Alloc>
    bool xref:#concurrent_flat_map_operator_2[operator!=](const concurrent_flat_map<Key, T, Hash, Pred, Alloc>& x,
                    const concurrent_flat_map<Key, T, Hash, Pred, Alloc>& y);

  // swap
  template<class Key, class T, class Hash, class Pred, class Alloc>
    void xref:#concurrent_flat_map_swap_2[swap](concurrent_flat_map<Key, T, Hash, Pred, Alloc>& x,
              concurrent_flat_map<Key, T, Hash, Pred, Alloc>& y)
      noexcept(noexcept(x.swap(y)));

  // Erasure
  template<class K, class T, class H, class P, class A, class Predicate>
    typename concurrent_flat_map<K, T, H, P, A>::size_type
       xref:#concurrent_flat_map_erase_if_2[erase_if](concurrent_flat_map<K, T, H, P, A>& c, Predicate pred);
}
-----

---

=== Description

*Template Parameters*

[cols="1,1"]
|===

|_Key_
.2+|`Key` and `T` must be https://en.cppreference.com/w/cpp/named_req/MoveConstructible[MoveConstructible^].
`std::pair<const Key, T>` must be https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[EmplaceConstructible^]
into the table from any `std::pair` object convertible to it, and it also must be
https://en.cppreference.com/w/cpp/named_req/Erasable[Erasable^] from the table.

|_T_

|_Hash_
|A unary function object type that acts a hash function for a `Key`. It takes a single argument of type `Key` and returns a value of type `std::size_t`.

|_Pred_
|A binary function object that induces an equivalence relation on values of type `Key`. It takes two arguments of type `Key` and returns a value of type `bool`.

|_Allocator_
|An allocator whose value type is the same as the table's value type.
Allocators using https://en.cppreference.com/w/cpp/named_req/Allocator#Fancy_pointers[fancy pointers] are supported.

|===

The elements of the table are held into an internal _bucket array_. An element is inserted into a bucket determined by its
hash code, but if the bucket is already occupied (a _collision_), an available one in the vicinity of the
original position is used.

The size of the bucket array can be automatically increased by a call to `insert`/`emplace`, or as a result of calling
`rehash`/`reserve`. The _load factor_ of the table (number of elements divided by number of buckets) is never
greater than `max_load_factor()`, except possibly for small sizes where the implementation may decide to
allow for higher loads.

If `xref:hash_traits_hash_is_avalanching[hash_is_avalanching]<Hash>::value` is `true`, the hash function
is used as-is; otherwise, a bit-mixing post-processing stage is added to increase the quality of hashing
at the expense of extra computational cost.

---

=== Concurrency Requirements and Guarantees

Concurrent invocations of `operator()` on the same const instance of `Hash` or `Pred` are required
to not introduce data races. For `Alloc` being either `Allocator` or any allocator type rebound
from `Allocator`, concurrent invocations of the following operations on the same instance `al` of `Alloc`
are required to not introduce data races:

* Copy construction from `al` of an allocator rebound from `Alloc`
* `std::allocator_traits<Alloc>::allocate`
* `std::allocator_traits<Alloc>::deallocate`
* `std::allocator_traits<Alloc>::construct`
* `std::allocator_traits<Alloc>::destroy`

In general, these requirements on `Hash`, `Pred` and `Allocator` are met if these types
are not stateful or if the operations only involve constant access to internal data members.

With the exception of destruction, concurrent invocations of any operation on the same instance of a
`concurrent_flat_map` do not introduce data races — that is, they are thread-safe.

If an operation *op* is explicitly designated as _blocking on_ `x`, where `x` is an instance of a `boost::concurrent_flat_map`,
prior blocking operations on `x` synchronize with *op*. So, blocking operations on the same
`concurrent_flat_map` execute sequentially in a multithreaded scenario.

An operation is said to be _blocking on rehashing of_ ``__x__`` if it blocks on `x`
only when an internal rehashing is issued.

Access or modification of an element of a `boost::concurrent_flat_map` passed by reference to a
user-provided visitation function do not introduce data races when the visitation function
is executed internally by the `boost::concurrent_flat_map`.

Any `boost::concurrent_flat_map operation` that inserts or modifies an element `e`
synchronizes with the internal invocation of a visitation function on `e`.

Visitation functions executed by a `boost::concurrent_flat_map` `x` are not allowed to invoke any operation
on `x`; invoking operations on a different `boost::concurrent_flat_map` instance `y` is allowed only
if concurrent outstanding operations on `y` do not access `x` directly or indirectly.

---

=== Configuration Macros

==== `BOOST_UNORDERED_DISABLE_REENTRANCY_CHECK`

In debug builds (more precisely, when
link:../../../assert/doc/html/assert.html#boost_assert_is_void[`BOOST_ASSERT_IS_VOID`^]
is not defined), __container reentrancies__ (illegaly invoking an operation on `m` from within
a function visiting elements of `m`) are detected and signalled through `BOOST_ASSERT_MSG`.
When run-time speed is a concern, the feature can be disabled by globally defining
this macro.

=== Constants

```cpp
static constexpr size_type bulk_visit_size;
```

Chunk size internally used in xref:concurrent_flat_map_bulk_visit[bulk visit] operations.

=== Constructors

==== Default Constructor
```c++
concurrent_flat_map();
```

Constructs an empty table using `hasher()` as the hash function,
`key_equal()` as the key equality predicate and `allocator_type()` as the allocator.

[horizontal]
Postconditions:;; `size() == 0`
Requires:;; If the defaults are used, `hasher`, `key_equal` and `allocator_type` need to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== Bucket Count Constructor
```c++
explicit concurrent_flat_map(size_type n,
                             const hasher& hf = hasher(),
                             const key_equal& eql = key_equal(),
                             const allocator_type& a = allocator_type());
```

Constructs an empty table with at least `n` buckets, using `hf` as the hash
function, `eql` as the key equality predicate, and `a` as the allocator.

[horizontal]
Postconditions:;; `size() == 0`
Requires:;; If the defaults are used, `hasher`, `key_equal` and `allocator_type` need to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== Iterator Range Constructor
[source,c++,subs="+quotes"]
----
template<class InputIterator>
  concurrent_flat_map(InputIterator f, InputIterator l,
                      size_type n = _implementation-defined_,
                      const hasher& hf = hasher(),
                      const key_equal& eql = key_equal(),
                      const allocator_type& a = allocator_type());
----

Constructs an empty table with at least `n` buckets, using `hf` as the hash function, `eql` as the key equality predicate and `a` as the allocator, and inserts the elements from `[f, l)` into it.

[horizontal]
Requires:;; If the defaults are used, `hasher`, `key_equal` and `allocator_type` need to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== Copy Constructor
```c++
concurrent_flat_map(concurrent_flat_map const& other);
```

The copy constructor. Copies the contained elements, hash function, predicate and allocator.

If `Allocator::select_on_container_copy_construction` exists and has the right signature, the allocator will be constructed from its result.

[horizontal]
Requires:;; `value_type` is copy constructible
Concurrency:;; Blocking on `other`.

---

==== Move Constructor
```c++
concurrent_flat_map(concurrent_flat_map&& other);
```

The move constructor. The internal bucket array of `other` is transferred directly to the new table.
The hash function, predicate and allocator are moved-constructed from `other`.

[horizontal]
Concurrency:;; Blocking on `other`.

---

==== Iterator Range Constructor with Allocator
```c++
template<class InputIterator>
  concurrent_flat_map(InputIterator f, InputIterator l, const allocator_type& a);
```

Constructs an empty table using `a` as the allocator, with the default hash function and key equality predicate and inserts the elements from `[f, l)` into it.

[horizontal]
Requires:;; `hasher`, `key_equal` need to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== Allocator Constructor
```c++
explicit concurrent_flat_map(Allocator const& a);
```

Constructs an empty table, using allocator `a`.

---

==== Copy Constructor with Allocator
```c++
concurrent_flat_map(concurrent_flat_map const& other, Allocator const& a);
```

Constructs a table, copying ``other``'s contained elements, hash function, and predicate, but using allocator `a`.

[horizontal]
Concurrency:;; Blocking on `other`.

---

==== Move Constructor with Allocator
```c++
concurrent_flat_map(concurrent_flat_map&& other, Allocator const& a);
```

If `a == other.get_allocator()`, the elements of `other` are transferred directly to the new table;
otherwise, elements are moved-constructed from those of `other`. The hash function and predicate are moved-constructed
from `other`, and the allocator is copy-constructed from `a`.

[horizontal]
Concurrency:;; Blocking on `other`.

---

==== Move Constructor from unordered_flat_map

```c++
concurrent_flat_map(unordered_flat_map<Key, T, Hash, Pred, Allocator>&& other);
```

Move construction from a xref:#unordered_flat_map[`unordered_flat_map`].
The internal bucket array of `other` is transferred directly to the new container.
The hash function, predicate and allocator are moved-constructed from `other`.

[horizontal]
Complexity:;; O(`bucket_count()`) 

---

==== Initializer List Constructor
[source,c++,subs="+quotes"]
----
concurrent_flat_map(std::initializer_list<value_type> il,
                    size_type n = _implementation-defined_
                    const hasher& hf = hasher(),
                    const key_equal& eql = key_equal(),
                    const allocator_type& a = allocator_type());
----

Constructs an empty table with at least `n` buckets, using `hf` as the hash function, `eql` as the key equality predicate and `a`, and inserts the elements from `il` into it.

[horizontal]
Requires:;; If the defaults are used, `hasher`, `key_equal` and `allocator_type` need to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== Bucket Count Constructor with Allocator
```c++
concurrent_flat_map(size_type n, allocator_type const& a);
```

Constructs an empty table with at least `n` buckets, using `hf` as the hash function, the default hash function and key equality predicate and `a` as the allocator.

[horizontal]
Postconditions:;; `size() == 0`
Requires:;; `hasher` and `key_equal` need to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== Bucket Count Constructor with Hasher and Allocator
```c++
concurrent_flat_map(size_type n, hasher const& hf, allocator_type const& a);
```

Constructs an empty table with at least `n` buckets, using `hf` as the hash function, the default key equality predicate and `a` as the allocator.

[horizontal]
Postconditions:;; `size() == 0`
Requires:;; `key_equal` needs to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== Iterator Range Constructor with Bucket Count and Allocator
[source,c++,subs="+quotes"]
----
template<class InputIterator>
  concurrent_flat_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a);
----

Constructs an empty table with at least `n` buckets, using `a` as the allocator and default hash function and key equality predicate, and inserts the elements from `[f, l)` into it.

[horizontal]
Requires:;; `hasher`, `key_equal` need to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== Iterator Range Constructor with Bucket Count and Hasher
[source,c++,subs="+quotes"]
----
    template<class InputIterator>
      concurrent_flat_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
                          const allocator_type& a);
----

Constructs an empty table with at least `n` buckets, using `hf` as the hash function, `a` as the allocator, with the default key equality predicate, and inserts the elements from `[f, l)` into it.

[horizontal]
Requires:;; `key_equal` needs to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== initializer_list Constructor with Allocator

```c++
concurrent_flat_map(std::initializer_list<value_type> il, const allocator_type& a);
```

Constructs an empty table using `a` and default hash function and key equality predicate, and inserts the elements from `il` into it.

[horizontal]
Requires:;; `hasher` and `key_equal` need to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== initializer_list Constructor with Bucket Count and Allocator

```c++
concurrent_flat_map(std::initializer_list<value_type> il, size_type n, const allocator_type& a);
```

Constructs an empty table with at least `n` buckets, using `a` and default hash function and key equality predicate, and inserts the elements from `il` into it.

[horizontal]
Requires:;; `hasher` and `key_equal` need to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

==== initializer_list Constructor with Bucket Count and Hasher and Allocator

```c++
concurrent_flat_map(std::initializer_list<value_type> il, size_type n, const hasher& hf,
                    const allocator_type& a);
```

Constructs an empty table with at least `n` buckets, using `hf` as the hash function, `a` as the allocator and default key equality predicate,and inserts the elements from `il` into it.

[horizontal]
Requires:;; `key_equal` needs to be https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^].

---

=== Destructor

```c++
~concurrent_flat_map();
```

[horizontal]
Note:;; The destructor is applied to every element, and all memory is deallocated

---

=== Assignment

==== Copy Assignment

```c++
concurrent_flat_map& operator=(concurrent_flat_map const& other);
```

The assignment operator. Destroys previously existing elements, copy-assigns the hash function and predicate from `other`, 
copy-assigns the allocator from `other` if `Alloc::propagate_on_container_copy_assignment` exists and `Alloc::propagate_on_container_copy_assignment::value` is `true`,
and finally inserts copies of the elements of `other`.

[horizontal]
Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^]
Concurrency:;; Blocking on `*this` and `other`.

---

==== Move Assignment
```c++
concurrent_flat_map& operator=(concurrent_flat_map&& other)
  noexcept((boost::allocator_traits<Allocator>::is_always_equal::value ||
            boost::allocator_traits<Allocator>::propagate_on_container_move_assignment::value) &&
            std::is_same<pointer, value_type*>::value);
```
The move assignment operator. Destroys previously existing elements, swaps the hash function and predicate from `other`,
and move-assigns the allocator from `other` if `Alloc::propagate_on_container_move_assignment` exists and `Alloc::propagate_on_container_move_assignment::value` is `true`.
If at this point the allocator is equal to `other.get_allocator()`, the internal bucket array of `other` is transferred directly to `*this`;
otherwise, inserts move-constructed copies of the elements of `other`.

[horizontal]
Concurrency:;; Blocking on `*this` and `other`.

---

==== Initializer List Assignment
```c++
concurrent_flat_map& operator=(std::initializer_list<value_type> il);
```

Assign from values in initializer list. All previously existing elements are destroyed.

[horizontal]
Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^]
Concurrency:;; Blocking on `*this`.

---

=== Visitation

==== [c]visit

```c++
template<class F> size_t visit(const key_type& k, F f);
template<class F> size_t visit(const key_type& k, F f) const;
template<class F> size_t cvisit(const key_type& k, F f) const;
template<class K, class F> size_t visit(const K& k, F f);
template<class K, class F> size_t visit(const K& k, F f) const;
template<class K, class F> size_t cvisit(const K& k, F f) const;
```

If an element `x` exists with key equivalent to `k`, invokes `f` with a reference to `x`.
Such reference is const iff `*this` is const.

[horizontal]
Returns:;; The number of elements visited (0 or 1).
Notes:;; The `template<class K, class F>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

---

==== Bulk visit

```c++
template<class FwdIterator, class F>
  size_t visit(FwdIterator first, FwdIterator last, F f);
template<class FwdIterator, class F>
  size_t visit(FwdIterator first, FwdIterator last, F f) const;
template<class FwdIterator, class F>
  size_t cvisit(FwdIterator first, FwdIterator last, F f) const;
```

For each element `k` in the range [`first`, `last`),
if there is an element `x` in the container with key equivalent to `k`,
invokes `f` with a reference to `x`.
Such reference is const iff `*this` is const.

Although functionally equivalent to individually invoking
xref:concurrent_flat_map_cvisit[`[c\]visit`] for each key, bulk visitation
performs generally faster due to internal streamlining optimizations.
It is advisable that `std::distance(first,last)` be at least
xref:#concurrent_flat_map_constants[`bulk_visit_size`] to enjoy
a performance gain: beyond this size, performance is not expected
to increase further.

[horizontal]
Requires:;; `FwdIterator` is a https://en.cppreference.com/w/cpp/named_req/ForwardIterator[LegacyForwardIterator^]
({cpp}11 to {cpp}17), 
or satisfies https://en.cppreference.com/w/cpp/iterator/forward_iterator[std::forward_iterator^] ({cpp}20 and later).
For `K` = `std::iterator_traits<FwdIterator>::value_type`, either `K` is `key_type` or
else `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs.
In the latter case, the library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent.
This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
Returns:;; The number of elements visited.

---

==== [c]visit_all

```c++
template<class F> size_t visit_all(F f);
template<class F> size_t visit_all(F f) const;
template<class F> size_t cvisit_all(F f) const;
```

Successively invokes `f` with references to each of the elements in the table.
Such references are const iff `*this` is const.

[horizontal]
Returns:;; The number of elements visited.

---

==== Parallel [c]visit_all

```c++
template<class ExecutionPolicy, class F> void visit_all(ExecutionPolicy&& policy, F f);
template<class ExecutionPolicy, class F> void visit_all(ExecutionPolicy&& policy, F f) const;
template<class ExecutionPolicy, class F> void cvisit_all(ExecutionPolicy&& policy, F f) const;
```

Invokes `f` with references to each of the elements in the table. Such references are const iff `*this` is const.
Execution is parallelized according to the semantics of the execution policy specified.

[horizontal]
Throws:;; Depending on the exception handling mechanism of the execution policy used, may call `std::terminate` if an exception is thrown within `f`.
Notes:;; Only available in compilers supporting C++17 parallel algorithms. +
+
These overloads only participate in overload resolution if `std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` is `true`. +
+
Unsequenced execution policies are not allowed.

---

==== [c]visit_while

```c++
template<class F> bool visit_while(F f);
template<class F> bool visit_while(F f) const;
template<class F> bool cvisit_while(F f) const;
```

Successively invokes `f` with references to each of the elements in the table until `f` returns `false`
or all the elements are visited.
Such references to the elements are const iff `*this` is const.

[horizontal]
Returns:;; `false` iff `f` ever returns `false`.

---

==== Parallel [c]visit_while

```c++
template<class ExecutionPolicy, class F> bool visit_while(ExecutionPolicy&& policy, F f);
template<class ExecutionPolicy, class F> bool visit_while(ExecutionPolicy&& policy, F f) const;
template<class ExecutionPolicy, class F> bool cvisit_while(ExecutionPolicy&& policy, F f) const;
```

Invokes `f` with references to each of the elements in the table until `f` returns `false`
or all the elements are visited.
Such references to the elements are const iff `*this` is const.
Execution is parallelized according to the semantics of the execution policy specified.

[horizontal]
Returns:;; `false` iff `f` ever returns `false`.
Throws:;; Depending on the exception handling mechanism of the execution policy used, may call `std::terminate` if an exception is thrown within `f`.
Notes:;; Only available in compilers supporting C++17 parallel algorithms. +
+
These overloads only participate in overload resolution if `std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` is `true`. +
+
Unsequenced execution policies are not allowed. +
+
Parallelization implies that execution does not necessary finish as soon as `f` returns `false`, and as a result
`f` may be invoked with further elements for which the return value is also `false`.

---

=== Size and Capacity

==== empty

```c++
[[nodiscard]] bool empty() const noexcept;
```

[horizontal]
Returns:;; `size() == 0`

---

==== size

```c++
size_type size() const noexcept;
```

[horizontal]
Returns:;; The number of elements in the table.

[horizontal]
Notes:;; In the presence of concurrent insertion operations, the value returned may not accurately reflect
the true size of the table right after execution.

---

==== max_size

```c++
size_type max_size() const noexcept;
```

[horizontal]
Returns:;; `size()` of the largest possible table.

---

=== Modifiers

==== emplace
```c++
template<class... Args> bool emplace(Args&&... args);
```

Inserts an object, constructed with the arguments `args`, in the table if and only if there is no element in the table with an equivalent key.

[horizontal]
Requires:;; `value_type` is constructible from `args`.
Returns:;; `true` if an insert took place.
Concurrency:;; Blocking on rehashing of `*this`.
Notes:;; Invalidates pointers and references to elements if a rehashing is issued.

---

==== Copy Insert
```c++
bool insert(const value_type& obj);
bool insert(const init_type& obj);
```

Inserts `obj` in the table if and only if there is no element in the table with an equivalent key.

[horizontal]
Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^].
Returns:;; `true` if an insert took place. +
Concurrency:;; Blocking on rehashing of `*this`.
Notes:;; Invalidates pointers and references to elements if a rehashing is issued. +
+
A call of the form `insert(x)`, where `x` is equally convertible to both `const value_type&` and `const init_type&`, is not ambiguous and selects the `init_type` overload.

---

==== Move Insert
```c++
bool insert(value_type&& obj);
bool insert(init_type&& obj);
```

Inserts `obj` in the table if and only if there is no element in the table with an equivalent key.

[horizontal]
Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/MoveInsertable[MoveInsertable^].
Returns:;; `true` if an insert took place. 
Concurrency:;; Blocking on rehashing of `*this`.
Notes:;; Invalidates pointers and references to elements if a rehashing is issued. +
+
A call of the form `insert(x)`, where `x` is equally convertible to both `value_type&&` and `init_type&&`, is not ambiguous and selects the `init_type` overload.

---

==== Insert Iterator Range
```c++
template<class InputIterator> size_type insert(InputIterator first, InputIterator last);
```

Equivalent to
[listing,subs="+macros,+quotes"]
-----
  while(first != last) this->xref:#concurrent_flat_map_emplace[emplace](*first++);
-----

[horizontal]
Returns:;; The number of elements inserted. 

---

==== Insert Initializer List
```c++
size_type insert(std::initializer_list<value_type> il);
```

Equivalent to
[listing,subs="+macros,+quotes"]
-----
  this->xref:#concurrent_flat_map_insert_iterator_range[insert](il.begin(), il.end());
-----

[horizontal]
Returns:;; The number of elements inserted. 

---

==== emplace_or_[c]visit
```c++
template<class... Args, class F> bool emplace_or_visit(Args&&... args, F&& f);
template<class... Args, class F> bool emplace_or_cvisit(Args&&... args, F&& f);
```

Inserts an object, constructed with the arguments `args`, in the table if there is no element in the table with an equivalent key.
Otherwise, invokes `f` with a reference to the equivalent element; such reference is const iff `emplace_or_cvisit` is used.

[horizontal]
Requires:;; `value_type` is constructible from `args`.
Returns:;; `true` if an insert took place.
Concurrency:;; Blocking on rehashing of `*this`.
Notes:;; Invalidates pointers and references to elements if a rehashing is issued. +
+
The interface is exposition only, as C++ does not allow to declare a parameter `f` after a variadic parameter pack.

---

==== Copy insert_or_[c]visit
```c++
template<class F> bool insert_or_visit(const value_type& obj, F f);
template<class F> bool insert_or_cvisit(const value_type& obj, F f);
template<class F> bool insert_or_visit(const init_type& obj, F f);
template<class F> bool insert_or_cvisit(const init_type& obj, F f);
```

Inserts `obj` in the table if and only if there is no element in the table with an equivalent key.
Otherwise, invokes `f` with a reference to the equivalent element; such reference is const iff a `*_cvisit` overload is used.

[horizontal]
Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^].
Returns:;; `true` if an insert took place. +
Concurrency:;; Blocking on rehashing of `*this`.
Notes:;; Invalidates pointers and references to elements if a rehashing is issued. +
+
In a call of the form `insert_or_[c]visit(obj, f)`, the overloads accepting a `const value_type&` argument participate in overload resolution
only if `std::remove_cv<std::remove_reference<decltype(obj)>::type>::type` is `value_type`.

---

==== Move insert_or_[c]visit
```c++
template<class F> bool insert_or_visit(value_type&& obj, F f);
template<class F> bool insert_or_cvisit(value_type&& obj, F f);
template<class F> bool insert_or_visit(init_type&& obj, F f);
template<class F> bool insert_or_cvisit(init_type&& obj, F f);
```

Inserts `obj` in the table if and only if there is no element in the table with an equivalent key.
Otherwise, invokes `f` with a reference to the equivalent element; such reference is const iff a `*_cvisit` overload is used.

[horizontal]
Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/MoveInsertable[MoveInsertable^].
Returns:;; `true` if an insert took place. +
Concurrency:;; Blocking on rehashing of `*this`.
Notes:;; Invalidates pointers and references to elements if a rehashing is issued. +
+
In a call of the form `insert_or_[c]visit(obj, f)`, the overloads accepting a `value_type&&` argument participate in overload resolution
only if `std::remove_reference<decltype(obj)>::type` is `value_type`.

---

==== Insert Iterator Range or Visit
```c++
template<class InputIterator,class F>
    size_type insert_or_visit(InputIterator first, InputIterator last, F f);
template<class InputIterator,class F>
    size_type insert_or_cvisit(InputIterator first, InputIterator last, F f);
```

Equivalent to
[listing,subs="+macros,+quotes"]
-----
  while(first != last) this->xref:#concurrent_flat_map_emplace_or_cvisit[emplace_or_[c\]visit](*first++, f);
-----

[horizontal]
Returns:;; The number of elements inserted. 

---

==== Insert Initializer List or Visit
```c++
template<class F> size_type insert_or_visit(std::initializer_list<value_type> il, F f);
template<class F> size_type insert_or_cvisit(std::initializer_list<value_type> il, F f);
```

Equivalent to
[listing,subs="+macros,+quotes"]
-----
  this->xref:#concurrent_flat_map_insert_iterator_range_or_visit[insert_or[c\]visit](il.begin(), il.end(), f);
-----

[horizontal]
Returns:;; The number of elements inserted. 

---

==== try_emplace
```c++
template<class... Args> bool try_emplace(const key_type& k, Args&&... args);
template<class... Args> bool try_emplace(key_type&& k, Args&&... args);
template<class K, class... Args> bool try_emplace(K&& k, Args&&... args);
```

Inserts an element constructed from `k` and `args` into the table if there is no existing element with key `k` contained within it.

[horizontal]
Returns:;; `true` if an insert took place. +
Concurrency:;; Blocking on rehashing of `*this`.
Notes:;; This function is similiar to xref:#concurrent_flat_map_emplace[emplace], with the difference that no `value_type` is constructed
if there is an element with an equivalent key; otherwise, the construction is of the form: +
+
--
```c++
// first two overloads
value_type(std::piecewise_construct,
           std::forward_as_tuple(std::forward<Key>(k)),
           std::forward_as_tuple(std::forward<Args>(args)...))

// third overload
value_type(std::piecewise_construct,
           std::forward_as_tuple(std::forward<K>(k)),
           std::forward_as_tuple(std::forward<Args>(args)...))
```

unlike xref:#concurrent_flat_map_emplace[emplace], which simply forwards all arguments to ``value_type``'s constructor.

Invalidates pointers and references to elements if a rehashing is issued.

The `template<class K, class\... Args>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

--

---

==== try_emplace_or_[c]visit
```c++
template<class... Args, class F>
  bool try_emplace_or_visit(const key_type& k, Args&&... args, F&& f);
template<class... Args, class F>
  bool try_emplace_or_cvisit(const key_type& k, Args&&... args, F&& f);
template<class... Args, class F>
  bool try_emplace_or_visit(key_type&& k, Args&&... args, F&& f);
template<class... Args, class F>
  bool try_emplace_or_cvisit(key_type&& k, Args&&... args, F&& f);
template<class K, class... Args, class F>
  bool try_emplace_or_visit(K&& k, Args&&... args, F&& f);
template<class K, class... Args, class F>
  bool try_emplace_or_cvisit(K&& k, Args&&... args, F&& f);
```

Inserts an element constructed from `k` and `args` into the table if there is no existing element with key `k` contained within it.
Otherwise, invokes `f` with a reference to the equivalent element; such reference is const iff a `*_cvisit` overload is used.

[horizontal]
Returns:;; `true` if an insert took place. +
Concurrency:;; Blocking on rehashing of `*this`.
Notes:;; No `value_type` is constructed
if there is an element with an equivalent key; otherwise, the construction is of the form: +
+
--
```c++
// first four overloads
value_type(std::piecewise_construct,
           std::forward_as_tuple(std::forward<Key>(k)),
           std::forward_as_tuple(std::forward<Args>(args)...))

// last two overloads
value_type(std::piecewise_construct,
           std::forward_as_tuple(std::forward<K>(k)),
           std::forward_as_tuple(std::forward<Args>(args)...))
```

Invalidates pointers and references to elements if a rehashing is issued.

The interface is exposition only, as C++ does not allow to declare a parameter `f` after a variadic parameter pack.

The `template<class K, class\... Args, class F>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

--

---

==== insert_or_assign
```c++
template<class M> bool insert_or_assign(const key_type& k, M&& obj);
template<class M> bool insert_or_assign(key_type&& k, M&& obj);
template<class K, class M> bool insert_or_assign(K&& k, M&& obj);
```

Inserts a new element into the table or updates an existing one by assigning to the contained value.

If there is an element with key `k`, then it is updated by assigning `std::forward<M>(obj)`.

If there is no such element, it is added to the table as:
```c++
// first two overloads
value_type(std::piecewise_construct,
           std::forward_as_tuple(std::forward<Key>(k)),
           std::forward_as_tuple(std::forward<M>(obj)))

// third overload
value_type(std::piecewise_construct,
           std::forward_as_tuple(std::forward<K>(k)),
           std::forward_as_tuple(std::forward<M>(obj)))
```

[horizontal]
Returns:;; `true` if an insert took place.
Concurrency:;; Blocking on rehashing of `*this`.
Notes:;; Invalidates pointers and references to elements if a rehashing is issued. +
+
The `template<class K, class M>` only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

---

==== erase
```c++
size_type erase(const key_type& k);
template<class K> size_type erase(const K& k);
```

Erases the element with key equivalent to `k` if it exists.

[horizontal]
Returns:;; The number of elements erased (0 or 1).
Throws:;; Only throws an exception if it is thrown by `hasher` or `key_equal`.
Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

---

==== erase_if by Key
```c++
template<class F> size_type erase_if(const key_type& k, F f);
template<class K, class F> size_type erase_if(const K& k, F f);
```

Erases the element `x` with key equivalent to `k` if it exists and `f(x)` is `true`.

[horizontal]
Returns:;; The number of elements erased (0 or 1).
Throws:;; Only throws an exception if it is thrown by `hasher`, `key_equal` or `f`.
Notes:;; The `template<class K, class F>` overload only participates in overload resolution if `std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` is `false`. +
+
The `template<class K, class F>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

---

==== erase_if
```c++
template<class F> size_type erase_if(F f);
```

Successively invokes `f` with references to each of the elements in the table, and erases those for which `f` returns `true`.

[horizontal]
Returns:;; The number of elements erased.
Throws:;; Only throws an exception if it is thrown by `f`.

---

==== Parallel erase_if
```c++
template<class ExecutionPolicy, class  F> void erase_if(ExecutionPolicy&& policy, F f);
```

Invokes `f` with references to each of the elements in the table, and erases those for which `f` returns `true`.
Execution is parallelized according to the semantics of the execution policy specified.

[horizontal]
Throws:;; Depending on the exception handling mechanism of the execution policy used, may call `std::terminate` if an exception is thrown within `f`.
Notes:;; Only available in compilers supporting C++17 parallel algorithms. +
+
This overload only participates in overload resolution if `std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` is `true`. +
+
Unsequenced execution policies are not allowed.

---

==== swap
```c++
void swap(concurrent_flat_map& other)
  noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
           boost::allocator_traits<Allocator>::propagate_on_container_swap::value);
```

Swaps the contents of the table with the parameter.

If `Allocator::propagate_on_container_swap` is declared and `Allocator::propagate_on_container_swap::value` is `true` then the tables' allocators are swapped. Otherwise, swapping with unequal allocators results in undefined behavior.

[horizontal]
Throws:;; Nothing unless `key_equal` or `hasher` throw on swapping.
Concurrency:;; Blocking on `*this` and `other`.

---

==== clear
```c++
void clear() noexcept;
```

Erases all elements in the table.

[horizontal]
Postconditions:;; `size() == 0`, `max_load() >= max_load_factor() * bucket_count()`
Concurrency:;; Blocking on `*this`.

---

==== merge
```c++
template<class H2, class P2>
  size_type merge(concurrent_flat_map<Key, T, H2, P2, Allocator>& source);
template<class H2, class P2>
  size_type merge(concurrent_flat_map<Key, T, H2, P2, Allocator>&& source);
```

Move-inserts all the elements from `source` whose key is not already present in `*this`, and erases them from `source`.

[horizontal]
Returns:;; The number of elements inserted.
Concurrency:;; Blocking on `*this` and `source`.

---

=== Observers

==== get_allocator
```
allocator_type get_allocator() const noexcept;
```

[horizontal]
Returns:;; The table's allocator.

---

==== hash_function
```
hasher hash_function() const;
```

[horizontal]
Returns:;; The table's hash function.

---

==== key_eq
```
key_equal key_eq() const;
```

[horizontal]
Returns:;; The table's key equality predicate.

---

=== Map Operations

==== count
```c++
size_type        count(const key_type& k) const;
template<class K>
  size_type      count(const K& k) const;
```

[horizontal]
Returns:;; The number of elements with key equivalent to `k` (0 or 1).
Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type. +
+
In the presence of concurrent insertion operations, the value returned may not accurately reflect
the true state of the table right after execution.

---

==== contains
```c++
bool             contains(const key_type& k) const;
template<class K>
  bool           contains(const K& k) const;
```

[horizontal]
Returns:;; A boolean indicating whether or not there is an element with key equal to `k` in the table.
Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.  +
+
In the presence of concurrent insertion operations, the value returned may not accurately reflect
the true state of the table right after execution.

---
=== Bucket Interface

==== bucket_count
```c++
size_type bucket_count() const noexcept;
```

[horizontal]
Returns:;; The size of the bucket array.

---

=== Hash Policy

==== load_factor
```c++
float load_factor() const noexcept;
```

[horizontal]
Returns:;; `static_cast<float>(size())/static_cast<float>(bucket_count())`, or `0` if `bucket_count() == 0`.

---

==== max_load_factor

```c++
float max_load_factor() const noexcept;
```

[horizontal]
Returns:;; Returns the table's maximum load factor.

---

==== Set max_load_factor
```c++
void max_load_factor(float z);
```

[horizontal]
Effects:;; Does nothing, as the user is not allowed to change this parameter. Kept for compatibility with `boost::unordered_map`.

---


==== max_load

```c++
size_type max_load() const noexcept;
```

[horizontal]
Returns:;; The maximum number of elements the table can hold without rehashing, assuming that no further elements will be erased.
Note:;; After construction, rehash or clearance, the table's maximum load is at least `max_load_factor() * bucket_count()`.
This number may decrease on erasure under high-load conditions. +
+
In the presence of concurrent insertion operations, the value returned may not accurately reflect
the true state of the table right after execution.

---

==== rehash
```c++
void rehash(size_type n);
```

Changes if necessary the size of the bucket array so that there are at least `n` buckets, and so that the load factor is less than or equal to the maximum load factor. When applicable, this will either grow or shrink the `bucket_count()` associated with the table.

When `size() == 0`, `rehash(0)` will deallocate the underlying buckets array.

Invalidates pointers and references to elements, and changes the order of elements.

[horizontal]
Throws:;; The function has no effect if an exception is thrown, unless it is thrown by the table's hash function or comparison function.
Concurrency:;; Blocking on `*this`.
---

==== reserve
```c++
void reserve(size_type n);
```

Equivalent to `a.rehash(ceil(n / a.max_load_factor()))`.

Similar to `rehash`, this function can be used to grow or shrink the number of buckets in the table.

Invalidates pointers and references to elements, and changes the order of elements.

[horizontal]
Throws:;; The function has no effect if an exception is thrown, unless it is thrown by the table's hash function or comparison function.
Concurrency:;; Blocking on `*this`.

---

=== Deduction Guides
A deduction guide will not participate in overload resolution if any of the following are true:

  - It has an `InputIterator` template parameter and a type that does not qualify as an input iterator is deduced for that parameter.
  - It has an `Allocator` template parameter and a type that does not qualify as an allocator is deduced for that parameter.
  - It has a `Hash` template parameter and an integral type or a type that qualifies as an allocator is deduced for that parameter.
  - It has a `Pred` template parameter and a type that qualifies as an allocator is deduced for that parameter.

A `size_­type` parameter type in a deduction guide refers to the `size_­type` member type of the
table type deduced by the deduction guide. Its default value coincides with the default value
of the constructor selected.

==== __iter-value-type__
[listings,subs="+macros,+quotes"]
-----
template<class InputIterator>
  using __iter-value-type__ =
    typename std::iterator_traits<InputIterator>::value_type; // exposition only
-----

==== __iter-key-type__
[listings,subs="+macros,+quotes"]
-----
template<class InputIterator>
  using __iter-key-type__ = std::remove_const_t<
    std::tuple_element_t<0, xref:#concurrent_map_iter_value_type[__iter-value-type__]<InputIterator>>>; // exposition only
-----

==== __iter-mapped-type__
[listings,subs="+macros,+quotes"]
-----
template<class InputIterator>
  using __iter-mapped-type__ =
    std::tuple_element_t<1, xref:#concurrent_map_iter_value_type[__iter-value-type__]<InputIterator>>;  // exposition only
-----

==== __iter-to-alloc-type__
[listings,subs="+macros,+quotes"]
-----
template<class InputIterator>
  using __iter-to-alloc-type__ = std::pair<
    std::add_const_t<std::tuple_element_t<0, xref:#concurrent_map_iter_value_type[__iter-value-type__]<InputIterator>>>,
    std::tuple_element_t<1, xref:#concurrent_map_iter_value_type[__iter-value-type__]<InputIterator>>>; // exposition only
-----

=== Equality Comparisons

==== operator==
```c++
template<class Key, class T, class Hash, class Pred, class Alloc>
  bool operator==(const concurrent_flat_map<Key, T, Hash, Pred, Alloc>& x,
                  const concurrent_flat_map<Key, T, Hash, Pred, Alloc>& y);
```

Returns `true` if `x.size() == y.size()` and for every element in `x`, there is an element in `y` with the same key, with an equal value (using `operator==` to compare the value types).

[horizontal]
Concurrency:;; Blocking on `x` and `y`.
Notes:;; Behavior is undefined if the two tables don't have equivalent equality predicates.

---

==== operator!=
```c++
template<class Key, class T, class Hash, class Pred, class Alloc>
  bool operator!=(const concurrent_flat_map<Key, T, Hash, Pred, Alloc>& x,
                  const concurrent_flat_map<Key, T, Hash, Pred, Alloc>& y);
```

Returns `false` if `x.size() == y.size()` and for every element in `x`, there is an element in `y` with the same key, with an equal value (using `operator==` to compare the value types).

[horizontal]
Concurrency:;; Blocking on `x` and `y`.
Notes:;; Behavior is undefined if the two tables don't have equivalent equality predicates.

---

=== Swap
```c++
template<class Key, class T, class Hash, class Pred, class Alloc>
  void swap(concurrent_flat_map<Key, T, Hash, Pred, Alloc>& x,
            concurrent_flat_map<Key, T, Hash, Pred, Alloc>& y)
    noexcept(noexcept(x.swap(y)));
```

Equivalent to
[listing,subs="+macros,+quotes"]
-----
x.xref:#concurrent_flat_map_swap[swap](y);
-----

---

=== erase_if
```c++
template<class K, class T, class H, class P, class A, class Predicate>
  typename concurrent_flat_map<K, T, H, P, A>::size_type
    erase_if(concurrent_flat_map<K, T, H, P, A>& c, Predicate pred);
```

Equivalent to
[listing,subs="+macros,+quotes"]
-----
c.xref:#concurrent_flat_map_erase_if[erase_if](pred);
-----

=== Serialization

``concurrent_flat_map``s can be archived/retrieved by means of
link:../../../serialization/index.html[Boost.Serialization^] using the API provided
by this library. Both regular and XML archives are supported. 

==== Saving an concurrent_flat_map to an archive

Saves all the elements of a `concurrent_flat_map` `x` to an archive (XML archive) `ar`.

[horizontal]
Requires:;; `std::remove_const<key_type>::type` and `std::remove_const<mapped_type>::type`
are serializable (XML serializable), and they do support Boost.Serialization
`save_construct_data`/`load_construct_data` protocol (automatically suported by
https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^]
types).  
Concurrency:;; Blocking on `x`.

---

==== Loading an concurrent_flat_map from an archive

Deletes all preexisting elements of a `concurrent_flat_map` `x` and inserts
from an archive (XML archive) `ar` restored copies of the elements of the
original `concurrent_flat_map` `other` saved to the storage read by `ar`.

[horizontal]
Requires:;; `x.key_equal()` is functionally equivalent to `other.key_equal()`.
Concurrency:;; Blocking on `x`.
