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