- Generated by
1.9.8
|
BDE 4.39.x Production Release
|
#include <bdlc_flathashtable.h>
This class template provides a flat hash table implementation useful for implementing a flat hash set and flat hash map.
Public Types | |
| typedef KEY | key_type |
| typedef ENTRY | entry_type |
| typedef ENTRY_UTIL | entry_util_type |
| typedef HASH | hash_type |
| typedef EQUAL | key_equal_type |
| typedef bslstl::ForwardIterator< ENTRY, IteratorImp > | iterator |
| typedef bslstl::ForwardIterator< const ENTRY, IteratorImp > | const_iterator |
Public Member Functions | |
| FlatHashTable (bsl::size_t capacity, const HASH &hash, const EQUAL &equal, bslma::Allocator *basicAllocator=0) | |
| FlatHashTable (const FlatHashTable &original, bslma::Allocator *basicAllocator=0) | |
| FlatHashTable (bslmf::MovableRef< FlatHashTable > original) | |
| FlatHashTable (bslmf::MovableRef< FlatHashTable > original, bslma::Allocator *basicAllocator) | |
| ~FlatHashTable () | |
| FlatHashTable & | operator= (const FlatHashTable &rhs) |
| FlatHashTable & | operator= (bslmf::MovableRef< FlatHashTable > rhs) |
| template<class KEY_TYPE > | |
| ENTRY & | operator[] (BSLS_COMPILERFEATURES_FORWARD_REF(KEY_TYPE) key) |
| void | clear () |
| bsl::pair< iterator, iterator > | equal_range (const KEY &key) |
| template<class LOOKUP_KEY > | |
| bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, bsl::pair< iterator, iterator > >::type | equal_range (const LOOKUP_KEY &key) |
| template<class... ARGS> | |
| bsl::pair< iterator, bool > | emplace (ARGS &&... args) |
| bsl::size_t | erase (const KEY &key) |
| template<class LOOKUP_KEY > | |
| bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, bsl::size_t >::type | erase (LOOKUP_KEY &&key) |
| iterator | erase (const_iterator position) |
| iterator | erase (iterator position) |
| iterator | erase (const_iterator first, const_iterator last) |
| iterator | find (const KEY &key) |
| template<class LOOKUP_KEY > | |
| bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, iterator >::type | find (const LOOKUP_KEY &key) |
| bsl::pair< iterator, bool > | insert (const ENTRY &entry) |
| bsl::pair< iterator, bool > | insert (bslmf::MovableRef< ENTRY > entry) |
| template<class LOOKUP_KEY > | |
| bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, bsl::pair< iterator, bool > >::type | insertTransparent (LOOKUP_KEY &&key) |
| template<class INPUT_ITERATOR > | |
| void | insert (INPUT_ITERATOR first, INPUT_ITERATOR last) |
| void | rehash (bsl::size_t minimumCapacity) |
| void | reserve (bsl::size_t numEntries) |
| void | reset () |
| template<class... ARGS> | |
| bsl::pair< iterator, bool > | try_emplace (const KEY &key, ARGS &&... args) |
| template<class... ARGS> | |
| bsl::pair< iterator, bool > | try_emplace (BloombergLP::bslmf::MovableRef< KEY > key, ARGS &&... args) |
| template<class LOOKUP_KEY , class... ARGS> | |
| bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, bsl::pair< iterator, bool > >::type | try_emplace (LOOKUP_KEY &&key, ARGS &&... args) |
| iterator | begin () |
| iterator | end () |
| void | swap (FlatHashTable &other) |
| bsl::size_t | capacity () const |
| bool | contains (const KEY &key) const |
| const bsl::uint8_t * | controls () const |
| bsl::size_t | count (const KEY &key) const |
| bool | empty () const |
| const ENTRY * | entries () const |
| bsl::pair< const_iterator, const_iterator > | equal_range (const KEY &key) const |
| template<class LOOKUP_KEY > | |
| bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, bsl::pair< const_iterator, const_iterator > >::type | equal_range (const LOOKUP_KEY &key) const |
| const_iterator | find (const KEY &key) const |
| template<class LOOKUP_KEY > | |
| bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate< HASH, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate< EQUAL, LOOKUP_KEY >::value, const_iterator >::type | find (const LOOKUP_KEY &key) const |
| HASH | hash_function () const |
| EQUAL | key_eq () const |
| float | load_factor () const |
| float | max_load_factor () const |
| bsl::size_t | size () const |
| const_iterator | begin () const |
| const_iterator | cbegin () const |
| const_iterator | cend () const |
| const_iterator | end () const |
| bslma::Allocator * | allocator () const |
| template<class... ARGS> | |
| bsl::pair< typename FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::iterator, bool > | emplace (ARGS &&... args) |
| template<class... ARGS> | |
| bsl::pair< typename FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::iterator, bool > | try_emplace (const KEY &key, ARGS &&... args) |
| template<class... ARGS> | |
| bsl::pair< typename FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::iterator, bool > | try_emplace (BloombergLP::bslmf::MovableRef< KEY > key, ARGS &&... args) |
Static Public Attributes | |
| static const bsl::size_t | k_MIN_CAPACITY = 2 * GroupControl::k_SIZE |
| static const bsl::int8_t | k_HASHLET_MASK = 0x7f |
| static const bsl::size_t | k_MAX_LOAD_FACTOR_NUMERATOR = 7 |
| static const bsl::size_t | k_MAX_LOAD_FACTOR_DENOMINATOR = 8 |
| typedef bslstl::ForwardIterator<const ENTRY, IteratorImp> bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::const_iterator |
| typedef ENTRY bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::entry_type |
| typedef ENTRY_UTIL bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::entry_util_type |
| typedef HASH bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::hash_type |
| typedef bslstl::ForwardIterator<ENTRY, IteratorImp> bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::iterator |
| typedef EQUAL bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::key_equal_type |
| typedef KEY bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::key_type |
|
inline |
Create an empty table having at least the specified capacity, that will use the specified hash to generate hash values for the keys of the entries contained in this table, and the specified equal to verify that the keys of the two entries are the same. Optionally specify a basicAllocator used to supply memory. If basicAllocator is 0, the currently installed default allocator is used. If 0 == capacity, no memory is allocated and the object is defined to be in the "zero-capacity" state.
|
inline |
Create a table having the same value, hasher, and key-equality comparator as the specified original. Optionally specify a basicAllocator used to supply memory. If basicAllocator is 0, the currently installed default allocator is used.
|
inlineexplicit |
Create an table having the same value as the specified original object by moving (in constant time) the contents of original to the new table. Use a copy of original.hash_function() to generate hash values for the keys of the entries contained in this table. Use a copy of original.key_eq() to verify that two keys are equal. The allocator associated with original is propagated for use in the newly-created table. original is left in a (valid) unspecified state.
| bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::FlatHashTable | ( | bslmf::MovableRef< FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL > > | original, |
| bslma::Allocator * | basicAllocator | ||
| ) |
Create a table having the same value, hasher, and key-equality comparator as the specified original object by moving the contents of original to the new table, and using the specified basicAllocator to supply memory. Use a copy of original.hash_function() to generate hash values for the entries contained in this table. Use a copy of original.key_eq() to verify that the keys of two entries are equal. This method requires that the (template parameter) type ENTRY be move-insertable into this FlatHashTable. If basicAllocator is 0, the currently installed default allocator is used. If original and the newly created object have the same allocator then the value of original becomes unspecified but valid, and no exceptions will be thrown; otherwise original is unchanged (and an exception may be thrown).
|
inline |
Destroy this object and each of its entries.
|
inline |
Return the allocator used by this hash table to supply memory.
|
inline |
Return an iterator representing the beginning of the sequence of entries held by this container.
|
inline |
|
inline |
Return the number of elements this table could hold if the load factor were 1.
|
inline |
Return an iterator representing the beginning of the sequence of entries held by this container.
|
inline |
|
inline |
Remove all entries from this table.
capacity method.
|
inline |
Return true if this table contains an entry having the specified key, and false otherwise.
|
inline |
Return the address of the first element of the underlying array of control values in this table, or 0 if this table is in the zero-capacity state. An element of this array has the value FlatHashTable_GroupControl::k_EMPTY, FlatHashTable_GroupControl::k_ERASED, or a seven bit hashlet value for the in-use position (the highest-order bit is unset).
|
inline |
Return the number of objects contained within this table having the specified key.
| bsl::pair< iterator, bool > bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::emplace | ( | ARGS &&... | args | ) |
Create an ENTRY object from the specified args, and attempt to add it to this flat hash table. Return a bsl::pair containing an iterator to the newly inserted object and true if the element was added. If an entry with the same key already exists in this flat hash table, return an iterator to that entry and false. This method requires that the ENTRY be copy-constructible.
|
inline |
|
inline |
Return true if this table contains no entries, and false otherwise.
|
inline |
Return an iterator representing one past the end of the sequence of entries held by this container.
|
inline |
Return an iterator representing one past the end of the sequence of entries held by this container.
|
inline |
Return the address of the first element of the underlying array of entries in this table, or 0 if this table is in the zero-capacity state.
controls array before dereferencing an entry in this array.
|
inline |
Return a pair of iterators providing modifiable access to the sequence of objects in this flat hash table having the specified key, where the first iterator is positioned at the start of the sequence, and the second is positioned one past the end of the sequence. If this table contains no object having key, then the two returned iterators will have the same value, end().
|
inline |
Return a pair of iterators providing non-modifiable access to the sequence of objects in this table having the specified key, where the first iterator is positioned at the start of the sequence, and the second is positioned one past the end of the sequence. If this table contains no objects having key, then the two returned iterators will have the same value, end().
|
inline |
Return a pair of iterators providing non-modifiable access to the sequence of objects in this table having a key equivalent to the specified key, where the first iterator is positioned at the start of the sequence, and the second is positioned one past the end of the sequence. If this table contains no objects having a key equivalent to the specified key, then the two returned iterators will have the same value, end().
|
inline |
Return a pair of iterators providing non-modifiable access to the sequence of objects in this table having a key equivalent to the specified key, where the first iterator is positioned at the start of the sequence, and the second is positioned one past the end of the sequence. If this table contains no objects having a key equivalent to the specified key, then the two returned iterators will have the same value, end().
|
inline |
Remove from this table the object having the specified key, if it exists, and return 1; otherwise (there is no object with a key equal to key in this table) return 0 with no other effect. This method invalidates all iterators, and references to the removed element.
| iterator bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::erase | ( | const_iterator | first, |
| const_iterator | last | ||
| ) |
Remove from this table the objects starting at the specified first position up to, but not including, the specified last position, and return last. This method invalidates all iterators, and references to the removed element.
first and last either refer to elements in this table or are the end iterator, and the first position is at or before the last position in the iteration sequence provided by this container. | iterator bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::erase | ( | const_iterator | position | ) |
Remove from this table the object at the specified position, and return an iterator referring to the element immediately following the removed element, or to the past-the-end position if the removed element was the last element in the sequence of elements maintained by this table. This method invalidates all iterators, and references to the removed element.
position refers to an object in this table. | iterator bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::erase | ( | iterator | position | ) |
|
inline |
Remove from this table the object having the specified key, if it exists, and return 1; otherwise (there is no object with a key equal to key in this table) return 0 with no other effect. This method invalidates all iterators, and references to the removed element.
|
inline |
Return an iterator providing modifiable access to the object in this flat hash table with a key equal to the specified key, if such an entry exists, and end() otherwise.
|
inline |
Return an iterator representing the position of the entry in this flat hash table having the specified key, or end() if no such entry exists in this table.
|
inline |
Return an iterator providing modifiable access to the object in this flat hash table with a key equivalent to the specified key, if such an entry exists, and end() otherwise.
|
inline |
Return an iterator representing the position of the entry in this flat hash table that is equivalent to the specified key, or end()
|
inline |
Return (a copy of) the unary hash functor used by this flat hash table to generate a hash value (of type bsl::size_t) for aKEY' object.
|
inline |
|
inline |
Insert the specified entry into this table if the key of the entry does not already exist in this table; otherwise, this method has no effect. Return a pair whose first member is an iterator referring to the (possibly newly inserted) object in this table whose key is the equal to that of the object to be inserted, and whose second member is true if a new entry was inserted, and false if a entry having an equal key was already present. Bitwise movable types that are not bitwise copyable will be copied (to avoid confusion with regard to calling the entry destructor after this call).
|
inline |
Create an object for each iterator in the range starting at the specified first iterator and ending immediately before the specified last iterator, by converting from the object referred to by each iterator. Insert into this table each such object whose key is not already contained. The (template parameter) type INPUT_ITERATOR shall meet the requirements of an input iterator defined in the C++11 standard [24.2.3] providing access to values of a type convertible to ENTRY.
first and last refer to a sequence of valid values where first is at a position at or before last.
|
inline |
Insert the specified key into this table if a key equivalent to key does not already exist in this table; otherwise, this method has no effect. Return a pair whose first member is an iterator referring to the (possibly newly inserted) object in this table whose key is the equal to that of the object to be inserted, and whose second member is true if a new entry was inserted, and false if a entry having an equal key was already present. Bitwise movable types that are not bitwise copyable will be copied (to avoid confusion with regard to calling the entry destructor after this call).
|
inline |
Return (a copy of) the binary key-equality functor used by this flat hash table that returns true if two KEY objects are equal, and false otherwise.
|
inline |
Return the current ratio between the number of elements in this table and its capacity.
|
inline |
Return the maximum load factor allowed for this table.
insert and rehash).
|
inline |
Assign to this object the value, hash function, and key-equality comparator of the specified rhs object and return a reference offering modifiable access to this object. The entries of rhs are moved (in constant time) to this object if the two have the same allocator, otherwise entries from rhs are moved into this table. In either case, rhs is left in a valid but unspecified state. If an exception is thrown, this object is left in a valid but unspecified state.
|
inline |
Assign to this object the value, hasher, and key-equality functor of the specified rhs object and return a reference offering modifiable access to this object.
|
inline |
If an entry with the specified key is not already present in this table, insert an entry having the value defined by ENTRY_UTIL::construct; otherwise, this method has no effect. Return an iterator referring to the (possibly newly inserted) object in this table with the key.
|
inline |
Change the capacity of this table to at least the specified minimumCapacity, and redistribute all the contained elements into a new sequence of entries, according to their hash values. If 0 == minimumCapacity and 0 == size(), the table is returned to the zero-capacity state. On return, load_factor() is less than or equal to max_load_factor() and all iterators, pointers, and references to elements of this FlatHashTable are invalidated.
|
inline |
Change the capacity of this table to at least a capacity that can accommodate the specified numEntries (accounting for the load factor invariant), and redistribute all the contained elements into a new sequence of entries, according to their hash values. If 0 == numEntries and 0 == size(), the table is returned to the zero-capacity state. After this call, load_factor() will be less than or equal to max_load_factor().
|
inline |
Remove all entries from this table and release all memory from this table, returning the table to the zero-capacity state.
|
inline |
Return the number of entries in this table.
|
inline |
Efficiently exchange the value of this table with the value of the specified other table. This method provides the no-throw exception-safety guarantee.
other. | bsl::pair< iterator, bool > bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::try_emplace | ( | BloombergLP::bslmf::MovableRef< KEY > | key, |
| ARGS &&... | args | ||
| ) |
If a key equivalent to the specified key already exists in this map, return a pair containing an iterator referring to the existing item, and false. Otherwise, insert into this map a newly-created ENTRY object, constructed from std::forward<KEY>(key) and the specified args, and return a pair containing an iterator referring to the newly-created entry and true. This method requires that the (template parameter) types KEY and VALUE are emplace-constructible from key and args respectively. For C++03, VALUE must also be copy-constructible.
| bsl::pair< typename FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::iterator, bool > bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::try_emplace | ( | BloombergLP::bslmf::MovableRef< KEY > | key, |
| ARGS &&... | args | ||
| ) |
Note: args contains piecewise_construct and key
| bsl::pair< iterator, bool > bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::try_emplace | ( | const KEY & | key, |
| ARGS &&... | args | ||
| ) |
If a key equivalent to the specified key already exists in this map, return a pair containing an iterator referring to the existing item, and false. Otherwise, insert into this map a newly-created ENTRY object, constructed from key and the specified args, and return a pair containing an iterator referring to the newly-created entry and true. This method requires that the (template parameter) types KEY and VALUE are emplace-constructible from key and args respectively. For C++03, VALUE must also be copy-constructible.
| bsl::pair< typename FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::iterator, bool > bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::try_emplace | ( | const KEY & | key, |
| ARGS &&... | args | ||
| ) |
Note: args contains piecewise_construct and key
|
inline |
If a key equivalent to the specified key already exists in this map return a pair containing an iterator referring to the existing item, and false. Otherwise, insert into this map a newly-created ENTRY object, constructed from std::forward<LOOKUP_KEY>(k) and the specified args, and return a pair containing an iterator referring to the newly-created entry and true. This method requires that the (template parameter) types KEY and VALUE are emplace-constructible from key and args respectively. For C++03, VALUE must also be copy-constructible.
|
static |
|
static |
|
static |
|
static |
1.9.8