Class Template concurrent_flat_set
boost::concurrent_flat_set
— A hash table that stores unique values and
allows for concurrent element insertion, erasure, lookup and access
without external synchronization mechanisms.
Even though it acts as a container, boost::concurrent_flat_set
does not model the standard C++ 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_flat_set
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_set
is similar to that of
boost::unordered_flat_set
. 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_set.hpp>
namespace boost {
namespace unordered {
template<class Key,
class Hash = boost::hash<Key>,
class Pred = std::equal_to<Key>,
class Allocator = std::allocator<Key>>
class concurrent_flat_set {
public:
// types
using key_type = Key;
using value_type = Key;
using init_type = Key;
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_set();
explicit concurrent_flat_set(size_type n,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template<class InputIterator>
concurrent_flat_set(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_set(const concurrent_flat_set& other);
concurrent_flat_set(concurrent_flat_set&& other);
template<class InputIterator>
concurrent_flat_set(InputIterator f, InputIterator l,const allocator_type& a);
explicit concurrent_flat_set(const Allocator& a);
concurrent_flat_set(const concurrent_flat_set& other, const Allocator& a);
concurrent_flat_set(concurrent_flat_set&& other, const Allocator& a);
concurrent_flat_set(unordered_flat_set<Key, Hash, Pred, Allocator>&& other);
concurrent_flat_set(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_set(size_type n, const allocator_type& a);
concurrent_flat_set(size_type n, const hasher& hf, const allocator_type& a);
template<class InputIterator>
concurrent_flat_set(InputIterator f, InputIterator l, size_type n,
const allocator_type& a);
template<class InputIterator>
concurrent_flat_set(InputIterator f, InputIterator l, size_type n, const hasher& hf,
const allocator_type& a);
concurrent_flat_set(std::initializer_list<value_type> il, const allocator_type& a);
concurrent_flat_set(std::initializer_list<value_type> il, size_type n,
const allocator_type& a);
concurrent_flat_set(std::initializer_list<value_type> il, size_type n, const hasher& hf,
const allocator_type& a);
~concurrent_flat_set();
concurrent_flat_set& operator=(const concurrent_flat_set& other);
concurrent_flat_set& operator=(concurrent_flat_set&& other)
noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
boost::allocator_traits<Allocator>::propagate_on_container_move_assignment::value);
concurrent_flat_set& 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(value_type&& obj);
template<class K> bool insert(K&& k);
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(value_type&& obj, F f);
template<class F> bool insert_or_cvisit(value_type&& obj, F f);
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);
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(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 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);
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);
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_set& 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_set<Key, H2, P2, Allocator>& source);
template<class H2, class P2>
size_type merge(concurrent_flat_set<Key, H2, P2, Allocator>&& source);
// observers
hasher hash_function() const;
key_equal key_eq() const;
// set 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-value-type<InputIterator>>,
class Pred = std::equal_to<iter-value-type<InputIterator>>,
class Allocator = std::allocator<iter-value-type<InputIterator>>>
concurrent_flat_set(InputIterator, InputIterator, typename see below::size_type = see below,
Hash = Hash(), Pred = Pred(), Allocator = Allocator())
-> concurrent_flat_set<iter-value-type<InputIterator>, Hash, Pred, Allocator>;
template<class T, class Hash = boost::hash<T>, class Pred = std::equal_to<T>,
class Allocator = std::allocator<T>>
concurrent_flat_set(std::initializer_list<T>, typename see below::size_type = see below,
Hash = Hash(), Pred = Pred(), Allocator = Allocator())
-> concurrent_flat_set<T, Hash, Pred, Allocator>;
template<class InputIterator, class Allocator>
concurrent_flat_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
-> concurrent_flat_set<iter-value-type<InputIterator>,
boost::hash<iter-value-type<InputIterator>>,
std::equal_to<iter-value-type<InputIterator>>, Allocator>;
template<class InputIterator, class Allocator>
concurrent_flat_set(InputIterator, InputIterator, Allocator)
-> concurrent_flat_set<iter-value-type<InputIterator>,
boost::hash<iter-value-type<InputIterator>>,
std::equal_to<iter-value-type<InputIterator>>, Allocator>;
template<class InputIterator, class Hash, class Allocator>
concurrent_flat_set(InputIterator, InputIterator, typename see below::size_type, Hash,
Allocator)
-> concurrent_flat_set<iter-value-type<InputIterator>, Hash,
std::equal_to<iter-value-type<InputIterator>>, Allocator>;
template<class T, class Allocator>
concurrent_flat_set(std::initializer_list<T>, typename see below::size_type, Allocator)
-> concurrent_flat_set<T, boost::hash<T>, std::equal_to<T>, Allocator>;
template<class T, class Allocator>
concurrent_flat_set(std::initializer_list<T>, Allocator)
-> concurrent_flat_set<T, boost::hash<T>, std::equal_to<T>, Allocator>;
template<class T, class Hash, class Allocator>
concurrent_flat_set(std::initializer_list<T>, typename see below::size_type, Hash, Allocator)
-> concurrent_flat_set<T, Hash, std::equal_to<T>, Allocator>;
} // namespace unordered
} // namespace boost
Description
Template Parameters
Key |
|
Hash |
A unary function object type that acts a hash function for a |
Pred |
A binary function object that induces an equivalence relation on values of type |
Allocator |
An allocator whose value type is the same as the table’s value type.
|
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 fromAlloc
-
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_set
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_set
,
prior blocking operations on x
synchronize with op. So, blocking operations on the same
concurrent_flat_set
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_set
, 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_set 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_set
x
are not allowed to invoke any operation
on x
; invoking operations on a different boost::concurrent_flat_set
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_set();
Constructs an empty table using hasher()
as the hash function,
key_equal()
as the key equality predicate and allocator_type()
as the allocator.
Postconditions: |
|
Requires: |
If the defaults are used, |
Bucket Count Constructor
explicit concurrent_flat_set(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: |
|
Requires: |
If the defaults are used, |
Iterator Range Constructor
template<class InputIterator>
concurrent_flat_set(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, |
Copy Constructor
concurrent_flat_set(concurrent_flat_set 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: |
|
Concurrency: |
Blocking on |
Move Constructor
concurrent_flat_set(concurrent_flat_set&& 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 |
Iterator Range Constructor with Allocator
template<class InputIterator>
concurrent_flat_set(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: |
|
Allocator Constructor
explicit concurrent_flat_set(Allocator const& a);
Constructs an empty table, using allocator a
.
Copy Constructor with Allocator
concurrent_flat_set(concurrent_flat_set const& other, Allocator const& a);
Constructs a table, copying other
's contained elements, hash function, and predicate, but using allocator a
.
Concurrency: |
Blocking on |
Move Constructor with Allocator
concurrent_flat_set(concurrent_flat_set&& 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 |
Move Constructor from unordered_flat_set
concurrent_flat_set(unordered_flat_set<Key, Hash, Pred, Allocator>&& other);
Move construction from a unordered_flat_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 enabled,
transfers the internal statistical information from other
and calls other.reset_stats()
.
Complexity: |
O( |
Initializer List Constructor
concurrent_flat_set(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, |
Bucket Count Constructor with Allocator
concurrent_flat_set(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: |
|
Requires: |
|
Bucket Count Constructor with Hasher and Allocator
concurrent_flat_set(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: |
|
Requires: |
|
Iterator Range Constructor with Bucket Count and Allocator
template<class InputIterator>
concurrent_flat_set(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: |
|
Iterator Range Constructor with Bucket Count and Hasher
template<class InputIterator>
concurrent_flat_set(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: |
|
initializer_list Constructor with Allocator
concurrent_flat_set(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: |
|
initializer_list Constructor with Bucket Count and Allocator
concurrent_flat_set(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: |
|
initializer_list Constructor with Bucket Count and Hasher and Allocator
concurrent_flat_set(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: |
|
Destructor
~concurrent_flat_set();
Note: |
The destructor is applied to every element, and all memory is deallocated |
Assignment
Copy Assignment
concurrent_flat_set& operator=(concurrent_flat_set 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: |
|
Concurrency: |
Blocking on |
Move Assignment
concurrent_flat_set& operator=(concurrent_flat_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 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 |
Initializer List Assignment
concurrent_flat_set& operator=(std::initializer_list<value_type> il);
Assign from values in initializer list. All previously existing elements are destroyed.
Requires: |
|
Concurrency: |
Blocking on |
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 const reference to x
.
Returns: |
The number of elements visited (0 or 1). |
Notes: |
The |
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 const reference to x
.
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: |
|
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 const references to each of the elements in the table.
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 const references to each of the elements in the table.
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 |
Notes: |
Only available in compilers supporting C++17 parallel algorithms. These overloads only participate in overload resolution if 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 const references to each of the elements in the table until f
returns false
or all the elements are visited.
Returns: |
|
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 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.
Returns: |
|
Throws: |
Depending on the exception handling mechanism of the execution policy used, may call |
Notes: |
Only available in compilers supporting C++17 parallel algorithms. These overloads only participate in overload resolution if Unsequenced execution policies are not allowed. Parallelization implies that execution does not necessary finish as soon as |
Size and Capacity
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: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
Notes: |
Invalidates pointers and references to elements if a rehashing is issued. |
Copy Insert
bool insert(const value_type& obj);
Inserts obj
in the table if and only if there is no element in the table with an equivalent key.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
Notes: |
Invalidates pointers and references to elements if a rehashing is issued. |
Move Insert
bool insert(value_type&& obj);
Inserts obj
in the table if and only if there is no element in the table with an equivalent key.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
Notes: |
Invalidates pointers and references to elements if a rehashing is issued. |
Transparent Insert
template<class K> bool insert(K&& k);
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.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
Notes: |
Invalidates pointers and references to elements if a rehashing is issued. This overload only participates in overload resolution if |
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 const reference to the equivalent element.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
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 |
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);
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.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
Notes: |
Invalidates pointers and references to elements if a rehashing is issued. |
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);
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.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
Notes: |
Invalidates pointers and references to elements if a rehashing is issued. |
Transparent insert_or_[c]visit
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);
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.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
Notes: |
Invalidates pointers and references to elements if a rehashing is issued. These overloads only participate in overload resolution if |
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 const reference to the newly created element.
Otherwise, invokes f2
with a const reference to the equivalent element.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
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 |
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);
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.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
Notes: |
Invalidates pointers and references to elements if a rehashing is issued. |
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);
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.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
Notes: |
Invalidates pointers and references to elements if a rehashing is issued. |
Transparent insert_and_[c]visit
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);
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.
Requires: |
|
Returns: |
|
Concurrency: |
Blocking on rehashing of |
Notes: |
Invalidates pointers and references to elements if a rehashing is issued. These overloads only participate in overload resolution if |
Insert Iterator Range and Visit
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);
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. |
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 |
Notes: |
The |
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 |
Notes: |
The The |
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 |
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 |
Notes: |
Only available in compilers supporting C++17 parallel algorithms. This overload only participates in overload resolution if Unsequenced execution policies are not allowed. |
swap
void swap(concurrent_flat_set& 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 |
Concurrency: |
Blocking on |
clear
void clear() noexcept;
Erases all elements in the table.
Postconditions: |
|
Concurrency: |
Blocking on |
merge
template<class H2, class P2>
size_type merge(concurrent_flat_set<Key, H2, P2, Allocator>& source);
template<class H2, class P2>
size_type merge(concurrent_flat_set<Key, 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 |
Set 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 |
Notes: |
The 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 |
Notes: |
The In the presence of concurrent insertion operations, the value returned may not accurately reflect the true state of the table right after execution. |
Hash Policy
load_factor
float load_factor() const noexcept;
Returns: |
|
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 |
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 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 |
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 |
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
container type deduced by the deduction guide. Its default value coincides with the default value
of the constructor selected.
Equality Comparisons
operator==
template<class Key, class Hash, class Pred, class Alloc>
bool operator==(const concurrent_flat_set<Key, Hash, Pred, Alloc>& x,
const concurrent_flat_set<Key, 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 |
Notes: |
Behavior is undefined if the two tables don’t have equivalent equality predicates. |
operator!=
template<class Key, class Hash, class Pred, class Alloc>
bool operator!=(const concurrent_flat_set<Key, Hash, Pred, Alloc>& x,
const concurrent_flat_set<Key, 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 |
Notes: |
Behavior is undefined if the two tables don’t have equivalent equality predicates. |
Swap
template<class Key, class Hash, class Pred, class Alloc>
void swap(concurrent_flat_set<Key, Hash, Pred, Alloc>& x,
concurrent_flat_set<Key, Hash, Pred, Alloc>& y)
noexcept(noexcept(x.swap(y)));
Equivalent to
x.swap(y);
erase_if
template<class K, class H, class P, class A, class Predicate>
typename concurrent_flat_set<K, H, P, A>::size_type
erase_if(concurrent_flat_set<K, H, P, A>& c, Predicate pred);
Equivalent to
c.erase_if(pred);
Serialization
concurrent_flat_set
s 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_set to an archive
Saves all the elements of a concurrent_flat_set
x
to an archive (XML archive) ar
.
Requires: |
|
Concurrency: |
Blocking on |
Loading an concurrent_flat_set from an archive
Deletes all preexisting elements of a concurrent_flat_set
x
and inserts
from an archive (XML archive) ar
restored copies of the elements of the
original concurrent_flat_set
other
saved to the storage read by ar
.
Requires: |
|
Concurrency: |
Blocking on |