Main MRPT website > C++ reference for MRPT 1.5.6
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-2017, 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:47
vec_t::const_iterator const_iterator
Definition: map_as_vector.h:57
size_type max_size() const
Maximum size due to system limits.
Definition: map_as_vector.h:88
map_as_vector(const map_as_vector< KEY, VALUE > &o)
Copy constructor.
Definition: map_as_vector.h:79
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) ...
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...
Scalar * iterator
Definition: eigen_plugins.h:23
map_as_vector()
< Default constructor - does nothing */
Definition: map_as_vector.h:77
const_iterator begin() const
Definition: map_as_vector.h:63
const Scalar * const_iterator
Definition: eigen_plugins.h:24
void clear()
Clear the contents of this container.
Definition: map_as_vector.h:94
const vec_t & getVector() const
Return a read-only reference to the internal vector.
Definition: map_as_vector.h:91
Helper types for STL containers with Eigen memory allocators.
reverse_iterator rend()
Definition: map_as_vector.h:67
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...
std::pair< KEY, VALUE > value_type
Definition: map_as_vector.h:53
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::reverse_iterator< iterator > reverse_iterator
Definition: map_as_vector.h:58
vec_t::size_type size_type
Definition: map_as_vector.h:55
reverse_iterator rbegin()
Definition: map_as_vector.h:65
void insert(const value_type &keyvalpair)
Insert pair<key,val>, as in std::map.
const_reverse_iterator rbegin() const
Definition: map_as_vector.h:66
vec_t m_vec
The actual container.
Definition: map_as_vector.h:71
const_reverse_iterator rend() const
Definition: map_as_vector.h:68
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: map_as_vector.h:59
const_iterator end() const
Definition: map_as_vector.h:64
vec_t::iterator iterator
Definition: map_as_vector.h:56
void swap(map_as_vector< KEY, VALUE > &o)
Efficient swap with another object.
Definition: map_as_vector.h:97
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



Page generated by Doxygen 1.8.6 for MRPT 1.5.6 Git: 4c65e84 Tue Apr 24 08:18:17 2018 +0200 at mar abr 24 08:26:17 CEST 2018