Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 607 lines (527 sloc) 20.457 kB
27494a2 @jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
1 /*
2 * Copyright 2012 Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 /*
18 * This header defines two classes that very nearly model
19 * AssociativeContainer (but not quite). These implement set-like and
20 * map-like behavior on top of a sorted vector, instead of using
21 * rb-trees like std::set and std::map.
22 *
23 * This is potentially useful in cases where the number of elements in
24 * the set or map is small, or when you want to avoid using more
25 * memory than necessary and insertions/deletions are much more rare
26 * than lookups (these classes have O(N) insertions/deletions).
27 *
28 * In the interest of using these in conditions where the goal is to
29 * minimize memory usage, they support a GrowthPolicy parameter, which
30 * is a class defining a single function called increase_capacity,
31 * which will be called whenever we are about to insert something: you
32 * can then decide to call reserve() based on the current capacity()
33 * and size() of the passed in vector-esque Container type. An
34 * example growth policy that grows one element at a time:
35 *
36 * struct OneAtATimePolicy {
37 * template<class Container>
38 * void increase_capacity(Container& c) {
39 * if (c.size() == c.capacity()) {
40 * c.reserve(c.size() + 1);
41 * }
42 * }
43 * };
44 *
45 * typedef sorted_vector_set<int,
46 * std::less<int>,
47 * std::allocator<int>,
48 * OneAtATimePolicy>
49 * OneAtATimeIntSet;
50 *
51 * Important differences from std::set and std::map:
52 * - insert() and erase() invalidate iterators and references
53 * - insert() and erase() are O(N)
54 * - our iterators model RandomAccessIterator
55 * - sorted_vector_map::value_type is pair<K,V>, not pair<const K,V>.
56 * (This is basically because we want to store the value_type in
57 * std::vector<>, which requires it to be Assignable.)
58 */
59
60 #ifndef FOLLY_SORTED_VECTOR_TYPES_H_
61 #define FOLLY_SORTED_VECTOR_TYPES_H_
62
63 #include <vector>
64 #include <algorithm>
65 #include <utility>
66 #include <iterator>
67 #include <boost/operators.hpp>
68 #include <boost/bind.hpp>
69 #include <boost/type_traits/is_same.hpp>
70
71 namespace folly {
72
73 //////////////////////////////////////////////////////////////////////
74
75 namespace detail {
76
77 // This wrapper goes around a GrowthPolicy and provides iterator
78 // preservation semantics, but only if the growth policy is not the
79 // default (i.e. nothing).
80 template<class Policy>
81 struct growth_policy_wrapper : private Policy {
82 template<class Container, class Iterator>
83 Iterator increase_capacity(Container& c, Iterator desired_insertion)
84 {
85 typedef typename Container::difference_type diff_t;
86 diff_t d = desired_insertion - c.begin();
87 Policy::increase_capacity(c);
88 return c.begin() + d;
89 }
90 };
91 template<>
92 struct growth_policy_wrapper<void> {
93 template<class Container, class Iterator>
94 Iterator increase_capacity(Container&, Iterator it) {
95 return it;
96 }
97 };
98
99 /*
100 * This helper returns the distance between two iterators if it is
101 * possible to figure it out without messing up the range
102 * (i.e. unless they are InputIterators). Otherwise this returns
103 * -1.
104 */
105 template<class Iterator>
106 int distance_if_multipass(Iterator first, Iterator last) {
107 typedef typename std::iterator_traits<Iterator>::iterator_category categ;
108 if (boost::is_same<categ,std::input_iterator_tag>::value)
109 return -1;
110 return std::distance(first, last);
111 }
112
113 template<class OurContainer, class Vector, class GrowthPolicy>
114 std::pair<typename OurContainer::iterator,bool>
115 insert_with_hint(OurContainer& sorted,
116 Vector& cont,
117 typename OurContainer::iterator hint,
118 typename OurContainer::value_type value,
119 GrowthPolicy& po)
120 {
121 const typename OurContainer::value_compare& cmp(sorted.value_comp());
122 if (hint == cont.end() || cmp(value, *hint)) {
123 if (hint == cont.begin()) {
124 po.increase_capacity(cont, cont.begin());
125 return std::make_pair(cont.insert(cont.begin(), value), true);
126 }
127 if (cmp(*(hint - 1), value)) {
128 hint = po.increase_capacity(cont, hint);
129 return std::make_pair(cont.insert(hint, value), true);
130 }
131 return sorted.insert(value);
132 }
133
134 if (cmp(*hint, value)) {
135 if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
136 typename OurContainer::iterator it =
137 po.increase_capacity(cont, hint + 1);
138 return std::make_pair(cont.insert(it, value), true);
139 }
140 }
141
142 // Value and *hint did not compare, so they are equal keys.
143 return std::make_pair(hint, false);
144 }
145
146 }
147
148 //////////////////////////////////////////////////////////////////////
149
150 /**
151 * A sorted_vector_set is a container similar to std::set<>, but
152 * implemented as as a sorted array with std::vector<>.
153 *
154 * @param class T Data type to store
155 * @param class Compare Comparison function that imposes a
156 * strict weak ordering over instances of T
157 * @param class Allocator allocation policy
158 * @param class GrowthPolicy policy object to control growth
159 *
160 * @author Aditya Agarwal <aditya@fb.com>
161 * @author Akhil Wable <akhil@fb.com>
162 * @author Jordan DeLong <delong.j@fb.com>
163 */
164 template<class T,
165 class Compare = std::less<T>,
166 class Allocator = std::allocator<T>,
167 class GrowthPolicy = void>
168 class sorted_vector_set
169 : boost::totally_ordered1<
170 sorted_vector_set<T,Compare,Allocator,GrowthPolicy>
171 , detail::growth_policy_wrapper<GrowthPolicy> >
172 {
173 typedef std::vector<T,Allocator> ContainerT;
174
175 detail::growth_policy_wrapper<GrowthPolicy>&
176 get_growth_policy() { return *this; }
177
178 public:
179 typedef T value_type;
180 typedef T key_type;
181 typedef Compare key_compare;
182 typedef Compare value_compare;
183
184 typedef typename ContainerT::pointer pointer;
185 typedef typename ContainerT::reference reference;
186 typedef typename ContainerT::const_reference const_reference;
187 /*
188 * XXX: Our normal iterator ought to also be a constant iterator
189 * (cf. Defect Report 103 for std::set), but this is a bit more of a
190 * pain.
191 */
192 typedef typename ContainerT::iterator iterator;
193 typedef typename ContainerT::const_iterator const_iterator;
194 typedef typename ContainerT::difference_type difference_type;
195 typedef typename ContainerT::size_type size_type;
196 typedef typename ContainerT::reverse_iterator reverse_iterator;
197 typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
198
199 explicit sorted_vector_set(const Compare& comp = Compare(),
200 const Allocator& alloc = Allocator())
201 : m_(comp, alloc)
202 {}
203
204 template<class InputIterator>
205 explicit sorted_vector_set(
206 InputIterator first,
207 InputIterator last,
208 const Compare& comp = Compare(),
209 const Allocator& alloc = Allocator())
210 : m_(comp, alloc)
211 {
212 // This is linear if [first, last) is already sorted (and if we
213 // can figure out the distance between the two iterators).
214 insert(first, last);
215 }
216
217 key_compare key_comp() const { return m_; }
218 value_compare value_comp() const { return m_; }
219
220 iterator begin() { return m_.cont_.begin(); }
221 iterator end() { return m_.cont_.end(); }
222 const_iterator begin() const { return m_.cont_.begin(); }
223 const_iterator end() const { return m_.cont_.end(); }
224 reverse_iterator rbegin() { return m_.cont_.rbegin(); }
225 reverse_iterator rend() { return m_.cont_.rend(); }
226 const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
227 const_reverse_iterator rend() const { return m_.cont_.rend(); }
228
229 void clear() { return m_.cont_.clear(); }
230 size_type size() const { return m_.cont_.size(); }
231 size_type max_size() const { return m_.cont_.max_size(); }
232 bool empty() const { return m_.cont_.empty(); }
233 void reserve(size_type s) { return m_.cont_.reserve(s); }
234 size_type capacity() const { return m_.cont_.capacity(); }
235
236 std::pair<iterator,bool> insert(const value_type& value) {
237 iterator it = lower_bound(value);
238 if (it == end() || value_comp()(value, *it)) {
239 it = get_growth_policy().increase_capacity(m_.cont_, it);
240 return std::make_pair(m_.cont_.insert(it, value), true);
241 }
242 return std::make_pair(it, false);
243 }
244
245 std::pair<iterator,bool> insert(iterator hint, const value_type& value) {
246 return detail::insert_with_hint(*this, m_.cont_, hint, value,
247 get_growth_policy());
248 }
249
250 template<class InputIterator>
251 void insert(InputIterator first, InputIterator last) {
252 int d = detail::distance_if_multipass(first, last);
253 if (d != -1) {
254 m_.cont_.reserve(m_.cont_.size() + d);
255 }
256 for (; first != last; ++first) {
257 insert(end(), *first);
258 }
259 }
260
261 size_type erase(const key_type& key) {
262 iterator it = lower_bound(key);
263 if (it == end()) {
264 return 0;
265 }
266 m_.cont_.erase(it);
267 return 1;
268 }
269
270 void erase(iterator it) {
271 m_.cont_.erase(it);
272 }
273
274 void erase(iterator first, iterator last) {
275 m_.cont_.erase(first, last);
276 }
277
278 iterator find(const key_type& key) {
279 iterator it = lower_bound(key);
280 if (it == end() || !key_comp()(key, *it))
281 return it;
282 return end();
283 }
284
285 const_iterator find(const key_type& key) const {
286 const_iterator it = lower_bound(key);
287 if (it == end() || !key_comp()(key, *it))
288 return it;
289 return end();
290 }
291
292 size_type count(const key_type& key) const {
293 return find(key) == end() ? 0 : 1;
294 }
295
296 iterator lower_bound(const key_type& key) {
297 return std::lower_bound(begin(), end(), key, key_comp());
298 }
299
300 const_iterator lower_bound(const key_type& key) const {
301 return std::lower_bound(begin(), end(), key, key_comp());
302 }
303
304 iterator upper_bound(const key_type& key) {
305 return std::upper_bound(begin(), end(), key, key_comp());
306 }
307
308 const_iterator upper_bound(const key_type& key) const {
309 return std::upper_bound(begin(), end(), key, key_comp());
310 }
311
312 std::pair<iterator,iterator> equal_range(const key_type& key) {
313 return std::equal_range(begin(), end(), key, key_comp());
314 }
315
316 std::pair<const_iterator,const_iterator>
317 equal_range(const key_type& key) const {
318 return std::equal_range(begin(), end(), key, key_comp());
319 }
320
321 // Nothrow as long as swap() on the Compare type is nothrow.
322 void swap(sorted_vector_set& o) {
323 using std::swap; // Allow ADL for swap(); fall back to std::swap().
324 Compare& a = m_;
325 Compare& b = o.m_;
326 swap(a, b);
327 m_.cont_.swap(o.m_.cont_);
328 }
329
330 bool operator==(const sorted_vector_set& other) const {
331 return other.m_.cont_ == m_.cont_;
332 }
333
334 bool operator<(const sorted_vector_set& other) const {
335 return m_.cont_ < other.m_.cont_;
336 }
337
338 private:
339 /*
340 * This structure derives from the comparison object in order to
341 * make use of the empty base class optimization if our comparison
342 * functor is an empty class (usual case).
343 *
344 * Wrapping up this member like this is better than deriving from
345 * the Compare object ourselves (there are some perverse edge cases
346 * involving virtual functions).
347 *
348 * More info: http://www.cantrip.org/emptyopt.html
349 */
350 struct EBO : Compare {
351 explicit EBO(const Compare& c, const Allocator& alloc)
352 : Compare(c)
353 , cont_(alloc)
354 {}
355 ContainerT cont_;
356 } m_;
357 };
358
359 // Swap function that can be found using ADL.
360 template<class T, class C, class A, class G>
361 inline void swap(sorted_vector_set<T,C,A,G>& a,
362 sorted_vector_set<T,C,A,G>& b) {
363 return a.swap(b);
364 }
365
366 //////////////////////////////////////////////////////////////////////
367
368 /**
369 * A sorted_vector_map is similar to a sorted_vector_set but stores
370 * <key,value> pairs instead of single elements.
371 *
372 * @param class Key Key type
373 * @param class Value Value type
374 * @param class Compare Function that can compare key types and impose
375 * a strict weak ordering over them.
376 * @param class Allocator allocation policy
377 * @param class GrowthPolicy policy object to control growth
378 *
379 * @author Aditya Agarwal <aditya@fb.com>
380 * @author Akhil Wable <akhil@fb.com>
381 * @author Jordan DeLong <delong.j@fb.com>
382 */
383 template<class Key,
384 class Value,
385 class Compare = std::less<Key>,
386 class Allocator = std::allocator<std::pair<Key,Value> >,
387 class GrowthPolicy = void>
388 class sorted_vector_map
389 : boost::totally_ordered1<
390 sorted_vector_map<Key,Value,Compare,Allocator,GrowthPolicy>
391 , detail::growth_policy_wrapper<GrowthPolicy> >
392 {
393 typedef std::vector<std::pair<Key,Value>,Allocator> ContainerT;
394
395 detail::growth_policy_wrapper<GrowthPolicy>&
396 get_growth_policy() { return *this; }
397
398 public:
399 typedef Key key_type;
400 typedef Value mapped_type;
401 typedef std::pair<key_type,mapped_type> value_type;
402 typedef Compare key_compare;
403
404 struct value_compare
405 : std::binary_function<value_type,value_type,bool>
406 , private Compare
407 {
408 bool operator()(const value_type& a, const value_type& b) const {
409 return Compare::operator()(a.first, b.first);
410 }
411
412 protected:
413 friend class sorted_vector_map;
414 explicit value_compare(const Compare& c) : Compare(c) {}
415 };
416
417 typedef typename ContainerT::pointer pointer;
418 typedef typename ContainerT::reference reference;
419 typedef typename ContainerT::const_reference const_reference;
420 typedef typename ContainerT::iterator iterator;
421 typedef typename ContainerT::const_iterator const_iterator;
422 typedef typename ContainerT::difference_type difference_type;
423 typedef typename ContainerT::size_type size_type;
424 typedef typename ContainerT::reverse_iterator reverse_iterator;
425 typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
426
427 explicit sorted_vector_map(const Compare& comp = Compare(),
428 const Allocator& alloc = Allocator())
429 : m_(value_compare(comp), alloc)
430 {}
431
432 template<class InputIterator>
433 explicit sorted_vector_map(
434 InputIterator first,
435 InputIterator last,
436 const Compare& comp = Compare(),
437 const Allocator& alloc = Allocator())
438 : m_(value_compare(comp), alloc)
439 {
440 insert(first, last);
441 }
442
443 key_compare key_comp() const { return m_; }
444 value_compare value_comp() const { return m_; }
445
446 iterator begin() { return m_.cont_.begin(); }
447 iterator end() { return m_.cont_.end(); }
448 const_iterator begin() const { return m_.cont_.begin(); }
449 const_iterator end() const { return m_.cont_.end(); }
450 reverse_iterator rbegin() { return m_.cont_.rbegin(); }
451 reverse_iterator rend() { return m_.cont_.rend(); }
452 const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
453 const_reverse_iterator rend() const { return m_.cont_.rend(); }
454
455 void clear() { return m_.cont_.clear(); }
456 size_type size() const { return m_.cont_.size(); }
457 size_type max_size() const { return m_.cont_.max_size(); }
458 bool empty() const { return m_.cont_.empty(); }
459 void reserve(size_type s) { return m_.cont_.reserve(s); }
460 size_type capacity() const { return m_.cont_.capacity(); }
461
462 std::pair<iterator,bool> insert(const value_type& value) {
463 iterator it = lower_bound(value.first);
464 if (it == end() || value_comp()(value, *it)) {
465 it = get_growth_policy().increase_capacity(m_.cont_, it);
466 return std::make_pair(m_.cont_.insert(it, value), true);
467 }
468 return std::make_pair(it, false);
469 }
470
471 std::pair<iterator,bool> insert(iterator hint, const value_type& value) {
472 return detail::insert_with_hint(*this, m_.cont_, hint, value,
473 get_growth_policy());
474 }
475
476 template<class InputIterator>
477 void insert(InputIterator first, InputIterator last) {
478 int d = detail::distance_if_multipass(first, last);
479 if (d != -1) {
480 m_.cont_.reserve(m_.cont_.size() + d);
481 }
482 for (; first != last; ++first) {
483 insert(end(), *first);
484 }
485 }
486
487 size_type erase(const key_type& key) {
488 iterator it = find(key);
489 if (it == end()) {
490 return 0;
491 }
492 m_.cont_.erase(it);
493 return 1;
494 }
495
496 void erase(iterator it) {
497 m_.cont_.erase(it);
498 }
499
500 void erase(iterator first, iterator last) {
501 m_.cont_.erase(first, last);
502 }
503
504 iterator find(const key_type& key) {
505 iterator it = lower_bound(key);
506 if (it == end() || !key_comp()(key, it->first))
507 return it;
508 return end();
509 }
510
511 const_iterator find(const key_type& key) const {
512 const_iterator it = lower_bound(key);
513 if (it == end() || !key_comp()(key, it->first))
514 return it;
515 return end();
516 }
517
518 size_type count(const key_type& key) {
519 return find(key) == end() ? 0 : 1;
520 }
521
522 iterator lower_bound(const key_type& key) {
523 return std::lower_bound(begin(), end(), key,
524 boost::bind(key_comp(), boost::bind(&value_type::first, _1), _2));
525 }
526
527 const_iterator lower_bound(const key_type& key) const {
528 return std::lower_bound(begin(), end(), key,
529 boost::bind(key_comp(), boost::bind(&value_type::first, _1), _2));
530 }
531
532 iterator upper_bound(const key_type& key) {
533 return std::upper_bound(begin(), end(), key,
534 boost::bind(key_comp(), _1, boost::bind(&value_type::first, _2)));
535 }
536
537 const_iterator upper_bound(const key_type& key) const {
538 return std::upper_bound(begin(), end(), key,
539 boost::bind(key_comp(), _1, boost::bind(&value_type::first, _2)));
540 }
541
542 std::pair<iterator,iterator> equal_range(const key_type& key) {
543 // Note: std::equal_range can't be passed a functor that takes
544 // argument types different from the iterator value_type, so we
545 // have to do this.
546 iterator low = lower_bound(key);
547 iterator high = std::upper_bound(low, end(), key,
548 boost::bind(key_comp(), _1, boost::bind(&value_type::first, _2)));
549 return std::make_pair(low, high);
550 }
551
552 std::pair<const_iterator,const_iterator>
553 equal_range(const key_type& key) const {
554 return const_cast<sorted_vector_map*>(this)->equal_range(key);
555 }
556
557 // Nothrow as long as swap() on the Compare type is nothrow.
558 void swap(sorted_vector_map& o) {
559 using std::swap; // Allow ADL for swap(); fall back to std::swap().
560 Compare& a = m_;
561 Compare& b = o.m_;
562 swap(a, b);
563 m_.cont_.swap(o.m_.cont_);
564 }
565
566 mapped_type& operator[](const key_type& key) {
567 iterator it = lower_bound(key);
568 if (it == end() || key_comp()(key, it->first)) {
569 return insert(it, value_type(key, mapped_type())).first->second;
570 }
571 return it->second;
572 }
573
574 bool operator==(const sorted_vector_map& other) const {
575 return m_.cont_ == other.m_.cont_;
576 }
577
578 bool operator<(const sorted_vector_map& other) const {
579 return m_.cont_ < other.m_.cont_;
580 }
581
582 private:
583 // This is to get the empty base optimization; see the comment in
584 // sorted_vector_set.
585 struct EBO : value_compare {
586 explicit EBO(const value_compare& c, const Allocator& alloc)
587 : value_compare(c)
588 , cont_(alloc)
589 {}
590 ContainerT cont_;
591 } m_;
592 };
593
594 // Swap function that can be found using ADL.
595 template<class K, class V, class C, class A, class G>
596 inline void swap(sorted_vector_map<K,V,C,A,G>& a,
597 sorted_vector_map<K,V,C,A,G>& b) {
598 return a.swap(b);
599 }
600
601 //////////////////////////////////////////////////////////////////////
602
603 }
604
605 #endif
606
Something went wrong with that request. Please try again.