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 | |
76 | namespace folly { |
77 | |
78 | ////////////////////////////////////////////////////////////////////// |
79 | |
80 | namespace detail { |
81 | |
82 | template <typename, typename Compare, typename Key, typename T> |
83 | struct sorted_vector_enable_if_is_transparent {}; |
84 | |
85 | template <typename Compare, typename Key, typename T> |
86 | struct 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). |
97 | template <class Policy> |
98 | struct 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 | }; |
107 | template <> |
108 | struct 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 | */ |
121 | template <class Iterator> |
122 | int 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 | |
130 | template <class OurContainer, class Vector, class GrowthPolicy> |
131 | typename 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 | |
160 | template <class OurContainer, class Vector, class InputIterator> |
161 | void 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 | |
198 | template <typename Container, typename Compare> |
199 | Container&& 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 | */ |
222 | template < |
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>> |
228 | class 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. |
606 | template <class T, class C, class A, class G> |
607 | inline 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 | */ |
630 | template < |
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>> |
637 | class 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. |
1043 | template <class K, class V, class C, class A, class G> |
1044 | inline 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 | |