ALib C++ Library
Library Version: 2510 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
hashtable.inl
Go to the documentation of this file.
1
2//==================================================================================================
3/// \file
4/// This header-file is part of module \alib_containers of the \aliblong.
5///
6/// \emoji :copyright: 2013-2025 A-Worx GmbH, Germany.
7/// Published under \ref mainpage_license "Boost Software License".
8//==================================================================================================
9ALIB_EXPORT namespace alib { namespace containers {
10//==================================================================================================
11/// # Contents #
12/// \ref alib_ns_containers_hashtable_intro "1. Introduction" <br>
13/// \ref alib_ns_containers_hashtable_setandmap "2. Hash Sets vs. Hash Maps" <br>
14/// \ref alib_ns_containers_hashtable_single_multi "3. Single And Multiple Entries" <br>
15/// \ref alib_ns_containers_hashtable_rehashing "4. Re-Hashing" <br>
16/// \ref alib_ns_containers_hashtable_iterators "5. Iterators" <br>
17/// \ref alib_ns_containers_hashtable_hashcodes "6. Hash Codes" <br>
18/// &nbsp;&nbsp;\ref alib_ns_containers_hashtable_caching "6.1 Caching Hash Codes" <br>
19/// &nbsp;&nbsp;\ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Codes Pre-calculation" <br>
20/// &nbsp;&nbsp;\ref alib_ns_containers_hashtable_hashquality "6.3 Hash Codes Pre-calculation" <br>
21/// \ref alib_ns_containers_hashtable_memory "7. Memory Use" <br>
22/// \ref alib_ns_containers_hashtable_comparison "8. Comparison To Standard Library Hash-Types" <br>
23/// \ref alib_ns_containers_hashtable_referencedoc "Reference Documentation" <br>
24///
25/// \I{#############################################################################################}
26/// \anchor alib_ns_containers_hashtable_intro
27/// # 1. Introduction #
28/// This class implements a \https{hash table,en.wikipedia.org/wiki/Hash_table} that
29/// stores and retrieves objects very efficiently in respect to execution performance.
30/// All memory for the hash table and its entries are allocated using a template
31/// \alib{lang;Allocator;allocator type}.
32///
33/// Two type definitions based on this class exist, which change the set of template parameters
34/// of this type by providing reasonable replacements. These types are:
35/// - \alib{containers;HashMap} and
36/// - \alib{containers;HashSet}.
37///
38/// In many cases, the use of one of these definitions is more convenient than instantiating this
39/// type directly. The meaning of these types is discussed in the next section.
40///
41/// \I{#############################################################################################}
42/// \anchor alib_ns_containers_hashtable_setandmap
43/// # 2. Hash Sets vs. Hash Maps#
44/// A <em>"hash set"</em> is commonly understood as a type that contains custom values of
45/// #StoredType, which are also used as the key to finding such stored objects.
46/// <em>"Hash maps"</em> are hash tables that store objects of a custom #MappedType which are
47/// associated to a value of a key #KeyType. In this "mode" the key is not contained in the custom
48/// value.<br>
49/// The template parameters and implementation of this class supports both concepts and they are
50/// covered by the two provided alternative type definitions mentioned in the previous section.
51/// Furthermore, those go along well with what is found in the standard C++ library:
52///
53/// 1. \alib{containers;HashSet}
54/// Removes template parameter \p{TValueDescriptor} (by presetting it to a built-in helper-type)
55/// and instead denotes all three types, namely #StoredType, #KeyType and #MappedType to the
56/// same new template parameter \p{T}.
57/// Functors \p{THash} and \p{TEqual} consequently expect the \b %StoredType.<br>
58///
59/// This type definition is similar to what types <c>std::unordered_set</c> and
60/// <c>std::unordered_multiset</c> of the standard C++ class library provide.
61///
62/// 2. \alib{containers;HashMap}
63/// Removes template parameter \p{TValueDescriptor} (by presetting it to a built-in helper-type)
64/// and instead introduces template parameters \p{TKey} and \p{TMapped}.
65/// Here, only the <em>key-portion</em> is used for calculating hash values and testing elements
66/// for equality. The <em>mapped-portion</em> is the true custom type that is to be stored. <br>
67/// Consequently, \b %HashMap defines the #StoredType as <c>std::pair<TKey, TMapped></c>.<br>
68///
69/// The type definition is similar to what types <c>std::unordered_map</c> and
70/// <c>std::unordered_multimap</c> of the standard C++ class library provide.
71///
72/// To achieve this flexibility, template parameter \p{TValueDescriptor}, which is exposed as
73/// #DescriptorType, is constrained to have two methods \b Key() and \b Mapped() to extract
74/// a reference to the corresponding portions out of the stored value.
75///
76/// One of the advantages of this approach is that this type supports a third "mode", besides
77/// implementing <em>"hash sets"</em> and <em>"hash maps"</em>: Custom value type #StoredType
78/// may have a <em>key-portion</em> embedded, instead of using the complete type as a search key.<br>
79/// While there is no specific type definition for this "key-embedded mode" available, the using
80/// code needs to create a custom version of template parameter \p{TValueDescriptor}
81/// which enables the extraction of the key and mapped portions of the stored type.
82/// The following table summarizes this:
83///
84/// Working Mode | Type to Use | Value Descriptor Type
85/// ---------------------------|-------------------------------------|-------------------------
86/// Hash Set |\alib{containers;HashSet} (A type definition on \b %HashTable) | Automaticly chosen as built-in \alib{containers;TIdentDescriptor}
87/// Hash Map |\alib{containers;HashMap} (A type definition on \b %HashTable) | Automaticly chosen as built-in \alib{containers;TPairDescriptor}
88/// Hash Set with embedded Key |\alib{containers;HashTable} (The original type) | A <b>custom type</b> has to be provided
89///
90/// \note The hash-table implementations of the standard C++ library do not support a similar
91/// approach. While with the provision of customized hash- and comparison-functors, of course
92/// only a portion of a type stored in a set can be used for hashing and comparing, still the
93/// interface functions require to receive a "complete" instance, which then is often
94/// "nulled" or "empty" in respect to the fields that are not used for the key.<br>
95/// Because of this limitation, \alib introduces template parameter \p{TValueDescriptor} in
96/// addition to parameters \p{THash} and \p{TEqual}.
97///
98///
99/// As a sample for the advantage consider method
100/// #EmplaceIfNotExistent(const KeyType& key, TArgs&&... args).
101/// A corresponding method is found with type <c>std::unordered_map::try_emplace</c>, but not
102/// with <c>std::unordered_set</c>. In contrast with this implementation, the method
103/// is usable with <em>hash maps</em> as well as with <em>hash sets</em>!<br>
104/// The only precondition to the availability of this method, is that the #StoredType has to be
105/// constructible from the combined list of given arguments, hence the \p{KeyType} argument along
106/// with given arguments of variadic template types \p{TArgs}.
107/// The same is true for method #EmplaceOrAssign(const KeyType&, TArgs&&... args)
108///
109///
110/// The set of available interface methods slightly changes with the two operation modes:
111/// 1. <b>Hash Set Mode:</b><br>
112/// Method overload #EmplaceIfNotExistent(TArgs&&... args) is exclusively available with hash
113/// sets.<br>
114///
115/// 2. <b>Hash Map Mode:</b><br>
116/// The following method overloads are exclusively available with hash \b maps:
117/// - #InsertOrAssign(const KeyType&, MappedType&&)
118/// - #InsertOrAssign(const KeyType&, const MappedType&)
119/// - #InsertIfNotExistent(const KeyType&, MappedType&&)
120/// - #InsertIfNotExistent(const KeyType&, const MappedType&)
121/// <br><br>
122///
123/// In addition, the following method overloads of inner types are also exclusively available
124/// with hash \b maps.
125/// - \alib{containers::detail::HashTableBase;TIterator::Mapped}
126/// - \alib{containers::detail::HashTableBase;TLocalIterator::Mapped}
127/// - \alib{containers::HashTable;ElementHandle::Mapped}
128///
129/// A hint to restrictions is given with the documentation of each method of concern.
130/// Note that methods that expect a single #KeyType are usable with both operation modes, because
131/// with hash sets the key-type equals type #StoredType.
132///
133/// \note
134/// Technically, the availability of the methods is selected at compile-time.
135///
136/// \I{#############################################################################################}
137/// \anchor alib_ns_containers_hashtable_single_multi
138/// # 3. Single And Multiple Entries #
139/// The standard C++ library differentiates between hashing containers that accept only one
140/// element with a specific <em>key-portion</em> of the value (see <c>std::unordered_set</c> and
141/// <c>std::unordered_map</c>) and those that accept multiple insertions of objects with the
142/// same <em>key-portion</em> (see <c>std::unordered_multiset</c> <c>std::unordered_multimap</c>).
143///
144/// This library does \b not provide separate types and any instantiation of this class allows
145/// multiple entries. But this is rather an extension of functionality, than a restriction
146/// and does not impose a penalty on performance.
147///
148/// If unique entries are to be achieved, the user of the type has to make sure for herself that
149/// no multiple entries are inserted. This can be guaranteed, with the exclusive use of the
150/// following set of (partly overloaded) methods, which prevent the creation of multiple entries:
151///
152/// - #InsertUnique / #EmplaceUnique
153/// - #InsertOrAssign / #EmplaceOrAssign
154/// - #InsertIfNotExistent / #EmplaceIfNotExistent
155///
156/// In contrast to this, methods #Insert and #Emplace (and their overloads) will insert
157/// an equal value without giving further notice (for example by providing a special return value
158/// that indicates if the inserted key existed before).<br>
159/// Method #EraseUnique(const KeyType&) is more efficient than #erase(const KeyType&)
160/// and a further advantage is that it asserts (in debug-compilations) that not more than one
161/// element is found in the table.
162///
163/// \note
164/// If uniqueness of key values is needed, it might be seen by the reader to be a "disadvantage"
165/// that the burden is on the user of the class to guarantee such uniqueness.
166/// However, such burden exists with the set-types of the standard library likewise:
167/// There, result values have to be evaluated to determine if an insertion was successful or not.
168/// The various smaller changes and extensions of the <c>std</c>-types with C++ 14 and 17 reflect
169/// the design problems of the approach to provide "unique" and "multi" types.
170///
171/// \note
172/// The approach that \alib takes here has three small benefits:
173/// 1. A user is free to choose a "mixed mode" by allowing duplicates of certain values (keys)
174/// and not allowing duplicates for others.
175/// While this can be achieved with <c>std::unordered_multimap/set</c> as well, a performance
176/// penalty is given, unless the extended interface of C++17 standard is used with great care.
177/// 2. The code is better readable, due to explicit naming of the invocations, in contrast
178/// to the need to knowing a container's type with each invocation.
179/// 3. The use of the type and this documentation is less confusing, because only one type exists.
180/// In contrast, the two types found in <c>std</c> have equally named methods that act
181/// differently and return different result types.
182///
183/// \I{#############################################################################################}
184/// \anchor alib_ns_containers_hashtable_rehashing
185/// # 4. Re-Hashing #
186/// A check for the need to perform re-hashing is made with every insertion of an element.
187/// The policy for re-hashing is described as follows:
188/// - With insertions, the new average bucket size is calculated as #Size divided by #BucketCount.
189/// - This value is compared with #MaxLoadFactor and if higher the number of buckets is increased.
190/// - When increased, the new minimum number of buckets is calculated as #Size divided by
191/// #BaseLoadFactor. Starting from this minimum, the effective number of buckets is chosen as a
192/// next higher prime number from a static table.
193/// - Automatic rehashes may be disabled by setting #MaxLoadFactor to a very high value, e.g.
194/// <c>std::numeric_limits<float>::max()</c>
195///
196/// The number of buckets is never decreased, unless method #Reset is invoked.
197///
198/// Manual re-hashing is not supported by design. In our view, with monotonic growth (or stability
199/// in size) and hence the absence of dynamic increase/decrease scenarios, manual rehashing is not
200/// needed. Only the base and maximum load factors are of concern, which both can be
201/// specified with \ref HashTable::HashTable "construction" and with methods #MaxLoadFactor
202/// respectively #MaxLoadFactor.<br>
203/// What can be done, however, is to use the method #MaxLoadFactor to "disable" rehashing
204/// temporarily and thus to allow an efficient mass insertion. Nevertheless, if the number of
205/// elements to be inserted is known upfront, the use of method #Reserve, respectively
206/// #ReserveRecyclables is the preferred approach.
207///
208/// \I{############################################################################################}
209/// \anchor alib_ns_containers_hashtable_iterators
210/// # 5. Iterators #
211/// ## 5.1 Iterator Types ##
212/// There are two types of iterators provided:
213/// - \alib{containers::HashTable;Iterator} and its constant sibling
214/// \alib{containers::HashTable;ConstIterator}, used to iterate over all elements of the
215/// hash table,
216/// - \alib{containers::HashTable;LocalIterator} and its constant sibling
217/// \alib{containers::HashTable;ConstLocalIterator} used to iterate over the elements
218/// of a certain bucket only.
219///
220/// Both types satisfy the C++ standard library concept
221/// \https{ForwardIterator,en.cppreference.com/w/cpp/named_req/ForwardIterator}.
222///
223/// ## 5.2 Validity Rules ##
224/// The following rules define the validity of existing iterator instances on table operations:
225/// - <b>Element \b Insertions:</b>
226/// - If no rehashing is performed (see previous section) all iterators remain valid.
227/// - If rehashing is performed, existing iterators become invalid in respect to allowance
228/// of increments and comparison. The elements that existing iterators referred to
229/// before the insertion remain valid. Consequently existing iterators may still be used
230/// to access the custom element value and modify the mapped portion of it.
231/// - <b>Element \b Removals:</b> <br>
232/// All existing iterators that referred to elements that have been removed become invalid.
233/// All others remain fully intact.<br>
234/// The order of the elements that are not erased is preserved, what makes it possible to
235/// erase individual elements while iterating through the container.
236///
237///
238///\I{#############################################################################################}
239/// \anchor alib_ns_containers_hashtable_hashcodes
240/// # 6. Hash Codes #
241///
242///\I{#############################################################################################}
243/// \anchor alib_ns_containers_hashtable_caching
244/// ## 6.1 Caching Hash Codes ##
245///
246/// Template parameter \p{THashCaching} may be used to control if hash codes are cached.
247/// Caching the hash codes increases the memory consumption of this class by <c>sizeof(size_t)</c>
248/// per inserted element. While this is only a small amount and memory consumption should not
249/// be a great concern when monotonic allocation is used, caching the hash codes may impose a
250/// reasonable performance impact. This impact depends on the performance of functor \p{THash}
251/// working on the <c>key-portion</c> of the inserted value.
252///
253/// The cached hash code is used when the table is
254/// \ref alib_ns_containers_hashtable_rehashing "re-hashed". In addition, the cached
255/// hash code is also used with almost all interface methods (insertion, deletion and search
256/// operations): If cached, any needed comparison of two elements will first compare the hash
257/// codes and only invoke templated functor \p{TEqual} if those match.
258///
259/// If template parameter \p{THashCaching} evaluates to <b>Caching::Auto</b> then this class
260/// defaults to use caching if type #KeyType is not arithmetic
261/// (using <c>std::is_arithmetic<TKey></c> for this check).<br>
262///
263/// The caching option of an instance of this class can be queried with enum #CachedHashCodes.
264///
265///
266///\I{#############################################################################################}
267/// \anchor alib_ns_containers_hashtable_hashprecalc
268/// ## 6.2 Hash Codes Pre-calculation ##
269/// The following overloaded methods accept parameter \p{hashCode} in addition to the parameters
270/// accepted by their corresponding base version:
271/// - #Find(const KeyType&, size_t)
272/// - #Insert(const T&, size_t)
273/// - #Insert(T&&, size_t)
274/// - #InsertUnique(T&&, size_t)
275/// - #InsertOrAssign(const KeyType&, MappedType&& mapped, size_t)
276/// - #InsertIfNotExistent(const KeyType&, MappedType&& mapped, size_t)
277/// - #InsertIfNotExistent(T&&, size_t )
278/// - #Extract(const KeyType&, size_t )
279/// - #Erase(const KeyType&, size_t )
280/// - #EraseUnique( const KeyType&, size_t )
281///
282/// The rationale for the provision of these methods is to allow to "pre-calculate" a key's hash
283/// code before invoking the method. This is efficient in situations where one or more subsequent
284/// operations with the same key are performed. For example:
285/// - Insertions of multiple objects with the same key.
286/// - Insertions of an object into multiple hash tables.
287/// - Situations where the result of a find operation may may lead to further operations with the
288/// same object.
289///
290///\I{#############################################################################################}
291/// \anchor alib_ns_containers_hashtable_hashquality
292/// ## 6.3 Hash Code Quality ##
293/// To have hash tables perform in constant time <em>O(1)</em> in the average case, a well
294/// implemented calculation of hash-codes has to be provided for template type \p{TKey} with
295/// template functor \p{THash}. This is an obligation of the user of this type.
296///
297/// This \alibmod_nl supports the compiler-symbol \ref ALIB_DEBUG_CONTAINERS which enables extra
298/// features.
299/// The entities relevant for this type are:
300/// - \alib{containers;DbgGetHashTableDistribution},
301/// - \alib{containers;DbgDumpDistribution} and
302/// - \alib{containers;DbgDumpHashtable}.
303///
304/// These methods may be used to assert the quality of custom hash algorithms.
305///
306///\I{#############################################################################################}
307/// \anchor alib_ns_containers_hashtable_memory
308/// # 7. Memory Use #
309/// With template parameter \p{TRecycling} being either \alib{containers;Recycling;Private}
310/// (the default) or \alib{containers;Recycling;Shared}, the internal
311/// <em>"node objects"</em> are remembered when deleted, and "recycled" with future insertions.
312/// The rationale for this lies in the simple fact that memory cannot be returned to
313/// the monotonic allocator. The recycling mechanism is very lightweight and does not cost measurable
314/// performance. If it is assured that no deletions are made during the life-cycle of an instance,
315/// type \alib{containers;Recycling;None} may be used to eliminate this little overhead
316/// of recycling. This is why type-definition \alib{MonoAllocator} is recommended to be used
317/// with this container.
318///
319/// If the table is re-hashed, the former bucket list is likewise recycled and sliced into as many
320/// internal node objects as possible. The precondition for this is that the allocator
321/// interface method \alib{lang::Allocator;allowsMemSplit} returns \c true. This is true for type
322/// \b MonoAllocator.
323///
324/// With these two mechanisms in place, the use of monotonic allocation with this container
325/// is very safe in respect to avoid memory exhaustion.
326/// The use of this class, even in scenarios where a lot of (theoretically an endless amount of)
327/// erase and insert operations are performed, will not increase memory consumption, as long it is
328/// guaranteed that the overall size of the table is limited.<br>
329///
330/// If a maximum number of possible insertions is known, method #ReserveRecyclables might be used
331/// to allocate all needed memory at once. With that, a
332/// \alib{containers;MonoAllocator::TakeSnapshot;snapshot} of the allocator can be taken and
333/// later used to reset the allocator to the minimum that preserves all memory in the according
334/// hash table instance.<br>
335/// For advanced usage, it is advisable to fully understand the concept of monotonic allocation
336/// implemented with this module \alib_containers.
337///
338/// \I{############################################################################################}
339/// \anchor alib_ns_containers_hashtable_comparison
340/// # 8. Comparison To Standard Library Hash-Types #
341/// In the previous sections, it was already referred several times to types
342/// - <c>std::unordered_map</c>,
343/// - <c>std::unordered_multimap,</c>
344/// - <c>std::unordered_set</c> and
345/// - <c>std::unordered_multiset</c>
346///
347/// of the C++ standard library. The uses cases and features of these four compared to this type are
348/// generally the same and this type can be used to replace the standard tyes without general
349/// limitations and vice versa.
350///
351/// Then with C++17, the standard library was extended by a new set of types, namely
352/// - <c>std::pmr::unordered_map</c>,
353/// - <c>std::pmr::unordered_multimap,</c>
354/// - <c>std::pmr::unordered_set</c> and
355/// - <c>std::pmr::unordered_multiset</c>
356///
357/// which, likewise this type, may use monotonic allocation (for example, in combination with C++17
358/// type <c>std::pmr::monotonic_buffer_resource</c>).
359/// On the one hand, \alib in the past needed support of monotonic allocation already for
360/// C++ 11, and on the other hand, the C++17 library extensions follow slightly different design
361/// goals. Details of these were given in the previous section.
362///
363/// Besides these general differences, the specific similarities and differences can be summarized
364/// as follows:
365///
366/// - This \alib type does not distinguish sets and maps but provides a more flexible approach:
367/// Mapped types do not necessarily need to be build using a <c>std::pair</c> of key and value
368/// elements.
369/// For convenience, when the use of <c>std::pair</c> is suitable, type definition
370/// \alib{containers;HashMap} offers exactly this.
371/// - This \alib type does not distinguish sets/maps from multi-sets/maps.
372/// The rationale for this design decision has been described in section
373/// \ref alib_ns_containers_hashtable_single_multi "3. Single And Multiple Entries".
374/// - Almost all members of the four standard library types are implemented with this type
375/// in a very compatible fashion. The member names were translated from <em>lower_snake_case</em>
376/// to <em>UpperCamelCase</em> and then sometimes slightly changed.<br>
377/// C++17 extensions of the standard types were reflected.
378/// - Method #Find provides additional overloads that accept an externally (pre-) calculated
379/// hash code. This allows efficiently using the same key with a series of searches within
380/// different hash table instances. Note that C++20 offers a templated version of <c>find</c>,
381/// which allows performing the same optimization.
382/// - Erase methods that accept a #LocalIterator (bucket iterators) that are not available with
383/// the four standard library types, are provided with this type.
384/// - There is no <c>operator[]</c> defined. The rationale to omit this - at first sight convenient
385/// and intuitive - operator, is that it imposes insert operation even if used in r-value
386/// expressions. This is considered an unwanted side effect.
387/// - The caching of hash-codes can be controlled with this type, while it is an implementation
388/// dependent feature with the standard library.
389/// - The automatic increase (re-hashing) of the bucket number can be tweaked with
390/// constructor parameter \p{pBaseLoadFactor} (and method #BaseLoadFactor(float)), which is not
391/// specified with the standard library types.
392/// - Assignment <c>operator=</c> is not available with this implementation.
393/// If needed, such has to implemented by a user (full iteration with copying elements from one
394/// instance to another).
395///
396/// @see
397/// - Chapter \ref alib_contmono_containers_types of the joint Programmer's Manuals of modules
398/// \alib_containers and \alib_monomem.
399/// - Chapter \ref alib_threads_intro_assert_entry of the Programmer's Manual of module
400/// \alib_threads for information about debugging multithreaded access on instances of this type.
401///\I{#############################################################################################}
402/// \anchor alib_ns_containers_hashtable_referencedoc
403/// # Reference Documentation #
404/// @tparam TAllocator The allocator type to use, as prototyped with \alib{lang;Allocator}.
405/// @tparam TValueDescriptor Defines the #StoredType, #KeyType and #MappedType. Furthermore has to
406/// proving methods that to extract key- and mapped values out of the
407/// stored type.<br>
408/// For details on required type definitions and method signatures, see
409/// provided implementations
410/// \alib{containers;TIdentDescriptor} and
411/// \alib{containers;TPairDescriptor} as a sample.<br>
412/// The type is published as
413/// \alib{containers;HashTable::DescriptorType}.
414/// @tparam THash The hash functor applicable to the key-type defined by
415/// \p{TValueDescriptor}.
416/// Defaults to <c>std::hash<typename TValueDescriptor::KeyType></c>
417/// and is published as \alib{containers;HashTable::HashType}.
418/// @tparam TEqual The comparison functor on the key-type defined by \p{TValueDescriptor}.
419/// Defaults to <c>std::equal_to<typename TValueDescriptor::KeyType></c>
420/// and is published as \alib{containers;HashTable::EqualType}.
421/// @tparam THashCaching Determines if hash codes are cached when elements are inserted.
422/// Defaults to <b>Caching::Auto</b>, which enables caching if
423/// <c>std::is_arithmetic<TKey>::value</c> evaluates to \c false.
424/// @tparam TRecycling Denotes the type of recycling that is to be performed. Possible values
425/// are
426/// \alib{containers;Recycling;Private} (the default),
427/// \alib{containers;Recycling;Shared} or
428/// \alib{containers;Recycling;None}.
429//==================================================================================================
430template< typename TAllocator,
431 typename TValueDescriptor,
432 typename THash = std::hash <typename TValueDescriptor::KeyType>,
433 typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>,
434 lang::Caching THashCaching = lang::Caching::Auto,
435 Recycling TRecycling = Recycling::Private >
436class HashTable : protected detail::HashTableBase<TAllocator,TValueDescriptor,THash,TEqual,THashCaching,TRecycling>
437{
438 public:
439 #if !DOXYGEN
440 #if ALIB_DEBUG_CRITICAL_SECTIONS
441 mutable lang::DbgCriticalSections dcs;
442 #define DCS ALIB_DCS_WITH(dcs)
443 #define DCSSHRD ALIB_DCS_SHARED_WITH(dcs)
444 #else
445 #define DCS
446 #define DCSSHRD
447 #endif
448 #endif
449
450 protected:
451 // protected shortcuts to parent and its types we need
452 #if !DOXYGEN
454 using Element = typename base::Element;
455 using Node = typename base::Node;
456 #endif
457
458 /// The recycler type.
459 using recyclerType= typename base::recyclerType;
460
461
462 public:
463
464 //##############################################################################################
465 // Types and Constants
466 //##############################################################################################
467 /// Type definition publishing template parameter \p{TAllocator}.
468 using AllocatorType = TAllocator;
469
470 /// Type definition publishing template parameter \p{TValueDescriptor}.
471 using DescriptorType= TValueDescriptor;
472
473 /// Type definition publishing the stored type of this container as defined with template
474 /// parameter \p{TValueDescriptor}.
475 using StoredType = typename TValueDescriptor::StoredType;
476
477 /// Type definition publishing the key type of this container as defined with template
478 /// parameter \p{TValueDescriptor}.
479 using KeyType = typename TValueDescriptor::KeyType;
480
481 /// Type definition publishing the map type of this container as defined with template
482 /// parameter \p{TValueDescriptor}.
483 using MappedType = typename TValueDescriptor::MappedType;
484
485 /// Type definition publishing template parameter \p{THash}.
486 using HashType = THash;
487
488 /// Type definition publishing template parameter \p{TEqual}.
489 using EqualType = TEqual;
490
491 /// Determines whether hash codes are stored with the elements.
492 /// It is done in case the given template parameter \p{THashCashing} equals
493 /// \alib{lang;Caching;Caching::Enabled} or if it equals \alib{lang;Caching;Caching::Auto}
494 /// and the #KeyType type is an arithmetic type.
495 /// @return \c true if hash codes are stored for reuse, \c false if not.
496 static constexpr bool IsCachingHashes() { return base::IsCachingHashes(); }
497
498 /// @return The enum element value of template parameter \p{TRecycling}.
499 static constexpr Recycling RecyclingTag() { return TRecycling; }
500
501 /// This type definition may be used to define an externally managed shared recycler,
502 /// which can be passed to the alternative constructor of this class when template
503 /// parameter \p{TRecycling} equals \alib{containers;Recycling;Shared}.
504 /// \see
505 /// Chapter \ref alib_contmono_containers_recycling_shared of the Programmer's Manual
506 /// for this \alibmod.
507 using SharedRecyclerType= typename base::SharedRecyclerType;
508
509
510 /// Determines whether the used recycler type is in fact recycling elements.
511 /// @return \c false if template parameter \p{TRecycling} equals
512 /// \alib{containers;Recycling;None}, \c true otherwise.
513 static constexpr bool IsRecycling() { return recyclerType::IsRecycling(); }
514
515 /// Denotes whether hash codes are cached or not.
516 static constexpr bool CachedHashCodes = base::Element::CachedHashCodes;
517
518 /// The mutable iterator exposed by this container.
519 using Iterator = typename base::template TIterator < StoredType>;
520
521 /// The constant iterator exposed by this container.
522 using ConstIterator = typename base::template TIterator <const StoredType>;
523
524 /// The mutable iterator for a single bucket exposed by this container.
525 using LocalIterator = typename base::template TLocalIterator < StoredType>;
526
527 /// The constant iterator for a single bucket exposed by this container.
528 using ConstLocalIterator = typename base::template TLocalIterator <const StoredType>;
529
530 /// A value of this type is returned with methods #Extract, which allows removing
531 /// an element from the hashtable, without deleting its allocated storage and destructing its
532 /// custom value.
533 ///
534 /// This handle allows writing access to the value of an extracted element.
535 /// In combination with methods #Insert(ElementHandle&) and #InsertIfNotExistent(ElementHandle&),
536 /// this supports changing parts of the element value, including the <em>key-portion</em> with
537 /// proper re-insertion.
538 ///
539 /// Objects of this type cannot be copied, but just moved.
541 {
542 #if !DOXYGEN
543 friend class HashTable;
544 #endif
545
546 private:
547 HashTable* table; ///< The table we belong to.
548 Element* element; ///< The extracted element.
549
550 /// Constructor setting fields #table and #element.
551 /// @param pTable The table we belong to.
552 /// @param pElement The extracted element.
553 ElementHandle( HashTable* pTable, Element* pElement )
554 : table ( pTable )
555 , element( pElement )
556 {}
557
558 public:
559 /// Move constructor setting the moved object to emtpy.
560 /// @param other The handle to move.
562 : table ( other.table )
563 , element( other.element )
564 {
565 other.element= nullptr;
566 }
567
568 /// Default constructor creating and empty handle.
570 : element( nullptr )
571 {}
572
573 /// Deleted copy constructor.
574 ElementHandle( ElementHandle& other ) = delete;
575
576 /// Deleted copy assignment operator.
577 ElementHandle& operator=( const ElementHandle& other ) = delete;
578
579 /// Move assignment. Disposes any current content, and moves \p{other} into this.
580 /// @param other The handle to move into this object.
581 /// @return A reference to <c>this</c>.
583 {
584 if( element != nullptr )
585 table->recyclerType::Recycle(element);
586 table = other.table;
587 element= other.element;
588 other.element= nullptr;
589
590 return *this;
591 }
592
593 /// Destructor. If this handle is not empty, the allocated storage of the
594 /// represented element is added to the list of recyclable objects.
596 {
597 if( element != nullptr )
598 table->recyclerType::Recycle(element);
599 }
600
601 /// Determines if this is a "valid" handle.
602 /// @return Returns \c true if this objects represents a valid element, \c false
603 /// otherwise.
604 bool IsEmpty() const { return element == nullptr; }
605
606 /// Returns a mutable reference to this element's data.
607 /// Must not be invoked on empty instances.
608 /// @return Returns a mutable reference to value of the represented element.
609 StoredType& Value () const { return element->value; }
610
611 /// Returns a mutable reference to the <em>key-portion</em> of this element's data.
612 /// Must not be invoked on empty instances.
613 /// @return Returns a mutable reference to the <em>key-portion</em> of the represented
614 /// element.
615 KeyType& Key () const { return TValueDescriptor().Key( element->value ); }
616
617 /// Returns a mutable reference to the <em>mapped-portion</em> of this element's data.
618 /// Must not be invoked on empty instances.
619 /// @return Returns a mutable reference to the mapped object.
620 MappedType& Mapped () const { return TValueDescriptor().Mapped( element->value ); }
621
622 }; // class ElementHandle
623
624 //##############################################################################################
625 // Construction/Destruction And Allocator Access
626 //##############################################################################################
627
628 //==============================================================================================
629 /// Constructor.
630 /// \note
631 /// This constructor is not available if the template argument \p{TRecycling} equals
632 /// \alib{containers;Recycling;Shared}.
633 ///
634 /// @tparam TRequires Defaulted template parameter. Must not be specified.
635 /// @param pAllocator The allocator to use.
636 /// @param pBaseLoadFactor The base load factor. Defaults to <c>1.0</c>.
637 /// @param pMaxLoadFactor The maximum load factor. Defaults to <c>2.0</c>.
638 //==============================================================================================
639 template<bool TRequires= TRecycling!= Recycling::Shared>
640 requires TRequires
641 explicit
643 float pBaseLoadFactor = 1.0,
644 float pMaxLoadFactor = 2.0 )
645 : base( pAllocator, pBaseLoadFactor, pMaxLoadFactor )
647 , dcs("HashTable")
648 #endif
649 {}
650
651 //==============================================================================================
652 /// Constructor.
653 /// \note
654 /// This constructor is not available if the template argument \p{TRecycling} equals
655 /// \alib{containers;Recycling;Shared} and the
656 /// if template argument \p{TAllocator} does not equal \alib{lang;HeapAllocator}
657 ///
658 ///
659 /// @tparam TRequires Defaulted template parameter. Must not be specified.
660 /// @param pBaseLoadFactor The base load factor. Defaults to <c>1.0</c>.
661 /// @param pMaxLoadFactor The maximum load factor. Defaults to <c>2.0</c>.
662 //==============================================================================================
663 template<bool TRequires= TRecycling!= Recycling::Shared>
664 requires TRequires
665 explicit
666 HashTable( float pBaseLoadFactor = 1.0,
667 float pMaxLoadFactor = 2.0 )
668 : base( pBaseLoadFactor, pMaxLoadFactor )
670 , dcs("HashTable")
671 #endif
672 {}
673
674
675 //==============================================================================================
676 /// Constructor taking a shared recycler.
677 /// @param pAllocator The allocator to use.
678 /// @param pSharedRecycler The shared recycler.
679 /// @param pBaseLoadFactor The base load factor. See method #BaseLoadFactor for details.
680 /// Defaults to <c>1.0</c>.
681 /// @param pMaxLoadFactor The maximum load factor. See method #MaxLoadFactor for details.
682 /// Defaults to <c>2.0</c>.
683 /// @tparam TSharedRecycler Used to select this constructor. Deduced by the compiler.
684 //==============================================================================================
685 template<typename TSharedRecycler= SharedRecyclerType>
686 requires (!std::same_as<TSharedRecycler, void>)
688 TSharedRecycler& pSharedRecycler,
689 float pBaseLoadFactor = 1.0,
690 float pMaxLoadFactor = 2.0 )
691 : base( pAllocator, pSharedRecycler, pBaseLoadFactor, pMaxLoadFactor )
693 , dcs("HashTable")
694 #endif
695 {}
696
697 //==============================================================================================
698 /// Constructor taking a shared recycler.
699 /// @param pSharedRecycler The shared recycler.
700 /// @param pBaseLoadFactor The base load factor. See method #BaseLoadFactor for details.
701 /// Defaults to <c>1.0</c>.
702 /// @param pMaxLoadFactor The maximum load factor. See method #MaxLoadFactor for details.
703 /// Defaults to <c>2.0</c>.
704 /// @tparam TSharedRecycler Used to select this constructor. Deduced by the compiler.
705 //==============================================================================================
706 template<typename TSharedRecycler= SharedRecyclerType>
707 requires (!std::same_as<TSharedRecycler, void>)
708 HashTable( TSharedRecycler& pSharedRecycler,
709 float pBaseLoadFactor = 1.0,
710 float pMaxLoadFactor = 2.0 )
711 : base( pSharedRecycler, pBaseLoadFactor, pMaxLoadFactor )
713 , dcs("HashTable")
714 #endif
715 {}
716
717 //==============================================================================================
718 /// Returns the allocator of this object. Usually the allocator might be used to perform
719 /// allocations in respect to data found in objects stored in this object.
720 /// However, such allowance is dependent on the use case and not part of this class's
721 /// contract.
722 ///
723 /// @return The allocator that was provided in the constructor.
724 //==============================================================================================
726 { return base::base::GetAllocator(); }
727
728
729 //##############################################################################################
730 /// @name Size and Capacity
731 //##############################################################################################
732
733 //==============================================================================================
734 /// Destructs and removes all elements from this hash table. The allocated space
735 /// of the elements will be preserved and "recycled" with future insertions.
736 //==============================================================================================
737 void Clear() { DCS base::clear(); }
738
739 //==============================================================================================
740 /// Same as clear, but does not recycle internal nodes. Furthermore, all recyclables
741 /// are deleted. The latter is done only if template parameter \p{TRecycling} is not
742 /// \alib{containers;Recycling;Shared}. In this case, the elements are still recycled.
743 ///
744 /// This method is useful with monotonic allocators, that can be reset as well, after
745 /// this instance is reset.
746 /// But, because the life-cycle of the monotonic allocator(s) used for insertions is not
747 /// under control of this object, it is the obligation of the caller to ensure that the
748 /// monotonic allocator is kept in sync with this object.
749 /// The following recipe shows a valid use:
750 /// - Construct a \b HashTable passing a \b MonoAllocator.
751 /// - Create a snapshot of the \b MonoAllocator.
752 /// - Use the \b HashTable.
753 /// - Reset the \b HashTable and right afterwards the \b MonoAllocator to the snapeshot taken.
754 //==============================================================================================
755 void Reset()
756 {
757 recyclerType oldRecycler(*this);
758 auto baseLoadFactor = base::baseLoadFactor;
759 auto maxLoadFactor = base::maxLoadFactor ;
760 auto& allocator = base::base::GetAllocator();
761 lang::Destruct(*this);
762 if constexpr ( std::same_as< typename base::recyclerType,
764 new (this) HashTable( oldRecycler, baseLoadFactor, maxLoadFactor );
765 else
766 new (this) HashTable( allocator, baseLoadFactor, maxLoadFactor );
767 }
768
769 /// Returns the number of stored elements. Note that this method runs in constant time, as
770 /// the number of elements is kept counted during operation.
771 /// @return The number of elements stored in the hash table.
772 integer Size() const noexcept
773 { return base::size; }
774
775 //==============================================================================================
776 /// Invokes #Size and compares result with \c 0.
777 /// @return \c true if this list is empty, \c false otherwise.
778 //==============================================================================================
779 bool IsEmpty() const noexcept
780 { return base::size == 0; }
781
782 //==============================================================================================
783 /// Reserves space for at least the given number of elements.
784 /// This might re-hash this table.
785 /// \see Method #ReserveRecyclables.
786 /// @param qty The expected number or increase of elements to be stored in the hash table.
787 /// @param reference Denotes whether \p{expected} is meant as an absolute size or an increase.
788 //==============================================================================================
789 void Reserve( integer qty, lang::ValueReference reference )
790 {DCS
791 float expectedSize= float( qty + (reference == lang::ValueReference::Relative ? Size()
792 : 0 ) );
793 return base::rehash( uinteger(std::ceil( expectedSize / base::baseLoadFactor)) );
794 }
795
796 //==============================================================================================
797 /// Same as #Reserve but in addition also already allocates the required space for the number
798 /// of additional elements expected.
799 ///
800 /// @see Chapter \ref alib_contmono_containers_recycling_reserving of the Programmer's
801 /// Manual.
802 ///
803 /// @param qty The expected resulting number (or increase) of elements to be stored in
804 /// this container.
805 /// @param reference Denotes whether \p{qty} is meant as an absolute size or an
806 /// increase.
807 //==============================================================================================
809 {
810 Reserve( qty, reference );
811 {DCS
812 auto requiredRecyclables= ( qty - (reference == lang::ValueReference::Absolute ? Size()
813 : 0 ) )
814 - base::recyclerType::Count();
815 if( requiredRecyclables > 0 )
816 recyclerType::Reserve( requiredRecyclables );
817 }
818 }
819
820 //==============================================================================================
821 /// Counts the number of currently allocated but unused (not contained) element nodes
822 /// that will be recycled with upcoming insertions.
823 ///
824 /// \note
825 /// This method is provided for completeness and unit-testing. It should not be of
826 /// relevance for common usage.<br>
827 /// Furthermore, this method is not available (aka does not compile) with instantiations
828 /// that specify template parameter \p{TRecycling} as \alib{containers;Recycling;None}.
829 ///
830 /// @return The number of removed and not yet recycled elements.
831 //==============================================================================================
832 integer RecyclablesCount() const noexcept
833 {DCSSHRD return base::recyclerType::Count(); }
834
835 //##############################################################################################
836 /// @name Hash Policy
837 //##############################################################################################
838
839 //==============================================================================================
840 /// Sets a new value for the "base load factor" used with this container.
841 /// The base load factor determines the minimum number of buckets
842 /// when re-hashing is performed.
843 ///
844 /// The formula to determine the minimum number of buckets is #Size divided by this factor.
845 /// A static table of prime numbers is searched for the next higher number and this value
846 /// is then used to determine the number of buckets.
847 ///
848 /// The default value for this factor is defined as <c>1.0</c> by the default value
849 /// of parameter \p{pBaseLoadFactor} of the constructor.
850 ///
851 /// \note
852 /// Invoking this method never triggers rehashing.
853 ///
854 /// \see
855 /// Overloaded method #BaseLoadFactor() and this class's documentation section
856 /// \ref alib_ns_containers_hashtable_rehashing "4. Re-Hashing".
857 ///
858 /// @param newBaseLoadFactor The new base load factor to use when a rehash is performed.
859 //==============================================================================================
860 void BaseLoadFactor( float newBaseLoadFactor ) noexcept
861 { base::baseLoadFactor= newBaseLoadFactor; }
862
863 //==============================================================================================
864 /// Returns the actual base load factor.
865 ///
866 /// \see
867 /// Overloaded method #BaseLoadFactor(float) and this class's documentation section
868 /// \ref alib_ns_containers_hashtable_rehashing "4. Re-Hashing".
869 ///
870 /// @return The current value of the base load factor.
871 //==============================================================================================
872 float BaseLoadFactor() const noexcept
873 { return base::baseLoadFactor; }
874
875
876 //==============================================================================================
877 /// Sets a new value for the "maximum load factor" which is the average number of elements
878 /// per bucket.
879 ///
880 /// The default value for this factor is defined as <c>2.0</c> by the default value
881 /// of parameter \p{pMaxLoadFactor} of the constructor.
882 ///
883 /// \note
884 /// Invoking this method triggers rehashing, in case the hash table is not empty and
885 /// the new maximum load factor is below the current load factor of this container, which
886 /// equals #Size divided by #BucketCount.<br>
887 /// This method may be used to temporarily disable re-hashing by providing
888 /// <c>std::numeric_limits<float>::max()</c>.
889 ///
890 /// \see
891 /// Overloaded method #MaxLoadFactor() and this class's documentation section
892 /// \ref alib_ns_containers_hashtable_rehashing "4. Re-Hashing".
893 ///
894 /// @param newMaxLoadFactor The maximum load factor used to determine the need of re-hashing.
895 //==============================================================================================
896 void MaxLoadFactor( float newMaxLoadFactor ) noexcept
897 { base::setMaxLoadFactor( newMaxLoadFactor ); }
898
899 //==============================================================================================
900 /// Returns the actual maximum load factor.
901 ///
902 /// \see
903 /// Overloaded method #MaxLoadFactor(float) and this class's documentation section
904 /// \ref alib_ns_containers_hashtable_rehashing "4. Re-Hashing".
905 ///
906 /// @return The current value of the maximum load factor.
907 //==============================================================================================
908 float MaxLoadFactor() const noexcept
909 { return base::maxLoadFactor; }
910
911 //##############################################################################################
912 /// @name Bucket Interface
913 //##############################################################################################
914
915 //==============================================================================================
916 /// Returns the number of "buckets" that this hash table currently uses.
917 ///
918 /// @return The size of the array of hash buckets.
919 //==============================================================================================
920 uinteger BucketCount() const noexcept
921 { return base::bucketCount; }
922
923 //==============================================================================================
924 /// Returns the number of entries stored in the bucket with the given number.
925 ///
926 /// @param bucketNumber The number of the bucket to receive the size for.
927 /// @return The number of entries in the specified bucket.
928 //==============================================================================================
929 uinteger BucketSize( uinteger bucketNumber ) const noexcept
930 {DCSSHRD
931 ALIB_ASSERT_ERROR( bucketNumber < base::bucketCount, "MONOMEM/HASHTABLE",
932 "Bucket number out of range. {}>={}", bucketNumber, base::bucketCount )
933 return uinteger(base::buckets[bucketNumber].count());
934 }
935
936 //==============================================================================================
937 /// Returns the number of the bucket corresponding to \p{key}.
938 ///
939 /// @param key The key to evaluate the bucket number for.
940 /// @return The bucket number that \p{key} is assigned to.
941 //==============================================================================================
942 uinteger BucketNumber( const KeyType& key ) const noexcept
943 { return THash{}(key) % base::bucketCount; }
944
945 //##############################################################################################
946 /// @name Element Insertion
947 //##############################################################################################
948 //==============================================================================================
949 /// See #Insert(StoredType&&) which is invoked with a copy of \p{value}.
950 ///
951 /// @param value A value to copy and insert.
952 /// @return An iterator referring to the element added.
953 //==============================================================================================
955 { return Insert( value, THash{}( TValueDescriptor().Key( reinterpret_cast<StoredType&>(value)) ) ); }
956
957 //==============================================================================================
958 /// Overloaded version of method \alib{containers::HashTable;Insert(const StoredType&)} which
959 /// accepts the \p{hashCode} of the given \p{value} as a second parameter.
960 ///
961 /// @see Use cases of this method are discussed in reference documentation section
962 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
963 ///
964 /// @param value A value to copy and insert.
965 /// @param hashCode Pre-calculated hash code of \p{value}.
966 /// @return An iterator referring to the element added.
967 //==============================================================================================
968 Iterator Insert( const StoredType& value, size_t hashCode )
969 { return Insert(value, hashCode ); }
970
971 //==============================================================================================
972 /// Moves the given value into this table.<br>
973 /// Existing iterators remain valid.
974 ///
975 /// \note
976 /// The use of this method may insert elements sharing the same key as already existing
977 /// elements.
978 /// For more information, see
979 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
980 /// of the documentation of this class.
981 ///
982 /// @param value A rvalue reference of contained type \p{StoredType} to insert.
983 /// @return An iterator referring to the element added.
984 //==============================================================================================
986 {
987 auto hashCode = THash{}( TValueDescriptor().Key( reinterpret_cast<StoredType&>(value)) );
988 return Insert( std::move(value), hashCode );
989 }
990
991 //==============================================================================================
992 /// Overloaded version of method \alib{containers::HashTable;Insert(StoredType&&)} which
993 /// accepts the \p{hashCode} of the given \p{value} as a second parameter.
994 ///
995 /// @see Use cases of this method are discussed in reference documentation section
996 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
997 ///
998 /// @param value An rvalue reference of contained type \p{StoredType} to insert.
999 /// @param hashCode Pre-calculated hash code of \p{value}.
1000 /// @return An iterator referring to the element added.
1001 //==============================================================================================
1002 Iterator Insert( StoredType&& value, size_t hashCode )
1003 {DCS
1004 // Recycle node or create a new one
1005 Element* element= base::allocElement(hashCode);
1006
1007 // placement-new
1008 new ( &element->value ) StoredType ( std::move(value) );
1009
1010 // insert to hash table
1011 base::increaseSize( 1 );
1012 auto bucketIdx= base::insertInBucket( element, hashCode );
1013 return Iterator( this, bucketIdx, element);
1014 }
1015
1016 //==============================================================================================
1017 /// Inserts the element contained in the given \alib{containers::HashTable;ElementHandle}
1018 /// into the hash table.
1019 ///
1020 /// \note
1021 /// The use of this method may insert elements sharing the same key as already existing
1022 /// elements.
1023 /// For more information, see
1024 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1025 /// of the documentation of this class.
1026 ///
1027 /// <p>
1028 /// Objects of type \b ElementHandle objects may be received using overloaded methods
1029 /// #Extract. The combination of \b %Extract and this method (as well as method
1030 /// #InsertIfNotExistent(ElementHandle&) are the only way to change the <em>key-portion</em> of an
1031 /// element without element destruction/re-construction.
1032 ///
1033 /// @param handle A reference to a handle to an element, previously received with #Extract.
1034 /// @return On success, returns an iterator that refers to the inserted element.
1035 /// On failure (if parameter \p{handle} was empty), the returned iterator equals #end.
1036 //==============================================================================================
1037 Iterator Insert( ElementHandle& handle )
1038 {DCS
1039 if( handle.IsEmpty() )
1040 return end();
1041
1042 base::increaseSize( 1 );
1043 Element* element= handle.element;
1044 auto hashCode= THash{}( TValueDescriptor().Key( element->value ));
1045 element->fixHashCode( hashCode );
1046 auto bucketIdx= base::insertInBucket( element, hashCode );
1047 handle.element= nullptr;
1048 return Iterator( this, bucketIdx, element );
1049 }
1050
1051 //==============================================================================================
1052 /// See #InsertUnique(StoredType&&) which is invoked with a copy of \p{value}.
1053 ///
1054 /// @param value An element to insert whose <em>key-portion</em> has to be different to
1055 /// all currently contained elements.
1056 /// @return An iterator referring to the element added.
1057 //==============================================================================================
1059 { return InsertUnique(std::move(StoredType( value )) ); }
1060
1061 //==============================================================================================
1062 /// Overloaded version of method
1063 /// \alib{containers::HashTable;InsertUnique(const StoredType&)} which accepts the
1064 /// \p{hashCode} of the given \p{key} as a second parameter.
1065 ///
1066 /// @see Use cases of this method are discussed in reference documentation section
1067 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
1068 ///
1069 /// @param value An element to insert whose <em>key-portion</em> has to be different to
1070 /// all currently contained elements.
1071 /// @param hashCode Pre-calculated hash code of \p{value}.
1072 /// @return An iterator referring to the element added.
1073 //==============================================================================================
1074 Iterator InsertUnique( const StoredType& value, size_t hashCode )
1075 { return InsertUnique( StoredType( value ), hashCode ); }
1076
1077 //==============================================================================================
1078 /// Moves the given value into this table without checking to place it in the right
1079 /// position in respect to existing elements with the same <em>key-portion</em>.
1080 ///
1081 /// \attention
1082 /// This method must only be used if the caller guarantees that no other element is
1083 /// currently stored in this container having an equal <em>key-portion</em>.
1084 /// In such situations, this method is very efficient.<br>
1085 /// If one exists already, this hash table is not considered in a consistent state
1086 /// after the operation. I.e., method #EqualRange will discontinue to function properly.
1087 ///
1088 /// \attention
1089 /// In debug-compilations, an \alib assertion is raised, if an equal element exists.
1090 /// For this reason, performance differences to method #Insert will be seen only with
1091 /// release-compilations.
1092 ///
1093 /// \attention
1094 /// For more information, see
1095 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1096 /// of the documentation of this class.
1097 ///
1098 ///
1099 /// @param value An element to insert whose <em>key-portion</em> has to be different to
1100 /// all currently contained elements.
1101 /// @return An iterator referring to the element added.
1102 //==============================================================================================
1104 {
1105 auto hashCode = THash{}( TValueDescriptor().Key( reinterpret_cast<StoredType&>(value)) );
1106 return InsertUnique(std::move(value), hashCode );
1107 }
1108
1109 //==============================================================================================
1110 /// Overloaded version of method \alib{containers::HashTable;InsertUnique(StoredType&&)}
1111 /// which accepts the \p{hashCode} of the given \p{key} as a second parameter.
1112 ///
1113 /// @see Use cases of this method are discussed in reference documentation section
1114 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
1115 ///
1116 /// @param value An element to insert whose <em>key-portion</em> has to be different to
1117 /// all currently contained elements.
1118 /// @param hashCode Pre-calculated hash code of \p{value}.
1119 /// @return An iterator referring to the element added.
1120 //==============================================================================================
1121 Iterator InsertUnique( StoredType&& value, size_t hashCode )
1122 {DCS
1123 Element* element = base::allocElement( hashCode );
1124
1125 base::increaseSize( 1 );
1126 auto bucketIdx= hashCode % base::bucketCount;
1127 base::buckets[bucketIdx].pushFront( element );
1128
1129 new ( &element->value ) StoredType( std::move(value) );
1130
1131 #if ALIB_DEBUG
1132 //Check that this was the first of
1133 auto it= ConstLocalIterator( bucketIdx, base::buckets[bucketIdx].first() ); // cbegin(bucketIdx);
1134 ALIB_ASSERT( it.element == element, "MONOMEM/HASHTABLE" ) // has to be the first inserted
1135 while( ++it != cend(bucketIdx) )
1136 {
1137 ALIB_ASSERT_ERROR( !base::areEqual(element, it.element ), "MONOMEM/HASHTABLE",
1138 "InsertUnique used while element with same key-portion existed!" )
1139 }
1140 #endif
1141
1142 return Iterator( this, bucketIdx, element);
1143 }
1144
1145
1146 //==============================================================================================
1147 /// See #InsertOrAssign(const KeyType&, MappedType&&) which is invoked with a copy of \p{mapped}.
1148 ///
1149 /// \par Availability
1150 /// This method is only available with
1151 /// \ref alib_ns_containers_hashtable_setandmap "hash map mode".
1152 ///
1153 /// @tparam TRequires Used to disable this method for instantiations of this
1154 /// template type with <em>hash set mode</em>.<br>
1155 /// Defaulted and must not be specified with invocations.
1156 /// @param key The key to use for search and insertion.
1157 /// @param mapped The mapped value to copy and then insert or assign.
1158 /// @return A pair containing an iterator referencing the element added.
1159 /// The bool component is \c true if the insertion took place and \c false if the
1160 /// assignment took place.
1161 //==============================================================================================
1162 template<typename TRequires= MappedType>
1163 requires(!std::same_as<TRequires, StoredType>)
1164 std::pair<Iterator, bool> InsertOrAssign( const KeyType& key, const MappedType& mapped)
1165 { return InsertOrAssign( key, MappedType(mapped) ); }
1166
1167 //==============================================================================================
1168 /// Replaces an existing, respectively inserts a new element into this hash table.
1169 ///
1170 /// \note
1171 /// This method allows preventing the insertion of double entries.
1172 /// For more information, see
1173 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1174 /// of the documentation of this class.
1175 ///
1176 /// \par Availability
1177 /// This method is only available with
1178 /// \ref alib_ns_containers_hashtable_setandmap "hash map mode".
1179 ///
1180 /// @tparam TRequires Used to disable this method for instantiations of this
1181 /// template type with <em>hash set mode</em>.<br>
1182 /// Defaulted and must not be specified with invocations.
1183 /// @param key The key to use for search and insertion.
1184 /// @param mapped The mapped value to insert or assign.
1185 /// @return A pair containing an iterator referring to the element added.
1186 /// The bool component is \c true if the insertion took place and \c false if the
1187 /// assignment took place.
1188 //==============================================================================================
1189 template<typename TRequires= MappedType>
1190 requires(!std::same_as<TRequires, StoredType>)
1191 std::pair<Iterator, bool> InsertOrAssign( const KeyType& key, MappedType&& mapped )
1192 { return InsertOrAssign( key, std::move(mapped), THash{}(key) ); }
1193
1194 //==============================================================================================
1195 /// Overloaded version of method
1196 /// \alib{containers::HashTable;InsertOrAssign(const KeyType&; MappedType&&)} which
1197 /// accepts the \p{hashCode} of the given \p{key} as a third parameter.
1198 ///
1199 /// @see Use cases of this method are discussed in reference documentation section
1200 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
1201 ///
1202 /// \par Availability
1203 /// This method is only available with
1204 /// \ref alib_ns_containers_hashtable_setandmap "hash map mode".
1205 ///
1206 /// @tparam TRequires Used to disable this method for instantiations of this
1207 /// template type with <em>hash set mode</em>.<br>
1208 /// Defaulted and must not be specified with invocations.
1209 /// @param key The key to use for search and insertion.
1210 /// @param mapped The mapped value to insert or assign.
1211 /// @param hashCode Pre-calculated hash code of \p{key}.
1212 /// @return A pair containing an iterator referring to the element added.
1213 /// The bool component is \c true if the insertion took place and \c false if the
1214 /// assignment took place.
1215 //==============================================================================================
1216 template<typename TRequires= MappedType>
1217 requires(!std::same_as<TRequires, StoredType>)
1218 std::pair<Iterator, bool> InsertOrAssign( const KeyType& key, MappedType&& mapped, size_t hashCode )
1219 {DCS
1220 std::pair<Iterator, bool> result= base::insertOrGet( key, hashCode );
1221
1222 // if an existing element was found, we have to destruct the mapped value
1223 if( result.second == false )
1224 lang::Destruct( TValueDescriptor().Mapped( result.first.element->value ) );
1225
1226 // if otherwise a new element was inserted, we have to copy the key
1227 else
1228 new (&TValueDescriptor().Key( result.first.element->value )) KeyType( key );
1229
1230 // placement-new for the mapped object
1231 new ( &TValueDescriptor().Mapped( result.first.element->value ) ) MappedType( std::move( mapped) );
1232
1233 return result;
1234 }
1235
1236 //==============================================================================================
1237 /// See #InsertIfNotExistent(const KeyType&, MappedType&&) which is invoked with a copy of
1238 /// \p{mapped}.
1239 ///
1240 /// \par Availability
1241 /// This method is only available with
1242 /// \ref alib_ns_containers_hashtable_setandmap "hash map mode".
1243 ///
1244 /// @tparam TRequires Used to disable this method for instantiations of this
1245 /// template type with <em>hash set mode</em>.<br>
1246 /// Defaulted and must not be specified with invocations.
1247 /// @param key The key to use for search and insertion.
1248 /// @param mapped The mapped object to copy and insert if \p{key} is not existing.
1249 /// @return A pair containing an iterator referencing either the element found or the new
1250 /// element added. The bool component is \c true if the insertion took place and \c false
1251 /// if nothing was changed.
1252 //==============================================================================================
1253 template<typename TRequires= MappedType>
1254 requires(!std::same_as<TRequires, StoredType>)
1255 std::pair<Iterator, bool> InsertIfNotExistent( const KeyType& key, const MappedType& mapped)
1256 { return InsertIfNotExistent( key, MappedType(mapped) ); }
1257
1258 //==============================================================================================
1259 /// Overloaded version of method
1260 /// \alib{containers::HashTable;InsertIfNotExistent(const KeyType&,MappedType&&)} which
1261 /// accepts the \p{hashCode} of the given \p{key} as a third parameter.
1262 ///
1263 /// \par Availability
1264 /// This method is only available with
1265 /// \ref alib_ns_containers_hashtable_setandmap "hash map mode".
1266 ///
1267 /// @see Use cases of this method are discussed in reference documentation section
1268 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
1269 ///
1270 /// @tparam TRequires Used to disable this method for instantiations of this
1271 /// template type with <em>hash set mode</em>.<br>
1272 /// Defaulted and must not be specified with invocations.
1273 /// @param key The key to use for search and insertion.
1274 /// @param hashCode Pre-calculated hash code of \p{key}.
1275 /// @param mapped The mapped value to insert if \p{key} is not existing.
1276 /// @return A pair containing an iterator referencing either the element found or the new
1277 /// element added. The bool component is \c true if the insertion took place and \c false
1278 /// if nothing was changed.
1279 //==============================================================================================
1280 template<typename TRequires= MappedType>
1281 requires(!std::same_as<TRequires, StoredType>)
1282 std::pair<Iterator, bool> InsertIfNotExistent( const KeyType& key, MappedType&& mapped, size_t hashCode)
1283 {DCS
1284 // search element
1285 std::pair<Iterator, bool> result= base::insertIfNotExists( key, hashCode );
1286
1287 // existed? Do nothing
1288 if( result.second == false )
1289 return result;
1290
1291 // placement-new for the key (using copy constructor)
1292 new (&TValueDescriptor().Key( result.first.element->value )) KeyType( key );
1293
1294 // placement-new for the mapped (using move constructor)
1295 new ( &TValueDescriptor().Mapped( result.first.element->value ) ) MappedType( std::move( mapped) );
1296
1297 return result;
1298 }
1299
1300 //==============================================================================================
1301 /// Inserts a new mapped object only if no other object is contained that is associated
1302 /// already with the same key as given \p{key}.
1303 ///
1304 /// \note
1305 /// This method allows preventing the insertion of double entries.
1306 /// For more information, see
1307 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1308 /// of the documentation of this class.
1309 ///
1310 /// \par Availability
1311 /// This method is only available with
1312 /// \ref alib_ns_containers_hashtable_setandmap "hash map mode".
1313 ///
1314 /// @tparam TRequires Used to disable this method for instantiations of this
1315 /// template type with <em>hash set mode</em>.<br>
1316 /// Defaulted and must not be specified with invocations.
1317 /// @param key The key to use for search and insertion.
1318 /// @param mapped The mapped value to insert if \p{key} is not existing.
1319 /// @return A pair containing an iterator referencing either the element found or the new
1320 /// element added. The bool component is \c true if the insertion took place and \c false
1321 /// if nothing was changed.
1322 //==============================================================================================
1323 template<typename TRequires= MappedType>
1324 requires(!std::same_as<TRequires, StoredType>)
1325 std::pair<Iterator, bool> InsertIfNotExistent( const KeyType& key, MappedType&& mapped)
1326 { return InsertIfNotExistent( key, std::move(mapped), THash{}(key) ); }
1327
1328 //==============================================================================================
1329 /// See #InsertIfNotExistent(StoredType&&) which is invoked with a copy of \p{value}.
1330 ///
1331 /// @param value The value to copy and insert.
1332 /// @return A pair containing an iterator referencing either the element found or the new
1333 /// element added. The bool component is \c true if the insertion took place and \c false
1334 /// if nothing was changed.
1335 //==============================================================================================
1336 std::pair<Iterator, bool> InsertIfNotExistent( const StoredType& value )
1337 { return InsertIfNotExistent( StoredType(value) ); }
1338
1339 //==============================================================================================
1340 /// Inserts a new mapped object only if no other object is contained that is associated
1341 /// already with the same key as given \p{key}.
1342 ///
1343 /// \note
1344 /// This method allows preventing the insertion of double entries.
1345 /// For more information, see
1346 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1347 /// of the documentation of this class.
1348 ///
1349 /// @param value A rvalue reference of a \p{StoredType} to insert.
1350 /// @return A pair containing an iterator referencing either the element found or the new
1351 /// element added.
1352 /// The bool component is \c true if the insertion took place and \c false if nothing
1353 /// was changed.
1354 //==============================================================================================
1355 std::pair<Iterator, bool> InsertIfNotExistent( StoredType&& value )
1356 {
1357 auto hashCode= THash{}( TValueDescriptor().Key(value) );
1358 return InsertIfNotExistent(std::move(value), hashCode);
1359 }
1360
1361 //==============================================================================================
1362 /// Overloaded version of method
1363 /// \alib{containers::HashTable;InsertIfNotExistent(StoredType&&)} which accepts the
1364 /// \p{hashCode} of the given \p{key} as a second parameter.
1365 ///
1366 /// @see Use cases of this method are discussed in reference documentation section
1367 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
1368 ///
1369 /// @param value A rvalue reference of a \p{StoredType} to insert.
1370 /// @param hashCode Pre-calculated hash code of \p{value}.
1371 /// @return A pair containing an iterator referencing either the element found or the new
1372 /// element added.
1373 /// The bool component is \c true if the insertion took place and \c false if nothing
1374 /// was changed.
1375 //==============================================================================================
1376 std::pair<Iterator, bool> InsertIfNotExistent( StoredType&& value, size_t hashCode )
1377 {DCS
1378 // search element
1379 std::pair<Iterator, bool> result= base::insertIfNotExists( TValueDescriptor().Key(value), hashCode );
1380
1381 // existed? Do nothing
1382 if( result.second == false )
1383 return result;
1384
1385 // placement-new for the value(using move constructor)
1386 new ( &result.first.element->value ) StoredType( std::move(value) );
1387
1388 return result;
1389 }
1390
1391 //==============================================================================================
1392 /// Inserts the element contained in the given \alib{containers::HashTable;ElementHandle} into
1393 /// this table, if no equal element exists. In the unsuccessful case, the given
1394 /// \b %ElementHandle remains set and can be reused.<br>
1395 ///
1396 /// Existing iterators remain valid.
1397 ///
1398 /// \note
1399 /// This method allows preventing the insertion of double entries.
1400 /// For more information, see
1401 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1402 /// of the documentation of this class.
1403 ///
1404 /// <p>
1405 /// \see
1406 /// Objects of type \b ElementHandle objects may be received using overloaded methods
1407 /// #Extract. The combination of \b %Extract and this method (as well as method
1408 /// #Insert(ElementHandle&) are the only way to change the <em>key-portion</em> of an element
1409 /// without element destruction/re-construction.
1410 ///
1411 /// @param handle A reference to a handle to an element, previously received with #Extract.
1412 /// @return If an empty handle is given, #end is returned.
1413 /// Otherwise, if no equal element existed, an iterator that refers to the inserted
1414 /// element is returned and the given \p{handle} is emptied.<br>
1415 /// If an equal element existed, the returned iterator refers to the existing element
1416 /// and the \p{handle} remains set (not empty).
1417 //==============================================================================================
1418 Iterator InsertIfNotExistent( ElementHandle& handle )
1419 {DCS
1420 if( handle.IsEmpty() )
1421 return Iterator( this, base::bucketCount, nullptr ); //end();
1422
1423 Element* element = handle.element;
1424 auto hashCode = THash{}( TValueDescriptor().Key( handle.element->value ) );
1425 auto bucketIdx= hashCode % base::bucketCount;
1426
1427 Element* existing= base::findElement( hashCode, TValueDescriptor().Key( element->value ), hashCode );
1428 if ( existing != nullptr )
1429 return Iterator( this, bucketIdx, existing );
1430
1431 handle.element= nullptr;
1432 element->fixHashCode( hashCode ); // the key might have been changed outside
1433
1434 bucketIdx= base::increaseSize( 1, hashCode );
1435 base::buckets[bucketIdx].pushFront( element );
1436 return Iterator( this, bucketIdx, element);
1437 }
1438
1439 //==============================================================================================
1440 /// Constructs a new element within this container.
1441 ///
1442 /// \note
1443 /// The use of this method may insert elements sharing the same key as already existing
1444 /// elements.
1445 /// For more information, see
1446 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1447 /// of the documentation of this class.
1448 ///
1449 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1450 /// @param args Variadic parameters to be forwarded to the constructor of the inserted
1451 /// instance of type #StoredType.
1452 /// @return An iterator referring to the element added.
1453 //==============================================================================================
1454 template<typename... TArgs>
1455 Iterator Emplace( TArgs&&... args )
1456 {DCS
1457 // Recycle node or create a new one
1458 Element* element= base::allocElement( 0 );
1459
1460 // placement-new
1461 new ( &element->value ) StoredType( std::forward<TArgs>(args)... );
1462
1463 // fix the hash code which was not available at allocation, yet.
1464 auto hashCode= THash{}( TValueDescriptor().Key( element->value ));
1465 element->fixHashCode( hashCode );
1466
1467 // insert to hash table
1468 base::increaseSize( 1 );
1469 auto bucketIdx= base::insertInBucket( element, hashCode );
1470 return Iterator( this, bucketIdx, element);
1471 }
1472
1473 //==============================================================================================
1474 /// Constructs a value within this container without checking to place it in the right
1475 /// position in respect to existing elements with the same <em>key-portion</em>.
1476 ///
1477 /// \attention
1478 /// This method must only be used if the caller guarantees that no other element is
1479 /// currently stored in this container having an equal <em>key-portion</em>.
1480 /// In such situations, this method is very efficient.<br>
1481 /// If one exists already, this hash table is not considered in a consistent state
1482 /// after the operation. I.e., method #EqualRange will discontinue to function properly.
1483 ///
1484 /// \attention
1485 /// In debug-compilations, an \alib assertion is raised, if an equal element exists.
1486 /// For this reason, performance differences to method #Insert will be seen only with
1487 /// release-compilations.
1488 ///
1489 /// \attention
1490 /// For more information, see
1491 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1492 /// of the documentation of this class.
1493 ///
1494 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1495 /// @param args Variadic parameters to be forwarded to the constructor of the
1496 /// element to insert whose <em>key-portion</em> has to be different to
1497 /// all currently contained elements.
1498 /// @return An iterator referring to the element added.
1499 //==============================================================================================
1500 template<typename... TArgs>
1501 Iterator EmplaceUnique( TArgs&&... args )
1502 {DCS
1503 // Recycle node or create a new one
1504 Element* element= base::allocElement(0);
1505
1506 // placement-new
1507 new ( &element->value ) StoredType( std::forward<TArgs>(args)... );
1508
1509 // replace hash code (which is available only now)
1510 auto hashCode= THash{}( TValueDescriptor().Key( element->value ));
1511 element->fixHashCode( hashCode );
1512
1513
1514 // insert to hash table
1515 auto bucketIdx= base::increaseSize( 1, hashCode );
1516 base::buckets[bucketIdx].pushFront( element );
1517 auto result= Iterator( this, bucketIdx, element);
1518
1519 #if ALIB_DEBUG
1520 // Check that this was the first of
1521 auto it= ConstLocalIterator( result.bucketIdx, base::buckets[result.bucketIdx].first() ); // cbegin();
1522 ALIB_ASSERT( it.element == result.element, "MONOMEM/HASHTABLE" ) // has to be the first inserted
1523 while( ++it != ConstLocalIterator( result.bucketIdx, nullptr ) ) //cend(result.bucketIdx)
1524 ALIB_ASSERT_ERROR( !base::areEqual(result.element, it.element ), "MONOMEM/HASHTABLE",
1525 "EmplaceUnique used while element with same key-portion existed!" )
1526 #endif
1527
1528 return result;
1529 }
1530
1531#if DOXYGEN
1532 //==============================================================================================
1533 /// Replaces an existing, respectively constructs a new element within this container.
1534 ///
1535 /// \note
1536 /// This method allows preventing the insertion of double entries.
1537 /// For more information, see
1538 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1539 /// of the documentation of this class.
1540 ///
1541 /// \par Availability
1542 /// This method is available if this templated type is instantiated with
1543 /// \ref alib_ns_containers_hashtable_setandmap "hash map mode"
1544 /// or for hash sets that only define a subset of \p{StoredType} as a key type \p{TKey} and
1545 /// whose stored type \p{StoredType} is constructible if given a key value and the variadic
1546 /// template arguments.
1547 ///
1548 ///
1549 /// @tparam TRequires Used to disable this method where not available.<br>
1550 /// Defaulted and must not be specified with invocations.
1551 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1552 /// @param key The key to use for search and insertion.
1553 /// @param args Variadic parameters to be forwarded to the constructor of the mapped object
1554 /// of type <c>\p{MappedType}</c>.
1555 /// @return A pair containing an iterator referring to the element added.
1556 /// The bool component is \c true if the insertion took place and \c false if the
1557 /// assignment took place.
1558 //==============================================================================================
1559 template<typename TRequires= MappedType, typename... TArgs>
1560 requires(!std::same_as<TRequires, StoredType>)
1561 std::pair<Iterator, bool> EmplaceOrAssign( const KeyType& key, TArgs&&... args);
1562#else
1563 template<typename TRequires= MappedType, typename... TArgs>
1564 requires(!std::same_as<TRequires, StoredType>)
1565 std::pair<Iterator, bool> EmplaceOrAssign( const KeyType& key, TArgs&&... args)
1566 {DCS
1567 // insert to hash table
1568 std::pair<Iterator, bool> result= base::insertOrGet( key, THash{}(key) );
1569
1570 // if an existing element was found, we have to destruct the currently mapped object
1571 if( result.second == false )
1572 lang::Destruct( TValueDescriptor().Mapped( result.first.element->value ) );
1573
1574 // if otherwise an insertion took place, we have to copy the key
1575 else
1576 new (&TValueDescriptor().Key( result.first.element->value )) KeyType( key );
1577
1578 // placement-new for the mapped object
1579 new ( &TValueDescriptor().Mapped( result.first.element->value )) MappedType( std::forward<TArgs>( args)... );
1580
1581 return result;
1582 }
1583
1584 // set mode
1585 template<typename TRequires= MappedType, typename... TArgs>
1586 requires( std::same_as<TRequires, StoredType>
1587 && std::is_constructible< StoredType,
1588 const KeyType&,
1589 TArgs&&... >::value )
1590 std::pair<Iterator, bool> EmplaceOrAssign( const KeyType& key, TArgs&&... args)
1591 {DCS
1592 // insert to hash table
1593 std::pair<Iterator, bool> result= base::insertOrGet( key, THash{}(key) );
1594
1595 // if an existing element was found, we have to destruct the whole object
1596 if( result.second == false )
1597 lang::Destruct( result.first.element->value );
1598
1599 // placement-new for the whole object
1600 new (&result.first.element->value) StoredType( key, std::forward<TArgs>( args)... );
1601
1602 return result;
1603 }
1604#endif
1605
1606 //==============================================================================================
1607 /// Inserts a new element only if no other element is contained equals to the one
1608 /// that is constructed by \p{args}.
1609 ///
1610 /// \note
1611 /// This method allows preventing the insertion of double entries.
1612 /// For more information, see
1613 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1614 /// of the documentation of this class.
1615 /// <p>
1616 /// \note
1617 /// For comparison, a local object of type #StoredType is constructed. In case an equal
1618 /// object exists, it is destructed. Otherwise it is moved into this container.
1619 ///
1620 /// \par Availability
1621 /// This method is available only if this templated type is instantiated with
1622 /// \ref alib_ns_containers_hashtable_setandmap "hash set mode". For <em>hash map mode</em>,
1623 /// use overloaded version #EmplaceIfNotExistent(const KeyType& key, TArgs&&... args).
1624 /// \par
1625 /// Furthermore it is available only if custom type \p{StoredType} has a move constructor.
1626 ///
1627 /// \attention
1628 /// If a move constructor exists, but is not duly defined, the method produces undefined
1629 /// behavior.<br>
1630 /// An alternative version that does not require a move constructor is found with
1631 /// #EmplaceIfNotExistent(const KeyType& key, TArgs&&... args). This can be used for hash sets
1632 /// that define a subset of \p{StoredType} as a key type \p{TKey} and whose stored type
1633 /// is constructible from a constant <em>key-portion</em> and the variadic template arguments.
1634 ///
1635 /// @tparam TRequires Used to disable this method where not available.
1636 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.<br>
1637 /// Defaulted and must not be specified with invocations.
1638 /// @param args Variadic parameters to be forwarded to the constructor of \p{StoredType}.
1639 /// @return A pair containing an iterator referencing either the element found or the new
1640 /// element added.
1641 /// The bool component is \c true if the insertion took place and \c false nothing
1642 /// was changed.
1643 //==============================================================================================
1644 template<typename TRequires= MappedType, typename... TArgs>
1645 requires ( std::same_as<TRequires, StoredType>
1646 && std::is_move_constructible<StoredType>::value )
1647 std::pair<Iterator, bool> EmplaceIfNotExistent( TArgs&&... args)
1648 {DCS
1649 StoredType value( std::forward<TArgs>( args)... );
1650
1651 // search element
1652 std::pair<Iterator, bool> result= base::insertIfNotExists( TValueDescriptor().Key(value),
1653 THash{}(TValueDescriptor().Key(value)) );
1654
1655 // existed? Do nothing
1656 if( result.second == false )
1657 return result;
1658
1659 // placement-new moving the locally created object
1660 new ( &result.first.element->value ) StoredType( std::move(value) );
1661
1662 return result;
1663 }
1664
1665#if DOXYGEN
1666 //==============================================================================================
1667 /// Inserts a new mapped object only if no other object is contained that is associated
1668 /// already with a key that equals the given \p{key}.
1669 ///
1670 /// \note
1671 /// This method allows preventing the insertion of double entries.
1672 /// For more information, see
1673 /// \ref alib_ns_containers_hashtable_single_multi "Single And Multiple Entries"
1674 /// of the documentation of this class.
1675 ///
1676 /// \par Availability
1677 /// This method is available if this templated type is instantiated with
1678 /// \ref alib_ns_containers_hashtable_setandmap "hash map mode"
1679 /// or for hash sets that only define a subset of \p{StoredType} as a key type \p{TKey} and
1680 /// whose stored type is constructible if given a key value and the variadic template
1681 /// arguments.
1682 ///
1683 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1684 /// @param key The key to use for search and insertion.
1685 /// @param args Variadic parameters to be forwarded to the constructor of the mapped object
1686 /// of type <c>\p{MappedType}</c>.
1687 /// @return A pair containing an iterator referencing either the element found or the new
1688 /// element added.
1689 /// The bool component is \c true if the insertion took place and \c false nothing
1690 /// was changed.
1691 //==============================================================================================
1692 template<typename... TArgs>
1693 std::pair<Iterator, bool> EmplaceIfNotExistent( const KeyType& key, TArgs&&... args);
1694#else
1695 template<typename... TArgs>
1696 requires( !std::is_constructible< StoredType, const KeyType&, TArgs&&... >::value )
1697 std::pair<Iterator, bool> EmplaceIfNotExistent( const KeyType& key, TArgs&&... args)
1698 {DCS
1699 // search element
1700 std::pair<Iterator, bool> result= base::insertIfNotExists( key, THash{}(key) );
1701
1702 // existed? Do nothing
1703 if( result.second == false )
1704 return result;
1705
1706 // placement-new for the key (using copy constructor)
1707 new (&TValueDescriptor().Key(result.first.element->value)) KeyType( key );
1708
1709 // placement-new for the mapped object (using custom constructor)
1710 new (&TValueDescriptor().Mapped(result.first.element->value)) MappedType( std::forward<TArgs>( args)... );
1711
1712 return result;
1713 }
1714
1715 template<typename... TArgs>
1716 requires(std::is_constructible< StoredType, const KeyType&, TArgs&&...>::value )
1717 std::pair<Iterator, bool> EmplaceIfNotExistent( const KeyType& key, TArgs&&... args)
1718 {DCS
1719 // search element
1720 std::pair<Iterator, bool> result= base::insertIfNotExists( key, THash{}(key) );
1721
1722 // existed? Do nothing
1723 if( result.second == false )
1724 return result;
1725
1726 // placement-new for the element passing key and args together
1727 new (&result.first.element->value) StoredType( key, std::forward<TArgs>( args)... );
1728
1729 return result;
1730 }
1731#endif
1732
1733 //##############################################################################################
1734 /// @name Element Search
1735 //##############################################################################################
1736 //==============================================================================================
1737 /// Returns an iterator pointing to the first element of equal key value.
1738 ///
1739 /// \note
1740 /// The iterator returned may be incremented. It is ensured that further elements contained
1741 /// in this hash table with the same key are consecutively following this first element
1742 /// returned. However, the iterator does \b not end with the last element of that key.
1743 ///
1744 /// \see
1745 /// Method #EqualRange, which also returns an iterator pointing behind the last element
1746 /// with that key.
1747 ///
1748 ///
1749 /// @param key The key to search for.
1750 /// @return An iterator pointing to the first element found with equal <em>key-portion</em>,
1751 /// respectively, one being equal to #end, if no element was found with \p{key}.
1752 //==============================================================================================
1753 Iterator Find( const KeyType& key )
1754 {DCSSHRD
1755 auto hashCode = THash{}(key);
1756 auto bucketIdx= hashCode % base::bucketCount;
1757 Element* elem = base::findElement( bucketIdx, key, hashCode );
1758 return Iterator( this, elem == nullptr ? base::bucketCount : bucketIdx, elem );
1759 }
1760
1761 //==============================================================================================
1762 /// Searches an element.
1763 /// @param key The key to search for.
1764 /// @return An iterator pointing to the first element found with equal <em>key-portion</em>,
1765 /// respectively, one being equal to #end, if no element was found with \p{key}.
1766 //==============================================================================================
1767 ConstIterator Find( const KeyType& key ) const
1768 {DCSSHRD
1769 auto hashCode = THash{}(key);
1770 auto bucketIdx= hashCode % base::bucketCount;
1771 Element* elem = base::findElement( bucketIdx, key, hashCode );
1772 return ConstIterator( this, elem == nullptr ? base::bucketCount : bucketIdx, elem );
1773 }
1774
1775 //==============================================================================================
1776 /// Overloaded version of method \alib{containers::HashTable;Find(const KeyType&)} which
1777 /// accepts the \p{hashCode} of the given \p{key} as a second parameter.
1778 ///
1779 /// @see Use cases of this method are discussed in reference documentation section
1780 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
1781 ///
1782 /// @param key The key to search for.
1783 /// @param hashCode Pre-calculated hash code of \p{key}.
1784 /// @return An iterator pointing to the first element found with equal <em>key-portion</em>,
1785 /// respectively, one being equal to #end, if no element was found with \p{key}.
1786 //==============================================================================================
1787 Iterator Find( const KeyType& key, size_t hashCode )
1788 {DCSSHRD
1789 auto bucketIdx= hashCode % base::bucketCount;
1790 Element* elem = base::findElement( bucketIdx, key, hashCode );
1791 return Iterator( this, elem == nullptr ? base::bucketCount : bucketIdx, elem );
1792 }
1793
1794 //==============================================================================================
1795 /// Overloaded version of method \alib{containers::HashTable;Find(const KeyType&)const} which
1796 /// accepts the \p{hashCode} of the given \p{key} as a second parameter.
1797 ///
1798 /// @see Use cases of this method are discussed in reference documentation section
1799 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
1800 ///
1801 /// @param key The key to search for.
1802 /// @param hashCode Pre-calculated hash code of \p{key}.
1803 /// @return An iterator pointing to the first element found with equal <em>key-portion</em>,
1804 /// respectively, one being equal to #end, if no element was found with \p{key}.
1805 //==============================================================================================
1806 ConstIterator Find( const KeyType& key, size_t hashCode ) const
1807 {DCSSHRD
1808 auto bucketIdx= hashCode % base::bucketCount;
1809 Element* elem = base::findElement( bucketIdx, key, hashCode );
1810 return ConstIterator( this, elem == nullptr ? base::bucketCount : bucketIdx, elem );
1811 }
1812
1813 //==============================================================================================
1814 /// Tests if an element with given \p{key} is stored in this container.
1815 /// @param key The key to search for.
1816 /// @return \c true if this hash table contains at least one element with given
1817 /// <em>key-portion</em> \p{key}, \c false otherwise.
1818 //==============================================================================================
1819 bool Contains( const KeyType& key ) const
1820 {DCSSHRD
1821 auto hashCode= THash{}(key);
1822 return base::findElement(hashCode % base::bucketCount, key, hashCode )
1823 != nullptr;
1824 }
1825
1826 //==============================================================================================
1827 /// Searches a key and returns a pair of iterators. The first is pointing to the first
1828 /// element of the range, the second is pointing to the first element past the range.
1829 ///
1830 /// If both iterators are equal, the range is empty (both iterators will be equal to #end).
1831 ///
1832 /// @param key The key to search for.
1833 /// @return A pair of iterators defining the range of elements with key \p{key}.
1834 //==============================================================================================
1835 std::pair<Iterator,Iterator> EqualRange(const KeyType& key )
1836 {DCSSHRD return base::findRange( key ); }
1837
1838 //==============================================================================================
1839 /// Searches a key and returns a pair of iterators. The first is pointing to the first
1840 /// element of the range, the second is pointing to the first element past the range.
1841 ///
1842 /// If both iterators are equal, the range is empty (both iterators will be equal to #end).
1843 ///
1844 /// @param key The key to search for.
1845 /// @return A pair of iterators defining the range of elements with key \p{key}.
1846 //==============================================================================================
1847 std::pair<ConstIterator,ConstIterator> EqualRange(const KeyType& key ) const
1848 {DCSSHRD return base::findRange( key ); }
1849
1850 //##############################################################################################
1851 /// @name Element Removal
1852 //##############################################################################################
1853 //==============================================================================================
1854 /// Extracts the first element found with the given key from the hash table and returns a
1855 /// handle to it.<br>
1856 /// Extracting an element invalidates only the iterators to the extracted element and preserves
1857 /// the relative order of the elements that are not extracted.
1858 ///
1859 /// Extracting and re-inserting nodes is the only way to change a key of an element without
1860 /// performing reallocation and or destruction/construction.
1861 ///
1862 /// @param key The key to search a first element for.
1863 /// @return A handle to an element that allows changes of the formerly stored value.
1864 /// Changes may include the <em>key-portion</em> of the data stored.
1865 /// Handles may be passed to one of the overloaded insert methods.
1866 /// If no element was found, the returned handle is empty.
1867 //==============================================================================================
1868 ElementHandle Extract(const KeyType& key )
1869 { return Extract( key, THash{}(key) ); }
1870
1871 //==============================================================================================
1872 /// Overloaded version of method \alib{containers::HashTable;Extract(const KeyType&)} which
1873 /// accepts the \p{hashCode} of the given \p{key} as a second parameter.
1874 ///
1875 /// @see Use cases of this method are discussed in reference documentation section
1876 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
1877 ///
1878 /// @param key The key to search a first element for.
1879 /// @param hashCode Pre-calculated hash code of \p{key}.
1880 /// @return A handle to an element that allows changes of the formerly stored value.
1881 /// Changes may include the <em>key-portion</em> of the data stored.
1882 /// Handles may be passed to one of the overloaded insert methods.
1883 /// If no element was found, the returned handle is empty.
1884 //==============================================================================================
1885 ElementHandle Extract(const KeyType& key, size_t hashCode )
1886 {DCS
1887 Node* previous= base::findElementBefore( hashCode % base::bucketCount, hashCode, key );
1888 if( previous == nullptr )
1889 return ElementHandle(this, nullptr);
1890
1891 Element* element= previous->next();
1892 previous->removeNext();
1893 --base::size;
1894 return ElementHandle( this, element );
1895 }
1896
1897 //==============================================================================================
1898 /// Extracts the first element found with the given key from the hash table and returns a
1899 /// handle to it.<br>
1900 /// If the iterator was not valid (i.e., #end), the method has undefined behavior.
1901 /// With debug-builds an \alib assertion is raised.
1902 ///
1903 /// Extracting a element invalidates only the iterators to the extracted element, and preserves
1904 /// the relative order of the elements that are not extracted.
1905 ///
1906 /// Extracting and re-inserting nodes is the only way to change a key of an element without
1907 /// performing reallocation and or destruction/construction.
1908 ///
1909 /// @param pos The position of the element to extract.
1910 /// @return A handle to an element that allows changes of the formerly stored value.
1911 /// Changes may include the <em>key-portion</em> of the data stored.
1912 /// Handles may be passed to one of the overloaded insert methods.
1913 /// If no element was found, the returned handle is empty.
1914 //==============================================================================================
1915 ElementHandle Extract( ConstIterator pos )
1916 {DCS
1917 ALIB_ASSERT_ERROR( pos.element != nullptr
1918 && pos.table != nullptr ,
1919 "MONOMEM/HASHTABLE", "Illegal iterator." )
1920
1921 Node* previous= base::buckets[pos.bucketIdx].findLastBefore( pos.element );
1922 ALIB_ASSERT_ERROR( previous != nullptr, "MONOMEM/HASHTABLE",
1923 "Illegal iterator: Element not found." )
1924
1925 previous->removeNext();
1926 --base::size;
1927 return ElementHandle( this, pos.element );
1928 }
1929
1930 //==============================================================================================
1931 /// Erases all elements stored with the given key.
1932 ///
1933 /// @param key The key to search elements for deletion.
1934 /// @return The number of elements removed.
1935 //==============================================================================================
1936 integer erase(const KeyType& key )
1937 { return Erase( key, THash{}(key) ); }
1938
1939 //==============================================================================================
1940 /// Overloaded version of method \alib{containers::HashTable;erase(const KeyType&)}
1941 /// which accepts the \p{hashCode} of the given \p{key} as a second parameter.
1942 ///
1943 /// @see Use cases of this method are discussed in reference documentation section
1944 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
1945 ///
1946 /// @param key The key to search elements for deletion.
1947 /// @param hashCode Pre-calculated hash code of \p{key}.
1948 /// @return The number of elements removed.
1949 //==============================================================================================
1950 integer Erase(const KeyType& key, size_t hashCode )
1951 {DCS
1952 // search start
1953 Node* beforeFirst= base::findElementBefore( hashCode % base::bucketCount, hashCode, key );
1954 if( beforeFirst == nullptr )
1955 return 0;
1956
1957 // search end
1958 Element* end= beforeFirst->next();
1959 while( end && base::areEqual( end, key, hashCode ) )
1960 end= end->next();
1961
1962 // erase and add to recycler
1963 auto result= base::recyclerType::RecycleList(beforeFirst->next(), end);
1964 beforeFirst->next( end );
1965
1966 base::size-= result.second;
1967 return result.second;
1968 }
1969
1970 //==============================================================================================
1971 /// Erases the unique element with the given key.
1972 ///
1973 /// \note
1974 /// This method is slightly more efficient than method #erase(const KeyType&), as it will
1975 /// not search for a next element with an equal key.<br>
1976 /// In debug-compilations, the method asserts that no second element with the same \p{key}
1977 /// is available.<br>
1978 /// If this table is supposed to
1979 /// \ref alib_ns_containers_hashtable_single_multi "store only unique elements", the
1980 /// use of this method is therefore recommended, as an assertions hints to an erroneous use
1981 /// of the insertion methods.
1982 ///
1983 /// @param key The key to search elements for deletion.
1984 /// @return \c true if an element was found and removed, \c false otherwise.
1985 //==============================================================================================
1986 bool EraseUnique( const KeyType& key )
1987 { return EraseUnique( key, THash{}(key) ); }
1988
1989
1990 //==============================================================================================
1991 /// Overloaded version of method \alib{containers::HashTable;EraseUnique(const KeyType&)} which
1992 /// accepts the \p{hashCode} of the given \p{key} as a second parameter.
1993 ///
1994 /// @see Use cases of this method are discussed in reference documentation section
1995 /// \ref alib_ns_containers_hashtable_hashprecalc "6.2 Hash Code Pre-calculation".
1996 ///
1997 /// @param key The key to search elements for deletion.
1998 /// @param hashCode Pre-calculated hash code of \p{key}.
1999 /// @return \c true if an element was found and removed, \c false otherwise.
2000 //==============================================================================================
2001 bool EraseUnique( const KeyType& key, size_t hashCode )
2002 {DCS
2003 Node* before= base::findElementBefore( hashCode % base::bucketCount, hashCode, key );
2004 if( before == nullptr )
2005 return false;
2006
2007 ALIB_ASSERT_ERROR( before->next()->next() == nullptr
2008 || !base::areEqual( before->next()->next(), key, hashCode ),
2009 "MONOMEM/HASHTABLE", "More than one element found matching the given key" )
2010
2011 Element* elem= before->removeNext();
2012 base::recyclerType::Recycle(elem);
2013
2014 --base::size;
2015 return true;
2016 }
2017
2018
2019 //==============================================================================================
2020 /// Removes an element specified by an iterator.<br>
2021 /// If the iterator was not valid (i.e #end), the method has undefined behavior.
2022 /// With debug-builds an \alib assertion is raised.
2023 ///
2024 /// The order of the elements that are not erased is preserved, what makes it possible to
2025 /// erase individual elements while iterating through the container.
2026 ///
2027 /// @param pos The iterator to the element to remove.
2028 /// @return An iterator following the removed element.
2029 //==============================================================================================
2031 {DCS
2032 ALIB_ASSERT_ERROR( pos.element != nullptr
2033 && pos.table != nullptr ,
2034 "MONOMEM/HASHTABLE", "Illegal iterator." )
2035
2036 Iterator result( this, pos.bucketIdx, pos.element );
2037 ++result;
2038
2039 // search pointer to element before pos
2040 Node* previous= base::buckets[pos.bucketIdx].findLastBefore( pos.element );
2041 ALIB_ASSERT_ERROR( previous != nullptr, "MONOMEM/HASHTABLE",
2042 "Illegal iterator: Element not found." )
2043
2044
2045 Element* toDelete= previous->removeNext();
2046 base::recyclerType::Recycle(toDelete);
2047
2048 --base::size;
2049 return result;
2050 }
2051
2053 //==============================================================================================
2054 /// Removes all elements from the given position \p{start} to the element
2055 /// before given position \p{end}.
2056 ///
2057 /// The order of the elements that are not erased is preserved, what makes it possible to
2058 /// erase individual elements while iterating through the container.
2059 ///
2060 /// @param start The iterator to the element to remove.
2061 /// @param end The first element not to remove.
2062 /// @return An iterator following the last removed element.
2063 //==============================================================================================
2065 {DCS
2066 ALIB_ASSERT_ERROR( start.element != nullptr
2067 && start.table != nullptr ,
2068 "MONOMEM/HASHTABLE", "Illegal iterator." )
2069
2070 ALIB_ASSERT_ERROR( start.table == end.table, "MONOMEM/HASHTABLE",
2071 "Iterators are referring to different hash tables." )
2072
2073 if( start.element == end.element )
2074 return Iterator(this, start.bucketIdx, start.element );
2075
2076 // loop over all buckets in question
2077 for( uinteger bucketIdx= start.bucketIdx; bucketIdx <= end.bucketIdx; ++bucketIdx )
2078 {
2079 // end of buckets? Return iterator that marks hashtable end
2080 if( bucketIdx == base::bucketCount )
2081 return HashTable::end();
2082
2083 // find the previous pointer to the start node:
2084 Node* previous;
2085 if( bucketIdx == start.bucketIdx ) // With the first bucket in the loop, this has to be searched...
2086 {
2087 // search pointer to element before start
2088 previous= base::buckets[start.bucketIdx].findLastBefore( start.element );
2089 ALIB_ASSERT_ERROR( previous != nullptr, "MONOMEM/HASHTABLE",
2090 "Illegal iterator: Element not found." )
2091 }
2092 else // ...afterwards, its of course just the bucket that points to it
2093 {
2094 if( base::buckets[bucketIdx].isEmpty() )
2095 continue;
2096 previous= &base::buckets[bucketIdx];
2097 }
2098
2099 // destruct either to end of list or to end-iterator element
2100 if ( bucketIdx < end.bucketIdx )
2101 {
2102 base::size-= previous->count();
2103 base::recyclerType::RecycleList( previous->next() );
2104 previous->next( nullptr );
2105 }
2106 else
2107 {
2108 auto pair= base::recyclerType::RecycleList(previous->next(), end.element );
2109 previous->next( end.element );
2110 base::size-= pair.second;
2111
2112 return Iterator( this, bucketIdx, end.element );
2113 }
2114 }
2115 }
2117
2118
2119 //==============================================================================================
2120 /// Removes an element specified by a bucket iterator.
2121 /// Bucket iterators are receivable using overloaded methods #begin(uinteger) and
2122 /// \alib{containers::HashTable;cbegin(uinteger)const;cbegin(uinteger)}.
2123 ///
2124 /// The order of the elements that are not erased is preserved, what makes it possible to
2125 /// erase individual elements while iterating through the container.
2126 ///
2127 /// @param pos The iterator to the element to remove.
2128 /// @return An iterator following the removed element.
2129 //==============================================================================================
2131 {DCS
2132 ALIB_ASSERT_ERROR( pos.element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
2133
2134 LocalIterator result( pos.bucketIdx, pos.element->next() );
2135
2136 Element* element= pos.element;
2137 base::buckets[pos.bucketIdx].findAndRemove( element );
2138 base::recyclerType::Recycle( element);
2139 --base::size;
2140
2141 return result;
2142 }
2143
2144 //==============================================================================================
2145 /// Removes all element from the given bucket iterator position \p{start} to the element
2146 /// before given position \p{end}.
2147 ///
2148 /// The order of the elements that are not erased is preserved, what makes it possible to
2149 /// erase individual elements while iterating through the container.
2150 ///
2151 /// @param start The bucket iterator to the element to remove.
2152 /// @param end The bucket iterator to the first element not to remove.
2153 /// @return An iterator following the last removed element.
2154 //==============================================================================================
2156 {DCS
2157 ALIB_ASSERT_ERROR( start.element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
2158
2159 Node* previous= base::buckets[start.bucketIdx].findLastBefore( start.element );
2160 ALIB_ASSERT_ERROR( previous != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
2161 if( start.element == end.element )
2162 return LocalIterator( start.bucketIdx, start.element );
2163
2164 previous->next( end.element );
2165 auto pair= base::recyclerType::RecycleList( start.element, end.element );
2166
2167 base::size-= pair.second;
2168
2169 return LocalIterator( start.bucketIdx, end.element );
2170 }
2171
2172 //##############################################################################################
2173 /// @name std::iterator_traits Interface
2174 //##############################################################################################
2175
2176 /// Returns an iterator referring to a mutable element at the start of this table.
2177 /// @return The first of element in this container.
2178 Iterator begin() { return Iterator ( this, 0 ); }
2179
2180 /// Returns an iterator referring to a mutable, non-existing element.
2181 /// @return The end of the list of elements in this container.
2182 Iterator end() {DCSSHRD
2183 return Iterator ( this, base::bucketCount, nullptr ); }
2184
2185 /// Returns an iterator referring to a constant element at the start of this container.
2186 /// @return The first of element in this container.
2187 ConstIterator begin() const { return ConstIterator( this, 0 ); }
2188
2189 /// Returns an iterator referring to a constant, non-existing element.
2190 /// @return The end of the list of elements in this container.
2191 ConstIterator end() const {DCSSHRD
2192 return ConstIterator( this, base::bucketCount, nullptr); }
2193
2194 /// Returns an iterator referring to a constant element at the start of this container.
2195 /// @return The first of element in this container.
2196 ConstIterator cbegin() const { return ConstIterator( this, 0 ); }
2197
2198 /// Returns an iterator referring to a constant, non-existing element.
2199 /// @return The end of the list of elements in this container.
2200 ConstIterator cend() const {DCSSHRD
2201 return ConstIterator( this, base::bucketCount, nullptr); }
2202
2203 /// Returns an iterator referring to a mutable element at the start of bucket of index
2204 /// \p{bucketNumber}.
2205 /// @param bucketNumber The bucket to iterate on.
2206 /// @return The first element in bucket \p{bucketNumber}.
2208 {DCSSHRD
2209 ALIB_ASSERT_ERROR( bucketNumber < base::bucketCount, "MONOMEM/HASHTABLE",
2210 "Bucket number out of range: {}>={}.", bucketNumber, base::bucketCount )
2211 return LocalIterator( bucketNumber, base::buckets[bucketNumber].first() );
2212 }
2213
2214 /// Returns an iterator referring to a constant, non-existing element in bucket of index
2215 /// \p{bucketNumber}.
2216 /// @param bucketNumber The bucket to iterate on.
2217 /// @return The end of the list of elements in bucket \p{bucketNumber}.
2219 {DCSSHRD
2220 ALIB_ASSERT_ERROR( bucketNumber < base::bucketCount, "MONOMEM/HASHTABLE",
2221 "Bucket number out of range: {}>={}.", bucketNumber, base::bucketCount )
2222 return LocalIterator( bucketNumber, nullptr );
2223 }
2224
2225 /// Returns an iterator referring to a mutable element at the start of bucket of index
2226 /// \p{bucketNumber}.
2227 /// @param bucketNumber The bucket to iterate on.
2228 /// @return The first element in bucket \p{bucketNumber}.
2229 ConstLocalIterator begin( uinteger bucketNumber ) const
2230 {DCSSHRD
2231 ALIB_ASSERT_ERROR( bucketNumber < base::bucketCount, "MONOMEM/HASHTABLE",
2232 "Bucket number out of range: {}>={}.", bucketNumber, base::bucketCount )
2233 return ConstLocalIterator( bucketNumber, base::buckets[bucketNumber].first() );
2234 }
2235
2236 /// Returns an iterator referring to a constant, non-existing element in bucket of index
2237 /// \p{bucketNumber}.
2238 /// @param bucketNumber The bucket to iterate on.
2239 /// @return The end of the list of elements in bucket \p{bucketNumber}.
2240 ConstLocalIterator end( uinteger bucketNumber ) const
2241 {DCSSHRD
2242 ALIB_ASSERT_ERROR( bucketNumber < base::bucketCount, "MONOMEM/HASHTABLE",
2243 "Bucket number out of range: {}>={}.", bucketNumber, base::bucketCount )
2244 return ConstLocalIterator( bucketNumber, nullptr );
2245 }
2246
2247 /// Returns an iterator referring to a mutable element at the start of bucket of index
2248 /// \p{bucketNumber}.
2249 /// @param bucketNumber The bucket to iterate on.
2250 /// @return The first element in bucket \p{bucketNumber}.
2251 ConstLocalIterator cbegin( uinteger bucketNumber ) const
2252 {DCSSHRD
2253 ALIB_ASSERT_ERROR( bucketNumber < base::bucketCount, "MONOMEM/HASHTABLE",
2254 "Bucket number out of range: {}>={}.", bucketNumber, base::bucketCount )
2255 return ConstLocalIterator( bucketNumber, base::buckets[bucketNumber].first() );
2256 }
2257
2258 /// Returns an iterator referring to a constant, non-existing element in bucket of index
2259 /// \p{bucketNumber}.
2260 /// @param bucketNumber The bucket to iterate on.
2261 /// @return The end of the list of elements in bucket \p{bucketNumber}.
2262 ConstLocalIterator cend( uinteger bucketNumber ) const
2263 {DCSSHRD
2264 ALIB_ASSERT_ERROR( bucketNumber < base::bucketCount, "MONOMEM/HASHTABLE",
2265 "Bucket number out of range: {}>={}.", bucketNumber, base::bucketCount )
2266 return ConstLocalIterator( bucketNumber, nullptr );
2267 }
2268}; // class Hashtable
2269
2270
2271// #################################################################################################
2272// #################################################################################################
2273// Debug Functions
2274// #################################################################################################
2275// #################################################################################################
2276#if ALIB_DEBUG_CONTAINERS
2277#include "ALib.Lang.CIFunctions.H"
2278/// Generates statistics on the given hash table. The meanings of the returned tuple are:
2279/// 0. The expected average size of a bucket (simply table size divided by number of buckets).
2280/// 1. The <em>standard deviation</em> of the buckets. The lower this value, the better
2281/// is the hash algorithm used. A value of <c>1.0</c> denotes the <em>gaussian distribution</em>
2282/// which indicates perfect randomness. However, this value is unlikely (impossible) to be
2283/// achieved.
2284/// 2. The minimum number of elements found in a bucket.
2285/// 3. The maximum number of elements found in a bucket.
2286///
2287/// \par Availability
2288/// Available only if the compiler-symbol \ref ALIB_DEBUG_CONTAINERS is set.
2289///
2290/// \see
2291/// Sibling namespace functions \alib{containers;DbgDumpDistribution} and
2292/// \alib{containers;DbgDumpHashtable} provided for debugging and optimization.
2293///
2294/// @tparam THashtable A specification of templated type \alib{containers;HashTable}.
2295/// Deduced by the compiler by given parameter \p{hashtable}.
2296/// @param hashtable The hashtable to investigate on.
2297/// @return The tuple as described above.
2298template<typename THashtable>
2299inline
2300std::tuple<double,double,integer,integer>
2301DbgGetHashTableDistribution(const THashtable& hashtable )
2302{
2303 auto qtyBuckets = hashtable.BucketCount();
2304 double averageExpected = double(hashtable.Size()) / double(qtyBuckets);
2305 uinteger minimum = std::numeric_limits<uinteger>::max();
2306 uinteger maximum = std::numeric_limits<uinteger>::min();
2307 double diffs = 0.0;
2308 integer sumCheck = 0;
2309 for( uinteger i= 0 ; i < qtyBuckets ; ++i )
2310 {
2311 auto bucketSize= hashtable.BucketSize( i );
2312 sumCheck+= bucketSize;
2313 if( minimum > bucketSize ) minimum= bucketSize;
2314 if( maximum < bucketSize ) maximum= bucketSize;
2315
2316 double diff= averageExpected - double(bucketSize);
2317 diffs+= diff > 0 ? diff : - diff;
2318 }
2319
2320 ALIB_ASSERT_ERROR( sumCheck == hashtable.Size(), "MONOMEM/HASHTABLE",
2321 "Error: Hashtable::Size() and sum of bucket sizes differ: {}!={}", hashtable.Size(),sumCheck )
2322 double deviation= diffs / double(qtyBuckets);
2323
2324 return std::make_tuple( averageExpected, deviation, minimum, maximum );
2325}
2326
2327
2328#include "ALib.Lang.CIMethods.H"
2329#endif //ALIB_DEBUG_CONTAINERS
2330
2331//==================================================================================================
2332//===================================== HashSet =============================================
2333//==================================================================================================
2334
2335/// This type definition is a shortcut to \alib{containers;HashTable}, usable if the full
2336/// portion of the data stored in the container is used for the comparison of values.
2337///
2338/// \note
2339/// As with this definition template type \p{TKey} equals stored type \p{StoredType}, methods of
2340/// target type \alib{containers;HashTable} that accept an object of template type
2341/// \b TKey expect an object of \p{StoredType} when this type is used.<br>
2342/// In case this is not wanted (or possible), and only the true key-portion should be expected
2343/// by interface functions such as \alib{containers;HashTable::Find}, the original
2344/// type has to be used. Here, typically template parameter \p{TValueDescriptor} can be
2345/// set to \alib{containers;TSubsetKeyDescriptor}.
2346///
2347/// \see
2348/// For a detailed description of this type, see original type
2349/// \alib{containers;HashTable}, as well as alternative type definition
2350/// \alib{containers;HashMap}.
2351///
2352/// @tparam TAllocator The allocator type to use, as prototyped with \alib{lang;Allocator}.
2353/// @tparam T The element type stored with this container.
2354/// This type is published as \alib{containers;HashTable::StoredType}
2355/// and type definition \alib{containers;HashTable::KeyType} becomes
2356/// a synonym.
2357/// @tparam THash The hash functor applicable to \p{T}.<br>
2358/// Defaults to <c>std::hash<T></c> and is published as
2359/// \alib{containers;HashTable::HashType}.
2360/// @tparam TEqual The comparison functor on \p{T}.<br>
2361/// Defaults to <c>std::equal_to<T></c> and is published as
2362/// \alib{containers;HashTable::EqualType}.
2363/// @tparam THashCaching Determines if hash codes are cached when elements are inserted.<br>
2364/// Defaults to <b>Caching::Auto</b>, which enables caching if
2365/// <c>std::is_arithmetic<StoredType>::value</c> evaluates to \c false.
2366/// @tparam TRecycling Denotes the type of recycling that is to be performed. Possible values are
2367/// \alib{containers;Recycling;None},
2368/// \alib{containers;Recycling;Private} (the default), or
2369/// \alib{containers;Recycling;Shared}.
2370template< typename TAllocator,
2371 typename T,
2372 typename THash = std::hash <T>,
2373 typename TEqual = std::equal_to<T>,
2374 lang::Caching THashCaching = lang::Caching::Auto,
2375 Recycling TRecycling = Recycling::Private >
2376using HashSet= HashTable< TAllocator,
2378 THash, TEqual,
2379 THashCaching,
2380 TRecycling >;
2381
2382//==================================================================================================
2383//=================================== HashMap ==============================================
2384//==================================================================================================
2385
2386/// This type definition is a shortcut to \alib{containers;HashTable}, usable if data
2387/// stored in the container does not include a key-portion, and thus the key to the data
2388/// is to be separately defined.<br>
2389/// To achieve this, this type definition aggregates types \p{TKey} and \p{TMapped} into a
2390/// <c>std::pair<TKey,TMapped></c>. This is done using special value descriptor type
2391/// \alib{containers;TPairDescriptor}.
2392///
2393/// \see
2394/// For a detailed description of this type, see original type
2395/// \alib{containers;HashTable}, as well as alternative type definition
2396/// \alib{containers;HashSet}.
2397///
2398/// @tparam TAllocator The allocator type to use, as prototyped with \alib{lang;Allocator}.
2399/// @tparam TKey The type of the <em>key-portion</em> of the inserted data.<br>
2400/// This type is published as \alib{containers;HashTable::KeyType}.
2401/// @tparam TMapped The type of the <em>mapped-portion</em> of the inserted data.<br>
2402/// This type is published as \alib{containers;HashTable::MappedType}.
2403/// @tparam THash The hash functor applicable to \p{TKey}.<br>
2404/// Defaults to <c>std::hash<TKey></c> and is published as
2405/// \alib{containers;HashTable::HashType}.
2406/// @tparam TEqual The comparison functor on \p{TKey}.<br>
2407/// Defaults to <c>std::equal_to<TKey></c> and is published as
2408/// \alib{containers;HashTable::EqualType}.
2409/// @tparam THashCaching Determines if hash codes are cached when elements are inserted.<br>
2410/// Defaults to <b>Caching::Auto</b>, which enables caching if
2411/// <c>std::is_arithmetic<TKey>::value</c> evaluates to \c false.
2412/// @tparam TRecycling Denotes the type of recycling that is to be performed. Possible values are
2413/// \alib{containers;Recycling;None},
2414/// \alib{containers;Recycling;Private} (the default), or
2415/// \alib{containers;Recycling;Shared}.
2416template< typename TAllocator,
2417 typename TKey,
2418 typename TMapped,
2419 typename THash = std::hash <TKey>,
2420 typename TEqual = std::equal_to<TKey>,
2421 lang::Caching THashCaching = lang::Caching::Auto,
2422 Recycling TRecycling = Recycling::Private >
2423using HashMap= HashTable<TAllocator,
2425 THash,TEqual,
2426 THashCaching,
2427 TRecycling >;
2428
2429} // namespace alib[::containers]
2430
2431/// Type alias in namespace \b alib. See type definition \ref alib::containers::HashSet.
2432template< typename TAllocator,
2433 typename TValueDescriptor,
2434 typename THash = std::hash <typename TValueDescriptor::KeyType>,
2435 typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>,
2436 lang::Caching THashCaching = lang::Caching::Auto,
2437 Recycling TRecycling = Recycling::Private >
2439
2440/// Type alias in namespace \b alib. See type definition \ref alib::containers::HashSet.
2441template< typename TAllocator,
2442 typename T,
2443 typename THash = std::hash <T>,
2444 typename TEqual = std::equal_to<T>,
2445 lang::Caching THashCaching = lang::Caching::Auto,
2446 Recycling TRecycling = Recycling::Private >
2448
2449/// Type alias in namespace \b alib.
2450template< typename TAllocator,
2451 typename TKey,
2452 typename TMapped,
2453 typename THash = std::hash <TKey>,
2454 typename TEqual = std::equal_to<TKey>,
2455 lang::Caching THashCaching = lang::Caching::Auto,
2456 Recycling TRecycling = Recycling::Private >
2458
2459} // namespace [alib]
2460
2461#if ALIB_DEBUG_CRITICAL_SECTIONS
2462# undef DCS
2463# undef DCSSHRD
2464#endif
2465
2466
ElementHandle & operator=(const ElementHandle &other)=delete
Deleted copy assignment operator.
ElementHandle & operator=(ElementHandle &&other)
HashTable * table
The table we belong to.
ElementHandle(ElementHandle &other)=delete
Deleted copy constructor.
ElementHandle(HashTable *pTable, Element *pElement)
ElementHandle()
Default constructor creating and empty handle.
Element * element
The extracted element.
ALIB_WARNINGS_IGNORE_NOTHING_RETURNED Iterator erase(ConstIterator start, ConstIterator end)
std::pair< Iterator, bool > InsertIfNotExistent(const KeyType &key, const MappedType &mapped)
HashTable(AllocatorType &pAllocator, TSharedRecycler &pSharedRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)
std::pair< Iterator, bool > EmplaceIfNotExistent(const KeyType &key, TArgs &&... args)
ConstIterator cend() const
typename TValueDescriptor::MappedType MappedType
typename base::recyclerType recyclerType
The recycler type.
HashTable(AllocatorType &pAllocator, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)
typename base::template TLocalIterator< const StoredType > ConstLocalIterator
The constant iterator for a single bucket exposed by this container.
std::pair< Iterator, bool > InsertIfNotExistent(const KeyType &key, MappedType &&mapped)
typename TValueDescriptor::StoredType StoredType
TValueDescriptor DescriptorType
Type definition publishing template parameter TValueDescriptor.
std::pair< Iterator, bool > InsertOrAssign(const KeyType &key, const MappedType &mapped)
integer Erase(const KeyType &key, size_t hashCode)
std::pair< Iterator, bool > InsertIfNotExistent(const KeyType &key, MappedType &&mapped, size_t hashCode)
std::pair< Iterator, bool > InsertOrAssign(const KeyType &key, MappedType &&mapped, size_t hashCode)
typename base::SharedRecyclerType SharedRecyclerType
TAllocator AllocatorType
Type definition publishing template parameter TAllocator.
std::pair< Iterator, bool > InsertOrAssign(const KeyType &key, MappedType &&mapped)
THash HashType
Type definition publishing template parameter THash.
typename TValueDescriptor::KeyType KeyType
typename base::template TIterator< StoredType > Iterator
The mutable iterator exposed by this container.
typename base::template TLocalIterator< StoredType > LocalIterator
The mutable iterator for a single bucket exposed by this container.
TEqual EqualType
Type definition publishing template parameter TEqual.
typename base::template TIterator< const StoredType > ConstIterator
The constant iterator exposed by this container.
HashTable(TSharedRecycler &pSharedRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)
#define ALIB_ASSERT(cond, domain)
Definition alib.inl:1048
#define ALIB_WARNINGS_RESTORE
Definition alib.inl:705
#define ALIB_EXPORT
Definition alib.inl:488
#define ALIB_ASSERT_ERROR(cond, domain,...)
Definition alib.inl:1049
#define ALIB_WARNINGS_IGNORE_NOTHING_RETURNED
Definition alib.inl:681
#define ALIB_DEBUG_CRITICAL_SECTIONS
Definition prepro.md:43
std::tuple< double, double, integer, integer > DbgGetHashTableDistribution(const THashtable &hashtable)
HashTable< TAllocator, TPairDescriptor< TKey, TMapped >, THash, TEqual, THashCaching, TRecycling > HashMap
HashTable< TAllocator, TIdentDescriptor< T >, THash, TEqual, THashCaching, TRecycling > HashSet
void Destruct(T &object)
Definition tmp.inl:83
Caching
Denotes if a cache mechanism is enabled or disabled.
@ Auto
Auto/default mode.
ValueReference
Denotes if a value is interpreted as an absolute or relative number.
@ Relative
Referring to a relative value.
@ Absolute
Referring to an absolute value.
containers::HashSet< TAllocator, T, THash, TEqual, THashCaching, TRecycling > HashSet
Type alias in namespace alib. See type definition alib::containers::HashSet.
containers::HashTable< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling > HashTable
Type alias in namespace alib. See type definition alib::containers::HashSet.
lang::integer integer
Type alias in namespace alib.
Definition integers.inl:149
containers::HashMap< TAllocator, TKey, TMapped, THash, TEqual, THashCaching, TRecycling > HashMap
Type alias in namespace alib.
containers::Recycling Recycling
Type alias in namespace alib.
Definition recycling.inl:35
lang::uinteger uinteger
Type alias in namespace alib.
Definition integers.inl:152
float maxLoadFactor
The maximum quotient of size and bucketCount that triggers a rehash.
lang::SidiNodeBase< Element > Node
Type of a node in the List.
typename HTElementSelector< TValueDescriptor, THashCaching >::Type Element
The type stored in the bucket of class HashTable.
typename RecyclingSelector< TRecycling >::template Type< TAllocator, typename HTElementSelector< TValueDescriptor, THashCaching >::Type > base
Our base type.
float baseLoadFactor
The load factor that is set when the table is rehashed automatically.
TElement * removeNext() noexcept
Definition sidilist.inl:118