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, class K>
50 : class AssocVectorCompare : public C
51 : {
52 : typedef K first_argument_type;
53 : typedef std::pair<first_argument_type, Value>
54 : Data;
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 77 : { 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, K>
102 : {
103 : typedef std::vector<std::pair<K, V>, A> Base;
104 : typedef Private::AssocVectorCompare<V, C, K> 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::value_type& reference;
114 : typedef const typename A::value_type* 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::value_type* pointer;
120 : typedef const typename A::value_type* 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 : : private key_compare
126 : {
127 : friend class AssocVector;
128 :
129 : protected:
130 : value_compare(key_compare pred) : key_compare(pred)
131 : {}
132 :
133 : public:
134 : bool operator()(const value_type& lhs, const value_type& rhs) const
135 : { return key_compare::operator()(lhs.first, rhs.first); }
136 : };
137 :
138 : // 23.3.1.1 construct/copy/destroy
139 :
140 : explicit AssocVector(const key_compare& comp = key_compare(),
141 : const A& alloc = A())
142 : : Base(alloc), MyCompare(comp)
143 : {}
144 :
145 : template <class InputIterator>
146 : AssocVector(InputIterator first, InputIterator last,
147 : const key_compare& comp = key_compare(),
148 : const A& alloc = A())
149 : : Base( alloc ), MyCompare( comp )
150 : {
151 : typedef ::std::vector< ::std::pair< K, V >, A > BaseType;
152 : typedef ::std::map< K, V, C, A > TempMap;
153 : typedef ::std::back_insert_iterator< Base > MyInserter;
154 : MyCompare & me = *this;
155 : const A tempAlloc;
156 : // Make a temporary map similar to this type to prevent any duplicate elements.
157 : TempMap temp( first, last, me, tempAlloc );
158 : Base::reserve( temp.size() );
159 : BaseType & target = static_cast< BaseType & >( *this );
160 : MyInserter myInserter = ::std::back_inserter( target );
161 : ::std::copy( temp.begin(), temp.end(), myInserter );
162 : }
163 :
164 30 : AssocVector& operator=(const AssocVector& rhs)
165 : {
166 30 : AssocVector(rhs).swap(*this);
167 30 : return *this;
168 : }
169 :
170 : // iterators:
171 : // The following are here because MWCW gets 'using' wrong
172 : iterator begin() { return Base::begin(); }
173 : const_iterator begin() const { return Base::begin(); }
174 : iterator end() { return Base::end(); }
175 : const_iterator end() const { return Base::end(); }
176 : reverse_iterator rbegin() { return Base::rbegin(); }
177 : const_reverse_iterator rbegin() const { return Base::rbegin(); }
178 : reverse_iterator rend() { return Base::rend(); }
179 : const_reverse_iterator rend() const { return Base::rend(); }
180 :
181 : // capacity:
182 : bool empty() const { return Base::empty(); }
183 : size_type size() const { return Base::size(); }
184 : size_type max_size() { return Base::max_size(); }
185 :
186 : // 23.3.1.2 element access:
187 1145 : mapped_type& operator[](const key_type& key)
188 2290 : { return insert(value_type(key, mapped_type())).first->second; }
189 :
190 : // modifiers:
191 1145 : std::pair<iterator, bool> insert(const value_type& val)
192 : {
193 : bool found(true);
194 1145 : iterator i(lower_bound(val.first));
195 :
196 1145 : if (i == end() || this->operator()(val.first, i->first))
197 : {
198 1132 : i = Base::insert(i, val);
199 : found = false;
200 : }
201 1145 : return std::make_pair(i, !found);
202 : }
203 : //Section [23.1.2], Table 69
204 : //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4
205 : iterator insert(iterator pos, const value_type& val)
206 : {
207 : if( (pos == begin() || this->operator()(*(pos-1),val)) &&
208 : (pos == end() || this->operator()(val, *pos)) )
209 : {
210 : return Base::insert(pos, val);
211 : }
212 : return insert(val).first;
213 : }
214 :
215 : template <class InputIterator>
216 : void insert(InputIterator first, InputIterator last)
217 : { for (; first != last; ++first) insert(*first); }
218 :
219 : void erase(iterator pos)
220 3 : { Base::erase(pos); }
221 :
222 : size_type erase(const key_type& k)
223 : {
224 : iterator i(find(k));
225 : if (i == end()) return 0;
226 : erase(i);
227 : return 1;
228 : }
229 :
230 : void erase(iterator first, iterator last)
231 : { Base::erase(first, last); }
232 :
233 : void swap(AssocVector& other)
234 : {
235 : Base::swap(other);
236 : MyCompare& me = *this;
237 : MyCompare& rhs = other;
238 : std::swap(me, rhs);
239 : }
240 :
241 : void clear()
242 : { Base::clear(); }
243 :
244 : // observers:
245 : key_compare key_comp() const
246 : { return *this; }
247 :
248 : value_compare value_comp() const
249 : {
250 : const key_compare& comp = *this;
251 : return value_compare(comp);
252 : }
253 :
254 : // 23.3.1.3 map operations:
255 3 : iterator find(const key_type& k)
256 : {
257 : iterator i(lower_bound(k));
258 3 : if (i != end() && this->operator()(k, i->first))
259 : {
260 : i = end();
261 : }
262 3 : return i;
263 : }
264 :
265 46 : const_iterator find(const key_type& k) const
266 : {
267 : const_iterator i(lower_bound(k));
268 46 : if (i != end() && this->operator()(k, i->first))
269 : {
270 : i = end();
271 : }
272 46 : return i;
273 : }
274 :
275 : size_type count(const key_type& k) const
276 : { return find(k) != end(); }
277 :
278 : iterator lower_bound(const key_type& k)
279 : {
280 : MyCompare& me = *this;
281 1148 : return std::lower_bound(begin(), end(), k, me);
282 : }
283 :
284 : const_iterator lower_bound(const key_type& k) const
285 : {
286 : const MyCompare& me = *this;
287 46 : return std::lower_bound(begin(), end(), k, me);
288 : }
289 :
290 : iterator upper_bound(const key_type& k)
291 : {
292 : MyCompare& me = *this;
293 : return std::upper_bound(begin(), end(), k, me);
294 : }
295 :
296 : const_iterator upper_bound(const key_type& k) const
297 : {
298 : const MyCompare& me = *this;
299 : return std::upper_bound(begin(), end(), k, me);
300 : }
301 :
302 : std::pair<iterator, iterator> equal_range(const key_type& k)
303 : {
304 : MyCompare& me = *this;
305 : return std::equal_range(begin(), end(), k, me);
306 : }
307 :
308 : std::pair<const_iterator, const_iterator> equal_range(
309 : const key_type& k) const
310 : {
311 : const MyCompare& me = *this;
312 : return std::equal_range(begin(), end(), k, me);
313 : }
314 :
315 : template <class K1, class V1, class C1, class A1>
316 : friend bool operator==(const AssocVector<K1, V1, C1, A1>& lhs,
317 : const AssocVector<K1, V1, C1, A1>& rhs);
318 :
319 : bool operator<(const AssocVector& rhs) const
320 : {
321 : const Base& me = *this;
322 : const Base& yo = rhs;
323 : return me < yo;
324 : }
325 :
326 : template <class K1, class V1, class C1, class A1>
327 : friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs,
328 : const AssocVector<K1, V1, C1, A1>& rhs);
329 :
330 : template <class K1, class V1, class C1, class A1>
331 : friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs,
332 : const AssocVector<K1, V1, C1, A1>& rhs);
333 :
334 : template <class K1, class V1, class C1, class A1>
335 : friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs,
336 : const AssocVector<K1, V1, C1, A1>& rhs);
337 :
338 : template <class K1, class V1, class C1, class A1>
339 : friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs,
340 : const AssocVector<K1, V1, C1, A1>& rhs);
341 : };
342 :
343 : template <class K, class V, class C, class A>
344 : inline bool operator==(const AssocVector<K, V, C, A>& lhs,
345 : const AssocVector<K, V, C, A>& rhs)
346 : {
347 : const std::vector<std::pair<K, V>, A>& me = lhs;
348 : return me == rhs;
349 : }
350 :
351 : template <class K, class V, class C, class A>
352 : inline bool operator!=(const AssocVector<K, V, C, A>& lhs,
353 : const AssocVector<K, V, C, A>& rhs)
354 : { return !(lhs == rhs); }
355 :
356 : template <class K, class V, class C, class A>
357 : inline bool operator>(const AssocVector<K, V, C, A>& lhs,
358 : const AssocVector<K, V, C, A>& rhs)
359 : { return rhs < lhs; }
360 :
361 : template <class K, class V, class C, class A>
362 : inline bool operator>=(const AssocVector<K, V, C, A>& lhs,
363 : const AssocVector<K, V, C, A>& rhs)
364 : { return !(lhs < rhs); }
365 :
366 : template <class K, class V, class C, class A>
367 : inline bool operator<=(const AssocVector<K, V, C, A>& lhs,
368 : const AssocVector<K, V, C, A>& rhs)
369 : { return !(rhs < lhs); }
370 :
371 :
372 : // specialized algorithms:
373 : template <class K, class V, class C, class A>
374 : void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
375 : { lhs.swap(rhs); }
376 :
377 : } // namespace Loki
378 :
379 : #endif // end file guardian
380 :
|
