HashTable< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling > Class Template Reference

Description:

template<typename TAllocator, typename TValueDescriptor, typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>
class alib::containers::HashTable< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >

Contents

1. Introduction
2. Hash Sets vs. Hash Maps
3. Single And Multiple Entries
4. Re-Hashing
5. Iterators
6. Hash Codes
  6.1 Caching Hash Codes
  6.2 Hash Codes Pre-calculation
  6.3 Hash Codes Pre-calculation
7. Memory Use
8. Comparison To Standard Library Hash-Types
Reference Documentation

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 template allocator type.

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

• HashMap and
• HashSet.

In many cases, the use of one of these definitions is more convenient than instantiating this type directly. The meaning of these types is discussed in the next section.

2. Hash Sets vs. Hash Maps

A "hash set" is commonly understood as a type that contains custom values of StoredType, which are also used as the key to finding such stored objects. "Hash maps" are hash tables that store objects of a custom MappedType which are associated to a value of a key KeyType. In this "mode" the key is not contained in the custom value.
The template parameters and implementation of this class supports both concepts and they are covered by the two provided alternative type definitions mentioned in the previous section. Furthermore, those go along well with what is found in the standard C++ library:

1. HashSet Removes template parameter TValueDescriptor (by presetting it to a built-in helper-type) and instead denotes all three types, namely StoredType, KeyType and MappedType to the same new template parameter T. Functors THash and TEqual consequently expect the StoredType.
   

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

2. HashMap Removes template parameter TValueDescriptor (by presetting it to a built-in helper-type) and instead introduces template parameters TKey and TMapped. Here, only the key-portion is used for calculating hash values and testing elements for equality. The mapped-portion is the true custom type that is to be stored.
   Consequently, HashMap defines the StoredType as std::pair<TKey, TMapped>.
   

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

To achieve this flexibility, template parameter TValueDescriptor, which is exposed as DescriptorType, is constrained to have two methods Key() and Mapped() to extract a reference to the corresponding portions out of the stored value.

One of the advantages of this approach is that this type supports a third "mode", besides implementing "hash sets" and "hash maps": Custom value type StoredType may have a key-portion embedded, instead of using the complete type as a search key.
While there is no specific type definition for this "key-embedded mode" available, the using code needs to create a custom version of template parameter TValueDescriptor which enables the extraction of the key and mapped portions of the stored type. The following table summarizes this:

Working Mode	Type to Use	Value Descriptor Type
Hash Set	HashSet (A type definition on HashTable)	Automaticly chosen as built-in TIdentDescriptor
Hash Map	HashMap (A type definition on HashTable)	Automaticly chosen as built-in TPairDescriptor
Hash Set with embedded Key	HashTable (The original type)	A custom type has to be provided

Note

The hash-table implementations of the standard C++ library do not support a similar approach. While with the provision of customized hash- and comparison-functors, of course only a portion of a type stored in a set can be used for hashing and comparing, still the interface functions require to receive a "complete" instance, which then is often "nulled" or "empty" in respect to the fields that are not used for the key.
Because of this limitation, ALib introduces template parameter TValueDescriptor in addition to parameters THash and TEqual.

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 maps as well as with hash sets!
The only precondition to the availability of this method, is that the StoredType 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:

1. Hash Set Mode:
   Method overload EmplaceIfNotExistent(TArgs&&... args) is exclusively available with hash sets.
   

2. Hash Map Mode:
   The following method overloads are exclusively available with hash maps:

   • InsertOrAssign(const KeyType&, MappedType&&)
   • InsertOrAssign(const KeyType&, const MappedType&)
   • InsertIfNotExistent(const KeyType&, MappedType&&)
   • InsertIfNotExistent(const KeyType&, const MappedType&)
     
     

   In addition, the following method overloads of inner types are also exclusively available with hash maps.

   • TIterator::Mapped
   • TLocalIterator::Mapped
   • ElementHandle::Mapped

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, because with hash sets the key-type equals type StoredType.

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:

1. 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.
2. 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.
3. 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 the 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 before 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 Pre-calculation

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 rationale for the provision of these methods is to allow to "pre-calculate" a key's hash code before 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_CONTAINERS which enables extra features. The entities relevant for this type are:

• DbgGetHashTableDistribution,
• DbgDumpDistribution and
• DbgDumpHashtable.

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

7. Memory Use

With template parameter TRecycling being either Private (the default) or Shared, the internal "node objects" are remembered when deleted, and "recycled" with future insertions. The rationale for this lies in the simple fact that memory cannot 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 None may be used to eliminate this little overhead of recycling. This is why type-definition MonoAllocator is recommended to be used with this container.

If the table is re-hashed, the former bucket list is likewise recycled and sliced into as many internal node objects as possible. The precondition for this is that the allocator interface method allowsMemSplit returns true. This is true for type MonoAllocator.

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

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). On the one hand, ALib in the past needed support of monotonic allocation already for C++ 11, and on the other hand, the C++ 17 library extensions follow slightly different design goals. Details of these were given in the previous section.

Besides 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 rationale 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 efficiently using 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 performing 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 rationale 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).

See also

• Chapter 4.1 Provided Containers of the joint Programmer's Manuals of modules ALib Containers and ALib Monomem.
• Chapter 1.4.2 Asserting Critical Sections' Entry And Exit of the Programmer's Manual of module ALib Threads for information about debugging multithreaded access on instances of this type.

Reference Documentation

Template Parameters

TAllocator	The allocator type to use, as prototyped with Allocator.
TValueDescriptor	Defines the StoredType, KeyType and MappedType. Furthermore has to proving methods that to extract key- and mapped values out of the stored type. For details on required type definitions and method signatures, see provided implementations TIdentDescriptor and TPairDescriptor as a sample. The type is published as HashTable::DescriptorType.
THash	The hash functor applicable to the key-type defined by TValueDescriptor. Defaults to std::hash<typename TValueDescriptor::KeyType> and is published as HashTable::HashType.
TEqual	The comparison functor on the key-type defined by TValueDescriptor. Defaults to std::equal_to<typename TValueDescriptor::KeyType> and is published as HashTable::EqualType.
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 Private (the default), Shared or None.

Definition at line 458 of file hashtable.hpp.

#include <hashtable.hpp>

Inheritance diagram for HashTable< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >:

Collaboration diagram for HashTable< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >:

Inner Type Index:
class	ElementHandle

Public Type Index:
using	AllocatorType = TAllocator
	Type definition publishing template parameter TAllocator.
using	ConstIterator = typename base::template TIterator <const StoredType>
	The constant iterator exposed by this container.
using	ConstLocalIterator = typename base::template TLocalIterator <const StoredType>
	The constant iterator for a single bucket exposed by this container.
using	DescriptorType = TValueDescriptor
	Type definition publishing template parameter TValueDescriptor.
using	EqualType = TEqual
	Type definition publishing template parameter TEqual.
using	HashType = THash
	Type definition publishing template parameter THash.
using	Iterator = typename base::template TIterator < StoredType>
	The mutable iterator exposed by this container.
using	KeyType = typename TValueDescriptor::KeyType
using	LocalIterator = typename base::template TLocalIterator < StoredType>
	The mutable iterator for a single bucket exposed by this container.
using	MappedType = typename TValueDescriptor::MappedType
using	SharedRecyclerType = typename base::SharedRecyclerType
using	StoredType = typename TValueDescriptor::StoredType

Public Static Field Index:
static constexpr bool	CachedHashCodes = base::Element::CachedHashCodes
	TMP constant that denotes whether hash codes are cached or not.

Public Static Method Index:
static constexpr bool	IsCachingHashes ()
static constexpr bool	IsRecycling ()
static constexpr Recycling	RecyclingTag ()

Public Method Index:
	HashTable (AllocatorType &pAllocator, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)
template<typename TSharedRecycler = SharedRecyclerType, ATMP_T_IF(int, !ATMP_EQ(TSharedRecycler, void)) = 0>
	HashTable (AllocatorType &pAllocator, TSharedRecycler &pSharedRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)
	HashTable (float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)
template<typename TSharedRecycler = SharedRecyclerType, ATMP_T_IF(int, !ATMP_EQ(TSharedRecycler, void)) = 0>
	HashTable (TSharedRecycler &pSharedRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)
AllocatorType &	GetAllocator () noexcept
Size and Capacity
void	Clear ()
void	Reset ()
integer	Size () const noexcept
bool	IsEmpty () const noexcept
void	Reserve (integer qty, lang::ValueReference reference)
void	ReserveRecyclables (integer qty, lang::ValueReference reference)
integer	RecyclablesCount () const noexcept
Hash Policy
void	BaseLoadFactor (float newBaseLoadFactor) noexcept
float	BaseLoadFactor () const noexcept
void	MaxLoadFactor (float newMaxLoadFactor) noexcept
float	MaxLoadFactor () const noexcept
Bucket Interface
uinteger	BucketCount () const noexcept
uinteger	BucketSize (uinteger bucketNumber) const noexcept
uinteger	BucketNumber (const KeyType &key) const noexcept
Element Insertion
Iterator	Insert (const StoredType &value)
Iterator	Insert (const StoredType &value, size_t hashCode)
Iterator	Insert (StoredType &&value)
Iterator	Insert (StoredType &&value, size_t hashCode)
Iterator	Insert (ElementHandle &handle)
Iterator	InsertUnique (const StoredType &value)
Iterator	InsertUnique (const StoredType &value, size_t hashCode)
Iterator	InsertUnique (StoredType &&value)
Iterator	InsertUnique (StoredType &&value, size_t hashCode)
template<typename TEnableIf = MappedType>
	InsertOrAssign (const KeyType &key, const MappedType &mapped)
template<typename TEnableIf = MappedType>
	InsertOrAssign (const KeyType &key, MappedType &&mapped)
template<typename TEnableIf = MappedType>
	InsertOrAssign (const KeyType &key, MappedType &&mapped, size_t hashCode)
template<typename TEnableIf = MappedType>
	InsertIfNotExistent (const KeyType &key, const MappedType &mapped)
template<typename TEnableIf = MappedType>
	InsertIfNotExistent (const KeyType &key, MappedType &&mapped, size_t hashCode)
template<typename TEnableIf = MappedType>
	InsertIfNotExistent (const KeyType &key, MappedType &&mapped)
std::pair< Iterator, bool >	InsertIfNotExistent (const StoredType &value)
std::pair< Iterator, bool >	InsertIfNotExistent (StoredType &&value)
std::pair< Iterator, bool >	InsertIfNotExistent (StoredType &&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 = MappedType, typename... TArgs>
std::pair< Iterator, bool >	EmplaceOrAssign (const KeyType &key, TArgs &&... args)
template<typename TEnableIf = MappedType, 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

Protected Type Index:
using	recyclerType = typename base::recyclerType
	The recycler type.
Protected Type Index: inherited from HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >
using	base
	Our base type.
using	Element = typename HTElementSelector<TValueDescriptor, THashCaching>::Type
	The type stored in the bucket of class HashTable.
using	FwdList = lang::SidiListHook<Element>
	Type of a single linked node list.
using	Node = lang::SidiNodeBase<Element>
	Type of a node in the List.
using	recyclerType
	Type of a single linked node list.
using	SharedRecyclerType
using	T = typename TValueDescriptor::StoredType
	Type definition publishing template parameter T.
using	TKey = typename TValueDescriptor::KeyType
	Type definition publishing template parameter TKey.
using	TMapped = typename TValueDescriptor::MappedType
	Type definition publishing template parameter TKey.

Additional Inherited Members
Protected Static Method Index: inherited from HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >
static size_t	getHashCode (Element *elem)
static constexpr bool	IsCachingHashes ()
Protected Field Index: inherited from HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >
float	baseLoadFactor
	The load factor that is set when the table is rehashed automatically.
uinteger	bucketCount
	The number of buckets managed by this tree.
FwdList *	buckets
	The list of buckets.
float	maxLoadFactor
	The maximum quotient of size and bucketCount that triggers a rehash.
integer	size
	The number of elements stored.
integer	sizeLimitToRehash
	Calculated once with rehash. Product of maxLoadFactor and bucketCount.
Protected Method Index: inherited from HashTableBase< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >
	HashTableBase (float pBaseLoadFactor, float pMaxLoadFactor)
	HashTableBase (TAllocator &pAllocator, float pBaseLoadFactor, float pMaxLoadFactor)
template<typename TSharedRecycler = SharedRecyclerType, ATMP_T_IF(int, !ATMP_EQ(TSharedRecycler, void)) = 0>
	HashTableBase (TSharedRecycler &pSharedRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)
	~HashTableBase ()
Element *	allocElement (const size_t hashCode)
bool	areEqual (Element *elem, const TKey &key, size_t keyHashCode) const
bool	areEqual (Element *lhs, Element *rhs) const
void	clear ()
	Destructs and removes all entries from this hash table.
Element *	findElement (uinteger bucketIdx, const TKey &key, size_t keyHashCode) const
Node *	findElementBefore (uinteger bucketIdx, size_t keyHashCode, const TKey &key) const
std::pair< TIterator< T >, TIterator< T > >	findRange (const TKey &key)
size_t	increaseSize (integer increase, const size_t hashCode=0)
std::pair< TIterator< T >, bool >	insertIfNotExists (const TKey &key, size_t hashCode)
uinteger	insertInBucket (Element *element, const size_t hashCode)
std::pair< TIterator< T >, bool >	insertOrGet (const TKey &key, size_t hashCode)
void	rehash (uinteger newMinBucketCount)
void	setMaxLoadFactor (float pMaxLoadFactor)

Type Definition Details:

AllocatorType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

using AllocatorType = TAllocator

Type definition publishing template parameter TAllocator.

Definition at line 490 of file hashtable.hpp.

ConstIterator

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

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

The constant iterator exposed by this container.

Definition at line 544 of file hashtable.hpp.

ConstLocalIterator

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

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

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

Definition at line 550 of file hashtable.hpp.

DescriptorType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

using DescriptorType = TValueDescriptor

Type definition publishing template parameter TValueDescriptor.

Definition at line 493 of file hashtable.hpp.

EqualType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

using EqualType = TEqual

Type definition publishing template parameter TEqual.

Definition at line 511 of file hashtable.hpp.

HashType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

using HashType = THash

Type definition publishing template parameter THash.

Definition at line 508 of file hashtable.hpp.

Iterator

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

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

The mutable iterator exposed by this container.

Definition at line 541 of file hashtable.hpp.

KeyType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

using KeyType = typename TValueDescriptor::KeyType

Type definition publishing the key type of this container as defined with template parameter TValueDescriptor.

Definition at line 501 of file hashtable.hpp.

LocalIterator

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

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

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

Definition at line 547 of file hashtable.hpp.

MappedType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

using MappedType = typename TValueDescriptor::MappedType

Type definition publishing the map type of this container as defined with template parameter TValueDescriptor.

Definition at line 505 of file hashtable.hpp.

recyclerType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

using recyclerType = typename base::recyclerType

protected

The recycler type.

Definition at line 481 of file hashtable.hpp.

SharedRecyclerType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

using SharedRecyclerType = typename base::SharedRecyclerType

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

See also

Chapter 4.3 Shared Recycling of the Programmer's Manual for this ALib Module.

Definition at line 529 of file hashtable.hpp.

StoredType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

using StoredType = typename TValueDescriptor::StoredType

Type definition publishing the stored type of this container as defined with template parameter TValueDescriptor.

Definition at line 497 of file hashtable.hpp.

Field Details:

CachedHashCodes

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

bool CachedHashCodes = base::Element::CachedHashCodes

staticconstexpr

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

Definition at line 538 of file hashtable.hpp.

Constructor(s) / Destructor Details:

HashTable() [1/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

HashTable ( AllocatorType & pAllocator, float pBaseLoadFactor = 1.0, float pMaxLoadFactor = 2.0 )

inlineexplicit

Constructor.

Note

This constructor is not available if the template argument TRecycling equals Shared.

Parameters

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

HashTable() [2/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

HashTable ( float pBaseLoadFactor = 1.0, float pMaxLoadFactor = 2.0 )

inlineexplicit

Constructor.

Note

This constructor is not available if the template argument TRecycling equals Shared and the if template argument TAllocator does not equal HeapAllocator

Parameters

pBaseLoadFactor	The base load factor. Defaults to 1.0.
pMaxLoadFactor	The maximum load factor. Defaults to 2.0.

HashTable() [3/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

template<typename TSharedRecycler = SharedRecyclerType, ATMP_T_IF(int, !ATMP_EQ(TSharedRecycler, void)) = 0>

HashTable ( AllocatorType & pAllocator, TSharedRecycler & pSharedRecycler, float pBaseLoadFactor = 1.0, float pMaxLoadFactor = 2.0 )

inline

Constructor taking a shared recycler.

Parameters

pAllocator	The allocator to use.
pSharedRecycler	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 715 of file hashtable.hpp.

HashTable() [4/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

template<typename TSharedRecycler = SharedRecyclerType, ATMP_T_IF(int, !ATMP_EQ(TSharedRecycler, void)) = 0>

HashTable ( TSharedRecycler & pSharedRecycler, float pBaseLoadFactor = 1.0, float pMaxLoadFactor = 2.0 )

inline

Constructor taking a shared recycler.

Parameters

pSharedRecycler	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 735 of file hashtable.hpp.

Method Details:

BaseLoadFactor() [1/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

float BaseLoadFactor ( ) const

inlinenoexcept

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 899 of file hashtable.hpp.

BaseLoadFactor() [2/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

void BaseLoadFactor ( float newBaseLoadFactor )

inlinenoexcept

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 887 of file hashtable.hpp.

begin() [1/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2233 of file hashtable.hpp.

begin() [2/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2242 of file hashtable.hpp.

begin() [3/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2262 of file hashtable.hpp.

begin() [4/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2286 of file hashtable.hpp.

BucketCount()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

uinteger BucketCount ( ) const

inlinenoexcept

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

Returns

The size of the array of hash buckets.

Definition at line 947 of file hashtable.hpp.

BucketNumber()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

uinteger BucketNumber ( const KeyType & key ) const

inlinenoexcept

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 971 of file hashtable.hpp.

BucketSize()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

uinteger BucketSize ( uinteger bucketNumber ) const

inlinenoexcept

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 956 of file hashtable.hpp.

cbegin() [1/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2251 of file hashtable.hpp.

cbegin() [2/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2310 of file hashtable.hpp.

cend() [1/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2255 of file hashtable.hpp.

cend() [2/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2323 of file hashtable.hpp.

Clear()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 764 of file hashtable.hpp.

Contains()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 1865 of file hashtable.hpp.

Emplace()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 the constructor of the inserted instance of type StoredType.

Returns

An iterator referring to the element added.

Definition at line 1483 of file hashtable.hpp.

EmplaceIfNotExistent() [1/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 preventing 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 StoredType as a key type TKey and whose stored type 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 the 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 TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

template<typename TEnableIf = MappedType, 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 preventing 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 StoredType 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 StoredType 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 StoredType as a key type TKey and whose stored type 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 the constructor of StoredType.

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 TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

template<typename TEnableIf = MappedType, 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 preventing 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 StoredType as a key type TKey and whose stored type StoredType 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 the 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 TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 the 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 1529 of file hashtable.hpp.

end() [1/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2237 of file hashtable.hpp.

end() [2/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2246 of file hashtable.hpp.

end() [3/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2275 of file hashtable.hpp.

end() [4/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2299 of file hashtable.hpp.

EqualRange() [1/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 1881 of file hashtable.hpp.

EqualRange() [2/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 1893 of file hashtable.hpp.

Erase() [1/6]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 1983 of file hashtable.hpp.

Here is the call graph for this function:

Erase() [2/6]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

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 1997 of file hashtable.hpp.

Here is the call graph for this function:

Erase() [3/6]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2077 of file hashtable.hpp.

Here is the call graph for this function:

Erase() [4/6]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2113 of file hashtable.hpp.

Here is the call graph for this function:

Erase() [5/6]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2181 of file hashtable.hpp.

Erase() [6/6]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 last removed element.

Definition at line 2208 of file hashtable.hpp.

Here is the call graph for this function:

EraseUnique() [1/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 2033 of file hashtable.hpp.

Here is the call graph for this function:

EraseUnique() [2/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

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 2048 of file hashtable.hpp.

Extract() [1/3]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 an 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 1914 of file hashtable.hpp.

Here is the call graph for this function:

Extract() [2/3]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

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 1931 of file hashtable.hpp.

Extract() [3/3]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 1961 of file hashtable.hpp.

Here is the call graph for this function:

Find() [1/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 ensured 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 1799 of file hashtable.hpp.

Find() [2/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 1813 of file hashtable.hpp.

Find() [3/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

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.

Find() [4/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

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 1852 of file hashtable.hpp.

GetAllocator()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

AllocatorType & GetAllocator ( )

inlinenoexcept

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 752 of file hashtable.hpp.

Insert() [1/5]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

Iterator Insert ( const StoredType & value )

inline

See Insert(StoredType&&) 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 983 of file hashtable.hpp.

Here is the call graph for this function:

Insert() [2/5]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

Iterator Insert ( const StoredType & value, size_t hashCode )

inline

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

See also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

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 997 of file hashtable.hpp.

Here is the call graph for this function:

Insert() [3/5]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 1066 of file hashtable.hpp.

Here is the call graph for this function:

Insert() [4/5]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

Iterator Insert ( StoredType && 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

A rvalue reference of contained type StoredType to insert.

Returns

An iterator referring to the element added.

Definition at line 1014 of file hashtable.hpp.

Here is the call graph for this function:

Insert() [5/5]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

Iterator Insert ( StoredType && value, size_t hashCode )

inline

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

See also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

Parameters

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

Returns

An iterator referring to the element added.

Definition at line 1031 of file hashtable.hpp.

InsertIfNotExistent() [1/7]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

template<typename TEnableIf = MappedType>

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 1283 of file hashtable.hpp.

Here is the call graph for this function:

InsertIfNotExistent() [2/7]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

template<typename TEnableIf = MappedType>

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 preventing 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 1351 of file hashtable.hpp.

Here is the call graph for this function:

InsertIfNotExistent() [3/7]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

template<typename TEnableIf = MappedType>

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.

Availability

This method is only available with hash map mode.

See also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

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 1309 of file hashtable.hpp.

InsertIfNotExistent() [4/7]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

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

inline

See InsertIfNotExistent(StoredType&&) 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 1362 of file hashtable.hpp.

Here is the call graph for this function:

InsertIfNotExistent() [5/7]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling 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 preventing 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 1444 of file hashtable.hpp.

Here is the call graph for this function:

InsertIfNotExistent() [6/7]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

std::pair< Iterator, bool > InsertIfNotExistent ( StoredType && 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 preventing 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 StoredType 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 1381 of file hashtable.hpp.

Here is the call graph for this function:

InsertIfNotExistent() [7/7]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

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

inline

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

See also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

Parameters

value	A rvalue reference of a StoredType 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 1402 of file hashtable.hpp.

InsertOrAssign() [1/3]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

template<typename TEnableIf = MappedType>

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 1195 of file hashtable.hpp.

Here is the call graph for this function:

InsertOrAssign() [2/3]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

template<typename TEnableIf = MappedType>

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

inline

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

Note

This method allows preventing 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 1221 of file hashtable.hpp.

Here is the call graph for this function:

InsertOrAssign() [3/3]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

template<typename TEnableIf = MappedType>

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

inline

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

See also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

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 1247 of file hashtable.hpp.

Here is the call graph for this function:

InsertUnique() [1/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

Iterator InsertUnique ( const StoredType & value )

inline

See InsertUnique(StoredType&&) 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 1087 of file hashtable.hpp.

Here is the call graph for this function:

InsertUnique() [2/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

Iterator InsertUnique ( const StoredType & value, size_t hashCode )

inline

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

See also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

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 1103 of file hashtable.hpp.

Here is the call graph for this function:

InsertUnique() [3/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

Iterator InsertUnique ( StoredType && 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 1132 of file hashtable.hpp.

Here is the call graph for this function:

InsertUnique() [4/4]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

Iterator InsertUnique ( StoredType && value, size_t hashCode )

inline

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

See also

Use cases of this method are discussed in reference documentation section 6.2 Hash Code Pre-calculation.

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 1150 of file hashtable.hpp.

Here is the call graph for this function:

IsCachingHashes()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

static constexpr bool IsCachingHashes ( )

inlinestaticconstexpr

Determines whether hash codes are stored with the elements. It is done in case the given template parameter THashCashing equals Caching::Enabled or if it equals Caching::Auto and the KeyType type is an arithmetic type.

Returns

true if hash codes are stored for reuse, false if not.

Definition at line 518 of file hashtable.hpp.

IsEmpty()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

bool IsEmpty ( ) const

inlinenoexcept

Invokes Size and compares result with 0.

Returns

true if this list is empty, false otherwise.

Definition at line 806 of file hashtable.hpp.

IsRecycling()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

static constexpr bool IsRecycling ( )

inlinestaticconstexpr

Determines whether the used recycler type is in fact recycling elements.

Returns

false if template parameter TRecycling equals None, true otherwise.

Definition at line 535 of file hashtable.hpp.

MaxLoadFactor() [1/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

float MaxLoadFactor ( ) const

inlinenoexcept

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 935 of file hashtable.hpp.

MaxLoadFactor() [2/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

void MaxLoadFactor ( float newMaxLoadFactor )

inlinenoexcept

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 923 of file hashtable.hpp.

RecyclablesCount()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

integer RecyclablesCount ( ) const

inlinenoexcept

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

Returns

The number of removed and not yet recycled elements.

Definition at line 859 of file hashtable.hpp.

RecyclingTag()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

static constexpr Recycling RecyclingTag ( )

inlinestaticconstexpr

Returns

The enum element value of template parameter TRecycling.

Definition at line 521 of file hashtable.hpp.

Reserve()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

void Reserve ( integer qty, 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

qty	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 816 of file hashtable.hpp.

Here is the call graph for this function:

ReserveRecyclables()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

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

inline

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

See also

Chapter 4.5 Reserving Capacity of the Programmer's Manual.

Parameters

qty	The expected resulting number (or increase) of elements to be stored in this container.
reference	Denotes whether qty is meant as an absolute size or an increase.

Definition at line 835 of file hashtable.hpp.

Here is the call graph for this function:

Reset()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

void Reset ( )

inline

Same as clear, but does not recycle internal nodes. Furthermore, all recyclables are deleted. The latter is done only if template parameter TRecycling is not Shared. In this case, the elements are still recycled.

This method is useful with monotonic allocators, that can be reset as well, after this instance is reset. But, because the life-cycle of the monotonic allocator(s) used for insertions is not under control of this object, it is the obligation of the caller to ensure that the monotonic allocator is kept in sync with this object. The following recipe shows a valid use:

• Construct a HashTable passing a MonoAllocator.
• Create a snapshot of the MonoAllocator.
• Use the HashTable.
• Reset the HashTable and right afterwards the MonoAllocator to the snapeshot taken.

Definition at line 782 of file hashtable.hpp.

Here is the call graph for this function:

Size()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>

integer Size ( ) const

inlinenoexcept

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 799 of file hashtable.hpp.

---

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

• hashtablebase.inl
• hashtable.hpp