1/*
2 * Copyright 2011-present 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 erase(iterator) returns an iterator pointing to the next valid element.
54 * - insert() and erase() are O(N)
55 * - our iterators model RandomAccessIterator
56 * - sorted_vector_map::value_type is pair<K,V>, not pair<const K,V>.
57 * (This is basically because we want to store the value_type in
58 * std::vector<>, which requires it to be Assignable.)
59 */
60
61#pragma once
62
63#include <algorithm>
64#include <cassert>
65#include <initializer_list>
66#include <iterator>
67#include <stdexcept>
68#include <type_traits>
69#include <utility>
70#include <vector>
71
72#include <folly/Traits.h>
73#include <folly/Utility.h>
74#include <folly/lang/Exception.h>
75
76namespace folly {
77
78//////////////////////////////////////////////////////////////////////
79
80namespace detail {
81
82template <typename, typename Compare, typename Key, typename T>
83struct sorted_vector_enable_if_is_transparent {};
84
85template <typename Compare, typename Key, typename T>
86struct sorted_vector_enable_if_is_transparent<
87 void_t<typename Compare::is_transparent>,
88 Compare,
89 Key,
90 T> {
91 using type = T;
92};
93
94// This wrapper goes around a GrowthPolicy and provides iterator
95// preservation semantics, but only if the growth policy is not the
96// default (i.e. nothing).
97template <class Policy>
98struct growth_policy_wrapper : private Policy {
99 template <class Container, class Iterator>
100 Iterator increase_capacity(Container& c, Iterator desired_insertion) {
101 typedef typename Container::difference_type diff_t;
102 diff_t d = desired_insertion - c.begin();
103 Policy::increase_capacity(c);
104 return c.begin() + d;
105 }
106};
107template <>
108struct growth_policy_wrapper<void> {
109 template <class Container, class Iterator>
110 Iterator increase_capacity(Container&, Iterator it) {
111 return it;
112 }
113};
114
115/*
116 * This helper returns the distance between two iterators if it is
117 * possible to figure it out without messing up the range
118 * (i.e. unless they are InputIterators). Otherwise this returns
119 * -1.
120 */
121template <class Iterator>
122int distance_if_multipass(Iterator first, Iterator last) {
123 typedef typename std::iterator_traits<Iterator>::iterator_category categ;
124 if (std::is_same<categ, std::input_iterator_tag>::value) {
125 return -1;
126 }
127 return std::distance(first, last);
128}
129
130template <class OurContainer, class Vector, class GrowthPolicy>
131typename OurContainer::iterator insert_with_hint(
132 OurContainer& sorted,
133 Vector& cont,
134 typename OurContainer::iterator hint,
135 typename OurContainer::value_type&& value,
136 GrowthPolicy& po) {
137 const typename OurContainer::value_compare& cmp(sorted.value_comp());
138 if (hint == cont.end() || cmp(value, *hint)) {
139 if (hint == cont.begin() || cmp(*(hint - 1), value)) {
140 hint = po.increase_capacity(cont, hint);
141 return cont.insert(hint, std::move(value));
142 } else {
143 return sorted.insert(std::move(value)).first;
144 }
145 }
146
147 if (cmp(*hint, value)) {
148 if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
149 hint = po.increase_capacity(cont, hint + 1);
150 return cont.insert(hint, std::move(value));
151 } else {
152 return sorted.insert(std::move(value)).first;
153 }
154 }
155
156 // Value and *hint did not compare, so they are equal keys.
157 return hint;
158}
159
160template <class OurContainer, class Vector, class InputIterator>
161void bulk_insert(
162 OurContainer& sorted,
163 Vector& cont,
164 InputIterator first,
165 InputIterator last) {
166 // prevent deref of middle where middle == cont.end()
167 if (first == last) {
168 return;
169 }
170
171 auto const& cmp(sorted.value_comp());
172
173 int const d = distance_if_multipass(first, last);
174 if (d != -1) {
175 cont.reserve(cont.size() + d);
176 }
177 auto const prev_size = cont.size();
178
179 std::copy(first, last, std::back_inserter(cont));
180 auto const middle = cont.begin() + prev_size;
181 if (!std::is_sorted(middle, cont.end(), cmp)) {
182 std::sort(middle, cont.end(), cmp);
183 }
184 if (middle != cont.begin() && !cmp(*(middle - 1), *middle)) {
185 std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
186 }
187 cont.erase(
188 std::unique(
189 cont.begin(),
190 cont.end(),
191 [&](typename OurContainer::value_type const& a,
192 typename OurContainer::value_type const& b) {
193 return !cmp(a, b) && !cmp(b, a);
194 }),
195 cont.end());
196}
197
198template <typename Container, typename Compare>
199Container&& as_sorted(Container&& container, Compare const& comp) {
200 using namespace std;
201 std::sort(begin(container), end(container), comp);
202 return static_cast<Container&&>(container);
203}
204} // namespace detail
205
206//////////////////////////////////////////////////////////////////////
207
208/**
209 * A sorted_vector_set is a container similar to std::set<>, but
210 * implemented as a sorted array with std::vector<>.
211 *
212 * @param class T Data type to store
213 * @param class Compare Comparison function that imposes a
214 * strict weak ordering over instances of T
215 * @param class Allocator allocation policy
216 * @param class GrowthPolicy policy object to control growth
217 *
218 * @author Aditya Agarwal <aditya@fb.com>
219 * @author Akhil Wable <akhil@fb.com>
220 * @author Jordan DeLong <delong.j@fb.com>
221 */
222template <
223 class T,
224 class Compare = std::less<T>,
225 class Allocator = std::allocator<T>,
226 class GrowthPolicy = void,
227 class Container = std::vector<T, Allocator>>
228class sorted_vector_set : detail::growth_policy_wrapper<GrowthPolicy> {
229 detail::growth_policy_wrapper<GrowthPolicy>& get_growth_policy() {
230 return *this;
231 }
232
233 template <typename K, typename V, typename C = Compare>
234 using if_is_transparent =
235 _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>;
236
237 public:
238 typedef T value_type;
239 typedef T key_type;
240 typedef Compare key_compare;
241 typedef Compare value_compare;
242 typedef Allocator allocator_type;
243
244 typedef typename Container::pointer pointer;
245 typedef typename Container::reference reference;
246 typedef typename Container::const_reference const_reference;
247 /*
248 * XXX: Our normal iterator ought to also be a constant iterator
249 * (cf. Defect Report 103 for std::set), but this is a bit more of a
250 * pain.
251 */
252 typedef typename Container::iterator iterator;
253 typedef typename Container::const_iterator const_iterator;
254 typedef typename Container::difference_type difference_type;
255 typedef typename Container::size_type size_type;
256 typedef typename Container::reverse_iterator reverse_iterator;
257 typedef typename Container::const_reverse_iterator const_reverse_iterator;
258
259 sorted_vector_set() : m_(Compare(), Allocator()) {}
260
261 explicit sorted_vector_set(
262 const Compare& comp,
263 const Allocator& alloc = Allocator())
264 : m_(comp, alloc) {}
265
266 template <class InputIterator>
267 explicit sorted_vector_set(
268 InputIterator first,
269 InputIterator last,
270 const Compare& comp = Compare(),
271 const Allocator& alloc = Allocator())
272 : m_(comp, alloc) {
273 // This is linear if [first, last) is already sorted (and if we
274 // can figure out the distance between the two iterators).
275 insert(first, last);
276 }
277
278 /* implicit */ sorted_vector_set(
279 std::initializer_list<value_type> list,
280 const Compare& comp = Compare(),
281 const Allocator& alloc = Allocator())
282 : m_(comp, alloc) {
283 insert(list.begin(), list.end());
284 }
285
286 // Construct a sorted_vector_set by stealing the storage of a prefilled
287 // container. The container need not be sorted already. This supports
288 // bulk construction of sorted_vector_set with zero allocations, not counting
289 // those performed by the caller. (The iterator range constructor performs at
290 // least one allocation).
291 //
292 // Note that `sorted_vector_set(const Container& container)` is not provided,
293 // since the purpose of this constructor is to avoid an unnecessary copy.
294 explicit sorted_vector_set(
295 Container&& container,
296 const Compare& comp = Compare())
297 : sorted_vector_set(
298 presorted,
299 detail::as_sorted(std::move(container), comp),
300 comp) {}
301
302 // Construct a sorted_vector_set by stealing the storage of a prefilled
303 // container. The container must be sorted, as presorted_t hints. Supports
304 // bulk construction of sorted_vector_set with zero allocations, not counting
305 // those performed by the caller. (The iterator range constructor performs at
306 // least one allocation).
307 //
308 // Note that `sorted_vector_set(presorted_t, const Container& container)` is
309 // not provided, since the purpose of this constructor is to avoid an extra
310 // copy.
311 sorted_vector_set(
312 presorted_t,
313 Container&& container,
314 const Compare& comp = Compare())
315 : m_(comp, container.get_allocator()) {
316 assert(std::is_sorted(container.begin(), container.end(), value_comp()));
317 m_.cont_.swap(container);
318 }
319
320 sorted_vector_set& operator=(std::initializer_list<value_type> ilist) {
321 clear();
322 insert(ilist.begin(), ilist.end());
323 return *this;
324 }
325
326 key_compare key_comp() const {
327 return m_;
328 }
329 value_compare value_comp() const {
330 return m_;
331 }
332
333 iterator begin() {
334 return m_.cont_.begin();
335 }
336 iterator end() {
337 return m_.cont_.end();
338 }
339 const_iterator cbegin() const {
340 return m_.cont_.cbegin();
341 }
342 const_iterator begin() const {
343 return m_.cont_.begin();
344 }
345 const_iterator cend() const {
346 return m_.cont_.cend();
347 }
348 const_iterator end() const {
349 return m_.cont_.end();
350 }
351 reverse_iterator rbegin() {
352 return m_.cont_.rbegin();
353 }
354 reverse_iterator rend() {
355 return m_.cont_.rend();
356 }
357 const_reverse_iterator rbegin() const {
358 return m_.cont_.rbegin();
359 }
360 const_reverse_iterator rend() const {
361 return m_.cont_.rend();
362 }
363
364 void clear() {
365 return m_.cont_.clear();
366 }
367 size_type size() const {
368 return m_.cont_.size();
369 }
370 size_type max_size() const {
371 return m_.cont_.max_size();
372 }
373 bool empty() const {
374 return m_.cont_.empty();
375 }
376 void reserve(size_type s) {
377 return m_.cont_.reserve(s);
378 }
379 void shrink_to_fit() {
380 m_.cont_.shrink_to_fit();
381 }
382 size_type capacity() const {
383 return m_.cont_.capacity();
384 }
385
386 std::pair<iterator, bool> insert(const value_type& value) {
387 iterator it = lower_bound(value);
388 if (it == end() || value_comp()(value, *it)) {
389 it = get_growth_policy().increase_capacity(m_.cont_, it);
390 return std::make_pair(m_.cont_.insert(it, value), true);
391 }
392 return std::make_pair(it, false);
393 }
394
395 std::pair<iterator, bool> insert(value_type&& value) {
396 iterator it = lower_bound(value);
397 if (it == end() || value_comp()(value, *it)) {
398 it = get_growth_policy().increase_capacity(m_.cont_, it);
399 return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
400 }
401 return std::make_pair(it, false);
402 }
403
404 iterator insert(iterator hint, const value_type& value) {
405 return insert(hint, std::move(value_type(value)));
406 }
407
408 iterator insert(iterator hint, value_type&& value) {
409 return detail::insert_with_hint(
410 *this, m_.cont_, hint, std::move(value), get_growth_policy());
411 }
412
413 template <class InputIterator>
414 void insert(InputIterator first, InputIterator last) {
415 detail::bulk_insert(*this, m_.cont_, first, last);
416 }
417
418 void insert(std::initializer_list<value_type> ilist) {
419 insert(ilist.begin(), ilist.end());
420 }
421
422 // emplace isn't better than insert for sorted_vector_set, but aids
423 // compatibility
424 template <typename... Args>
425 std::pair<iterator, bool> emplace(Args&&... args) {
426 value_type v(std::forward<Args>(args)...);
427 return insert(std::move(v));
428 }
429
430 std::pair<iterator, bool> emplace(const value_type& value) {
431 return insert(value);
432 }
433
434 std::pair<iterator, bool> emplace(value_type&& value) {
435 return insert(std::move(value));
436 }
437
438 size_type erase(const key_type& key) {
439 iterator it = find(key);
440 if (it == end()) {
441 return 0;
442 }
443 m_.cont_.erase(it);
444 return 1;
445 }
446
447 iterator erase(iterator it) {
448 return m_.cont_.erase(it);
449 }
450
451 iterator erase(iterator first, iterator last) {
452 return m_.cont_.erase(first, last);
453 }
454
455 iterator find(const key_type& key) {
456 return find(*this, key);
457 }
458
459 const_iterator find(const key_type& key) const {
460 return find(*this, key);
461 }
462
463 template <typename K>
464 if_is_transparent<K, iterator> find(const K& key) {
465 return find(*this, key);
466 }
467
468 template <typename K>
469 if_is_transparent<K, const_iterator> find(const K& key) const {
470 return find(*this, key);
471 }
472
473 size_type count(const key_type& key) const {
474 return find(key) == end() ? 0 : 1;
475 }
476
477 template <typename K>
478 if_is_transparent<K, size_type> count(const K& key) const {
479 return find(key) == end() ? 0 : 1;
480 }
481
482 iterator lower_bound(const key_type& key) {
483 return std::lower_bound(begin(), end(), key, key_comp());
484 }
485
486 const_iterator lower_bound(const key_type& key) const {
487 return std::lower_bound(begin(), end(), key, key_comp());
488 }
489
490 template <typename K>
491 if_is_transparent<K, iterator> lower_bound(const K& key) {
492 return std::lower_bound(begin(), end(), key, key_comp());
493 }
494
495 template <typename K>
496 if_is_transparent<K, const_iterator> lower_bound(const K& key) const {
497 return std::lower_bound(begin(), end(), key, key_comp());
498 }
499
500 iterator upper_bound(const key_type& key) {
501 return std::upper_bound(begin(), end(), key, key_comp());
502 }
503
504 const_iterator upper_bound(const key_type& key) const {
505 return std::upper_bound(begin(), end(), key, key_comp());
506 }
507
508 template <typename K>
509 if_is_transparent<K, iterator> upper_bound(const K& key) {
510 return std::upper_bound(begin(), end(), key, key_comp());
511 }
512
513 template <typename K>
514 if_is_transparent<K, const_iterator> upper_bound(const K& key) const {
515 return std::upper_bound(begin(), end(), key, key_comp());
516 }
517
518 std::pair<iterator, iterator> equal_range(const key_type& key) {
519 return std::equal_range(begin(), end(), key, key_comp());
520 }
521
522 std::pair<const_iterator, const_iterator> equal_range(
523 const key_type& key) const {
524 return std::equal_range(begin(), end(), key, key_comp());
525 }
526
527 template <typename K>
528 if_is_transparent<K, std::pair<iterator, iterator>> equal_range(
529 const K& key) {
530 return std::equal_range(begin(), end(), key, key_comp());
531 }
532
533 template <typename K>
534 if_is_transparent<K, std::pair<const_iterator, const_iterator>> equal_range(
535 const K& key) const {
536 return std::equal_range(begin(), end(), key, key_comp());
537 }
538
539 // Nothrow as long as swap() on the Compare type is nothrow.
540 void swap(sorted_vector_set& o) {
541 using std::swap; // Allow ADL for swap(); fall back to std::swap().
542 Compare& a = m_;
543 Compare& b = o.m_;
544 swap(a, b);
545 m_.cont_.swap(o.m_.cont_);
546 }
547
548 bool operator==(const sorted_vector_set& other) const {
549 return other.m_.cont_ == m_.cont_;
550 }
551 bool operator!=(const sorted_vector_set& other) const {
552 return !operator==(other);
553 }
554
555 bool operator<(const sorted_vector_set& other) const {
556 return m_.cont_ < other.m_.cont_;
557 }
558 bool operator>(const sorted_vector_set& other) const {
559 return other < *this;
560 }
561 bool operator<=(const sorted_vector_set& other) const {
562 return !operator>(other);
563 }
564 bool operator>=(const sorted_vector_set& other) const {
565 return !operator<(other);
566 }
567
568 const value_type* data() const noexcept {
569 return m_.cont_.data();
570 }
571
572 private:
573 /*
574 * This structure derives from the comparison object in order to
575 * make use of the empty base class optimization if our comparison
576 * functor is an empty class (usual case).
577 *
578 * Wrapping up this member like this is better than deriving from
579 * the Compare object ourselves (there are some perverse edge cases
580 * involving virtual functions).
581 *
582 * More info: http://www.cantrip.org/emptyopt.html
583 */
584 struct EBO : Compare {
585 explicit EBO(const Compare& c, const Allocator& alloc)
586 : Compare(c), cont_(alloc) {}
587 Container cont_;
588 } m_;
589
590 template <typename Self>
591 using self_iterator_t = _t<
592 std::conditional<std::is_const<Self>::value, const_iterator, iterator>>;
593
594 template <typename Self, typename K>
595 static self_iterator_t<Self> find(Self& self, K const& key) {
596 auto end = self.end();
597 auto it = self.lower_bound(key);
598 if (it == end || !self.key_comp()(key, *it)) {
599 return it;
600 }
601 return end;
602 }
603};
604
605// Swap function that can be found using ADL.
606template <class T, class C, class A, class G>
607inline void swap(
608 sorted_vector_set<T, C, A, G>& a,
609 sorted_vector_set<T, C, A, G>& b) {
610 return a.swap(b);
611}
612
613//////////////////////////////////////////////////////////////////////
614
615/**
616 * A sorted_vector_map is similar to a sorted_vector_set but stores
617 * <key,value> pairs instead of single elements.
618 *
619 * @param class Key Key type
620 * @param class Value Value type
621 * @param class Compare Function that can compare key types and impose
622 * a strict weak ordering over them.
623 * @param class Allocator allocation policy
624 * @param class GrowthPolicy policy object to control growth
625 *
626 * @author Aditya Agarwal <aditya@fb.com>
627 * @author Akhil Wable <akhil@fb.com>
628 * @author Jordan DeLong <delong.j@fb.com>
629 */
630template <
631 class Key,
632 class Value,
633 class Compare = std::less<Key>,
634 class Allocator = std::allocator<std::pair<Key, Value>>,
635 class GrowthPolicy = void,
636 class Container = std::vector<std::pair<Key, Value>, Allocator>>
637class sorted_vector_map : detail::growth_policy_wrapper<GrowthPolicy> {
638 detail::growth_policy_wrapper<GrowthPolicy>& get_growth_policy() {
639 return *this;
640 }
641
642 template <typename K, typename V, typename C = Compare>
643 using if_is_transparent =
644 _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>;
645
646 public:
647 typedef Key key_type;
648 typedef Value mapped_type;
649 typedef typename Container::value_type value_type;
650 typedef Compare key_compare;
651 typedef Allocator allocator_type;
652
653 struct value_compare : private Compare {
654 bool operator()(const value_type& a, const value_type& b) const {
655 return Compare::operator()(a.first, b.first);
656 }
657
658 protected:
659 friend class sorted_vector_map;
660 explicit value_compare(const Compare& c) : Compare(c) {}
661 };
662
663 typedef typename Container::pointer pointer;
664 typedef typename Container::reference reference;
665 typedef typename Container::const_reference const_reference;
666 typedef typename Container::iterator iterator;
667 typedef typename Container::const_iterator const_iterator;
668 typedef typename Container::difference_type difference_type;
669 typedef typename Container::size_type size_type;
670 typedef typename Container::reverse_iterator reverse_iterator;
671 typedef typename Container::const_reverse_iterator const_reverse_iterator;
672
673 sorted_vector_map() : m_(value_compare(Compare()), Allocator()) {}
674
675 explicit sorted_vector_map(
676 const Compare& comp,
677 const Allocator& alloc = Allocator())
678 : m_(value_compare(comp), alloc) {}
679
680 template <class InputIterator>
681 explicit sorted_vector_map(
682 InputIterator first,
683 InputIterator last,
684 const Compare& comp = Compare(),
685 const Allocator& alloc = Allocator())
686 : m_(value_compare(comp), alloc) {
687 insert(first, last);
688 }
689
690 explicit sorted_vector_map(
691 std::initializer_list<value_type> list,
692 const Compare& comp = Compare(),
693 const Allocator& alloc = Allocator())
694 : m_(value_compare(comp), alloc) {
695 insert(list.begin(), list.end());
696 }
697
698 // Construct a sorted_vector_map by stealing the storage of a prefilled
699 // container. The container need not be sorted already. This supports
700 // bulk construction of sorted_vector_map with zero allocations, not counting
701 // those performed by the caller. (The iterator range constructor performs at
702 // least one allocation).
703 //
704 // Note that `sorted_vector_map(const Container& container)` is not provided,
705 // since the purpose of this constructor is to avoid an unnecessary copy.
706 explicit sorted_vector_map(
707 Container&& container,
708 const Compare& comp = Compare())
709 : sorted_vector_map(
710 presorted,
711 detail::as_sorted(std::move(container), value_compare(comp)),
712 comp) {}
713
714 // Construct a sorted_vector_map by stealing the storage of a prefilled
715 // container. The container must be sorted, as presorted_t hints. S supports
716 // bulk construction of sorted_vector_map with zero allocations, not counting
717 // those performed by the caller. (The iterator range constructor performs at
718 // least one allocation).
719 //
720 // Note that `sorted_vector_map(presorted_t, const Container& container)` is
721 // not provided, since the purpose of this constructor is to avoid an extra
722 // copy.
723 sorted_vector_map(
724 presorted_t,
725 Container&& container,
726 const Compare& comp = Compare())
727 : m_(value_compare(comp), container.get_allocator()) {
728 assert(std::is_sorted(container.begin(), container.end(), value_comp()));
729 m_.cont_.swap(container);
730 }
731
732 sorted_vector_map& operator=(std::initializer_list<value_type> ilist) {
733 clear();
734 insert(ilist.begin(), ilist.end());
735 return *this;
736 }
737
738 key_compare key_comp() const {
739 return m_;
740 }
741 value_compare value_comp() const {
742 return m_;
743 }
744
745 iterator begin() {
746 return m_.cont_.begin();
747 }
748 iterator end() {
749 return m_.cont_.end();
750 }
751 const_iterator cbegin() const {
752 return m_.cont_.cbegin();
753 }
754 const_iterator begin() const {
755 return m_.cont_.begin();
756 }
757 const_iterator cend() const {
758 return m_.cont_.cend();
759 }
760 const_iterator end() const {
761 return m_.cont_.end();
762 }
763 reverse_iterator rbegin() {
764 return m_.cont_.rbegin();
765 }
766 reverse_iterator rend() {
767 return m_.cont_.rend();
768 }
769 const_reverse_iterator rbegin() const {
770 return m_.cont_.rbegin();
771 }
772 const_reverse_iterator rend() const {
773 return m_.cont_.rend();
774 }
775
776 void clear() {
777 return m_.cont_.clear();
778 }
779 size_type size() const {
780 return m_.cont_.size();
781 }
782 size_type max_size() const {
783 return m_.cont_.max_size();
784 }
785 bool empty() const {
786 return m_.cont_.empty();
787 }
788 void reserve(size_type s) {
789 return m_.cont_.reserve(s);
790 }
791 void shrink_to_fit() {
792 m_.cont_.shrink_to_fit();
793 }
794 size_type capacity() const {
795 return m_.cont_.capacity();
796 }
797
798 std::pair<iterator, bool> insert(const value_type& value) {
799 iterator it = lower_bound(value.first);
800 if (it == end() || value_comp()(value, *it)) {
801 it = get_growth_policy().increase_capacity(m_.cont_, it);
802 return std::make_pair(m_.cont_.insert(it, value), true);
803 }
804 return std::make_pair(it, false);
805 }
806
807 std::pair<iterator, bool> insert(value_type&& value) {
808 iterator it = lower_bound(value.first);
809 if (it == end() || value_comp()(value, *it)) {
810 it = get_growth_policy().increase_capacity(m_.cont_, it);
811 return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
812 }
813 return std::make_pair(it, false);
814 }
815
816 iterator insert(iterator hint, const value_type& value) {
817 return insert(hint, std::move(value_type(value)));
818 }
819
820 iterator insert(iterator hint, value_type&& value) {
821 return detail::insert_with_hint(
822 *this, m_.cont_, hint, std::move(value), get_growth_policy());
823 }
824
825 template <class InputIterator>
826 void insert(InputIterator first, InputIterator last) {
827 detail::bulk_insert(*this, m_.cont_, first, last);
828 }
829
830 void insert(std::initializer_list<value_type> ilist) {
831 insert(ilist.begin(), ilist.end());
832 }
833
834 size_type erase(const key_type& key) {
835 iterator it = find(key);
836 if (it == end()) {
837 return 0;
838 }
839 m_.cont_.erase(it);
840 return 1;
841 }
842
843 iterator erase(iterator it) {
844 return m_.cont_.erase(it);
845 }
846
847 iterator erase(iterator first, iterator last) {
848 return m_.cont_.erase(first, last);
849 }
850
851 iterator find(const key_type& key) {
852 return find(*this, key);
853 }
854
855 const_iterator find(const key_type& key) const {
856 return find(*this, key);
857 }
858
859 template <typename K>
860 if_is_transparent<K, iterator> find(const K& key) {
861 return find(*this, key);
862 }
863
864 template <typename K>
865 if_is_transparent<K, const_iterator> find(const K& key) const {
866 return find(*this, key);
867 }
868
869 mapped_type& at(const key_type& key) {
870 iterator it = find(key);
871 if (it != end()) {
872 return it->second;
873 }
874 throw_exception<std::out_of_range>("sorted_vector_map::at");
875 }
876
877 const mapped_type& at(const key_type& key) const {
878 const_iterator it = find(key);
879 if (it != end()) {
880 return it->second;
881 }
882 throw_exception<std::out_of_range>("sorted_vector_map::at");
883 }
884
885 size_type count(const key_type& key) const {
886 return find(key) == end() ? 0 : 1;
887 }
888
889 template <typename K>
890 if_is_transparent<K, size_type> count(const K& key) const {
891 return find(key) == end() ? 0 : 1;
892 }
893
894 iterator lower_bound(const key_type& key) {
895 return lower_bound(*this, key);
896 }
897
898 const_iterator lower_bound(const key_type& key) const {
899 return lower_bound(*this, key);
900 }
901
902 template <typename K>
903 if_is_transparent<K, iterator> lower_bound(const K& key) {
904 return lower_bound(*this, key);
905 }
906
907 template <typename K>
908 if_is_transparent<K, const_iterator> lower_bound(const K& key) const {
909 return lower_bound(*this, key);
910 }
911
912 iterator upper_bound(const key_type& key) {
913 return upper_bound(*this, key);
914 }
915
916 const_iterator upper_bound(const key_type& key) const {
917 return upper_bound(*this, key);
918 }
919
920 template <typename K>
921 if_is_transparent<K, iterator> upper_bound(const K& key) {
922 return upper_bound(*this, key);
923 }
924
925 template <typename K>
926 if_is_transparent<K, const_iterator> upper_bound(const K& key) const {
927 return upper_bound(*this, key);
928 }
929
930 std::pair<iterator, iterator> equal_range(const key_type& key) {
931 return equal_range(*this, key);
932 }
933
934 std::pair<const_iterator, const_iterator> equal_range(
935 const key_type& key) const {
936 return equal_range(*this, key);
937 }
938
939 template <typename K>
940 if_is_transparent<K, std::pair<iterator, iterator>> equal_range(
941 const K& key) {
942 return equal_range(*this, key);
943 }
944
945 template <typename K>
946 if_is_transparent<K, std::pair<const_iterator, const_iterator>> equal_range(
947 const K& key) const {
948 return equal_range(*this, key);
949 }
950
951 // Nothrow as long as swap() on the Compare type is nothrow.
952 void swap(sorted_vector_map& o) {
953 using std::swap; // Allow ADL for swap(); fall back to std::swap().
954 Compare& a = m_;
955 Compare& b = o.m_;
956 swap(a, b);
957 m_.cont_.swap(o.m_.cont_);
958 }
959
960 mapped_type& operator[](const key_type& key) {
961 iterator it = lower_bound(key);
962 if (it == end() || key_comp()(key, it->first)) {
963 return insert(it, value_type(key, mapped_type()))->second;
964 }
965 return it->second;
966 }
967
968 bool operator==(const sorted_vector_map& other) const {
969 return m_.cont_ == other.m_.cont_;
970 }
971 bool operator!=(const sorted_vector_map& other) const {
972 return !operator==(other);
973 }
974
975 bool operator<(const sorted_vector_map& other) const {
976 return m_.cont_ < other.m_.cont_;
977 }
978 bool operator>(const sorted_vector_map& other) const {
979 return other < *this;
980 }
981 bool operator<=(const sorted_vector_map& other) const {
982 return !operator>(other);
983 }
984 bool operator>=(const sorted_vector_map& other) const {
985 return !operator<(other);
986 }
987
988 const value_type* data() const noexcept {
989 return m_.cont_.data();
990 }
991
992 private:
993 // This is to get the empty base optimization; see the comment in
994 // sorted_vector_set.
995 struct EBO : value_compare {
996 explicit EBO(const value_compare& c, const Allocator& alloc)
997 : value_compare(c), cont_(alloc) {}
998 Container cont_;
999 } m_;
1000
1001 template <typename Self>
1002 using self_iterator_t = _t<
1003 std::conditional<std::is_const<Self>::value, const_iterator, iterator>>;
1004
1005 template <typename Self, typename K>
1006 static self_iterator_t<Self> find(Self& self, K const& key) {
1007 auto end = self.end();
1008 auto it = self.lower_bound(key);
1009 if (it == end || !self.key_comp()(key, it->first)) {
1010 return it;
1011 }
1012 return end;
1013 }
1014
1015 template <typename Self, typename K>
1016 static self_iterator_t<Self> lower_bound(Self& self, K const& key) {
1017 auto f = [c = self.key_comp()](value_type const& a, K const& b) {
1018 return c(a.first, b);
1019 };
1020 return std::lower_bound(self.begin(), self.end(), key, f);
1021 }
1022
1023 template <typename Self, typename K>
1024 static self_iterator_t<Self> upper_bound(Self& self, K const& key) {
1025 auto f = [c = self.key_comp()](K const& a, value_type const& b) {
1026 return c(a, b.first);
1027 };
1028 return std::upper_bound(self.begin(), self.end(), key, f);
1029 }
1030
1031 template <typename Self, typename K>
1032 static std::pair<self_iterator_t<Self>, self_iterator_t<Self>> equal_range(
1033 Self& self,
1034 K const& key) {
1035 // Note: std::equal_range can't be passed a functor that takes
1036 // argument types different from the iterator value_type, so we
1037 // have to do this.
1038 return {lower_bound(self, key), upper_bound(self, key)};
1039 }
1040};
1041
1042// Swap function that can be found using ADL.
1043template <class K, class V, class C, class A, class G>
1044inline void swap(
1045 sorted_vector_map<K, V, C, A, G>& a,
1046 sorted_vector_map<K, V, C, A, G>& b) {
1047 return a.swap(b);
1048}
1049
1050//////////////////////////////////////////////////////////////////////
1051
1052} // namespace folly
1053