2 * Copyright 2017 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.)
63 #include <initializer_list>
66 #include <type_traits>
70 #include <boost/operators.hpp>
71 #include <folly/portability/BitsFunctexcept.h>
75 //////////////////////////////////////////////////////////////////////
79 // This wrapper goes around a GrowthPolicy and provides iterator
80 // preservation semantics, but only if the growth policy is not the
81 // default (i.e. nothing).
82 template<class Policy>
83 struct growth_policy_wrapper : private Policy {
84 template<class Container, class Iterator>
85 Iterator increase_capacity(Container& c, Iterator desired_insertion)
87 typedef typename Container::difference_type diff_t;
88 diff_t d = desired_insertion - c.begin();
89 Policy::increase_capacity(c);
94 struct growth_policy_wrapper<void> {
95 template<class Container, class Iterator>
96 Iterator increase_capacity(Container&, Iterator it) {
102 * This helper returns the distance between two iterators if it is
103 * possible to figure it out without messing up the range
104 * (i.e. unless they are InputIterators). Otherwise this returns
107 template<class Iterator>
108 int distance_if_multipass(Iterator first, Iterator last) {
109 typedef typename std::iterator_traits<Iterator>::iterator_category categ;
110 if (std::is_same<categ,std::input_iterator_tag>::value)
112 return std::distance(first, last);
115 template<class OurContainer, class Vector, class GrowthPolicy>
116 typename OurContainer::iterator
117 insert_with_hint(OurContainer& sorted,
119 typename OurContainer::iterator hint,
120 typename OurContainer::value_type&& value,
123 const typename OurContainer::value_compare& cmp(sorted.value_comp());
124 if (hint == cont.end() || cmp(value, *hint)) {
125 if (hint == cont.begin()) {
126 po.increase_capacity(cont, cont.begin());
127 return cont.insert(cont.begin(), std::move(value));
129 if (cmp(*(hint - 1), value)) {
130 hint = po.increase_capacity(cont, hint);
131 return cont.insert(hint, std::move(value));
133 return sorted.insert(std::move(value)).first;
136 if (cmp(*hint, value)) {
137 if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
138 typename OurContainer::iterator it =
139 po.increase_capacity(cont, hint + 1);
140 return cont.insert(it, std::move(value));
144 // Value and *hint did not compare, so they are equal keys.
148 template <class OurContainer, class Vector, class InputIterator>
150 OurContainer& sorted,
153 InputIterator last) {
154 // prevent deref of middle where middle == cont.end()
159 auto const& cmp(sorted.value_comp());
161 int const d = distance_if_multipass(first, last);
163 cont.reserve(cont.size() + d);
165 auto const prev_size = cont.size();
167 std::copy(first, last, std::back_inserter(cont));
168 auto const middle = cont.begin() + prev_size;
169 if (!std::is_sorted(middle, cont.end(), cmp)) {
170 std::sort(middle, cont.end(), cmp);
172 if (middle != cont.begin() && cmp(*middle, *(middle - 1))) {
173 std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
178 //////////////////////////////////////////////////////////////////////
181 * A sorted_vector_set is a container similar to std::set<>, but
182 * implemented as as a sorted array with std::vector<>.
184 * @param class T Data type to store
185 * @param class Compare Comparison function that imposes a
186 * strict weak ordering over instances of T
187 * @param class Allocator allocation policy
188 * @param class GrowthPolicy policy object to control growth
190 * @author Aditya Agarwal <aditya@fb.com>
191 * @author Akhil Wable <akhil@fb.com>
192 * @author Jordan DeLong <delong.j@fb.com>
195 class Compare = std::less<T>,
196 class Allocator = std::allocator<T>,
197 class GrowthPolicy = void>
198 class sorted_vector_set
199 : boost::totally_ordered1<
200 sorted_vector_set<T,Compare,Allocator,GrowthPolicy>
201 , detail::growth_policy_wrapper<GrowthPolicy> >
203 typedef std::vector<T,Allocator> ContainerT;
205 detail::growth_policy_wrapper<GrowthPolicy>&
206 get_growth_policy() { return *this; }
209 typedef T value_type;
211 typedef Compare key_compare;
212 typedef Compare value_compare;
214 typedef typename ContainerT::pointer pointer;
215 typedef typename ContainerT::reference reference;
216 typedef typename ContainerT::const_reference const_reference;
218 * XXX: Our normal iterator ought to also be a constant iterator
219 * (cf. Defect Report 103 for std::set), but this is a bit more of a
222 typedef typename ContainerT::iterator iterator;
223 typedef typename ContainerT::const_iterator const_iterator;
224 typedef typename ContainerT::difference_type difference_type;
225 typedef typename ContainerT::size_type size_type;
226 typedef typename ContainerT::reverse_iterator reverse_iterator;
227 typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
229 explicit sorted_vector_set(const Compare& comp = Compare(),
230 const Allocator& alloc = Allocator())
234 template<class InputIterator>
235 explicit sorted_vector_set(
238 const Compare& comp = Compare(),
239 const Allocator& alloc = Allocator())
242 // This is linear if [first, last) is already sorted (and if we
243 // can figure out the distance between the two iterators).
247 /* implicit */ sorted_vector_set(
248 std::initializer_list<value_type> list,
249 const Compare& comp = Compare(),
250 const Allocator& alloc = Allocator())
253 insert(list.begin(), list.end());
256 key_compare key_comp() const { return m_; }
257 value_compare value_comp() const { return m_; }
259 iterator begin() { return m_.cont_.begin(); }
260 iterator end() { return m_.cont_.end(); }
261 const_iterator cbegin() const { return m_.cont_.cbegin(); }
262 const_iterator begin() const { return m_.cont_.begin(); }
263 const_iterator cend() const { return m_.cont_.cend(); }
264 const_iterator end() const { return m_.cont_.end(); }
265 reverse_iterator rbegin() { return m_.cont_.rbegin(); }
266 reverse_iterator rend() { return m_.cont_.rend(); }
267 const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
268 const_reverse_iterator rend() const { return m_.cont_.rend(); }
270 void clear() { return m_.cont_.clear(); }
271 size_type size() const { return m_.cont_.size(); }
272 size_type max_size() const { return m_.cont_.max_size(); }
273 bool empty() const { return m_.cont_.empty(); }
274 void reserve(size_type s) { return m_.cont_.reserve(s); }
275 void shrink_to_fit() { m_.cont_.shrink_to_fit(); }
276 size_type capacity() const { return m_.cont_.capacity(); }
278 std::pair<iterator,bool> insert(const value_type& value) {
279 return insert(std::move(value_type(value)));
282 std::pair<iterator,bool> insert(value_type&& value) {
283 iterator it = lower_bound(value);
284 if (it == end() || value_comp()(value, *it)) {
285 it = get_growth_policy().increase_capacity(m_.cont_, it);
286 return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
288 return std::make_pair(it, false);
291 iterator insert(iterator hint, const value_type& value) {
292 return insert(hint, std::move(value_type(value)));
295 iterator insert(iterator hint, value_type&& value) {
296 return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
297 get_growth_policy());
300 template<class InputIterator>
301 void insert(InputIterator first, InputIterator last) {
302 detail::bulk_insert(*this, m_.cont_, first, last);
305 size_type erase(const key_type& key) {
306 iterator it = find(key);
314 void erase(iterator it) {
318 void erase(iterator first, iterator last) {
319 m_.cont_.erase(first, last);
322 iterator find(const key_type& key) {
323 iterator it = lower_bound(key);
324 if (it == end() || !key_comp()(key, *it))
329 const_iterator find(const key_type& key) const {
330 const_iterator it = lower_bound(key);
331 if (it == end() || !key_comp()(key, *it))
336 size_type count(const key_type& key) const {
337 return find(key) == end() ? 0 : 1;
340 iterator lower_bound(const key_type& key) {
341 return std::lower_bound(begin(), end(), key, key_comp());
344 const_iterator lower_bound(const key_type& key) const {
345 return std::lower_bound(begin(), end(), key, key_comp());
348 iterator upper_bound(const key_type& key) {
349 return std::upper_bound(begin(), end(), key, key_comp());
352 const_iterator upper_bound(const key_type& key) const {
353 return std::upper_bound(begin(), end(), key, key_comp());
356 std::pair<iterator,iterator> equal_range(const key_type& key) {
357 return std::equal_range(begin(), end(), key, key_comp());
360 std::pair<const_iterator,const_iterator>
361 equal_range(const key_type& key) const {
362 return std::equal_range(begin(), end(), key, key_comp());
365 // Nothrow as long as swap() on the Compare type is nothrow.
366 void swap(sorted_vector_set& o) {
367 using std::swap; // Allow ADL for swap(); fall back to std::swap().
371 m_.cont_.swap(o.m_.cont_);
374 bool operator==(const sorted_vector_set& other) const {
375 return other.m_.cont_ == m_.cont_;
378 bool operator<(const sorted_vector_set& other) const {
379 return m_.cont_ < other.m_.cont_;
384 * This structure derives from the comparison object in order to
385 * make use of the empty base class optimization if our comparison
386 * functor is an empty class (usual case).
388 * Wrapping up this member like this is better than deriving from
389 * the Compare object ourselves (there are some perverse edge cases
390 * involving virtual functions).
392 * More info: http://www.cantrip.org/emptyopt.html
394 struct EBO : Compare {
395 explicit EBO(const Compare& c, const Allocator& alloc)
403 // Swap function that can be found using ADL.
404 template<class T, class C, class A, class G>
405 inline void swap(sorted_vector_set<T,C,A,G>& a,
406 sorted_vector_set<T,C,A,G>& b) {
410 //////////////////////////////////////////////////////////////////////
413 * A sorted_vector_map is similar to a sorted_vector_set but stores
414 * <key,value> pairs instead of single elements.
416 * @param class Key Key type
417 * @param class Value Value type
418 * @param class Compare Function that can compare key types and impose
419 * a strict weak ordering over them.
420 * @param class Allocator allocation policy
421 * @param class GrowthPolicy policy object to control growth
423 * @author Aditya Agarwal <aditya@fb.com>
424 * @author Akhil Wable <akhil@fb.com>
425 * @author Jordan DeLong <delong.j@fb.com>
429 class Compare = std::less<Key>,
430 class Allocator = std::allocator<std::pair<Key,Value> >,
431 class GrowthPolicy = void>
432 class sorted_vector_map
433 : boost::totally_ordered1<
434 sorted_vector_map<Key,Value,Compare,Allocator,GrowthPolicy>
435 , detail::growth_policy_wrapper<GrowthPolicy> >
437 typedef std::vector<std::pair<Key,Value>,Allocator> ContainerT;
439 detail::growth_policy_wrapper<GrowthPolicy>&
440 get_growth_policy() { return *this; }
443 typedef Key key_type;
444 typedef Value mapped_type;
445 typedef std::pair<key_type,mapped_type> value_type;
446 typedef Compare key_compare;
448 struct value_compare : private Compare {
449 bool operator()(const value_type& a, const value_type& b) const {
450 return Compare::operator()(a.first, b.first);
454 friend class sorted_vector_map;
455 explicit value_compare(const Compare& c) : Compare(c) {}
458 typedef typename ContainerT::pointer pointer;
459 typedef typename ContainerT::reference reference;
460 typedef typename ContainerT::const_reference const_reference;
461 typedef typename ContainerT::iterator iterator;
462 typedef typename ContainerT::const_iterator const_iterator;
463 typedef typename ContainerT::difference_type difference_type;
464 typedef typename ContainerT::size_type size_type;
465 typedef typename ContainerT::reverse_iterator reverse_iterator;
466 typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
468 explicit sorted_vector_map(const Compare& comp = Compare(),
469 const Allocator& alloc = Allocator())
470 : m_(value_compare(comp), alloc)
473 template<class InputIterator>
474 explicit sorted_vector_map(
477 const Compare& comp = Compare(),
478 const Allocator& alloc = Allocator())
479 : m_(value_compare(comp), alloc)
484 explicit sorted_vector_map(
485 std::initializer_list<value_type> list,
486 const Compare& comp = Compare(),
487 const Allocator& alloc = Allocator())
488 : m_(value_compare(comp), alloc)
490 insert(list.begin(), list.end());
493 key_compare key_comp() const { return m_; }
494 value_compare value_comp() const { return m_; }
496 iterator begin() { return m_.cont_.begin(); }
497 iterator end() { return m_.cont_.end(); }
498 const_iterator cbegin() const { return m_.cont_.cbegin(); }
499 const_iterator begin() const { return m_.cont_.begin(); }
500 const_iterator cend() const { return m_.cont_.cend(); }
501 const_iterator end() const { return m_.cont_.end(); }
502 reverse_iterator rbegin() { return m_.cont_.rbegin(); }
503 reverse_iterator rend() { return m_.cont_.rend(); }
504 const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
505 const_reverse_iterator rend() const { return m_.cont_.rend(); }
507 void clear() { return m_.cont_.clear(); }
508 size_type size() const { return m_.cont_.size(); }
509 size_type max_size() const { return m_.cont_.max_size(); }
510 bool empty() const { return m_.cont_.empty(); }
511 void reserve(size_type s) { return m_.cont_.reserve(s); }
512 void shrink_to_fit() { m_.cont_.shrink_to_fit(); }
513 size_type capacity() const { return m_.cont_.capacity(); }
515 std::pair<iterator,bool> insert(const value_type& value) {
516 return insert(std::move(value_type(value)));
519 std::pair<iterator,bool> insert(value_type&& value) {
520 iterator it = lower_bound(value.first);
521 if (it == end() || value_comp()(value, *it)) {
522 it = get_growth_policy().increase_capacity(m_.cont_, it);
523 return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
525 return std::make_pair(it, false);
528 iterator insert(iterator hint, const value_type& value) {
529 return insert(hint, std::move(value_type(value)));
532 iterator insert(iterator hint, value_type&& value) {
533 return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
534 get_growth_policy());
537 template<class InputIterator>
538 void insert(InputIterator first, InputIterator last) {
539 detail::bulk_insert(*this, m_.cont_, first, last);
542 size_type erase(const key_type& key) {
543 iterator it = find(key);
551 void erase(iterator it) {
555 void erase(iterator first, iterator last) {
556 m_.cont_.erase(first, last);
559 iterator find(const key_type& key) {
560 iterator it = lower_bound(key);
561 if (it == end() || !key_comp()(key, it->first))
566 const_iterator find(const key_type& key) const {
567 const_iterator it = lower_bound(key);
568 if (it == end() || !key_comp()(key, it->first))
573 mapped_type& at(const key_type& key) {
574 iterator it = find(key);
578 std::__throw_out_of_range("sorted_vector_map::at");
581 const mapped_type& at(const key_type& key) const {
582 const_iterator it = find(key);
586 std::__throw_out_of_range("sorted_vector_map::at");
589 size_type count(const key_type& key) const {
590 return find(key) == end() ? 0 : 1;
593 iterator lower_bound(const key_type& key) {
595 auto f = [&](const value_type& a, const key_type& b) {
596 return c(a.first, b);
598 return std::lower_bound(begin(), end(), key, f);
601 const_iterator lower_bound(const key_type& key) const {
603 auto f = [&](const value_type& a, const key_type& b) {
604 return c(a.first, b);
606 return std::lower_bound(begin(), end(), key, f);
609 iterator upper_bound(const key_type& key) {
611 auto f = [&](const key_type& a, const value_type& b) {
612 return c(a, b.first);
614 return std::upper_bound(begin(), end(), key, f);
617 const_iterator upper_bound(const key_type& key) const {
619 auto f = [&](const key_type& a, const value_type& b) {
620 return c(a, b.first);
622 return std::upper_bound(begin(), end(), key, f);
625 std::pair<iterator,iterator> equal_range(const key_type& key) {
626 // Note: std::equal_range can't be passed a functor that takes
627 // argument types different from the iterator value_type, so we
629 iterator low = lower_bound(key);
631 auto f = [&](const key_type& a, const value_type& b) {
632 return c(a, b.first);
634 iterator high = std::upper_bound(low, end(), key, f);
635 return std::make_pair(low, high);
638 std::pair<const_iterator,const_iterator>
639 equal_range(const key_type& key) const {
640 return const_cast<sorted_vector_map*>(this)->equal_range(key);
643 // Nothrow as long as swap() on the Compare type is nothrow.
644 void swap(sorted_vector_map& o) {
645 using std::swap; // Allow ADL for swap(); fall back to std::swap().
649 m_.cont_.swap(o.m_.cont_);
652 mapped_type& operator[](const key_type& key) {
653 iterator it = lower_bound(key);
654 if (it == end() || key_comp()(key, it->first)) {
655 return insert(it, value_type(key, mapped_type()))->second;
660 bool operator==(const sorted_vector_map& other) const {
661 return m_.cont_ == other.m_.cont_;
664 bool operator<(const sorted_vector_map& other) const {
665 return m_.cont_ < other.m_.cont_;
669 // This is to get the empty base optimization; see the comment in
670 // sorted_vector_set.
671 struct EBO : value_compare {
672 explicit EBO(const value_compare& c, const Allocator& alloc)
680 // Swap function that can be found using ADL.
681 template<class K, class V, class C, class A, class G>
682 inline void swap(sorted_vector_map<K,V,C,A,G>& a,
683 sorted_vector_map<K,V,C,A,G>& b) {
687 //////////////////////////////////////////////////////////////////////