1 ////////////////////////////////////////////////////////////////////////////////
2 // The Loki Library
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_
17 
18 // $Id: AssocVector.h 765 2006-10-18 13:55:32Z syntheticpp $
19 
20 
21 #include <algorithm>
22 #include <functional>
23 #include <vector>
24 #include <utility>
25 
26 namespace Loki
27 {
28 ////////////////////////////////////////////////////////////////////////////////
29 // class template AssocVectorCompare
30 // Used by AssocVector
31 ////////////////////////////////////////////////////////////////////////////////
32 
33     namespace Private
34     {
35         template <class Value, class C>
36         class AssocVectorCompare : public C
37         {
38             typedef std::pair<typename C::first_argument_type, Value>
39                 Data;
40             typedef typename C::first_argument_type first_argument_type;
41 
42         public:
AssocVectorCompare()43             AssocVectorCompare()
44             {}
45 
AssocVectorCompare(const C & src)46             AssocVectorCompare(const C& src) : C(src)
47             {}
48 
operator()49             bool operator()(const first_argument_type& lhs,
50                 const first_argument_type& rhs) const
51             { return C::operator()(lhs, rhs); }
52 
operator()53             bool operator()(const Data& lhs, const Data& rhs) const
54             { return operator()(lhs.first, rhs.first); }
55 
operator()56             bool operator()(const Data& lhs,
57                 const first_argument_type& rhs) const
58             { return operator()(lhs.first, rhs); }
59 
operator()60             bool operator()(const first_argument_type& lhs,
61                 const Data& rhs) const
62             { return operator()(lhs, rhs.first); }
63         };
64     }
65 
66 ////////////////////////////////////////////////////////////////////////////////
67 // class template AssocVector
68 // An associative vector built as a syntactic drop-in replacement for std::map
69 // BEWARE: AssocVector doesn't respect all map's guarantees, the most important
70 //     being:
71 // * iterators are invalidated by insert and erase operations
72 // * the complexity of insert/erase is O(N) not O(log N)
73 // * value_type is std::pair<K, V> not std::pair<const K, V>
74 // * iterators are random
75 ////////////////////////////////////////////////////////////////////////////////
76 
77 
78     template
79     <
80         class K,
81         class V,
82         class C = std::less<K>,
83         class A = std::allocator< std::pair<K, V> >
84     >
85     class AssocVector
86         : private std::vector< std::pair<K, V>, A >
87         , private Private::AssocVectorCompare<V, C>
88     {
89         typedef std::vector<std::pair<K, V>, A> Base;
90         typedef Private::AssocVectorCompare<V, C> MyCompare;
91 
92     public:
93         typedef K key_type;
94         typedef V mapped_type;
95         typedef typename Base::value_type value_type;
96 
97         typedef C key_compare;
98         typedef A allocator_type;
99         typedef typename A::reference reference;
100         typedef typename A::const_reference const_reference;
101         typedef typename Base::iterator iterator;
102         typedef typename Base::const_iterator const_iterator;
103         typedef typename Base::size_type size_type;
104         typedef typename Base::difference_type difference_type;
105         typedef typename A::pointer pointer;
106         typedef typename A::const_pointer const_pointer;
107         typedef typename Base::reverse_iterator reverse_iterator;
108         typedef typename Base::const_reverse_iterator const_reverse_iterator;
109 
110         class value_compare
111             : public std::binary_function<value_type, value_type, bool>
112             , private key_compare
113         {
114             friend class AssocVector;
115 
116         protected:
value_compare(key_compare pred)117             value_compare(key_compare pred) : key_compare(pred)
118             {}
119 
120         public:
operator()121             bool operator()(const value_type& lhs, const value_type& rhs) const
122             { return key_compare::operator()(lhs.first, rhs.first); }
123         };
124 
125         // 23.3.1.1 construct/copy/destroy
126 
127         explicit AssocVector(const key_compare& comp = key_compare(),
128             const A& alloc = A())
Base(alloc)129         : Base(alloc), MyCompare(comp)
130         {}
131 
132         template <class InputIterator>
133         AssocVector(InputIterator first, InputIterator last,
134             const key_compare& comp = key_compare(),
135             const A& alloc = A())
Base(first,last,alloc)136         : Base(first, last, alloc), MyCompare(comp)
137         {
138             MyCompare& me = *this;
139             std::sort(begin(), end(), me);
140         }
141 
142         AssocVector& operator=(const AssocVector& rhs)
143         {
144             AssocVector(rhs).swap(*this);
145             return *this;
146         }
147 
148         // iterators:
149         // The following are here because MWCW gets 'using' wrong
begin()150         iterator begin() { return Base::begin(); }
begin()151         const_iterator begin() const { return Base::begin(); }
end()152         iterator end() { return Base::end(); }
end()153         const_iterator end() const { return Base::end(); }
rbegin()154         reverse_iterator rbegin() { return Base::rbegin(); }
rbegin()155         const_reverse_iterator rbegin() const { return Base::rbegin(); }
rend()156         reverse_iterator rend() { return Base::rend(); }
rend()157         const_reverse_iterator rend() const { return Base::rend(); }
158 
159         // capacity:
empty()160         bool empty() const { return Base::empty(); }
size()161         size_type size() const { return Base::size(); }
max_size()162         size_type max_size() { return Base::max_size(); }
163 
164         // 23.3.1.2 element access:
165         mapped_type& operator[](const key_type& key)
166         { return insert(value_type(key, mapped_type())).first->second; }
167 
168         // modifiers:
insert(const value_type & val)169         std::pair<iterator, bool> insert(const value_type& val)
170         {
171             bool found(true);
172             iterator i(lower_bound(val.first));
173 
174             if (i == end() || this->operator()(val.first, i->first))
175             {
176                 i = Base::insert(i, val);
177                 found = false;
178             }
179             return std::make_pair(i, !found);
180         }
181         //Section [23.1.2], Table 69
182         //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4
insert(iterator pos,const value_type & val)183         iterator insert(iterator pos, const value_type& val)
184         {
185             if( (pos == begin() || this->operator()(*(pos-1),val)) &&
186                 (pos == end()    || this->operator()(val, *pos)) )
187             {
188                 return Base::insert(pos, val);
189             }
190             return insert(val).first;
191         }
192 
193         template <class InputIterator>
insert(InputIterator first,InputIterator last)194         void insert(InputIterator first, InputIterator last)
195         { for (; first != last; ++first) insert(*first); }
196 
erase(iterator pos)197         void erase(iterator pos)
198         { Base::erase(pos); }
199 
erase(const key_type & k)200         size_type erase(const key_type& k)
201         {
202             iterator i(find(k));
203             if (i == end()) return 0;
204             erase(i);
205             return 1;
206         }
207 
erase(iterator first,iterator last)208         void erase(iterator first, iterator last)
209         { Base::erase(first, last); }
210 
swap(AssocVector & other)211         void swap(AssocVector& other)
212         {
213             Base::swap(other);
214             MyCompare& me = *this;
215             MyCompare& rhs = other;
216             std::swap(me, rhs);
217         }
218 
clear()219         void clear()
220         { Base::clear(); }
221 
222         // observers:
key_comp()223         key_compare key_comp() const
224         { return *this; }
225 
value_comp()226         value_compare value_comp() const
227         {
228             const key_compare& comp = *this;
229             return value_compare(comp);
230         }
231 
232         // 23.3.1.3 map operations:
find(const key_type & k)233         iterator find(const key_type& k)
234         {
235             iterator i(lower_bound(k));
236             if (i != end() && this->operator()(k, i->first))
237             {
238                 i = end();
239             }
240             return i;
241         }
242 
find(const key_type & k)243         const_iterator find(const key_type& k) const
244         {
245             const_iterator i(lower_bound(k));
246             if (i != end() && this->operator()(k, i->first))
247             {
248                 i = end();
249             }
250             return i;
251         }
252 
count(const key_type & k)253         size_type count(const key_type& k) const
254         { return find(k) != end(); }
255 
lower_bound(const key_type & k)256         iterator lower_bound(const key_type& k)
257         {
258             MyCompare& me = *this;
259             return std::lower_bound(begin(), end(), k, me);
260         }
261 
lower_bound(const key_type & k)262         const_iterator lower_bound(const key_type& k) const
263         {
264             const MyCompare& me = *this;
265             return std::lower_bound(begin(), end(), k, me);
266         }
267 
upper_bound(const key_type & k)268         iterator upper_bound(const key_type& k)
269         {
270             MyCompare& me = *this;
271             return std::upper_bound(begin(), end(), k, me);
272         }
273 
upper_bound(const key_type & k)274         const_iterator upper_bound(const key_type& k) const
275         {
276             const MyCompare& me = *this;
277             return std::upper_bound(begin(), end(), k, me);
278         }
279 
equal_range(const key_type & k)280         std::pair<iterator, iterator> equal_range(const key_type& k)
281         {
282             MyCompare& me = *this;
283             return std::equal_range(begin(), end(), k, me);
284         }
285 
equal_range(const key_type & k)286         std::pair<const_iterator, const_iterator> equal_range(
287             const key_type& k) const
288         {
289             const MyCompare& me = *this;
290             return std::equal_range(begin(), end(), k, me);
291         }
292 
293         template <class K1, class V1, class C1, class A1>
294         friend bool operator==(const AssocVector<K1, V1, C1, A1>& lhs,
295                         const AssocVector<K1, V1, C1, A1>& rhs);
296 
297         bool operator<(const AssocVector& rhs) const
298         {
299             const Base& me = *this;
300             const Base& yo = rhs;
301             return me < yo;
302         }
303 
304         template <class K1, class V1, class C1, class A1>
305         friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs,
306                                const AssocVector<K1, V1, C1, A1>& rhs);
307 
308         template <class K1, class V1, class C1, class A1>
309         friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs,
310                               const AssocVector<K1, V1, C1, A1>& rhs);
311 
312         template <class K1, class V1, class C1, class A1>
313         friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs,
314                                const AssocVector<K1, V1, C1, A1>& rhs);
315 
316         template <class K1, class V1, class C1, class A1>
317         friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs,
318                                const AssocVector<K1, V1, C1, A1>& rhs);
319     };
320 
321     template <class K, class V, class C, class A>
322     inline bool operator==(const AssocVector<K, V, C, A>& lhs,
323                            const AssocVector<K, V, C, A>& rhs)
324     {
325       const std::vector<std::pair<K, V>, A>& me = lhs;
326       return me == rhs;
327     }
328 
329     template <class K, class V, class C, class A>
330     inline bool operator!=(const AssocVector<K, V, C, A>& lhs,
331                            const AssocVector<K, V, C, A>& rhs)
332     { return !(lhs == rhs); }
333 
334     template <class K, class V, class C, class A>
335     inline bool operator>(const AssocVector<K, V, C, A>& lhs,
336                           const AssocVector<K, V, C, A>& rhs)
337     { return rhs < lhs; }
338 
339     template <class K, class V, class C, class A>
340     inline bool operator>=(const AssocVector<K, V, C, A>& lhs,
341                            const AssocVector<K, V, C, A>& rhs)
342     { return !(lhs < rhs); }
343 
344     template <class K, class V, class C, class A>
345     inline bool operator<=(const AssocVector<K, V, C, A>& lhs,
346                            const AssocVector<K, V, C, A>& rhs)
347     { return !(rhs < lhs); }
348 
349 
350     // specialized algorithms:
351     template <class K, class V, class C, class A>
swap(AssocVector<K,V,C,A> & lhs,AssocVector<K,V,C,A> & rhs)352     void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
353     { lhs.swap(rhs); }
354 
355 } // namespace Loki
356 
357 #endif // end file guardian
358 
359