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

Archive Download this file

Branches

Tags

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