SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 (sd_vector const &sd)
sd_vectoroperator= (sd_vector const &v)
sd_vectoroperator= (sd_vector &&v)
 sd_vector (sd_vector &&sd)
 sd_vector (bit_vector const &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.
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.
size_type size () const
 Returns the size of the original bit vector.
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, 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.
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== (sd_vector const &v) const
bool operator!= (sd_vector const &v) const

Public Attributes

uint8_t const & wl = m_wl
hi_bit_vector_type const & high = m_high
int_vector const & low = m_low
select_1_support_type const & high_1_select = m_high_1_select
select_0_support_type const & high_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 134 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 141 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 139 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 151 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 142 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 140 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 146 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 147 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 143 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 148 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 144 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 149 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 137 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 138 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 172 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 ( sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > const & sd)
inline

Definition at line 175 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 213 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 ( bit_vector const & bv)
inline

Definition at line 218 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 260 of file sd_vector.hpp.

◆ sd_vector() [6/6]

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

Definition at line 301 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 475 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 463 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 452 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 480 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 359 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 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>
bool 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 > const & v) const
inline

Definition at line 490 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= ( sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > && v)
inline

Definition at line 197 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 > const & v)
inline

Definition at line 187 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== ( sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > const & v) const
inline

Definition at line 485 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 328 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 426 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 420 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>
hi_bit_vector_type const& sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::high = m_high

Definition at line 167 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>
select_0_support_type const& sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::high_0_select = m_high_0_select

Definition at line 170 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>
select_1_support_type const& sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::high_1_select = m_high_1_select

Definition at line 169 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>
int_vector const& sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::low = m_low

Definition at line 168 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>
uint8_t const& sdsl::sd_vector< t_hi_bit_vector, t_select_1, t_select_0 >::wl = m_wl

Definition at line 166 of file sd_vector.hpp.


The documentation for this class was generated from the following file:
  • /builddir/build/BUILD/sdsl-lite-3.0.3-build/sdsl-lite-3.0.3/include/sdsl/sd_vector.hpp