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

Archive Download this file

Branches

Tags

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