Class Template 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++ 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

// #include <boost/unordered/concurrent_flat_map.hpp>

namespace boost {
namespace unordered {

  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;

    using stats                = stats-type; // if statistics are enabled

    // constants
    static constexpr size_type bulk_visit_size = implementation-defined;

    // construct/copy/destroy
    concurrent_flat_map();
    explicit 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>
      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());
    concurrent_flat_map(const concurrent_flat_map& other);
    concurrent_flat_map(concurrent_flat_map&& other);
    template<class InputIterator>
      concurrent_flat_map(InputIterator f, InputIterator l,const allocator_type& a);
    explicit concurrent_flat_map(const Allocator& a);
    concurrent_flat_map(const concurrent_flat_map& other, const Allocator& a);
    concurrent_flat_map(concurrent_flat_map&& other, const Allocator& a);
    concurrent_flat_map(unordered_flat_map<Key, T, Hash, Pred, Allocator>&& other);
    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());
    concurrent_flat_map(size_type n, const allocator_type& a);
    concurrent_flat_map(size_type n, const hasher& hf, const allocator_type& a);
    template<class InputIterator>
      concurrent_flat_map(InputIterator f, InputIterator l, size_type n,
                          const allocator_type& a);
    template<class InputIterator>
      concurrent_flat_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
                          const allocator_type& a);
    concurrent_flat_map(std::initializer_list<value_type> il, const allocator_type& a);
    concurrent_flat_map(std::initializer_list<value_type> il, size_type n,
                        const allocator_type& a);
    concurrent_flat_map(std::initializer_list<value_type> il, size_type n, const hasher& hf,
                        const allocator_type& a);
    ~concurrent_flat_map();
    concurrent_flat_map& operator=(const concurrent_flat_map& other);
    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);
    concurrent_flat_map& operator=(std::initializer_list<value_type>);
    allocator_type get_allocator() const noexcept;


    // visitation
    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;

    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;

    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;
    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;

    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;
    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;

    // capacity
    [[nodiscard]] bool empty() const noexcept;
    size_type size() const noexcept;
    size_type max_size() const noexcept;

    // modifiers
    template<class... Args> bool emplace(Args&&... args);
    bool insert(const value_type& obj);
    bool insert(const init_type& obj);
    bool insert(value_type&& obj);
    bool insert(init_type&& obj);
    template<class InputIterator> size_type insert(InputIterator first, InputIterator last);
    size_type insert(std::initializer_list<value_type> il);

    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);
    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);
    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);
    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);
    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);

    template<class... Args, class F1, class F2>
      bool emplace_and_visit(Args&&... args, F1&& f1, F2&& f2);
    template<class... Args, class F1, class F2>
      bool emplace_and_cvisit(Args&&... args, F1&& f1, F2&& f2);
    template<class F1, class F2> bool insert_and_visit(const value_type& obj, F1 f1, F2 f2);
    template<class F1, class F2> bool insert_and_cvisit(const value_type& obj, F1 f1, F2 f2);
    template<class F1, class F2> bool insert_and_visit(const init_type& obj, F1 f1, F2 f2);
    template<class F1, class F2> bool insert_and_cvisit(const init_type& obj, F1 f1, F2 f2);
    template<class F1, class F2> bool insert_and_visit(value_type&& obj, F1 f1, F2 f2);
    template<class F1, class F2> bool insert_and_cvisit(value_type&& obj, F1 f1, F2 f2);
    template<class F1, class F2> bool insert_and_visit(init_type&& obj, F1 f1, F2 f2);
    template<class F1, class F2> bool insert_and_cvisit(init_type&& obj, F1 f1, F2 f2);
    template<class InputIterator,class F1, class F2>
      size_type insert_and_visit(InputIterator first, InputIterator last, F1 f1, F2 f2);
    template<class InputIterator,class F1, class F2>
      size_type insert_and_cvisit(InputIterator first, InputIterator last, F1 f1, F2 f2);
    template<class F1, class F2>
      size_type insert_and_visit(std::initializer_list<value_type> il, F1 f1, F2 f2);
    template<class F1, class F2>
      size_type insert_and_cvisit(std::initializer_list<value_type> il, F1 f1, F2 f2);

    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);

    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);

    template<class... Args, class F1, class F2>
      bool try_emplace_and_visit(const key_type& k, Args&&... args, F1&& f1, F2&& f2);
    template<class... Args, class F1, class F2>
      bool try_emplace_and_cvisit(const key_type& k, Args&&... args, F1&& f1, F2&& f2);
    template<class... Args, class F1, class F2>
      bool try_emplace_and_visit(key_type&& k, Args&&... args, F1&& f1, F2&& f2);
    template<class... Args, class F1, class F2>
      bool try_emplace_and_cvisit(key_type&& k, Args&&... args, F1&& f1, F2&& f2);
    template<class K, class... Args, class F1, class F2>
      bool try_emplace_and_visit(K&& k, Args&&... args, F1&& f1, F2&& f2);
    template<class K, class... Args, class F1, class F2>
      bool try_emplace_and_cvisit(K&& k, Args&&... args, F1&& f1, F2&& f2);

    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);

    size_type erase(const key_type& k);
    template<class K> size_type erase(const K& k);

    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);
    template<class F> size_type erase_if(F f);
    template<class ExecutionPolicy, class  F> void erase_if(ExecutionPolicy&& policy, F f);

    void      swap(concurrent_flat_map& other)
      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
               boost::allocator_traits<Allocator>::propagate_on_container_swap::value);
    void      clear() noexcept;

    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);

    // observers
    hasher hash_function() const;
    key_equal key_eq() const;

    // map operations
    size_type        count(const key_type& k) const;
    template<class K>
      size_type      count(const K& k) const;
    bool             contains(const key_type& k) const;
    template<class K>
      bool           contains(const K& k) const;

    // bucket interface
    size_type bucket_count() const noexcept;

    // hash policy
    float load_factor() const noexcept;
    float max_load_factor() const noexcept;
    void max_load_factor(float z);
    size_type max_load() const noexcept;
    void rehash(size_type n);
    void reserve(size_type n);

    // statistics (if enabled)
    stats get_stats() const;
    void reset_stats() noexcept;
  };

  // Deduction Guides
  template<class InputIterator,
           class Hash = boost::hash<iter-key-type<InputIterator>>,
           class Pred = std::equal_to<iter-key-type<InputIterator>>,
           class Allocator = std::allocator<iter-to-alloc-type<InputIterator>>>
    concurrent_flat_map(InputIterator, InputIterator, typename see below::size_type = see below,
                        Hash = Hash(), Pred = Pred(), Allocator = Allocator())
      -> concurrent_flat_map<iter-key-type<InputIterator>, 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 see below::size_type = 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 see below::size_type, Allocator)
      -> concurrent_flat_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
                             boost::hash<iter-key-type<InputIterator>>,
                             std::equal_to<iter-key-type<InputIterator>>, Allocator>;

  template<class InputIterator, class Allocator>
    concurrent_flat_map(InputIterator, InputIterator, Allocator)
      -> concurrent_flat_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
                             boost::hash<iter-key-type<InputIterator>>,
                             std::equal_to<iter-key-type<InputIterator>>, Allocator>;

  template<class InputIterator, class Hash, class Allocator>
    concurrent_flat_map(InputIterator, InputIterator, typename see below::size_type, Hash,
                        Allocator)
      -> concurrent_flat_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Hash,
                             std::equal_to<iter-key-type<InputIterator>>, Allocator>;

  template<class Key, class T, class Allocator>
    concurrent_flat_map(std::initializer_list<std::pair<Key, T>>, typename 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 see below::size_type,
                        Hash, Allocator)
      -> concurrent_flat_map<Key, T, Hash, std::equal_to<Key>, Allocator>;

} // namespace unordered
} // namespace boost

Description

Template Parameters

Key

Key and T must be MoveConstructible. std::pair<const Key, T> must be EmplaceConstructible into the table from any std::pair object convertible to it, and it also must be 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 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 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.

When executed internally by a boost::concurrent_flat_map, the following operations by a user-provided visitation function on the element passed do not introduce data races:

  • Read access to the element.

  • Non-mutable modification of the element.

  • Mutable modification of the element:

    • Within a container function accepting two visitation functions, always for the first function.

    • Within a non-const container function whose name does not contain cvisit, for the last (or only) visitation function.

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 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.


BOOST_UNORDERED_ENABLE_STATS

Globally define this macro to enable statistics calculation for the table. Note that this option decreases the overall performance of many operations.


Constants

static constexpr size_type bulk_visit_size;

Chunk size internally used in bulk visit operations.

Constructors

Default Constructor

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.

Postconditions:

size() == 0

Requires:

If the defaults are used, hasher, key_equal and allocator_type need to be DefaultConstructible.


Bucket Count Constructor

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.

Postconditions:

size() == 0

Requires:

If the defaults are used, hasher, key_equal and allocator_type need to be DefaultConstructible.


Iterator Range Constructor

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.

Requires:

If the defaults are used, hasher, key_equal and allocator_type need to be DefaultConstructible.


Copy Constructor

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.

Requires:

value_type is copy constructible

Concurrency:

Blocking on other.


Move Constructor

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. If statistics are enabled, transfers the internal statistical information from other and calls other.reset_stats().

Concurrency:

Blocking on other.


Iterator Range Constructor with Allocator

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.

Requires:

hasher, key_equal need to be DefaultConstructible.


Allocator Constructor

explicit concurrent_flat_map(Allocator const& a);

Constructs an empty table, using allocator a.


Copy Constructor with Allocator

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.

Concurrency:

Blocking on other.


Move Constructor with Allocator

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. If statistics are enabled, transfers the internal statistical information from other iff a == other.get_allocator(), and always calls other.reset_stats().

Concurrency:

Blocking on other.


Move Constructor from unordered_flat_map

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

Move construction from a 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. If statistics are enabled, transfers the internal statistical information from other and calls other.reset_stats().

Complexity:

O(bucket_count())


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());

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.

Requires:

If the defaults are used, hasher, key_equal and allocator_type need to be DefaultConstructible.


Bucket Count Constructor with Allocator

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.

Postconditions:

size() == 0

Requires:

hasher and key_equal need to be DefaultConstructible.


Bucket Count Constructor with Hasher and Allocator

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.

Postconditions:

size() == 0

Requires:

key_equal needs to be DefaultConstructible.


Iterator Range Constructor with Bucket Count and Allocator

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.

Requires:

hasher, key_equal need to be DefaultConstructible.


Iterator Range Constructor with Bucket Count and Hasher

    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.

Requires:

key_equal needs to be DefaultConstructible.


initializer_list Constructor with Allocator

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.

Requires:

hasher and key_equal need to be DefaultConstructible.


initializer_list Constructor with Bucket Count and Allocator

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.

Requires:

hasher and key_equal need to be DefaultConstructible.


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);

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.

Requires:

key_equal needs to be DefaultConstructible.


Destructor

~concurrent_flat_map();
Note:

The destructor is applied to every element, and all memory is deallocated


Assignment

Copy Assignment

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.

Requires:

value_type is CopyInsertable

Concurrency:

Blocking on *this and other.


Move Assignment

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. If statistics are enabled, transfers the internal statistical information from other iff the final allocator is equal to other.get_allocator(), and always calls other.reset_stats().

Concurrency:

Blocking on *this and other.


Initializer List Assignment

concurrent_flat_map& operator=(std::initializer_list<value_type> il);

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

Requires:

value_type is CopyInsertable

Concurrency:

Blocking on *this.


Visitation

[c]visit

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.

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

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 [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 bulk_visit_size to enjoy a performance gain: beyond this size, performance is not expected to increase further.

Requires:

FwdIterator is a LegacyForwardIterator (C++11 to C++17), or satisfies std::forward_iterator (C++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

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.

Returns:

The number of elements visited.


Parallel [c]visit_all

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.

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

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.

Returns:

false iff f ever returns false.


Parallel [c]visit_while

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.

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

[[nodiscard]] bool empty() const noexcept;
Returns:

size() == 0


size

size_type size() const noexcept;
Returns:

The number of elements in the table.

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

size_type max_size() const noexcept;
Returns:

size() of the largest possible table.


Modifiers

emplace

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.

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.

If args…​ is of the form k,v, it delays constructing the whole object until it is certain that an element should be inserted, using only the k argument to check.


Copy Insert

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.

Requires:

value_type is 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

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.

Requires:

value_type is 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

template<class InputIterator> size_type insert(InputIterator first, InputIterator last);

Equivalent to

  while(first != last) this->emplace(*first++);
Returns:

The number of elements inserted.


Insert Initializer List

size_type insert(std::initializer_list<value_type> il);

Equivalent to

  this->insert(il.begin(), il.end());
Returns:

The number of elements inserted.


emplace_or_[c]visit

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.

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

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.

Requires:

value_type is 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

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.

Requires:

value_type is 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

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

  while(first != last) this->emplace_or_[c]visit(*first++, f);
Returns:

The number of elements inserted.


Insert Initializer List or Visit

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

  this->insert_or_[c]visit(il.begin(), il.end(), std::ref(f));
Returns:

The number of elements inserted.


emplace_and_[c]visit

template<class... Args, class F1, class F2>
  bool emplace_and_visit(Args&&... args, F1&& f1, F2&& f2);
template<class... Args, class F1, class F2>
  bool emplace_and_cvisit(Args&&... args, F1&& f1, F2&& f2);

Inserts an object, constructed with the arguments args, in the table if there is no element in the table with an equivalent key, and then invokes f1 with a non-const reference to the newly created element. Otherwise, invokes f2 with a reference to the equivalent element; such reference is const iff emplace_and_cvisit is used.

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 parameters f1 and f2 after a variadic parameter pack.


Copy insert_and_[c]visit

template<class F1, class F2> bool insert_and_visit(const value_type& obj, F1 f1, F2 f2);
template<class F1, class F2> bool insert_and_cvisit(const value_type& obj, F1 f1, F2 f2);
template<class F1, class F2> bool insert_and_visit(const init_type& obj, F1 f1, F2 f2);
template<class F1, class F2> bool insert_and_cvisit(const init_type& obj, F1 f1, F2 f2);

Inserts obj in the table if and only if there is no element in the table with an equivalent key, and then invokes f1 with a non-const reference to the newly created element. Otherwise, invokes f2 with a reference to the equivalent element; such reference is const iff a *_cvisit overload is used.

Requires:

value_type is 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_and_[c]visit(obj, f1, f2), 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_and_[c]visit

template<class F1, class F2> bool insert_and_visit(value_type&& obj, F1 f1, F2 f2);
template<class F1, class F2> bool insert_and_cvisit(value_type&& obj, F1 f1, F2 f2);
template<class F1, class F2> bool insert_and_visit(init_type&& obj, F1 f1, F2 f2);
template<class F1, class F2> bool insert_and_cvisit(init_type&& obj, F1 f1, F2 f2);

Inserts obj in the table if and only if there is no element in the table with an equivalent key, and then invokes f1 with a non-const reference to the newly created element. Otherwise, invokes f2 with a reference to the equivalent element; such reference is const iff a *_cvisit overload is used.

Requires:

value_type is 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_and_[c]visit(obj, f1, f2), 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 and Visit

template<class InputIterator, class F1, class F2>
    size_type insert_or_visit(InputIterator first, InputIterator last, F1 f1, F2 f2);
template<class InputIterator, class F1, class F2>
    size_type insert_or_cvisit(InputIterator first, InputIterator last, F1 f1, F2 f2);

Equivalent to

  while(first != last) this->emplace_and_[c]visit(*first++, f1, f2);
Returns:

The number of elements inserted.


Insert Initializer List and Visit

template<class F1, class F2>
  size_type insert_and_visit(std::initializer_list<value_type> il, F1 f1, F2 f2);
template<class F1, class F2>
  size_type insert_and_cvisit(std::initializer_list<value_type> il, F1 f1, F2 f2);

Equivalent to

  this->insert_and_[c]visit(il.begin(), il.end(), std::ref(f1), std::ref(f2));
Returns:

The number of elements inserted.


try_emplace

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.

Returns:

true if an insert took place.

Concurrency:

Blocking on rehashing of *this.

Notes:

This function is similiar to 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:

// 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 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

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.

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:

// 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.


try_emplace_and_[c]visit

template<class... Args, class F1, class F2>
  bool try_emplace_and_visit(const key_type& k, Args&&... args, F1&& f1, F2&& f2);
template<class... Args, class F1, class F2>
  bool try_emplace_and_cvisit(const key_type& k, Args&&... args, F1&& f1, F2&& f2);
template<class... Args, class F1, class F2>
  bool try_emplace_and_visit(key_type&& k, Args&&... args, F1&& f1, F2&& f2);
template<class... Args, class F1, class F2>
  bool try_emplace_and_cvisit(key_type&& k, Args&&... args, F1&& f1, F2&& f2);
template<class K, class... Args, class F1, class F2>
  bool try_emplace_and_visit(K&& k, Args&&... args, F1&& f1, F2&& f2);
template<class K, class... Args, class F1, class F2>
  bool try_emplace_and_cvisit(K&& k, Args&&... args, F1&& f1, F2&& f2);

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

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:

// 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 parameters f1 and f2 after a variadic parameter pack.

The template<class K, class... Args, class F1, class F2> 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

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:

// 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)))
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

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.

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

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.

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

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.

Returns:

The number of elements erased.

Throws:

Only throws an exception if it is thrown by f.


Parallel erase_if

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.

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

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.

Throws:

Nothing unless key_equal or hasher throw on swapping.

Concurrency:

Blocking on *this and other.


clear

void clear() noexcept;

Erases all elements in the table.

Postconditions:

size() == 0, max_load() >= max_load_factor() * bucket_count()

Concurrency:

Blocking on *this.


merge

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.

Returns:

The number of elements inserted.

Concurrency:

Blocking on *this and source.


Observers

get_allocator

allocator_type get_allocator() const noexcept;
Returns:

The table’s allocator.


hash_function

hasher hash_function() const;
Returns:

The table’s hash function.


key_eq

key_equal key_eq() const;
Returns:

The table’s key equality predicate.


Map Operations

count

size_type        count(const key_type& k) const;
template<class K>
  size_type      count(const K& k) const;
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

bool             contains(const key_type& k) const;
template<class K>
  bool           contains(const K& k) const;
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

size_type bucket_count() const noexcept;
Returns:

The size of the bucket array.


Hash Policy

load_factor

float load_factor() const noexcept;
Returns:

static_cast<float>(size())/static_cast<float>(bucket_count()), or 0 if bucket_count() == 0.


max_load_factor

float max_load_factor() const noexcept;
Returns:

Returns the table’s maximum load factor.


Set max_load_factor

void max_load_factor(float z);
Effects:

Does nothing, as the user is not allowed to change this parameter. Kept for compatibility with boost::unordered_map.


max_load

size_type max_load() const noexcept;
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

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.

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

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.

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.


Statistics

get_stats

stats get_stats() const;
Returns:

A statistical description of the insertion and lookup operations performed by the table so far.

Notes:

Only available if statistics calculation is enabled.


reset_stats

void reset_stats() noexcept;
Effects:

Sets to zero the internal statistics kept by the table.

Notes:

Only available if statistics calculation is enabled.


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

template<class InputIterator>
  using iter-value-type =
    typename std::iterator_traits<InputIterator>::value_type; // exposition only

iter-key-type

template<class InputIterator>
  using iter-key-type = std::remove_const_t<
    std::tuple_element_t<0, iter-value-type<InputIterator>>>; // exposition only

iter-mapped-type

template<class InputIterator>
  using iter-mapped-type =
    std::tuple_element_t<1, iter-value-type<InputIterator>>;  // exposition only

iter-to-alloc-type

template<class InputIterator>
  using iter-to-alloc-type = std::pair<
    std::add_const_t<std::tuple_element_t<0, iter-value-type<InputIterator>>>,
    std::tuple_element_t<1, iter-value-type<InputIterator>>>; // exposition only

Equality Comparisons

operator==

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).

Concurrency:

Blocking on x and y.

Notes:

Behavior is undefined if the two tables don’t have equivalent equality predicates.


operator!=

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).

Concurrency:

Blocking on x and y.

Notes:

Behavior is undefined if the two tables don’t have equivalent equality predicates.


Swap

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

x.swap(y);

erase_if

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

c.erase_if(pred);

Serialization

concurrent_flat_maps can be archived/retrieved by means of 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.

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 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.

Requires:

x.key_equal() is functionally equivalent to other.key_equal().

Concurrency:

Blocking on x.