1 ////////////////////////////////////////////////////////////////////////////////
3 // Copyright (c) 2001 by Andrei Alexandrescu
4 // This code accompanies the book:
5 // Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design
6 // Patterns Applied". Copyright (c) 2001. Addison-Wesley.
7 // Permission to use, copy, modify, distribute and sell this software for any
8 // purpose is hereby granted without fee, provided that the above copyright
9 // notice appear in all copies and that both that copyright notice and this
10 // permission notice appear in supporting documentation.
11 // The author or Addison-Wesley Longman make no representations about the
12 // suitability of this software for any purpose. It is provided "as is"
13 // without express or implied warranty.
14 ////////////////////////////////////////////////////////////////////////////////
15 #ifndef LOKI_ASSOCVECTOR_INC_
16 #define LOKI_ASSOCVECTOR_INC_
18 // $Id: AssocVector.h 765 2006-10-18 13:55:32Z syntheticpp $
28 ////////////////////////////////////////////////////////////////////////////////
29 // class template AssocVectorCompare
30 // Used by AssocVector
31 ////////////////////////////////////////////////////////////////////////////////
35 template <class Value, class C>
36 class AssocVectorCompare : public C
38 typedef std::pair<typename C::first_argument_type, Value>
40 typedef typename C::first_argument_type first_argument_type;
46 AssocVectorCompare(const C &src) : C(src)
49 bool operator()(const first_argument_type &lhs,
50 const first_argument_type &rhs) const
52 return C::operator()(lhs, rhs);
55 bool operator()(const Data &lhs, const Data &rhs) const
57 return operator()(lhs.first, rhs.first);
60 bool operator()(const Data &lhs,
61 const first_argument_type &rhs) const
63 return operator()(lhs.first, rhs);
66 bool operator()(const first_argument_type &lhs,
67 const Data &rhs) const
69 return operator()(lhs, rhs.first);
74 ////////////////////////////////////////////////////////////////////////////////
75 // class template AssocVector
76 // An associative vector built as a syntactic drop-in replacement for std::map
77 // BEWARE: AssocVector doesn't respect all map's guarantees, the most important
79 // * iterators are invalidated by insert and erase operations
80 // * the complexity of insert/erase is O(N) not O(log N)
81 // * value_type is std::pair<K, V> not std::pair<const K, V>
82 // * iterators are random
83 ////////////////////////////////////////////////////////////////////////////////
90 class C = std::less<K>,
91 class A = std::allocator< std::pair<K, V> >
94 : private std::vector< std::pair<K, V>, A >
95 , private Private::AssocVectorCompare<V, C>
97 typedef std::vector<std::pair<K, V>, A> Base;
98 typedef Private::AssocVectorCompare<V, C> MyCompare;
102 typedef V mapped_type;
103 typedef typename Base::value_type value_type;
105 typedef C key_compare;
106 typedef A allocator_type;
107 typedef typename A::reference reference;
108 typedef typename A::const_reference const_reference;
109 typedef typename Base::iterator iterator;
110 typedef typename Base::const_iterator const_iterator;
111 typedef typename Base::size_type size_type;
112 typedef typename Base::difference_type difference_type;
113 typedef typename A::pointer pointer;
114 typedef typename A::const_pointer const_pointer;
115 typedef typename Base::reverse_iterator reverse_iterator;
116 typedef typename Base::const_reverse_iterator const_reverse_iterator;
119 : public std::binary_function<value_type, value_type, bool>
120 , private key_compare
122 friend class AssocVector;
125 value_compare(key_compare pred) : key_compare(pred)
129 bool operator()(const value_type &lhs, const value_type &rhs) const
131 return key_compare::operator()(lhs.first, rhs.first);
135 // 23.3.1.1 construct/copy/destroy
137 explicit AssocVector(const key_compare &comp = key_compare(),
138 const A &alloc = A())
139 : Base(alloc), MyCompare(comp)
142 template <class InputIterator>
143 AssocVector(InputIterator first, InputIterator last,
144 const key_compare &comp = key_compare(),
145 const A &alloc = A())
146 : Base(first, last, alloc), MyCompare(comp)
148 MyCompare &me = *this;
149 std::sort(begin(), end(), me);
152 AssocVector &operator=(const AssocVector &rhs)
154 AssocVector(rhs).swap(*this);
159 // The following are here because MWCW gets 'using' wrong
162 return Base::begin();
164 const_iterator begin() const
166 return Base::begin();
172 const_iterator end() const
176 reverse_iterator rbegin()
178 return Base::rbegin();
180 const_reverse_iterator rbegin() const
182 return Base::rbegin();
184 reverse_iterator rend()
188 const_reverse_iterator rend() const
196 return Base::empty();
198 size_type size() const
204 return Base::max_size();
207 // 23.3.1.2 element access:
208 mapped_type &operator[](const key_type &key)
210 return insert(value_type(key, mapped_type())).first->second;
214 std::pair<iterator, bool> insert(const value_type &val)
217 iterator i(lower_bound(val.first));
219 if (i == end() || this->operator()(val.first, i->first))
221 i = Base::insert(i, val);
224 return std::make_pair(i, !found);
226 //Section [23.1.2], Table 69
227 //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4
228 iterator insert(iterator pos, const value_type &val)
230 if( (pos == begin() || this->operator()(*(pos-1),val)) &&
231 (pos == end() || this->operator()(val, *pos)) )
233 return Base::insert(pos, val);
235 return insert(val).first;
238 template <class InputIterator>
239 void insert(InputIterator first, InputIterator last)
241 for (; first != last; ++first) insert(*first);
244 void erase(iterator pos)
249 size_type erase(const key_type &k)
252 if (i == end()) return 0;
257 void erase(iterator first, iterator last)
259 Base::erase(first, last);
262 void swap(AssocVector &other)
265 MyCompare &me = *this;
266 MyCompare &rhs = other;
276 key_compare key_comp() const
281 value_compare value_comp() const
283 const key_compare &comp = *this;
284 return value_compare(comp);
287 // 23.3.1.3 map operations:
288 iterator find(const key_type &k)
290 iterator i(lower_bound(k));
291 if (i != end() && this->operator()(k, i->first))
298 const_iterator find(const key_type &k) const
300 const_iterator i(lower_bound(k));
301 if (i != end() && this->operator()(k, i->first))
308 size_type count(const key_type &k) const
310 return find(k) != end();
313 iterator lower_bound(const key_type &k)
315 MyCompare &me = *this;
316 return std::lower_bound(begin(), end(), k, me);
319 const_iterator lower_bound(const key_type &k) const
321 const MyCompare &me = *this;
322 return std::lower_bound(begin(), end(), k, me);
325 iterator upper_bound(const key_type &k)
327 MyCompare &me = *this;
328 return std::upper_bound(begin(), end(), k, me);
331 const_iterator upper_bound(const key_type &k) const
333 const MyCompare &me = *this;
334 return std::upper_bound(begin(), end(), k, me);
337 std::pair<iterator, iterator> equal_range(const key_type &k)
339 MyCompare &me = *this;
340 return std::equal_range(begin(), end(), k, me);
343 std::pair<const_iterator, const_iterator> equal_range(
344 const key_type &k) const
346 const MyCompare &me = *this;
347 return std::equal_range(begin(), end(), k, me);
350 template <class K1, class V1, class C1, class A1>
351 friend bool operator==(const AssocVector<K1, V1, C1, A1>& lhs,
352 const AssocVector<K1, V1, C1, A1>& rhs);
354 bool operator<(const AssocVector &rhs) const
356 const Base &me = *this;
357 const Base &yo = rhs;
361 template <class K1, class V1, class C1, class A1>
362 friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs,
363 const AssocVector<K1, V1, C1, A1>& rhs);
365 template <class K1, class V1, class C1, class A1>
366 friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs,
367 const AssocVector<K1, V1, C1, A1>& rhs);
369 template <class K1, class V1, class C1, class A1>
370 friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs,
371 const AssocVector<K1, V1, C1, A1>& rhs);
373 template <class K1, class V1, class C1, class A1>
374 friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs,
375 const AssocVector<K1, V1, C1, A1>& rhs);
378 template <class K, class V, class C, class A>
379 inline bool operator==(const AssocVector<K, V, C, A>& lhs,
380 const AssocVector<K, V, C, A>& rhs)
382 const std::vector<std::pair<K, V>, A>& me = lhs;
386 template <class K, class V, class C, class A>
387 inline bool operator!=(const AssocVector<K, V, C, A>& lhs,
388 const AssocVector<K, V, C, A>& rhs)
390 return !(lhs == rhs);
393 template <class K, class V, class C, class A>
394 inline bool operator>(const AssocVector<K, V, C, A>& lhs,
395 const AssocVector<K, V, C, A>& rhs)
400 template <class K, class V, class C, class A>
401 inline bool operator>=(const AssocVector<K, V, C, A>& lhs,
402 const AssocVector<K, V, C, A>& rhs)
407 template <class K, class V, class C, class A>
408 inline bool operator<=(const AssocVector<K, V, C, A>& lhs,
409 const AssocVector<K, V, C, A>& rhs)
415 // specialized algorithms:
416 template <class K, class V, class C, class A>
417 void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
424 #endif // end file guardian