Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Member Functions | List of all members
operations_research::sat::CompactVectorVector< K, V > Class Template Reference

#include <util.h>

Public Member Functions

size_t size () const
 Size of the "key" space, always in [0, size()).
 
bool empty () const
 
absl::Span< V > operator[] (K key)
 
absl::Span< const V > operator[] (K key) const
 
std::vector< absl::Span< const V > > AsVectorOfSpan () const
 
void clear ()
 Restore to empty vector<vector<>>.
 
void reserve (int size)
 Reserve memory if it is already known or tightly estimated.
 
void reserve (int size, int num_terms)
 
template<typename Keys , typename Values >
void ResetFromFlatMapping (Keys keys, Values values)
 
void ResetFromTranspose (const CompactVectorVector< V, K > &other, int min_transpose_size=0)
 Similar to ResetFromFlatMapping().
 
int Add (absl::Span< const V > values)
 
template<typename L >
int AddLiterals (const std::vector< L > &wrapped_values)
 
void RemoveBySwap (K key, int index)
 
void ReplaceValuesBySmallerSet (K key, absl::Span< const V > values)
 
void emplace_back (V const *begin, V const *end)
 

Detailed Description

template<typename K = int, typename V = int>
class operations_research::sat::CompactVectorVector< K, V >

Small utility class to store a vector<vector<>> where one can only append new vector and never change previously added ones. This allows to store a static key -> value(s) mapping.

This is a lot more compact memorywise and thus faster than vector<vector<>>.

Note
we implement a really small subset of the vector<vector<>> API.

We support int and StrongType for key K and any copyable type for value V.

Definition at line 69 of file util.h.

Member Function Documentation

◆ Add()

template<typename K , typename V >
int operations_research::sat::CompactVectorVector< K, V >::Add ( absl::Span< const V > values)
inline

Append a new entry. Returns the previous size() as this is convenient for how we use it.

Definition at line 739 of file util.h.

◆ AddLiterals()

template<typename K , typename V >
template<typename L >
int operations_research::sat::CompactVectorVector< K, V >::AddLiterals ( const std::vector< L > & wrapped_values)
inline

Hacky: same as Add() but for sat::Literal or any type from which we can get a value type V via L.Index().value().

Definition at line 758 of file util.h.

◆ AsVectorOfSpan()

template<typename K , typename V >
std::vector< absl::Span< const V > > operations_research::sat::CompactVectorVector< K, V >::AsVectorOfSpan ( ) const
inline

Definition at line 803 of file util.h.

◆ clear()

template<typename K , typename V >
void operations_research::sat::CompactVectorVector< K, V >::clear ( )
inline

Restore to empty vector<vector<>>.

Definition at line 812 of file util.h.

◆ emplace_back()

template<typename K = int, typename V = int>
void operations_research::sat::CompactVectorVector< K, V >::emplace_back ( V const * begin,
V const * end )
inline

Interface so this can be used as an output of FindStronglyConnectedComponents().

Definition at line 144 of file util.h.

◆ empty()

template<typename K , typename V >
bool operations_research::sat::CompactVectorVector< K, V >::empty ( ) const
inline

Definition at line 824 of file util.h.

◆ operator[]() [1/2]

template<typename K , typename V >
absl::Span< V > operations_research::sat::CompactVectorVector< K, V >::operator[] ( K key)
inline

Getters, either via [] or via a wrapping to be compatible with older api.

Warning
Spans are only valid until the next modification!

Definition at line 791 of file util.h.

◆ operator[]() [2/2]

template<typename K , typename V >
absl::Span< const V > operations_research::sat::CompactVectorVector< K, V >::operator[] ( K key) const
inline

Definition at line 780 of file util.h.

◆ RemoveBySwap()

template<typename K = int, typename V = int>
void operations_research::sat::CompactVectorVector< K, V >::RemoveBySwap ( K key,
int index )
inline

We lied when we said this is a pure read-only class :) It is possible to shrink inner vectors with not much cost.

Removes the element at index from this[key] by swapping it with this[key].back() and then decreasing this key size. It is an error to call this on an empty inner vector.

Definition at line 130 of file util.h.

◆ ReplaceValuesBySmallerSet()

template<typename K , typename V >
void operations_research::sat::CompactVectorVector< K, V >::ReplaceValuesBySmallerSet ( K key,
absl::Span< const V > values )
inline

Replace the values at the given key. This will crash if there are more values than before.

Definition at line 748 of file util.h.

◆ reserve() [1/2]

template<typename K = int, typename V = int>
void operations_research::sat::CompactVectorVector< K, V >::reserve ( int size)
inline

Reserve memory if it is already known or tightly estimated.

Definition at line 86 of file util.h.

◆ reserve() [2/2]

template<typename K = int, typename V = int>
void operations_research::sat::CompactVectorVector< K, V >::reserve ( int size,
int num_terms )
inline

Definition at line 90 of file util.h.

◆ ResetFromFlatMapping()

template<typename K , typename V >
template<typename Keys , typename Values >
void operations_research::sat::CompactVectorVector< K, V >::ResetFromFlatMapping ( Keys keys,
Values values )
inline

Given a flat mapping (keys[i] -> values[i]) with two parallel vectors, not necessarily sorted by key, regroup the same key so that CompactVectorVector[key] list all values in the order in which they appear.

We only check keys.size(), so this can be used with IdentityMap() as second argument.

Compute maximum index.

Compute sizes_;

Compute starts_;

Copy data and uses starts as temporary indices.

Restore starts_.

Definition at line 830 of file util.h.

◆ ResetFromTranspose()

template<typename K , typename V >
void operations_research::sat::CompactVectorVector< K, V >::ResetFromTranspose ( const CompactVectorVector< V, K > & other,
int min_transpose_size = 0 )
inline

Similar to ResetFromFlatMapping().

Initialize this vector from the transpose of another. IMPORTANT: This cannot be called with the vector itself.

If min_transpose_size is given, then the transpose will have at least this size even if some of the last keys do not appear in other.

If this is called twice in a row, then it has the side effect of sorting all inner vectors by values !

Compute maximum index.

Compute sizes_;

Compute starts_;

Copy data and uses starts as temporary indices.

Restore starts_.

Definition at line 867 of file util.h.

◆ size()

template<typename K , typename V >
size_t operations_research::sat::CompactVectorVector< K, V >::size ( ) const
inline

Size of the "key" space, always in [0, size()).

Definition at line 819 of file util.h.

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