Main MRPT website > C++ reference
MRPT logo
Private Attributes

mrpt::utils::map_as_vector< KEY, VALUE > Class Template Reference


Detailed Description

template<typename KEY, typename VALUE>
class mrpt::utils::map_as_vector< KEY, VALUE >

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).

Definition at line 58 of file map_as_vector.h.

#include <mrpt/utils/map_as_vector.h>

Inheritance diagram for mrpt::utils::map_as_vector< KEY, VALUE >:
Inheritance graph
[legend]

List of all members.

Public Member Functions

Constructors, read/write access and other operations
 map_as_vector ()
 < Default constructor - does nothing */
 map_as_vector (const map_as_vector< KEY, VALUE > &o)
 Copy constructor.
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.
size_type max_size () const
 Maximum size due to system limits.
const vec_tgetVector () const
 Return a read-only reference to the internal vector.
void clear ()
 Clear the contents of this container.
void swap (map_as_vector< KEY, VALUE > &o)
 Efficient swap with another object.
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.
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)
void insert (const value_type &keyvalpair)
 Insert pair<key,val>, as in std::map.
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)
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)

Private Attributes

vec_t m_vec
 The actual container.

Iterators stuff and other types

typedef KEY key_type
typedef std::pair< KEY, VALUE > value_type
typedef
mrpt::aligned_containers
< value_type >::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

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

Definition at line 68 of file map_as_vector.h.

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

Definition at line 70 of file map_as_vector.h.

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

Definition at line 67 of file map_as_vector.h.

template<typename KEY, typename VALUE>
typedef KEY mrpt::utils::map_as_vector< KEY, VALUE >::key_type

Definition at line 63 of file map_as_vector.h.

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

Definition at line 69 of file map_as_vector.h.

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

Definition at line 66 of file map_as_vector.h.

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

Definition at line 64 of file map_as_vector.h.

template<typename KEY, typename VALUE>
typedef mrpt::aligned_containers<value_type>::vector_t mrpt::utils::map_as_vector< KEY, VALUE >::vec_t

Definition at line 65 of file map_as_vector.h.


Constructor & Destructor Documentation

template<typename KEY, typename VALUE>
mrpt::utils::map_as_vector< KEY, VALUE >::map_as_vector ( ) [inline]

< Default constructor - does nothing */

Definition at line 88 of file map_as_vector.h.

template<typename KEY, typename VALUE>
mrpt::utils::map_as_vector< KEY, VALUE >::map_as_vector ( const map_as_vector< KEY, VALUE > &  o) [inline]

Copy constructor.

Definition at line 90 of file map_as_vector.h.


Member Function Documentation

template<typename KEY, typename VALUE>
iterator mrpt::utils::map_as_vector< KEY, VALUE >::begin ( ) [inline]
template<typename KEY, typename VALUE>
const_iterator mrpt::utils::map_as_vector< KEY, VALUE >::begin ( ) const [inline]

Definition at line 74 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

template<typename KEY, typename VALUE>
void mrpt::utils::map_as_vector< KEY, VALUE >::clear ( void  ) [inline]

Clear the contents of this container.

Definition at line 105 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

template<typename KEY, typename VALUE>
size_type mrpt::utils::map_as_vector< KEY, VALUE >::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 96 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

template<typename KEY, typename VALUE>
bool mrpt::utils::map_as_vector< KEY, VALUE >::empty ( ) const [inline]

Definition at line 93 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

template<typename KEY, typename VALUE>
const_iterator mrpt::utils::map_as_vector< KEY, VALUE >::end ( ) const [inline]

Definition at line 75 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

template<typename KEY, typename VALUE>
iterator mrpt::utils::map_as_vector< KEY, VALUE >::end ( ) [inline]
template<typename KEY, typename VALUE>
iterator mrpt::utils::map_as_vector< KEY, VALUE >::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 123 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

template<typename KEY, typename VALUE>
const_iterator mrpt::utils::map_as_vector< KEY, VALUE >::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 125 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

template<typename KEY, typename VALUE>
const vec_t& mrpt::utils::map_as_vector< KEY, VALUE >::getVector ( ) const [inline]

Return a read-only reference to the internal vector.

Definition at line 102 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

template<typename KEY, typename VALUE>
void mrpt::utils::map_as_vector< KEY, VALUE >::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 118 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::operator[]().

template<typename KEY, typename VALUE>
void mrpt::utils::map_as_vector< KEY, VALUE >::insert ( const value_type keyvalpair) [inline]

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

Definition at line 120 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::operator[]().

template<typename KEY, typename VALUE>
size_type mrpt::utils::map_as_vector< KEY, VALUE >::max_size ( ) const [inline]

Maximum size due to system limits.

Definition at line 99 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

template<typename KEY, typename VALUE>
VALUE& mrpt::utils::map_as_vector< KEY, VALUE >::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 111 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

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

template<typename KEY, typename VALUE>
reverse_iterator mrpt::utils::map_as_vector< KEY, VALUE >::rbegin ( ) [inline]

Definition at line 76 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::end().

template<typename KEY, typename VALUE>
const_reverse_iterator mrpt::utils::map_as_vector< KEY, VALUE >::rbegin ( ) const [inline]

Definition at line 77 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::end().

template<typename KEY, typename VALUE>
reverse_iterator mrpt::utils::map_as_vector< KEY, VALUE >::rend ( ) [inline]

Definition at line 78 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::begin().

template<typename KEY, typename VALUE>
const_reverse_iterator mrpt::utils::map_as_vector< KEY, VALUE >::rend ( ) const [inline]

Definition at line 79 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::begin().

template<typename KEY, typename VALUE>
size_t mrpt::utils::map_as_vector< KEY, VALUE >::size ( ) const [inline]

Definition at line 92 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.

template<typename KEY, typename VALUE>
void mrpt::utils::map_as_vector< KEY, VALUE >::swap ( map_as_vector< KEY, VALUE > &  o) [inline]

Efficient swap with another object.

Definition at line 108 of file map_as_vector.h.

References mrpt::utils::map_as_vector< KEY, VALUE >::m_vec.


Member Data Documentation

template<typename KEY, typename VALUE>
vec_t mrpt::utils::map_as_vector< KEY, VALUE >::m_vec [private]



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN:exported at Tue Jan 25 21:56:31 UTC 2011