Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
bit vector example
/*
g++ -std=c++14 -o main main.cpp -I/home/cocomoff/sdsl-lite/build/include -L/home/cocomoff/sdsl-lite/build/lib -lsdsl -ldivsufsort -ldivsufsort64
*/
#include <bits/stdc++.h>
#include <sdsl/int_vector.hpp>
#include <sdsl/bit_vectors.hpp>
#include <sdsl/rank_support.hpp>
#include <sdsl/util.hpp>
using namespace std;
using namespace sdsl;
typedef bit_vector::size_type size_type;
int main() {
const int N = 10;
size_type n = N;
bit_vector bv(n, 0);
rank_support_v<1> rs(&bv);
// U = {0, 1, ..., 9}
// V = {0, 2, 3, 5, 9}
bv[0] = bv[2] = bv[3] = bv[5] = bv[0] = 1;
cout << bv << endl;
// access(B, x)
for (int i = 0; i < N; i++) {
cout << "Element " << i << " is in U? = " << boolalpha << bv[i] << endl;
}
// (i+1)-th smaller element in V
for (int i = 0; i < N; i++) {
cout << i << "-th smaller element in U = " << rs(i) << endl;
}
// 1-support
size_t zeros = rank_support_v<0>(&bv)(bv.size());
bit_vector::select_0_type b_sel(&bv);
cout << zeros << endl;
for (auto i = 1; i <= zeros; i++) {
cout << i << ":" << b_sel(i) << " " << b_sel(rs.rank(i)) << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment