monotone

monotone Mtn Source Tree

Root/smap.hh

1#ifndef __SMAP_HH__
2#define __SMAP_HH__
3
4// copyright (C) 2005 graydon hoare <graydon@pobox.com>,
5// all rights reserved.
6// licensed to the public under the terms of the GNU GPL (>= 2)
7// see the file COPYING for details
8
9#include <functional>
10#include <numeric>
11#include <vector>
12
13// this is a linear-for-smaller-maps, sorted-binary-search-for-larger maps
14// map. for small key sets which don't change much it's faster than other
15// types of maps. it's a derived version of stl_map.h from libstdc++; I
16// *believe* deriving from its text and upgrading to GPL is kosher.
17
18// FIXME: it is not clear how much of a win this really is; replacing our uses
19// of it with hash_map's in change_set.cc caused an 8% slowdown, but that may
20// have to do with smap using single_client_alloc and hash_map not.
21// Re-evaluate when later gcc automatically uses single_client_alloc when
22// possible...
23
24// We don't use quick_alloc.hh's QA() macro here, because macros don't know
25// about <>'s as grouping mechanisms, so it thinks the "," in the middle of
26// std::pair<K, D> is breaking things into two arguments.
27template<typename K, typename D,
28 typename compare = std::less<K>,
29#if defined(__GNUC__) && __GNUC__ < 3 || (__GNUC__ == 3 && __GNUC_MINOR__ < 4)
30 typename alloc = std::__allocator<std::pair<K, D>, std::__single_client_alloc> >
31#else
32 typename alloc = std::allocator<std::pair<K, D> > >
33#endif
34class
35smap
36{
37public:
38 typedef K key_type;
39 typedef D mapped_type;
40 typedef std::pair<key_type, mapped_type> value_type;
41 typedef compare key_compare;
42
43protected:
44 class value_compare
45 : public std::binary_function<value_type, value_type, bool>
46 {
47 friend class smap<K,D,compare>;
48 protected:
49 compare comp;
50 value_compare(compare c) : comp(c) {}
51
52 public:
53 bool operator()(const value_type & a,
54 const value_type & b) const
55 {
56 return comp(a.first, b.first);
57 }
58 };
59
60 value_compare val_cmp;
61
62 typedef std::vector<value_type> vec_type;
63 mutable vec_type vec;
64 mutable bool damaged;
65
66 inline void
67 ensure_sort() const
68 {
69 if (damaged)
70 {
71 std::sort(vec.begin(), vec.end(), val_cmp);
72 damaged = false;
73 }
74 }
75
76public:
77
78 typedef alloc allocator_type;
79
80 typedef typename alloc::pointer pointer;
81 typedef typename alloc::const_pointer const_pointer;
82
83 typedef typename alloc::reference reference;
84 typedef typename alloc::const_reference const_reference;
85
86 typedef typename vec_type::size_type size_type;
87 typedef typename vec_type::difference_type difference_type;
88
89 typedef typename vec_type::iterator iterator;
90 typedef typename vec_type::const_iterator const_iterator;
91 typedef typename vec_type::reverse_iterator reverse_iterator;
92 typedef typename vec_type::const_reverse_iterator const_reverse_iterator;
93
94 smap()
95 : val_cmp(compare()),
96 damaged(false)
97 { };
98
99 explicit
100 smap(compare const & cmp,
101 alloc const & a = alloc())
102 : val_cmp(cmp),
103 vec(a),
104 damaged(false)
105 { }
106
107 smap(smap const & other)
108 : val_cmp(other.val_cmp),
109 vec(other.vec),
110 damaged(other.damaged)
111 { }
112
113 template <typename InputIterator>
114 smap(InputIterator first, InputIterator last)
115 : damaged(false)
116 {
117 insert(first, last);
118 }
119
120 template <typename InputIterator>
121 smap(InputIterator first, InputIterator last,
122 compare const & cmp,
123 alloc const & a = alloc())
124 : val_cmp(cmp),
125 vec(a),
126 damaged(false)
127 {
128 insert(first, last);
129 }
130
131 smap &
132 operator=(smap const & other)
133 {
134 val_cmp = other.val_cmp;
135 vec = other.vec;
136 damaged = other.damaged;
137 return *this;
138 }
139
140
141 allocator_type get_allocator() const { return vec.get_allocator(); }
142
143 iterator begin() { return vec.begin(); }
144 iterator end() { return vec.end(); }
145 iterator rbegin() { return vec.rbegin(); }
146 iterator rend() { return vec.rend(); }
147
148 const_iterator begin() const { return vec.begin(); }
149 const_iterator end() const { return vec.end(); }
150 const_iterator rbegin() const { return vec.rbegin(); }
151 const_iterator rend() const { return vec.rend(); }
152
153 bool empty() const { return vec.empty(); }
154 size_type size() const { return vec.size(); }
155 size_type max_size() const { return vec.max_size(); }
156
157 mapped_type &
158 operator[](const key_type & k)
159 {
160 iterator i = find(k);
161 if (i != end() && i->first == k)
162 {
163 return i->second;
164 }
165
166 value_type v = std::make_pair(k, mapped_type());
167 if (size() > 0 && val_cmp(v, *(begin() + size() - 1)))
168 {
169 damaged = true;
170 }
171 vec.push_back(v);
172 return v.second;
173 }
174
175 std::pair<iterator, bool>
176 insert(value_type const & v)
177 {
178 iterator i = find(v.first);
179 if (i != end())
180 {
181 return std::make_pair(vec.end(), false);
182 }
183 if (size() > 0 && val_cmp(v, *(begin() + size() - 1)))
184 {
185 damaged = true;
186 }
187 vec.push_back(v);
188 return std::make_pair(begin() + (size() - 1), true);
189 }
190
191 iterator
192 insert(iterator pos, value_type const & v)
193 {
194 iterator i = find(v.first);
195 if (i != end())
196 {
197 return i;
198 }
199 if (size() > 0 && val_cmp(v, *(begin() + size() - 1)))
200 {
201 damaged = true;
202 }
203 vec.push_back(v);
204 return begin() + (size() - 1);
205 }
206
207 template <typename InputIterator>
208 void
209 insert(InputIterator first, InputIterator last)
210 {
211 iterator i = begin();
212 while (first != last)
213 {
214 i = insert(i, *first++);
215 }
216 }
217
218 void
219 erase(iterator i)
220 {
221 vec.erase(i);
222 }
223
224 size_type
225 erase(key_type const & k)
226 {
227 iterator i = find(k);
228 size_type c = 0;
229 while (i != end() && i->first == k)
230 {
231 erase(i);
232 ++c;
233 ++i;
234 }
235 return c;
236 }
237
238 void
239 erase(iterator first, iterator last)
240 {
241 while (first != last)
242 {
243 erase(first++);
244 }
245 }
246
247 void
248 swap(smap & x)
249 {
250 ensure_sort();
251 x.ensure_sort();
252 vec.swap(x.vec);
253 }
254
255 void
256 clear()
257 {
258 vec.clear();
259 damaged = false;
260 }
261
262 key_compare
263 key_comp() const
264 {
265 return val_cmp.comp;
266 }
267
268 value_compare
269 value_comp() const
270 {
271 return val_cmp;
272 }
273
274 iterator
275 find(key_type const & k)
276 {
277 if (size() < 256)
278 {
279 // linear search
280 iterator e = end();
281 for (iterator i = begin(); i != e; ++i)
282 {
283 if (i->first == k)
284 {
285 return i;
286 }
287 }
288 return e;
289 }
290 else
291 {
292 // maybe-sort + binary search
293 iterator i = lower_bound(k);
294 if (i != end() && i->first == k)
295 {
296 return i;
297 }
298 return end();
299 }
300 }
301
302 const_iterator
303 find(key_type const & k) const
304 {
305 if (size() < 256)
306 {
307 // linear search
308 const_iterator e = end();
309 for (const_iterator i = begin(); i != e; ++i)
310 {
311 if (i->first == k)
312 {
313 return i;
314 }
315 }
316 return e;
317 }
318 else
319 {
320 // maybe-sort + binary search
321 const_iterator i = lower_bound(k);
322 if (i != end() && i->first == k)
323 {
324 return i;
325 }
326 return end();
327 }
328 }
329
330 size_type
331 count(key_type const & k) const
332 {
333 return (find(k) == end() ? 0 : 1);
334 }
335
336 iterator
337 lower_bound(key_type const & k)
338 {
339 ensure_sort();
340 value_type v(k, mapped_type());
341 return std::lower_bound(begin(), end(), v, val_cmp);
342 }
343
344 const_iterator
345 lower_bound(key_type const & k) const
346 {
347 ensure_sort();
348 value_type v(k, mapped_type());
349 return std::lower_bound(begin(), end(), v, val_cmp);
350 }
351
352 iterator
353 upper_bound(key_type const & k)
354 {
355 ensure_sort();
356 value_type v(k, mapped_type());
357 return std::upper_bound(begin(), end(), v, val_cmp);
358 }
359
360 const_iterator
361 upper_bound(key_type const & k) const
362 {
363 ensure_sort();
364 value_type v(k, mapped_type());
365 return std::upper_bound(begin(), end(), v, val_cmp);
366 }
367
368 std::pair<iterator, iterator>
369 equal_range(key_type const & k)
370 {
371 ensure_sort();
372 value_type v(k, mapped_type());
373 return std::equal_range(begin(), end(), v, val_cmp);
374 }
375
376 std::pair<const_iterator, const_iterator>
377 equal_range(key_type const & k) const
378 {
379 ensure_sort();
380 value_type v(k, mapped_type());
381 return std::equal_range(begin(), end(), v, val_cmp);
382 }
383
384
385 template <typename K1, typename T1, typename C1, typename A1>
386 friend bool
387 operator== (const smap<K1,T1,C1,A1>&,
388 const smap<K1,T1,C1,A1>&);
389
390 template <typename K1, typename T1, typename C1, typename A1>
391 friend bool
392 operator< (const smap<K1,T1,C1,A1>&,
393 const smap<K1,T1,C1,A1>&);
394
395};
396
397template <typename K, typename D,
398 typename compare,
399 typename alloc>
400inline bool
401operator==(smap<K, D, compare, alloc> const & a,
402 smap<K, D, compare, alloc> const & b)
403{
404 a.ensure_sort();
405 b.ensure_sort();
406 return a.vec == b.vec;
407}
408
409template <typename K, typename D,
410 typename compare,
411 typename alloc>
412inline bool
413operator<(smap<K, D, compare, alloc> const & a,
414 smap<K, D, compare, alloc> const & b)
415{
416 a.ensure_sort();
417 b.ensure_sort();
418 return a.vec < b.vec;
419}
420
421template <typename K, typename D,
422 typename compare,
423 typename alloc>
424inline bool
425operator!=(smap<K, D, compare, alloc> const & a,
426 smap<K, D, compare, alloc> const & b)
427{
428 return !(a == b);
429}
430
431template <typename K, typename D,
432 typename compare,
433 typename alloc>
434inline bool
435operator>(smap<K, D, compare, alloc> const & a,
436 smap<K, D, compare, alloc> const & b)
437{
438 return b < a;
439}
440
441template <typename K, typename D,
442 typename compare,
443 typename alloc>
444inline bool
445operator<=(smap<K, D, compare, alloc> const & a,
446 smap<K, D, compare, alloc> const & b)
447{
448 return !(b < a);
449}
450
451template <typename K, typename D,
452 typename compare,
453 typename alloc>
454inline bool
455operator>=(smap<K, D, compare, alloc> const & a,
456 smap<K, D, compare, alloc> const & b)
457{
458 return !(a < b);
459}
460
461template <typename K, typename D,
462 typename compare,
463 typename alloc>
464inline void
465swap(smap<K, D, compare, alloc> & a,
466 smap<K, D, compare, alloc> & b)
467{
468 a.swap(b);
469}
470
471
472#endif // __SMAP_HH__

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status