pasta::bit_vector  v1.0.0
Compact and Fast Rank and Select Data Structure for Bit Vectors
Documentation Overview



The code in this repository is very easy to use. To use our fastest implementation you can simply use the code below. If further tuning is required, we recommend to see the Configuration .

#include <pasta/bit_vector/bit_vector.hpp>
#include <pasta/bit_vector/support/flat_rank_select.hpp>
// Create a bit vector of size 1000 containing only zeros and flip every other bit.
pasta::BitVector bv(1000, 0);
for (size_t i = 0; i < bv.size(); ++i) {
if (i % 2 == 0) { bv[i] = 1; }
// Print the bit vector to see that everything worked ;-)
for (auto it = bv.begin(); it != bv.end(); ++it) {
std::cout << ((*it == true) ? '1' : '0');
std::cout << std::endl;
// Create rank and select support and print the result of some queries.
std::cout << rs.rank0(250) << ", " << rs.rank1(250)
<< ", "
<< rs.select0(250) << ", " << rs.rank1(250)
<< std::endl;
Uncompressed, highly tuned, fixed size bit vector.
Definition: bit_vector.hpp:179
Select support for BitVector that can be used as an alternative to RankSelect for bit vectors up to l...
Definition: flat_rank_select.hpp:73


Here, we present the most interesting results from our paper [1]. For more information on the hardware used and our competitors, please look to the paper where we explain the experiments in detail. Additionally, you can look at our repository that contains all scripts needed to reproduce the results.

First, we compare the additional space that is required for the rank and select data structures.

Next, we look at the query time for rank queries w.r.t. different fill counts of the bit vector.

Then, we look at select queries in the same setting.

Finally, we compare our own implementations that can be easily switched using the Configuration .