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_vector >	const_iterator

typedef const_iterator	iterator

typedef const value_type	const_reference

typedef const_reference	reference

typedef const_reference *	pointer

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_vector &	operator= (dac_vector const &v)

dac_vector &	operator= (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_b	Split block size.
t_rank	Rank 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

c	A 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:

/builddir/build/BUILD/sdsl-lite-3.0.3-build/sdsl-lite-3.0.3/include/sdsl/dac_vector.hpp

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ difference_type

◆ index_category

◆ iterator

◆ pointer

◆ rank_support_type

◆ reference

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ dac_vector() [1/5]

◆ dac_vector() [2/5]

◆ dac_vector() [3/5]

◆ dac_vector() [4/5]

◆ dac_vector() [5/5]

Member Function Documentation

◆ begin()

◆ CEREAL_LOAD_FUNCTION_NAME()

◆ CEREAL_SAVE_FUNCTION_NAME()

◆ empty()

◆ end()

◆ load()

◆ max_size()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ serialize()

◆ size()