00001
00002 #ifndef STLUTIL_MAPVECTOR_H
00003 #define STLUTIL_MAPVECTOR_H 1
00004
00005 #include "CLHEP/config/CLHEP.h"
00006 #include <memory>
00007 #include <algorithm>
00008 #include <functional>
00009 #include <vector>
00010 #include <utility>
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00044 template <class KEY, class DATA, class COMP=std::less<KEY>,
00045 class Allocator=std::allocator<std::pair<KEY,DATA> > >
00046 class MapVector
00047 {
00048 public:
00049 typedef std::pair<KEY,DATA> value_type;
00050 typedef DATA data_type;
00051 typedef KEY key_type;
00052 typedef COMP compare_type;
00053 typedef Allocator allocator_type;
00054 typedef std::vector<value_type,allocator_type> collection_type;
00055 typedef typename collection_type::iterator iterator;
00056 typedef typename collection_type::const_iterator const_iterator;
00057 typedef typename collection_type::reference reference;
00058 typedef typename collection_type::const_reference const_reference;
00059 typedef typename collection_type::size_type size_type;
00060
00061 MapVector();
00062
00063 iterator find(const key_type& key);
00064 const_iterator find(const key_type& key) const;
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079 DATA& operator[](const key_type& key);
00080
00081
00082 reference at(size_type s) { cont.at(s); }
00083 const_reference at(size_type s) const { cont.at(s); }
00084
00085 iterator end() { return cont.end(); }
00086 const_iterator end() const { return cont.end(); }
00087 iterator begin() { return cont.begin(); }
00088 const_iterator begin() const { return cont.begin(); }
00089
00090 void add(const key_type& key, const data_type& data);
00091 void push_back(const value_type& newitem);
00092
00093 iterator insert(iterator i,const value_type& newitem)
00094 { push_back(newitem); return i;}
00095
00096 void reserve(typename collection_type::size_type x) { cont.reserve(x); }
00097
00098 size_type size() const { return cont.size(); }
00099
00100 private:
00101 friend class MapVectorTest;
00102 void sort_() const;
00103 iterator find_(const key_type& key) const;
00104
00105 struct comp
00106 {
00107 bool operator()(const value_type& a, const value_type& b)
00108 {
00109 compare_type c;
00110 return c(a.first,b.first);
00111 }
00112 };
00113
00114 struct comp2
00115 {
00116 bool operator()(const value_type& a, const key_type& b)
00117 {
00118 compare_type c;
00119 return c(a.first,b);
00120 }
00121 };
00122
00123 mutable collection_type cont;
00124 mutable bool is_sorted_;
00125 };
00126
00127
00128
00129 template <class KEY,class DATA,class COMP,class Allocator>
00130 inline MapVector<KEY,DATA,COMP,Allocator>::MapVector():is_sorted_(true) { }
00131
00132 template <class KEY,class DATA,class COMP,class Allocator>
00133 inline void MapVector<KEY,DATA,COMP,Allocator>::sort_() const
00134 {
00135 if(is_sorted_==false)
00136 {
00137 std::sort(cont.begin(),cont.end(),comp());
00138 is_sorted_=true;
00139 }
00140 }
00141
00142 template <class KEY,class DATA,class COMP,class Allocator>
00143 inline DATA& MapVector<KEY,DATA,COMP,Allocator>::operator[](const key_type& key)
00144 {
00145 if (cont.size() == 0) {
00146 push_back( value_type(key,data_type()) );
00147 return cont.back().second;
00148 }
00149
00150 if (is_sorted_) {
00151
00152 COMP comp;
00153
00154 if (comp(cont.back().first, key)) {
00155 push_back(value_type(key, data_type()));
00156 }
00157
00158 if (! comp(key, cont.back().first)) {
00159 return cont.back().second;
00160 }
00161 }
00162
00163 iterator i = find(key);
00164
00165 if(i!=end())
00166 return i->second;
00167 else
00168 {
00169 push_back( value_type(key,data_type()) );
00170 return cont.back().second;
00171 }
00172 }
00173
00174 template <class KEY,class DATA,class COMP,class Allocator>
00175 inline typename MapVector<KEY,DATA,COMP,Allocator>::iterator
00176 MapVector<KEY,DATA,COMP,Allocator>::find(const key_type& key)
00177 {
00178 return find_(key);
00179 }
00180
00181 template <class KEY,class DATA,class COMP,class Allocator>
00182 inline typename MapVector<KEY,DATA,COMP,Allocator>::const_iterator
00183 MapVector<KEY,DATA,COMP,Allocator>::find(const key_type& key) const
00184 {
00185 return find_(key);
00186 }
00187
00188 template <class KEY,class DATA,class COMP,class Allocator>
00189 inline typename MapVector<KEY,DATA,COMP,Allocator>::iterator
00190 MapVector<KEY,DATA,COMP,Allocator>::find_(const key_type& key) const
00191 {
00192 sort_();
00193 iterator x(std::lower_bound(cont.begin(),cont.end(),key,comp2()));
00194 if(x==cont.end()) return x;
00195 if(x->first!=key) return cont.end();
00196 return x;
00197 }
00198
00199 template <class KEY,class DATA,class COMP,class Allocator>
00200 inline void MapVector<KEY,DATA,COMP,Allocator>::push_back(const value_type& newitem)
00201 {
00202 COMP comp;
00203 if (cont.size() > 0 &&
00204 comp(newitem.first, cont.back().first)) is_sorted_ = false;
00205 cont.push_back(newitem);
00206 }
00207
00208 template <class KEY,class DATA,class COMP,class Allocator>
00209 inline void
00210 MapVector<KEY,DATA,COMP,Allocator>::add(const key_type& key, const data_type& data)
00211 {
00212 push_back(value_type(key,data));
00213 }
00214
00215 #endif