SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::dac_vector< t_b, t_rank > Class Template Reference

A generic immutable space-saving vector class for unsigned integers. More...

#include <dac_vector.hpp>

Public Types

typedef int_vector ::value_type value_type
 
typedef random_access_const_iterator< dac_vectorconst_iterator
 
typedef const_iterator iterator
 
typedef const value_type const_reference
 
typedef const_reference reference
 
typedef const_referencepointer
 
typedef const pointer const_pointer
 
typedef int_vector ::size_type size_type
 
typedef ptrdiff_t difference_type
 
typedef t_rank rank_support_type
 
typedef iv_tag index_category
 

Public Member Functions

 dac_vector ()=default
 
 dac_vector (dac_vector const &v)
 
 dac_vector (dac_vector &&v)
 
dac_vectoroperator= (dac_vector const &v)
 
dac_vectoroperator= (dac_vector &&v)
 
template<class Container>
 dac_vector (Container const &c)
 Constructor for a Container of unsigned integers.
 
template<uint8_t int_width>
 dac_vector (int_vector_buffer< int_width > &v_buf)
 Constructor for an int_vector_buffer of unsigned integers.
 
size_type size () const
 The number of elements in the dac_vector.
 
bool empty () const
 Returns if the dac_vector is empty.
 
const const_iterator begin () const
 Iterator that points to the first element of the dac_vector.
 
const const_iterator end () const
 Iterator that points to the position after the last element of the dac_vector.
 
value_type operator[] (size_type i) const
 []-operator
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serializes the dac_vector to a stream.
 
void load (std::istream &in)
 Load from a stream.
 
template<typename archive_t>
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 Serialise (save) via cereal.
 
template<typename archive_t>
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 
bool operator== (dac_vector const &v) const
 
bool operator!= (dac_vector const &v) const
 

Static Public Member Functions

static size_type max_size ()
 Return the largest size that this container can ever have.
 

Detailed Description

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
class sdsl::dac_vector< t_b, t_rank >

A generic immutable space-saving vector class for unsigned integers.

The values of a dac_vector are immutable after the constructor call. The ,,escaping'' technique is used to encode values. This is defined as follows (see [1]): A k-bit integer is split into $K=\lceil k/(b-1)\rceil$ bits each and encoded into $K$ blocks of $ b $ bits each. All but the last block are marked with by a 1 in the most significant bit. Escaping with b=8 is also known as vbyte-coding (see [2]). A experimental study of using escaping for the LCP array is given in [3].

Time complexity
  • $\Order{\log n/b}$ worst case, where b is the number of bits in a block
References
[1] F. Transier and P. Sanders: ,,Engineering Basic Search Algorithms of an In-Memory Text Search Engine'', ACM Transactions on Information Systems, Vol. 29, No.1, Article 2, 2010 [2] H.E. Williams and J. Zobel: ,,Compressing integers for fast file access'', Computing Journal Vol 43, No.3, 1999 [3] N. Brisboa, S. Ladra, G. Navarro: ,,Directly addressable variable- length codes'', Proceedings of SPIRE 2009.
Template Parameters
t_bSplit block size.
t_rankRank structure to navigate between the different levels.

Definition at line 59 of file dac_vector.hpp.

Member Typedef Documentation

◆ const_iterator

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef random_access_const_iterator<dac_vector> sdsl::dac_vector< t_b, t_rank >::const_iterator

Definition at line 67 of file dac_vector.hpp.

◆ const_pointer

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef const pointer sdsl::dac_vector< t_b, t_rank >::const_pointer

Definition at line 72 of file dac_vector.hpp.

◆ const_reference

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef const value_type sdsl::dac_vector< t_b, t_rank >::const_reference

Definition at line 69 of file dac_vector.hpp.

◆ difference_type

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef ptrdiff_t sdsl::dac_vector< t_b, t_rank >::difference_type

Definition at line 74 of file dac_vector.hpp.

◆ index_category

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef iv_tag sdsl::dac_vector< t_b, t_rank >::index_category

Definition at line 76 of file dac_vector.hpp.

◆ iterator

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef const_iterator sdsl::dac_vector< t_b, t_rank >::iterator

Definition at line 68 of file dac_vector.hpp.

◆ pointer

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef const_reference* sdsl::dac_vector< t_b, t_rank >::pointer

Definition at line 71 of file dac_vector.hpp.

◆ rank_support_type

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef t_rank sdsl::dac_vector< t_b, t_rank >::rank_support_type

Definition at line 75 of file dac_vector.hpp.

◆ reference

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef const_reference sdsl::dac_vector< t_b, t_rank >::reference

Definition at line 70 of file dac_vector.hpp.

◆ size_type

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef int_vector ::size_type sdsl::dac_vector< t_b, t_rank >::size_type

Definition at line 73 of file dac_vector.hpp.

◆ value_type

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
typedef int_vector ::value_type sdsl::dac_vector< t_b, t_rank >::value_type

Definition at line 66 of file dac_vector.hpp.

Constructor & Destructor Documentation

◆ dac_vector() [1/5]

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
sdsl::dac_vector< t_b, t_rank >::dac_vector ( )
default

◆ dac_vector() [2/5]

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
sdsl::dac_vector< t_b, t_rank >::dac_vector ( dac_vector< t_b, t_rank > const & v)
inline

Definition at line 88 of file dac_vector.hpp.

◆ dac_vector() [3/5]

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
sdsl::dac_vector< t_b, t_rank >::dac_vector ( dac_vector< t_b, t_rank > && v)
inline

Definition at line 98 of file dac_vector.hpp.

◆ dac_vector() [4/5]

template<uint8_t t_b, typename t_rank>
template<class Container>
sdsl::dac_vector< t_b, t_rank >::dac_vector ( Container const & c)

Constructor for a Container of unsigned integers.

Parameters
cA container of unsigned integers.
Precondition
No two adjacent values should be equal.

Definition at line 219 of file dac_vector.hpp.

◆ dac_vector() [5/5]

template<uint8_t t_b, typename t_rank>
template<uint8_t int_width>
sdsl::dac_vector< t_b, t_rank >::dac_vector ( int_vector_buffer< int_width > & v_buf)

Constructor for an int_vector_buffer of unsigned integers.

Definition at line 302 of file dac_vector.hpp.

Member Function Documentation

◆ begin()

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
const const_iterator sdsl::dac_vector< t_b, t_rank >::begin ( ) const
inline

Iterator that points to the first element of the dac_vector.

Definition at line 155 of file dac_vector.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint8_t t_b, typename t_rank>
template<typename archive_t>
void sdsl::dac_vector< t_b, t_rank >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)

Definition at line 411 of file dac_vector.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint8_t t_b, typename t_rank>
template<typename archive_t>
void sdsl::dac_vector< t_b, t_rank >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const

Serialise (save) via cereal.

Definition at line 400 of file dac_vector.hpp.

◆ empty()

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
bool sdsl::dac_vector< t_b, t_rank >::empty ( ) const
inline

Returns if the dac_vector is empty.

Definition at line 149 of file dac_vector.hpp.

◆ end()

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
const const_iterator sdsl::dac_vector< t_b, t_rank >::end ( ) const
inline

Iterator that points to the position after the last element of the dac_vector.

Definition at line 161 of file dac_vector.hpp.

◆ load()

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
void sdsl::dac_vector< t_b, t_rank >::load ( std::istream & in)
inline

Load from a stream.

Definition at line 189 of file dac_vector.hpp.

◆ max_size()

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
static size_type sdsl::dac_vector< t_b, t_rank >::max_size ( )
inlinestatic

Return the largest size that this container can ever have.

Definition at line 143 of file dac_vector.hpp.

◆ operator!=()

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
bool sdsl::dac_vector< t_b, t_rank >::operator!= ( dac_vector< t_b, t_rank > const & v) const
inline

Definition at line 211 of file dac_vector.hpp.

◆ operator=() [1/2]

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
dac_vector & sdsl::dac_vector< t_b, t_rank >::operator= ( dac_vector< t_b, t_rank > && v)
inline

Definition at line 112 of file dac_vector.hpp.

◆ operator=() [2/2]

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
dac_vector & sdsl::dac_vector< t_b, t_rank >::operator= ( dac_vector< t_b, t_rank > const & v)
inline

Definition at line 102 of file dac_vector.hpp.

◆ operator==()

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
bool sdsl::dac_vector< t_b, t_rank >::operator== ( dac_vector< t_b, t_rank > const & v) const
inline

Definition at line 205 of file dac_vector.hpp.

◆ operator[]()

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
value_type sdsl::dac_vector< t_b, t_rank >::operator[] ( size_type i) const
inline

[]-operator

Definition at line 167 of file dac_vector.hpp.

◆ serialize()

template<uint8_t t_b, typename t_rank>
dac_vector::size_type sdsl::dac_vector< t_b, t_rank >::serialize ( std::ostream & out,
structure_tree_node * v = nullptr,
std::string name = "" ) const

Serializes the dac_vector to a stream.

Definition at line 385 of file dac_vector.hpp.

◆ size()

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
size_type sdsl::dac_vector< t_b, t_rank >::size ( ) const
inline

The number of elements in the dac_vector.

Definition at line 138 of file dac_vector.hpp.


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