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.2 for MRPT 0.9.4 SVN: at Mon Jan 10 22:30:30 UTC 2011 |