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>
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_t & | getVector () 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 |
typedef vec_t::const_iterator mrpt::utils::map_as_vector< KEY, VALUE >::const_iterator |
Definition at line 68 of file map_as_vector.h.
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.
typedef vec_t::iterator mrpt::utils::map_as_vector< KEY, VALUE >::iterator |
Definition at line 67 of file map_as_vector.h.
typedef KEY mrpt::utils::map_as_vector< KEY, VALUE >::key_type |
Definition at line 63 of file map_as_vector.h.
typedef std::reverse_iterator<iterator> mrpt::utils::map_as_vector< KEY, VALUE >::reverse_iterator |
Definition at line 69 of file map_as_vector.h.
typedef vec_t::size_type mrpt::utils::map_as_vector< KEY, VALUE >::size_type |
Definition at line 66 of file map_as_vector.h.
typedef std::pair<KEY,VALUE> mrpt::utils::map_as_vector< KEY, VALUE >::value_type |
Definition at line 64 of file map_as_vector.h.
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.
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.
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.
iterator mrpt::utils::map_as_vector< KEY, VALUE >::begin | ( | ) | [inline] |
Definition at line 72 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 >::rend().
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.
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.
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.
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.
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.
iterator mrpt::utils::map_as_vector< KEY, VALUE >::end | ( | ) | [inline] |
Definition at line 73 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 >::rbegin().
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.
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.
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.
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[]().
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[]().
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.
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().
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().
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().
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().
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().
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.
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.
vec_t mrpt::utils::map_as_vector< KEY, VALUE >::m_vec [private] |
The actual container.
Definition at line 82 of file map_as_vector.h.
Referenced by mrpt::utils::map_as_vector< KEY, VALUE >::begin(), mrpt::utils::map_as_vector< KEY, VALUE >::clear(), mrpt::utils::map_as_vector< KEY, VALUE >::count(), mrpt::utils::map_as_vector< KEY, VALUE >::empty(), mrpt::utils::map_as_vector< KEY, VALUE >::end(), mrpt::utils::map_as_vector< KEY, VALUE >::find(), mrpt::utils::map_as_vector< KEY, VALUE >::getVector(), mrpt::utils::map_as_vector< KEY, VALUE >::max_size(), mrpt::utils::map_as_vector< KEY, VALUE >::operator[](), mrpt::utils::map_as_vector< KEY, VALUE >::size(), and mrpt::utils::map_as_vector< KEY, VALUE >::swap().
Page generated by Doxygen 1.7.2 for MRPT 0.9.4 SVN: at Mon Jan 10 22:30:30 UTC 2011 |