carb::container::IntrusiveUnorderedMultimap

Defined in carb/container/IntrusiveUnorderedMultimap.h

Classes

carb::container::IntrusiveUnorderedMultimap::const_iterator: A LegacyForwardIterator to const ValueType .
carb::container::IntrusiveUnorderedMultimap::iterator: A LegacyForwardIterator to ValueType .

template<class Key, class T, IntrusiveUnorderedMultimapLink<Key, T> T::* U, class Hash = ::std::hash<Key>, class Pred = ::std::equal_to<Key>> class 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 the T 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 an Allocator type, but in a real application some stored instances may be on the stack while others are on the heap, which makes using std::unordered_multimap impractical. Furthermore, a stored type may which to be removed from one list and inserted into another. With std::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. For std::unordered_multimap the mapped type would have to be a pointer or pointer-like type which is an inefficient use of space, cache, etc. The IntrusiveUnorderedMultimapLink 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. For std::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 type T is required to be contained and a custom hasher/equality-predicate would have to be written to support it—it 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, the Pred template parameter is used to compare keys until a match is found. A truly ideal hash at the default load factor of 1.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 and initializer_list constructor variants are not present in IntrusiveUnorderedMultimap.
The iterator and initializer_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 and begin(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");

Template Parameters

Key – A key to associate with the mapped data.
T – The mapped data, referred to by Key.
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.
Hash – A class that is used to hash the key value. Better hashing functions produce better performance.
Pred – A class that is used to equality-compare two key values.

Public Types

using KeyType = const Key : The type of the key; type Key

using MappedType = T : The type of the mapped data; type T

using Link = IntrusiveUnorderedMultimapLink<Key, T>: The type of the IntrusiveUnorderedMultimapLink that must be a member of MappedType.

using ValueType = typename Link::ValueType: Helper definition for std::pair<const Key, T&>.

Public Functions

inline constexpr IntrusiveUnorderedMultimap(): Constructor. Initializes *this to be empty().

inline IntrusiveUnorderedMultimap(IntrusiveUnorderedMultimap &&other) noexcept

Move-construct. Moves all entries to *this from other and leaves it empty.

Parameters: other – Another IntrusiveUnorderedMultimap to move entries from.

inline ~IntrusiveUnorderedMultimap(): Destructor. Implies clear().

inline IntrusiveUnorderedMultimap &operator=(IntrusiveUnorderedMultimap &&other) noexcept

Move-assign. Moves all entries from other and leaves other 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 iterator end() noexcept

Returns an iterator to the end.

Returns: An iterator to the end.

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 returns end(). O(n).

Parameters: value – The value to check for.
Returns: An iterator to value if contained in *this; end() otherwise.

inline const_iterator locate(T &value) const noexcept

Returns an iterator to the given value if it is contained in *this, otherwise returns end(). 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 void clear(): Removes all elements.

Note

Postcondition: *this is empty().

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 (via U) 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 iterator emplace(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 constructed pair must not be contained (via U) 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 iterator find(const Key &key)

Finds an element with a specific key.

Parameters: key – The key that identifies an element.
Returns: An iterator to the element, if found; end() otherwise.

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.

Parameters: key – The key that identifies an element.
Returns: A pair of iterator objects that define a range: the first iterator is the first item in the range and the second iterator is immediately past the end of the range. If no elements exist with key, std::pair(end(), end()) is returned.

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: the first const_iterator is the first item in the range and the second const_iterator is immediately past the end of the range. If no elements exist with key, 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.