Detailed Description

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_std_vector<std::pair<KEY, VALUE>>>
class mrpt::containers::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/containers/map_as_vector.h>

Definition at line 59 of file map_as_vector.h.

#include <mrpt/containers/map_as_vector.h>

Inheritance diagram for mrpt::containers::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
using	key_type = KEY

using	value_type = std::pair< KEY, VALUE >

using	vec_t = VECTOR_T

using	size_type = typename vec_t::size_type

using	iterator = typename vec_t::iterator

using	const_iterator = typename vec_t::const_iterator

using	reverse_iterator = std::reverse_iterator< iterator >

using	const_reverse_iterator = std::reverse_iterator< const_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_std_vector<std::pair<KEY, VALUE>>>

using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::const_iterator = typename vec_t::const_iterator

Definition at line 69 of file map_as_vector.h.

◆ const_reverse_iterator

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

using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::const_reverse_iterator = std::reverse_iterator<const_iterator>

Definition at line 71 of file map_as_vector.h.

◆ iterator

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

using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::iterator = typename vec_t::iterator

Definition at line 68 of file map_as_vector.h.

◆ key_type

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

using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::key_type = KEY

Definition at line 64 of file map_as_vector.h.

◆ reverse_iterator

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

using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::reverse_iterator = std::reverse_iterator<iterator>

Definition at line 70 of file map_as_vector.h.

◆ size_type

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

using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::size_type = typename vec_t::size_type

Definition at line 67 of file map_as_vector.h.

◆ value_type

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

using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::value_type = std::pair<KEY, VALUE>

Definition at line 65 of file map_as_vector.h.

◆ vec_t

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

using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::vec_t = VECTOR_T

Definition at line 66 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_std_vector<std::pair<KEY, VALUE>>>

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

inline

< Default constructor - does nothing *‍/

Definition at line 96 of file map_as_vector.h.

◆ map_as_vector() [2/2]

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

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

inline

Copy constructor.

Definition at line 98 of file map_as_vector.h.

Member Function Documentation

◆ begin() [1/2]

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

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

inline

Definition at line 73 of file map_as_vector.h.

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

◆ begin() [2/2]

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

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

inline

Definition at line 75 of file map_as_vector.h.

◆ clear()

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

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

inline

Clear the contents of this container.

Definition at line 114 of file map_as_vector.h.

◆ count()

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

size_type mrpt::containers::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 104 of file map_as_vector.h.

◆ empty()

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

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

inline

Definition at line 100 of file map_as_vector.h.

◆ end() [1/2]

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

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

inline

Definition at line 74 of file map_as_vector.h.

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

◆ end() [2/2]

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

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

inline

Definition at line 76 of file map_as_vector.h.

◆ find() [1/2]

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

iterator mrpt::containers::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 142 of file map_as_vector.h.

◆ find() [2/2]

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

const_iterator mrpt::containers::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 152 of file map_as_vector.h.

◆ getVector()

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

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

inline

Return a read-only reference to the internal vector.

Definition at line 112 of file map_as_vector.h.

◆ insert() [1/2]

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

void mrpt::containers::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 128 of file map_as_vector.h.

◆ insert() [2/2]

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

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

inline

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

Definition at line 134 of file map_as_vector.h.

◆ max_size()

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

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

inline

Maximum size due to system limits.

Definition at line 110 of file map_as_vector.h.

◆ operator[]()

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

VALUE& mrpt::containers::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 119 of file map_as_vector.h.

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

◆ rbegin() [1/2]

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

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

inline

Definition at line 77 of file map_as_vector.h.

◆ rbegin() [2/2]

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

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

inline

Definition at line 78 of file map_as_vector.h.

◆ rend() [1/2]

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

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

inline

Definition at line 82 of file map_as_vector.h.

◆ rend() [2/2]

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

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

inline

Definition at line 83 of file map_as_vector.h.

◆ size()

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

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

inline

Definition at line 99 of file map_as_vector.h.

◆ swap()

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

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

inline

Efficient swap with another object.

Definition at line 116 of file map_as_vector.h.

Member Data Documentation

◆ m_vec

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

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

private

The actual container.

Definition at line 90 of file map_as_vector.h.

Detailed Description

template<typename KEY, typename VALUE, typename VECTOR_T = typename mrpt::aligned_std_vector<std::pair<KEY, VALUE>>> class mrpt::containers::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_std_vector<std::pair<KEY, VALUE>>>
class mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >