Description:

This is the reference documentation of namespace alib::containers, which holds types of module ALib Containers, which in turn is part of the ALib C++ Library.

Extensive documentation for this module is provided with the Programmer's Manual of this module.

Nested Namespaces:
namespace	detail
	Detail namespace of module ALib Containers.

Type Index:
class	FixedCapacityVector

class	HashTable

class	List

class	LRUCacheTable

class	SharedPtr

class	SharedVal

class	StringTree

struct	StringTreeNamesAlloc

struct	StringTreeNamesDynamic

struct	StringTreeNamesStatic

struct	TIdentDescriptor

struct	TPairDescriptor

struct	TSubsetKeyDescriptor

Type Definition Index:
template<typename T , std::size_t TSize, typename TCompare = std::less<T>>
using	FixedSizePriorityQueue = std::priority_queue< T, FixedCapacityVector<T, TSize>, TCompare>

template<typename TAllocator , typename TKey , typename TMapped , typename THash = std::hash <TKey>, typename TEqual = std::equal_to<TKey>, lang::Caching THashCaching = lang::Caching::Auto, Recycling TRecycling = Recycling::Private>
using	HashMap

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

template<typename TAllocator , typename TKey , typename TMapped , typename THash = std::hash <TKey>, typename TEqual = std::equal_to<TKey>>
using	LRUCacheMap

template<typename TAllocator , typename T , typename THash = std::hash <T>, typename TEqual = std::equal_to<T>>
using	LRUCacheSet

Enumeration Index:
enum class	Recycling { None , Private , Shared }

Function Index:
template<typename THashtable >
AString	DbgDumpDistribution (const THashtable &hashtable, bool detailedBucketList)

template<typename THashtable >
AString	DbgDumpHashtable (const THashtable &hashtable)

template<typename THashtable >
std::tuple< double, double, integer, integer >	DbgGetHashTableDistribution (const THashtable &hashtable)

Variable Index:
ALIB_API uinteger	DBG_STATS_STRINGTREE_NAME_OVERFLOWS = 0

ALIB_API uinteger	DBG_STATS_STRINGTREE_NAMES = 0

Type Definition Details:

◆ FixedSizePriorityQueue

template<typename T , std::size_t TSize, typename TCompare = std::less<T>>

using FixedSizePriorityQueue = std::priority_queue< T, FixedCapacityVector<T, TSize>, TCompare>

Type alias which denotes a std::priority_queue using a FixedCapacityVector as its underlying container type.

Definition at line 103 of file fixedcapacityvector.hpp.

◆ HashMap

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

using HashMap

Initial value:

 HashTable<TAllocator,
                         TPairDescriptor<TKey, TMapped>,
                         THash,TEqual,
                         THashCaching,
                         TRecycling                                           >

This type definition is a shortcut to HashTable, usable if data stored in the container does not include a key-portion, and thus the key to the data is to be separately defined.
To achieve this, this type definition aggregates types TKey and TMapped into a std::pair<TKey,TMapped>. This is done using special value descriptor type TPairDescriptor.

See also: For a detailed description of this type, see original type HashTable, as well as alternative type definition HashSet.

Template Parameters

TAllocator	The allocator type to use, as prototyped with Allocator.
TKey	The type of the key-portion of the inserted data. This type is published as HashTable::KeyType.
TMapped	The type of the mapped-portion of the inserted data. This type is published as HashTable::MappedType.
THash	The hash functor applicable to TKey. Defaults to `std::hash<TKey>` and is published as HashTable::HashType.
TEqual	The comparison functor on TKey. Defaults to `std::equal_to<TKey>` 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 None, Private (the default), or Shared.

Definition at line 2632 of file hashtable.hpp.

◆ HashSet

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

using HashSet

Initial value:

 HashTable< TAllocator,
                          TIdentDescriptor<T>,
                          THash, TEqual,
                          THashCaching,
                          TRecycling                  >

This type definition is a shortcut to HashTable, usable if the full portion of the data stored in the container is used for the comparison of values.

Note: As with this definition template type TKey equals stored type StoredType, methods of target type HashTable that accept an object of template type TKey expect an object of StoredType when this type is used.
In case this is not wanted (or possible), and only the true key-portion should be expected by interface functions such as HashTable::Find, the original type has to be used. Here, typically template parameter TValueDescriptor can be set to TSubsetKeyDescriptor.

See also: For a detailed description of this type, see original type HashTable, as well as alternative type definition HashMap.

Template Parameters

TAllocator	The allocator type to use, as prototyped with Allocator.
T	The element type stored with this container. This type is published as HashTable::StoredType and type definition HashTable::KeyType becomes a synonym.
THash	The hash functor applicable to T. Defaults to `std::hash<T>` and is published as HashTable::HashType.
TEqual	The comparison functor on T. Defaults to `std::equal_to<T>` 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<StoredType>::value` evaluates to `false`.
TRecycling	Denotes the type of recycling that is to be performed. Possible values are None, Private (the default), or Shared.

Definition at line 2585 of file hashtable.hpp.

◆ LRUCacheMap

template<typename TAllocator , typename TKey , typename TMapped , typename THash = std::hash <TKey>, typename TEqual = std::equal_to<TKey>>

using LRUCacheMap

Initial value:

 LRUCacheTable< TAllocator,
                                      containers::TPairDescriptor<TKey, TMapped>,
                                      THash, TEqual >

This type definition is a shortcut to LRUCacheTable, usable if data stored in the container does not include a key-portion, and thus the key to the data retrievable from the cache has to be separately defined.
To achieve this, this type definition aggregates types TKey and TMapped into a std::pair<TKey,TMapped>. This is done using special value descriptor type TPairDescriptor.

See also: For a detailed description of this type, see original type LRUCacheTable, as well as alternative type definition LRUCacheSet.

Template Parameters

TAllocator	The allocator type to use, as prototyped with Allocator.
TKey	The type of the key-portion of the inserted data. This type is published as LRUCacheTable::KeyType.
TMapped	The type of the mapped-portion of the inserted data. This type is published as LRUCacheTable::MappedType.
THash	The hash functor applicable to TKey. Defaults to `std::hash<TKey>` and is published as LRUCacheTable::HashType.
TEqual	The comparison functor on TKey. Defaults to `std::equal_to<TKey>` and is published as LRUCacheTable::EqualType.

Definition at line 671 of file lrucachetable.hpp.

◆ LRUCacheSet

template<typename TAllocator , typename T , typename THash = std::hash <T>, typename TEqual = std::equal_to<T>>

using LRUCacheSet

Initial value:

 LRUCacheTable< TAllocator,
                                      TIdentDescriptor<T>,
                                      THash, TEqual        >

This type definition is a shortcut to LRUCacheTable, usable if the full portion of the data stored in the container is used for the comparison of values.

Note: As with this definition template type TKey equals stored type T, methods of target type LRUCacheTable that accept an object of template type TKey expect an object of T when this type type defintion is used.
In case this is not wanted (or possible), and only the true key-portion should be expected by interface functions such as LRUCacheTable::Try, the underlying original type LRUCacheTable) has to be used.

See also: For a detailed description of this type, see original type LRUCacheTable, as well as alternative type definition LRUCacheMap.

Template Parameters

TAllocator	The allocator type to use, as prototyped with Allocator.
T	The element type stored with this container. This type is published as LRUCacheTable::StoredType and type definition LRUCacheTable::KeyType becomes a synonym.
THash	The hash functor applicable to T. If `void` is given, no hashing is performed. Defaults to `std::hash<T>` and is published as LRUCacheTable::HashType.
TEqual	The comparison functor on TKey. Defaults to `std::equal_to<TKey>` and is published as LRUCacheTable::EqualType.

Definition at line 707 of file lrucachetable.hpp.

Enumeration Details:

◆ Recycling

enum class Recycling

strong

This enumeration contains three elements, which denote the type of node-recycling that a container instantiation is deemed to perform. One of these elements is to be set as the value for a corresponding template parameter named TRecycling found in container types of this module.

In the case Shared is given, the container type will expose a type definition named SharedRecyclerType, which can be used to define the external shared recycler object. This object has then to be passed to the constructor of the container instance.

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

Enumerator
None	< Denotes that no recycling should be performed.
Private	< Denotes private recycling. This is usaully the default value.
Shared	< Denotes shared recycling.

Definition at line 31 of file recycling.hpp.

Function Details:

◆ DbgDumpDistribution()

template<typename THashtable >

AString DbgDumpDistribution	(	const THashtable &	hashtable,
		bool	detailedBucketList )

inline

Invokes method DbgGetHashTableDistribution and creates human-readable output, ready to be logged or written to the console.

Availability: Available only if compiler symbol ALIB_DEBUG_CONTAINERS is set and module ALib BaseCamp is included in the alibdist.

See also: Sibling namespace functions DbgGetHashTableDistribution and DbgDumpHashtable provided for debugging and optimization.

Template Parameters

THashtable A specification of templated type HashTable. Deduced by the compiler by given parameter hashtable.

Parameters

hashtable	The hashtable to investigate on.
detailedBucketList	If `true` is given, for each bucket a line with its size value and a "size bar" is written.

Returns: A string containing human-readable information about the distribution of elements in the hashtable.

Definition at line 2418 of file hashtable.hpp.

Here is the call graph for this function:

◆ DbgDumpHashtable()

template<typename THashtable >

AString DbgDumpHashtable ( const THashtable & hashtable )

inline

Dumps all values of the hash table sorted by buckets. Besides other scenarios of usage, this method allows investigating into how the keys of the table are distributed in the buckets, and thus learn something about the hash algorithm used.

Before invoking this method, specializations of T_Append have to be made and furthermore, boxed values of the type have to be "made appendable" to instances of type AString. The latter is rather simple, if done using this macro during bootstrap.

Note: If the prerequisites for using this method seem to be too complicated and not worth the effort for a "quick debug session", it is recommended to just copy the source code of this inline function and adopt the Formatter::Format statement to suit a specific type stored in hashtable.

Availability: Available only if compiler symbol ALIB_DEBUG_CONTAINERS is set and module ALib BaseCamp is included in the alibdist.

See also: Sibling namespace functions DbgGetHashTableDistribution and DbgDumpDistribution provided for debugging and optimization.

Template Parameters

THashtable A specification of templated type HashTable. Deduced by the compiler by given parameter hashtable.

Parameters

hashtable The hashtable to investigate on.

Returns: A string containing a dump of the given hash table's contents.

Definition at line 2504 of file hashtable.hpp.

Here is the call graph for this function:

◆ DbgGetHashTableDistribution()

template<typename THashtable >

std::tuple< double, double, integer, integer > DbgGetHashTableDistribution ( const THashtable & hashtable )

inline

Generates statistics on the given hash table. The meanings of the returned tuple are:

The expected average size of a bucket (simply table size divided by number of buckets).
The standard deviation of the buckets. The lower this value, the better is the hash algorithm used. A value of 1.0 denotes the gaussian distribution which indicates perfect randomness. However, this value is unlikely (impossible) to be achieved.
The minimum number of elements found in a bucket.
The maximum number of elements found in a bucket.

Availability: Available only if compiler symbol ALIB_DEBUG_CONTAINERS is set.

See also: Sibling namespace functions DbgDumpDistribution and DbgDumpHashtable provided for debugging and optimization.

Template Parameters

THashtable A specification of templated type HashTable. Deduced by the compiler by given parameter hashtable.

Parameters

hashtable The hashtable to investigate on.

Returns: The tuple as described above.

Definition at line 2363 of file hashtable.hpp.

Variable Details:

◆ DBG_STATS_STRINGTREE_NAME_OVERFLOWS

ALIB_API uinteger DBG_STATS_STRINGTREE_NAME_OVERFLOWS = 0

Statistic variable increased by StringTreeNamesDynamic with every creation of a node whose name exceeds the internal string buffer size. With process creation the variable is 0. A user may reset the variable to inspect percentages of name overflows during certain operations. The variable is not thread safe and used by any instance of class StringTree which uses node handler StringTreeNamesDynamic.

See also: Sibling variable DBG_STATS_STRINGTREE_NAME_OVERFLOWS

Definition at line 94 of file hashtablebase.cpp.

◆ DBG_STATS_STRINGTREE_NAMES

ALIB_API uinteger DBG_STATS_STRINGTREE_NAMES = 0

Statistic variable increased by StringTreeNamesDynamic with every creation of a node. With process creation the variable is 0. A user may reset the variable to inspect percentages of name overflows during certain operations. The variable is not thread safe and used by any instance of class StringTree which uses node handler StringTreeNamesDynamic.

See also: Sibling variable DBG_STATS_STRINGTREE_NAME_OVERFLOWS

Definition at line 93 of file hashtablebase.cpp.

Description:

Nested Namespaces:

Type Index:

Type Definition Index:

Enumeration Index:

Function Index:

Variable Index:

Type Definition Details:

◆ FixedSizePriorityQueue

◆ HashMap

◆ HashSet

◆ LRUCacheMap

◆ LRUCacheSet

Enumeration Details:

◆ Recycling

Function Details:

◆ DbgDumpDistribution()

◆ DbgDumpHashtable()

◆ DbgGetHashTableDistribution()

Variable Details:

◆ DBG_STATS_STRINGTREE_NAME_OVERFLOWS

◆ DBG_STATS_STRINGTREE_NAMES