|
bool | Build () noexcept |
| Constructs the Rank /Select dictionary. More...
|
|
bool | Has (uint32_t idx) const noexcept |
| Tests to determine whether a particular value is contained in the set. More...
|
|
size_t | MemSize () const noexcept |
| Returns the amount of memory explicitly allocated by the class. More...
|
|
uint32_t | GetBitVectorSize () const noexcept |
| Returns the size of the bit vector. More...
|
|
const uint32_t * | GetBitVector () const noexcept |
| Returns the pointer to the bit vector. More...
|
|
void | Reset () noexcept |
| Returns the object to the state immediately after the constructor is called.
|
|
|
constexpr | Sbv () noexcept |
| Instantiates the object.
|
|
| ~Sbv () noexcept |
| Destructor.
|
|
| Sbv (Sbv &&rhs) noexcept |
| Instantiates the object (move constructor). This function is useful when using C++11.
|
|
Sbv & | operator= (Sbv &&rhs) noexcept |
| Move assignment operator. This function is useful when using C++11.
|
|
| Sbv (Sbv &rhs, move_tag) noexcept |
| Corresponds to a move constructor.
|
|
Sbv & | assign (Sbv &rhs, move_tag) noexcept |
| Corresponds to a move assignment operator.
|
|
void | swap (Sbv &rhs) noexcept |
| Swaps the contents of an object. More...
|
|
|
Used before running Build .
|
bool | Init (uint32_t bv_size) noexcept |
| Initializes an object. More...
|
|
bool | TurnOn (uint32_t idx) noexcept |
| Adds a 32-bit unsigned integer to the set. More...
|
|
bool | TurnOff (uint32_t idx) noexcept |
| Removes a 32-bit unsigned integer from the set. More...
|
|
|
|
uint32_t | Rank1 (uint32_t idx) const noexcept |
| Performs a Rank operation. More...
|
|
uint32_t | Rank0 (uint32_t idx) const noexcept |
| Performs a Rank operation. More...
|
|
int32_t | Select1 (uint32_t nth) const noexcept |
| Returns the position of the nth 1 bit. nth starts from 0. More...
|
|
int32_t | Select0 (uint32_t nth) const noexcept |
| Returns the position of the nth 0 bit. nth starts from 0. More...
|
|
|
bool | Export (BinaryWriter *w) const noexcept |
| Writes the object to the file. More...
|
|
bool | Import (BinaryReader *r) noexcept |
| Reads the written object. More...
|
|
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select
operation.
- Description
- This class holds a set of 32-bit unsigned integers in the form of a bit vector, and supports
Rank
and Select
operations by \(O(1)\)
constant time. High speed operations on modern compact data structures can be implemented using the Rank/Select
operations. Refer to Set::Rank1
and Select1
for a detailed description of Rank/Select
operations.
- Use this class in the following way.
-
Create the objects using the constructor.
-
Initialize the bit vector using
Init
to set the defined space.
-
Add integers to the set using
TurnOn
.
-
Construct a dictionary using
Build
to run Rank
/Select
operations at constant time.
-
Rank/Select
operations can now be used.
- When the data has been written using
Export
, the data may be used by calling the data using Import
after running the constructor. This class holds all of the bit vector within the definition domain, allowing for high speed Rank
operations. However, it consumes a large amount of memory. The use of SparseSet
is recommended when the set is a nowhere dense set.
Definition at line 73 of file Sbv.h.