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 
16 namespace 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;
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(); }
65  inline reverse_iterator rbegin() { return reverse_iterator(end()); }
67  inline reverse_iterator rend() { return reverse_iterator(begin()); }
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
const vec_t & getVector() const
Return a read-only reference to the internal vector.
Definition: map_as_vector.h:91
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
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 ...
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
std::pair< KEY, VALUE > value_type
Definition: map_as_vector.h:53
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
Scalar * iterator
Definition: eigen_plugins.h:23
const Scalar * const_iterator
Definition: eigen_plugins.h:24
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.1 for MRPT 1.4.0 SVN: at Mon Apr 18 03:37:47 UTC 2022