Main MRPT website > C++ reference
MRPT logo

map_as_vector.h

Go to the documentation of this file.
00001 /* +---------------------------------------------------------------------------+
00002    |          The Mobile Robot Programming Toolkit (MRPT) C++ library          |
00003    |                                                                           |
00004    |                   http://mrpt.sourceforge.net/                            |
00005    |                                                                           |
00006    |   Copyright (C) 2005-2011  University of Malaga                           |
00007    |                                                                           |
00008    |    This software was written by the Machine Perception and Intelligent    |
00009    |      Robotics Lab, University of Malaga (Spain).                          |
00010    |    Contact: Jose-Luis Blanco  <jlblanco@ctima.uma.es>                     |
00011    |                                                                           |
00012    |  This file is part of the MRPT project.                                   |
00013    |                                                                           |
00014    |     MRPT is free software: you can redistribute it and/or modify          |
00015    |     it under the terms of the GNU General Public License as published by  |
00016    |     the Free Software Foundation, either version 3 of the License, or     |
00017    |     (at your option) any later version.                                   |
00018    |                                                                           |
00019    |   MRPT is distributed in the hope that it will be useful,                 |
00020    |     but WITHOUT ANY WARRANTY; without even the implied warranty of        |
00021    |     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         |
00022    |     GNU General Public License for more details.                          |
00023    |                                                                           |
00024    |     You should have received a copy of the GNU General Public License     |
00025    |     along with MRPT.  If not, see <http://www.gnu.org/licenses/>.         |
00026    |                                                                           |
00027    +---------------------------------------------------------------------------+ */
00028 #ifndef  mrpt_map_as_vector_H
00029 #define  mrpt_map_as_vector_H
00030 
00031 // Note: This file is included from "stl_extensions.h"
00032 #include <mrpt/utils/utils_defs.h>
00033 #include <map>
00034 #include <vector>
00035 
00036 namespace mrpt
00037 {
00038         namespace utils
00039         {
00040                 /** 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.
00041                   *  Note that KEY must be integer types only (size_t, uint32_t, etc.)
00042                   *  This implementation is much more efficient than std::map<> when the most common operation is accesing elements
00043                   *   by KEY with find() or [], and the range of KEY values starts at 0 (or a reasonable low number).
00044                   *
00045                   * This container is internally implemented as a linear array (std::vector) of the same fundamental type than the equivalent std::map<K,V>,
00046                   *  that is, elements are <code> std::pair<K,V> </code> (note that K is NOT const as in std::map).
00047                   * I know, I know... this implementation wastes a lot of useless key elements in the pair.first when indices
00048                   * are already implicit in the std::vector<> order... but I promise I'll pay a beer to whoever show me an
00049                   *  *efficient* alternative. If failed, update this comment: COUNTER OF WASTED HOURS WITH THIS: 3h
00050                   *
00051                   * Note that there is one <b>fundamental difference</b> wrt std::map<>: if you start with an empty map_as_vector<> and
00052                   *   insert one element at the i'th position (with either [] or insert), the elements [0,i-1] will also exist then, but both
00053                   *   their first & second entries (for the corresponding std::pair) will be <b>undefined</b>. This was intentional in order to
00054                   *   gain efficiency (in particular, each std::pair<> doesn't have a constructor when resizing the underlying std::vector).
00055                   *
00056                   */
00057                 template <typename KEY,typename VALUE>
00058                 class map_as_vector
00059                 {
00060                 public:
00061                         /** @name Iterators stuff and other types
00062                             @{ */
00063                         typedef KEY                                     key_type;
00064                         typedef std::pair<KEY,VALUE>                    value_type;
00065                         typedef typename mrpt::aligned_containers<value_type>::vector_t  vec_t;
00066                         typedef typename vec_t::size_type               size_type;
00067                         typedef typename vec_t::iterator                iterator;
00068                         typedef typename vec_t::const_iterator          const_iterator;
00069                         typedef std::reverse_iterator<iterator>                 reverse_iterator;
00070                         typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
00071 
00072                         inline iterator                 begin()   { return m_vec.begin(); }
00073                         inline iterator                 end()     { return m_vec.end(); }
00074                         inline const_iterator   begin() const   { return m_vec.begin(); }
00075                         inline const_iterator   end() const             { return m_vec.end(); }
00076                         inline reverse_iterator                 rbegin()                { return reverse_iterator(end()); }
00077                         inline const_reverse_iterator   rbegin() const  { return const_reverse_iterator(end()); }
00078                         inline reverse_iterator                 rend()                  { return reverse_iterator(begin()); }
00079                         inline const_reverse_iterator   rend() const    { return const_reverse_iterator(begin()); }
00080                         /** @} */
00081                 private:
00082                         vec_t  m_vec; //!< The actual container
00083 
00084                 public:
00085                         /** @name Constructors, read/write access and other operations
00086                             @{ */
00087                         //!< Default constructor - does nothing */
00088                         inline map_as_vector() { }
00089                         /** Copy constructor */
00090                         inline map_as_vector(const map_as_vector<KEY,VALUE> &o) : m_vec(o.m_vec) { }
00091 
00092                         inline size_t size() const { return m_vec.size(); }
00093                         inline bool empty() const { return m_vec.empty(); }
00094 
00095                         /** 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 */
00096                         inline size_type count ( const key_type i ) const { return (i<m_vec.size()) ? 1 : 0; }
00097 
00098                         /** Maximum size due to system limits */
00099                         inline size_type max_size() const { return m_vec.max_size(); }
00100 
00101                         /** Return a read-only reference to the internal vector */
00102                         inline const vec_t &getVector() const { return m_vec; }
00103 
00104                         /** Clear the contents of this container */
00105                         inline void clear() { m_vec.clear(); }
00106 
00107                         /** Efficient swap with another object */
00108                         inline void swap(map_as_vector<KEY,VALUE>& o) { m_vec.swap(o.m_vec); }
00109 
00110                         /** Write/read via [i] operator, that creates all elements up to (and including) the i'th if they didn't exist already. */
00111                         inline VALUE & operator[](const size_t i) {
00112                                 if (m_vec.size()<=i) m_vec.resize(i+1);
00113                                 m_vec[i].first=i;
00114                                 return m_vec[i].second;
00115                         }
00116 
00117                         /** Insert pair<key,val>, as in std::map (guess_point is actually ignored in this class) */
00118                         inline void insert(const iterator &guess_point, const value_type &keyvalpair ) { this->operator[](keyvalpair.first)=keyvalpair; }
00119                         /** Insert pair<key,val>, as in std::map */
00120                         inline void insert(const value_type &keyvalpair ) { this->operator[](keyvalpair.first)=keyvalpair; }
00121 
00122                         /** 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) */
00123                         inline iterator       find(const size_t i)       { if (i<m_vec.size()) return m_vec.begin()+i; else return m_vec.end(); }
00124                         /** 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) */
00125                         inline const_iterator find(const size_t i) const { if (i<m_vec.size()) return m_vec.begin()+i; else return m_vec.end(); }
00126 
00127                         /** @} */
00128 
00129 
00130                 };  // end class map_as_vector
00131 
00132         } // End of namespace
00133 } // End of namespace
00134 #endif



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN:exported at Tue Jan 25 21:56:31 UTC 2011