Main MRPT website > C++ reference for MRPT 1.4.0
map_as_vector.h
Go to the documentation of this file.
1/* +---------------------------------------------------------------------------+
2 | Mobile Robot Programming Toolkit (MRPT) |
3 | http://www.mrpt.org/ |
4 | |
5 | Copyright (c) 2005-2016, Individual contributors, see AUTHORS file |
6 | See: http://www.mrpt.org/Authors - All rights reserved. |
7 | Released under BSD License. See details in http://www.mrpt.org/License |
8 +---------------------------------------------------------------------------+ */
9#ifndef mrpt_map_as_vector_H
10#define mrpt_map_as_vector_H
11
13#include <map>
14#include <vector>
15
16namespace mrpt
17{
18 namespace utils
19 {
20 /** 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.
21 * Note that KEY must be integer types only (size_t, uint32_t, etc.)
22 * This implementation is much more efficient than std::map<> when the most common operation is accesing elements
23 * by KEY with find() or [], and the range of KEY values starts at 0 (or a reasonable low number).
24 *
25 * This container is internally implemented as a linear array (std::vector) of the same fundamental type than the equivalent std::map<K,V>,
26 * that is, elements are <code> std::pair<K,V> </code> (note that K is NOT const as in std::map).
27 * I know, I know... this implementation wastes a lot of useless key elements in the pair.first when indices
28 * are already implicit in the std::vector<> order... but I promise I'll pay a beer to whoever show me an
29 * *efficient* alternative. If failed, update this comment: COUNTER OF WASTED HOURS WITH THIS: 3h
30 *
31 * Note that there is one <b>fundamental difference</b> wrt std::map<>: if you start with an empty map_as_vector<> and
32 * insert one element at the i'th position (with either [] or insert), the elements [0,i-1] will also exist then, but both
33 * their first & second entries (for the corresponding std::pair) will be <b>undefined</b>. This was intentional in order to
34 * gain efficiency (in particular, each std::pair<> doesn't have a constructor when resizing the underlying std::vector).
35 *
36 * The default underlying non-associative container is a "memory-aligned std::vector<>", but it can be changed to a
37 * standard vector<> or to a deque<> (to avoid memory reallocations) by changing the template parameter \a VECTOR_T.
38 *
39 * \note Defined in #include <mrpt/utils/map_as_vector.h>
40 * \ingroup stlext_grp
41 */
42 template <
43 typename KEY,
44 typename VALUE,
45 typename VECTOR_T = typename mrpt::aligned_containers<std::pair<KEY,VALUE> >::vector_t
46 >
48 {
49 public:
50 /** @name Iterators stuff and other types
51 @{ */
52 typedef KEY key_type;
53 typedef std::pair<KEY,VALUE> value_type;
54 typedef VECTOR_T vec_t;
55 typedef typename vec_t::size_type size_type;
56 typedef typename vec_t::iterator iterator;
57 typedef typename vec_t::const_iterator const_iterator;
58 typedef std::reverse_iterator<iterator> reverse_iterator;
59 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
60
61 inline iterator begin() { return m_vec.begin(); }
62 inline iterator end() { return m_vec.end(); }
63 inline const_iterator begin() const { return m_vec.begin(); }
64 inline const_iterator end() const { return m_vec.end(); }
69 /** @} */
70 private:
71 vec_t m_vec; //!< The actual container
72
73 public:
74 /** @name Constructors, read/write access and other operations
75 @{ */
76 //!< Default constructor - does nothing */
77 inline map_as_vector() { }
78 /** Copy constructor */
80
81 inline size_t size() const { return m_vec.size(); }
82 inline bool empty() const { return m_vec.empty(); }
83
84 /** 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 */
85 inline size_type count ( const key_type i ) const { return (i<m_vec.size()) ? 1 : 0; }
86
87 /** Maximum size due to system limits */
88 inline size_type max_size() const { return m_vec.max_size(); }
89
90 /** Return a read-only reference to the internal vector */
91 inline const vec_t &getVector() const { return m_vec; }
92
93 /** Clear the contents of this container */
94 inline void clear() { m_vec.clear(); }
95
96 /** Efficient swap with another object */
97 inline void swap(map_as_vector<KEY,VALUE>& o) { m_vec.swap(o.m_vec); }
98
99 /** Write/read via [i] operator, that creates all elements up to (and including) the i'th if they didn't exist already. */
100 inline VALUE & operator[](const size_t i) {
101 if (m_vec.size()<=i) m_vec.resize(i+1);
102 m_vec[i].first=i;
103 return m_vec[i].second;
104 }
105
106 /** Insert pair<key,val>, as in std::map (guess_point is actually ignored in this class) */
107 inline void insert(const iterator &guess_point, const value_type &keyvalpair ) { this->operator[](keyvalpair.first)=keyvalpair; }
108 /** Insert pair<key,val>, as in std::map */
109 inline void insert(const value_type &keyvalpair ) { this->operator[](keyvalpair.first)=keyvalpair; }
110
111 /** 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) */
112 inline iterator find(const size_t i) { if (i<m_vec.size()) return m_vec.begin()+i; else return m_vec.end(); }
113 /** 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) */
114 inline const_iterator find(const size_t i) const { if (i<m_vec.size()) return m_vec.begin()+i; else return m_vec.end(); }
115
116 /** @} */
117
118
119 }; // end class map_as_vector
120
121 } // End of namespace
122} // End of namespace
123#endif
A STL-like container which looks and behaves (almost exactly) like a std::map<> but is implemented as...
Definition: map_as_vector.h:48
vec_t m_vec
The actual container.
Definition: map_as_vector.h:71
vec_t::size_type size_type
Definition: map_as_vector.h:55
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: map_as_vector.h:59
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,...
const_reverse_iterator rend() const
Definition: map_as_vector.h:68
vec_t::const_iterator const_iterator
Definition: map_as_vector.h:57
void swap(map_as_vector< KEY, VALUE > &o)
Efficient swap with another object.
Definition: map_as_vector.h:97
const_iterator begin() const
Definition: map_as_vector.h:63
map_as_vector()
< Default constructor - does nothing *‍/
Definition: map_as_vector.h:77
reverse_iterator rbegin()
Definition: map_as_vector.h:65
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)
vec_t::iterator iterator
Definition: map_as_vector.h:56
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 ...
std::pair< KEY, VALUE > value_type
Definition: map_as_vector.h:53
const vec_t & getVector() const
Return a read-only reference to the internal vector.
Definition: map_as_vector.h:91
void clear()
Clear the contents of this container.
Definition: map_as_vector.h:94
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...
Definition: map_as_vector.h:85
size_type max_size() const
Maximum size due to system limits.
Definition: map_as_vector.h:88
const_reverse_iterator rbegin() const
Definition: map_as_vector.h:66
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,...
const_iterator end() const
Definition: map_as_vector.h:64
void insert(const value_type &keyvalpair)
Insert pair<key,val>, as in std::map.
map_as_vector(const map_as_vector< KEY, VALUE > &o)
Copy constructor.
Definition: map_as_vector.h:79
reverse_iterator rend()
Definition: map_as_vector.h:67
std::reverse_iterator< iterator > reverse_iterator
Definition: map_as_vector.h:58
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
Helper types for STL containers with Eigen memory allocators.



Page generated by Doxygen 1.9.6 for MRPT 1.4.0 SVN: at Fri Jan 20 00:13:14 UTC 2023