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



Page generated by Doxygen 1.8.14 for MRPT 2.0.4 Git: 33de1d0ad Sat Jun 20 11:02:42 2020 +0200 at sáb jun 20 17:35:17 CEST 2020