Detailed Description

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>
class mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >

A STL-like container which looks and behaves (almost exactly) like a std::map<> but is implemented as a linear std::vector<> indexed by KEY.

Note that KEY must be integer types only (size_t, uint32_t, etc.) This implementation is much more efficient than std::map<> when the most common operation is accesing elements by KEY with find() or [], and the range of KEY values starts at 0 (or a reasonable low number).

This container is internally implemented as a linear array (std::vector) of the same fundamental type than the equivalent std::map<K,V>, that is, elements are std::pair<K,V> (note that K is NOT const as in std::map). I know, I know... this implementation wastes a lot of useless key elements in the pair.first when indices are already implicit in the std::vector<> order... but I promise I'll pay a beer to whoever show me an efficient alternative. If failed, update this comment: COUNTER OF WASTED HOURS WITH THIS: 3h

Note that there is one fundamental difference wrt std::map<>: if you start with an empty map_as_vector<> and insert one element at the i'th position (with either [] or insert), the elements [0,i-1] will also exist then, but both their first & second entries (for the corresponding std::pair) will be undefined. This was intentional in order to gain efficiency (in particular, each std::pair<> doesn't have a constructor when resizing the underlying std::vector).

The default underlying non-associative container is a "memory-aligned std::vector<>", but it can be changed to a standard vector<> or to a deque<> (to avoid memory reallocations) by changing the template parameter VECTOR_T.

Note: Defined in #include <mrpt/utils/map_as_vector.h>

Definition at line 47 of file map_as_vector.h.

#include <mrpt/utils/map_as_vector.h>

Inheritance diagram for mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >:

Public Member Functions
Constructors, read/write access and other operations
	map_as_vector ()
	< Default constructor - does nothing */ More...

	map_as_vector (const map_as_vector< KEY, VALUE > &o)
	Copy constructor. More...

size_t	size () const

bool	empty () const

size_type	count (const key_type i) const
	Count how many entries have a given key value - unlike std::map<K,V>, recall that this class will say an element i<N-1 exists just due to an insertion of element at N. More...

size_type	max_size () const
	Maximum size due to system limits. More...

const vec_t &	getVector () const
	Return a read-only reference to the internal vector. More...

void	clear ()
	Clear the contents of this container. More...

void	swap (map_as_vector< KEY, VALUE > &o)
	Efficient swap with another object. More...

VALUE &	operator[] (const size_t i)
	Write/read via [i] operator, that creates all elements up to (and including) the i'th if they didn't exist already. More...

void	insert (const iterator &guess_point, const value_type &keyvalpair)
	Insert pair<key,val>, as in std::map (guess_point is actually ignored in this class) More...

void	insert (const value_type &keyvalpair)
	Insert pair<key,val>, as in std::map. More...

iterator	find (const size_t i)
	Constant-time find, returning an iterator to the <key,val> pair or to end() if not found (that is, if it's above the maximum index in the vector) More...

const_iterator	find (const size_t i) const
	Constant-time find, returning an iterator to the <key,val> pair or to end() if not found (that is, if it's above the maximum index in the vector) More...

Private Attributes
vec_t	m_vec
	The actual container. More...

Iterators stuff and other types
typedef KEY	key_type

typedef std::pair< KEY, VALUE >	value_type

typedef VECTOR_T	vec_t

typedef vec_t::size_type	size_type

typedef vec_t::iterator	iterator

typedef vec_t::const_iterator	const_iterator

typedef std::reverse_iterator< iterator >	reverse_iterator

typedef std::reverse_iterator< const_iterator >	const_reverse_iterator

iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

reverse_iterator	rbegin ()

const_reverse_iterator	rbegin () const

reverse_iterator	rend ()

const_reverse_iterator	rend () const

Member Typedef Documentation

◆ const_iterator

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

typedef vec_t::const_iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::const_iterator

Definition at line 57 of file map_as_vector.h.

◆ const_reverse_iterator

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

typedef std::reverse_iterator<const_iterator> mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::const_reverse_iterator

Definition at line 59 of file map_as_vector.h.

◆ iterator

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

typedef vec_t::iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::iterator

Definition at line 56 of file map_as_vector.h.

◆ key_type

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

typedef KEY mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::key_type

Definition at line 52 of file map_as_vector.h.

◆ reverse_iterator

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

typedef std::reverse_iterator<iterator> mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::reverse_iterator

Definition at line 58 of file map_as_vector.h.

◆ size_type

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

typedef vec_t::size_type mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::size_type

Definition at line 55 of file map_as_vector.h.

◆ value_type

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

typedef std::pair<KEY,VALUE> mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::value_type

Definition at line 53 of file map_as_vector.h.

◆ vec_t

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

typedef VECTOR_T mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::vec_t

Definition at line 54 of file map_as_vector.h.

Constructor & Destructor Documentation

◆ map_as_vector() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::map_as_vector ( )

inline

< Default constructor - does nothing */

Definition at line 77 of file map_as_vector.h.

◆ map_as_vector() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::map_as_vector ( const map_as_vector< KEY, VALUE > & o )

inline

Copy constructor.

Definition at line 79 of file map_as_vector.h.

Member Function Documentation

◆ begin() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::begin ( )

inline

Definition at line 61 of file map_as_vector.h.

Referenced by mrpt::utils::map_as_vector< KEY, VALUE >::rend().

◆ begin() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

const_iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::begin ( ) const

inline

Definition at line 63 of file map_as_vector.h.

◆ clear()

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

void mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::clear ( )

inline

Clear the contents of this container.

Definition at line 94 of file map_as_vector.h.

Referenced by mrpt::math::MatrixBlockSparseCols< Scalar, NROWS, NCOLS, INFO, HAS_REMAP, INDEX_REMAP_MAP_IMPL >::clearAll().

◆ count()

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

size_type mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::count ( const key_type i ) const

inline

Count how many entries have a given key value - unlike std::map<K,V>, recall that this class will say an element i<N-1 exists just due to an insertion of element at N.

Definition at line 85 of file map_as_vector.h.

◆ empty()

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

bool mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::empty ( ) const

inline

Definition at line 82 of file map_as_vector.h.

◆ end() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::end ( )

inline

Definition at line 62 of file map_as_vector.h.

Referenced by mrpt::utils::map_as_vector< KEY, VALUE >::rbegin().

◆ end() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

const_iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::end ( ) const

inline

Definition at line 64 of file map_as_vector.h.

◆ find() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::find ( const size_t i )

inline

Constant-time find, returning an iterator to the <key,val> pair or to end() if not found (that is, if it's above the maximum index in the vector)

Definition at line 112 of file map_as_vector.h.

◆ find() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

const_iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::find ( const size_t i ) const

inline

Constant-time find, returning an iterator to the <key,val> pair or to end() if not found (that is, if it's above the maximum index in the vector)

Definition at line 114 of file map_as_vector.h.

◆ getVector()

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

const vec_t& mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::getVector ( ) const

inline

Return a read-only reference to the internal vector.

Definition at line 91 of file map_as_vector.h.

◆ insert() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

void mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::insert	(	const iterator &	guess_point,
		const value_type &	keyvalpair
	)

inline

Insert pair<key,val>, as in std::map (guess_point is actually ignored in this class)

Definition at line 107 of file map_as_vector.h.

◆ insert() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

void mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::insert ( const value_type & keyvalpair )

inline

Insert pair<key,val>, as in std::map.

Definition at line 109 of file map_as_vector.h.

◆ max_size()

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

size_type mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::max_size ( ) const

inline

Maximum size due to system limits.

Definition at line 88 of file map_as_vector.h.

◆ operator[]()

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

VALUE& mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::operator[] ( const size_t i )

inline

Write/read via [i] operator, that creates all elements up to (and including) the i'th if they didn't exist already.

Definition at line 100 of file map_as_vector.h.

Referenced by mrpt::utils::map_as_vector< KEY, VALUE >::insert().

◆ rbegin() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

reverse_iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::rbegin ( )

inline

Definition at line 65 of file map_as_vector.h.

◆ rbegin() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

const_reverse_iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::rbegin ( ) const

inline

Definition at line 66 of file map_as_vector.h.

◆ rend() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

reverse_iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::rend ( )

inline

Definition at line 67 of file map_as_vector.h.

◆ rend() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

const_reverse_iterator mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::rend ( ) const

inline

Definition at line 68 of file map_as_vector.h.

◆ size()

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

size_t mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::size ( ) const

inline

Definition at line 81 of file map_as_vector.h.

◆ swap()

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

void mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::swap ( map_as_vector< KEY, VALUE > & o )

inline

Efficient swap with another object.

Definition at line 97 of file map_as_vector.h.

Member Data Documentation

◆ m_vec

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>

vec_t mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >::m_vec

private

The actual container.

Definition at line 71 of file map_as_vector.h.

Detailed Description

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t> class mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >

Public Member Functions

Private Attributes

Iterators stuff and other types

Member Typedef Documentation

◆ const_iterator

◆ const_reverse_iterator

◆ iterator

◆ key_type

◆ reverse_iterator

◆ size_type

◆ value_type

◆ vec_t

Constructor & Destructor Documentation

◆ map_as_vector() [1/2]

◆ map_as_vector() [2/2]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ count()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ getVector()

◆ insert() [1/2]

◆ insert() [2/2]

◆ max_size()

◆ operator[]()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ size()

◆ swap()

Member Data Documentation

◆ m_vec

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t>
class mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T >