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).
#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 |
Definition at line 69 of file map_as_vector.h.
| typedef std::reverse_iterator<const_iterator> mrpt::utils::map_as_vector::const_reverse_iterator |
Definition at line 71 of file map_as_vector.h.
Definition at line 68 of file map_as_vector.h.
| typedef KEY mrpt::utils::map_as_vector::key_type |
Definition at line 64 of file map_as_vector.h.
| typedef std::reverse_iterator<iterator> mrpt::utils::map_as_vector::reverse_iterator |
Definition at line 70 of file map_as_vector.h.
| typedef vec_t::size_type mrpt::utils::map_as_vector::size_type |
Definition at line 67 of file map_as_vector.h.
| typedef std::pair<KEY,VALUE> mrpt::utils::map_as_vector::value_type |
Definition at line 65 of file map_as_vector.h.
| typedef mrpt::aligned_containers<value_type>::vector_t mrpt::utils::map_as_vector::vec_t |
Definition at line 66 of file map_as_vector.h.
| mrpt::utils::map_as_vector::map_as_vector | ( | ) | [inline] |
< Default constructor - does nothing */
Definition at line 89 of file map_as_vector.h.
| mrpt::utils::map_as_vector::map_as_vector | ( | const map_as_vector< KEY, VALUE > & | o | ) | [inline] |
Copy constructor.
Definition at line 91 of file map_as_vector.h.
| iterator mrpt::utils::map_as_vector::begin | ( | ) | [inline] |
Definition at line 73 of file map_as_vector.h.
Referenced by mrpt::utils::map_as_vector< KEY, VALUE >::rend().
| const_iterator mrpt::utils::map_as_vector::begin | ( | ) | const [inline] |
Definition at line 75 of file map_as_vector.h.
| void mrpt::utils::map_as_vector::clear | ( | void | ) | [inline] |
Clear the contents of this container.
Definition at line 106 of file map_as_vector.h.
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 97 of file map_as_vector.h.
| bool mrpt::utils::map_as_vector::empty | ( | ) | const [inline] |
Definition at line 94 of file map_as_vector.h.
| iterator mrpt::utils::map_as_vector::end | ( | ) | [inline] |
Definition at line 74 of file map_as_vector.h.
Referenced by mrpt::utils::map_as_vector< KEY, VALUE >::rbegin().
| const_iterator mrpt::utils::map_as_vector::end | ( | ) | const [inline] |
Definition at line 76 of file map_as_vector.h.
| iterator mrpt::utils::map_as_vector::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 124 of file map_as_vector.h.
| const_iterator mrpt::utils::map_as_vector::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 126 of file map_as_vector.h.
| const vec_t& mrpt::utils::map_as_vector::getVector | ( | ) | const [inline] |
Return a read-only reference to the internal vector.
Definition at line 103 of file map_as_vector.h.
| void mrpt::utils::map_as_vector::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 119 of file map_as_vector.h.
| void mrpt::utils::map_as_vector::insert | ( | const value_type & | keyvalpair | ) | [inline] |
Insert pair<key,val>, as in std::map.
Definition at line 121 of file map_as_vector.h.
| size_type mrpt::utils::map_as_vector::max_size | ( | ) | const [inline] |
Maximum size due to system limits.
Definition at line 100 of file map_as_vector.h.
| VALUE& mrpt::utils::map_as_vector::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 112 of file map_as_vector.h.
Referenced by mrpt::utils::map_as_vector< KEY, VALUE >::insert().
| reverse_iterator mrpt::utils::map_as_vector::rbegin | ( | ) | [inline] |
Definition at line 77 of file map_as_vector.h.
| const_reverse_iterator mrpt::utils::map_as_vector::rbegin | ( | ) | const [inline] |
Definition at line 78 of file map_as_vector.h.
| reverse_iterator mrpt::utils::map_as_vector::rend | ( | ) | [inline] |
Definition at line 79 of file map_as_vector.h.
| const_reverse_iterator mrpt::utils::map_as_vector::rend | ( | ) | const [inline] |
Definition at line 80 of file map_as_vector.h.
| size_t mrpt::utils::map_as_vector::size | ( | ) | const [inline] |
Definition at line 93 of file map_as_vector.h.
| void mrpt::utils::map_as_vector::swap | ( | map_as_vector< KEY, VALUE > & | o | ) | [inline] |
Efficient swap with another object.
Definition at line 109 of file map_as_vector.h.
vec_t mrpt::utils::map_as_vector::m_vec [private] |
The actual container.
Definition at line 83 of file map_as_vector.h.
Referenced by mrpt::utils::map_as_vector< KEY, VALUE >::begin(), mrpt::utils::map_as_vector< KEY, VALUE >::end(), mrpt::utils::map_as_vector< KEY, VALUE >::size(), mrpt::utils::map_as_vector< KEY, VALUE >::empty(), mrpt::utils::map_as_vector< KEY, VALUE >::count(), mrpt::utils::map_as_vector< KEY, VALUE >::max_size(), mrpt::utils::map_as_vector< KEY, VALUE >::getVector(), mrpt::utils::map_as_vector< KEY, VALUE >::clear(), mrpt::utils::map_as_vector< KEY, VALUE >::swap(), mrpt::utils::map_as_vector< KEY, VALUE >::operator[](), and mrpt::utils::map_as_vector< KEY, VALUE >::find().
| Page generated by Doxygen 1.7.5 for MRPT 0.9.5 SVN: at Thu Oct 13 21:25:36 UTC 2011 |