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

Archive Download this file

Branches

Tags

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