#include <bdlc_flathashtable.h>
List of all members.
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) |
| 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 () |
| 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 |
| const_iterator | begin () const |
| const_iterator | cbegin () const |
| const_iterator | cend () const |
| const_iterator | end () const |
| bslma::Allocator * | allocator () const |
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 |
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
class bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >
Member Typedef Documentation
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
Constructor & Destructor Documentation
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
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>
Destroy this object and each of its entries.
Member Function Documentation
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
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>
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>
template<class KEY_TYPE >
| ENTRY& bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::operator[] |
( |
BSLS_COMPILERFEATURES_FORWARD_REF(KEY_TYPE) |
key |
) |
|
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>
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>
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::size_t bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::erase |
( |
const KEY & |
key |
) |
|
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>
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>
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>
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.
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class ENTRY_TYPE >
- Parameters:
-
| entry | 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). |
Referenced by bdlc::FlatHashSet< KEY, HASH, EQUAL >::insert(), and bdlc::FlatHashMap< KEY, VALUE, HASH, EQUAL >::insert().
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 | |
|
) |
| | |
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>
| void bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::rehash |
( |
bsl::size_t |
minimumCapacity |
) |
|
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 |
) |
|
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:
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
Remove all entries from this table and release all memory from this table, returning the table to the zero-capacity state.
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
Return an iterator representing the beginning of the sequence of entries held by this container.
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
Return an iterator representing one past the end of the sequence of entries held by this container.
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
Efficiently exchange the value of this table with the value of the specified other table. This method provides the no-throw exception-safety guarantee. The behavior is undefined unless this array was created with the same allocator as other.
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
Return the number of elements this table could hold if the load factor were 1.
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
| bool bdlc::FlatHashTable< KEY, ENTRY, ENTRY_UTIL, HASH, EQUAL >::contains |
( |
const KEY & |
key |
) |
const |
Return true if this table contains an entry having the specified key, and false otherwise.
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 |
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 |
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>
Return true if this table contains no entries, and false otherwise.
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>
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>
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.
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
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 a 'KEY object.
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 current ratio between the number of elements in this table and its capacity.
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>
Return the number of entries in this table.
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
Return an iterator representing the beginning of the sequence of entries held by this container.
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
Return an iterator representing one past the end of the sequence of entries held by this container.
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
Return the allocator used by this hash table to supply memory.
Member Data Documentation
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
template<class KEY, class ENTRY, class ENTRY_UTIL, class HASH, class EQUAL>
The documentation for this class was generated from the following file:
