Construcing Uncompressed Bitvectors

Introduction

This tutorial shows how to construct and use uncompressed bitvector representations.

Code

#include <stdint.h>
#include <sdsl/bit_vectors.hpp>
#include <sdsl/util.hpp>

using namespace sdsl;

int main(int argc,char** argv) {
	uint64_t size = 123456789;
	// create bv of size bits
	bit_vector bv(size);

	// set every 7-th bit to one
	for(uint64_t i=0;i<size;i+=7) {
		bv[i] = 1;
	}

	// calculate the number of one bits
	uint64_t count = 0;
	for(uint64_t i=0;i<size;i++) {
		if(bv[i] == 1) count++;
	}

	// output
	std::cout << "There are " << count << " one bits in bv." << std::endl;
	std::cout << "The bit vector uses " << util::get_size_in_mega_bytes(bv) << " MB. << std::endl;

	// clear up memory used by bv
	sdsl::util::clear(bv);
	
	return EXIT_SUCCESS;
}

Explanation

The bit_vector class is a specialization of the int_vector class available in sdsl/int_vector.hpp:

typedef int_vector<1> bit_vector;

All bit vectors available in sdsl can be included using

#include <sdsl/bitvectors.hpp>

All sdsl data structures use the sdsl namespace:

using namespace sdsl;

The individual bits of the bit vector can easiliy be accessed through the [] operator:

bv[i] = 1;
if(bv[i] == 1) count++;

To output the space used by any sdsl data structure you can use the following two function in the util name space:

size_t size_in_bytes = util::get_size_in_mega_bytes(bv)
size_t size_in_mb = util::get_size_in_bytes(bv);

You can free the space used by any sdsl data structure using:

sdsl::util::clear(bv);

Compiling

You can compile the above example using the following command:

g++ -O3 -funroll-loops -I${HOME}/include -L${HOME}/lib bitvec.cpp -o bitvec -lsdsl

where -I${HOME}/include is the include directory you installed the sdsl header files and -L${HOME}/lib is the path of the sdsl library.