2 * Copyright 2014 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
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.
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).
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:
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);
45 * typedef sorted_vector_set<int,
47 * std::allocator<int>,
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.)
60 #ifndef FOLLY_SORTED_VECTOR_TYPES_H_
61 #define FOLLY_SORTED_VECTOR_TYPES_H_
64 #include <initializer_list>
68 #include <boost/operators.hpp>
69 #include <boost/bind.hpp>
70 #include <boost/type_traits/is_same.hpp>
74 //////////////////////////////////////////////////////////////////////
78 // This wrapper goes around a GrowthPolicy and provides iterator
79 // preservation semantics, but only if the growth policy is not the
80 // default (i.e. nothing).
81 template<class Policy>
82 struct growth_policy_wrapper : private Policy {
83 template<class Container, class Iterator>
84 Iterator increase_capacity(Container& c, Iterator desired_insertion)
86 typedef typename Container::difference_type diff_t;
87 diff_t d = desired_insertion - c.begin();
88 Policy::increase_capacity(c);
93 struct growth_policy_wrapper<void> {
94 template<class Container, class Iterator>
95 Iterator increase_capacity(Container&, Iterator it) {
101 * This helper returns the distance between two iterators if it is
102 * possible to figure it out without messing up the range
103 * (i.e. unless they are InputIterators). Otherwise this returns
106 template<class Iterator>
107 int distance_if_multipass(Iterator first, Iterator last) {
108 typedef typename std::iterator_traits<Iterator>::iterator_category categ;
109 if (boost::is_same<categ,std::input_iterator_tag>::value)
111 return std::distance(first, last);
114 template<class OurContainer, class Vector, class GrowthPolicy>
115 std::pair<typename OurContainer::iterator,bool>
116 insert_with_hint(OurContainer& sorted,
118 typename OurContainer::iterator hint,
119 typename OurContainer::value_type value,
122 const typename OurContainer::value_compare& cmp(sorted.value_comp());
123 if (hint == cont.end() || cmp(value, *hint)) {
124 if (hint == cont.begin()) {
125 po.increase_capacity(cont, cont.begin());
126 return std::make_pair(cont.insert(cont.begin(), value), true);
128 if (cmp(*(hint - 1), value)) {
129 hint = po.increase_capacity(cont, hint);
130 return std::make_pair(cont.insert(hint, value), true);
132 return sorted.insert(value);
135 if (cmp(*hint, value)) {
136 if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
137 typename OurContainer::iterator it =
138 po.increase_capacity(cont, hint + 1);
139 return std::make_pair(cont.insert(it, value), true);
143 // Value and *hint did not compare, so they are equal keys.
144 return std::make_pair(hint, false);
149 //////////////////////////////////////////////////////////////////////
152 * A sorted_vector_set is a container similar to std::set<>, but
153 * implemented as as a sorted array with std::vector<>.
155 * @param class T Data type to store
156 * @param class Compare Comparison function that imposes a
157 * strict weak ordering over instances of T
158 * @param class Allocator allocation policy
159 * @param class GrowthPolicy policy object to control growth
161 * @author Aditya Agarwal <aditya@fb.com>
162 * @author Akhil Wable <akhil@fb.com>
163 * @author Jordan DeLong <delong.j@fb.com>
166 class Compare = std::less<T>,
167 class Allocator = std::allocator<T>,
168 class GrowthPolicy = void>
169 class sorted_vector_set
170 : boost::totally_ordered1<
171 sorted_vector_set<T,Compare,Allocator,GrowthPolicy>
172 , detail::growth_policy_wrapper<GrowthPolicy> >
174 typedef std::vector<T,Allocator> ContainerT;
176 detail::growth_policy_wrapper<GrowthPolicy>&
177 get_growth_policy() { return *this; }
180 typedef T value_type;
182 typedef Compare key_compare;
183 typedef Compare value_compare;
185 typedef typename ContainerT::pointer pointer;
186 typedef typename ContainerT::reference reference;
187 typedef typename ContainerT::const_reference const_reference;
189 * XXX: Our normal iterator ought to also be a constant iterator
190 * (cf. Defect Report 103 for std::set), but this is a bit more of a
193 typedef typename ContainerT::iterator iterator;
194 typedef typename ContainerT::const_iterator const_iterator;
195 typedef typename ContainerT::difference_type difference_type;
196 typedef typename ContainerT::size_type size_type;
197 typedef typename ContainerT::reverse_iterator reverse_iterator;
198 typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
200 explicit sorted_vector_set(const Compare& comp = Compare(),
201 const Allocator& alloc = Allocator())
205 template<class InputIterator>
206 explicit sorted_vector_set(
209 const Compare& comp = Compare(),
210 const Allocator& alloc = Allocator())
213 // This is linear if [first, last) is already sorted (and if we
214 // can figure out the distance between the two iterators).
218 explicit sorted_vector_set(
219 std::initializer_list<value_type> list,
220 const Compare& comp = Compare(),
221 const Allocator& alloc = Allocator())
224 insert(list.begin(), list.end());
227 key_compare key_comp() const { return m_; }
228 value_compare value_comp() const { return m_; }
230 iterator begin() { return m_.cont_.begin(); }
231 iterator end() { return m_.cont_.end(); }
232 const_iterator begin() const { return m_.cont_.begin(); }
233 const_iterator end() const { return m_.cont_.end(); }
234 reverse_iterator rbegin() { return m_.cont_.rbegin(); }
235 reverse_iterator rend() { return m_.cont_.rend(); }
236 const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
237 const_reverse_iterator rend() const { return m_.cont_.rend(); }
239 void clear() { return m_.cont_.clear(); }
240 size_type size() const { return m_.cont_.size(); }
241 size_type max_size() const { return m_.cont_.max_size(); }
242 bool empty() const { return m_.cont_.empty(); }
243 void reserve(size_type s) { return m_.cont_.reserve(s); }
244 size_type capacity() const { return m_.cont_.capacity(); }
246 std::pair<iterator,bool> insert(const value_type& value) {
247 iterator it = lower_bound(value);
248 if (it == end() || value_comp()(value, *it)) {
249 it = get_growth_policy().increase_capacity(m_.cont_, it);
250 return std::make_pair(m_.cont_.insert(it, value), true);
252 return std::make_pair(it, false);
255 std::pair<iterator,bool> insert(iterator hint, const value_type& value) {
256 return detail::insert_with_hint(*this, m_.cont_, hint, value,
257 get_growth_policy());
260 template<class InputIterator>
261 void insert(InputIterator first, InputIterator last) {
262 int d = detail::distance_if_multipass(first, last);
264 m_.cont_.reserve(m_.cont_.size() + d);
266 for (; first != last; ++first) {
267 insert(end(), *first);
271 size_type erase(const key_type& key) {
272 iterator it = lower_bound(key);
280 void erase(iterator it) {
284 void erase(iterator first, iterator last) {
285 m_.cont_.erase(first, last);
288 iterator find(const key_type& key) {
289 iterator it = lower_bound(key);
290 if (it == end() || !key_comp()(key, *it))
295 const_iterator find(const key_type& key) const {
296 const_iterator it = lower_bound(key);
297 if (it == end() || !key_comp()(key, *it))
302 size_type count(const key_type& key) const {
303 return find(key) == end() ? 0 : 1;
306 iterator lower_bound(const key_type& key) {
307 return std::lower_bound(begin(), end(), key, key_comp());
310 const_iterator lower_bound(const key_type& key) const {
311 return std::lower_bound(begin(), end(), key, key_comp());
314 iterator upper_bound(const key_type& key) {
315 return std::upper_bound(begin(), end(), key, key_comp());
318 const_iterator upper_bound(const key_type& key) const {
319 return std::upper_bound(begin(), end(), key, key_comp());
322 std::pair<iterator,iterator> equal_range(const key_type& key) {
323 return std::equal_range(begin(), end(), key, key_comp());
326 std::pair<const_iterator,const_iterator>
327 equal_range(const key_type& key) const {
328 return std::equal_range(begin(), end(), key, key_comp());
331 // Nothrow as long as swap() on the Compare type is nothrow.
332 void swap(sorted_vector_set& o) {
333 using std::swap; // Allow ADL for swap(); fall back to std::swap().
337 m_.cont_.swap(o.m_.cont_);
340 bool operator==(const sorted_vector_set& other) const {
341 return other.m_.cont_ == m_.cont_;
344 bool operator<(const sorted_vector_set& other) const {
345 return m_.cont_ < other.m_.cont_;
350 * This structure derives from the comparison object in order to
351 * make use of the empty base class optimization if our comparison
352 * functor is an empty class (usual case).
354 * Wrapping up this member like this is better than deriving from
355 * the Compare object ourselves (there are some perverse edge cases
356 * involving virtual functions).
358 * More info: http://www.cantrip.org/emptyopt.html
360 struct EBO : Compare {
361 explicit EBO(const Compare& c, const Allocator& alloc)
369 // Swap function that can be found using ADL.
370 template<class T, class C, class A, class G>
371 inline void swap(sorted_vector_set<T,C,A,G>& a,
372 sorted_vector_set<T,C,A,G>& b) {
376 //////////////////////////////////////////////////////////////////////
379 * A sorted_vector_map is similar to a sorted_vector_set but stores
380 * <key,value> pairs instead of single elements.
382 * @param class Key Key type
383 * @param class Value Value type
384 * @param class Compare Function that can compare key types and impose
385 * a strict weak ordering over them.
386 * @param class Allocator allocation policy
387 * @param class GrowthPolicy policy object to control growth
389 * @author Aditya Agarwal <aditya@fb.com>
390 * @author Akhil Wable <akhil@fb.com>
391 * @author Jordan DeLong <delong.j@fb.com>
395 class Compare = std::less<Key>,
396 class Allocator = std::allocator<std::pair<Key,Value> >,
397 class GrowthPolicy = void>
398 class sorted_vector_map
399 : boost::totally_ordered1<
400 sorted_vector_map<Key,Value,Compare,Allocator,GrowthPolicy>
401 , detail::growth_policy_wrapper<GrowthPolicy> >
403 typedef std::vector<std::pair<Key,Value>,Allocator> ContainerT;
405 detail::growth_policy_wrapper<GrowthPolicy>&
406 get_growth_policy() { return *this; }
409 typedef Key key_type;
410 typedef Value mapped_type;
411 typedef std::pair<key_type,mapped_type> value_type;
412 typedef Compare key_compare;
415 : std::binary_function<value_type,value_type,bool>
418 bool operator()(const value_type& a, const value_type& b) const {
419 return Compare::operator()(a.first, b.first);
423 friend class sorted_vector_map;
424 explicit value_compare(const Compare& c) : Compare(c) {}
427 typedef typename ContainerT::pointer pointer;
428 typedef typename ContainerT::reference reference;
429 typedef typename ContainerT::const_reference const_reference;
430 typedef typename ContainerT::iterator iterator;
431 typedef typename ContainerT::const_iterator const_iterator;
432 typedef typename ContainerT::difference_type difference_type;
433 typedef typename ContainerT::size_type size_type;
434 typedef typename ContainerT::reverse_iterator reverse_iterator;
435 typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
437 explicit sorted_vector_map(const Compare& comp = Compare(),
438 const Allocator& alloc = Allocator())
439 : m_(value_compare(comp), alloc)
442 template<class InputIterator>
443 explicit sorted_vector_map(
446 const Compare& comp = Compare(),
447 const Allocator& alloc = Allocator())
448 : m_(value_compare(comp), alloc)
453 explicit sorted_vector_map(
454 std::initializer_list<value_type> list,
455 const Compare& comp = Compare(),
456 const Allocator& alloc = Allocator())
457 : m_(value_compare(comp), alloc)
459 insert(list.begin(), list.end());
462 key_compare key_comp() const { return m_; }
463 value_compare value_comp() const { return m_; }
465 iterator begin() { return m_.cont_.begin(); }
466 iterator end() { return m_.cont_.end(); }
467 const_iterator begin() const { return m_.cont_.begin(); }
468 const_iterator end() const { return m_.cont_.end(); }
469 reverse_iterator rbegin() { return m_.cont_.rbegin(); }
470 reverse_iterator rend() { return m_.cont_.rend(); }
471 const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
472 const_reverse_iterator rend() const { return m_.cont_.rend(); }
474 void clear() { return m_.cont_.clear(); }
475 size_type size() const { return m_.cont_.size(); }
476 size_type max_size() const { return m_.cont_.max_size(); }
477 bool empty() const { return m_.cont_.empty(); }
478 void reserve(size_type s) { return m_.cont_.reserve(s); }
479 size_type capacity() const { return m_.cont_.capacity(); }
481 std::pair<iterator,bool> insert(const value_type& value) {
482 iterator it = lower_bound(value.first);
483 if (it == end() || value_comp()(value, *it)) {
484 it = get_growth_policy().increase_capacity(m_.cont_, it);
485 return std::make_pair(m_.cont_.insert(it, value), true);
487 return std::make_pair(it, false);
490 std::pair<iterator,bool> insert(iterator hint, const value_type& value) {
491 return detail::insert_with_hint(*this, m_.cont_, hint, value,
492 get_growth_policy());
495 template<class InputIterator>
496 void insert(InputIterator first, InputIterator last) {
497 int d = detail::distance_if_multipass(first, last);
499 m_.cont_.reserve(m_.cont_.size() + d);
501 for (; first != last; ++first) {
502 insert(end(), *first);
506 size_type erase(const key_type& key) {
507 iterator it = find(key);
515 void erase(iterator it) {
519 void erase(iterator first, iterator last) {
520 m_.cont_.erase(first, last);
523 iterator find(const key_type& key) {
524 iterator it = lower_bound(key);
525 if (it == end() || !key_comp()(key, it->first))
530 const_iterator find(const key_type& key) const {
531 const_iterator it = lower_bound(key);
532 if (it == end() || !key_comp()(key, it->first))
537 size_type count(const key_type& key) const {
538 return find(key) == end() ? 0 : 1;
541 iterator lower_bound(const key_type& key) {
542 return std::lower_bound(begin(), end(), key,
543 boost::bind(key_comp(), boost::bind(&value_type::first, _1), _2));
546 const_iterator lower_bound(const key_type& key) const {
547 return std::lower_bound(begin(), end(), key,
548 boost::bind(key_comp(), boost::bind(&value_type::first, _1), _2));
551 iterator upper_bound(const key_type& key) {
552 return std::upper_bound(begin(), end(), key,
553 boost::bind(key_comp(), _1, boost::bind(&value_type::first, _2)));
556 const_iterator upper_bound(const key_type& key) const {
557 return std::upper_bound(begin(), end(), key,
558 boost::bind(key_comp(), _1, boost::bind(&value_type::first, _2)));
561 std::pair<iterator,iterator> equal_range(const key_type& key) {
562 // Note: std::equal_range can't be passed a functor that takes
563 // argument types different from the iterator value_type, so we
565 iterator low = lower_bound(key);
566 iterator high = std::upper_bound(low, end(), key,
567 boost::bind(key_comp(), _1, boost::bind(&value_type::first, _2)));
568 return std::make_pair(low, high);
571 std::pair<const_iterator,const_iterator>
572 equal_range(const key_type& key) const {
573 return const_cast<sorted_vector_map*>(this)->equal_range(key);
576 // Nothrow as long as swap() on the Compare type is nothrow.
577 void swap(sorted_vector_map& o) {
578 using std::swap; // Allow ADL for swap(); fall back to std::swap().
582 m_.cont_.swap(o.m_.cont_);
585 mapped_type& operator[](const key_type& key) {
586 iterator it = lower_bound(key);
587 if (it == end() || key_comp()(key, it->first)) {
588 return insert(it, value_type(key, mapped_type())).first->second;
593 bool operator==(const sorted_vector_map& other) const {
594 return m_.cont_ == other.m_.cont_;
597 bool operator<(const sorted_vector_map& other) const {
598 return m_.cont_ < other.m_.cont_;
602 // This is to get the empty base optimization; see the comment in
603 // sorted_vector_set.
604 struct EBO : value_compare {
605 explicit EBO(const value_compare& c, const Allocator& alloc)
613 // Swap function that can be found using ADL.
614 template<class K, class V, class C, class A, class G>
615 inline void swap(sorted_vector_map<K,V,C,A,G>& a,
616 sorted_vector_map<K,V,C,A,G>& b) {
621 * Efficiently moves all elements from b into a by taking advantage of sorted
622 * inputs. Any keys that belong to both a and b will have the value from b.
623 * Assumes that C and A can be constructed using the default constructor.
625 * std::merge cannot be used for this use case because in the event of equal
626 * keys belonging to both a and b, it undefined which element will be inserted
627 * into the output map last (and therefore be present in the map).
629 template<class K, class V, class C, class A, class G>
630 inline void merge(sorted_vector_map<K,V,C,A,G>& a,
631 sorted_vector_map<K,V,C,A,G>& b) {
632 auto size = a.size();
633 auto it_a = a.begin();
634 auto it_b = b.begin();
635 while (it_a != a.end() && it_b != b.end()) {
636 auto comp = a.key_comp()(it_a->first, it_b->first);
638 if (!a.key_comp()(it_b->first, it_a->first)) {
649 if (it_b != b.end()) {
650 size += b.end() - it_b;
653 sorted_vector_map<K,V,C,A,G> c;
657 while (it_a != a.end() && it_b != b.end()) {
658 auto comp = a.key_comp()(it_a->first, it_b->first);
660 if (!a.key_comp()(it_b->first, it_a->first)) {
661 c.insert(c.end(), std::move(*it_b));
665 c.insert(c.end(), std::move(*it_b));
669 c.insert(c.end(), std::move(*it_a));
673 while (it_a != a.end()) {
674 c.insert(c.end(), std::move(*it_a));
677 while (it_b != b.end()) {
678 c.insert(c.end(), std::move(*it_b));
685 //////////////////////////////////////////////////////////////////////