This class template implements a value‐semantic container type holding an unordered sequence of (possibly duplicate) elements, that can be rapidly accessed using their key, with the constraint on the container that elements whose keys compare equal according to the specified COMPARATOR will be stored in a stable, contiguous sequence within the container. The value type and key type of the elements maintained by a HashTable are determined by aliases provided through the (template parameter) type KEY_CONFIG. Elements in a HashTable are stored in "nodes" that are allocated using an allocator of the specified ALLOCATOR type (rebound to the node type), and elements are constructed directly in the node using the allocator as described in the C++11 standard under the allocator‐aware container requirements in ([container.requirements.general], C++11 23.2.1). The (template parameter) types HASHER and COMPARATOR shall be copy‐constructible function‐objects. HASHER shall support a function call operator compatible with the following statements: ` HASHER hash; KEY_CONFIG::KeyType key; std::size_t result = hash(key); ` where the definition of the called function meets the requirements of a hash function, as specified in {`bslstl_hash`}. COMPARATOR shall support the a function call operator compatible with the following statements: ` COMPARATOR compare; KEY_CONFIG::KeyType key1, key2; bool result = compare(key1, key2); ` where the definition of the called function defines an equivalence relationship on keys that is both reflexive and transitive. The HASHER and COMPARATOR attributes of this class are further constrained, such for any two objects whose keys compare equal by the comparator, shall produce the same value from the hasher.

Synopsis

Declared in <bslstl_hashtable.h>

template<>
class HashTable<UnorderedMapKeyConfiguration<basic_string<char> const, pair<basic_string<char> const, Json>>, TransparentHash, TransparentEqualTo, allocator<pair<basic_string<char> const, Json>>>;

Description

This class: * supports a complete set of value‐semantic operations

  • except for bdex serialization * is exception‐neutral (agnostic except for the at method) * is alias‐safe * is const thread‐safe For terminology see {`bsldoc_glossary`}.

Type Aliases

Name

Description

AllocatorTraits

This typedef is an alias to bsl::allocator_traits<AllocatorType>.

AllocatorType

This typedef is an alias to the (template parameter) ALLOCATOR.

KeyType

This typedef is an alias to KEY_CONFIG::KeyType.

NodeType

Node type stored in the hash table.

NonConstKeyType

This typedef is an alias to the non‐`const` form of KeyType.

SizeType

This typedef is an alias to AllocatorTraits::size_type.

ValueType

Alias to the ValueType defined in the (template parameter) KEY_CONFIG.

Member Functions

Name

Description

HashTable [constructor]

Constructors

~HashTable [destructor]

Destroy this object.

operator=

Assignment operators

allocator

Return a copy of the allocator used to construct this hash table. Note that this is not the allocator used to allocate elements for this hash table, which is instead a copy of that allocator rebound to allocate the nodes used by the internal data structure of this hash table.

bucketAtIndex

Return a reference offering non‐modifiable access to the HashTableBucket at the specified index position in the array of buckets of this table. The behavior is undefined unless 'index < numBuckets()'.

bucketIndexForKey

bucketIndexForKey overloads

comparator

Return a reference providing non‐modifiable access to the key‐equality comparison functor used by this hash table.

countElementsInBucket

Return the number elements contained in the bucket at the specified index. Note that this operation has linear run‐time complexity with respect to the number of elements in the indexed bucket.

elementListRoot

Return the address of the first element in this hash table, or a null pointer value if this hash table is empty.

emplace

Insert into this hash‐table a newly‐created ValueType object, constructed by forwarding the specified (variable number of) arguments to the corresponding constructor of ValueType, and return the address of the newly inserted node. If a key equivalent to that of the newly‐created object already exists in this hash‐table, then insert the newly‐created object immediately before the first such element. Additional buckets are allocated, as needed, to preserve the invariant loadFactor <= maxLoadFactor. If this function tries to allocate a number of buckets larger than can be represented by this hash‐table's SizeType, a std::length_error exception is thrown. This method requires that the ValueType defined in the (template parameter) type KEY_CONFIG be emplace‐constructible into this hash‐table from arguments (see {Requirements on KEY_CONFIG});

emplaceIfMissing

Insert into this hash‐table a newly‐created ValueType object, constructed by forwarding the specified (variable number of) arguments to the corresponding constructor of ValueType, if a key equivalent to that of the newly‐created object does not already exist in this hash‐table. Return the address of the (possibly newly created and inserted) element in this hash table whose key is equivalent to that of an object created from arguments. Load true into the specified isInsertedFlag if a new value was inserted, and false if an equivalent key was already present. If this hash‐table contains more than one element with an equivalent key, return the first such element (from the contiguous sequence of elements having a matching key). Additional buckets are allocated, as needed, to preserve the invariant loadFactor <= maxLoadFactor. If this function tries to allocate a number of buckets larger than can be represented by this hash‐table's SizeType, a std::length_error exception is thrown. This method requires that the ValueType defined in the (template parameter) type KEY_CONFIG be emplace‐constructible into this hash‐table from arguments (see {Requirements on KEY_CONFIG});

emplaceWithHint

Insert into this hash‐table a newly‐created ValueType object, constructed by forwarding the specified (variable number of) arguments to the corresponding constructor of ValueType (immediately preceding the specified hint if hint is not null and the key of the node pointed to by hint is equivalent to that of the newly‐created object), and return the address of the newly inserted node. If hint is null or the key of the node pointed to by hint is not equivalent to that of the newly created object, and a key equivalent to that of the newly‐created object already exists in this hash‐table, then insert the newly‐created object immediately before the first such element. Additional buckets will be allocated, as needed, to preserve the invariant loadFactor <= maxLoadFactor. If this function tries to allocate a number of buckets larger than can be represented by this hash table's SizeType, a std::length_error exception is thrown. This method requires that ValueType defined in the (template parameter) type KEY_CONFIG be emplace‐constructible into this hash‐table from arguments (see {Requirements on KEY_CONFIG}). The behavior is undefined unless hint is either null or points to a node in this hash table.

find

find overloads

findEndOfRange

Return the address of the first node after any nodes holding a value having the same key as the specified first node (according to this hash‐table's comparator), and a null pointer value if all nodes following first hold values with the same key as first. The behavior is undefined unless first is a link in this hash‐table. Note that this hash‐table ensures all elements having the same key form a contiguous sequence.

findRange

findRange overloads

hasSameValue

Return true if the specified other has the same value as this object, and false otherwise. Two HashTable objects have the same value if they have the same number of elements, and for every subset of elements in this object having keys that compare equal (according to that hash table's comparator), a corresponding subset of elements exists in the other object, having the same number of elements, where, for some permutation of the subset in this object, every element in that subset compares equal (using operator==) to the corresponding element in the other subset. The behavior is undefined unless both the hasher and comparator of this object and the other return the same value for every valid input. Note that this method requires that the ValueType of the parameterized KEY_CONFIG be "equality‐comparable" (see {Requirements on KEY_CONFIG}).

hasher

Return a reference providing non‐modifiable access to the hash functor used by this hash‐table.

insert

insert overloads

insertIfMissing

insertIfMissing overloads

insertIfMissingTransparent

Insert into this hash‐table a ValueType object created from the specified value if a key equivalent to that of such an object does not already exist in this hash‐table. Return the address of the (possibly newly inserted) element in this hash‐table whose key is equivalent to that of the object created from value. Load true into the specified isInsertedFlag if a new value was inserted, and false if an equivalent key was already present. If this hash‐table contains more than one element with an equivalent key, return the first such element (from the contiguous sequence of elements having a matching key). Additional buckets are allocated, as needed, to preserve the invariant loadFactor <= maxLoadFactor. If this function tries to allocate a number of buckets larger than can be represented by this hash‐table's SizeType, a std::length_error exception is thrown. This method requires that the ValueType defined in the (template parameter) type KEY_CONFIG be move‐insertable into this hash‐table (see {Requirements on KEY_CONFIG}) and the (template parameter) type SOURCE_TYPE be implicitly convertible to ValueType.

insertOrAssign

If a key equivalent to the specified key already exists in this hash‐table, assign the specified obj to the value associated with that key, load false into the specified isInsertedFlag and return a pointer to the existing entry. Otherwise, insert into this hash‐table a newly‐created value_type object, constructed from key and obj, load true into isInsertedFlag, and return a pointer to the newly‐created entry. Use the optionally specified hint as a starting place for the search for the existing key.

insertOrAssignTransparent

If a key equivalent to the specified key already exists in this hash‐table, assign the specified obj to the value associated with that key, load false into the specified isInsertedFlag and return a pointer to the existing entry. Otherwise, insert into this hash‐table a newly‐created value_type object, constructed from key and obj, load true into isInsertedFlag, and return a pointer to the newly‐created entry. Use the optionally specified hint as a starting place for the search for the existing key.

loadFactor

Return the current load factor for this table. The load factor is the statistical mean number of elements per bucket.

maxLoadFactor

Return the maximum load factor permitted by this hash table object, where the load factor is the statistical mean number of elements per bucket. Note that this hash table will enforce the maximum load factor by rehashing into a larger array of buckets on any any insertion operation where a successful insertion would exceed the maximum load factor. The maximum load factor may actually be less than the current load factor if the maximum load factor has been reset, but no insert operations have yet occurred.

maxNumBuckets

Return a theoretical upper bound on the largest number of buckets that this hash‐table could possibly have. Note that there is no guarantee that the hash‐table can successfully maintain that number of buckets, or even close to that number of buckets without running out of resources.

maxSize

Return a theoretical upper bound on the largest number of elements that this hash‐table could possibly hold. Note that there is no guarantee that the hash‐table can successfully grow to the returned size, or even close to that size without running out of resources.

numBuckets

Return the number of buckets contained in this hash table.

rehashForNumBuckets

Re‐organize this hash‐table to have at least the specified newNumBuckets, preserving the invariant loadFactor <= maxLoadFactor. If this function tries to allocate a number of buckets larger than can be represented by this hash table's SizeType, a std::length_error exception is thrown. This operation provides the strong exception guarantee (see {`bsldoc_glossary`}) unless the hasher throws, in which case this operation provides the basic exception guarantee, leaving the hash‐table in a valid, but otherwise unspecified (and potentially empty), state. Note that more buckets than requested may be allocated in order to preserve the bucket allocation strategy of the hash table (but never fewer).

rehashThreshold

Return the number of elements this hash table can hold without requiring a rehash operation in order to respect the maxLoadFactor.

remove

Remove the specified node from this hash‐table, and return the address of the node immediately after node in this hash‐table (prior to its removal), or a null pointer value if node is the last node in the table. This method invalidates only iterators and references to the removed node and previously saved values of the end() iterator, and preserves the relative order of the nodes not removed. The behavior is undefined unless node refers to a node in this hash‐table.

removeAll

Remove all the elements from this hash‐table. Note that this hash‐table is empty after this call, but allocated memory may be retained for future use. The destructor of each (non‐trivial) element that is remove shall be run.

reserveForNumElements

Re‐organize this hash‐table to have a sufficient number of buckets to accommodate at least the specified numElements without exceeding the maxLoadFactor, and ensure that there are sufficient nodes pre‐allocated in this object's node pool. If this function tries to allocate a number of buckets larger than can be represented by this hash table's SizeType, a std::length_error exception is thrown. This operation provides the strong exception guarantee (see {`bsldoc_glossary`}) unless the hasher throws, in which case this operation provides the basic exception guarantee, leaving the hash‐table in a valid, but otherwise unspecified (and potentially empty), state.

setMaxLoadFactor

Set the maximum load factor permitted by this hash table to the specified newMaxLoadFactor, where load factor is the statistical mean number of elements per bucket. If 'newMaxLoadFactor < loadFactor', allocate at least enough buckets to re‐establish the invariant loadFactor <= maxLoadFactor. If this function tries to allocate a number of buckets larger than can be represented by this hash table's SizeType, a std::length_error exception is thrown. The behavior is undefined unless 0 < maxLoadFactor.

size

Return the number of elements in this hash table.

swap

Exchange the value of this object, its comparator functor, its hasher functor, and its maxLoadFactor with those of the specified other object. Additionally, if bslstl::AllocatorTraits<ALLOCATOR>::propagate_on_container_swap is true, then exchange the allocator of this object with that of the other object, and do not modify either allocator otherwise. This method provides the no‐throw exception‐safety guarantee unless any of the comparator or hasher functors throw when swapped, leaving both objects in a safely destructible, but otherwise unusable, state. The operation guarantees O[1] complexity. The behavior is undefined unless either this object has an allocator that compares equal to the allocator of other, or the trait bslstl::AllocatorTraits<ALLOCATOR>::propagate_on_container_swap is true.

tryEmplace

tryEmplace overloads

Created with MrDocs