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