Main MRPT website > C++ reference
MRPT logo
map_as_vector.h
Go to the documentation of this file.
1 /* +---------------------------------------------------------------------------+
2  | The Mobile Robot Programming Toolkit (MRPT) C++ library |
3  | |
4  | http://www.mrpt.org/ |
5  | |
6  | Copyright (C) 2005-2012 University of Malaga |
7  | |
8  | This software was written by the Machine Perception and Intelligent |
9  | Robotics Lab, University of Malaga (Spain). |
10  | Contact: Jose-Luis Blanco <jlblanco@ctima.uma.es> |
11  | |
12  | This file is part of the MRPT project. |
13  | |
14  | MRPT is free software: you can redistribute it and/or modify |
15  | it under the terms of the GNU General Public License as published by |
16  | the Free Software Foundation, either version 3 of the License, or |
17  | (at your option) any later version. |
18  | |
19  | MRPT is distributed in the hope that it will be useful, |
20  | but WITHOUT ANY WARRANTY; without even the implied warranty of |
21  | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22  | GNU General Public License for more details. |
23  | |
24  | You should have received a copy of the GNU General Public License |
25  | along with MRPT. If not, see <http://www.gnu.org/licenses/>. |
26  | |
27  +---------------------------------------------------------------------------+ */
28 #ifndef mrpt_map_as_vector_H
29 #define mrpt_map_as_vector_H
30 
31 // Note: This file is included from "stl_extensions.h"
32 #include <mrpt/utils/utils_defs.h>
33 #include <map>
34 #include <vector>
35 
36 namespace mrpt
37 {
38  namespace utils
39  {
40  /** 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.
41  * Note that KEY must be integer types only (size_t, uint32_t, etc.)
42  * This implementation is much more efficient than std::map<> when the most common operation is accesing elements
43  * by KEY with find() or [], and the range of KEY values starts at 0 (or a reasonable low number).
44  *
45  * This container is internally implemented as a linear array (std::vector) of the same fundamental type than the equivalent std::map<K,V>,
46  * that is, elements are <code> std::pair<K,V> </code> (note that K is NOT const as in std::map).
47  * I know, I know... this implementation wastes a lot of useless key elements in the pair.first when indices
48  * are already implicit in the std::vector<> order... but I promise I'll pay a beer to whoever show me an
49  * *efficient* alternative. If failed, update this comment: COUNTER OF WASTED HOURS WITH THIS: 3h
50  *
51  * Note that there is one <b>fundamental difference</b> wrt std::map<>: if you start with an empty map_as_vector<> and
52  * insert one element at the i'th position (with either [] or insert), the elements [0,i-1] will also exist then, but both
53  * their first & second entries (for the corresponding std::pair) will be <b>undefined</b>. This was intentional in order to
54  * gain efficiency (in particular, each std::pair<> doesn't have a constructor when resizing the underlying std::vector).
55  *
56  * \ingroup stlext_grp
57  */
58  template <typename KEY,typename VALUE>
59  class map_as_vector
60  {
61  public:
62  /** @name Iterators stuff and other types
63  @{ */
64  typedef KEY key_type;
65  typedef std::pair<KEY,VALUE> value_type;
66  typedef typename mrpt::aligned_containers<value_type>::vector_t vec_t;
67  typedef typename vec_t::size_type size_type;
68  typedef typename vec_t::iterator iterator;
69  typedef typename vec_t::const_iterator const_iterator;
70  typedef std::reverse_iterator<iterator> reverse_iterator;
71  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
72 
73  inline iterator begin() { return m_vec.begin(); }
74  inline iterator end() { return m_vec.end(); }
75  inline const_iterator begin() const { return m_vec.begin(); }
76  inline const_iterator end() const { return m_vec.end(); }
77  inline reverse_iterator rbegin() { return reverse_iterator(end()); }
78  inline const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
79  inline reverse_iterator rend() { return reverse_iterator(begin()); }
80  inline const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
81  /** @} */
82  private:
83  vec_t m_vec; //!< The actual container
84 
85  public:
86  /** @name Constructors, read/write access and other operations
87  @{ */
88  //!< Default constructor - does nothing */
89  inline map_as_vector() { }
90  /** Copy constructor */
91  inline map_as_vector(const map_as_vector<KEY,VALUE> &o) : m_vec(o.m_vec) { }
92 
93  inline size_t size() const { return m_vec.size(); }
94  inline bool empty() const { return m_vec.empty(); }
95 
96  /** 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 */
97  inline size_type count ( const key_type i ) const { return (i<m_vec.size()) ? 1 : 0; }
98 
99  /** Maximum size due to system limits */
100  inline size_type max_size() const { return m_vec.max_size(); }
101 
102  /** Return a read-only reference to the internal vector */
103  inline const vec_t &getVector() const { return m_vec; }
104 
105  /** Clear the contents of this container */
106  inline void clear() { m_vec.clear(); }
107 
108  /** Efficient swap with another object */
109  inline void swap(map_as_vector<KEY,VALUE>& o) { m_vec.swap(o.m_vec); }
110 
111  /** Write/read via [i] operator, that creates all elements up to (and including) the i'th if they didn't exist already. */
112  inline VALUE & operator[](const size_t i) {
113  if (m_vec.size()<=i) m_vec.resize(i+1);
114  m_vec[i].first=i;
115  return m_vec[i].second;
116  }
117 
118  /** Insert pair<key,val>, as in std::map (guess_point is actually ignored in this class) */
119  inline void insert(const iterator &guess_point, const value_type &keyvalpair ) { this->operator[](keyvalpair.first)=keyvalpair; }
120  /** Insert pair<key,val>, as in std::map */
121  inline void insert(const value_type &keyvalpair ) { this->operator[](keyvalpair.first)=keyvalpair; }
122 
123  /** 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) */
124  inline iterator find(const size_t i) { if (i<m_vec.size()) return m_vec.begin()+i; else return m_vec.end(); }
125  /** 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) */
126  inline const_iterator find(const size_t i) const { if (i<m_vec.size()) return m_vec.begin()+i; else return m_vec.end(); }
127 
128  /** @} */
129 
130 
131  }; // end class map_as_vector
132 
133  } // End of namespace
134 } // End of namespace
135 #endif


Page generated by Doxygen 1.8.3 for MRPT 0.9.6 SVN: at Fri Feb 15 22:05:02 EST 2013