bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR > Class Template Reference

#include <bslstl_hashtable.h>

List of all members.

Public Types
typedef ALLOCATOR	AllocatorType
typedef ::bsl::allocator_traits < AllocatorType >	AllocatorTraits
typedef KEY_CONFIG::KeyType	KeyType
typedef KEY_CONFIG::ValueType	ValueType
typedef bslalg::BidirectionalNode < ValueType >	NodeType
typedef AllocatorTraits::size_type	SizeType
Public Member Functions
	HashTable (const ALLOCATOR &basicAllocator=ALLOCATOR())
	HashTable (const HASHER &hash, const COMPARATOR &compare, SizeType initialNumBuckets, float initialMaxLoadFactor, const ALLOCATOR &basicAllocator=ALLOCATOR())
	HashTable (const HashTable &original)
	HashTable (BloombergLP::bslmf::MovableRef< HashTable > original)
	HashTable (const HashTable &original, const ALLOCATOR &basicAllocator)
	HashTable (BloombergLP::bslmf::MovableRef< HashTable > original, const ALLOCATOR &basicAllocator)
	~HashTable ()
HashTable &	operator= (const HashTable &rhs)
HashTable &	operator= (BloombergLP::bslmf::MovableRef< HashTable > rhs)
template<class... Args>
bslalg::BidirectionalLink *	emplace (Args &&...arguments)
template<class... Args>
bslalg::BidirectionalLink *	emplaceWithHint (bslalg::BidirectionalLink *hint, Args &&...arguments)
template<class... Args>
bslalg::BidirectionalLink *	emplaceIfMissing (bool *isInsertedFlag, Args &&...arguments)
bslalg::BidirectionalLink *	insertIfMissing (const KeyType &key)
bslalg::BidirectionalLink *	insertIfMissing (bool *isInsertedFlag, const ValueType &value)
bslalg::BidirectionalLink *	insertIfMissing (bool *isInsertedFlag, bslmf::MovableRef< ValueType > value)
template<class SOURCE_TYPE >
bslalg::BidirectionalLink *	insertIfMissing (bool *isInsertedFlag, BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE) value)
template<class SOURCE_TYPE >
bslalg::BidirectionalLink *	insert (BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE) value)
template<class SOURCE_TYPE >
bslalg::BidirectionalLink *	insert (BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE) value, bslalg::BidirectionalLink *hint)
template<class KEY_ARG , class BDE_OTHER_TYPE >
bslalg::BidirectionalLink *	insertOrAssign (bool *isInsertedFlag, bslalg::BidirectionalLink *hint, BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key, BDE_OTHER_TYPE &&obj)
void	rehashForNumBuckets (SizeType newNumBuckets)
bslalg::BidirectionalLink *	remove (bslalg::BidirectionalLink *node)
void	removeAll ()
void	reserveForNumElements (SizeType numElements)
void	setMaxLoadFactor (float newMaxLoadFactor)
void	swap (HashTable &other)
template<class KEY_ARG , class... Args>
bslalg::BidirectionalLink *	tryEmplace (bool *isInsertedFlag, bslalg::BidirectionalLink *hint, BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG) key, Args &&...args)
ALLOCATOR	allocator () const
const bslalg::HashTableBucket &	bucketAtIndex (SizeType index) const
SizeType	bucketIndexForKey (const KeyType &key) const
const COMPARATOR &	comparator () const
SizeType	countElementsInBucket (SizeType index) const
bslalg::BidirectionalLink *	elementListRoot () const
template<class LOOKUP_KEY >
bsl::enable_if < BloombergLP::bslmf::IsTransparentPredicate < HASHER, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate < COMPARATOR, LOOKUP_KEY > ::value, bslalg::BidirectionalLink * > ::type	find (const LOOKUP_KEY &key) const
bslalg::BidirectionalLink *	find (const KeyType &key) const
bslalg::BidirectionalLink *	findEndOfRange (bslalg::BidirectionalLink *first) const
template<class LOOKUP_KEY >
bsl::enable_if < BloombergLP::bslmf::IsTransparentPredicate < HASHER, LOOKUP_KEY >::value &&BloombergLP::bslmf::IsTransparentPredicate < COMPARATOR, LOOKUP_KEY > ::value, void >::type	findRange (bslalg::BidirectionalLink **first, bslalg::BidirectionalLink **last, const LOOKUP_KEY &key) const
void	findRange (bslalg::BidirectionalLink **first, bslalg::BidirectionalLink **last, const KeyType &key) const
bool	hasSameValue (const HashTable &other) const
const HASHER &	hasher () const
float	loadFactor () const
float	maxLoadFactor () const
SizeType	maxNumBuckets () const
SizeType	maxSize () const
SizeType	numBuckets () const
SizeType	rehashThreshold () const
SizeType	size () const

---

Detailed Description

template<class KEY_CONFIG, class HASHER, class COMPARATOR, class ALLOCATOR>
class bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >

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.

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.

See Component bslstl_hashtable

---

Member Typedef Documentation

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

typedef ALLOCATOR bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::AllocatorType

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

typedef ::bsl::allocator_traits<AllocatorType> bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::AllocatorTraits

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

typedef KEY_CONFIG::KeyType bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::KeyType

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

typedef KEY_CONFIG::ValueType bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::ValueType

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

typedef bslalg::BidirectionalNode<ValueType> bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::NodeType

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

typedef AllocatorTraits::size_type bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::SizeType

---

Constructor & Destructor Documentation

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::HashTable

(

const ALLOCATOR &

basicAllocator = ALLOCATOR()

)

[explicit]

Create an empty hash-table. Optionally specify a basicAllocator used to supply memory. If basicAllocator is not supplied, a default-constructed object of the (template parameter) type ALLOCATOR is used. If the type ALLOCATOR is bsl::allocator and basicAllocator is not supplied, the currently installed default allocator is used to supply memory. Use 1.0 for the maxLoadFactor. Use a default constructed object of the (template parameter) type HASHER and a default constructed object of the (template parameter) type COMPARATOR to organize elements in the table. No memory is allocated unless the HASHER or COMPARATOR types allocate memory in their default constructor. Note that a bslma::Allocator * can be supplied for basicAllocator if the type ALLOCATOR is bsl::allocator (the default).

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::HashTable	(	const HASHER &	hash,
		const COMPARATOR &	compare,
		SizeType	initialNumBuckets,
		float	initialMaxLoadFactor,
		const ALLOCATOR &	basicAllocator = ALLOCATOR()
	)

Create an empty hash-table using the specified hash and compare functors to organize elements in the table, which will initially have at least the specified initialNumBuckets and a maxLoadFactor of the specified initialMaxLoadFactor. Optionally specify a basicAllocator used to supply memory. If basicAllocator is not supplied, a default-constructed object of the (template parameter) type ALLOCATOR is used. If the type ALLOCATOR is bsl::allocator and basicAllocator is not supplied, the currently installed default allocator is used to supply memory. If this constructor 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 < initialMaxLoadFactor. Note that more than initialNumBuckets buckets may be created in order to preserve the bucket allocation strategy of the hash-table (but never fewer). Also note that a bslma::Allocator * can be supplied for basicAllocator if the type ALLOCATOR is bsl::allocator (the default).

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::HashTable

(

const HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR > &

original

)

Create a hash-table having the same value (and maxLoadFactor) as the specified original object. Use a copy of original.hasher() and a copy of original.comparator() to organize elements in this hash-table. Use the allocator returned by 'bslallocator_traits<ALLOCATOR>:: select_on_container_copy_construction(original.allocator())' to allocate memory. This method requires that the ValueType defined by the (template parameter) type KEY_CONFIG be copy-insertable into this hash-table (see 'Requirements on KEY_CONFIG). Note that this hash-table may have fewer buckets than original, and a correspondingly higher loadFactor, so long as maxLoadFactor is not exceeded. Also note that the created hash table may have a different numBuckets than original, and a correspondingly different loadFactor, as long as maxLoadFactor is not exceeded.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::HashTable

(

BloombergLP::bslmf::MovableRef< HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR > >

original

)

Create a hash-table having the same value (and maxLoadFactor) as the specified original object by moving (in constant time) the contents of original to the new hash-table. Use a copy of original.hasher() and a copy of original.comparator() to organize elements in this hash-table. The allocator associated with original is propagated for use in the newly created hash-table. original is left in a valid but unspecified state.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::HashTable	(	const HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR > &	original,
		const ALLOCATOR &	basicAllocator
	)

Create a hash-table having the same value (and maxLoadFactor) as the specified original object that uses the specified basicAllocator to supply memory. Use a copy of original.hasher() and a copy of original.comparator() to organize elements in this hash-table. This method requires that the ValueType defined by the (template parameter) type KEY_CONFIG be move-insertable into this hash-table. Note that this hash-table may have a different numBuckets than original, and a correspondingly different loadFactor, as long as maxLoadFactor is not exceeded.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::HashTable	(	BloombergLP::bslmf::MovableRef< HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR > >	original,
		const ALLOCATOR &	basicAllocator
	)

Create a hash table having the same value (and maxLoadFactor) as the specified original object that uses the specified basicAllocator to supply memory. The contents of original are moved (in constant time) to the new hash-table if basicAllocator == original.get_allocator(), and are move-inserted (in linear time) using basicAllocator otherwise. original is left in a valid but unspecified state. Use a copy of original.hasher() and a copy of original.comparator() to organize elements in this hash-table. This method requires that the ValueType defined by the (template parameter) type KEY_CONFIG be move-insertable into this hash-table. Note that this hash-table may have a different numBuckets than original, and a correspondingly different loadFactor, as long as maxLoadFactor is not exceeded. Also note that a bslma::Allocator * can be supplied for basicAllocator if the (template parameter) ALLOCATOR is bsl::allocator (the default).

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::~HashTable

(

)

Destroy this object.

---

Member Function Documentation

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

HashTable& bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::operator=

(

const HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR > &

rhs

)

Assign to this object the value, hasher, comparator and maxLoadFactor of the specified rhs object, propagate to this object the allocator of rhs if the ALLOCATOR type has trait propagate_on_container_copy_assignment, and return a reference providing modifiable access to this object. This method requires that the ValueType defined by the (template parameter) type KEY_CONFIG be copy-assignable and copy-insertable into this hash-table (see Requirements on KEY_CONFIG). This method requires that the (template parameter) types HASHER and COMPARATOR be copy-constructible and copy-assignable. Note that these requirements are modeled after the unordered container requirements table in the C++11 standard, which is imprecise on this operation; these requirements might simplify in the future, if the standard is updated.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

HashTable& bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::operator=

(

BloombergLP::bslmf::MovableRef< HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR > >

rhs

)

Assign to this object the value, hasher, comparator, and maxLoadFactor of the specified rhs object, propagate to this object the allocator of rhs if the ALLOCATOR type has trait propagate_on_container_move_assignment, and return a reference providing modifiable access to this object. If this hash-table and rhs use the same allocator (after considering the aforementioned trait), all of the contents of rhs are moved to this hash-table in constant time; otherwise, all elements in this hash table are either destroyed or move-assigned to and each additional element in rhs is move-inserted into this hash-table. rhs is left in a valid but unspecified state. This method requires that the ValueType defined by the (template parameter) type KEY_CONFIG be both move-assignable and move-insertable into this hash-table (see Requirements on KEY_CONFIG).

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

template<class... Args>

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::emplace

(

Args &&...

arguments

)

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);

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

template<class... Args>

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::emplaceWithHint	(	bslalg::BidirectionalLink *	hint,
		Args &&...	arguments
	)

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

template<class... Args>

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::emplaceIfMissing	(	bool *	isInsertedFlag,
		Args &&...	arguments
	)

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);

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::insertIfMissing

(

const KeyType &

key

)

Insert into this hash-table a newly-created ValueType object, constructed by forwarding the specified key and a default-constructed object of the type ValueType::second_type, to the corresponding constructor of ValueType, if key 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 key. If this hash-table contains more than one element with the supplied 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 a pair of arguments representing the key and value, respectively (see Requirements on KEY_CONFIG);

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::insertIfMissing	(	bool *	isInsertedFlag,
		const ValueType &	value
	)

Insert the specified value into this hash-table if a key equivalent to that of value 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 value. If this hash-table contains more than one element with a matching 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 copy-insertable into this hash-table (see Requirements on KEY_CONFIG);

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::insertIfMissing	(	bool *	isInsertedFlag,
		bslmf::MovableRef< ValueType >	value
	)

Insert the specified value into this hash-table if a key equivalent to that of value 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 value. value is left in a valid but unspecified state. If this hash-table contains more than one element with a matching 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);

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

template<class SOURCE_TYPE >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::insertIfMissing	(	bool *	isInsertedFlag,
		BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE)	value
	)

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

template<class SOURCE_TYPE >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::insert

(

BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE)

value

)

Insert into this hash-table a ValueType object created from the specified value 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 new 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 move-insertable into this hash-table (see Requirements on KEY_CONFIG) and the (template parameter) type SOURCE_TYPE be implicitly convertible to ValueType. Note that this method is deprecated is provided only to ensure backward compatibility with existing clients; use the emplace method instead.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

template<class SOURCE_TYPE >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::insert	(	BSLS_COMPILERFEATURES_FORWARD_REF(SOURCE_TYPE)	value,
		bslalg::BidirectionalLink *	hint
	)

Insert into this hash-table a ValueType object created from the specified value (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 move-insertable into this hash-table (see Requirements on KEY_CONFIG) and the (template parameter) type SOURCE_TYPE be implicitly convertible to ValueType. Note that this method is deprecated and is provided only to ensure backward compatibility with existing clients; use the emplaceWithHint method instead.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

template<class KEY_ARG , class BDE_OTHER_TYPE >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::insertOrAssign	(	bool *	isInsertedFlag,
		bslalg::BidirectionalLink *	hint,
		BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG)	key,
		BDE_OTHER_TYPE &&	obj
	)

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

void bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::rehashForNumBuckets

(

SizeType

newNumBuckets

)

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).

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::remove

(

bslalg::BidirectionalLink *

node

)

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

void bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

void bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::reserveForNumElements

(

SizeType

numElements

)

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

void bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::setMaxLoadFactor

(

float

newMaxLoadFactor

)

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

void bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::swap

(

HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR > &

other

)

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

template<class KEY_ARG , class... Args>

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::tryEmplace	(	bool *	isInsertedFlag,
		bslalg::BidirectionalLink *	hint,
		BSLS_COMPILERFEATURES_FORWARD_REF(KEY_ARG)	key,
		Args &&...	args
	)

If a key equivalent to the specified key already exists in this hash-table, 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 the specified args, 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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

ALLOCATOR bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::allocator

(

)

const

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

const bslalg::HashTableBucket& bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::bucketAtIndex

(

SizeType

index

)

const

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()'.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

SizeType bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::bucketIndexForKey

(

const KeyType &

key

)

const

Return the index of the bucket that would contain all the elements having the specified key.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

const COMPARATOR& bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::comparator

(

)

const

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

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

SizeType bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::countElementsInBucket

(

SizeType

index

)

const

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::elementListRoot

(

)

const

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

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

template<class LOOKUP_KEY >

bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate<HASHER, LOOKUP_KEY>::value && BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,LOOKUP_KEY>::value, bslalg::BidirectionalLink *>::type bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::find

(

const LOOKUP_KEY &

key

)

const [inline]

< Return the address of a link whose key is equivalent to the specified key (according to this hash-table's comparator), and a null pointer value if no such link exists. If this hash-table contains more than one element having the supplied key, return the first such element (from the contiguous sequence of elements having the same key). The behavior is undefined unless key is equivalent to the elements of at most one equivalent-key group.

References bslstl::HashTable_ImplParameters< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::comparator(), and bslstl::HashTable_ImplParameters< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::hashCodeForKey().

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::find

(

const KeyType &

key

)

const

Return the address of a link whose key has the same value as the specified key (according to this hash-table's comparator), and a null pointer value if no such link exists. If this hash-table contains more than one element having the supplied key, return the first such element (from the contiguous sequence of elements having the same key).

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bslalg::BidirectionalLink* bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::findEndOfRange

(

bslalg::BidirectionalLink *

first

)

const

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.

Referenced by bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::findRange().

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

template<class LOOKUP_KEY >

bsl::enable_if< BloombergLP::bslmf::IsTransparentPredicate<HASHER, LOOKUP_KEY>::value && BloombergLP::bslmf::IsTransparentPredicate<COMPARATOR,LOOKUP_KEY>::value, void>::type bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::findRange	(	bslalg::BidirectionalLink **	first,
		bslalg::BidirectionalLink **	last,
		const LOOKUP_KEY &	key
	)			const [inline]

< Load into the specified first and last pointers the respective addresses of the first and last link (in the list of elements owned by this hash table) where the contained elements have a key that is equivalent to the specified key using the comparator of this hash-table, and null pointer values if there are no elements matching key. The behavior is undefined unless key is equivalent to the elements of at most one equivalent-key group. Note that the output values will form a closed range, where both first and last point to links satisfying the predicate (rather than a semi-open range where last would point to the element following the range). Also note that this hash-table ensures all elements having the same key form a contiguous sequence.

Note: implemented inline due to Sun CC compilation error.

References BSLS_ASSERT_SAFE, and bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::findEndOfRange().

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

void bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::findRange	(	bslalg::BidirectionalLink **	first,
		bslalg::BidirectionalLink **	last,
		const KeyType &	key
	)			const

Load into the specified first and last pointers the respective addresses of the first and last link (in the list of elements owned by this hash table) where the contained elements have a key that compares equal to the specified key using the comparator of this hash-table, and null pointer values if there are no elements matching key. Note that the output values will form a closed range, where both first and last point to links satisfying the predicate (rather than a semi-open range where last would point to the element following the range). Also note that this hash-table ensures all elements having the same key form a contiguous sequence.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

bool bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::hasSameValue

(

const HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR > &

other

)

const

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).

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

const HASHER& bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::hasher

(

)

const

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

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

float bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::loadFactor

(

)

const

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

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

float bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::maxLoadFactor

(

)

const

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

SizeType bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::maxNumBuckets

(

)

const

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

SizeType bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::maxSize

(

)

const

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.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

SizeType bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::numBuckets

(

)

const

Return the number of buckets contained in this hash table.

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

SizeType bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::rehashThreshold

(

)

const

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

template<class KEY_CONFIG , class HASHER , class COMPARATOR , class ALLOCATOR >

SizeType bslstl::HashTable< KEY_CONFIG, HASHER, COMPARATOR, ALLOCATOR >::size

(

)

const

Return the number of elements in this hash table.

---

The documentation for this class was generated from the following file:

• bslstl_hashtable.h