carb::container::IntrusiveUnorderedMultimap¶
Defined in carb/container/IntrusiveUnorderedMultimap.h
-
template<class
Key
, classT
, IntrusiveUnorderedMultimapLink<Key, T>T
::*U
, classHash
= ::std::hash<Key>, classPred
= ::std::equal_to<Key>>
classcarb::container
::
IntrusiveUnorderedMultimap
¶ IntrusiveUnorderedMultimap is a closed-addressing hash table very similar to std::unordered_multimap, but requires the tracking information to be contained within the stored type
T
, rather than built around it.In other words, the tracking information is “intrusive” in the type
T
by way of the IntrusiveUnorderedMultimapLink type. IntrusiveUnorderedMultimap does no allocation of theT
type; all allocation is done outside of the context of IntrusiveUnorderedMultimap, which allows stored items to be on the stack, grouped with other items, etc.The impetus behind intrusive containers is specifically to allow the application to own the allocation patterns for a type, but still be able to store them in a container. For
std::unordered_multimap
, everything goes through anAllocator
type, but in a real application some stored instances may be on the stack while others are on the heap, which makes usingstd::unordered_multimap
impractical. Furthermore, a stored type may which to be removed from one list and inserted into another. Withstd::unordered_multimap
, this would require heap interaction to erase from one list and insert into another. With IntrusiveUnorderedMultimap, this operation would not require any heap interaction and would be done very quickly (O(1)).Another example is a
std::unordered_multimap
of polymorphic types. Forstd::unordered_multimap
the mapped type would have to be a pointer or pointer-like type which is an inefficient use of space, cache, etc. TheIntrusiveUnorderedMultimapLink
can be part of the contained object which is a more efficient use of space.Since IntrusiveUnorderedMultimap doesn’t require any form of
Allocator
, the allocation strategy is completely left up to the application. This means that items could be allocated on the stack, pooled, or items mixed between stack and heap.An intrusive unique-map (i.e. an intrusive equivalent to
std::unordered_map
) is impractical because allocation is not the responsibility of the container. Forstd::unordered_map::insert
, if a matching key already exists, a new entry is not created and an iterator to the existing entry is returned. Conversely, with the intrusive container, the insert function is being given an already-created object that cannot be destroyed. It is therefore up to the application to ensure uniqueness if desired. Similarly, the existence of an intrusive (multi-)set is impractical since a typeT
is required to be contained and a custom hasher/equality-predicate would have to be written to support itit would be simpler to use carb::container::IntrusiveList.It is important to select a good hashing function in order to reduce collisions that may sap performance. Generally
std::hash
is used which is typically based on the FNV-1a hash algorithm. Hash computation is only done for finding the bucket that would contain an item. Once the bucket is selected, thePred
template parameter is used to compare keys until a match is found. A truly ideal hash at the default load factor of1.0
results in a single entry per bucket; however, this is not always true in practice. Hash collisions cause multiple items to fall into the same bucket, increasing the amount of work that must be done to find an item.Iterator invalidation mirrors that of
std::unordered_multimap
: rehashing invalidates iterators and may cause elements to be rearranged into different buckets, but does not invalidate references or pointers to keys or the mapped type.IntrusiveUnorderedMultimap matches
std::unordered_multimap
with the following exceptions:The
iterator
andinitializer_list
constructor variants are not present in IntrusiveUnorderedMultimap.The
iterator
andinitializer_list
insert() variants are not present in IntrusiveUnorderedMultimap.IntrusiveUnorderedMultimap cannot be copied (though may still be moved).
IntrusiveUnorderedMultimap does not have
erase()
to erase an item from the list, but instead has remove() which will remove an item from the container. It is up to the caller to manage the memory for the item.Likewise, clear() functions as a “remove all” and does not destroy items in the container.
iter_from_value() is a new function that translates an item contained in IntrusiveUnorderedMultimap into an iterator.
local_iterator
andbegin(size_type)
/end(size_type)
are not implemented.
Example:
class Subscription { public: IntrusiveUnorderedMultimapLink<std::string, Subscription> link; void notify(); }; IntrusiveUnorderedMultimap<std::string, &Subscription::link> map; Subscription sub; map.emplace("my subscription", sub); // Notify all subscriptions: for (auto& entry : map) entry.second.notify(); map.remove("my subscription");
- tparam Key
A key to associate with the mapped data.
- tparam T
The mapped data, referred to by
Key
.- tparam U
A pointer-to-member of
T
that must be of type IntrusiveUnorderedMultimapLink. This member will be used by the IntrusiveUnorderedMultimap for storing the key type and tracking the contained object.- tparam Hash
A class that is used to hash the key value. Better hashing functions produce better performance.
- tparam Pred
A class that is used to equality-compare two key values.
Public Types
-
using
Link
= IntrusiveUnorderedMultimapLink<Key, T>¶ The type of the IntrusiveUnorderedMultimapLink that must be a member of MappedType.
Public Functions
-
inline
IntrusiveUnorderedMultimap
(IntrusiveUnorderedMultimap &&other) noexcept¶ Move-construct. Moves all entries to
*this
fromother
and leaves it empty.- Parameters
other – Another IntrusiveUnorderedMultimap to move entries from.
-
inline IntrusiveUnorderedMultimap &
operator=
(IntrusiveUnorderedMultimap &&other) noexcept¶ Move-assign. Moves all entries from
other
and leavesother
in a valid but possibly non-empty state.- Parameters
other – Another IntrusiveUnorderedMultimap to move entries from.
-
inline bool
empty
() const noexcept¶ Checks whether the container is empty.
- Returns
true
if*this
is empty;false
otherwise.
-
inline size_t
size
() const noexcept¶ Returns the number of elements contained.
- Returns
The number of elements contained.
-
inline size_t
max_size
() const noexcept¶ Returns the maximum possible number of elements.
- Returns
The maximum possible number of elements.
-
inline iterator
begin
() noexcept¶ Returns an iterator to the beginning.
- Returns
An iterator to the beginning.
-
inline const_iterator
cbegin
() const noexcept¶ Returns a const_iterator to the beginning.
- Returns
A const_iterator to the beginning.
-
inline const_iterator
cend
() const noexcept¶ Returns a const_iterator to the end.
- Returns
A const_iterator to the end.
-
inline const_iterator
begin
() const noexcept¶ Returns a const_iterator to the beginning.
- Returns
A const_iterator to the beginning.
-
inline const_iterator
end
() const noexcept¶ Returns a const_iterator to the end.
- Returns
A const_iterator to the end.
-
inline iterator
locate
(T &value) noexcept¶ Returns an iterator to the given value if it is contained in
*this
, otherwise returnsend()
. O(n).
-
inline const_iterator
locate
(T &value) const noexcept¶ Returns an iterator to the given value if it is contained in
*this
, otherwise returnsend()
. O(n).- Parameters
value – The value to check for.
- Returns
A const_iterator to
value
if contained in*this
; end() otherwise.
-
inline iterator
iter_from_value
(T &value)¶ Naively produces an iterator for
value
within*this
.Warning
Undefined behavior results if
value
is not contained within*this
. Use locate() to safely check.- Parameters
value – The value to convert.
- Returns
An iterator to
value
.
-
inline const_iterator
iter_from_value
(T &value) const¶ Naively produces an iterator for
value
within*this
.Warning
Undefined behavior results if
value
is not contained within*this
. Use locate() to safely check.- Parameters
value – The value to convert.
- Returns
A const_iterator to
value
.
-
inline iterator
insert
(ValueType value)¶ Inserts an element.
Note
No uniqueness checking is performed; multiple values with the same
Key
may be inserted.Note
Precondition:
value.second
must not be contained (viaU
) in this or any other IntrusiveUnorderedMultimap.- Parameters
value – The pair of
[key, value reference]
to insert.- Returns
An iterator to the newly-inserted
value
.
-
template<class ...
Args
>
inline iteratoremplace
(Args&&... args)¶ Inserts an element while allowing key emplacement.
Note
No uniqueness checking is performed; multiple values with the same
Key
may be inserted.Note
Precondition: The
second
member of the constructedpair
must not be contained (viaU
) in this or any other IntrusiveUnorderedMultimap.- Parameters
args – Arguments passed to
std::pair<KeyType, MappedType>
to insert.- Returns
An iterator to the newly-inserted value.
-
inline const_iterator
find
(const Key &key) const¶ Finds an element with a specific key.
- Parameters
key – The key that identifies an element.
- Returns
A const_iterator to the element, if found; end() otherwise.
-
inline std::pair<iterator, iterator>
equal_range
(const Key &key)¶ Finds a range of elements matching the given key.
-
inline std::pair<const_iterator, const_iterator>
equal_range
(const Key &key) const¶ Finds a range of elements matching the given key.
- Parameters
key – The key that identifies an element.
- Returns
A
pair
of const_iterator objects that define a range: thefirst
const_iterator is the first item in the range and thesecond
const_iterator is immediately past the end of the range. If no elements exist withkey
,std::pair(end(), end())
is returned.
-
inline size_t
count
(const Key &key) const¶ Returns the number of elements matching a specific key.
- Parameters
key – The key to search for.
- Returns
The number of elements matching the given key.
-
inline iterator
remove
(const_iterator pos)¶ Removes an element by iterator.
Note
Precondition:
pos
must be a valid const_iterator of*this
and may not be end().- Parameters
pos – A const_iterator to the element to remove.
- Returns
A iterator to the element immediately following
pos
, or end() if no elements followed it.
-
inline T &
remove
(T &value)¶ Removes an element by reference.
Note
Precondition:
value
must be contained in*this
.- Parameters
value – The element to remove.
- Returns
value
for convenience.
-
inline size_t
remove
(const Key &key)¶ Removes all elements matching a specific key.
- Parameters
key – The key to search for.
- Returns
The number of elements that were removed.
-
inline void
swap
(IntrusiveUnorderedMultimap &other) noexcept¶ Swaps the contents of
*this
with another IntrusiveUnorderedMultimap.- Parameters
other – The other IntrusiveUnorderedMultimap to swap with.
-
inline size_t
bucket_count
() const noexcept¶ Returns the number of buckets.
- Returns
The number of buckets.
-
inline size_t
max_bucket_count
() const noexcept¶ Returns the maximum number of buckets.
- Returns
The maximum number of buckets.
-
inline size_t
bucket
(const Key &key) const¶ Returns the bucket index for a specific key.
- Parameters
key – The key to hash.
- Returns
A bucket index in the range
[0, bucket_count())
.
-
inline float
load_factor
() const¶ Returns the average number of elements per bucket.
- Returns
The average number of elements per bucket.
-
inline float
max_load_factor
() const noexcept¶ Returns the max load factor for
*this
.- Returns
The max load factor for
*this
. The default is 1.0.
-
inline void
max_load_factor
(float ml)¶ Sets the maximum load factor for
*this
.Note
Precondition:
ml
must be greater than 0.Note
Changes do not take effect until the hash table is re-generated.
- Parameters
ml – The new maximum load factor for
*this
.
-
inline void
reserve
(size_t count)¶ Reserves space for at least the specified number of elements and re-generates the hash table.
- Parameters
count – The minimum number of elements to reserve space for.
-
inline void
rehash
(size_t buckets)¶ Reserves at least the specified number of buckets and re-generates the hash table.
- Parameters
buckets – The minimum number of buckets required.
-
class
const_iterator
¶ A LegacyForwardIterator to
const ValueType
.Subclassed by carb::container::IntrusiveUnorderedMultimap< Key, T, U, Hash, Pred >::iterator