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) {
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 (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 insert_with_hint(
117 OurContainer& sorted,
119 typename OurContainer::iterator hint,
120 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() || cmp(*(hint - 1), value)) {
125 hint = po.increase_capacity(cont, hint);
126 return cont.insert(hint, std::move(value));
128 return sorted.insert(std::move(value)).first;
132 if (cmp(*hint, value)) {
133 if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
134 hint = po.increase_capacity(cont, hint + 1);
135 return cont.insert(hint, std::move(value));
137 return sorted.insert(std::move(value)).first;
141 // Value and *hint did not compare, so they are equal keys.
145 template <class OurContainer, class Vector, class InputIterator>
147 OurContainer& sorted,
150 InputIterator last) {
151 // prevent deref of middle where middle == cont.end()
156 auto const& cmp(sorted.value_comp());
158 int const d = distance_if_multipass(first, last);
160 cont.reserve(cont.size() + d);
162 auto const prev_size = cont.size();
164 std::copy(first, last, std::back_inserter(cont));
165 auto const middle = cont.begin() + prev_size;
166 if (!std::is_sorted(middle, cont.end(), cmp)) {
167 std::sort(middle, cont.end(), cmp);
169 if (middle != cont.begin() && !cmp(*(middle - 1), *middle)) {
170 std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
175 [&](typename OurContainer::value_type const& a,
176 typename OurContainer::value_type const& b) {
177 return !cmp(a, b) && !cmp(b, a);
182 } // namespace detail
184 //////////////////////////////////////////////////////////////////////
187 * A sorted_vector_set is a container similar to std::set<>, but
188 * implemented as as a sorted array with std::vector<>.
190 * @param class T Data type to store
191 * @param class Compare Comparison function that imposes a
192 * strict weak ordering over instances of T
193 * @param class Allocator allocation policy
194 * @param class GrowthPolicy policy object to control growth
196 * @author Aditya Agarwal <aditya@fb.com>
197 * @author Akhil Wable <akhil@fb.com>
198 * @author Jordan DeLong <delong.j@fb.com>
202 class Compare = std::less<T>,
203 class Allocator = std::allocator<T>,
204 class GrowthPolicy = void>
205 class sorted_vector_set
206 : boost::totally_ordered1<
207 sorted_vector_set<T,Compare,Allocator,GrowthPolicy>
208 , detail::growth_policy_wrapper<GrowthPolicy> >
210 typedef std::vector<T,Allocator> ContainerT;
212 detail::growth_policy_wrapper<GrowthPolicy>&
213 get_growth_policy() { return *this; }
216 typedef T value_type;
218 typedef Compare key_compare;
219 typedef Compare value_compare;
221 typedef typename ContainerT::pointer pointer;
222 typedef typename ContainerT::reference reference;
223 typedef typename ContainerT::const_reference const_reference;
225 * XXX: Our normal iterator ought to also be a constant iterator
226 * (cf. Defect Report 103 for std::set), but this is a bit more of a
229 typedef typename ContainerT::iterator iterator;
230 typedef typename ContainerT::const_iterator const_iterator;
231 typedef typename ContainerT::difference_type difference_type;
232 typedef typename ContainerT::size_type size_type;
233 typedef typename ContainerT::reverse_iterator reverse_iterator;
234 typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
236 explicit sorted_vector_set(const Compare& comp = Compare(),
237 const Allocator& alloc = Allocator())
241 template <class InputIterator>
242 explicit sorted_vector_set(
245 const Compare& comp = Compare(),
246 const Allocator& alloc = Allocator())
249 // This is linear if [first, last) is already sorted (and if we
250 // can figure out the distance between the two iterators).
254 /* implicit */ sorted_vector_set(
255 std::initializer_list<value_type> list,
256 const Compare& comp = Compare(),
257 const Allocator& alloc = Allocator())
260 insert(list.begin(), list.end());
263 // Construct a sorted_vector_set by stealing the storage of a prefilled
264 // container. The container need not be sorted already. This supports
265 // bulk construction of sorted_vector_set with zero allocations, not counting
266 // those performed by the caller. (The iterator range constructor performs at
267 // least one allocation).
269 // Note that `sorted_vector_set(const ContainerT& container)` is not provided,
270 // since the purpose of this constructor is to avoid an unnecessary copy.
271 explicit sorted_vector_set(
272 ContainerT&& container,
273 const Compare& comp = Compare())
274 : m_(comp, container.get_allocator()) {
275 std::sort(container.begin(), container.end(), value_comp());
276 m_.cont_.swap(container);
279 key_compare key_comp() const { return m_; }
280 value_compare value_comp() const { return m_; }
282 iterator begin() { return m_.cont_.begin(); }
283 iterator end() { return m_.cont_.end(); }
284 const_iterator cbegin() const { return m_.cont_.cbegin(); }
285 const_iterator begin() const { return m_.cont_.begin(); }
286 const_iterator cend() const { return m_.cont_.cend(); }
287 const_iterator end() const { return m_.cont_.end(); }
288 reverse_iterator rbegin() { return m_.cont_.rbegin(); }
289 reverse_iterator rend() { return m_.cont_.rend(); }
290 const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
291 const_reverse_iterator rend() const { return m_.cont_.rend(); }
293 void clear() { return m_.cont_.clear(); }
294 size_type size() const { return m_.cont_.size(); }
295 size_type max_size() const { return m_.cont_.max_size(); }
296 bool empty() const { return m_.cont_.empty(); }
297 void reserve(size_type s) { return m_.cont_.reserve(s); }
298 void shrink_to_fit() { m_.cont_.shrink_to_fit(); }
299 size_type capacity() const { return m_.cont_.capacity(); }
301 std::pair<iterator,bool> insert(const value_type& value) {
302 return insert(std::move(value_type(value)));
305 std::pair<iterator,bool> insert(value_type&& value) {
306 iterator it = lower_bound(value);
307 if (it == end() || value_comp()(value, *it)) {
308 it = get_growth_policy().increase_capacity(m_.cont_, it);
309 return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
311 return std::make_pair(it, false);
314 iterator insert(iterator hint, const value_type& value) {
315 return insert(hint, std::move(value_type(value)));
318 iterator insert(iterator hint, value_type&& value) {
319 return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
320 get_growth_policy());
323 template <class InputIterator>
324 void insert(InputIterator first, InputIterator last) {
325 detail::bulk_insert(*this, m_.cont_, first, last);
328 size_type erase(const key_type& key) {
329 iterator it = find(key);
337 void erase(iterator it) {
341 void erase(iterator first, iterator last) {
342 m_.cont_.erase(first, last);
345 iterator find(const key_type& key) {
346 iterator it = lower_bound(key);
347 if (it == end() || !key_comp()(key, *it)) {
353 const_iterator find(const key_type& key) const {
354 const_iterator it = lower_bound(key);
355 if (it == end() || !key_comp()(key, *it)) {
361 size_type count(const key_type& key) const {
362 return find(key) == end() ? 0 : 1;
365 iterator lower_bound(const key_type& key) {
366 return std::lower_bound(begin(), end(), key, key_comp());
369 const_iterator lower_bound(const key_type& key) const {
370 return std::lower_bound(begin(), end(), key, key_comp());
373 iterator upper_bound(const key_type& key) {
374 return std::upper_bound(begin(), end(), key, key_comp());
377 const_iterator upper_bound(const key_type& key) const {
378 return std::upper_bound(begin(), end(), key, key_comp());
381 std::pair<iterator,iterator> equal_range(const key_type& key) {
382 return std::equal_range(begin(), end(), key, key_comp());
385 std::pair<const_iterator,const_iterator>
386 equal_range(const key_type& key) const {
387 return std::equal_range(begin(), end(), key, key_comp());
390 // Nothrow as long as swap() on the Compare type is nothrow.
391 void swap(sorted_vector_set& o) {
392 using std::swap; // Allow ADL for swap(); fall back to std::swap().
396 m_.cont_.swap(o.m_.cont_);
399 bool operator==(const sorted_vector_set& other) const {
400 return other.m_.cont_ == m_.cont_;
403 bool operator<(const sorted_vector_set& other) const {
404 return m_.cont_ < other.m_.cont_;
409 * This structure derives from the comparison object in order to
410 * make use of the empty base class optimization if our comparison
411 * functor is an empty class (usual case).
413 * Wrapping up this member like this is better than deriving from
414 * the Compare object ourselves (there are some perverse edge cases
415 * involving virtual functions).
417 * More info: http://www.cantrip.org/emptyopt.html
419 struct EBO : Compare {
420 explicit EBO(const Compare& c, const Allocator& alloc)
428 // Swap function that can be found using ADL.
429 template <class T, class C, class A, class G>
430 inline void swap(sorted_vector_set<T,C,A,G>& a,
431 sorted_vector_set<T,C,A,G>& b) {
435 //////////////////////////////////////////////////////////////////////
438 * A sorted_vector_map is similar to a sorted_vector_set but stores
439 * <key,value> pairs instead of single elements.
441 * @param class Key Key type
442 * @param class Value Value type
443 * @param class Compare Function that can compare key types and impose
444 * a strict weak ordering over them.
445 * @param class Allocator allocation policy
446 * @param class GrowthPolicy policy object to control growth
448 * @author Aditya Agarwal <aditya@fb.com>
449 * @author Akhil Wable <akhil@fb.com>
450 * @author Jordan DeLong <delong.j@fb.com>
455 class Compare = std::less<Key>,
456 class Allocator = std::allocator<std::pair<Key, Value>>,
457 class GrowthPolicy = void>
458 class sorted_vector_map
459 : boost::totally_ordered1<
460 sorted_vector_map<Key,Value,Compare,Allocator,GrowthPolicy>
461 , detail::growth_policy_wrapper<GrowthPolicy> >
463 typedef std::vector<std::pair<Key,Value>,Allocator> ContainerT;
465 detail::growth_policy_wrapper<GrowthPolicy>&
466 get_growth_policy() { return *this; }
469 typedef Key key_type;
470 typedef Value mapped_type;
471 typedef std::pair<key_type,mapped_type> value_type;
472 typedef Compare key_compare;
474 struct value_compare : private Compare {
475 bool operator()(const value_type& a, const value_type& b) const {
476 return Compare::operator()(a.first, b.first);
480 friend class sorted_vector_map;
481 explicit value_compare(const Compare& c) : Compare(c) {}
484 typedef typename ContainerT::pointer pointer;
485 typedef typename ContainerT::reference reference;
486 typedef typename ContainerT::const_reference const_reference;
487 typedef typename ContainerT::iterator iterator;
488 typedef typename ContainerT::const_iterator const_iterator;
489 typedef typename ContainerT::difference_type difference_type;
490 typedef typename ContainerT::size_type size_type;
491 typedef typename ContainerT::reverse_iterator reverse_iterator;
492 typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
494 explicit sorted_vector_map(const Compare& comp = Compare(),
495 const Allocator& alloc = Allocator())
496 : m_(value_compare(comp), alloc)
499 template <class InputIterator>
500 explicit sorted_vector_map(
503 const Compare& comp = Compare(),
504 const Allocator& alloc = Allocator())
505 : m_(value_compare(comp), alloc)
510 explicit sorted_vector_map(
511 std::initializer_list<value_type> list,
512 const Compare& comp = Compare(),
513 const Allocator& alloc = Allocator())
514 : m_(value_compare(comp), alloc)
516 insert(list.begin(), list.end());
519 // Construct a sorted_vector_map by stealing the storage of a prefilled
520 // container. The container need not be sorted already. This supports
521 // bulk construction of sorted_vector_map with zero allocations, not counting
522 // those performed by the caller. (The iterator range constructor performs at
523 // least one allocation).
525 // Note that `sorted_vector_map(const ContainerT& container)` is not provided,
526 // since the purpose of this constructor is to avoid an unnecessary copy.
527 explicit sorted_vector_map(
528 ContainerT&& container,
529 const Compare& comp = Compare())
530 : m_(value_compare(comp), container.get_allocator()) {
531 std::sort(container.begin(), container.end(), value_comp());
532 m_.cont_.swap(container);
535 key_compare key_comp() const { return m_; }
536 value_compare value_comp() const { return m_; }
538 iterator begin() { return m_.cont_.begin(); }
539 iterator end() { return m_.cont_.end(); }
540 const_iterator cbegin() const { return m_.cont_.cbegin(); }
541 const_iterator begin() const { return m_.cont_.begin(); }
542 const_iterator cend() const { return m_.cont_.cend(); }
543 const_iterator end() const { return m_.cont_.end(); }
544 reverse_iterator rbegin() { return m_.cont_.rbegin(); }
545 reverse_iterator rend() { return m_.cont_.rend(); }
546 const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
547 const_reverse_iterator rend() const { return m_.cont_.rend(); }
549 void clear() { return m_.cont_.clear(); }
550 size_type size() const { return m_.cont_.size(); }
551 size_type max_size() const { return m_.cont_.max_size(); }
552 bool empty() const { return m_.cont_.empty(); }
553 void reserve(size_type s) { return m_.cont_.reserve(s); }
554 void shrink_to_fit() { m_.cont_.shrink_to_fit(); }
555 size_type capacity() const { return m_.cont_.capacity(); }
557 std::pair<iterator,bool> insert(const value_type& value) {
558 return insert(std::move(value_type(value)));
561 std::pair<iterator,bool> insert(value_type&& value) {
562 iterator it = lower_bound(value.first);
563 if (it == end() || value_comp()(value, *it)) {
564 it = get_growth_policy().increase_capacity(m_.cont_, it);
565 return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
567 return std::make_pair(it, false);
570 iterator insert(iterator hint, const value_type& value) {
571 return insert(hint, std::move(value_type(value)));
574 iterator insert(iterator hint, value_type&& value) {
575 return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
576 get_growth_policy());
579 template <class InputIterator>
580 void insert(InputIterator first, InputIterator last) {
581 detail::bulk_insert(*this, m_.cont_, first, last);
584 size_type erase(const key_type& key) {
585 iterator it = find(key);
593 void erase(iterator it) {
597 void erase(iterator first, iterator last) {
598 m_.cont_.erase(first, last);
601 iterator find(const key_type& key) {
602 iterator it = lower_bound(key);
603 if (it == end() || !key_comp()(key, it->first)) {
609 const_iterator find(const key_type& key) const {
610 const_iterator it = lower_bound(key);
611 if (it == end() || !key_comp()(key, it->first)) {
617 mapped_type& at(const key_type& key) {
618 iterator it = find(key);
622 std::__throw_out_of_range("sorted_vector_map::at");
625 const mapped_type& at(const key_type& key) const {
626 const_iterator it = find(key);
630 std::__throw_out_of_range("sorted_vector_map::at");
633 size_type count(const key_type& key) const {
634 return find(key) == end() ? 0 : 1;
637 iterator lower_bound(const key_type& key) {
639 auto f = [&](const value_type& a, const key_type& b) {
640 return c(a.first, b);
642 return std::lower_bound(begin(), end(), key, f);
645 const_iterator lower_bound(const key_type& key) const {
647 auto f = [&](const value_type& a, const key_type& b) {
648 return c(a.first, b);
650 return std::lower_bound(begin(), end(), key, f);
653 iterator upper_bound(const key_type& key) {
655 auto f = [&](const key_type& a, const value_type& b) {
656 return c(a, b.first);
658 return std::upper_bound(begin(), end(), key, f);
661 const_iterator upper_bound(const key_type& key) const {
663 auto f = [&](const key_type& a, const value_type& b) {
664 return c(a, b.first);
666 return std::upper_bound(begin(), end(), key, f);
669 std::pair<iterator,iterator> equal_range(const key_type& key) {
670 // Note: std::equal_range can't be passed a functor that takes
671 // argument types different from the iterator value_type, so we
673 iterator low = lower_bound(key);
675 auto f = [&](const key_type& a, const value_type& b) {
676 return c(a, b.first);
678 iterator high = std::upper_bound(low, end(), key, f);
679 return std::make_pair(low, high);
682 std::pair<const_iterator,const_iterator>
683 equal_range(const key_type& key) const {
684 return const_cast<sorted_vector_map*>(this)->equal_range(key);
687 // Nothrow as long as swap() on the Compare type is nothrow.
688 void swap(sorted_vector_map& o) {
689 using std::swap; // Allow ADL for swap(); fall back to std::swap().
693 m_.cont_.swap(o.m_.cont_);
696 mapped_type& operator[](const key_type& key) {
697 iterator it = lower_bound(key);
698 if (it == end() || key_comp()(key, it->first)) {
699 return insert(it, value_type(key, mapped_type()))->second;
704 bool operator==(const sorted_vector_map& other) const {
705 return m_.cont_ == other.m_.cont_;
708 bool operator<(const sorted_vector_map& other) const {
709 return m_.cont_ < other.m_.cont_;
713 // This is to get the empty base optimization; see the comment in
714 // sorted_vector_set.
715 struct EBO : value_compare {
716 explicit EBO(const value_compare& c, const Allocator& alloc)
724 // Swap function that can be found using ADL.
725 template <class K, class V, class C, class A, class G>
726 inline void swap(sorted_vector_map<K,V,C,A,G>& a,
727 sorted_vector_map<K,V,C,A,G>& b) {
731 //////////////////////////////////////////////////////////////////////