class SparseSet

Declaration

template <typename ValueT,
          typename KeyFunctorT = identity<unsigned int>,
          typename SparseT = uint8_t>
class SparseSet { /* full declaration omitted */ };

Description

SparseSet - Fast set implementation for objects that can be identified by small unsigned keys. 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.

Declared at: llvm/include/llvm/ADT/SparseSet.h:124

Templates

ValueT
The type of objects in the set.
KeyFunctorT = identity<unsigned int>
A functor that computes an unsigned index from KeyT.
SparseT = uint8_t
An unsigned integer type. See above.

Member Variables

private llvm::SparseSet::DenseT Dense
private SparseT* Sparse = nullptr
private unsigned int Universe = 0
private KeyFunctorT KeyIndexOf
private SparseSetValFunctor<llvm::SparseSet::KeyT, ValueT, KeyFunctorT> ValIndexOf

Method Overview

Methods

SparseSet<ValueT, KeyFunctorT, SparseT>(
    const SparseSet<ValueT,
                    KeyFunctorT,
                    SparseT>&)

Declared at: llvm/include/llvm/ADT/SparseSet.h:146

Parameters

const SparseSet<ValueT, KeyFunctorT, SparseT>& 

SparseSet<ValueT, KeyFunctorT, SparseT>()

Declared at: llvm/include/llvm/ADT/SparseSet.h:145

llvm::SparseSet::iterator begin()

Declared at: llvm/include/llvm/ADT/SparseSet.h:177

llvm::SparseSet::const_iterator begin() const

Declared at: llvm/include/llvm/ADT/SparseSet.h:175

void clear()

Description

clear - Clears the set. This is a very fast constant time operation.

Declared at: llvm/include/llvm/ADT/SparseSet.h:195

bool contains(
    const llvm::SparseSet::KeyT& Key) const

Description

Check if the set contains the given \c Key.

Declared at: llvm/include/llvm/ADT/SparseSet.h:236

Parameters

const llvm::SparseSet::KeyT& Key
A valid key to find.

llvm::SparseSet::size_type count(
    const llvm::SparseSet::KeyT& Key) const

Description

count - Returns 1 if this set contains an element identified by Key, 0 otherwise.

Declared at: llvm/include/llvm/ADT/SparseSet.h:241

Parameters

const llvm::SparseSet::KeyT& Key

bool empty() const

Description

empty - Returns true if the set is empty. This is not the same as BitVector::empty().

Declared at: llvm/include/llvm/ADT/SparseSet.h:184

llvm::SparseSet::const_iterator end() const

Declared at: llvm/include/llvm/ADT/SparseSet.h:176

llvm::SparseSet::iterator end()

Declared at: llvm/include/llvm/ADT/SparseSet.h:178

llvm::SparseSet::iterator erase(
    llvm::SparseSet::iterator I)

Description

erase - Erases an existing element identified by a valid iterator. This invalidates all iterators, but erase() returns an iterator pointing to the next element. This makes it possible to erase selected elements while iterating over the set: for (SparseSet::iterator I = Set.begin(); I != Set.end();) if (test(*I)) I = Set.erase(I); else ++I; Note that end() changes when elements are erased, unlike std::list.

Declared at: llvm/include/llvm/ADT/SparseSet.h:289

Parameters

llvm::SparseSet::iterator I

bool erase(const llvm::SparseSet::KeyT& Key)

Description

erase - Erases an element identified by Key, if it exists.

Declared at: llvm/include/llvm/ADT/SparseSet.h:308

Parameters

const llvm::SparseSet::KeyT& Key
The key identifying the element to erase.

Returns

True when an element was erased, false if no element was found.

llvm::SparseSet::iterator find(
    const llvm::SparseSet::KeyT& Key)

Description

find - Find an element by its key.

Declared at: llvm/include/llvm/ADT/SparseSet.h:225

Parameters

const llvm::SparseSet::KeyT& Key
A valid key to find.

Returns

An iterator to the element identified by key, or end().

llvm::SparseSet::const_iterator find(
    const llvm::SparseSet::KeyT& Key) const

Declared at: llvm/include/llvm/ADT/SparseSet.h:229

Parameters

const llvm::SparseSet::KeyT& Key

llvm::SparseSet::iterator findIndex(
    unsigned int Idx)

Description

findIndex - Find an element by its index.

Declared at: llvm/include/llvm/ADT/SparseSet.h:205

Parameters

unsigned int Idx
A valid index to find.

Returns

An iterator to the element identified by key, or end().

std::pair<iterator, bool> insert(
    const ValueT& Val)

Description

insert - Attempts to insert a new element. If Val is successfully inserted, return (I, true), where I is an iterator pointing to the newly inserted element. If the set already contains an element with the same key as Val, return (I, false), where I is an iterator pointing to the existing element. Insertion invalidates all iterators.

Declared at: llvm/include/llvm/ADT/SparseSet.h:253

Parameters

const ValueT& Val

ValueT pop_back_val()

Declared at: llvm/include/llvm/ADT/SparseSet.h:270

void setUniverse(unsigned int U)

Description

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.

Declared at: llvm/include/llvm/ADT/SparseSet.h:156

Parameters

unsigned int U
Universe size. All object keys must be less than U.

llvm::SparseSet::size_type size() const

Description

size - Returns the number of elements in the set. This is not the same as BitVector::size() which returns the size of the universe.

Declared at: llvm/include/llvm/ADT/SparseSet.h:191

~SparseSet<ValueT, KeyFunctorT, SparseT>()

Declared at: llvm/include/llvm/ADT/SparseSet.h:148