|
| | 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 () |
| | Destroy this object and each of its entries.
|
| |
| 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... ARGS> |
| bsl::pair< iterator, bool > | emplace (ARGS &&... args) |
| |
| bsl::size_t | erase (const 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 ENTRY_TYPE > |
| bsl::enable_if< bsl::is_convertible< ENTRY_TYPE, ENTRY >::value, bsl::pair< iterator, bool > >::type | insert (BSLS_COMPILERFEATURES_FORWARD_REF(ENTRY_TYPE) entry) |
| |
| 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) |
| |
| 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 |
| |
| const_iterator | find (const 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 |
| | Return the number of entries in this table.
|
| |
| const_iterator | begin () const |
| |
| const_iterator | cbegin () const |
| |
| const_iterator | cend () const |
| |
| const_iterator | end () const |
| |
| bslma::Allocator * | allocator () const |
| | Return the allocator used by this hash table to supply memory.
|
| |
| 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) |
| | Note: args contains key
|
| |
| template<class... ARGS> |
| bsl::pair< typename FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::iterator, bool > | try_emplace (BloombergLP::bslmf::MovableRef< KEY > key, ARGS &&... args) |
| | Note: args contains key
|
| |
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
class bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >
This class template provides a flat hash table implementation useful for implementing a flat hash set and flat hash map.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
| bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::FlatHashTable |
( |
bsl::size_t |
capacity, |
|
|
const HASH & |
hash, |
|
|
const EQUAL & |
equal, |
|
|
bslma::Allocator * |
basicAllocator = 0 |
|
) |
| |
|
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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
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).
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
Remove all entries from this table. Note that this table will be empty after calling this method, but allocated memory may be retained for future use. See the capacity method.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
| const bsl::uint8_t * bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::controls |
( |
| ) |
const |
|
inline |
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
| bsl::size_t bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::count |
( |
const KEY & |
key | ) |
const |
|
inline |
Return the number of objects contained within this table having the specified key. Note that since a table maintains unique keys, the returned value will be either 0 or 1.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
template<class... 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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
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. The behavior is undefined unless the address is verified in-use through use of the controls array before dereferencing an entry in this array.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
| bsl::pair< typename FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::iterator, typename FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::iterator > bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::equal_range |
( |
const KEY & |
key | ) |
|
|
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(). Note that since each key in a flat hash table is unique, the returned range contains at most one element.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
| bsl::pair< typename FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::const_iterator, typename FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::const_iterator > bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::equal_range |
( |
const KEY & |
key | ) |
const |
|
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(). Note that since a table maintains unique keys, the range will contain at most one entry.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
| bsl::size_t bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::erase |
( |
const KEY & |
key | ) |
|
|
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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
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. The behavior is undefined unless 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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
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. The behavior is undefined unless position refers to an object in this table.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
template<class ENTRY_TYPE >
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).
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
template<class INPUT_ITERATOR >
| void bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::insert |
( |
INPUT_ITERATOR |
first, |
|
|
INPUT_ITERATOR |
last |
|
) |
| |
|
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. The behavior is undefined unless first and last refer to a sequence of valid values where first is at a position at or before last.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
Return the maximum load factor allowed for this table. Note that if an insert operation would cause the load factor to exceed the max_load_factor, that same insert operation will increase the capacity and rehash the entries of the container (see insert and rehash). Note that the value returned by max_load_factor is implementation dependent and cannot be changed by the user.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
| FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL > & bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::operator= |
( |
bslmf::MovableRef< FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL > > |
rhs | ) |
|
|
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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
| FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL > & bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::operator= |
( |
const FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL > & |
rhs | ) |
|
|
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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
template<class KEY_TYPE >
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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
| void bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::rehash |
( |
bsl::size_t |
minimumCapacity | ) |
|
|
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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
| void bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::reserve |
( |
bsl::size_t |
numEntries | ) |
|
|
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(). Note that this method is effectively equivalent to:
float max_load_factor() const
Definition bdlc_flathashtable.h:2056
void rehash(bsl::size_t minimumCapacity)
Definition bdlc_flathashtable.h:1766
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
template<class... 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.
template<class KEY , class ENTRY , class ENTRY_UTIL , class HASH , class EQUAL >
template<class... 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.
1.9.8