* SparseByteSet
Declared in <folly/container/SparseByteSet.h>
class SparseByteSet;A special-purpose data structure representing a set of bytes. May have better performance than std::bitset<256>, depending on workload.
Operations:
add(byte)
remove(byte)
contains(byte)
clear()
Performance:
The entire capacity of the set is inline; the set never allocates.
The constructor zeros only the first two bytes of the object.
add and contains both run in constant time w.r.t. the size of the set. Constant time - not amortized constant - and with small constant factor.
This data structure is ideal for on-stack use.
Aho, Hopcroft, and Ullman refer to this trick in "The Design and Analysis of Computer Algorithms" (1974), but the best description is here: http://research.swtch.com/sparse http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7319
| Name | Description |
|---|---|
SparseByteSet [constructor] | Constructs an empty set; the backing byte arrays need no initialization. |
add | * add(byte) |
clear | * clear() |
contains | * contains(byte) |
remove | * remove(byte) |
size | * size() |
| Name | Description |
|---|---|
kCapacity | The number of distinct byte values the set can hold. |