operations_research::CompressedStrongVector< EntryIndex, Index > Class Template Reference

Detailed Description

template<typename EntryIndex, typename Index>
class operations_research::CompressedStrongVector< EntryIndex, Index >

A compressed vector of strong indices (e.g. SubsetIndex, ElementIndex), with EntryIndex indicating the position in the vector (e.g. RowEntryIndex or ColumnEntryIndex). The vector is compressed in a variable-length encoding, where each element is encoded as a delta from the previous element. The vector is stored in a byte stream, which is addressed byte-by-byte, which is necessary to store variable-length integers. The variable-length encoding is little-endian base128 (LEB128) as used by protobufs. Since we only use non-negative integers, there is no need to encode the sign bit (so non-zigzag encoding or similar techniques).

Todo

(user): There is a lot of room for optimization in this class.

• Use a bit-twiddling approach to encode and decode integers.
• Use another simpler variable encoding (base on vu128) using a single 64-bit word and limited to storing 8 bytes with 7 bits per byte. A 64-bit word would contain 8*7 = 56 bits. This is enough for an index in an array with 2^56 = 7.2e16 elements, and more that the address space of current (2025) machines.
• Access memory by 64-bit words instead of bytes.
• Make Codecs a template parameter of CompressedStrongVector (?)

Definition at line 103 of file base_types.h.

#include <base_types.h>

Public Types
using	iterator = CompressedStrongVectorIterator<EntryIndex, Index>
using	const_iterator = CompressedStrongVectorIterator<EntryIndex, Index>
using	value_type = Index

Public Member Functions
	CompressedStrongVector ()
	CompressedStrongVector (const util_intops::StrongVector< EntryIndex, Index > &strong_vector)
	CompressedStrongVector (absl::Span< const Index > vec)
void	push_back (Index x)
	Appends an x to the vector in a compressed form.
const std::vector< uint8_t > &	byte_stream () const
	Returns a reference to the underlying byte stream.
size_t	size_in_bytes () const
	Returns the number of bytes needed to store the vector.
bool	empty () const
void	Reserve (size_t n)
	Reserves space for n bytes.
iterator	begin ()
	For range-for loops.
iterator	end ()
const_iterator	begin () const
	For const range-for loops.
const_iterator	end () const

Member Typedef Documentation

const_iterator

template<typename EntryIndex, typename Index>

using operations_research::CompressedStrongVector< EntryIndex, Index >::const_iterator = CompressedStrongVectorIterator<EntryIndex, Index>

Definition at line 106 of file base_types.h.

iterator

template<typename EntryIndex, typename Index>

using operations_research::CompressedStrongVector< EntryIndex, Index >::iterator = CompressedStrongVectorIterator<EntryIndex, Index>

Definition at line 105 of file base_types.h.

value_type

template<typename EntryIndex, typename Index>

using operations_research::CompressedStrongVector< EntryIndex, Index >::value_type = Index

Definition at line 107 of file base_types.h.

Constructor & Destructor Documentation

CompressedStrongVector() [1/3]

template<typename EntryIndex, typename Index>

operations_research::CompressedStrongVector< EntryIndex, Index >::CompressedStrongVector ( )

inlineexplicit

Definition at line 109 of file base_types.h.

CompressedStrongVector() [2/3]

template<typename EntryIndex, typename Index>

operations_research::CompressedStrongVector< EntryIndex, Index >::CompressedStrongVector ( const util_intops::StrongVector< EntryIndex, Index > & strong_vector )

inlineexplicit

Initializes the compressed vector from a strong vector.

Todo

(user): try to guess the size of the compressed vector and pre-allocate it. Experience shows it consumes between 1 and 2 bytes per Index on average.

Definition at line 115 of file base_types.h.

CompressedStrongVector() [3/3]

template<typename EntryIndex, typename Index>

operations_research::CompressedStrongVector< EntryIndex, Index >::CompressedStrongVector ( absl::Span< const Index > vec )

inlineexplicit

Definition at line 123 of file base_types.h.

Member Function Documentation

begin() [1/2]

template<typename EntryIndex, typename Index>

iterator operations_research::CompressedStrongVector< EntryIndex, Index >::begin ( )

inline

For range-for loops.

Definition at line 145 of file base_types.h.

begin() [2/2]

template<typename EntryIndex, typename Index>

const_iterator operations_research::CompressedStrongVector< EntryIndex, Index >::begin ( ) const

inline

For const range-for loops.

Definition at line 149 of file base_types.h.

byte_stream()

template<typename EntryIndex, typename Index>

const std::vector< uint8_t > & operations_research::CompressedStrongVector< EntryIndex, Index >::byte_stream ( ) const

inline

Returns a reference to the underlying byte stream.

Definition at line 134 of file base_types.h.

empty()

template<typename EntryIndex, typename Index>

bool operations_research::CompressedStrongVector< EntryIndex, Index >::empty ( ) const

inline

Definition at line 139 of file base_types.h.

end() [1/2]

template<typename EntryIndex, typename Index>

iterator operations_research::CompressedStrongVector< EntryIndex, Index >::end ( )

inline

Definition at line 146 of file base_types.h.

end() [2/2]

template<typename EntryIndex, typename Index>

const_iterator operations_research::CompressedStrongVector< EntryIndex, Index >::end ( ) const

inline

Definition at line 150 of file base_types.h.

push_back()

template<typename EntryIndex, typename Index>

void operations_research::CompressedStrongVector< EntryIndex, Index >::push_back ( Index x )

inline

Appends an x to the vector in a compressed form.

Definition at line 131 of file base_types.h.

Reserve()

template<typename EntryIndex, typename Index>

void operations_research::CompressedStrongVector< EntryIndex, Index >::Reserve ( size_t n )

inline

Reserves space for n bytes.

Definition at line 142 of file base_types.h.

size_in_bytes()

template<typename EntryIndex, typename Index>

size_t operations_research::CompressedStrongVector< EntryIndex, Index >::size_in_bytes ( ) const

inline

Returns the number of bytes needed to store the vector.

Definition at line 137 of file base_types.h.

---

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

• ortools/set_cover/base_types.h