MRPT  1.9.9
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-2018, 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::containers
17 {
18 /** A STL-like container which looks and behaves (almost exactly) like a
19  * std::map<> but is implemented as a linear std::vector<> indexed by KEY.
20  * Note that KEY must be integer types only (size_t, uint32_t, etc.)
21  * This implementation is much more efficient than std::map<> when the most
22  * common operation is accesing elements
23  * by KEY with find() or [], and the range of KEY values starts at 0 (or a
24  * reasonable low number).
25  *
26  * This container is internally implemented as a linear array (std::vector) of
27  * the same fundamental type than the equivalent std::map<K,V>,
28  * that is, elements are <code> std::pair<K,V> </code> (note that K is NOT
29  * const as in std::map).
30  * I know, I know... this implementation wastes a lot of useless key elements
31  * in the pair.first when indices
32  * are already implicit in the std::vector<> order... but I promise I'll pay a
33  * beer to whoever show me an
34  * *efficient* alternative. If failed, update this comment: COUNTER OF WASTED
35  * HOURS WITH THIS: 3h
36  *
37  * Note that there is one <b>fundamental difference</b> wrt std::map<>: if you
38  * start with an empty map_as_vector<> and
39  * insert one element at the i'th position (with either [] or insert), the
40  * elements [0,i-1] will also exist then, but both
41  * their first & second entries (for the corresponding std::pair) will be
42  * <b>undefined</b>. This was intentional in order to
43  * gain efficiency (in particular, each std::pair<> doesn't have a
44  * constructor when resizing the underlying std::vector).
45  *
46  * The default underlying non-associative container is a "memory-aligned
47  * std::vector<>", but it can be changed to a
48  * standard vector<> or to a deque<> (to avoid memory reallocations) by
49  * changing the template parameter \a VECTOR_T.
50  *
51  * \note Defined in #include <mrpt/containers/map_as_vector.h>
52  * \ingroup mrpt_containers_grp
53  */
54 template <typename KEY, typename VALUE,
55  typename VECTOR_T =
58 {
59  public:
60  /** @name Iterators stuff and other types
61  @{ */
62  using key_type = KEY;
63  using value_type = std::pair<KEY, VALUE>;
64  using vec_t = VECTOR_T;
65  using size_type = typename vec_t::size_type;
66  using iterator = typename vec_t::iterator;
68  using reverse_iterator = std::reverse_iterator<iterator>;
69  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
70 
71  inline iterator begin() { return m_vec.begin(); }
72  inline iterator end() { return m_vec.end(); }
73  inline const_iterator begin() const { return m_vec.begin(); }
74  inline const_iterator end() const { return m_vec.end(); }
75  inline reverse_iterator rbegin() { return reverse_iterator(end()); }
77  {
78  return const_reverse_iterator(end());
79  }
80  inline reverse_iterator rend() { return reverse_iterator(begin()); }
82  {
83  return const_reverse_iterator(begin());
84  }
85  /** @} */
86  private:
87  /** The actual container */
89 
90  public:
91  /** @name Constructors, read/write access and other operations
92  @{ */
93  //!< Default constructor - does nothing */
94  inline map_as_vector() {}
95  /** Copy constructor */
97  inline size_t size() const { return m_vec.size(); }
98  inline bool empty() const { return m_vec.empty(); }
99  /** Count how many entries have a given key value - unlike std::map<K,V>,
100  * recall that this class will say an element i<N-1 exists just due to an
101  * insertion of element at N */
102  inline size_type count(const key_type i) const
103  {
104  return (i < m_vec.size()) ? 1 : 0;
105  }
106 
107  /** Maximum size due to system limits */
108  inline size_type max_size() const { return m_vec.max_size(); }
109  /** Return a read-only reference to the internal vector */
110  inline const vec_t& getVector() const { return m_vec; }
111  /** Clear the contents of this container */
112  inline void clear() { m_vec.clear(); }
113  /** Efficient swap with another object */
114  inline void swap(map_as_vector<KEY, VALUE>& o) { m_vec.swap(o.m_vec); }
115  /** Write/read via [i] operator, that creates all elements up to (and
116  * including) the i'th if they didn't exist already. */
117  inline VALUE& operator[](const size_t i)
118  {
119  if (m_vec.size() <= i) m_vec.resize(i + 1);
120  m_vec[i].first = i;
121  return m_vec[i].second;
122  }
123 
124  /** Insert pair<key,val>, as in std::map (guess_point is actually ignored in
125  * this class) */
126  inline void insert(
127  const iterator& guess_point, const value_type& keyvalpair)
128  {
129  this->operator[](keyvalpair.first) = keyvalpair;
130  }
131  /** Insert pair<key,val>, as in std::map */
132  inline void insert(const value_type& keyvalpair)
133  {
134  this->operator[](keyvalpair.first) = keyvalpair;
135  }
136 
137  /** Constant-time find, returning an iterator to the <key,val> pair or to
138  * end() if not found (that is, if it's above the maximum index in the
139  * vector) */
140  inline iterator find(const size_t i)
141  {
142  if (i < m_vec.size())
143  return m_vec.begin() + i;
144  else
145  return m_vec.end();
146  }
147  /** Constant-time find, returning an iterator to the <key,val> pair or to
148  * end() if not found (that is, if it's above the maximum index in the
149  * vector) */
150  inline const_iterator find(const size_t i) const
151  {
152  if (i < m_vec.size())
153  return m_vec.begin() + i;
154  else
155  return m_vec.end();
156  }
157 
158  /** @} */
159 
160 }; // end class map_as_vector
161 
162 }
163 #endif
164 
165 
const vec_t & getVector() const
Return a read-only reference to the internal vector.
Scalar * iterator
Definition: eigen_plugins.h:26
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) ...
VALUE & operator[](const size_t i)
Write/read via [i] operator, that creates all elements up to (and including) the i&#39;th if they didn&#39;t ...
typename vec_t::const_iterator const_iterator
Definition: map_as_vector.h:67
std::vector< T, mrpt::aligned_allocator_cpp11< T > > aligned_std_vector
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...
map_as_vector(const map_as_vector< KEY, VALUE > &o)
Copy constructor.
Definition: map_as_vector.h:96
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_reverse_iterator rbegin() const
Definition: map_as_vector.h:76
const_reverse_iterator rend() const
Definition: map_as_vector.h:81
void insert(const value_type &keyvalpair)
Insert pair<key,val>, as in std::map.
A STL-like container which looks and behaves (almost exactly) like a std::map<> but is implemented as...
Definition: map_as_vector.h:57
std::reverse_iterator< iterator > reverse_iterator
Definition: map_as_vector.h:68
typename mrpt::aligned_std_vector< std::pair< KEY, VALUE >> vec_t
Definition: map_as_vector.h:64
size_type max_size() const
Maximum size due to system limits.
void clear()
Clear the contents of this container.
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...
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: map_as_vector.h:69
const_iterator end() const
Definition: map_as_vector.h:74
const_iterator begin() const
Definition: map_as_vector.h:73
void swap(map_as_vector< KEY, VALUE > &o)
Efficient swap with another object.
const Scalar * const_iterator
Definition: eigen_plugins.h:27
map_as_vector()
< Default constructor - does nothing */
Definition: map_as_vector.h:94
vec_t m_vec
The actual container.
Definition: map_as_vector.h:88



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: 7d5e6d718 Fri Aug 24 01:51:28 2018 +0200 at lun nov 2 08:35:50 CET 2020