ALib C++ Library
Library Version: 2510 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
alib::containers Namespace Reference

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, integerDbgGetHashTableDistribution (const THashtable &hashtable)
 

Variable Index:

uinteger DBG_STATS_STRINGTREE_NAME_OVERFLOWS = 0
 
uinteger DBG_STATS_STRINGTREE_NAMES = 0
 

Type Definition Details:

◆ FixedSizePriorityQueue

template<typename T, std::size_t TSize, typename TCompare = std::less<T>>
using alib::containers::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 91 of file fixedcapacityvector.inl.

◆ 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 alib::containers::HashMap
Initial value:

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
TAllocatorThe allocator type to use, as prototyped with Allocator.
TKeyThe type of the key-portion of the inserted data.
This type is published as HashTable::KeyType.
TMappedThe type of the mapped-portion of the inserted data.
This type is published as HashTable::MappedType.
THashThe hash functor applicable to TKey.
Defaults to std::hash<TKey> and is published as HashTable::HashType.
TEqualThe comparison functor on TKey.
Defaults to std::equal_to<TKey> and is published as HashTable::EqualType.
THashCachingDetermines 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.
TRecyclingDenotes the type of recycling that is to be performed. Possible values are None, Private (the default), or Shared.

Definition at line 2423 of file hashtable.inl.

◆ 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 alib::containers::HashSet
Initial value:
HashTable< TAllocator,
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
TAllocatorThe allocator type to use, as prototyped with Allocator.
TThe element type stored with this container. This type is published as HashTable::StoredType and type definition HashTable::KeyType becomes a synonym.
THashThe hash functor applicable to T.
Defaults to std::hash<T> and is published as HashTable::HashType.
TEqualThe comparison functor on T.
Defaults to std::equal_to<T> and is published as HashTable::EqualType.
THashCachingDetermines 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.
TRecyclingDenotes the type of recycling that is to be performed. Possible values are None, Private (the default), or Shared.

Definition at line 2376 of file hashtable.inl.

◆ LRUCacheMap

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

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
TAllocatorThe allocator type to use, as prototyped with Allocator.
TKeyThe type of the key-portion of the inserted data.
This type is published as LRUCacheTable::KeyType.
TMappedThe type of the mapped-portion of the inserted data.
This type is published as LRUCacheTable::MappedType.
THashThe hash functor applicable to TKey.
Defaults to std::hash<TKey> and is published as LRUCacheTable::HashType.
TEqualThe comparison functor on TKey.
Defaults to std::equal_to<TKey> and is published as LRUCacheTable::EqualType.

Definition at line 645 of file lrucachetable.inl.

◆ LRUCacheSet

template<typename TAllocator, typename T, typename THash = std::hash <T>, typename TEqual = std::equal_to<T>>
using alib::containers::LRUCacheSet
Initial value:
LRUCacheTable< TAllocator,
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
TAllocatorThe allocator type to use, as prototyped with Allocator.
TThe element type stored with this container. This type is published as LRUCacheTable::StoredType and type definition LRUCacheTable::KeyType becomes a synonym.
THashThe hash functor applicable to T. If void is given, no hashing is performed.
Defaults to std::hash<T> and is published as LRUCacheTable::HashType.
TEqualThe comparison functor on TKey.
Defaults to std::equal_to<TKey> and is published as LRUCacheTable::EqualType.

Definition at line 681 of file lrucachetable.inl.

Enumeration Details:

◆ Recycling

enum class alib::containers::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 24 of file recycling.inl.

Function Details:

◆ DbgDumpDistribution()

template<typename THashtable>
AString alib::containers::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
This function is an extension, which is injected by the higher-level module ALib Format and is accessed through the header file ALib.Format.H.
See also
Sibling namespace functions DbgGetHashTableDistribution and DbgDumpHashtable provided for debugging and optimization.
Template Parameters
THashtableA specification of templated type HashTable. Deduced by the compiler by given parameter hashtable.
Parameters
hashtableThe hashtable to investigate on.
detailedBucketListIf 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 36 of file containers_hashtable.inl.

Here is the call graph for this function:

◆ DbgDumpHashtable()

template<typename THashtable>
AString alib::containers::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 AppendableTraits 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
This function is an extension, which is injected by the higher-level module ALib Format and is accessed through the header file ALib.Format.H.
See also
Sibling namespace functions DbgGetHashTableDistribution and DbgDumpDistribution provided for debugging and optimization.
Template Parameters
THashtableA specification of templated type HashTable. Deduced by the compiler by given parameter hashtable.
Parameters
hashtableThe hashtable to investigate on.
Returns
A string containing a dump of the given hash table's contents.

Definition at line 123 of file containers_hashtable.inl.

◆ DbgGetHashTableDistribution()

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

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

  1. The expected average size of a bucket (simply table size divided by number of buckets).
  2. 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.
  3. The minimum number of elements found in a bucket.
  4. The maximum number of elements found in a bucket.
Availability
Available only if the compiler-symbol ALIB_DEBUG_CONTAINERS is set.
See also
Sibling namespace functions DbgDumpDistribution and DbgDumpHashtable provided for debugging and optimization.
Template Parameters
THashtableA specification of templated type HashTable. Deduced by the compiler by given parameter hashtable.
Parameters
hashtableThe hashtable to investigate on.
Returns
The tuple as described above.

Definition at line 2301 of file hashtable.inl.

Variable Details:

◆ DBG_STATS_STRINGTREE_NAME_OVERFLOWS

ALIB_DLL uinteger alib::containers::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 29 of file stringtreebase.cpp.

◆ DBG_STATS_STRINGTREE_NAMES

ALIB_DLL uinteger alib::containers::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 28 of file stringtreebase.cpp.