Description:

template<typename T, typename TStored, typename TKey, typename TIfMapped, typename THash, typename TEqual, typename TAccess, lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>
class alib::monomem::HashTable< T, TStored, TKey, TIfMapped, THash, TEqual, TAccess, THashCaching, TRecycling >

1. Introduction

This class implements a hash table that stores and retrieves objects very efficiently in respect to execution performance. All memory for the hash table and its entries are allocated using a MonoAllocator , which has to be provided with construction of an instance.

Two type definitions based on this class exists, which reduce the set of template parameters of this type by providing reasonable replacements. These types are:

HashSet and
HashMap .

In most cases, one of the two definitions are to be used instead of instantiating this type directly. The meaning of these types are discussed in the next section.

2. Hash Set vs. Hash Map Mode Of Operation

Besides storing values of custom type T , the template parameters and implementation of this class support the concept of "hash maps" which are hash tables that store objects of MappedType which are associated to a value of KeyType.

With that, two type definitions mentioned in the previous section go along well with what is found in the standard C++ library:

HashSet Configures this type to not having a MappedType (the type definition then equals an internal helper struct and is not usable). The full portion of stored type T is used for calculating hash values and testing elements for equality.

The type definition is similar to what types std::unordered_set and std::unordered_multiset of the standard C++ class library provide.

HashMap Configures the type to split the value into a key- and value-portion. Only the key-portion is used for calculating hash values and testing elements for equality. For the value type T , this definition uses type std::pair<const TKey, TMapped>.

The type definition is similar to what types std::unordered_map and std::unordered_multimap of the standard C++ class library provide.

If instead of one of these two type definitions, this type HashTable is "directly" used, the terms "set" and "map" become become a slightly different meaning. Therefore this documentation defines "modes of operation" with this type:

"hash set mode"
Is active if no dedicated mapped type is available. Still the value type T may consist of "more" than type TKey , i.e. the TKey is embedded in T , but the rest of T is not aggregated into a dedicated TMapped value.
"hash map mode"
Is active if otherwise a dedicated TMapped type is given and type T can be constructed by constructing the key-portion and the mapped-portion separately.

The advantage of this approach is obvious: This types supports custom value types T that have a key-portion embedded, as often found in custom types. Remember, this case leads to "hash set mode" although it also has some notion that usual "hash maps" have.

As a sample for the advantage consider method EmplaceIfNotExistent(const KeyType& key, TArgs&&... args). A corresponding method is found with type std::unordered_map::try_emplace, but not with std::unordered_set. In contrast with this implementation, the method is usable with hash map mode as well as with hash set mode!
The only precondition to the availability of this method in hash set mode, is that value type T has to be constructible from the combined list of given arguments, hence the KeyType argument along with given arguments of variadic template types TArgs . The same is true for method EmplaceOrAssign(const KeyType&, TArgs&&... args)

The set of available interface methods slightly changes with the two operation modes:

Hash set mode:
Method overload EmplaceIfNotExistent(TArgs&&... args) is exclusively available with hash sets.
Hash map mode:
The following method overloads are exclusively available with hash maps:
In addition, the following method overloads of inner types are also exclusively available with hash maps.

A hint to restrictions is given with the documentation of each method of concern. Note that methods that expect a single KeyType are usable with both operation modes, as with hash sets the key-type equals type ValueType.

Note: Technically, the availability of the methods is selected at compile-time (using std::enable_if).

3. Single And Multiple Entries

The standard C++ library differentiates between hashing containers that accept only one element with a specific key-portion of the value (see std::unordered_set and std::unordered_map) and those that accept multiple insertions of objects with the same key-portion (see std::unordered_multiset std::unordered_multimap).

This library does not provide separate types and any instantiation of this class allows multiple entries. But this is rather an extension of functionality, than a restriction and does not impose a penalty on performance.

If unique entries are to be achieved, the user of the type has to make sure for herself that no multiple entries are inserted. This can be guaranteed, with the exclusive use of the following set of (partly overloaded) methods, which prevent the creation of multiple entries:

InsertUnique / EmplaceUnique
InsertOrAssign / EmplaceOrAssign
InsertIfNotExistent / EmplaceIfNotExistent

In contrast to this, methods Insert and Emplace (and their overloads) will insert an equal value without giving further notice (for example by providing a special return value that indicates if the inserted key existed before).
Method EraseUnique(const KeyType&) is more efficient than Erase(const KeyType&) and a further advantage is that it asserts (in debug-compilations) that not more than one element is found in the table.

Note

If uniqueness of key values is needed, it might be seen by the reader to be a "disadvantage" that the burden is on the user of the class to guarantee such uniqueness. However, such burden exists with the set-types of the standard library likewise: There, result values have to be evaluated to determine if an insertion was successful or not. The various smaller changes and extensions of the std-types with C++ 14 and 17 reflect the design problems of the approach to provide "unique" and "multi" types.

The approach that ALib takes here has three small benefits:

A user is free to choose a "mixed mode" by allowing duplicates of certain values (keys) and not allowing duplicates for others. While this can be achieved with std::unordered_multimap/set as well, a performance penalty is given, unless the extended interface of C++ 17 standard is used with great care.
The code is better readable, due to explicit naming of the invocations, in contrast to the need to knowing a container's type with each invocation.
The use of the type and this documentation is less confusing, because only one type exists. In contrast, the two types found in std have equally named methods that act differently and return different result types.

4. Re-Hashing

A check for the need to perform re-hashing is made with every insertion of an element. The policy for re-hashing is described as follows:

With insertions, the new average bucket size is calculated as Size divided by BucketCount.
This value is compared with MaxLoadFactor and if higher the number of buckets is increased.
When increased, the new minimum number of buckets is calculated as Size divided by BaseLoadFactor. Starting from this minimum, the effective number of buckets is chosen as a next higher prime number from a static table.
Automatic rehashes may be disabled by setting MaxLoadFactor to a very high value, e.g. std::numeric_limits<float>::max()

The number of buckets is never decreased, unless method Reset is invoked.

Manual re-hashing is not supported by design. In our view, with monotonic growth (or stability in size) and hence the absence of dynamic increase/decrease scenarios, manual rehashing is not needed. Only the base and maximum load factors are of concern, which both can be specified with construction and with methods MaxLoadFactor respectively MaxLoadFactor.
What can be done however is to use method MaxLoadFactor to "disable" rehashing temporarily and thus to allow an efficient mass insertion. Nevertheless, if the number of elements to be inserted is known upfront, the use of method Reserve, respectively ReserveRecyclables is the preferred approach.

5. Iterators

5.1 Iterator Types

There are two types of iterators provided:

Iterator and its constant sibling ConstIterator , used to iterate over all elements of the hash table,
LocalIterator and its constant sibling ConstLocalIterator used to iterate over the elements of a certain bucket only.

Both types satisfy the C++ standard library concept ForwardIterator .

5.2 Validity Rules

The following rules define the validity of existing iterator instances on table operations:

Element Insertions:
- If no rehashing is performed (see previous section) all iterators remain valid.
- If rehashing is performed, existing iterators become invalid in respect to allowance of increments and comparison. The elements that existing iterators referred to prior to the insertion remain valid. Consequently existing iterators may still be used to access the custom element value and modify the mapped portion of it.
Element Removals:
All existing iterators that referred to elements that have been removed become invalid. All others remain fully intact.
The order of the elements that are not erased is preserved, what makes it possible to erase individual elements while iterating through the container.

6. Hash Codes

6.1 Caching Hash Codes

Template parameter THashCaching may be used to control if hash codes are cached. Caching the hash codes increases the memory consumption of this class by sizeof(size_t) per inserted element. While this is only a small amount and memory consumption should not be a great concern when monotonic allocation is used, caching the hash codes may impose a reasonable performance impact. This impact depends on the performance of functor THash working on the key-portion of the inserted value.

The cached hash code is used when the table is re-hashed. In addition, the cached hash code is also used with almost all interface methods (insertion, deletion and search operations): If cached, any needed comparison of two elements will first compare the hash codes and only invoke templated functor TEqual if those match.

If template parameter THashCaching evaluates to Caching::Auto then this class defaults to use caching if type KeyType is not arithmetic (using std::is_arithmetic<TKey> for this check).

The caching option of an instance of this class can be queried with enum CachedHashCodes.

6.2 Hash Codes Precalculation

The following overloaded methods accept parameter hashCode in addition to the parameters accepted by their corresponding base version:

Find(const KeyType&, size_t)
Insert(const T&, size_t)
Insert(T&&, size_t)
InsertUnique(T&&, size_t)
InsertOrAssign(const KeyType&, MappedType&& mapped, size_t)
InsertIfNotExistent(const KeyType&, MappedType&& mapped, size_t)
InsertIfNotExistent(T&&, size_t )
Extract(const KeyType&, size_t )
Erase(const KeyType&, size_t )
EraseUnique( const KeyType&, size_t )

The rational for the provision of these methods is to allow to "pre-calculate" a key's hash code prior to invoking the method. This is efficient in situations where one or more subsequent operations with the same key are performed. For example:

Insertions of multiple objects with the same key.
Insertions of an object into multiple hash tables.
Situations where the result of a find operation may may lead to further operations with the same object.

6.3 Hash Code Quality

To have hash tables perform in constant time O(1) in the average case, a well implemented calculation of hash-codes has to be provided for template type TKey with template functor THash . This is an obligation of the user of this type.

This ALib Module supports compiler symbol ALIB_DEBUG_MONOMEM which enables extra features. The entities relevant for this type are:

These methods may be used to assert the quality of custom hash algorithms.

7. Memory Use

With template parameter TRecycling being either Recycling::Private (the default) or Recycling::Shared the internal "node objects" are remembered when elements are erased, and "recycled" with future insertions. The rational for this lies in the simple fact that memory can not be returned to the monotonic allocator. The recycling mechanism is very lightweight and does not cost measurable performance. If it is assured that no deletions are made during the life-cycle of an instance, type Recycling::None may be used to eliminate this little overhead of recycling.

If the table is re-hashed, the former bucket list is likewise recycled and sliced into as many internal node objects as possible.

With these two mechanisms in place, the use of monotonic allocation with this container is very safe in respect to avoid memory exhaustion. The use of this class, even in scenarios where a lot of (theoretically an endless amount of) erase and insert operations are performed, will not increase memory consumption, as long it is guaranteed that the overall size of the table is limited.

If a maximum number of possible insertions is known, method ReserveRecyclables might be used to allocate all needed memory at once. With that, a snapshot of the allocator can be taken and later used to reset the allocator to the minimum that preserves all memory in the according hash table instance.
For advanced usage, it is advisable to fully understand the concept of monotonic allocation implemented with this module ALib Monomem .

8. Comparison To Standard Library Hash-Types

In the previous sections, it was already referred several times to types

std::unordered_map,
std::unordered_multimap,
std::unordered_set and
std::unordered_multiset

of the C++ standard library. The uses cases and features of these four compared to this type are generally the same and this type can be used to replace the standard tyes without general limitations and vice versa.

Then with C++ 17, the standard library was extended by a new set of types, namely

std::pmr::unordered_map,
std::pmr::unordered_multimap,
std::pmr::unordered_set and
std::pmr::unordered_multiset

which likewise this type, may use monotonic allocation (for example in combination with C++ 17 type std::pmr::monotonic_buffer_resource). While on the one hand ALib in the past needed support of monotonic allocation already for C++ 11, on the other hand the C++ 17 library extensions follow slightly different design goal. Details of this are given in the previous section.

Beside these general differences, the specific similarities and differences can be summarized as follows:

This ALib type does not distinguish sets and maps but provides a more flexible approach: Mapped types do not necessarily need to be build using a std::pair of key and value elements. For convenience, when the use of std::pair is suitable, type definition HashMap offers exactly this.
This ALib type does not distinguish sets/maps from multi-sets/maps. The rational for this design decision has been described in section 3. Single And Multiple Entries.
Almost all members of the four standard library types are implemented with this type in a very compatible fashion. The member names were translated from lower_snake_case to UpperCamelCase and then sometimes slightly changed.
C++ 17 extensions of the standard types were reflected.
Method Find provides additional overloads that accept an externally (pre-) calculated hash code. This allows to efficiently use the same key with a series of searches within different hash table instances. Note that C++ 20 offers a templated version of find, which allows to perform the same optimization.
Erase methods that accept a LocalIterator (bucket iterators) that are not available with the four standard library types, are provided with this type.
There is no operator[] defined. The rational to omit this - at first sight convenient and intuitive - operator, is that it imposes insert operation even if used in r-value expressions. This is considered an unwanted side effect.
The caching of hash-codes can be controlled with this type, while it is an implementation dependent feature with the standard library.
The automatic increase (re-hashing) of the bucket number can be tweaked with constructor parameter pBaseLoadFactor (and method BaseLoadFactor(float)), which is not specified with the standard library types.
Assignment operator= is not available with this implementation. If needed such has to implemented by a user (full iteration with copying elements from one instance to another).

Reference Documentation

Template Parameters

T	The values that this hash table stores. In case of hash map mode, this type needs to contain both, the key-portion and the mapped-portion of the data.
TStored	Internal storage version of T . This is used with hash map mode to provide a data type which is storage-compatible to T but with a constant key-portion. The internally stored (mutable) data is reinterpreted (!) as T in this case. Hence, a reinterpret cast from this type to T has to be "legal". With hash set mode, this type should be the same as T .
TKey	The key type. In case of hash set mode, the type given has to be the same as T . This type is published as HashTable::KeyType .
TIfMapped	The type of the mapped portion of the data. This type is published as HashTable::MappedType . In case of hash set mode, type `void` has to be given and the resulting type HashTable::MappedType is "undefined" (not usable).
THash	With hash map mode, this type needs to be a hash functor on type TKey , which in hash set mode, equals T . This type is published as HashTable::HashType .
TEqual	With hash map mode, this type needs to be a comparison functor on TKey , which in hash set mode, equals T . The type is published as HashTable::EqualType .
TAccess	A functor-like struct used to access the key- and mapped-portion of type T . Needs to provide static method, Key with hash set mode and with hash map mode, in addition method Mapped() has to be defined. For details on required method signatures see provided implementations detail::HashSetAccess and detail::HashMapAccess as a sample.
THashCaching	Determines if hash codes are cached when elements are inserted. Defaults to Caching::Auto, which enables caching if `std::is_arithmetic<TKey>::value` evaluates to `false`.
TRecycling	Denotes the type of recycling that is to be performed. Possible values are Recycling::Private (the default), Recycling::Shared or Recycling::None .

Definition at line 453 of file hashtable.hpp.

#include <hashtable.hpp>

Inheritance diagram for HashTable< T, TStored, TKey, TIfMapped, THash, TEqual, TAccess, THashCaching, TRecycling >:

[legend]

Collaboration diagram for HashTable< T, TStored, TKey, TIfMapped, THash, TEqual, TAccess, THashCaching, TRecycling >:

[legend]

Inner Type Index:
class	ElementHandle

Public Method Index:
Construction/Destruction And Allocator Access
############################################################################################ #############################################################################################
	HashTable (MonoAllocator *pAllocator, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)

	HashTable (MonoAllocator *pAllocator, TSharedRecycler &pRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)

	~HashTable ()

void	SetAllocatorPostConstruction (MonoAllocator *pAllocator)

MonoAllocator *	GetAllocator () const

Size and Capacity
############################################################################################ #############################################################################################
void	Clear ()

void	Reset ()

integer	Size () const

bool	IsEmpty () const

void	Reserve (integer expected, lang::ValueReference reference)

void	ReserveRecyclables (integer expected, lang::ValueReference reference)

integer	RecyclablesCount () const

Hash Policy
############################################################################################ #############################################################################################
void	BaseLoadFactor (float newBaseLoadFactor)

float	BaseLoadFactor () const

void	MaxLoadFactor (float newMaxLoadFactor)

float	MaxLoadFactor () const

Bucket Interface
############################################################################################ #############################################################################################
uinteger	BucketCount () const

uinteger	BucketSize (uinteger bucketNumber) const

uinteger	BucketNumber (const KeyType &key) const

Element Insertion
############################################################################################ #############################################################################################
Iterator	Insert (const T &value)

Iterator	Insert (const T &value, size_t hashCode)

Iterator	Insert (T &&value)

Iterator	Insert (T &&value, size_t hashCode)

Iterator	Insert (ElementHandle &handle)

Iterator	InsertUnique (const T &value)

Iterator	InsertUnique (const T &value, size_t hashCode)

Iterator	InsertUnique (T &&value)

Iterator	InsertUnique (T &&value, size_t hashCode)

template<typename TEnableIf = TIfMapped>
	InsertOrAssign (const KeyType &key, const MappedType &mapped)

template<typename TEnableIf = TIfMapped>
	InsertOrAssign (const KeyType &key, MappedType &&mapped)

template<typename TEnableIf = TIfMapped>
	InsertOrAssign (const KeyType &key, MappedType &&mapped, size_t hashCode)

template<typename TEnableIf = TIfMapped>
	InsertIfNotExistent (const KeyType &key, const MappedType &mapped)

template<typename TEnableIf = TIfMapped>
	InsertIfNotExistent (const KeyType &key, MappedType &&mapped, size_t hashCode)

template<typename TEnableIf = TIfMapped>
	InsertIfNotExistent (const KeyType &key, MappedType &&mapped)

std::pair< Iterator, bool >	InsertIfNotExistent (const T &value)

std::pair< Iterator, bool >	InsertIfNotExistent (T &&value)

std::pair< Iterator, bool >	InsertIfNotExistent (T &&value, size_t hashCode)

Iterator	InsertIfNotExistent (ElementHandle &handle)

template<typename... TArgs>
Iterator	Emplace (TArgs &&... args)

template<typename... TArgs>
Iterator	EmplaceUnique (TArgs &&... args)

template<typename TEnableIf = TIfMapped, typename... TArgs>
std::pair< Iterator, bool >	EmplaceOrAssign (const KeyType &key, TArgs &&... args)

template<typename TEnableIf = TIfMapped, typename... TArgs>
std::pair< Iterator, bool >	EmplaceIfNotExistent (TArgs &&... args)

template<typename TEnableIf , typename... TArgs>
std::pair< Iterator, bool >	EmplaceIfNotExistent (const KeyType &key, TArgs &&... args)

Element Search
############################################################################################ #############################################################################################
Iterator	Find (const KeyType &key)

ConstIterator	Find (const KeyType &key) const

Iterator	Find (const KeyType &key, size_t hashCode)

ConstIterator	Find (const KeyType &key, size_t hashCode) const

bool	Contains (const KeyType &key) const

std::pair< Iterator, Iterator >	EqualRange (const KeyType &key)

std::pair< ConstIterator, ConstIterator >	EqualRange (const KeyType &key) const

Element Removal
############################################################################################ #############################################################################################
ElementHandle	Extract (const KeyType &key)

ElementHandle	Extract (const KeyType &key, size_t hashCode)

ElementHandle	Extract (ConstIterator pos)

integer	Erase (const KeyType &key)

integer	Erase (const KeyType &key, size_t hashCode)

bool	EraseUnique (const KeyType &key)

bool	EraseUnique (const KeyType &key, size_t hashCode)

Iterator	Erase (ConstIterator pos)

ALIB_WARNINGS_IGNORE_NOTHING_RETURNED Iterator	Erase (ConstIterator start, ConstIterator end)

ALIB_WARNINGS_RESTORE LocalIterator	Erase (ConstLocalIterator pos)

LocalIterator	Erase (ConstLocalIterator start, ConstLocalIterator end)

std::iterator_traits Interface
############################################################################################ #############################################################################################
Iterator	begin ()

Iterator	end ()

ConstIterator	begin () const

ConstIterator	end () const

ConstIterator	cbegin () const

ConstIterator	cend () const

LocalIterator	begin (uinteger bucketNumber)

LocalIterator	end (uinteger bucketNumber)

ConstLocalIterator	begin (uinteger bucketNumber) const

ConstLocalIterator	end (uinteger bucketNumber) const

ConstLocalIterator	cbegin (uinteger bucketNumber) const

ConstLocalIterator	cend (uinteger bucketNumber) const

Type Definition Details:

◆ AccessType

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using AccessType = TAccess

Type definition publishing template parameter TAccess .

Definition at line 485 of file hashtable.hpp.

◆ ConstIterator

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using ConstIterator = typename base::template TIterator <const T>

The constant iterator exposed by this container.

Definition at line 502 of file hashtable.hpp.

◆ ConstLocalIterator

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using ConstLocalIterator = typename base::template TLocalIterator <const T>

The constant iterator for a single bucket exposed by this container.

Definition at line 508 of file hashtable.hpp.

◆ EqualType

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using EqualType = TEqual

Type definition publishing template parameter TEqual .

Definition at line 482 of file hashtable.hpp.

◆ HashType

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using HashType = THash

Type definition publishing template parameter THash .

Definition at line 479 of file hashtable.hpp.

◆ Iterator

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using Iterator = typename base::template TIterator < T>

The mutable iterator exposed by this container.

Definition at line 499 of file hashtable.hpp.

◆ KeyType

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using KeyType = TKey

Type definition publishing template parameter TKey .

Definition at line 472 of file hashtable.hpp.

◆ LocalIterator

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using LocalIterator = typename base::template TLocalIterator < T>

The mutable iterator for a single bucket exposed by this container.

Definition at line 505 of file hashtable.hpp.

◆ MappedType

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using MappedType = typename base::TMapped

Type definition publishing template parameter TIfMapped in the case void is not given. If TIfMapped is void, this type definition is not usable.

Definition at line 476 of file hashtable.hpp.

◆ TSharedRecycler

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using TSharedRecycler = lang::SidiListHelper<Element>

This type definition may be used to define an externally managed shared recycler, which can be passed to the alternative constructor of this class when template parameter TRecycling equals Recycling::Shared .

See also: Chapter 1.5 Recycling of the Programmer's Manual for this ALib Module .

Definition at line 493 of file hashtable.hpp.

◆ ValueType

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

using ValueType = T

Type definition publishing template parameter T .

Definition at line 469 of file hashtable.hpp.

Field Details:

◆ CachedHashCodes

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

constexpr bool CachedHashCodes = base::Element::CachedHashCodes

staticconstexpr

TMP constant that denotes whether hash codes are cached or not.

Definition at line 496 of file hashtable.hpp.

Constructor(s) / Destructor Details::

◆ HashTable() [1/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

HashTable	(	MonoAllocator *	pAllocator,
		float	pBaseLoadFactor = 1.0,
		float	pMaxLoadFactor = 2.0 )

inlineexplicit

Constructor.

Note: This cnstructor is not available if template argument TRecycling equals type Recycling::Shared .

Parameters

pAllocator	The monotonic allocator to use.
pBaseLoadFactor	The base load factor. Defaults to `1.0`.
pMaxLoadFactor	The maximum load factor. Defaults to `2.0`.

◆ HashTable() [2/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

HashTable	(	MonoAllocator *	pAllocator,
		TSharedRecycler &	pRecycler,
		float	pBaseLoadFactor = 1.0,
		float	pMaxLoadFactor = 2.0 )

inlineexplicit

Constructor taking a shared recycler.

Parameters

pAllocator	The monotonic allocator to use.
pRecycler	The shared recycler.
pBaseLoadFactor	The base load factor. See method BaseLoadFactor for details. Defaults to `1.0`.
pMaxLoadFactor	The maximum load factor. See method MaxLoadFactor for details. Defaults to `2.0`.

Definition at line 669 of file hashtable.hpp.

◆ ~HashTable()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

~HashTable ( )

inline

Destructor. Destructs all elements in this object.

Definition at line 682 of file hashtable.hpp.

Here is the call graph for this function:

Method Details:

◆ BaseLoadFactor() [1/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

float BaseLoadFactor ( ) const

inline

Returns the actual base load factor.

See also: Overloaded method BaseLoadFactor(float) and this class's documentation section 4. Re-Hashing.

Returns: The current value of the base load factor.

Definition at line 868 of file hashtable.hpp.

◆ BaseLoadFactor() [2/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

void BaseLoadFactor ( float newBaseLoadFactor )

inline

Sets a new value for the "base load factor" used with this container. The base load factor determines the minimum number of buckets when re-hashing is performed.

The formula to determine the minimum number of buckets is Size divided by this factor. A static table of prime numbers is searched for the next higher number and this value is then used to determine the number of buckets.

The default value for this factor is defined as 1.0 by the default value of parameter pBaseLoadFactor of the constructor.

Note: Invoking this method never triggers rehashing.

See also: Overloaded method BaseLoadFactor() and this class's documentation section 4. Re-Hashing.

Parameters

newBaseLoadFactor The new base load factor to use when a rehash is performed.

Definition at line 854 of file hashtable.hpp.

◆ begin() [1/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator begin ( )

inline

Returns an iterator referring to a mutable element at the start of this table.

Returns: The first of element in this container.

Definition at line 2256 of file hashtable.hpp.

◆ begin() [2/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ConstIterator begin ( ) const

inline

Returns an iterator referring to a constant element at the start of this container.

Returns: The first of element in this container.

Definition at line 2264 of file hashtable.hpp.

◆ begin() [3/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

LocalIterator begin ( uinteger bucketNumber )

inline

Returns an iterator referring to a mutable element at the start of bucket of index bucketNumber .

Parameters

bucketNumber The bucket to iterate on.

Returns: The first element in bucket bucketNumber .

Definition at line 2284 of file hashtable.hpp.

◆ begin() [4/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ConstLocalIterator begin ( uinteger bucketNumber ) const

inline

Returns an iterator referring to a mutable element at the start of bucket of index bucketNumber .

Parameters

bucketNumber The bucket to iterate on.

Returns: The first element in bucket bucketNumber .

Definition at line 2308 of file hashtable.hpp.

◆ BucketCount()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

uinteger BucketCount ( ) const

inline

Returns the number of "buckets" that this hash table currently uses.

Returns: The size of the array of hash buckets.

Definition at line 922 of file hashtable.hpp.

◆ BucketNumber()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

uinteger BucketNumber ( const KeyType & key ) const

inline

Returns the number of the bucket corresponding to key .

Parameters

key	The key to evaluate the bucket number for.

Returns: The bucket number that key is assigned to.

Definition at line 948 of file hashtable.hpp.

◆ BucketSize()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

uinteger BucketSize ( uinteger bucketNumber ) const

inline

Returns the number of entries stored in the bucket with the given number.

Parameters

bucketNumber The number of the bucket to receive the size for.

Returns: The number of entries in the specified bucket.

Definition at line 933 of file hashtable.hpp.

◆ cbegin() [1/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ConstIterator cbegin ( ) const

inline

Returns an iterator referring to a constant element at the start of this container.

Returns: The first of element in this container.

Definition at line 2272 of file hashtable.hpp.

◆ cbegin() [2/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ConstLocalIterator cbegin ( uinteger bucketNumber ) const

inline

Returns an iterator referring to a mutable element at the start of bucket of index bucketNumber .

Parameters

bucketNumber The bucket to iterate on.

Returns: The first element in bucket bucketNumber .

Definition at line 2332 of file hashtable.hpp.

◆ cend() [1/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ConstIterator cend ( ) const

inline

Returns an iterator referring to a constant, non-existing element.

Returns: The end of the list of elements in this container.

Definition at line 2276 of file hashtable.hpp.

◆ cend() [2/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ConstLocalIterator cend ( uinteger bucketNumber ) const

inline

Returns an iterator referring to a constant, non-existing element in bucket of index bucketNumber .

Parameters

bucketNumber The bucket to iterate on.

Returns: The end of the list of elements in bucket bucketNumber .

Definition at line 2345 of file hashtable.hpp.

◆ Clear()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

void Clear ( )

inline

Destructs and removes all elements from this hash table. The allocated space of the elements will be preserved and "recycled" with future insertions.

Definition at line 724 of file hashtable.hpp.

◆ Contains()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

bool Contains ( const KeyType & key ) const

inline

Tests if an element with given key is stored in this container.

Parameters

key	The key to search for.

Returns: true if this hash table contains at least one element with given key-portion key , false otherwise.

Definition at line 1846 of file hashtable.hpp.

◆ Emplace()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename... TArgs>

Iterator Emplace ( TArgs &&... args )

inline

Constructs a new element within this container.

Note: The use of this method may insert elements sharing the same key as already existing elements. For more information, see Single And Multiple Entries of the documentation of this class.

Template Parameters

TArgs Types of variadic parameters given with parameter args .

Parameters

args	Variadic parameters to be forwarded to constructor of the inserted element's custom data of ValueType.

Returns: An iterator referring to the element added.

Definition at line 1468 of file hashtable.hpp.

◆ EmplaceIfNotExistent() [1/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename TEnableIf , typename... TArgs>

std::pair< Iterator, bool > EmplaceIfNotExistent	(	const KeyType &	key,
		TArgs &&...	args )

inline

Inserts a new mapped object only if no other object is contained that is associated already with a key that equals the given key .

Note: This method allows to prevent the insertion of double entries. For more information, see Single And Multiple Entries of the documentation of this class.

Availability: This method is available if this templated type is instantiated with hash map mode or for hash sets that only define a subset of T as a key type TKey and whose value type T is constructible if given a key value and the variadic template arguments.

Template Parameters

TEnableIf	Used to disable this method where not available.
TArgs	Types of variadic parameters given with parameter args .

Parameters

key	The key to use for search and insertion.
args	Variadic parameters to be forwarded to constructor of the mapped object of type `MappedType` .

Returns: A pair containing an iterator referencing either the element found or the new element added. The bool component is true if the insertion took place and false nothing was changed.

◆ EmplaceIfNotExistent() [2/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename TEnableIf = TIfMapped, typename... TArgs>

std::pair< Iterator, bool > EmplaceIfNotExistent ( TArgs &&... args )

inline

Inserts a new element only if no other element is contained equals to the one that is constructed by args .

Note: This method allows to prevent the insertion of double entries. For more information, see Single And Multiple Entries of the documentation of this class.; For comparison, a local object of type T is constructed. In case an equal object exists, it is destructed. Otherwise it is moved into this container.

Availability: This method is available only if this templated type is instantiated with hash set mode. For hash map mode, use overloaded version EmplaceIfNotExistent(const KeyType& key, TArgs&&... args).

: Furthermore it is available only if custom type T has a move constructor.

Attention: If a move constructor exists, but is not duly defined, the method produces undefined behavior.
An alternative version that does not require a move constructor is found with EmplaceIfNotExistent(const KeyType& key, TArgs&&... args). This can be used for hash sets that define a subset of T as a key type TKey and whose value type T is constructible from a constant key-portion and the variadic template arguments.

Template Parameters

TEnableIf	Used to disable this method where not available.
TArgs	Types of variadic parameters given with parameter args .

Parameters

args	Variadic parameters to be forwarded to constructor of T .

Returns: A pair containing an iterator referencing either the element found or the new element added. The bool component is true if the insertion took place and false nothing was changed.

◆ EmplaceOrAssign()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename TEnableIf = TIfMapped, typename... TArgs>

std::pair< Iterator, bool > EmplaceOrAssign	(	const KeyType &	key,
		TArgs &&...	args )

inline

Replaces an existing, respectively constructs a new element within this container.

Note: This method allows to prevent the insertion of double entries. For more information, see Single And Multiple Entries of the documentation of this class.

Availability: This method is available if this templated type is instantiated with hash map mode or for hash sets that only define a subset of T as a key type TKey and whose value type T is constructible if given a key value and the variadic template arguments.

Template Parameters

TEnableIf	Used to disable this method where not available.
TArgs	Types of variadic parameters given with parameter args .

Parameters

key	The key to use for search and insertion.
args	Variadic parameters to be forwarded to constructor of the mapped object of type `MappedType` .

Returns: A pair containing an iterator referring to the element added. The bool component is true if the insertion took place and false if the assignment took place.

◆ EmplaceUnique()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename... TArgs>

Iterator EmplaceUnique ( TArgs &&... args )

inline

Constructs a value within this container without checking to place it in the right position in respect to existing elements with the same key-portion.

Attention: This method must only be used if the caller guarantees that no other element is currently stored in this container having an equal key-portion. In such situations, this method is very efficient.
If one exists already, this hash table is not considered in a consistent state after the operation. I.e., method EqualRange will discontinue to function properly.; In debug-compilations, an ALib assertion is raised, if an equal element exists. For this reason, performance differences to method Insert will be seen only with release-compilations.; For more information, see Single And Multiple Entries of the documentation of this class.

Template Parameters

TArgs Types of variadic parameters given with parameter args .

Parameters

args	Variadic parameters to be forwarded to constructor of the element to insert whose key-portion has to be different to all currently contained elements.

Returns: An iterator referring to the element added.

Definition at line 1514 of file hashtable.hpp.

Here is the call graph for this function:

◆ end() [1/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator end ( )

inline

Returns an iterator referring to a mutable, non-existing element.

Returns: The end of the list of elements in this container.

Definition at line 2260 of file hashtable.hpp.

◆ end() [2/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ConstIterator end ( ) const

inline

Returns an iterator referring to a constant, non-existing element.

Returns: The end of the list of elements in this container.

Definition at line 2268 of file hashtable.hpp.

◆ end() [3/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

LocalIterator end ( uinteger bucketNumber )

inline

Returns an iterator referring to a constant, non-existing element in bucket of index bucketNumber .

Parameters

bucketNumber The bucket to iterate on.

Returns: The end of the list of elements in bucket bucketNumber .

Definition at line 2297 of file hashtable.hpp.

◆ end() [4/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ConstLocalIterator end ( uinteger bucketNumber ) const

inline

Returns an iterator referring to a constant, non-existing element in bucket of index bucketNumber .

Parameters

bucketNumber The bucket to iterate on.

Returns: The end of the list of elements in bucket bucketNumber .

Definition at line 2321 of file hashtable.hpp.

◆ EqualRange() [1/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

std::pair< Iterator, Iterator > EqualRange ( const KeyType & key )

inline

Searches a key and returns a pair of iterators. The first is pointing to the first element of the range, the second is pointing to the first element past the range.

If both iterators are equal, the range is empty (both iterators will be equal to end).

Parameters

key	The key to search for.

Returns: A pair of iterators defining the range of elements with key key .

Definition at line 1862 of file hashtable.hpp.

◆ EqualRange() [2/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

std::pair< ConstIterator, ConstIterator > EqualRange ( const KeyType & key ) const

inline

Searches a key and returns a pair of iterators. The first is pointing to the first element of the range, the second is pointing to the first element past the range.

If both iterators are equal, the range is empty (both iterators will be equal to end).

Parameters

key	The key to search for.

Returns: A pair of iterators defining the range of elements with key key .

Definition at line 1876 of file hashtable.hpp.

◆ Erase() [1/6]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

integer Erase ( const KeyType & key )

inline

Erases all elements stored with the given key.

Parameters

key	The key to search elements for deletion.

Returns: The number of elements removed.

Definition at line 1969 of file hashtable.hpp.

Here is the call graph for this function:

◆ Erase() [2/6]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

integer Erase	(	const KeyType &	key,
		size_t	hashCode )

inline

Overloaded version of method Erase(const KeyType&) which accepts the hashCode of the given key as a second parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Parameters

key	The key to search elements for deletion.
hashCode	Pre-calculated hash code of key .

Returns: The number of elements removed.

Definition at line 1985 of file hashtable.hpp.

Here is the call graph for this function:

◆ Erase() [3/6]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator Erase ( ConstIterator pos )

inline

Removes an element specified by an iterator.
If the iterator was not valid (i.e end), the method has undefined behavior. With debug builds an ALib assertion is raised.

The order of the elements that are not erased is preserved, what makes it possible to erase individual elements while iterating through the container.

Parameters

pos	The iterator to the element to remove.

Returns: An iterator following the removed element.

Definition at line 2072 of file hashtable.hpp.

Here is the call graph for this function:

◆ Erase() [4/6]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ALIB_WARNINGS_IGNORE_NOTHING_RETURNED Iterator Erase	(	ConstIterator	start,
		ConstIterator	end )

inline

Removes all elements from the given position start to the element before given position end .

The order of the elements that are not erased is preserved, what makes it possible to erase individual elements while iterating through the container.

Parameters

start	The iterator to the element to remove.
end	The first element not to remove.

Returns: An iterator following the last removed element.

Definition at line 2108 of file hashtable.hpp.

Here is the call graph for this function:

◆ Erase() [5/6]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ALIB_WARNINGS_RESTORE LocalIterator Erase ( ConstLocalIterator pos )

inline

Removes an element specified by a bucket iterator. Bucket iterators are receivable using overloaded methods begin(uinteger) and cbegin(uinteger) .

The order of the elements that are not erased is preserved, what makes it possible to erase individual elements while iterating through the container.

Parameters

pos	The iterator to the element to remove.

Returns: An iterator following the removed element.

Definition at line 2190 of file hashtable.hpp.

◆ Erase() [6/6]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

LocalIterator Erase	(	ConstLocalIterator	start,
		ConstLocalIterator	end )

inline

Removes all element from the given bucket iterator position start to the element before given position end .

The order of the elements that are not erased is preserved, what makes it possible to erase individual elements while iterating through the container.

Parameters

start	The bucket iterator to the element to remove.
end	The bucket iterator to the first element not to remove.

Returns: An iterator following the removed element.

Definition at line 2218 of file hashtable.hpp.

Here is the call graph for this function:

◆ EraseUnique() [1/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

bool EraseUnique ( const KeyType & key )

inline

Erases the unique element with the given key.

Note: This method is slightly more efficient than method Erase(const KeyType&), as it will not search for a next element with an equal key.
In debug-compilations, the method asserts that no second element with the same key is available.
If this table is supposed to store only unique elements, the use of this method is therefore recommended, as an assertions hints to an erroneous use of the insertion methods.

Parameters

key	The key to search elements for deletion.

Returns: true if an element was found and removed, false otherwise.

Definition at line 2027 of file hashtable.hpp.

Here is the call graph for this function:

◆ EraseUnique() [2/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

bool EraseUnique	(	const KeyType &	key,
		size_t	hashCode )

inline

Overloaded version of method EraseUnique(const KeyType&) which accepts the hashCode of the given key as a second parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Parameters

key	The key to search elements for deletion.
hashCode	Pre-calculated hash code of key .

Returns: true if an element was found and removed, false otherwise.

Definition at line 2043 of file hashtable.hpp.

Here is the call graph for this function:

◆ Extract() [1/3]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ElementHandle Extract ( const KeyType & key )

inline

Extracts the first element found with the given key from the hash table and returns a handle to it.
Extracting a element invalidates only the iterators to the extracted element, and preserves the relative order of the elements that are not extracted.

Extracting and re-inserting nodes is the only way to change a key of an element without performing reallocation and or destruction/construction.

Parameters

key	The key to search a first element for.

Returns: A handle to an element that allows changes of the formerly stored value. Changes may include the key-portion of the data stored. Handles may be passed to one of the overloaded insert methods. If no element was found, the returned handle is empty.

Definition at line 1899 of file hashtable.hpp.

Here is the call graph for this function:

◆ Extract() [2/3]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ElementHandle Extract	(	const KeyType &	key,
		size_t	hashCode )

inline

Overloaded version of method Extract(const KeyType&) which accepts the hashCode of the given key as a second parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Parameters

key	The key to search a first element for.
hashCode	Pre-calculated hash code of key .

Returns: A handle to an element that allows changes of the formerly stored value. Changes may include the key-portion of the data stored. Handles may be passed to one of the overloaded insert methods. If no element was found, the returned handle is empty.

Definition at line 1917 of file hashtable.hpp.

Here is the call graph for this function:

◆ Extract() [3/3]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ElementHandle Extract ( ConstIterator pos )

inline

Extracts the first element found with the given key from the hash table and returns a handle to it.
If the iterator was not valid (i.e. end), the method has undefined behavior. With debug builds an ALib assertion is raised.

Extracting a element invalidates only the iterators to the extracted element, and preserves the relative order of the elements that are not extracted.

Extracting and re-inserting nodes is the only way to change a key of an element without performing reallocation and or destruction/construction.

Parameters

pos	The position of the element to extract.

Returns: A handle to an element that allows changes of the formerly stored value. Changes may include the key-portion of the data stored. Handles may be passed to one of the overloaded insert methods. If no element was found, the returned handle is empty.

Definition at line 1947 of file hashtable.hpp.

Here is the call graph for this function:

◆ Find() [1/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator Find ( const KeyType & key )

inline

Returns an iterator pointing to the first element of equal key value.

Note: The iterator returned may be incremented. It is assured that further elements contained in this hash table with the same key are consecutively following this first element returned. However, the iterator does not end with the last element of that key.

See also: Method EqualRange, which also returns an iterator pointing behind the last element with that key.

Parameters

key	The key to search for.

Returns: An iterator pointing to the first element found with equal key-portion, respectively one being equal to end, if no element was found with key .

Definition at line 1782 of file hashtable.hpp.

◆ Find() [2/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ConstIterator Find ( const KeyType & key ) const

inline

Searches an element.

Parameters

key	The key to search for.

Returns: An iterator pointing to the first element found with equal key-portion, respectively one being equal to end, if no element was found with key .

Definition at line 1796 of file hashtable.hpp.

◆ Find() [3/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator Find	(	const KeyType &	key,
		size_t	hashCode )

inline

Overloaded version of method Find(const KeyType&) which accepts the hashCode of the given key as a second parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Parameters

key	The key to search for.
hashCode	Pre-calculated hash code of key .

Returns: An iterator pointing to the first element found with equal key-portion, respectively one being equal to end, if no element was found with key .

Definition at line 1815 of file hashtable.hpp.

◆ Find() [4/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

ConstIterator Find	(	const KeyType &	key,
		size_t	hashCode ) const

inline

Overloaded version of method Find(const KeyType&)const which accepts the hashCode of the given key as a second parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Parameters

key	The key to search for.
hashCode	Pre-calculated hash code of key .

Returns: An iterator pointing to the first element found with equal key-portion, respectively one being equal to end, if no element was found with key .

Definition at line 1833 of file hashtable.hpp.

◆ GetAllocator()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

MonoAllocator * GetAllocator ( ) const

inline

Returns the allocator of this object. Usually the allocator might be used to perform allocations in respect to data found in objects stored in this object. However, such allowance is dependent on the use case and not part of this class's contract.

Returns: The allocator that was provided in the constructor.

Definition at line 710 of file hashtable.hpp.

◆ Insert() [1/5]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator Insert ( const T & value )

inline

See Insert(T&&) which is invoked with a copy of value .

Parameters

value A value to copy and insert.

Returns: An iterator referring to the element added.

Definition at line 962 of file hashtable.hpp.

Here is the call graph for this function:

◆ Insert() [2/5]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator Insert	(	const T &	value,
		size_t	hashCode )

inline

Overloaded version of method Insert(const T&) which accepts the hashCode of the given value as a second parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Parameters

value	A value to copy and insert.
hashCode	Pre-calculated hash code of value .

Returns: An iterator referring to the element added.

Definition at line 977 of file hashtable.hpp.

Here is the call graph for this function:

◆ Insert() [3/5]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator Insert ( ElementHandle & handle )

inline

Inserts the element contained in the given ElementHandle into the hash table.

Note: The use of this method may insert elements sharing the same key as already existing elements. For more information, see Single And Multiple Entries of the documentation of this class.

Objects of type ElementHandle objects may be received using overloaded methods Extract. The combination of Extract and this method (as well as method InsertIfNotExistent(ElementHandle&) are the only way to change the key-portion of an element without element destruction/re-construction.

Parameters

handle A reference to a handle to an element, previously received with Extract.

Returns: On success, returns an iterator that refers to the inserted element. On failure (if parameter handle was empty), the returned iterator equals end.

Definition at line 1048 of file hashtable.hpp.

Here is the call graph for this function:

◆ Insert() [4/5]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator Insert ( T && value )

inline

Moves the given value into this table.
Existing iterators remain valid.

Note: The use of this method may insert elements sharing the same key as already existing elements. For more information, see Single And Multiple Entries of the documentation of this class.

Parameters

value An rvalue reference of contained type T to insert.

Returns: An iterator referring to the element added.

Definition at line 996 of file hashtable.hpp.

Here is the call graph for this function:

◆ Insert() [5/5]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator Insert	(	T &&	value,
		size_t	hashCode )

inline

Overloaded version of method Insert(T&&) which accepts the hashCode of the given value as a second parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Parameters

value	An rvalue reference of contained type T to insert.
hashCode	Pre-calculated hash code of value .

Returns: An iterator referring to the element added.

Definition at line 1013 of file hashtable.hpp.

◆ InsertIfNotExistent() [1/7]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename TEnableIf = TIfMapped>

InsertIfNotExistent	(	const KeyType &	key,
		const MappedType &	mapped )

inline

See InsertIfNotExistent(const KeyType&, MappedType&&) which is invoked with a copy of mapped .

Availability: This method is only available with hash map mode.

Template Parameters

TEnableIf Used to disable this method for instantiations of this template type with hash set mode.

Parameters

key	The key to use for search and insertion.
mapped	The mapped object to copy and insert if key is not existing.

Returns: A pair containing an iterator referencing either the element found or the new element added. The bool component is true if the insertion took place and false if nothing was changed.

Definition at line 1269 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertIfNotExistent() [2/7]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename TEnableIf = TIfMapped>

InsertIfNotExistent	(	const KeyType &	key,
		MappedType &&	mapped )

inline

Inserts a new mapped object only if no other object is contained that is associated already with the same key as given key .

Note: This method allows to prevent the insertion of double entries. For more information, see Single And Multiple Entries of the documentation of this class.

Availability: This method is only available with hash map mode.

Template Parameters

TEnableIf Used to disable this method for instantiations of this template type with hash set mode.

Parameters

key	The key to use for search and insertion.
mapped	The mapped value to insert if key is not existing.

Returns: A pair containing an iterator referencing either the element found or the new element added. The bool component is true if the insertion took place and false if nothing was changed.

Definition at line 1334 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertIfNotExistent() [3/7]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename TEnableIf = TIfMapped>

InsertIfNotExistent	(	const KeyType &	key,
		MappedType &&	mapped,
		size_t	hashCode )

inline

Overloaded version of method InsertIfNotExistent(const KeyType&,MappedType&&) which accepts the hashCode of the given key as a third parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Template Parameters

TEnableIf Used to disable this method for instantiations of this template type with hash set mode.

Parameters

key	The key to use for search and insertion.
hashCode	Pre-calculated hash code of key .
mapped	The mapped value to insert if key is not existing.

Returns: A pair containing an iterator referencing either the element found or the new element added. The bool component is true if the insertion took place and false if nothing was changed.

Definition at line 1292 of file hashtable.hpp.

◆ InsertIfNotExistent() [4/7]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

std::pair< Iterator, bool > InsertIfNotExistent ( const T & value )

inline

See InsertIfNotExistent(T&&) which is invoked with a copy of value .

Parameters

value The value to copy and insert.

Returns: A pair containing an iterator referencing either the element found or the new element added. The bool component is true if the insertion took place and false if nothing was changed.

Definition at line 1347 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertIfNotExistent() [5/7]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator InsertIfNotExistent ( ElementHandle & handle )

inline

Inserts the element contained in the given ElementHandle into this table, if no equal element exists. In the unsuccessful case, the given ElementHandle remains set and can be reused.

Existing iterators remain valid.

Note: This method allows to prevent the insertion of double entries. For more information, see Single And Multiple Entries of the documentation of this class.

See also: Objects of type ElementHandle objects may be received using overloaded methods Extract. The combination of Extract and this method (as well as method Insert(ElementHandle&) are the only way to change the key-portion of an element without element destruction/re-construction.

Parameters

handle A reference to a handle to an element, previously received with Extract.

Returns: If an empty handle is given, end is returned. Otherwise, if no equal element existed, an iterator that refers to the inserted element is returned and the given handle is emptied.
If an equal element existed, the returned iterator refers to the existing element and the handle remains set (not empty).

Definition at line 1429 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertIfNotExistent() [6/7]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

std::pair< Iterator, bool > InsertIfNotExistent ( T && value )

inline

Inserts a new mapped object only if no other object is contained that is associated already with the same key as given key .

Note: This method allows to prevent the insertion of double entries. For more information, see Single And Multiple Entries of the documentation of this class.

Parameters

value A rvalue reference of a T to insert.

Returns: A pair containing an iterator referencing either the element found or the new element added. The bool component is true if the insertion took place and false if nothing was changed.

Definition at line 1368 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertIfNotExistent() [7/7]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

std::pair< Iterator, bool > InsertIfNotExistent	(	T &&	value,
		size_t	hashCode )

inline

Overloaded version of method InsertIfNotExistent(T&&) which accepts the hashCode of the given key as a second parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Parameters

value	A rvalue reference of a T to insert.
hashCode	Pre-calculated hash code of value .

Returns: A pair containing an iterator referencing either the element found or the new element added. The bool component is true if the insertion took place and false if nothing was changed.

Definition at line 1387 of file hashtable.hpp.

◆ InsertOrAssign() [1/3]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename TEnableIf = TIfMapped>

InsertOrAssign	(	const KeyType &	key,
		const MappedType &	mapped )

inline

See InsertOrAssign(const KeyType&, MappedType&&) which is invoked with a copy of mapped .

Availability: This method is only available with hash map mode.

Template Parameters

TEnableIf Used to disable this method for instantiations of this template type with hash set mode.

Parameters

key	The key to use for search and insertion.
mapped	The mapped value to copy and then insert or assign.

Returns: A pair containing an iterator referencing the element added. The bool component is true if the insertion took place and false if the assignment took place.

Definition at line 1178 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertOrAssign() [2/3]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename TEnableIf = TIfMapped>

InsertOrAssign	(	const KeyType &	key,
		MappedType &&	mapped )

inline

Replaces an existing, respectively inserts a new element into this hash table.

Note: This method allows to prevent the insertion of double entries. For more information, see Single And Multiple Entries of the documentation of this class.

Availability: This method is only available with hash map mode.

Template Parameters

TEnableIf Used to disable this method for instantiations of this template type with hash set mode.

Parameters

key	The key to use for search and insertion.
mapped	The mapped value to insert or assign.

Returns: A pair containing an iterator referring to the element added. The bool component is true if the insertion took place and false if the assignment took place.

Definition at line 1206 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertOrAssign() [3/3]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

template<typename TEnableIf = TIfMapped>

InsertOrAssign	(	const KeyType &	key,
		MappedType &&	mapped,
		size_t	hashCode )

inline

Overloaded version of method alib::monomem::HashTable::InsertOrAssign(const KeyType& " MappedType&&)" which accepts the hashCode of the given key as a third parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Availability: This method is only available with hash map mode.

Template Parameters

TEnableIf Used to disable this method for instantiations of this template type with hash set mode.

Parameters

key	The key to use for search and insertion.
mapped	The mapped value to insert or assign.
hashCode	Pre-calculated hash code of key .

Returns: A pair containing an iterator referring to the element added. The bool component is true if the insertion took place and false if the assignment took place.

Definition at line 1233 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertUnique() [1/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator InsertUnique ( const T & value )

inline

See InsertUnique(T&&) which is invoked with a copy of value .

Parameters

value An element to insert whose key-portion has to be different to all currently contained elements.

Returns: An iterator referring to the element added.

Definition at line 1069 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertUnique() [2/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator InsertUnique	(	const T &	value,
		size_t	hashCode )

inline

Overloaded version of method InsertUnique(const T&) which accepts the hashCode of the given key as a second parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Parameters

value	An element to insert whose key-portion has to be different to all currently contained elements.
hashCode	Pre-calculated hash code of value .

Returns: An iterator referring to the element added.

Definition at line 1085 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertUnique() [3/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator InsertUnique ( T && value )

inline

Moves the given value into this table without checking to place it in the right position in respect to existing elements with the same key-portion.

Attention: This method must only be used if the caller guarantees that no other element is currently stored in this container having an equal key-portion. In such situations, this method is very efficient.
If one exists already, this hash table is not considered in a consistent state after the operation. I.e., method EqualRange will discontinue to function properly.; In debug-compilations, an ALib assertion is raised, if an equal element exists. For this reason, performance differences to method Insert will be seen only with release-compilations.; For more information, see Single And Multiple Entries of the documentation of this class.

Parameters

value An element to insert whose key-portion has to be different to all currently contained elements.

Returns: An iterator referring to the element added.

Definition at line 1116 of file hashtable.hpp.

Here is the call graph for this function:

◆ InsertUnique() [4/4]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

Iterator InsertUnique	(	T &&	value,
		size_t	hashCode )

inline

Overloaded version of method InsertUnique(T&&) which accepts the hashCode of the given key as a second parameter.

See alib_ns_monomem_hashtable_hashprecalc for use cases of this method.

Parameters

value	An element to insert whose key-portion has to be different to all currently contained elements.
hashCode	Pre-calculated hash code of value .

Returns: An iterator referring to the element added.

Definition at line 1133 of file hashtable.hpp.

Here is the call graph for this function:

◆ IsEmpty()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

bool IsEmpty ( ) const

inline

Invokes Size and compares result with 0.

Returns: true if this list is empty, false otherwise.

Definition at line 756 of file hashtable.hpp.

◆ MaxLoadFactor() [1/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

float MaxLoadFactor ( ) const

inline

Returns the actual maximum load factor.

See also: Overloaded method MaxLoadFactor(float) and this class's documentation section 4. Re-Hashing.

Returns: The current value of the maximum load factor.

Definition at line 908 of file hashtable.hpp.

◆ MaxLoadFactor() [2/2]

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

void MaxLoadFactor ( float newMaxLoadFactor )

inline

Sets a new value for the "maximum load factor" which is the average number of elements per bucket.

The default value for this factor is defined as 2.0 by the default value of parameter pMaxLoadFactor of the constructor.

Note: Invoking this method triggers rehashing, in case the hash table is not empty and the new maximum load factor is below the current load factor of this container, which equals Size divided by BucketCount.
This method may be used to temporarily disable re-hashing by providing std::numeric_limits<float>::max().

See also: Overloaded method MaxLoadFactor() and this class's documentation section 4. Re-Hashing.

Parameters

newMaxLoadFactor The maximum load factor used to determine the need of re-hashing.

Definition at line 894 of file hashtable.hpp.

◆ RecyclablesCount()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

integer RecyclablesCount ( ) const

inline

Counts the number of currently allocated but unused (not contained) element nodes that will be recycled with upcoming insertions.

Note: This method is provided for completeness and unit-testing. It should not be of relevance for common usage.
Furthermore, this method is not available (aka does not compile) with instantiations that specify template parameter TRecycling as Recycling::None .

Returns: The number of removed and not yet recycled elements.

Definition at line 824 of file hashtable.hpp.

◆ Reserve()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

void Reserve	(	integer	expected,
		lang::ValueReference	reference )

inline

Reserves space for at least the given number of elements. This might re-hash this table.

See also: Method ReserveRecyclables.

Parameters

expected	The expected number or increase of elements to be stored in the hash table.
reference	Denotes whether expected is meant as an absolute size or an increase .

Definition at line 768 of file hashtable.hpp.

Here is the call graph for this function:

◆ ReserveRecyclables()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

void ReserveRecyclables	(	integer	expected,
		lang::ValueReference	reference )

inline

Same as Reserve but in addition also already allocates the required space for the number of additional elements expected.

Note: If the definite number of stored elements that is never exceeded is known, a snapshot of the monotonic allocator could be taken after the invocation of this method and then used to reset the monotonic allocator with preserving the memory used by this container.; This method is not available (aka does not compile) with instantiations that specify template parameter TRecycling as Recycling::None .

Parameters

expected	The expected number or increase of elements to be stored in the hash table.
reference	Denotes whether expected is meant as an absolute size or an increase .

Definition at line 793 of file hashtable.hpp.

Here is the call graph for this function:

◆ Reset()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

void Reset ( )

inline

Resets this container. Invokes Clear to destruct all keys and values and in case of private recycling disposes all previously allocated recyclable instances of the internal element type.

This method has to be called prior to resetting the associated monotonic allocator given in the constructor.

Definition at line 737 of file hashtable.hpp.

◆ SetAllocatorPostConstruction()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

void SetAllocatorPostConstruction ( MonoAllocator * pAllocator )

inline

In some situations, the allocator object to use might not be available with construction of an instance. This method may be used to attach an external allocator at a later point in time - but prior to this instance's first use.

Parameters

pAllocator The allocator that was omitted in the constructor.

Definition at line 695 of file hashtable.hpp.

◆ Size()

template<typename T , typename TStored , typename TKey , typename TIfMapped , typename THash , typename TEqual , typename TAccess , lang::Caching THashCaching = lang::Caching::Auto, typename TRecycling = Recycling::Private>

integer Size ( ) const

inline

Returns the number of stored elements. Note that this method runs in constant time, as the number of elements is kept counted during operation.

Returns: The number of elements stored in the hash table.

Definition at line 747 of file hashtable.hpp.

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

Description:

Contents

1. Introduction

2. Hash Set vs. Hash Map Mode Of Operation

3. Single And Multiple Entries

4. Re-Hashing

5. Iterators

5.1 Iterator Types

5.2 Validity Rules

6. Hash Codes

6.1 Caching Hash Codes

6.2 Hash Codes Precalculation

6.3 Hash Code Quality

7. Memory Use

8. Comparison To Standard Library Hash-Types

Reference Documentation

Inner Type Index:

Public Method Index:

Type Definition Details:

◆ AccessType

◆ ConstIterator

◆ ConstLocalIterator

◆ EqualType

◆ HashType

◆ Iterator

◆ KeyType

◆ LocalIterator

◆ MappedType

◆ TSharedRecycler

◆ ValueType

Field Details:

◆ CachedHashCodes

Constructor(s) / Destructor Details::

◆ HashTable() [1/2]

◆ HashTable() [2/2]

◆ ~HashTable()

Method Details:

◆ BaseLoadFactor() [1/2]

◆ BaseLoadFactor() [2/2]

◆ begin() [1/4]

◆ begin() [2/4]

◆ begin() [3/4]

◆ begin() [4/4]

◆ BucketCount()

◆ BucketNumber()

◆ BucketSize()

◆ cbegin() [1/2]

◆ cbegin() [2/2]

◆ cend() [1/2]

◆ cend() [2/2]

◆ Clear()

◆ Contains()

◆ Emplace()

◆ EmplaceIfNotExistent() [1/2]

◆ EmplaceIfNotExistent() [2/2]

◆ EmplaceOrAssign()

◆ EmplaceUnique()

◆ end() [1/4]

◆ end() [2/4]

◆ end() [3/4]

◆ end() [4/4]

◆ EqualRange() [1/2]

◆ EqualRange() [2/2]

◆ Erase() [1/6]

◆ Erase() [2/6]

◆ Erase() [3/6]

◆ Erase() [4/6]

◆ Erase() [5/6]

◆ Erase() [6/6]

◆ EraseUnique() [1/2]

◆ EraseUnique() [2/2]

◆ Extract() [1/3]

◆ Extract() [2/3]

◆ Extract() [3/3]

◆ Find() [1/4]

◆ Find() [2/4]

◆ Find() [3/4]

◆ Find() [4/4]

◆ GetAllocator()

◆ Insert() [1/5]