SDSL 3.0.1
Succinct Data Structure Library
sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > Class Template Reference

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

#include <sd_vector.hpp>

Public Types

typedef bit_vector::size_type size_type
 
typedef size_type value_type
 
typedef bit_vector::difference_type difference_type
 
typedef random_access_const_iterator< sd_vectoriterator
 
typedef iterator const_iterator
 
typedef bv_tag index_category
 
typedef t_select_0 select_0_support_type
 
typedef t_select_1 select_1_support_type
 
typedef rank_support_sd< 0, t_hi_bit_vector, select_1_support_type, select_0_support_typerank_0_type
 
typedef rank_support_sd< 1, t_hi_bit_vector, select_1_support_type, select_0_support_typerank_1_type
 
typedef select_support_sd< 0, t_hi_bit_vector, select_1_support_type, select_0_support_typeselect_0_type
 
typedef select_support_sd< 1, t_hi_bit_vector, select_1_support_type, select_0_support_typeselect_1_type
 
typedef t_hi_bit_vector hi_bit_vector_type
 

Public Member Functions

 sd_vector ()
 
 sd_vector (const sd_vector &sd)
 
sd_vectoroperator= (const sd_vector &v)
 
sd_vectoroperator= (sd_vector &&v)
 
 sd_vector (sd_vector &&sd)
 
 sd_vector (const bit_vector &bv)
 
template<class t_itr >
 sd_vector (const t_itr begin, const t_itr end)
 
 sd_vector (sd_vector_builder &builder)
 
value_type operator[] (size_type i) const
 Accessing the i-th element of the original bit_vector. More...
 
uint64_t get_int (size_type idx, const uint8_t len=64) const
 Get the integer value of the binary string of length len starting at position idx. More...
 
size_type size () const
 Returns the size of the original bit vector. More...
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serializes the data structure into the given ostream. More...
 
void load (std::istream &in)
 Loads the data structure from the given istream. More...
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 
iterator begin () const
 
iterator end () const
 
bool operator== (const sd_vector &v) const
 
bool operator!= (const sd_vector &v) const
 

Public Attributes

const uint8_t & wl = m_wl
 
const hi_bit_vector_typehigh = m_high
 
const int_vectorlow = m_low
 
const select_1_support_typehigh_1_select = m_high_1_select
 
const select_0_support_typehigh_0_select = m_high_0_select
 

Detailed Description

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
class sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_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
t_hi_bit_vectorType of the bitvector used for the unary decoded differences of the high part of the positions of the 1s.
t_select_1Type of the select structure which is used to select ones in HI.
t_select_0Type of the select structure which is used to select zeros in HI.

Definition at line 114 of file sd_vector.hpp.

Member Typedef Documentation

◆ const_iterator

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef iterator sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::const_iterator

Definition at line 121 of file sd_vector.hpp.

◆ difference_type

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef bit_vector::difference_type sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::difference_type

Definition at line 119 of file sd_vector.hpp.

◆ hi_bit_vector_type

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef t_hi_bit_vector sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::hi_bit_vector_type

Definition at line 131 of file sd_vector.hpp.

◆ index_category

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef bv_tag sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::index_category

Definition at line 122 of file sd_vector.hpp.

◆ iterator

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef random_access_const_iterator<sd_vector> sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::iterator

Definition at line 120 of file sd_vector.hpp.

◆ rank_0_type

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef rank_support_sd<0, t_hi_bit_vector, select_1_support_type, select_0_support_type> sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::rank_0_type

Definition at line 126 of file sd_vector.hpp.

◆ rank_1_type

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef rank_support_sd<1, t_hi_bit_vector, select_1_support_type, select_0_support_type> sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::rank_1_type

Definition at line 127 of file sd_vector.hpp.

◆ select_0_support_type

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef t_select_0 sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::select_0_support_type

Definition at line 123 of file sd_vector.hpp.

◆ select_0_type

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef select_support_sd<0, t_hi_bit_vector, select_1_support_type, select_0_support_type> sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::select_0_type

Definition at line 128 of file sd_vector.hpp.

◆ select_1_support_type

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef t_select_1 sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::select_1_support_type

Definition at line 124 of file sd_vector.hpp.

◆ select_1_type

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef select_support_sd<1, t_hi_bit_vector, select_1_support_type, select_0_support_type> sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::select_1_type

Definition at line 129 of file sd_vector.hpp.

◆ size_type

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef bit_vector::size_type sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::size_type

Definition at line 117 of file sd_vector.hpp.

◆ value_type

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
typedef size_type sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::value_type

Definition at line 118 of file sd_vector.hpp.

Constructor & Destructor Documentation

◆ sd_vector() [1/6]

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::sd_vector ( )
inline

Definition at line 152 of file sd_vector.hpp.

◆ sd_vector() [2/6]

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::sd_vector ( const sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > &  sd)
inline

Definition at line 154 of file sd_vector.hpp.

◆ sd_vector() [3/6]

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::sd_vector ( sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > &&  sd)
inline

Definition at line 192 of file sd_vector.hpp.

◆ sd_vector() [4/6]

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::sd_vector ( const bit_vector bv)
inline

Definition at line 194 of file sd_vector.hpp.

◆ sd_vector() [5/6]

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
template<class t_itr >
sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::sd_vector ( const t_itr  begin,
const t_itr  end 
)
inline

Definition at line 236 of file sd_vector.hpp.

◆ sd_vector() [6/6]

sdsl::sd_vector::sd_vector ( sd_vector_builder builder)
inline

Definition at line 271 of file sd_vector.hpp.

Member Function Documentation

◆ begin()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
iterator sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::begin ( ) const
inline

Definition at line 437 of file sd_vector.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
template<typename archive_t >
void sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 425 of file sd_vector.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
template<typename archive_t >
void sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 414 of file sd_vector.hpp.

◆ end()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
iterator sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::end ( ) const
inline

Definition at line 439 of file sd_vector.hpp.

◆ get_int()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
uint64_t sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::get_int ( size_type  idx,
const uint8_t  len = 64 
) const
inline

Get the integer value of the binary string of length len starting at position idx.

Parameters
idxStarting index of the binary representation of the integer.
lenLength of the binary representation of the integer. Default value is 64.
Returns
The integer value of the binary string of length len starting at position idx.
Precondition
idx+len-1 in [0..size()-1]
len in [1..64]

Definition at line 328 of file sd_vector.hpp.

◆ load()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
void sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::load ( std::istream &  in)
inline

Loads the data structure from the given istream.

Definition at line 403 of file sd_vector.hpp.

◆ operator!=()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
bool sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::operator!= ( const sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > &  v) const
inline

Definition at line 446 of file sd_vector.hpp.

◆ operator=() [1/2]

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
sd_vector & sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::operator= ( const sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > &  v)
inline

Definition at line 166 of file sd_vector.hpp.

◆ operator=() [2/2]

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
sd_vector & sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::operator= ( sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > &&  v)
inline

Definition at line 176 of file sd_vector.hpp.

◆ operator==()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
bool sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::operator== ( const sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > &  v) const
inline

Definition at line 441 of file sd_vector.hpp.

◆ operator[]()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
value_type sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::operator[] ( size_type  i) const
inline

Accessing the i-th element of the original bit_vector.

Parameters
iAn index i with $ 0 \leq i < size()  $.
Returns
The i-th bit of the original bit_vector
Time complexity
$ \Order{t_{select0} + n/m} $, where m equals the number of zeros
Remark
The time complexity can be easily improved to $\Order{t_{select0}+\log(n/m)}$ by using binary search in the second step.

Definition at line 298 of file sd_vector.hpp.

◆ serialize()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
size_type sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
inline

Serializes the data structure into the given ostream.

Definition at line 388 of file sd_vector.hpp.

◆ size()

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
size_type sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::size ( ) const
inline

Returns the size of the original bit vector.

Definition at line 385 of file sd_vector.hpp.

Member Data Documentation

◆ high

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
const hi_bit_vector_type& sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::high = m_high

Definition at line 147 of file sd_vector.hpp.

◆ high_0_select

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
const select_0_support_type& sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::high_0_select = m_high_0_select

Definition at line 150 of file sd_vector.hpp.

◆ high_1_select

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
const select_1_support_type& sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::high_1_select = m_high_1_select

Definition at line 149 of file sd_vector.hpp.

◆ low

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
const int_vector& sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::low = m_low

Definition at line 148 of file sd_vector.hpp.

◆ wl

template<class t_hi_bit_vector = bit_vector, class t_select_1 = typename t_hi_bit_vector::select_1_type, class t_select_0 = typename t_hi_bit_vector::select_0_type>
const uint8_t& sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::wl = m_wl

Definition at line 146 of file sd_vector.hpp.


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