Line data Source code
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 : //
8 : // Permission is hereby granted, free of charge, to any person obtaining a copy
9 : // of this software and associated documentation files (the "Software"), to deal
10 : // in the Software without restriction, including without limitation the rights
11 : // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 : // copies of the Software, and to permit persons to whom the Software is
13 : // furnished to do so, subject to the following conditions:
14 : //
15 : // The above copyright notice and this permission notice shall be included in
16 : // all copies or substantial portions of the Software.
17 : //
18 : // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 : // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 : // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 : // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 : // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 : // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 : // SOFTWARE.
25 : ////////////////////////////////////////////////////////////////////////////////
26 : #ifndef LOKI_ASSOCVECTOR_INC_
27 : #define LOKI_ASSOCVECTOR_INC_
28 :
29 : // $Id$
30 :
31 :
32 : #include <algorithm>
33 : #include <functional>
34 : #include <vector>
35 : #include <utility>
36 : #include <iterator>
37 : #include <map>
38 :
39 :
40 : namespace Loki
41 : {
42 : ////////////////////////////////////////////////////////////////////////////////
43 : // class template AssocVectorCompare
44 : // Used by AssocVector
45 : ////////////////////////////////////////////////////////////////////////////////
46 :
47 : namespace Private
48 : {
49 : template <class Value, class C>
50 : class AssocVectorCompare : public C
51 : {
52 : typedef std::pair<typename C::first_argument_type, Value>
53 : Data;
54 : typedef typename C::first_argument_type first_argument_type;
55 :
56 : public:
57 : AssocVectorCompare()
58 : {}
59 :
60 : AssocVectorCompare(const C& src) : C(src)
61 : {}
62 :
63 : bool operator()(const first_argument_type& lhs,
64 : const first_argument_type& rhs) const
65 : { return C::operator()(lhs, rhs); }
66 :
67 : bool operator()(const Data& lhs, const Data& rhs) const
68 : { return operator()(lhs.first, rhs.first); }
69 :
70 : bool operator()(const Data& lhs,
71 : const first_argument_type& rhs) const
72 57 : { return operator()(lhs.first, rhs); }
73 :
74 : bool operator()(const first_argument_type& lhs,
75 : const Data& rhs) const
76 : { return operator()(lhs, rhs.first); }
77 : };
78 : }
79 :
80 : ////////////////////////////////////////////////////////////////////////////////
81 : // class template AssocVector
82 : // An associative vector built as a syntactic drop-in replacement for std::map
83 : // BEWARE: AssocVector doesn't respect all map's guarantees, the most important
84 : // being:
85 : // * iterators are invalidated by insert and erase operations
86 : // * the complexity of insert/erase is O(N) not O(log N)
87 : // * value_type is std::pair<K, V> not std::pair<const K, V>
88 : // * iterators are random
89 : ////////////////////////////////////////////////////////////////////////////////
90 :
91 :
92 : template
93 : <
94 : class K,
95 : class V,
96 : class C = std::less<K>,
97 : class A = std::allocator< std::pair<K, V> >
98 : >
99 30 : class AssocVector
100 : : private std::vector< std::pair<K, V>, A >
101 : , private Private::AssocVectorCompare<V, C>
102 : {
103 : typedef std::vector<std::pair<K, V>, A> Base;
104 : typedef Private::AssocVectorCompare<V, C> MyCompare;
105 :
106 : public:
107 : typedef K key_type;
108 : typedef V mapped_type;
109 : typedef typename Base::value_type value_type;
110 :
111 : typedef C key_compare;
112 : typedef A allocator_type;
113 : typedef typename A::reference reference;
114 : typedef typename A::const_reference const_reference;
115 : typedef typename Base::iterator iterator;
116 : typedef typename Base::const_iterator const_iterator;
117 : typedef typename Base::size_type size_type;
118 : typedef typename Base::difference_type difference_type;
119 : typedef typename A::pointer pointer;
120 : typedef typename A::const_pointer const_pointer;
121 : typedef typename Base::reverse_iterator reverse_iterator;
122 : typedef typename Base::const_reverse_iterator const_reverse_iterator;
123 :
124 : class value_compare
125 : : public std::binary_function<value_type, value_type, bool>
126 : , private key_compare
127 : {
128 : friend class AssocVector;
129 :
130 : protected:
131 : value_compare(key_compare pred) : key_compare(pred)
132 : {}
133 :
134 : public:
135 : bool operator()(const value_type& lhs, const value_type& rhs) const
136 : { return key_compare::operator()(lhs.first, rhs.first); }
137 : };
138 :
139 : // 23.3.1.1 construct/copy/destroy
140 :
141 : explicit AssocVector(const key_compare& comp = key_compare(),
142 : const A& alloc = A())
143 : : Base(alloc), MyCompare(comp)
144 : {}
145 :
146 : template <class InputIterator>
147 : AssocVector(InputIterator first, InputIterator last,
148 : const key_compare& comp = key_compare(),
149 : const A& alloc = A())
150 : : Base( alloc ), MyCompare( comp )
151 : {
152 : typedef ::std::vector< ::std::pair< K, V >, A > BaseType;
153 : typedef ::std::map< K, V, C, A > TempMap;
154 : typedef ::std::back_insert_iterator< Base > MyInserter;
155 : MyCompare & me = *this;
156 : const A tempAlloc;
157 : // Make a temporary map similar to this type to prevent any duplicate elements.
158 : TempMap temp( first, last, me, tempAlloc );
159 : Base::reserve( temp.size() );
160 : BaseType & target = static_cast< BaseType & >( *this );
161 : MyInserter myInserter = ::std::back_inserter( target );
162 : ::std::copy( temp.begin(), temp.end(), myInserter );
163 : }
164 :
165 30 : AssocVector& operator=(const AssocVector& rhs)
166 : {
167 30 : AssocVector(rhs).swap(*this);
168 30 : return *this;
169 : }
170 :
171 : // iterators:
172 : // The following are here because MWCW gets 'using' wrong
173 : iterator begin() { return Base::begin(); }
174 : const_iterator begin() const { return Base::begin(); }
175 : iterator end() { return Base::end(); }
176 : const_iterator end() const { return Base::end(); }
177 : reverse_iterator rbegin() { return Base::rbegin(); }
178 : const_reverse_iterator rbegin() const { return Base::rbegin(); }
179 : reverse_iterator rend() { return Base::rend(); }
180 : const_reverse_iterator rend() const { return Base::rend(); }
181 :
182 : // capacity:
183 : bool empty() const { return Base::empty(); }
184 : size_type size() const { return Base::size(); }
185 : size_type max_size() { return Base::max_size(); }
186 :
187 : // 23.3.1.2 element access:
188 1143 : mapped_type& operator[](const key_type& key)
189 1143 : { return insert(value_type(key, mapped_type())).first->second; }
190 :
191 : // modifiers:
192 1143 : std::pair<iterator, bool> insert(const value_type& val)
193 : {
194 : bool found(true);
195 1143 : iterator i(lower_bound(val.first));
196 :
197 13 : if (i == end() || this->operator()(val.first, i->first))
198 : {
199 1134 : i = Base::insert(i, val);
200 : found = false;
201 : }
202 1143 : return std::make_pair(i, !found);
203 : }
204 : //Section [23.1.2], Table 69
205 : //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4
206 : iterator insert(iterator pos, const value_type& val)
207 : {
208 : if( (pos == begin() || this->operator()(*(pos-1),val)) &&
209 : (pos == end() || this->operator()(val, *pos)) )
210 : {
211 : return Base::insert(pos, val);
212 : }
213 : return insert(val).first;
214 : }
215 :
216 : template <class InputIterator>
217 : void insert(InputIterator first, InputIterator last)
218 : { for (; first != last; ++first) insert(*first); }
219 :
220 : void erase(iterator pos)
221 5 : { Base::erase(pos); }
222 :
223 : size_type erase(const key_type& k)
224 : {
225 : iterator i(find(k));
226 : if (i == end()) return 0;
227 : erase(i);
228 : return 1;
229 : }
230 :
231 : void erase(iterator first, iterator last)
232 : { Base::erase(first, last); }
233 :
234 : void swap(AssocVector& other)
235 : {
236 : Base::swap(other);
237 : MyCompare& me = *this;
238 : MyCompare& rhs = other;
239 : std::swap(me, rhs);
240 : }
241 :
242 : void clear()
243 : { Base::clear(); }
244 :
245 : // observers:
246 : key_compare key_comp() const
247 : { return *this; }
248 :
249 : value_compare value_comp() const
250 : {
251 : const key_compare& comp = *this;
252 : return value_compare(comp);
253 : }
254 :
255 : // 23.3.1.3 map operations:
256 5 : iterator find(const key_type& k)
257 : {
258 : iterator i(lower_bound(k));
259 5 : if (i != end() && this->operator()(k, i->first))
260 : {
261 : i = end();
262 : }
263 5 : return i;
264 : }
265 :
266 41 : const_iterator find(const key_type& k) const
267 : {
268 : const_iterator i(lower_bound(k));
269 33 : if (i != end() && this->operator()(k, i->first))
270 : {
271 : i = end();
272 : }
273 41 : return i;
274 : }
275 :
276 : size_type count(const key_type& k) const
277 : { return find(k) != end(); }
278 :
279 : iterator lower_bound(const key_type& k)
280 : {
281 : MyCompare& me = *this;
282 1148 : return std::lower_bound(begin(), end(), k, me);
283 : }
284 :
285 : const_iterator lower_bound(const key_type& k) const
286 : {
287 : const MyCompare& me = *this;
288 41 : return std::lower_bound(begin(), end(), k, me);
289 : }
290 :
291 : iterator upper_bound(const key_type& k)
292 : {
293 : MyCompare& me = *this;
294 : return std::upper_bound(begin(), end(), k, me);
295 : }
296 :
297 : const_iterator upper_bound(const key_type& k) const
298 : {
299 : const MyCompare& me = *this;
300 : return std::upper_bound(begin(), end(), k, me);
301 : }
302 :
303 : std::pair<iterator, iterator> equal_range(const key_type& k)
304 : {
305 : MyCompare& me = *this;
306 : return std::equal_range(begin(), end(), k, me);
307 : }
308 :
309 : std::pair<const_iterator, const_iterator> equal_range(
310 : const key_type& k) const
311 : {
312 : const MyCompare& me = *this;
313 : return std::equal_range(begin(), end(), k, me);
314 : }
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 : bool operator<(const AssocVector& rhs) const
321 : {
322 : const Base& me = *this;
323 : const Base& yo = rhs;
324 : return me < yo;
325 : }
326 :
327 : template <class K1, class V1, class C1, class A1>
328 : friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs,
329 : const AssocVector<K1, V1, C1, A1>& rhs);
330 :
331 : template <class K1, class V1, class C1, class A1>
332 : friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs,
333 : const AssocVector<K1, V1, C1, A1>& rhs);
334 :
335 : template <class K1, class V1, class C1, class A1>
336 : friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs,
337 : const AssocVector<K1, V1, C1, A1>& rhs);
338 :
339 : template <class K1, class V1, class C1, class A1>
340 : friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs,
341 : const AssocVector<K1, V1, C1, A1>& rhs);
342 : };
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 : {
348 : const std::vector<std::pair<K, V>, A>& me = lhs;
349 : return me == rhs;
350 : }
351 :
352 : template <class K, class V, class C, class A>
353 : inline bool operator!=(const AssocVector<K, V, C, A>& lhs,
354 : const AssocVector<K, V, C, A>& rhs)
355 : { return !(lhs == rhs); }
356 :
357 : template <class K, class V, class C, class A>
358 : inline bool operator>(const AssocVector<K, V, C, A>& lhs,
359 : const AssocVector<K, V, C, A>& rhs)
360 : { return rhs < lhs; }
361 :
362 : template <class K, class V, class C, class A>
363 : inline bool operator>=(const AssocVector<K, V, C, A>& lhs,
364 : const AssocVector<K, V, C, A>& rhs)
365 : { return !(lhs < rhs); }
366 :
367 : template <class K, class V, class C, class A>
368 : inline bool operator<=(const AssocVector<K, V, C, A>& lhs,
369 : const AssocVector<K, V, C, A>& rhs)
370 : { return !(rhs < lhs); }
371 :
372 :
373 : // specialized algorithms:
374 : template <class K, class V, class C, class A>
375 : void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
376 : { lhs.swap(rhs); }
377 :
378 : } // namespace Loki
379 :
380 : #endif // end file guardian
381 :
|