SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
Declared in <llvm/ADT/SparseSet.h>
template<
typename ValueT,
typename KeyT = unsigned int,
typename KeyFunctorT = identity,
typename SparseT = uint8_t>
class SparseSet;SparseSet 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, SparseSet provides constant-time fast clear() and iteration 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. When no elements have been erased, the iteration order is the insertion order.
Compared to BitVector, SparseSet<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.
SparseSet 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 2 cache lines, but the sparse array uses 4 x Universe bytes.
When SparseT is uint8_t (the default), find() touches up to 2+[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.
| Name | Description |
|---|---|
const_iterator | Const iterator over elements in insertion order. |
const_pointer | Const pointer to a stored element. |
const_reference | Const reference to a stored element. |
iterator | Mutable iterator over elements in insertion order. |
pointer | Mutable pointer to a stored element. |
reference | Mutable reference to a stored element. |
value_type | Element type stored in the set. |
| Name | Description |
|---|---|
SparseSet [constructor] | Constructors |
operator= [deleted] | Copy assignment is deleted; the sparse array is not shareable. |
begin | begin overloads |
clear | clear - Clears the set. This is a very fast constant time operation. |
contains | Check if the set contains the given Key. |
count | count - Returns 1 if this set contains an element identified by Key, 0 otherwise. |
empty | empty - Returns true if the set is empty. |
end | end overloads |
erase | erase overloads |
find | find overloads |
findIndex | findIndex - Find an element by its index. |
insert | insert - Attempts to insert a new element. |
operator[] | operator[]- Return the element for Key, inserting one if absent. |
pop_back_val | Remove and return the last element in insertion order. |
setUniverse | 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. |
size | size - Returns the number of elements in the set. |
| Name | Description |
|---|---|
| ValueT | The type of objects in the set. |
| KeyT | The type of the key, which is passed to the key functor. |
| KeyFunctorT | A functor that computes an unsigned index from KeyT. |
| SparseT | An unsigned integer type. See above. |