MRPT  1.9.9
List of all members | Private Attributes
mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T > Class Template Reference

Detailed Description

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 55 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
 < 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_tgetVector () 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 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 65 of file map_as_vector.h.

◆ const_reverse_iterator

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 67 of file map_as_vector.h.

◆ iterator

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::iterator = typename vec_t::iterator

Definition at line 64 of file map_as_vector.h.

◆ key_type

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::key_type = KEY

Definition at line 60 of file map_as_vector.h.

◆ reverse_iterator

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 66 of file map_as_vector.h.

◆ size_type

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 63 of file map_as_vector.h.

◆ value_type

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 61 of file map_as_vector.h.

◆ vec_t

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
using mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::vec_t = VECTOR_T

Definition at line 62 of file map_as_vector.h.

Constructor & Destructor Documentation

◆ map_as_vector() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::map_as_vector ( )
inlinedefault

< Default constructor - does nothing */

◆ map_as_vector() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 94 of file map_as_vector.h.

Member Function Documentation

◆ begin() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
iterator mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::begin ( )
inline

Definition at line 69 of file map_as_vector.h.

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

Here is the caller graph for this function:

◆ begin() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
const_iterator mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::begin ( ) const
inline

Definition at line 71 of file map_as_vector.h.

◆ clear()

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 110 of file map_as_vector.h.

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

Here is the caller graph for this function:

◆ count()

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 100 of file map_as_vector.h.

◆ empty()

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
bool mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::empty ( ) const
inline

Definition at line 96 of file map_as_vector.h.

◆ end() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
iterator mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::end ( )
inline

Definition at line 70 of file map_as_vector.h.

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

Here is the caller graph for this function:

◆ end() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
const_iterator mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::end ( ) const
inline

Definition at line 72 of file map_as_vector.h.

◆ find() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 138 of file map_as_vector.h.

◆ find() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 148 of file map_as_vector.h.

◆ getVector()

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 108 of file map_as_vector.h.

◆ insert() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 124 of file map_as_vector.h.

◆ insert() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 130 of file map_as_vector.h.

◆ max_size()

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 106 of file map_as_vector.h.

◆ operator[]()

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 115 of file map_as_vector.h.

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

Here is the caller graph for this function:

◆ rbegin() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
reverse_iterator mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::rbegin ( )
inline

Definition at line 73 of file map_as_vector.h.

◆ rbegin() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
const_reverse_iterator mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::rbegin ( ) const
inline

Definition at line 74 of file map_as_vector.h.

◆ rend() [1/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
reverse_iterator mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::rend ( )
inline

Definition at line 78 of file map_as_vector.h.

◆ rend() [2/2]

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
const_reverse_iterator mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::rend ( ) const
inline

Definition at line 79 of file map_as_vector.h.

◆ size()

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
size_t mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::size ( ) const
inline

Definition at line 95 of file map_as_vector.h.

◆ swap()

template<typename KEY, typename VALUE, typename VECTOR_T = typename 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 112 of file map_as_vector.h.

Member Data Documentation

◆ m_vec

template<typename KEY, typename VALUE, typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>>
vec_t mrpt::containers::map_as_vector< KEY, VALUE, VECTOR_T >::m_vec
private



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: 45d659fbb Tue Dec 10 18:21:14 2019 +0100 at mar dic 10 18:30:09 CET 2019