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 | |
82 | namespace folly { |
83 | |
84 | ////////////////////////////////////////////////////////////////////// |
85 | |
86 | namespace detail { |
87 | |
88 | template <typename, typename Compare, typename Key, typename T> |
89 | struct sorted_vector_enable_if_is_transparent {}; |
90 | |
91 | template <typename Compare, typename Key, typename T> |
92 | struct 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). |
103 | template <class Policy> |
104 | struct 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 | }; |
113 | template <> |
114 | struct 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 | */ |
127 | template <class Iterator> |
128 | int 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 | |
136 | template <class OurContainer, class Vector, class GrowthPolicy, class Value> |
137 | typename 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 | |
166 | template <class OurContainer, class Vector, class InputIterator> |
167 | void 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 | |
204 | template <typename Container, typename Compare> |
205 | bool 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 | |
218 | template <typename Container, typename Compare> |
219 | Container&& 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 | */ |
249 | template < |
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>> |
255 | class 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. |
725 | template <class T, class C, class A, class G> |
726 | inline 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 | |
734 | namespace pmr { |
735 | |
736 | template < |
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>>> |
742 | using 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 | */ |
770 | template < |
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>> |
777 | class 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. |
1293 | template <class K, class V, class C, class A, class G> |
1294 | inline 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 | |
1302 | namespace pmr { |
1303 | |
1304 | template < |
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>>>> |
1312 | using 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 | |