00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016 #ifndef ASSOCVECTOR_INC_
00017 #define ASSOCVECTOR_INC_
00018
00019 #include <algorithm>
00020 #include <functional>
00021 #include <vector>
00022 #include <utility>
00023
00024 namespace Loki
00025 {
00026
00027
00028
00029
00030
00031 namespace Private
00032 {
00033 template <class Value, class C>
00034 class AssocVectorCompare : public C
00035 {
00036 typedef std::pair<typename C::first_argument_type, Value>
00037 Data;
00038 typedef typename C::first_argument_type first_argument_type;
00039
00040 public:
00041 AssocVectorCompare()
00042 {}
00043
00044 AssocVectorCompare(const C& src) : C(src)
00045 {}
00046
00047 bool operator()(const first_argument_type& lhs,
00048 const first_argument_type& rhs) const
00049 { return C::operator()(lhs, rhs); }
00050
00051 bool operator()(const Data& lhs, const Data& rhs) const
00052 { return operator()(lhs.first, rhs.first); }
00053
00054 bool operator()(const Data& lhs,
00055 const first_argument_type& rhs) const
00056 { return operator()(lhs.first, rhs); }
00057
00058 bool operator()(const first_argument_type& lhs,
00059 const Data& rhs) const
00060 { return operator()(lhs, rhs.first); }
00061 };
00062 }
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075 template
00076 <
00077 class K,
00078 class V,
00079 class C = std::less<K>,
00080 class A = std::allocator< std::pair<K, V> >
00081 >
00082 class AssocVector
00083 : private std::vector< std::pair<K, V>, A >
00084 , private Private::AssocVectorCompare<V, C>
00085 {
00086 typedef std::vector<std::pair<K, V>, A> Base;
00087 typedef Private::AssocVectorCompare<V, C> MyCompare;
00088
00089 public:
00090 typedef K key_type;
00091 typedef V mapped_type;
00092 typedef typename Base::value_type value_type;
00093
00094 typedef C key_compare;
00095 typedef A allocator_type;
00096 typedef typename A::reference reference;
00097 typedef typename A::const_reference const_reference;
00098 typedef typename Base::iterator iterator;
00099 typedef typename Base::const_iterator const_iterator;
00100 typedef typename Base::size_type size_type;
00101 typedef typename Base::difference_type difference_type;
00102 typedef typename A::pointer pointer;
00103 typedef typename A::const_pointer const_pointer;
00104 typedef typename Base::reverse_iterator reverse_iterator;
00105 typedef typename Base::const_reverse_iterator const_reverse_iterator;
00106
00107 class value_compare
00108 : public std::binary_function<value_type, value_type, bool>
00109 , private key_compare
00110 {
00111 friend class AssocVector;
00112
00113 protected:
00114 value_compare(key_compare pred) : key_compare(pred)
00115 {}
00116
00117 public:
00118 bool operator()(const value_type& lhs, const value_type& rhs) const
00119 { return key_compare::operator()(lhs.first, rhs.first); }
00120 };
00121
00122
00123
00124 explicit AssocVector(const key_compare& comp = key_compare(),
00125 const A& alloc = A())
00126 : Base(alloc), MyCompare(comp)
00127 {}
00128
00129 template <class InputIterator>
00130 AssocVector(InputIterator first, InputIterator last,
00131 const key_compare& comp = key_compare(),
00132 const A& alloc = A())
00133 : Base(first, last, alloc), MyCompare(comp)
00134 {
00135 MyCompare& me = *this;
00136 std::sort(begin(), end(), me);
00137 }
00138
00139 AssocVector& operator=(const AssocVector& rhs)
00140 {
00141 AssocVector(rhs).swap(*this);
00142 return *this;
00143 }
00144
00145
00146
00147 iterator begin() { return Base::begin(); }
00148 const_iterator begin() const { return Base::begin(); }
00149 iterator end() { return Base::end(); }
00150 const_iterator end() const { return Base::end(); }
00151 reverse_iterator rbegin() { return Base::rbegin(); }
00152 const_reverse_iterator rbegin() const { return Base::rbegin(); }
00153 reverse_iterator rend() { return Base::rend(); }
00154 const_reverse_iterator rend() const { return Base::rend(); }
00155
00156
00157 bool empty() const { return Base::empty(); }
00158 size_type size() const { return Base::size(); }
00159 size_type max_size() { return Base::max_size(); }
00160
00161
00162 mapped_type& operator[](const key_type& key)
00163 { return insert(value_type(key, mapped_type())).first->second; }
00164
00165
00166 std::pair<iterator, bool> insert(const value_type& val)
00167 {
00168 bool found(true);
00169 iterator i(lower_bound(val.first));
00170
00171 if (i == end() || this->operator()(val.first, i->first))
00172 {
00173 i = Base::insert(i, val);
00174 found = false;
00175 }
00176 return std::make_pair(i, !found);
00177 }
00178
00179 iterator insert(iterator pos, const value_type& val)
00180 {
00181 if (pos != end() && this->operator()(*pos, val) &&
00182 (pos == end() - 1 ||
00183 !this->operator()(val, pos[1]) &&
00184 this->operator()(pos[1], val)))
00185 {
00186 return Base::insert(pos, val);
00187 }
00188 return insert(val).first;
00189 }
00190
00191 template <class InputIterator>
00192 void insert(InputIterator first, InputIterator last)
00193 { for (; first != last; ++first) insert(*first); }
00194
00195 void erase(iterator pos)
00196 { Base::erase(pos); }
00197
00198 size_type erase(const key_type& k)
00199 {
00200 iterator i(find(k));
00201 if (i == end()) return 0;
00202 erase(i);
00203 return 1;
00204 }
00205
00206 void erase(iterator first, iterator last)
00207 { Base::erase(first, last); }
00208
00209 void swap(AssocVector& other)
00210 {
00211 using std::swap;
00212 Base::swap(other);
00213 MyCompare& me = *this;
00214 MyCompare& rhs = other;
00215 swap(me, rhs);
00216 }
00217
00218 void clear()
00219 { Base::clear(); }
00220
00221
00222 key_compare key_comp() const
00223 { return *this; }
00224
00225 value_compare value_comp() const
00226 {
00227 const key_compare& comp = *this;
00228 return value_compare(comp);
00229 }
00230
00231
00232 iterator find(const key_type& k)
00233 {
00234 iterator i(lower_bound(k));
00235 if (i != end() && this->operator()(k, i->first))
00236 {
00237 i = end();
00238 }
00239 return i;
00240 }
00241
00242 const_iterator find(const key_type& k) const
00243 {
00244 const_iterator i(lower_bound(k));
00245 if (i != end() && this->operator()(k, i->first))
00246 {
00247 i = end();
00248 }
00249 return i;
00250 }
00251
00252 size_type count(const key_type& k) const
00253 { return find(k) != end(); }
00254
00255 iterator lower_bound(const key_type& k)
00256 {
00257 MyCompare& me = *this;
00258 return std::lower_bound(begin(), end(), k, me);
00259 }
00260
00261 const_iterator lower_bound(const key_type& k) const
00262 {
00263 const MyCompare& me = *this;
00264 return std::lower_bound(begin(), end(), k, me);
00265 }
00266
00267 iterator upper_bound(const key_type& k)
00268 {
00269 MyCompare& me = *this;
00270 return std::upper_bound(begin(), end(), k, me);
00271 }
00272
00273 const_iterator upper_bound(const key_type& k) const
00274 {
00275 const MyCompare& me = *this;
00276 return std::upper_bound(begin(), end(), k, me);
00277 }
00278
00279 std::pair<iterator, iterator> equal_range(const key_type& k)
00280 {
00281 MyCompare& me = *this;
00282 return std::equal_range(begin(), end(), k, me);
00283 }
00284
00285 std::pair<const_iterator, const_iterator> equal_range(
00286 const key_type& k) const
00287 {
00288 const MyCompare& me = *this;
00289 return std::equal_range(begin(), end(), k, me);
00290 }
00291
00292 friend bool operator==(const AssocVector& lhs, const AssocVector& rhs)
00293 {
00294 const Base& me = lhs;
00295 return me == rhs;
00296 }
00297
00298 bool operator<(const AssocVector& rhs) const
00299 {
00300 const Base& me = *this;
00301 const Base& yo = rhs;
00302 return me < yo;
00303 }
00304
00305 friend bool operator!=(const AssocVector& lhs, const AssocVector& rhs)
00306 { return !(lhs == rhs); }
00307
00308 friend bool operator>(const AssocVector& lhs, const AssocVector& rhs)
00309 { return rhs < lhs; }
00310
00311 friend bool operator>=(const AssocVector& lhs, const AssocVector& rhs)
00312 { return !(lhs < rhs); }
00313
00314 friend bool operator<=(const AssocVector& lhs, const AssocVector& rhs)
00315 { return !(rhs < lhs); }
00316 };
00317
00318
00319 template <class K, class V, class C, class A>
00320 void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
00321 { lhs.swap(rhs); }
00322
00323 }
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336 #endif // ASSOCVECTOR_INC_