source: mainline/uspace/lib/cpp/include/impl/map.hpp@ 8a7da64d

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 8a7da64d was 8a7da64d, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: added map::try_emplace and map::insert_or_assign
  • Property mode set to 100644
File size: 35.9 KB
RevLine 
[7ca0410f]1/*
2 * Copyright (c) 2018 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_MAP
30#define LIBCPP_MAP
31
32#include <functional>
33#include <internal/rbtree.hpp>
34#include <iterator>
35#include <memory>
36#include <utility>
37#include <type_traits>
38
39namespace std
40{
41 /**
42 * 23.4.4, class template map:
43 */
44
45 template<
46 class Key, class Value,
47 class Compare = less<Key>,
48 class Alloc = allocator<pair<const Key, Value>>
49 >
50 class map
51 {
52 public:
53 using key_type = Key;
54 using mapped_type = Value;
55 using value_type = pair<const key_type, mapped_type>;
56 using key_compare = Compare;
57 using allocator_type = Alloc;
58 using pointer = typename allocator_traits<allocator_type>::pointer;
59 using const_pointer = typename allocator_traits<allocator_type>::const_pointer;
60 using reference = value_type&;
61 using const_reference = const value_type&;
62 using size_type = size_t;
63 using difference_type = ptrdiff_t;
64
65 using iterator = aux::rbtree_iterator<
66 value_type, reference, pointer, size_type
67 >;
68 using const_iterator = aux::rbtree_const_iterator<
69 value_type, const_reference, const_pointer, size_type
70 >;
71
72 using reverse_iterator = std::reverse_iterator<iterator>;
73 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
74
75 class value_compare
76 {
77 friend class map;
78
79 protected:
80 key_compare comp;
81
82 value_compare(key_compare c)
83 : comp{c}
84 { /* DUMMY BODY */ }
85
86 public:
87 using result_type = bool;
88 using first_argument_type = value_type;
89 using second_argument_type = value_type;
90
91 bool operator()(const value_type& lhs, const value_type& rhs) const
92 {
93 return comp(lhs.first, rhs.first);
94 }
95 };
96
97 /**
98 * 24.4.4.2, construct/copy/destroy:
99 */
100
101 map()
102 : map{key_compare{}}
103 { /* DUMMY BODY */ }
104
105 explicit map(const key_compare& comp,
106 const allocator_type& alloc = allocator_type{})
107 : tree_{comp}, allocator_{alloc}
108 { /* DUMMY BODY */ }
109
110 template<class InputIterator>
111 map(InputIterator first, InputIterator last,
112 const key_compare& comp = key_compare{},
113 const allocator_type& alloc = allocator_type{})
114 : map{comp, alloc}
115 {
116 insert(first, last);
117 }
118
119 map(const map& other)
120 : map{other, other.allocator_}
121 { /* DUMMY BODY */ }
122
123 map(map&& other)
124 : tree_{move(other.tree_)}, allocator_{move(other.allocator_)}
125 { /* DUMMY BODY */ }
126
127 explicit map(const allocator_type& alloc)
128 : tree_{}, allocator_{alloc}
129 { /* DUMMY BODY */ }
130
131 map(const map& other, const allocator_type& alloc)
132 : tree_{other.tree_}, allocator_{alloc}
133 { /* DUMMY BODY */ }
134
135 map(map&& other, const allocator_type& alloc)
136 : tree_{move(other.tree_)}, allocator_{alloc}
137 { /* DUMMY BODY */ }
138
139 map(initializer_list<value_type> init,
140 const key_compare& comp = key_compare{},
141 const allocator_type& alloc = allocator_type{})
142 : map{comp, alloc}
143 {
144 insert(init.begin(), init.end());
145 }
146
147 template<class InputIterator>
148 map(InputIterator first, InputIterator last,
149 const allocator_type& alloc)
150 : map{first, last, key_compare{}, alloc}
151 { /* DUMMY BODY */ }
152
153 map(initializer_list<value_type> init,
154 const allocator_type& alloc)
155 : map{init, key_compare{}, alloc}
156 { /* DUMMY BODY */ }
157
158 ~map()
159 { /* DUMMY BODY */ }
160
161 map& operator=(const map& other)
162 {
163 tree_ = other.tree_;
164 allocator_ = other.allocator_;
165
166 return *this;
167 }
168
169 map& operator=(map&& other)
170 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
171 is_nothrow_move_assignable<key_compare>::value)
172 {
173 tree_ = move(other.tree_);
174 allocator_ = move(other.allocator_);
175
176 return *this;
177 }
178
179 map& operator=(initializer_list<value_type>& init)
180 {
181 tree_.clear();
182
183 insert(init.begin(), init.end());
184
185 return *this;
186 }
187
188 allocator_type get_allocator() const noexcept
189 {
190 return allocator_;
191 }
192
193 iterator begin() noexcept
194 {
195 return tree_.begin();
196 }
197
198 const_iterator begin() const noexcept
199 {
200 return tree_.begin();
201 }
202
203 iterator end() noexcept
204 {
205 return tree_.end();
206 }
207
208 const_iterator end() const noexcept
209 {
210 return tree_.end();
211 }
212
213 reverse_iterator rbegin() noexcept
214 {
215 return tree_.rbegin();
216 }
217
218 const_reverse_iterator rbegin() const noexcept
219 {
220 return tree_.rbegin();
221 }
222
223 reverse_iterator rend() noexcept
224 {
225 return tree_.rend();
226 }
227
228 const_reverse_iterator rend() const noexcept
229 {
230 return tree_.rend();
231 }
232
233 const_iterator cbegin() const noexcept
234 {
235 return tree_.cbegin();
236 }
237
238 const_iterator cend() const noexcept
239 {
240 return tree_.cend();
241 }
242
243 const_reverse_iterator crbegin() const noexcept
244 {
245 return tree_.crbegin();
246 }
247
248 const_reverse_iterator crend() const noexcept
249 {
250 return tree_.crend();
251 }
252
253 bool empty() const noexcept
254 {
255 return tree_.empty();
256 }
257
258 size_type size() const noexcept
259 {
260 return tree_.size();
261 }
262
263 size_type max_size() const noexcept
264 {
265 return tree_.max_size(allocator_);
266 }
267
268 /**
269 * 23.4.4.3, element access:
270 */
271
[e8ebed9]272 mapped_type& operator[](const key_type& key)
273 {
274 auto parent = tree_.find_parent_for_insertion(key);
275 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
276 return parent->value.second;
277
278 auto node = new node_type{value_type{key, mapped_type{}}};
279 tree_.insert_node(node, parent);
280
281 return node->value.second;
282 }
283
284 mapped_type& operator[](key_type&& key)
285 {
286 auto parent = tree_.find_parent_for_insertion(key);
287 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
288 return parent->value.second;
289
290 auto node = new node_type{value_type{move(key), mapped_type{}}};
291 tree_.insert_node(node, parent);
292
293 return node->value.second;
294 }
[7ca0410f]295
296 /**
297 * 23.4.4.4, modifiers:
298 */
299
300 template<class... Args>
301 pair<iterator, bool> emplace(Args&&... args)
302 {
303 return tree_.emplace(forward<Args>(args)...);
304 }
305
306 template<class... Args>
307 iterator emplace_hint(const_iterator, Args&&... args)
308 {
309 return emplace(forward<Args>(args)...).first;
310 }
311
312 pair<iterator, bool> insert(const value_type& val)
313 {
314 return tree_.insert(val);
315 }
316
317 pair<iterator, bool> insert(value_type&& val)
318 {
319 return tree_.insert(forward<value_type>(val));
320 }
321
322 template<class T>
323 pair<iterator, bool> insert(
324 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val)
325 {
326 return emplace(forward<T>(val));
327 }
328
329 iterator insert(const_iterator, const value_type& val)
330 {
331 return insert(val).first;
332 }
333
334 iterator insert(const_iterator, value_type&& val)
335 {
336 return insert(forward<value_type>(val)).first;
337 }
338
339 template<class T>
340 iterator insert(
341 const_iterator hint,
342 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
343 )
344 {
345 return emplace_hint(hint, forward<T>(val));
346 }
347
348 template<class InputIterator>
349 void insert(InputIterator first, InputIterator last)
350 {
351 while (first != last)
352 insert(*first++);
353 }
354
355 void insert(initializer_list<value_type> init)
356 {
357 insert(init.begin(), init.end());
358 }
359
[8a7da64d]360 template<class... Args>
361 pair<iterator, bool> try_emplace(const key_type& key, Args&&... args)
362 {
363 auto parent = tree_.find_parent_for_insertion(key);
364 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
365 return make_pair(iterator{parent, false}, false);
366 else
367 {
368 auto node = new node_type{value_type{key, forward<Args>(args)...}};
369 tree_.insert_node(node, parent);
370
371 return make_pair(iterator{node, false}, true);
372 }
373 }
374
375 template<class... Args>
376 pair<iterator, bool> try_emplace(key_type&& key, Args&&... args)
377 {
378 auto parent = tree_.find_parent_for_insertion(key);
379 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
380 return make_pair(iterator{parent, false}, false);
381 else
382 {
383 auto node = new node_type{value_type{move(key), forward<Args>(args)...}};
384 tree_.insert_node(node, parent);
385
386 return make_pair(iterator{node, false}, true);
387 }
388 }
389
390 template<class... Args>
391 iterator try_emplace(const_iterator, const key_type& key, Args&&... args)
392 {
393 return try_emplace(key, forward<Args>(args)...).first;
394 }
395
396 template<class... Args>
397 iterator try_emplace(const_iterator, key_type&& key, Args&&... args)
398 {
399 return try_emplace(move(key), forward<Args>(args)...).first;
400 }
401
402 template<class T>
403 pair<iterator, bool> insert_or_assign(const key_type& key, T&& val)
404 {
405 auto parent = tree_.find_parent_for_insertion(key);
406 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
407 {
408 parent->value = value_type{key, forward<T>(val)};
409
410 return make_pair(iterator{parent, false}, false);
411 }
412 else
413 {
414 auto node = new node_type{value_type{key, forward<T>(val)}};
415 tree_.insert_node(node, parent);
416
417 return make_pair(iterator{node, false}, true);
418 }
419 }
420
421 template<class T>
422 pair<iterator, bool> insert_or_assign(key_type&& key, T&& val)
423 {
424 auto parent = tree_.find_parent_for_insertion(key);
425 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
426 {
427 parent->value = value_type{move(key), forward<T>(val)};
428
429 return make_pair(iterator{parent, false}, false);
430 }
431 else
432 {
433 auto node = new node_type{value_type{move(key), forward<T>(val)}};
434 tree_.insert_node(node, parent);
435
436 return make_pair(iterator{node, false}, true);
437 }
438 }
439
440 template<class T>
441 iterator insert_or_assign(const_iterator, const key_type& key, T&& val)
442 {
443 return insert_or_assign(key, forward<T>(val)).first;
444 }
445
446 template<class T>
447 iterator insert_or_assign(const_iterator, key_type&& key, T&& val)
448 {
449 return insert_or_assign(move(key), forward<T>(val)).first;
450 }
[7ca0410f]451
452 iterator erase(const_iterator position)
453 {
454 return tree_.erase(position);
455 }
456
457 size_type erase(const key_type& key)
458 {
459 return tree_.erase(key);
460 }
461
462 iterator erase(const_iterator first, const_iterator last)
463 {
464 while (first != last)
465 first = erase(first);
466
467 return iterator{
468 first.node(), first.end()
469 };
470 }
471
472 void swap(map& other)
473 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
474 noexcept(std::swap(declval<key_compare>(), declval<key_compare>())))
475 {
476 tree_.swap(other.tree_);
477 std::swap(allocator_, other.allocator_);
478 }
479
480 void clear() noexcept
481 {
482 tree_.clear();
483 }
484
485 key_compare key_comp() const
486 {
487 return tree_.key_comp();
488 }
489
490 value_compare value_comp() const
491 {
492 return value_compare{tree_.key_comp()};
493 }
494
495 iterator find(const key_type& key)
496 {
497 return tree_.find(key);
498 }
499
500 const_iterator find(const key_type& key) const
501 {
502 return tree_.find(key);
503 }
504
505 template<class K>
506 iterator find(
507 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
508 )
509 {
510 return tree_.find(key);
511 }
512
513 template<class K>
514 const_iterator find(
515 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
516 ) const
517 {
518 return tree_.find(key);
519 }
520
521 size_type count(const key_type& key) const
522 {
523 return tree_.count(key);
524 }
525
526 template<class K>
527 size_type count(
528 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
529 ) const
530 {
531 return tree_.count(key);
532 }
533
534 iterator lower_bound(const key_type& key)
535 {
536 return tree_.lower_bound(key);
537 }
538
539 const_iterator lower_bound(const key_type& key) const
540 {
541 return tree_.lower_bound(key);
542 }
543
544 template<class K>
545 iterator lower_bound(
546 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
547 )
548 {
549 return tree_.lower_bound(key);
550 }
551
552 template<class K>
553 const_iterator lower_bound(
554 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
555 ) const
556 {
557 return tree_.lower_bound(key);
558 }
559
560 iterator upper_bound(const key_type& key)
561 {
562 return tree_.upper_bound(key);
563 }
564
565 const_iterator upper_bound(const key_type& key) const
566 {
567 return tree_.upper_bound(key);
568 }
569
570 template<class K>
571 iterator upper_bound(
572 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
573 )
574 {
575 return tree_.upper_bound(key);
576 }
577
578 template<class K>
579 const_iterator upper_bound(
580 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
581 ) const
582 {
583 return tree_.upper_bound(key);
584 }
585
586 pair<iterator, iterator> equal_range(const key_type& key)
587 {
588 return tree_.equal_range(key);
589 }
590
591 pair<const_iterator, const_iterator> equal_range(const key_type& key) const
592 {
593 return tree_.equal_range(key);
594 }
595
596 template<class K>
597 pair<iterator, iterator> equal_range(
598 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
599 )
600 {
601 return tree_.equal_range(key);
602 }
603
604 template<class K>
605 pair<const_iterator, const_iterator> equal_range(
606 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
607 ) const
608 {
609 return tree_.equal_range(key);
610 }
611
612 private:
613 using tree_type = aux::rbtree<
614 value_type, key_type, aux::key_value_key_extractor<key_type, mapped_type>,
615 key_compare, allocator_type, size_type,
616 iterator, const_iterator,
617 aux::rbtree_single_policy
618 >;
619
[e8ebed9]620 using node_type = typename tree_type::node_type;
621
[7ca0410f]622 tree_type tree_;
623 allocator_type allocator_;
624
625 template<class K, class C, class A>
626 friend bool operator==(const map<K, C, A>&,
627 const map<K, C, A>&);
628 };
629
630 template<class Key, class Compare, class Allocator>
631 bool operator==(const map<Key, Compare, Allocator>& lhs,
632 const map<Key, Compare, Allocator>& rhs)
633 {
634 return lhs.tree_.is_eq_to(rhs.tree_);
635 }
636
637 template<class Key, class Compare, class Allocator>
638 bool operator<(const map<Key, Compare, Allocator>& lhs,
639 const map<Key, Compare, Allocator>& rhs)
640 {
[026cb10]641 return lexicographical_compare(
642 lhs.begin(), lhs.end(),
643 rhs.begin(), rhs.end(),
644 lhs.value_comp()
645 );
[7ca0410f]646 }
647
648 template<class Key, class Compare, class Allocator>
649 bool operator!=(const map<Key, Compare, Allocator>& lhs,
650 const map<Key, Compare, Allocator>& rhs)
651 {
652 return !(lhs == rhs);
653 }
654
655 template<class Key, class Compare, class Allocator>
656 bool operator>(const map<Key, Compare, Allocator>& lhs,
657 const map<Key, Compare, Allocator>& rhs)
658 {
[026cb10]659 return rhs < lhs;
[7ca0410f]660 }
661
662 template<class Key, class Compare, class Allocator>
663 bool operator>=(const map<Key, Compare, Allocator>& lhs,
664 const map<Key, Compare, Allocator>& rhs)
665 {
[026cb10]666 return !(lhs < rhs);
[7ca0410f]667 }
668
669 template<class Key, class Compare, class Allocator>
670 bool operator<=(const map<Key, Compare, Allocator>& lhs,
671 const map<Key, Compare, Allocator>& rhs)
672 {
[026cb10]673 return !(rhs < lhs);
[7ca0410f]674 }
[026cb10]675
[7ca0410f]676 /**
677 * 23.4.5, class template multimap:
678 */
679
680 template<
681 class Key, class Value,
682 class Compare = less<Key>,
683 class Alloc = allocator<pair<const Key, Value>>
684 >
685 class multimap
686 {
687 public:
688 using key_type = Key;
689 using mapped_type = Value;
690 using value_type = pair<const key_type, mapped_type>;
691 using key_compare = Compare;
692 using allocator_type = Alloc;
693 using pointer = typename allocator_traits<allocator_type>::pointer;
694 using const_pointer = typename allocator_traits<allocator_type>::const_pointer;
695 using reference = value_type&;
696 using const_reference = const value_type&;
697 using size_type = size_t;
698 using difference_type = ptrdiff_t;
699
700 class value_compare
701 {
702 friend class multimap;
703
704 protected:
705 key_compare comp;
706
707 value_compare(key_compare c)
708 : comp{c}
709 { /* DUMMY BODY */ }
710
711 public:
712 using result_type = bool;
713 using first_argument_type = value_type;
714 using second_argument_type = value_type;
715
716 bool operator()(const value_type& lhs, const value_type& rhs) const
717 {
718 return comp(lhs.first, rhs.first);
719 }
720 };
721
722 using iterator = aux::rbtree_iterator<
723 value_type, reference, pointer, size_type
724 >;
725 using const_iterator = aux::rbtree_const_iterator<
726 value_type, const_reference, const_pointer, size_type
727 >;
728
729 using reverse_iterator = std::reverse_iterator<iterator>;
730 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
731
732 multimap()
733 : multimap{key_compare{}}
734 { /* DUMMY BODY */ }
735
736 explicit multimap(const key_compare& comp,
737 const allocator_type& alloc = allocator_type{})
738 : tree_{comp}, allocator_{alloc}
739 { /* DUMMY BODY */ }
740
741 template<class InputIterator>
742 multimap(InputIterator first, InputIterator last,
743 const key_compare& comp = key_compare{},
744 const allocator_type& alloc = allocator_type{})
745 : multimap{comp, alloc}
746 {
747 insert(first, last);
748 }
749
750 multimap(const multimap& other)
751 : multimap{other, other.allocator_}
752 { /* DUMMY BODY */ }
753
754 multimap(multimap&& other)
755 : tree_{move(other.tree_)}, allocator_{move(other.allocator_)}
756 { /* DUMMY BODY */ }
757
758 explicit multimap(const allocator_type& alloc)
759 : tree_{}, allocator_{alloc}
760 { /* DUMMY BODY */ }
761
762 multimap(const multimap& other, const allocator_type& alloc)
763 : tree_{other.tree_}, allocator_{alloc}
764 { /* DUMMY BODY */ }
765
766 multimap(multimap&& other, const allocator_type& alloc)
767 : tree_{move(other.tree_)}, allocator_{alloc}
768 { /* DUMMY BODY */ }
769
770 multimap(initializer_list<value_type> init,
771 const key_compare& comp = key_compare{},
772 const allocator_type& alloc = allocator_type{})
773 : multimap{comp, alloc}
774 {
775 insert(init.begin(), init.end());
776 }
777
778 template<class InputIterator>
779 multimap(InputIterator first, InputIterator last,
780 const allocator_type& alloc)
781 : multimap{first, last, key_compare{}, alloc}
782 { /* DUMMY BODY */ }
783
784 multimap(initializer_list<value_type> init,
785 const allocator_type& alloc)
786 : multimap{init, key_compare{}, alloc}
787 { /* DUMMY BODY */ }
788
789 ~multimap()
790 { /* DUMMY BODY */ }
791
792 multimap& operator=(const multimap& other)
793 {
794 tree_ = other.tree_;
795 allocator_ = other.allocator_;
796
797 return *this;
798 }
799
800 multimap& operator=(multimap&& other)
801 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
802 is_nothrow_move_assignable<key_compare>::value)
803 {
804 tree_ = move(other.tree_);
805 allocator_ = move(other.allocator_);
806
807 return *this;
808 }
809
810 multimap& operator=(initializer_list<value_type>& init)
811 {
812 tree_.clear();
813
814 insert(init.begin(), init.end());
815
816 return *this;
817 }
818
819 allocator_type get_allocator() const noexcept
820 {
821 return allocator_;
822 }
823
824 iterator begin() noexcept
825 {
826 return tree_.begin();
827 }
828
829 const_iterator begin() const noexcept
830 {
831 return tree_.begin();
832 }
833
834 iterator end() noexcept
835 {
836 return tree_.end();
837 }
838
839 const_iterator end() const noexcept
840 {
841 return tree_.end();
842 }
843
844 reverse_iterator rbegin() noexcept
845 {
846 return tree_.rbegin();
847 }
848
849 const_reverse_iterator rbegin() const noexcept
850 {
851 return tree_.rbegin();
852 }
853
854 reverse_iterator rend() noexcept
855 {
856 return tree_.rend();
857 }
858
859 const_reverse_iterator rend() const noexcept
860 {
861 return tree_.rend();
862 }
863
864 const_iterator cbegin() const noexcept
865 {
866 return tree_.cbegin();
867 }
868
869 const_iterator cend() const noexcept
870 {
871 return tree_.cend();
872 }
873
874 const_reverse_iterator crbegin() const noexcept
875 {
876 return tree_.crbegin();
877 }
878
879 const_reverse_iterator crend() const noexcept
880 {
881 return tree_.crend();
882 }
883
884 bool empty() const noexcept
885 {
886 return tree_.empty();
887 }
888
889 size_type size() const noexcept
890 {
891 return tree_.size();
892 }
893
894 size_type max_size() const noexcept
895 {
896 return tree_.max_size(allocator_);
897 }
898
899 template<class... Args>
900 iterator emplace(Args&&... args)
901 {
902 return tree_.emplace(forward<Args>(args)...);
903 }
904
905 template<class... Args>
906 iterator emplace_hint(const_iterator, Args&&... args)
907 {
908 return emplace(forward<Args>(args)...);
909 }
910
911 iterator insert(const value_type& val)
912 {
913 return tree_.insert(val);
914 }
915
916 iterator insert(value_type&& val)
917 {
918 return tree_.insert(forward<value_type>(val));
919 }
920
921 template<class T>
922 iterator insert(
923 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
924 )
925 {
926 return emplace(forward<T>(val));
927 }
928
929 iterator insert(const_iterator, const value_type& val)
930 {
931 return insert(val);
932 }
933
934 iterator insert(const_iterator, value_type&& val)
935 {
936 return insert(forward<value_type>(val));
937 }
938
939 template<class T>
940 iterator insert(
941 const_iterator hint,
942 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
943 )
944 {
945 return emplace_hint(hint, forward<T>(val));
946 }
947
948 template<class InputIterator>
949 void insert(InputIterator first, InputIterator last)
950 {
951 while (first != last)
952 insert(*first++);
953 }
954
955 void insert(initializer_list<value_type> init)
956 {
957 insert(init.begin(), init.end());
958 }
959
960 iterator erase(const_iterator position)
961 {
962 return tree_.erase(position);
963 }
964
965 size_type erase(const key_type& key)
966 {
967 return tree_.erase(key);
968 }
969
970 iterator erase(const_iterator first, const_iterator last)
971 {
972 while (first != last)
973 first = erase(first);
974
975 return iterator{
976 first.node(), first.end()
977 };
978 }
979
980 void swap(multimap& other)
981 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
982 noexcept(std::swap(declval<key_compare>(), declval<key_compare>())))
983 {
984 tree_.swap(other.tree_);
985 std::swap(allocator_, other.allocator_);
986 }
987
988 void clear() noexcept
989 {
990 tree_.clear();
991 }
992
993 key_compare key_comp() const
994 {
995 return tree_.key_comp();
996 }
997
998 value_compare value_comp() const
999 {
1000 return value_compare{tree_.key_comp()};
1001 }
1002
1003 iterator find(const key_type& key)
1004 {
1005 return tree_.find(key);
1006 }
1007
1008 const_iterator find(const key_type& key) const
1009 {
1010 return tree_.find(key);
1011 }
1012
1013 template<class K>
1014 iterator find(
1015 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1016 )
1017 {
1018 return tree_.find(key);
1019 }
1020
1021 template<class K>
1022 const_iterator find(
1023 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1024 ) const
1025 {
1026 return tree_.find(key);
1027 }
1028
1029 size_type count(const key_type& key) const
1030 {
1031 return tree_.count(key);
1032 }
1033
1034 template<class K>
1035 size_type count(
1036 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1037 ) const
1038 {
1039 return tree_.count(key);
1040 }
1041
1042 iterator lower_bound(const key_type& key)
1043 {
1044 return tree_.lower_bound(key);
1045 }
1046
1047 const_iterator lower_bound(const key_type& key) const
1048 {
1049 return tree_.lower_bound(key);
1050 }
1051
1052 template<class K>
1053 iterator lower_bound(
1054 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1055 )
1056 {
1057 return tree_.lower_bound(key);
1058 }
1059
1060 template<class K>
1061 const_iterator lower_bound(
1062 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1063 ) const
1064 {
1065 return tree_.lower_bound(key);
1066 }
1067
1068 iterator upper_bound(const key_type& key)
1069 {
1070 return tree_.upper_bound(key);
1071 }
1072
1073 const_iterator upper_bound(const key_type& key) const
1074 {
1075 return tree_.upper_bound(key);
1076 }
1077
1078 template<class K>
1079 iterator upper_bound(
1080 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1081 )
1082 {
1083 return tree_.upper_bound(key);
1084 }
1085
1086 template<class K>
1087 const_iterator upper_bound(
1088 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1089 ) const
1090 {
1091 return tree_.upper_bound(key);
1092 }
1093
1094 pair<iterator, iterator> equal_range(const key_type& key)
1095 {
1096 return tree_.equal_range(key);
1097 }
1098
1099 pair<const_iterator, const_iterator> equal_range(const key_type& key) const
1100 {
1101 return tree_.equal_range(key);
1102 }
1103
1104 template<class K>
1105 pair<iterator, iterator> equal_range(
1106 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1107 )
1108 {
1109 return tree_.equal_range(key);
1110 }
1111
1112 template<class K>
1113 pair<const_iterator, const_iterator> equal_range(
1114 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1115 ) const
1116 {
1117 return tree_.equal_range(key);
1118 }
1119
1120 private:
1121 using tree_type = aux::rbtree<
1122 value_type, key_type, aux::key_value_key_extractor<key_type, mapped_type>,
1123 key_compare, allocator_type, size_type,
1124 iterator, const_iterator,
1125 aux::rbtree_multi_policy
1126 >;
1127
1128 tree_type tree_;
1129 allocator_type allocator_;
1130
1131 template<class K, class C, class A>
1132 friend bool operator==(const multimap<K, C, A>&,
1133 const multimap<K, C, A>&);
1134 };
1135
1136 template<class Key, class Compare, class Allocator>
1137 bool operator==(const multimap<Key, Compare, Allocator>& lhs,
1138 const multimap<Key, Compare, Allocator>& rhs)
1139 {
1140 return lhs.tree_.is_eq_to(rhs.tree_);
1141 }
1142
1143 template<class Key, class Compare, class Allocator>
1144 bool operator<(const multimap<Key, Compare, Allocator>& lhs,
1145 const multimap<Key, Compare, Allocator>& rhs)
1146 {
[026cb10]1147 return lexicographical_compare(
1148 lhs.begin(), lhs.end(),
1149 rhs.begin(), rhs.end(),
1150 lhs.value_comp()
1151 );
[7ca0410f]1152 }
1153
1154 template<class Key, class Compare, class Allocator>
1155 bool operator!=(const multimap<Key, Compare, Allocator>& lhs,
1156 const multimap<Key, Compare, Allocator>& rhs)
1157 {
1158 return !(lhs == rhs);
1159 }
1160
1161 template<class Key, class Compare, class Allocator>
1162 bool operator>(const multimap<Key, Compare, Allocator>& lhs,
1163 const multimap<Key, Compare, Allocator>& rhs)
1164 {
[026cb10]1165 return rhs < lhs;
[7ca0410f]1166 }
1167
1168 template<class Key, class Compare, class Allocator>
1169 bool operator>=(const multimap<Key, Compare, Allocator>& lhs,
1170 const multimap<Key, Compare, Allocator>& rhs)
1171 {
[026cb10]1172 return !(lhs < rhs);
[7ca0410f]1173 }
1174
1175 template<class Key, class Compare, class Allocator>
1176 bool operator<=(const multimap<Key, Compare, Allocator>& lhs,
1177 const multimap<Key, Compare, Allocator>& rhs)
1178 {
[026cb10]1179 return !(rhs < lhs);
[7ca0410f]1180 }
1181}
1182
1183#endif
Note: See TracBrowser for help on using the repository browser.