Main MRPT website > C++ reference for MRPT 1.9.9
List of all members | Private Attributes
mrpt::utils::map_as_vector< KEY, VALUE, VECTOR_T > Class Template Reference

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 59 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 >:
Inheritance graph

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_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

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< iteratorreverse_iterator
 
typedef std::reverse_iterator< const_iteratorconst_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 69 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 71 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 68 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 64 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 70 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 67 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 65 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 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_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 96 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 98 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 73 of file map_as_vector.h.

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

Here is the caller graph for this function:

◆ 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 75 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 114 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 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 104 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 100 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 74 of file map_as_vector.h.

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

Here is the caller graph for this function:

◆ 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 76 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 142 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 152 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 112 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 128 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 134 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 110 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 119 of file map_as_vector.h.

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

Here is the caller graph for this function:

◆ 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 77 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 78 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 82 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 83 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 99 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 116 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



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: ae4571287 Thu Nov 23 00:06:53 2017 +0100 at dom oct 27 23:51:55 CET 2019