2 * Copyright 2011-present 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.)
64 #include <initializer_list>
67 #include <type_traits>
71 #include <boost/operators.hpp>
73 #include <folly/Traits.h>
74 #include <folly/Utility.h>
75 #include <folly/portability/BitsFunctexcept.h>
79 //////////////////////////////////////////////////////////////////////
83 template <typename, typename Compare, typename Key, typename T>
84 struct sorted_vector_enable_if_is_transparent {};
86 template <typename Compare, typename Key, typename T>
87 struct sorted_vector_enable_if_is_transparent<
88 void_t<typename Compare::is_transparent>,
95 // This wrapper goes around a GrowthPolicy and provides iterator
96 // preservation semantics, but only if the growth policy is not the
97 // default (i.e. nothing).
98 template <class Policy>
99 struct growth_policy_wrapper : private Policy {
100 template <class Container, class Iterator>
101 Iterator increase_capacity(Container& c, Iterator desired_insertion) {
102 typedef typename Container::difference_type diff_t;
103 diff_t d = desired_insertion - c.begin();
104 Policy::increase_capacity(c);
105 return c.begin() + d;
109 struct growth_policy_wrapper<void> {
110 template <class Container, class Iterator>
111 Iterator increase_capacity(Container&, Iterator it) {
117 * This helper returns the distance between two iterators if it is
118 * possible to figure it out without messing up the range
119 * (i.e. unless they are InputIterators). Otherwise this returns
122 template <class Iterator>
123 int distance_if_multipass(Iterator first, Iterator last) {
124 typedef typename std::iterator_traits<Iterator>::iterator_category categ;
125 if (std::is_same<categ, std::input_iterator_tag>::value) {
128 return std::distance(first, last);
131 template <class OurContainer, class Vector, class GrowthPolicy>
132 typename OurContainer::iterator insert_with_hint(
133 OurContainer& sorted,
135 typename OurContainer::iterator hint,
136 typename OurContainer::value_type&& value,
138 const typename OurContainer::value_compare& cmp(sorted.value_comp());
139 if (hint == cont.end() || cmp(value, *hint)) {
140 if (hint == cont.begin() || cmp(*(hint - 1), value)) {
141 hint = po.increase_capacity(cont, hint);
142 return cont.insert(hint, std::move(value));
144 return sorted.insert(std::move(value)).first;
148 if (cmp(*hint, value)) {
149 if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
150 hint = po.increase_capacity(cont, hint + 1);
151 return cont.insert(hint, std::move(value));
153 return sorted.insert(std::move(value)).first;
157 // Value and *hint did not compare, so they are equal keys.
161 template <class OurContainer, class Vector, class InputIterator>
163 OurContainer& sorted,
166 InputIterator last) {
167 // prevent deref of middle where middle == cont.end()
172 auto const& cmp(sorted.value_comp());
174 int const d = distance_if_multipass(first, last);
176 cont.reserve(cont.size() + d);
178 auto const prev_size = cont.size();
180 std::copy(first, last, std::back_inserter(cont));
181 auto const middle = cont.begin() + prev_size;
182 if (!std::is_sorted(middle, cont.end(), cmp)) {
183 std::sort(middle, cont.end(), cmp);
185 if (middle != cont.begin() && !cmp(*(middle - 1), *middle)) {
186 std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
191 [&](typename OurContainer::value_type const& a,
192 typename OurContainer::value_type const& b) {
193 return !cmp(a, b) && !cmp(b, a);
199 template <typename Container, typename Compare>
200 Container&& as_sorted(Container&& container, Compare const& comp) {
202 std::sort(begin(container), end(container), comp);
203 return static_cast<Container&&>(container);
205 } // namespace detail
207 //////////////////////////////////////////////////////////////////////
210 * A sorted_vector_set is a container similar to std::set<>, but
211 * implemented as a sorted array with std::vector<>.
213 * @param class T Data type to store
214 * @param class Compare Comparison function that imposes a
215 * strict weak ordering over instances of T
216 * @param class Allocator allocation policy
217 * @param class GrowthPolicy policy object to control growth
219 * @author Aditya Agarwal <aditya@fb.com>
220 * @author Akhil Wable <akhil@fb.com>
221 * @author Jordan DeLong <delong.j@fb.com>
225 class Compare = std::less<T>,
226 class Allocator = std::allocator<T>,
227 class GrowthPolicy = void,
228 class Container = std::vector<T, Allocator>>
229 class sorted_vector_set
230 : boost::totally_ordered1<
231 sorted_vector_set<T, Compare, Allocator, GrowthPolicy>,
232 detail::growth_policy_wrapper<GrowthPolicy>> {
233 detail::growth_policy_wrapper<GrowthPolicy>&
234 get_growth_policy() { return *this; }
236 template <typename K, typename V, typename C = Compare>
237 using if_is_transparent =
238 _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>;
241 typedef T value_type;
243 typedef Compare key_compare;
244 typedef Compare value_compare;
246 typedef typename Container::pointer pointer;
247 typedef typename Container::reference reference;
248 typedef typename Container::const_reference const_reference;
250 * XXX: Our normal iterator ought to also be a constant iterator
251 * (cf. Defect Report 103 for std::set), but this is a bit more of a
254 typedef typename Container::iterator iterator;
255 typedef typename Container::const_iterator const_iterator;
256 typedef typename Container::difference_type difference_type;
257 typedef typename Container::size_type size_type;
258 typedef typename Container::reverse_iterator reverse_iterator;
259 typedef typename Container::const_reverse_iterator const_reverse_iterator;
261 explicit sorted_vector_set(const Compare& comp = Compare(),
262 const Allocator& alloc = Allocator())
266 template <class InputIterator>
267 explicit sorted_vector_set(
270 const Compare& comp = Compare(),
271 const Allocator& alloc = Allocator())
274 // This is linear if [first, last) is already sorted (and if we
275 // can figure out the distance between the two iterators).
279 /* implicit */ sorted_vector_set(
280 std::initializer_list<value_type> list,
281 const Compare& comp = Compare(),
282 const Allocator& alloc = Allocator())
285 insert(list.begin(), list.end());
288 // Construct a sorted_vector_set by stealing the storage of a prefilled
289 // container. The container need not be sorted already. This supports
290 // bulk construction of sorted_vector_set with zero allocations, not counting
291 // those performed by the caller. (The iterator range constructor performs at
292 // least one allocation).
294 // Note that `sorted_vector_set(const Container& container)` is not provided,
295 // since the purpose of this constructor is to avoid an unnecessary copy.
296 explicit sorted_vector_set(
297 Container&& container,
298 const Compare& comp = Compare())
301 detail::as_sorted(std::move(container), comp),
304 // Construct a sorted_vector_set by stealing the storage of a prefilled
305 // container. The container must be sorted, as unsafe_t hints. This supports
306 // bulk construction of sorted_vector_set with zero allocations, not counting
307 // those performed by the caller. (The iterator range constructor performs at
308 // least one allocation).
310 // Note that `sorted_vector_set(unsafe_t, const Container& container)` is not
311 // provided, since the purpose of this constructor is to avoid an unnecessary
315 Container&& container,
316 const Compare& comp = Compare())
317 : m_(comp, container.get_allocator()) {
318 assert(std::is_sorted(container.begin(), container.end(), value_comp()));
319 m_.cont_.swap(container);
322 key_compare key_comp() const { return m_; }
323 value_compare value_comp() const { return m_; }
325 iterator begin() { return m_.cont_.begin(); }
326 iterator end() { return m_.cont_.end(); }
327 const_iterator cbegin() const { return m_.cont_.cbegin(); }
328 const_iterator begin() const { return m_.cont_.begin(); }
329 const_iterator cend() const { return m_.cont_.cend(); }
330 const_iterator end() const { return m_.cont_.end(); }
331 reverse_iterator rbegin() { return m_.cont_.rbegin(); }
332 reverse_iterator rend() { return m_.cont_.rend(); }
333 const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
334 const_reverse_iterator rend() const { return m_.cont_.rend(); }
336 void clear() { return m_.cont_.clear(); }
337 size_type size() const { return m_.cont_.size(); }
338 size_type max_size() const { return m_.cont_.max_size(); }
339 bool empty() const { return m_.cont_.empty(); }
340 void reserve(size_type s) { return m_.cont_.reserve(s); }
341 void shrink_to_fit() { m_.cont_.shrink_to_fit(); }
342 size_type capacity() const { return m_.cont_.capacity(); }
344 std::pair<iterator,bool> insert(const value_type& value) {
345 return insert(std::move(value_type(value)));
348 std::pair<iterator,bool> insert(value_type&& value) {
349 iterator it = lower_bound(value);
350 if (it == end() || value_comp()(value, *it)) {
351 it = get_growth_policy().increase_capacity(m_.cont_, it);
352 return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
354 return std::make_pair(it, false);
357 iterator insert(iterator hint, const value_type& value) {
358 return insert(hint, std::move(value_type(value)));
361 iterator insert(iterator hint, value_type&& value) {
362 return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
363 get_growth_policy());
366 template <class InputIterator>
367 void insert(InputIterator first, InputIterator last) {
368 detail::bulk_insert(*this, m_.cont_, first, last);
371 size_type erase(const key_type& key) {
372 iterator it = find(key);
380 void erase(iterator it) {
384 void erase(iterator first, iterator last) {
385 m_.cont_.erase(first, last);
388 iterator find(const key_type& key) {
389 return find(*this, key);
392 const_iterator find(const key_type& key) const {
393 return find(*this, key);
396 template <typename K>
397 if_is_transparent<K, iterator> find(const K& key) {
398 return find(*this, key);
401 template <typename K>
402 if_is_transparent<K, const_iterator> find(const K& key) const {
403 return find(*this, key);
406 size_type count(const key_type& key) const {
407 return find(key) == end() ? 0 : 1;
410 template <typename K>
411 if_is_transparent<K, size_type> count(const K& key) const {
412 return find(key) == end() ? 0 : 1;
415 iterator lower_bound(const key_type& key) {
416 return std::lower_bound(begin(), end(), key, key_comp());
419 const_iterator lower_bound(const key_type& key) const {
420 return std::lower_bound(begin(), end(), key, key_comp());
423 template <typename K>
424 if_is_transparent<K, iterator> lower_bound(const K& key) {
425 return std::lower_bound(begin(), end(), key, key_comp());
428 template <typename K>
429 if_is_transparent<K, const_iterator> lower_bound(const K& key) const {
430 return std::lower_bound(begin(), end(), key, key_comp());
433 iterator upper_bound(const key_type& key) {
434 return std::upper_bound(begin(), end(), key, key_comp());
437 const_iterator upper_bound(const key_type& key) const {
438 return std::upper_bound(begin(), end(), key, key_comp());
441 template <typename K>
442 if_is_transparent<K, iterator> upper_bound(const K& key) {
443 return std::upper_bound(begin(), end(), key, key_comp());
446 template <typename K>
447 if_is_transparent<K, const_iterator> upper_bound(const K& key) const {
448 return std::upper_bound(begin(), end(), key, key_comp());
451 std::pair<iterator, iterator> equal_range(const key_type& key) {
452 return std::equal_range(begin(), end(), key, key_comp());
455 std::pair<const_iterator, const_iterator> equal_range(
456 const key_type& key) const {
457 return std::equal_range(begin(), end(), key, key_comp());
460 template <typename K>
461 if_is_transparent<K, std::pair<iterator, iterator>> equal_range(
463 return std::equal_range(begin(), end(), key, key_comp());
466 template <typename K>
467 if_is_transparent<K, std::pair<const_iterator, const_iterator>> equal_range(
468 const K& key) const {
469 return std::equal_range(begin(), end(), key, key_comp());
472 // Nothrow as long as swap() on the Compare type is nothrow.
473 void swap(sorted_vector_set& o) {
474 using std::swap; // Allow ADL for swap(); fall back to std::swap().
478 m_.cont_.swap(o.m_.cont_);
481 bool operator==(const sorted_vector_set& other) const {
482 return other.m_.cont_ == m_.cont_;
485 bool operator<(const sorted_vector_set& other) const {
486 return m_.cont_ < other.m_.cont_;
491 * This structure derives from the comparison object in order to
492 * make use of the empty base class optimization if our comparison
493 * functor is an empty class (usual case).
495 * Wrapping up this member like this is better than deriving from
496 * the Compare object ourselves (there are some perverse edge cases
497 * involving virtual functions).
499 * More info: http://www.cantrip.org/emptyopt.html
501 struct EBO : Compare {
502 explicit EBO(const Compare& c, const Allocator& alloc)
509 template <typename Self>
510 using self_iterator_t = _t<
511 std::conditional<std::is_const<Self>::value, const_iterator, iterator>>;
513 template <typename Self, typename K>
514 static self_iterator_t<Self> find(Self& self, K const& key) {
515 auto end = self.end();
516 auto it = self.lower_bound(key);
517 if (it == end || !self.key_comp()(key, *it)) {
524 // Swap function that can be found using ADL.
525 template <class T, class C, class A, class G>
526 inline void swap(sorted_vector_set<T,C,A,G>& a,
527 sorted_vector_set<T,C,A,G>& b) {
531 //////////////////////////////////////////////////////////////////////
534 * A sorted_vector_map is similar to a sorted_vector_set but stores
535 * <key,value> pairs instead of single elements.
537 * @param class Key Key type
538 * @param class Value Value type
539 * @param class Compare Function that can compare key types and impose
540 * a strict weak ordering over them.
541 * @param class Allocator allocation policy
542 * @param class GrowthPolicy policy object to control growth
544 * @author Aditya Agarwal <aditya@fb.com>
545 * @author Akhil Wable <akhil@fb.com>
546 * @author Jordan DeLong <delong.j@fb.com>
551 class Compare = std::less<Key>,
552 class Allocator = std::allocator<std::pair<Key, Value>>,
553 class GrowthPolicy = void,
554 class Container = std::vector<std::pair<Key, Value>, Allocator>>
555 class sorted_vector_map
556 : boost::totally_ordered1<
557 sorted_vector_map<Key, Value, Compare, Allocator, GrowthPolicy>,
558 detail::growth_policy_wrapper<GrowthPolicy>> {
559 detail::growth_policy_wrapper<GrowthPolicy>&
560 get_growth_policy() { return *this; }
562 template <typename K, typename V, typename C = Compare>
563 using if_is_transparent =
564 _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>;
567 typedef Key key_type;
568 typedef Value mapped_type;
569 typedef std::pair<key_type,mapped_type> value_type;
570 typedef Compare key_compare;
572 struct value_compare : private Compare {
573 bool operator()(const value_type& a, const value_type& b) const {
574 return Compare::operator()(a.first, b.first);
578 friend class sorted_vector_map;
579 explicit value_compare(const Compare& c) : Compare(c) {}
582 typedef typename Container::pointer pointer;
583 typedef typename Container::reference reference;
584 typedef typename Container::const_reference const_reference;
585 typedef typename Container::iterator iterator;
586 typedef typename Container::const_iterator const_iterator;
587 typedef typename Container::difference_type difference_type;
588 typedef typename Container::size_type size_type;
589 typedef typename Container::reverse_iterator reverse_iterator;
590 typedef typename Container::const_reverse_iterator const_reverse_iterator;
592 explicit sorted_vector_map(const Compare& comp = Compare(),
593 const Allocator& alloc = Allocator())
594 : m_(value_compare(comp), alloc)
597 template <class InputIterator>
598 explicit sorted_vector_map(
601 const Compare& comp = Compare(),
602 const Allocator& alloc = Allocator())
603 : m_(value_compare(comp), alloc)
608 explicit sorted_vector_map(
609 std::initializer_list<value_type> list,
610 const Compare& comp = Compare(),
611 const Allocator& alloc = Allocator())
612 : m_(value_compare(comp), alloc)
614 insert(list.begin(), list.end());
617 // Construct a sorted_vector_map by stealing the storage of a prefilled
618 // container. The container need not be sorted already. This supports
619 // bulk construction of sorted_vector_map with zero allocations, not counting
620 // those performed by the caller. (The iterator range constructor performs at
621 // least one allocation).
623 // Note that `sorted_vector_map(const Container& container)` is not provided,
624 // since the purpose of this constructor is to avoid an unnecessary copy.
625 explicit sorted_vector_map(
626 Container&& container,
627 const Compare& comp = Compare())
630 detail::as_sorted(std::move(container), value_compare(comp)),
633 // Construct a sorted_vector_map by stealing the storage of a prefilled
634 // container. The container must be sorted, as unsafe_t hints. This supports
635 // bulk construction of sorted_vector_map with zero allocations, not counting
636 // those performed by the caller. (The iterator range constructor performs at
637 // least one allocation).
639 // Note that `sorted_vector_map(unsafe_t, const Container& container)` is not
640 // provided, since the purpose of this constructor is to avoid an unnecessary
644 Container&& container,
645 const Compare& comp = Compare())
646 : m_(value_compare(comp), container.get_allocator()) {
647 assert(std::is_sorted(container.begin(), container.end(), value_comp()));
648 m_.cont_.swap(container);
651 key_compare key_comp() const { return m_; }
652 value_compare value_comp() const { return m_; }
654 iterator begin() { return m_.cont_.begin(); }
655 iterator end() { return m_.cont_.end(); }
656 const_iterator cbegin() const { return m_.cont_.cbegin(); }
657 const_iterator begin() const { return m_.cont_.begin(); }
658 const_iterator cend() const { return m_.cont_.cend(); }
659 const_iterator end() const { return m_.cont_.end(); }
660 reverse_iterator rbegin() { return m_.cont_.rbegin(); }
661 reverse_iterator rend() { return m_.cont_.rend(); }
662 const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
663 const_reverse_iterator rend() const { return m_.cont_.rend(); }
665 void clear() { return m_.cont_.clear(); }
666 size_type size() const { return m_.cont_.size(); }
667 size_type max_size() const { return m_.cont_.max_size(); }
668 bool empty() const { return m_.cont_.empty(); }
669 void reserve(size_type s) { return m_.cont_.reserve(s); }
670 void shrink_to_fit() { m_.cont_.shrink_to_fit(); }
671 size_type capacity() const { return m_.cont_.capacity(); }
673 std::pair<iterator,bool> insert(const value_type& value) {
674 return insert(std::move(value_type(value)));
677 std::pair<iterator,bool> insert(value_type&& value) {
678 iterator it = lower_bound(value.first);
679 if (it == end() || value_comp()(value, *it)) {
680 it = get_growth_policy().increase_capacity(m_.cont_, it);
681 return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
683 return std::make_pair(it, false);
686 iterator insert(iterator hint, const value_type& value) {
687 return insert(hint, std::move(value_type(value)));
690 iterator insert(iterator hint, value_type&& value) {
691 return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
692 get_growth_policy());
695 template <class InputIterator>
696 void insert(InputIterator first, InputIterator last) {
697 detail::bulk_insert(*this, m_.cont_, first, last);
700 size_type erase(const key_type& key) {
701 iterator it = find(key);
709 void erase(iterator it) {
713 void erase(iterator first, iterator last) {
714 m_.cont_.erase(first, last);
717 iterator find(const key_type& key) {
718 return find(*this, key);
721 const_iterator find(const key_type& key) const {
722 return find(*this, key);
725 template <typename K>
726 if_is_transparent<K, iterator> find(const K& key) {
727 return find(*this, key);
730 template <typename K>
731 if_is_transparent<K, const_iterator> find(const K& key) const {
732 return find(*this, key);
735 mapped_type& at(const key_type& key) {
736 iterator it = find(key);
740 std::__throw_out_of_range("sorted_vector_map::at");
743 const mapped_type& at(const key_type& key) const {
744 const_iterator it = find(key);
748 std::__throw_out_of_range("sorted_vector_map::at");
751 size_type count(const key_type& key) const {
752 return find(key) == end() ? 0 : 1;
755 template <typename K>
756 if_is_transparent<K, size_type> count(const K& key) const {
757 return find(key) == end() ? 0 : 1;
760 iterator lower_bound(const key_type& key) {
761 return lower_bound(*this, key);
764 const_iterator lower_bound(const key_type& key) const {
765 return lower_bound(*this, key);
768 template <typename K>
769 if_is_transparent<K, iterator> lower_bound(const K& key) {
770 return lower_bound(*this, key);
773 template <typename K>
774 if_is_transparent<K, const_iterator> lower_bound(const K& key) const {
775 return lower_bound(*this, key);
778 iterator upper_bound(const key_type& key) {
779 return upper_bound(*this, key);
782 const_iterator upper_bound(const key_type& key) const {
783 return upper_bound(*this, key);
786 template <typename K>
787 if_is_transparent<K, iterator> upper_bound(const K& key) {
788 return upper_bound(*this, key);
791 template <typename K>
792 if_is_transparent<K, const_iterator> upper_bound(const K& key) const {
793 return upper_bound(*this, key);
796 std::pair<iterator, iterator> equal_range(const key_type& key) {
797 return equal_range(*this, key);
800 std::pair<const_iterator, const_iterator> equal_range(
801 const key_type& key) const {
802 return equal_range(*this, key);
805 template <typename K>
806 if_is_transparent<K, std::pair<iterator, iterator>> equal_range(
808 return equal_range(*this, key);
811 template <typename K>
812 if_is_transparent<K, std::pair<const_iterator, const_iterator>> equal_range(
813 const K& key) const {
814 return equal_range(*this, key);
817 // Nothrow as long as swap() on the Compare type is nothrow.
818 void swap(sorted_vector_map& o) {
819 using std::swap; // Allow ADL for swap(); fall back to std::swap().
823 m_.cont_.swap(o.m_.cont_);
826 mapped_type& operator[](const key_type& key) {
827 iterator it = lower_bound(key);
828 if (it == end() || key_comp()(key, it->first)) {
829 return insert(it, value_type(key, mapped_type()))->second;
834 bool operator==(const sorted_vector_map& other) const {
835 return m_.cont_ == other.m_.cont_;
838 bool operator<(const sorted_vector_map& other) const {
839 return m_.cont_ < other.m_.cont_;
843 // This is to get the empty base optimization; see the comment in
844 // sorted_vector_set.
845 struct EBO : value_compare {
846 explicit EBO(const value_compare& c, const Allocator& alloc)
853 template <typename Self>
854 using self_iterator_t = _t<
855 std::conditional<std::is_const<Self>::value, const_iterator, iterator>>;
857 template <typename Self, typename K>
858 static self_iterator_t<Self> find(Self& self, K const& key) {
859 auto end = self.end();
860 auto it = self.lower_bound(key);
861 if (it == end || !self.key_comp()(key, it->first)) {
867 template <typename Self, typename K>
868 static self_iterator_t<Self> lower_bound(Self& self, K const& key) {
869 auto f = [c = self.key_comp()](value_type const& a, K const& b) {
870 return c(a.first, b);
872 return std::lower_bound(self.begin(), self.end(), key, f);
875 template <typename Self, typename K>
876 static self_iterator_t<Self> upper_bound(Self& self, K const& key) {
877 auto f = [c = self.key_comp()](K const& a, value_type const& b) {
878 return c(a, b.first);
880 return std::upper_bound(self.begin(), self.end(), key, f);
883 template <typename Self, typename K>
884 static std::pair<self_iterator_t<Self>, self_iterator_t<Self>> equal_range(
887 // Note: std::equal_range can't be passed a functor that takes
888 // argument types different from the iterator value_type, so we
890 return {lower_bound(self, key), upper_bound(self, key)};
894 // Swap function that can be found using ADL.
895 template <class K, class V, class C, class A, class G>
896 inline void swap(sorted_vector_map<K,V,C,A,G>& a,
897 sorted_vector_map<K,V,C,A,G>& b) {
901 //////////////////////////////////////////////////////////////////////