|
| | sparse_set () |
| |
| | sparse_set (size_type bucket_count, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator()) |
| |
| | sparse_set (size_type bucket_count, const Allocator &alloc) |
| |
| | sparse_set (size_type bucket_count, const Hash &hash, const Allocator &alloc) |
| |
| | sparse_set (const Allocator &alloc) |
| |
| template<class InputIt > |
| | sparse_set (InputIt first, InputIt last, size_type bucket_count=ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator()) |
| |
| template<class InputIt > |
| | sparse_set (InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc) |
| |
| template<class InputIt > |
| | sparse_set (InputIt first, InputIt last, size_type bucket_count, const Hash &hash, const Allocator &alloc) |
| |
| | sparse_set (std::initializer_list< value_type > init, size_type bucket_count=ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator()) |
| |
| | sparse_set (std::initializer_list< value_type > init, size_type bucket_count, const Allocator &alloc) |
| |
| | sparse_set (std::initializer_list< value_type > init, size_type bucket_count, const Hash &hash, const Allocator &alloc) |
| |
| sparse_set & | operator= (std::initializer_list< value_type > ilist) |
| |
| allocator_type | get_allocator () const |
| |
| iterator | begin () noexcept |
| |
| const_iterator | begin () const noexcept |
| |
| const_iterator | cbegin () const noexcept |
| |
| iterator | end () noexcept |
| |
| const_iterator | end () const noexcept |
| |
| const_iterator | cend () const noexcept |
| |
| bool | empty () const noexcept |
| |
| size_type | size () const noexcept |
| |
| size_type | max_size () const noexcept |
| |
| void | clear () noexcept |
| |
| std::pair< iterator, bool > | insert (const value_type &value) |
| |
| std::pair< iterator, bool > | insert (value_type &&value) |
| |
| iterator | insert (const_iterator hint, const value_type &value) |
| |
| iterator | insert (const_iterator hint, value_type &&value) |
| |
| template<class InputIt > |
| void | insert (InputIt first, InputIt last) |
| |
| void | insert (std::initializer_list< value_type > ilist) |
| |
| template<class... Args> |
| std::pair< iterator, bool > | emplace (Args &&... args) |
| |
| template<class... Args> |
| iterator | emplace_hint (const_iterator hint, Args &&... args) |
| |
| iterator | erase (iterator pos) |
| |
| iterator | erase (const_iterator pos) |
| |
| iterator | erase (const_iterator first, const_iterator last) |
| |
| size_type | erase (const key_type &key) |
| |
| size_type | erase (const key_type &key, std::size_t precalculated_hash) |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| size_type | erase (const K &key) |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| size_type | erase (const K &key, std::size_t precalculated_hash) |
| |
| void | swap (sparse_set &other) |
| |
| size_type | count (const Key &key) const |
| |
| size_type | count (const Key &key, std::size_t precalculated_hash) const |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| size_type | count (const K &key) const |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| size_type | count (const K &key, std::size_t precalculated_hash) const |
| |
| iterator | find (const Key &key) |
| |
| iterator | find (const Key &key, std::size_t precalculated_hash) |
| |
| const_iterator | find (const Key &key) const |
| |
| const_iterator | find (const Key &key, std::size_t precalculated_hash) const |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| iterator | find (const K &key) |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| iterator | find (const K &key, std::size_t precalculated_hash) |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| const_iterator | find (const K &key) const |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| const_iterator | find (const K &key, std::size_t precalculated_hash) const |
| |
| std::pair< iterator, iterator > | equal_range (const Key &key) |
| |
| std::pair< iterator, iterator > | equal_range (const Key &key, std::size_t precalculated_hash) |
| |
| std::pair< const_iterator, const_iterator > | equal_range (const Key &key) const |
| |
| std::pair< const_iterator, const_iterator > | equal_range (const Key &key, std::size_t precalculated_hash) const |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| std::pair< iterator, iterator > | equal_range (const K &key) |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| std::pair< iterator, iterator > | equal_range (const K &key, std::size_t precalculated_hash) |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| std::pair< const_iterator, const_iterator > | equal_range (const K &key) const |
| |
| template<class K , class KE = KeyEqual, typename std::enable_if< has_is_transparent< KE >::value >::type * = nullptr> |
| std::pair< const_iterator, const_iterator > | equal_range (const K &key, std::size_t precalculated_hash) const |
| |
| size_type | bucket_count () const |
| |
| size_type | max_bucket_count () const |
| |
| float | load_factor () const |
| |
| float | max_load_factor () const |
| |
| void | max_load_factor (float ml) |
| |
| void | rehash (size_type count) |
| |
| void | reserve (size_type count) |
| |
| hasher | hash_function () const |
| |
| key_equal | key_eq () const |
| |
| iterator | mutable_iterator (const_iterator pos) |
| |
| template<class Serializer > |
| void | serialize (Serializer &serializer) const |
| |
template<class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<Key>, class GrowthPolicy = tsl::sh::power_of_two_growth_policy<2>, tsl::sh::exception_safety ExceptionSafety = tsl::sh::exception_safety::basic, tsl::sh::sparsity Sparsity = tsl::sh::sparsity::medium>
class tsl::sparse_set< Key, Hash, KeyEqual, Allocator, GrowthPolicy, ExceptionSafety, Sparsity >
Implementation of a sparse hash set using open-addressing with quadratic probing. The goal on the hash set is to be the most memory efficient possible, even at low load factor, while keeping reasonable performances.
GrowthPolicy defines how the set grows and consequently how a hash value is mapped to a bucket. By default the set uses tsl::sh::power_of_two_growth_policy. This policy keeps the number of buckets to a power of two and uses a mask to map the hash to a bucket instead of the slow modulo. Other growth policies are available and you may define your own growth policy, check tsl::sh::power_of_two_growth_policy for the interface.
ExceptionSafety defines the exception guarantee provided by the class. By default only the basic exception safety is guaranteed which mean that all resources used by the hash set will be freed (no memory leaks) but the hash set may end-up in an undefined state if an exception is thrown (undefined here means that some elements may be missing). This can ONLY happen on rehash (either on insert or if rehash is called explicitly) and will occur if the Allocator can't allocate memory (std::bad_alloc) or if the copy constructor (when a nothrow move constructor is not available) throws an exception. This can be avoided by calling reserve beforehand. This basic guarantee is similar to the one of google::sparse_hash_map and spp::sparse_hash_map. It is possible to ask for the strong exception guarantee with tsl::sh::exception_safety::strong, the drawback is that the set will be slower on rehashes and will also need more memory on rehashes.
Sparsity defines how much the hash set will compromise between insertion speed and memory usage. A high sparsity means less memory usage but longer insertion times, and vice-versa for low sparsity. The default tsl::sh::sparsity::medium sparsity offers a good compromise. It doesn't change the lookup speed.
Key must be nothrow move constructible and/or copy constructible.
If the destructor of Key throws an exception, the behaviour of the class is undefined.
Iterators invalidation:
- clear, operator=, reserve, rehash: always invalidate the iterators.
- insert, emplace, emplace_hint: if there is an effective insert, invalidate the iterators.
- erase: always invalidate the iterators.
template<class Key , class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<Key>, class GrowthPolicy = tsl::sh::power_of_two_growth_policy<2>, tsl::sh::exception_safety ExceptionSafety = tsl::sh::exception_safety::basic, tsl::sh::sparsity Sparsity = tsl::sh::sparsity::medium>
template<class Deserializer >
| static sparse_set tsl::sparse_set< Key, Hash, KeyEqual, Allocator, GrowthPolicy, ExceptionSafety, Sparsity >::deserialize |
( |
Deserializer & |
deserializer, |
|
|
bool |
hash_compatible = false |
|
) |
| |
|
inlinestatic |
Deserialize a previouly serialized set through the deserializer parameter.
The deserializer parameter must be a function object that supports the following calls:
template<typename U> U operator()(); where the types std::uint64_t, float and Key must be supported for U.
If the deserialized hash set type is hash compatible with the serialized set, the deserialization process can be sped up by setting hash_compatible to true. To be hash compatible, the Hash, KeyEqual and GrowthPolicy must behave the same way than the ones used on the serialized set. The std::size_t must also be of the same size as the one on the platform used to serialize the set. If these criteria are not met, the behaviour is undefined with hash_compatible sets to true, .
The behaviour is undefined if the type Key of the sparse_set is not the same as the type used during serialization.
The implementation leaves binary compatibilty (endianness, IEEE 754 for floats, size of int, ...) of the types it deserializes in the hands of the Deserializer function object if compatibilty is required.
