[#llvm-SparseMultiSet]
= xref:llvm.adoc[llvm]::SparseMultiSet
:relfileprefix: ../
:mrdocs:

Fast multiset implementation for objects that can be identified by small unsigned keys.

== Synopsis

Declared in `<llvm/ADT/SparseMultiSet.h>`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
template<
    typename ValueT,
    typename KeyT = unsigned int,
    typename KeyFunctorT = xref:llvm/identity.adoc[identity],
    typename SparseT = uint8_t>
class SparseMultiSet;
----

== Description

SparseMultiSet allocates memory proportional to the size of the key universe, so it is not recommended for building composite data structures. It is useful for algorithms that require a single set with fast operations.

Compared to DenseSet and DenseMap, SparseMultiSet provides constant‐time fast clear() as fast as a vector. The find(), insert(), and erase() operations are all constant time, and typically faster than a hash table. The iteration order doesn't depend on numerical key values, it only depends on the order of insert() and erase() operations. Iteration order is the insertion order. Iteration is only provided over elements of equivalent keys, but iterators are bidirectional.

Compared to BitVector, SparseMultiSet<unsigned> uses 8x‐40x more memory, but offers constant‐time clear() and size() operations as well as fast iteration independent on the size of the universe.

SparseMultiSet contains a dense vector holding all the objects and a sparse array holding indexes into the dense vector. Most of the memory is used by the sparse array which is the size of the key universe. The SparseT template parameter provides a space/speed tradeoff for sets holding many elements.

When SparseT is uint32_t, find() only touches up to 3 cache lines, but the sparse array uses 4 x Universe bytes.

When SparseT is uint8_t (the default), find() touches up to 3+[N/256]cache lines, but the sparse array is 4x smaller. N is the number of elements in the set.

For sets that may grow to thousands of elements, SparseT should be set to uint16_t or uint32_t.

Multiset behavior is provided by providing doubly linked lists for values that are inlined in the dense vector. SparseMultiSet is a good choice when one desires a growable number of entries per key, as it will retain the SparseSet algorithmic properties despite being growable. Thus, it is often a better choice than a SparseSet of growable containers or a vector of vectors. SparseMultiSet also keeps iterators valid after erasure (provided the iterators don't point to the element erased), allowing for more intuitive and fast removal.

== Types

[cols="1,4"]
|===
| Name| Description
| xref:llvm/SparseMultiSet/iterator_base.adoc[`iterator_base`] 
| Our iterators are iterators over the collection of objects that share a key.
|===


== Type Aliases

[cols="1,4"]
|===
| Name| Description
| xref:llvm/SparseMultiSet/RangePair.adoc[`RangePair`] 
| Pair of iterators delimiting the equal‐range for one key.
| xref:llvm/SparseMultiSet/const_iterator.adoc[`const_iterator`] 
| Const iterator over elements that share a key.
| xref:llvm/SparseMultiSet/const_pointer.adoc[`const_pointer`] 
| Const pointer to an element.
| xref:llvm/SparseMultiSet/const_reference.adoc[`const_reference`] 
| Const reference to an element.
| xref:llvm/SparseMultiSet/iterator.adoc[`iterator`] 
| Mutable iterator over elements that share a key.
| xref:llvm/SparseMultiSet/pointer.adoc[`pointer`] 
| Mutable pointer to an element.
| xref:llvm/SparseMultiSet/reference.adoc[`reference`] 
| Mutable reference to an element.
| xref:llvm/SparseMultiSet/size_type.adoc[`size_type`] 
| Unsigned type used for sizes and counts.
| xref:llvm/SparseMultiSet/value_type.adoc[`value_type`] 
| Element type stored in the set.
|===


== Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:llvm/SparseMultiSet/2constructor-0b.adoc[`SparseMultiSet`]         [.small]#[constructor]#
| Constructors
| xref:llvm/SparseMultiSet/2destructor.adoc[`~SparseMultiSet`] [.small]#[destructor]#
| Free the sparse index array.
| xref:llvm/SparseMultiSet/operator_assign.adoc[`operator=`]  [.small]#[deleted]#
| Copy assignment is deleted.
| xref:llvm/SparseMultiSet/clear.adoc[`clear`] 
| Clears the set. This is a very fast constant time operation.
| xref:llvm/SparseMultiSet/contains.adoc[`contains`] 
| Returns true if this set contains an element identified by Key.
| xref:llvm/SparseMultiSet/count.adoc[`count`] 
| Returns the number of elements identified by Key. This will be linear in the number of elements of that key.
| xref:llvm/SparseMultiSet/empty.adoc[`empty`] 
| Returns true if the set is empty.
| xref:llvm/SparseMultiSet/end-0e.adoc[`end`] 
| `end` overloads
| xref:llvm/SparseMultiSet/equal_range.adoc[`equal_range`] 
| The bounds of the range of items sharing Key K. First member is the head of the list, and the second member is a decrementable end iterator for that key.
| xref:llvm/SparseMultiSet/erase.adoc[`erase`] 
| Erases an existing element identified by a valid iterator.
| xref:llvm/SparseMultiSet/eraseAll.adoc[`eraseAll`] 
| Erase all elements with the given key. This invalidates all iterators of that key.
| xref:llvm/SparseMultiSet/find-0d.adoc[`find`] 
| `find` overloads
| xref:llvm/SparseMultiSet/findIndex.adoc[`findIndex`] 
| Find an element by its index.
| xref:llvm/SparseMultiSet/getHead.adoc[`getHead`] 
| Return the head and tail of the subset's list, otherwise returns end().
| xref:llvm/SparseMultiSet/getTail.adoc[`getTail`] 
| Return an iterator to the last element sharing `Key,` or end().
| xref:llvm/SparseMultiSet/insert.adoc[`insert`] 
| Insert a new element at the tail of the subset list. Returns an iterator to the newly added entry.
| xref:llvm/SparseMultiSet/setUniverse.adoc[`setUniverse`] 
| Set the universe size which determines the largest key the set can hold. The universe must be sized before any elements can be added.
| xref:llvm/SparseMultiSet/size.adoc[`size`] 
| Returns the number of elements in the set.
|===


== Template Parameters

[cols="1,4"]
|===
| Name| Description
| *ValueT*
| The type of objects in the set.
| *KeyT*
| The type of the key that identifies objects in the set.
| *KeyFunctorT*
| A functor that computes an unsigned index from KeyT.
| *SparseT*
| An unsigned integer type. See above.
|===


[.small]#Created with https://www.mrdocs.com[MrDocs]#