en	﻿[#concurrent_node_set]

en	Class Template concurrent_node_set

en	:idprefix: concurrent_node_set_

en	`boost::concurrent_node_set` — A node-based hash table that stores unique values and allows for concurrent element insertion, erasure, lookup and access without external synchronization mechanisms.

en	Even though it acts as a container, `boost::concurrent_node_set` 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 is done through user-provided _visitation functions_ that are passed to `concurrent_node_set` operations where they are executed internally in a controlled fashion. Such visitation-based API allows for low-contention concurrent usage scenarios.

en	The internal data structure of `boost::concurrent_node_set` is similar to that of `boost::unordered_node_set`. Unlike `boost::concurrent_flat_set`, pointer stability and node handling functionalities are provided, at the expense of potentially lower performance.

en	Synopsis

en	---

en	Description

en	*Template Parameters*

en	_Key_

en	`Key` must be https://en.cppreference.com/w/cpp/named_req/MoveInsertable[MoveInsertable^] into the container

en	and https://en.cppreference.com/w/cpp/named_req/Erasable[Erasable^] from the container.

en	_Hash_

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

en	_Pred_

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

en	_Allocator_

en	An allocator whose value type is the same as the table's value type.

en	`std::allocator_traits<Allocator>::pointer` and `std::allocator_traits<Allocator>::const_pointer` must be convertible to/from `value_type*` and `const value_type*`, respectively.

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

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

en	If `link:../../../../../container_hash/doc/html/hash.html#ref_hash_is_avalanchinghash[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.

en	---

en	Concurrency Requirements and Guarantees

en	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:

en	Copy construction from `al` of an allocator rebound from `Alloc`

en	`std::allocator_traits<Alloc>::allocate`

en	`std::allocator_traits<Alloc>::deallocate`

en	`std::allocator_traits<Alloc>::construct`

en	`std::allocator_traits<Alloc>::destroy`

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

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

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

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

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

en	Read access to the element.

en	Non-mutable modification of the element.

en	Mutable modification of the element:

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

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

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

en	---

en	Configuration Macros

en	`BOOST_UNORDERED_DISABLE_REENTRANCY_CHECK`

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

en	---

en	`BOOST_UNORDERED_ENABLE_STATS`

en	Globally define this macro to enable xref:reference/stats.adoc#stats[statistics calculation] for the table. Note that this option decreases the overall performance of many operations.

en	---

en	Typedefs

en	A class for holding extracted table elements, modelling https://en.cppreference.com/w/cpp/container/node_handle[NodeHandle].

en	---

en	A specialization of an internal class template:

en	with `NodeType` = `node_type`.

en	---

en	Constants

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

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

en	Constructors

en	Default Constructor

en	```c++ concurrent_node_set(); ```

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

en	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^].

en	---

en	Bucket Count Constructor

en	```c++ explicit concurrent_node_set(size_type n, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); ```

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

en	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^].

en	---

en	Iterator Range Constructor

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

en	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^].

en	---

en	Copy Constructor

en	```c++ concurrent_node_set(concurrent_node_set const& other); ```

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

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

en	Requires:;; `value_type` is copy constructible Concurrency:;; Blocking on `other`.

en	---

en	Move Constructor

en	```c++ concurrent_node_set(concurrent_node_set&& other); ```

en	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 xref:concurrent_node_set_boost_unordered_enable_stats[enabled], transfers the internal statistical information from `other` and calls `other.reset_stats()`.

en	Concurrency:;; Blocking on `other`.

en	---

en	Iterator Range Constructor with Allocator

en	```c++ template<class InputIterator> concurrent_node_set(InputIterator f, InputIterator l, const allocator_type& a); ```

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

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

en	---

en	Allocator Constructor

en	```c++ explicit concurrent_node_set(Allocator const& a); ```

en	Constructs an empty table, using allocator `a`.

en	---

en	Copy Constructor with Allocator

en	```c++ concurrent_node_set(concurrent_node_set const& other, Allocator const& a); ```

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

en	Concurrency:;; Blocking on `other`.

en	---

en	Move Constructor with Allocator

en	```c++ concurrent_node_set(concurrent_node_set&& other, Allocator const& a); ```

en	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 xref:concurrent_node_set_boost_unordered_enable_stats[enabled], transfers the internal statistical information from `other` iff `a == other.get_allocator()`, and always calls `other.reset_stats()`.

en	Concurrency:;; Blocking on `other`.

en	---

en	Move Constructor from unordered_node_set

en	```c++ concurrent_node_set(unordered_node_set<Key, Hash, Pred, Allocator>&& other); ```

en	Move construction from a xref:#unordered_node_set[`unordered_node_set`]. 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 xref:concurrent_node_set_boost_unordered_enable_stats[enabled], transfers the internal statistical information from `other` and calls `other.reset_stats()`.

en	Complexity:;; O(`bucket_count()`)

en	---

en	Initializer List Constructor

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

en	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^].

en	---

en	Bucket Count Constructor with Allocator

en	```c++ concurrent_node_set(size_type n, allocator_type const& a); ```

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

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

en	---

en	Bucket Count Constructor with Hasher and Allocator

en	```c++ concurrent_node_set(size_type n, hasher const& hf, allocator_type const& a); ```

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

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

en	---

en	Iterator Range Constructor with Bucket Count and Allocator

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

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

en	---

en	Iterator Range Constructor with Bucket Count and Hasher

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

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

en	---

en	initializer_list Constructor with Allocator

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

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

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

en	---

en	initializer_list Constructor with Bucket Count and Allocator

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

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

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

en	---

en	initializer_list Constructor with Bucket Count and Hasher and Allocator

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

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

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

en	---

en	Destructor

en	```c++ ~concurrent_node_set(); ```

en	Note:;; The destructor is applied to every element, and all memory is deallocated

en	---

en	Assignment

en	Copy Assignment

en	```c++ concurrent_node_set& operator=(concurrent_node_set const& other); ```

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

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

en	---

en	Move Assignment

en	```c++ concurrent_node_set& operator=(concurrent_node_set&& other) noexcept(boost::allocator_traits<Allocator>::is_always_equal::value || boost::allocator_traits<Allocator>::propagate_on_container_move_assignment::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 xref:concurrent_node_set_boost_unordered_enable_stats[enabled], transfers the internal statistical information from `other` iff the final allocator is equal to `other.get_allocator()`, and always calls `other.reset_stats()`.

en	Concurrency:;; Blocking on `*this` and `other`.

en	---

en	Initializer List Assignment

en	```c++ concurrent_node_set& operator=(std::initializer_list<value_type> il); ```

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

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

en	---

en	Visitation

en	[c]visit

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

en	If an element `x` exists with key equivalent to `k`, invokes `f` with a const reference to `x`.

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

en	---

en	Bulk visit

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

en	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 const reference to `x`.

en	Although functionally equivalent to individually invoking xref:concurrent_node_set_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_node_set_constants[`bulk_visit_size`] to enjoy a performance gain: beyond this size, performance is not expected to increase further.

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

en	---

en	[c]visit_all

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

en	Successively invokes `f` with const references to each of the elements in the table.

en	Returns:;; The number of elements visited.

en	---

en	Parallel [c]visit_all

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

en	Invokes `f` with const references to each of the elements in the table. Execution is parallelized according to the semantics of the execution policy specified.

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

en	---

en	[c]visit_while

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

en	Successively invokes `f` with const references to each of the elements in the table until `f` returns `false` or all the elements are visited.

en	Returns:;; `false` iff `f` ever returns `false`.

en	---

en	Parallel [c]visit_while

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

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

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

en	---

en	Size and Capacity

en	empty

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

en	Returns:;; `size() == 0`

en	---

en	size

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

en	Returns:;; The number of elements in the table.

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

en	---

en	max_size

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

en	Returns:;; `size()` of the largest possible table.

en	---

en	Modifiers

en	emplace

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

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

en	Requires:;; `value_type` is constructible from `args`. Returns:;; `true` if an insert took place. Concurrency:;; Blocking on rehashing of `*this`.

en	---

en	Copy Insert

en	```c++ bool insert(const value_type& obj); ```

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

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

en	---

en	Move Insert

en	```c++ bool insert(value_type&& obj); ```

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

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

en	---

en	Transparent Insert

en	```c++ template<class K> bool insert(K&& k); ```

en	Inserts an element constructed from `std::forward<K>(k)` in the container if and only if there is no element in the container with an equivalent key.

en	Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[EmplaceConstructible^] from `k`. Returns:;; `true` if an insert took place. Concurrency:;; Blocking on rehashing of `*this`. Notes:;; This 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.

en	---

en	Insert Iterator Range

en	```c++ template<class InputIterator> size_type insert(InputIterator first, InputIterator last); ```

en	Equivalent to [listing,subs="+macros,+quotes"]

en	Returns:;; The number of elements inserted.

en	---

en	Insert Initializer List

en	```c++ size_type insert(std::initializer_list<value_type> il); ```

en	Equivalent to [listing,subs="+macros,+quotes"]

en	Returns:;; The number of elements inserted.

en	---

en	Insert Node

en	```c++ insert_return_type insert(node_type&& nh); ```

en	If `nh` is not empty, inserts the associated element in the table if and only if there is no element in the table with a key equivalent to `nh.value()`. `nh` is empty when the function returns.

en	Returns:;; An `insert_return_type` object constructed from `inserted` and `node`: +

en	If `nh` is empty, `inserted` is `false` and `node` is empty.

en	Otherwise if the insertion took place, `inserted` is true and `node` is empty.

en	If the insertion failed, `inserted` is false and `node` has the previous value of `nh`.

en	Throws:;; If an exception is thrown by an operation other than a call to `hasher` the function has no effect. Concurrency:;; Blocking on rehashing of `*this`. Notes:;; Behavior is undefined if `nh` is not empty and the allocators of `nh` and the container are not equal.

en	---

en	emplace_or_[c]visit

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

en	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 const reference to the equivalent element.

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

en	---

en	Copy insert_or_[c]visit

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

en	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 const reference to the equivalent element.

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

en	---

en	Move insert_or_[c]visit

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

en	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 const reference to the equivalent element.

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

en	---

en	Transparent insert_or_[c]visit

en	```c++ template<class K, class F> bool insert_or_visit(K&& k, F f); template<class K, class F> bool insert_or_cvisit(K&& k, F f); ```

en	Inserts an element constructed from `std::forward<K>(k)` in the container if and only if there is no element in the container with an equivalent key. Otherwise, invokes `f` with a const reference to the equivalent element.

en	Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[EmplaceConstructible^] from `k`. Returns:;; `true` if an insert took place. Concurrency:;; Blocking on rehashing of `*this`. Notes:;; These 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.

en	---

en	Insert Iterator Range or Visit

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

en	Equivalent to [listing,subs="+macros,+quotes"]

en	Returns:;; The number of elements inserted.

en	---

en	Insert Initializer List or Visit

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

en	Equivalent to [listing,subs="+macros,+quotes"]

en	Returns:;; The number of elements inserted.

en	---

en	Insert Node or Visit

en	```c++ template<class F> insert_return_type insert_or_visit(node_type&& nh, F f); template<class F> insert_return_type insert_or_cvisit(node_type&& nh, F f); ```

en	If `nh` is empty, does nothing. Otherwise, inserts the associated element in the table if and only if there is no element in the table with a key equivalent to `nh.value()`. Otherwise, invokes `f` with a const reference to the equivalent element.

en	Returns:;; An `insert_return_type` object constructed from `inserted` and `node`: +

en	If `nh` is empty, `inserted` is `false` and `node` is empty.

en	Otherwise if the insertion took place, `inserted` is true and `node` is empty.

en	If the insertion failed, `inserted` is false and `node` has the previous value of `nh`.

en	Throws:;; If an exception is thrown by an operation other than a call to `hasher` or call to `f`, the function has no effect. Concurrency:;; Blocking on rehashing of `*this`. Notes:;; Behavior is undefined if `nh` is not empty and the allocators of `nh` and the container are not equal.

en	---

en	emplace_and_[c]visit

en	```c++ template<class... Args, class F1, class F2> bool emplace_or_visit(Args&&... args, F1&& f1, F2&& f2); template<class... Args, class F1, class F2> bool emplace_or_cvisit(Args&&... args, F1&& f1, F2&& f2); ```

en	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 const reference to the newly created element. Otherwise, invokes `f2` with a const reference to the equivalent element.

en	Requires:;; `value_type` is constructible from `args`. Returns:;; `true` if an insert took place. Concurrency:;; Blocking on rehashing of `*this`. Notes:;; The interface is exposition only, as C++ does not allow to declare parameters `f1` and `f2` after a variadic parameter pack.

en	---

en	Copy insert_and_[c]visit

en	```c++ 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 f2, F2 f2); ```

en	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 const reference to the newly created element. Otherwise, invokes `f` with a const reference to the equivalent element.

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

en	---

en	Move insert_and_[c]visit

en	```c++ 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); ```

en	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 const reference to the newly created element. Otherwise, invokes `f2` with a const reference to the equivalent element.

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

en	---

en	Transparent insert_and_[c]visit

en	```c++ template<class K, class F1, class F2> bool insert_and_visit(K&& k, F1 f1, F2 f2); template<class K, class F1, class F2> bool insert_and_cvisit(K&& k, F1 f1, F2 f2); ```

en	Inserts an element constructed from `std::forward<K>(k)` in the container if and only if there is no element in the container with an equivalent key, and then invokes `f1` with a const reference to the newly created element. Otherwise, invokes `f2` with a const reference to the equivalent element.

en	Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[EmplaceConstructible^] from `k`. Returns:;; `true` if an insert took place. Concurrency:;; Blocking on rehashing of `*this`. Notes:;; These 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.

en	---

en	Insert Iterator Range and Visit

en	```c++ 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); ```

en	Equivalent to [listing,subs="+macros,+quotes"]

en	Returns:;; The number of elements inserted.

en	---

en	Insert Initializer List and Visit

en	```c++ 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); ```

en	Equivalent to [listing,subs="+macros,+quotes"]

en	Returns:;; The number of elements inserted.

en	---

en	Insert Node and Visit

en	```c++ template<class F1, class F2> insert_return_type insert_and_visit(node_type&& nh, F1 f1, F2 f2); template<class F1, class F2> insert_return_type insert_and_cvisit(node_type&& nh, F1 f1, F2 f2); ```

en	If `nh` is empty, does nothing. Otherwise, inserts the associated element in the table if and only if there is no element in the table with a key equivalent to `nh.value()`, and then invokes `f1` with a const reference to the newly inserted element. Otherwise, invokes `f2` with a const reference to the equivalent element.

en	Returns:;; An `insert_return_type` object constructed from `inserted` and `node`: +

en	If `nh` is empty, `inserted` is `false` and `node` is empty.

en	Otherwise if the insertion took place, `inserted` is true and `node` is empty.

en	If the insertion failed, `inserted` is false and `node` has the previous value of `nh`.

en	Throws:;; If an exception is thrown by an operation other than a call to `hasher` or call to `f1` or `f2`, the function has no effect. Concurrency:;; Blocking on rehashing of `*this`. Notes:;; Behavior is undefined if `nh` is not empty and the allocators of `nh` and the container are not equal.

en	---

en	erase

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

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

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

en	---

en	erase_if by Key

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

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

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

en	---

en	erase_if

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

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

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

en	---

en	Parallel erase_if

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

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

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

en	---

en	swap

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

en	Swaps the contents of the table with the parameter.

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

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

en	---

en	extract

en	```c++ node_type extract(const key_type& k); template<class K> node_type extract(K&& k); ```

en	Extracts the element with key equivalent to `k`, if it exists.

en	Returns:;; A `node_type` object holding the extracted element, or empty if no element was extracted. 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.

en	---

en	extract_if

en	```c++ template<class F> node_type extract_if(const key_type& k, F f); template<class K, class F> node_type extract_if(K&& k, F f); ```

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

en	Returns:;; A `node_type` object holding the extracted element, or empty if no element was extracted. Throws:;; Only throws an exception if it is thrown by `hasher` or `key_equal` or `f`. 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.

en	---

en	clear

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

en	Erases all elements in the table.

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

en	---

en	merge

en	```c++ template<class H2, class P2> size_type merge(concurrent_node_set<Key, H2, P2, Allocator>& source); template<class H2, class P2> size_type merge(concurrent_node_set<Key, H2, P2, Allocator>&& source); ```

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

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

en	---

en	Observers

en	get_allocator

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

en	Returns:;; The table's allocator.

en	---

en	hash_function

en	``` hasher hash_function() const; ```

en	Returns:;; The table's hash function.

en	---

en	key_eq

en	``` key_equal key_eq() const; ```

en	Returns:;; The table's key equality predicate.

en	---

en	Set Operations

en	count

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

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

en	---

en	contains

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

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

en	---

en	Bucket Interface

en	bucket_count

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

en	Returns:;; The size of the bucket array.

en	---

en	Hash Policy

en	load_factor

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

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

en	---

en	max_load_factor

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

en	Returns:;; Returns the table's maximum load factor.

en	---

en	Set max_load_factor

en	```c++ void max_load_factor(float z); ```

en	Effects:;; Does nothing, as the user is not allowed to change this parameter. Kept for compatibility with `boost::unordered_set`.

en	---

en	max_load

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

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

en	---

en	rehash

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

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

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

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

en	reserve

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

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

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

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

en	---

en	Statistics

en	get_stats

en	```c++ stats get_stats() const; ```

en	Returns:;; A statistical description of the insertion and lookup operations performed by the table so far. Notes:;; Only available if xref:reference/stats.adoc#stats[statistics calculation] is xref:concurrent_node_set_boost_unordered_enable_stats[enabled].

en	---

en	reset_stats

en	```c++ void reset_stats() noexcept; ```

en	Effects:;; Sets to zero the internal statistics kept by the table. Notes:;; Only available if xref:reference/stats.adoc#stats[statistics calculation] is xref:concurrent_node_set_boost_unordered_enable_stats[enabled].

en	---

en	Deduction Guides

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

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

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

en	__iter-value-type__

en	Equality Comparisons

en	operator

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

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

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

en	---

en	operator!

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

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

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

en	---

en	Swap

en	```c++ template<class Key, class Hash, class Pred, class Alloc> void swap(concurrent_node_set<Key, Hash, Pred, Alloc>& x, concurrent_node_set<Key, Hash, Pred, Alloc>& y) noexcept(noexcept(x.swap(y))); ```

en	Equivalent to [listing,subs="+macros,+quotes"]

en	---

en	erase_if

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

en	Equivalent to [listing,subs="+macros,+quotes"]

en	Serialization

en	``concurrent_node_set``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.

en	Saving an concurrent_node_set to an archive

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

en	Requires:;; `value_type` is serializable (XML serializable), and it supports 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`.

en	---

en	Loading an concurrent_node_set from an archive

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

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