* SparseByteSet
Synopsis
Declared in <folly/container/SparseByteSet.h>
class SparseByteSet;Description
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