operations_research::DenseSet< T, auto_resize > Class Template Reference

#include <dense_set.h>

Public Types
using	iterator = typename std::vector<T>::const_iterator
using	const_iterator = typename std::vector<T>::const_iterator
using	value_type = T

Public Member Functions
const_iterator	begin () const
const_iterator	end () const
size_t	size () const
bool	empty () const
void	reserve (size_t size)
size_t	capacity () const
std::pair< iterator, bool >	insert (T value)
iterator	find (T value)
bool	contains (T value) const
void	erase (iterator it)
int	erase (T value)
absl::Span< const T >	values () const
void	clear ()

Static Public Attributes
static constexpr bool	kAutoResize = auto_resize

Detailed Description

template<typename T, bool auto_resize = true>
class operations_research::DenseSet< T, auto_resize >

A set of dense non-negative integer values stored in a dense vector.

This is useful when we want to iterate over a small subset of the possible values and reuse the memory, or if we want to randomly sample from the set.

If the set is usually small but occasionally very large, iterating over a regular hash_set would be less efficient as you would (internal to the hash table iterator) have have to iterate over all the buckets in the hash table even if empty. If you clear the set frequently to avoid this, you would grow and rehash when you have a larger set.

If resize=false, users must call reserve(K) where K > any key before calling any other method.

Definition at line 39 of file dense_set.h.

Member Typedef Documentation

const_iterator

template<typename T , bool auto_resize = true>

using operations_research::DenseSet< T, auto_resize >::const_iterator = typename std::vector<T>::const_iterator

Definition at line 42 of file dense_set.h.

iterator

template<typename T , bool auto_resize = true>

using operations_research::DenseSet< T, auto_resize >::iterator = typename std::vector<T>::const_iterator

Definition at line 41 of file dense_set.h.

value_type

template<typename T , bool auto_resize = true>

using operations_research::DenseSet< T, auto_resize >::value_type = T

Definition at line 43 of file dense_set.h.

Member Function Documentation

begin()

template<typename T , bool auto_resize = true>

const_iterator operations_research::DenseSet< T, auto_resize >::begin ( ) const

inline

Definition at line 46 of file dense_set.h.

capacity()

template<typename T , bool auto_resize = true>

size_t operations_research::DenseSet< T, auto_resize >::capacity ( ) const

inline

Definition at line 54 of file dense_set.h.

clear()

template<typename T , bool auto_resize = true>

void operations_research::DenseSet< T, auto_resize >::clear ( )

inline

We expect values_ to be much smaller than the total number of possible values, so just clear entries in the set.

Definition at line 104 of file dense_set.h.

contains()

template<typename T , bool auto_resize = true>

bool operations_research::DenseSet< T, auto_resize >::contains ( T value ) const

inline

Definition at line 74 of file dense_set.h.

empty()

template<typename T , bool auto_resize = true>

bool operations_research::DenseSet< T, auto_resize >::empty ( ) const

inline

Definition at line 49 of file dense_set.h.

end()

template<typename T , bool auto_resize = true>

const_iterator operations_research::DenseSet< T, auto_resize >::end ( ) const

inline

Definition at line 47 of file dense_set.h.

erase() [1/2]

template<typename T , bool auto_resize = true>

void operations_research::DenseSet< T, auto_resize >::erase ( iterator it )

inline

This is a hack to allow erase to work with a const iterator.

Definition at line 79 of file dense_set.h.

erase() [2/2]

template<typename T , bool auto_resize = true>

int operations_research::DenseSet< T, auto_resize >::erase ( T value )

inline

Definition at line 89 of file dense_set.h.

find()

template<typename T , bool auto_resize = true>

iterator operations_research::DenseSet< T, auto_resize >::find ( T value )

inline

Definition at line 67 of file dense_set.h.

insert()

template<typename T , bool auto_resize = true>

std::pair< iterator, bool > operations_research::DenseSet< T, auto_resize >::insert ( T value )

inline

Definition at line 56 of file dense_set.h.

reserve()

template<typename T , bool auto_resize = true>

void operations_research::DenseSet< T, auto_resize >::reserve ( size_t size )

inline

Definition at line 50 of file dense_set.h.

size()

template<typename T , bool auto_resize = true>

size_t operations_research::DenseSet< T, auto_resize >::size ( ) const

inline

Definition at line 48 of file dense_set.h.

values()

template<typename T , bool auto_resize = true>

absl::Span< const T > operations_research::DenseSet< T, auto_resize >::values ( ) const

inline

The ordering is deterministic given the same sequence of inserts and erases but is arbitrary and should not be relied upon.

Definition at line 102 of file dense_set.h.

Member Data Documentation

kAutoResize

template<typename T , bool auto_resize = true>

bool operations_research::DenseSet< T, auto_resize >::kAutoResize = auto_resize

staticconstexpr

Definition at line 44 of file dense_set.h.

---

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

• ortools/util/dense_set.h