sdsl::sd_vector< hi_bit_vector_type, hi_select_1, hi_select_0 > Class Template Reference

A bit vector which compresses very sparse populated bit vectors by. More...

#include <sd_vector.hpp>

List of all members.

Public Types
typedef bit_vector::size_type	size_type
typedef size_type	value_type
typedef hi_select_0	select_0_support_type
typedef hi_select_1	select_1_support_type
typedef sd_rank_support < hi_bit_vector_type, select_1_support_type, select_0_support_type >	rank_1_type
typedef sd_select_support < hi_bit_vector_type, select_1_support_type, select_0_support_type >	select_1_type
Public Member Functions
	sd_vector (const bit_vector &bv)
value_type	operator[] (size_type i) const
	Accessing the i-th element of the original bit_vector.
void	swap (sd_vector &v)
	Swap method.
size_type	size () const
	Returns the size of the original bit vector.
sd_vector &	operator= (const sd_vector &v)
size_type	serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
	Serializes the data structure into the given ostream.
void	load (std::istream &in)
	Loads the data structure from the given istream.
Public Attributes
const hi_bit_vector_type &	high
const int_vector &	low
const select_1_support_type &	high_1_select
const select_0_support_type &	high_0_select
Friends
class	sd_rank_support< hi_bit_vector_type, select_1_support_type, select_0_support_type >
class	sd_select_support< hi_bit_vector_type, select_1_support_type, select_0_support_type >

---

Detailed Description

template<class hi_bit_vector_type = bit_vector, class hi_select_1 = typename hi_bit_vector_type::select_1_type, class hi_select_0 = typename hi_bit_vector_type::select_0_type>
class sdsl::sd_vector< hi_bit_vector_type, hi_select_1, hi_select_0 >

A bit vector which compresses very sparse populated bit vectors by.

Other implementations of this data structure:

• the sdarray of Okanohara and Sadakane
• Sebastiano Vigna implemented a elias_fano class in this sux library.

References

• P. Elias: ,,Efficient storage and retrieval by content and address of static files'', Journal of the ACM, 1974
• R. Fano: ,,On the number of bits required to implement an associative memory''. Memorandum 61. Computer Structures Group, Project MAC, MIT, 1971
• D. Okanohara, K. Sadakane: ,,Practical Entropy-Compressed Rank/Select Dictionary'', Proceedings of ALENEX 2007.

Template Parameters:

hi_bit_vector_type	Type of the bitvector HI used for representing the high part of the positions of the 1s.
hi_select_1	Type of the select support data structure which is used to select ones in HI.
hi_select_0	Type of the select support data structure which is used to select zeros in HI.

---

Member Function Documentation

template<class hi_bit_vector_type = bit_vector, class hi_select_1 = typename hi_bit_vector_type::select_1_type, class hi_select_0 = typename hi_bit_vector_type::select_0_type>

value_type sdsl::sd_vector< hi_bit_vector_type, hi_select_1, hi_select_0 >::operator[]

(

size_type

i

)

const [inline]

Accessing the i-th element of the original bit_vector.

Parameters:

i	An index i with .

Returns:

The i-th bit of the original bit_vector

Time complexity

, where m equals the number of zeros

Remark

The time complexity can be easily improved to by using binary search in the second step.

---

The documentation for this class was generated from the following file:

• sdsl/include/sdsl/sd_vector.hpp