source: mainline/uspace/lib/cpp/include/impl/map.hpp@ 68cfab1

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

cpp: added map::at
  • Property mode set to 100644
File size: 36.3 KB
Line 
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
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 }
295
296 mapped_type& at(const key_type& key)
297 {
298 auto it = find(key);
299
300 // TODO: throw out_of_range if it == end()
301 return it->second;
302 }
303
304 const mapped_type& at(const key_type& key) const
305 {
306 auto it = find(key);
307
308 // TODO: throw out_of_range if it == end()
309 return it->second;
310 }
311
312 /**
313 * 23.4.4.4, modifiers:
314 */
315
316 template<class... Args>
317 pair<iterator, bool> emplace(Args&&... args)
318 {
319 return tree_.emplace(forward<Args>(args)...);
320 }
321
322 template<class... Args>
323 iterator emplace_hint(const_iterator, Args&&... args)
324 {
325 return emplace(forward<Args>(args)...).first;
326 }
327
328 pair<iterator, bool> insert(const value_type& val)
329 {
330 return tree_.insert(val);
331 }
332
333 pair<iterator, bool> insert(value_type&& val)
334 {
335 return tree_.insert(forward<value_type>(val));
336 }
337
338 template<class T>
339 pair<iterator, bool> insert(
340 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val)
341 {
342 return emplace(forward<T>(val));
343 }
344
345 iterator insert(const_iterator, const value_type& val)
346 {
347 return insert(val).first;
348 }
349
350 iterator insert(const_iterator, value_type&& val)
351 {
352 return insert(forward<value_type>(val)).first;
353 }
354
355 template<class T>
356 iterator insert(
357 const_iterator hint,
358 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
359 )
360 {
361 return emplace_hint(hint, forward<T>(val));
362 }
363
364 template<class InputIterator>
365 void insert(InputIterator first, InputIterator last)
366 {
367 while (first != last)
368 insert(*first++);
369 }
370
371 void insert(initializer_list<value_type> init)
372 {
373 insert(init.begin(), init.end());
374 }
375
376 template<class... Args>
377 pair<iterator, bool> try_emplace(const key_type& key, Args&&... args)
378 {
379 auto parent = tree_.find_parent_for_insertion(key);
380 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
381 return make_pair(iterator{parent, false}, false);
382 else
383 {
384 auto node = new node_type{value_type{key, forward<Args>(args)...}};
385 tree_.insert_node(node, parent);
386
387 return make_pair(iterator{node, false}, true);
388 }
389 }
390
391 template<class... Args>
392 pair<iterator, bool> try_emplace(key_type&& key, Args&&... args)
393 {
394 auto parent = tree_.find_parent_for_insertion(key);
395 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
396 return make_pair(iterator{parent, false}, false);
397 else
398 {
399 auto node = new node_type{value_type{move(key), forward<Args>(args)...}};
400 tree_.insert_node(node, parent);
401
402 return make_pair(iterator{node, false}, true);
403 }
404 }
405
406 template<class... Args>
407 iterator try_emplace(const_iterator, const key_type& key, Args&&... args)
408 {
409 return try_emplace(key, forward<Args>(args)...).first;
410 }
411
412 template<class... Args>
413 iterator try_emplace(const_iterator, key_type&& key, Args&&... args)
414 {
415 return try_emplace(move(key), forward<Args>(args)...).first;
416 }
417
418 template<class T>
419 pair<iterator, bool> insert_or_assign(const key_type& key, T&& val)
420 {
421 auto parent = tree_.find_parent_for_insertion(key);
422 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
423 {
424 parent->value = value_type{key, forward<T>(val)};
425
426 return make_pair(iterator{parent, false}, false);
427 }
428 else
429 {
430 auto node = new node_type{value_type{key, forward<T>(val)}};
431 tree_.insert_node(node, parent);
432
433 return make_pair(iterator{node, false}, true);
434 }
435 }
436
437 template<class T>
438 pair<iterator, bool> insert_or_assign(key_type&& key, T&& val)
439 {
440 auto parent = tree_.find_parent_for_insertion(key);
441 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
442 {
443 parent->value = value_type{move(key), forward<T>(val)};
444
445 return make_pair(iterator{parent, false}, false);
446 }
447 else
448 {
449 auto node = new node_type{value_type{move(key), forward<T>(val)}};
450 tree_.insert_node(node, parent);
451
452 return make_pair(iterator{node, false}, true);
453 }
454 }
455
456 template<class T>
457 iterator insert_or_assign(const_iterator, const key_type& key, T&& val)
458 {
459 return insert_or_assign(key, forward<T>(val)).first;
460 }
461
462 template<class T>
463 iterator insert_or_assign(const_iterator, key_type&& key, T&& val)
464 {
465 return insert_or_assign(move(key), forward<T>(val)).first;
466 }
467
468 iterator erase(const_iterator position)
469 {
470 return tree_.erase(position);
471 }
472
473 size_type erase(const key_type& key)
474 {
475 return tree_.erase(key);
476 }
477
478 iterator erase(const_iterator first, const_iterator last)
479 {
480 while (first != last)
481 first = erase(first);
482
483 return iterator{
484 first.node(), first.end()
485 };
486 }
487
488 void swap(map& other)
489 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
490 noexcept(std::swap(declval<key_compare>(), declval<key_compare>())))
491 {
492 tree_.swap(other.tree_);
493 std::swap(allocator_, other.allocator_);
494 }
495
496 void clear() noexcept
497 {
498 tree_.clear();
499 }
500
501 key_compare key_comp() const
502 {
503 return tree_.key_comp();
504 }
505
506 value_compare value_comp() const
507 {
508 return value_compare{tree_.key_comp()};
509 }
510
511 iterator find(const key_type& key)
512 {
513 return tree_.find(key);
514 }
515
516 const_iterator find(const key_type& key) const
517 {
518 return tree_.find(key);
519 }
520
521 template<class K>
522 iterator find(
523 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
524 )
525 {
526 return tree_.find(key);
527 }
528
529 template<class K>
530 const_iterator find(
531 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
532 ) const
533 {
534 return tree_.find(key);
535 }
536
537 size_type count(const key_type& key) const
538 {
539 return tree_.count(key);
540 }
541
542 template<class K>
543 size_type count(
544 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
545 ) const
546 {
547 return tree_.count(key);
548 }
549
550 iterator lower_bound(const key_type& key)
551 {
552 return tree_.lower_bound(key);
553 }
554
555 const_iterator lower_bound(const key_type& key) const
556 {
557 return tree_.lower_bound(key);
558 }
559
560 template<class K>
561 iterator lower_bound(
562 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
563 )
564 {
565 return tree_.lower_bound(key);
566 }
567
568 template<class K>
569 const_iterator lower_bound(
570 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
571 ) const
572 {
573 return tree_.lower_bound(key);
574 }
575
576 iterator upper_bound(const key_type& key)
577 {
578 return tree_.upper_bound(key);
579 }
580
581 const_iterator upper_bound(const key_type& key) const
582 {
583 return tree_.upper_bound(key);
584 }
585
586 template<class K>
587 iterator upper_bound(
588 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
589 )
590 {
591 return tree_.upper_bound(key);
592 }
593
594 template<class K>
595 const_iterator upper_bound(
596 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
597 ) const
598 {
599 return tree_.upper_bound(key);
600 }
601
602 pair<iterator, iterator> equal_range(const key_type& key)
603 {
604 return tree_.equal_range(key);
605 }
606
607 pair<const_iterator, const_iterator> equal_range(const key_type& key) const
608 {
609 return tree_.equal_range(key);
610 }
611
612 template<class K>
613 pair<iterator, iterator> equal_range(
614 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
615 )
616 {
617 return tree_.equal_range(key);
618 }
619
620 template<class K>
621 pair<const_iterator, const_iterator> equal_range(
622 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
623 ) const
624 {
625 return tree_.equal_range(key);
626 }
627
628 private:
629 using tree_type = aux::rbtree<
630 value_type, key_type, aux::key_value_key_extractor<key_type, mapped_type>,
631 key_compare, allocator_type, size_type,
632 iterator, const_iterator,
633 aux::rbtree_single_policy
634 >;
635
636 using node_type = typename tree_type::node_type;
637
638 tree_type tree_;
639 allocator_type allocator_;
640
641 template<class K, class C, class A>
642 friend bool operator==(const map<K, C, A>&,
643 const map<K, C, A>&);
644 };
645
646 template<class Key, class Compare, class Allocator>
647 bool operator==(const map<Key, Compare, Allocator>& lhs,
648 const map<Key, Compare, Allocator>& rhs)
649 {
650 return lhs.tree_.is_eq_to(rhs.tree_);
651 }
652
653 template<class Key, class Compare, class Allocator>
654 bool operator<(const map<Key, Compare, Allocator>& lhs,
655 const map<Key, Compare, Allocator>& rhs)
656 {
657 return lexicographical_compare(
658 lhs.begin(), lhs.end(),
659 rhs.begin(), rhs.end(),
660 lhs.value_comp()
661 );
662 }
663
664 template<class Key, class Compare, class Allocator>
665 bool operator!=(const map<Key, Compare, Allocator>& lhs,
666 const map<Key, Compare, Allocator>& rhs)
667 {
668 return !(lhs == rhs);
669 }
670
671 template<class Key, class Compare, class Allocator>
672 bool operator>(const map<Key, Compare, Allocator>& lhs,
673 const map<Key, Compare, Allocator>& rhs)
674 {
675 return rhs < lhs;
676 }
677
678 template<class Key, class Compare, class Allocator>
679 bool operator>=(const map<Key, Compare, Allocator>& lhs,
680 const map<Key, Compare, Allocator>& rhs)
681 {
682 return !(lhs < rhs);
683 }
684
685 template<class Key, class Compare, class Allocator>
686 bool operator<=(const map<Key, Compare, Allocator>& lhs,
687 const map<Key, Compare, Allocator>& rhs)
688 {
689 return !(rhs < lhs);
690 }
691
692 /**
693 * 23.4.5, class template multimap:
694 */
695
696 template<
697 class Key, class Value,
698 class Compare = less<Key>,
699 class Alloc = allocator<pair<const Key, Value>>
700 >
701 class multimap
702 {
703 public:
704 using key_type = Key;
705 using mapped_type = Value;
706 using value_type = pair<const key_type, mapped_type>;
707 using key_compare = Compare;
708 using allocator_type = Alloc;
709 using pointer = typename allocator_traits<allocator_type>::pointer;
710 using const_pointer = typename allocator_traits<allocator_type>::const_pointer;
711 using reference = value_type&;
712 using const_reference = const value_type&;
713 using size_type = size_t;
714 using difference_type = ptrdiff_t;
715
716 class value_compare
717 {
718 friend class multimap;
719
720 protected:
721 key_compare comp;
722
723 value_compare(key_compare c)
724 : comp{c}
725 { /* DUMMY BODY */ }
726
727 public:
728 using result_type = bool;
729 using first_argument_type = value_type;
730 using second_argument_type = value_type;
731
732 bool operator()(const value_type& lhs, const value_type& rhs) const
733 {
734 return comp(lhs.first, rhs.first);
735 }
736 };
737
738 using iterator = aux::rbtree_iterator<
739 value_type, reference, pointer, size_type
740 >;
741 using const_iterator = aux::rbtree_const_iterator<
742 value_type, const_reference, const_pointer, size_type
743 >;
744
745 using reverse_iterator = std::reverse_iterator<iterator>;
746 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
747
748 multimap()
749 : multimap{key_compare{}}
750 { /* DUMMY BODY */ }
751
752 explicit multimap(const key_compare& comp,
753 const allocator_type& alloc = allocator_type{})
754 : tree_{comp}, allocator_{alloc}
755 { /* DUMMY BODY */ }
756
757 template<class InputIterator>
758 multimap(InputIterator first, InputIterator last,
759 const key_compare& comp = key_compare{},
760 const allocator_type& alloc = allocator_type{})
761 : multimap{comp, alloc}
762 {
763 insert(first, last);
764 }
765
766 multimap(const multimap& other)
767 : multimap{other, other.allocator_}
768 { /* DUMMY BODY */ }
769
770 multimap(multimap&& other)
771 : tree_{move(other.tree_)}, allocator_{move(other.allocator_)}
772 { /* DUMMY BODY */ }
773
774 explicit multimap(const allocator_type& alloc)
775 : tree_{}, allocator_{alloc}
776 { /* DUMMY BODY */ }
777
778 multimap(const multimap& other, const allocator_type& alloc)
779 : tree_{other.tree_}, allocator_{alloc}
780 { /* DUMMY BODY */ }
781
782 multimap(multimap&& other, const allocator_type& alloc)
783 : tree_{move(other.tree_)}, allocator_{alloc}
784 { /* DUMMY BODY */ }
785
786 multimap(initializer_list<value_type> init,
787 const key_compare& comp = key_compare{},
788 const allocator_type& alloc = allocator_type{})
789 : multimap{comp, alloc}
790 {
791 insert(init.begin(), init.end());
792 }
793
794 template<class InputIterator>
795 multimap(InputIterator first, InputIterator last,
796 const allocator_type& alloc)
797 : multimap{first, last, key_compare{}, alloc}
798 { /* DUMMY BODY */ }
799
800 multimap(initializer_list<value_type> init,
801 const allocator_type& alloc)
802 : multimap{init, key_compare{}, alloc}
803 { /* DUMMY BODY */ }
804
805 ~multimap()
806 { /* DUMMY BODY */ }
807
808 multimap& operator=(const multimap& other)
809 {
810 tree_ = other.tree_;
811 allocator_ = other.allocator_;
812
813 return *this;
814 }
815
816 multimap& operator=(multimap&& other)
817 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
818 is_nothrow_move_assignable<key_compare>::value)
819 {
820 tree_ = move(other.tree_);
821 allocator_ = move(other.allocator_);
822
823 return *this;
824 }
825
826 multimap& operator=(initializer_list<value_type>& init)
827 {
828 tree_.clear();
829
830 insert(init.begin(), init.end());
831
832 return *this;
833 }
834
835 allocator_type get_allocator() const noexcept
836 {
837 return allocator_;
838 }
839
840 iterator begin() noexcept
841 {
842 return tree_.begin();
843 }
844
845 const_iterator begin() const noexcept
846 {
847 return tree_.begin();
848 }
849
850 iterator end() noexcept
851 {
852 return tree_.end();
853 }
854
855 const_iterator end() const noexcept
856 {
857 return tree_.end();
858 }
859
860 reverse_iterator rbegin() noexcept
861 {
862 return tree_.rbegin();
863 }
864
865 const_reverse_iterator rbegin() const noexcept
866 {
867 return tree_.rbegin();
868 }
869
870 reverse_iterator rend() noexcept
871 {
872 return tree_.rend();
873 }
874
875 const_reverse_iterator rend() const noexcept
876 {
877 return tree_.rend();
878 }
879
880 const_iterator cbegin() const noexcept
881 {
882 return tree_.cbegin();
883 }
884
885 const_iterator cend() const noexcept
886 {
887 return tree_.cend();
888 }
889
890 const_reverse_iterator crbegin() const noexcept
891 {
892 return tree_.crbegin();
893 }
894
895 const_reverse_iterator crend() const noexcept
896 {
897 return tree_.crend();
898 }
899
900 bool empty() const noexcept
901 {
902 return tree_.empty();
903 }
904
905 size_type size() const noexcept
906 {
907 return tree_.size();
908 }
909
910 size_type max_size() const noexcept
911 {
912 return tree_.max_size(allocator_);
913 }
914
915 template<class... Args>
916 iterator emplace(Args&&... args)
917 {
918 return tree_.emplace(forward<Args>(args)...);
919 }
920
921 template<class... Args>
922 iterator emplace_hint(const_iterator, Args&&... args)
923 {
924 return emplace(forward<Args>(args)...);
925 }
926
927 iterator insert(const value_type& val)
928 {
929 return tree_.insert(val);
930 }
931
932 iterator insert(value_type&& val)
933 {
934 return tree_.insert(forward<value_type>(val));
935 }
936
937 template<class T>
938 iterator insert(
939 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
940 )
941 {
942 return emplace(forward<T>(val));
943 }
944
945 iterator insert(const_iterator, const value_type& val)
946 {
947 return insert(val);
948 }
949
950 iterator insert(const_iterator, value_type&& val)
951 {
952 return insert(forward<value_type>(val));
953 }
954
955 template<class T>
956 iterator insert(
957 const_iterator hint,
958 enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
959 )
960 {
961 return emplace_hint(hint, forward<T>(val));
962 }
963
964 template<class InputIterator>
965 void insert(InputIterator first, InputIterator last)
966 {
967 while (first != last)
968 insert(*first++);
969 }
970
971 void insert(initializer_list<value_type> init)
972 {
973 insert(init.begin(), init.end());
974 }
975
976 iterator erase(const_iterator position)
977 {
978 return tree_.erase(position);
979 }
980
981 size_type erase(const key_type& key)
982 {
983 return tree_.erase(key);
984 }
985
986 iterator erase(const_iterator first, const_iterator last)
987 {
988 while (first != last)
989 first = erase(first);
990
991 return iterator{
992 first.node(), first.end()
993 };
994 }
995
996 void swap(multimap& other)
997 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
998 noexcept(std::swap(declval<key_compare>(), declval<key_compare>())))
999 {
1000 tree_.swap(other.tree_);
1001 std::swap(allocator_, other.allocator_);
1002 }
1003
1004 void clear() noexcept
1005 {
1006 tree_.clear();
1007 }
1008
1009 key_compare key_comp() const
1010 {
1011 return tree_.key_comp();
1012 }
1013
1014 value_compare value_comp() const
1015 {
1016 return value_compare{tree_.key_comp()};
1017 }
1018
1019 iterator find(const key_type& key)
1020 {
1021 return tree_.find(key);
1022 }
1023
1024 const_iterator find(const key_type& key) const
1025 {
1026 return tree_.find(key);
1027 }
1028
1029 template<class K>
1030 iterator find(
1031 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1032 )
1033 {
1034 return tree_.find(key);
1035 }
1036
1037 template<class K>
1038 const_iterator find(
1039 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1040 ) const
1041 {
1042 return tree_.find(key);
1043 }
1044
1045 size_type count(const key_type& key) const
1046 {
1047 return tree_.count(key);
1048 }
1049
1050 template<class K>
1051 size_type count(
1052 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1053 ) const
1054 {
1055 return tree_.count(key);
1056 }
1057
1058 iterator lower_bound(const key_type& key)
1059 {
1060 return tree_.lower_bound(key);
1061 }
1062
1063 const_iterator lower_bound(const key_type& key) const
1064 {
1065 return tree_.lower_bound(key);
1066 }
1067
1068 template<class K>
1069 iterator lower_bound(
1070 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1071 )
1072 {
1073 return tree_.lower_bound(key);
1074 }
1075
1076 template<class K>
1077 const_iterator lower_bound(
1078 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1079 ) const
1080 {
1081 return tree_.lower_bound(key);
1082 }
1083
1084 iterator upper_bound(const key_type& key)
1085 {
1086 return tree_.upper_bound(key);
1087 }
1088
1089 const_iterator upper_bound(const key_type& key) const
1090 {
1091 return tree_.upper_bound(key);
1092 }
1093
1094 template<class K>
1095 iterator upper_bound(
1096 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1097 )
1098 {
1099 return tree_.upper_bound(key);
1100 }
1101
1102 template<class K>
1103 const_iterator upper_bound(
1104 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1105 ) const
1106 {
1107 return tree_.upper_bound(key);
1108 }
1109
1110 pair<iterator, iterator> equal_range(const key_type& key)
1111 {
1112 return tree_.equal_range(key);
1113 }
1114
1115 pair<const_iterator, const_iterator> equal_range(const key_type& key) const
1116 {
1117 return tree_.equal_range(key);
1118 }
1119
1120 template<class K>
1121 pair<iterator, iterator> equal_range(
1122 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1123 )
1124 {
1125 return tree_.equal_range(key);
1126 }
1127
1128 template<class K>
1129 pair<const_iterator, const_iterator> equal_range(
1130 enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
1131 ) const
1132 {
1133 return tree_.equal_range(key);
1134 }
1135
1136 private:
1137 using tree_type = aux::rbtree<
1138 value_type, key_type, aux::key_value_key_extractor<key_type, mapped_type>,
1139 key_compare, allocator_type, size_type,
1140 iterator, const_iterator,
1141 aux::rbtree_multi_policy
1142 >;
1143
1144 tree_type tree_;
1145 allocator_type allocator_;
1146
1147 template<class K, class C, class A>
1148 friend bool operator==(const multimap<K, C, A>&,
1149 const multimap<K, C, A>&);
1150 };
1151
1152 template<class Key, class Compare, class Allocator>
1153 bool operator==(const multimap<Key, Compare, Allocator>& lhs,
1154 const multimap<Key, Compare, Allocator>& rhs)
1155 {
1156 return lhs.tree_.is_eq_to(rhs.tree_);
1157 }
1158
1159 template<class Key, class Compare, class Allocator>
1160 bool operator<(const multimap<Key, Compare, Allocator>& lhs,
1161 const multimap<Key, Compare, Allocator>& rhs)
1162 {
1163 return lexicographical_compare(
1164 lhs.begin(), lhs.end(),
1165 rhs.begin(), rhs.end(),
1166 lhs.value_comp()
1167 );
1168 }
1169
1170 template<class Key, class Compare, class Allocator>
1171 bool operator!=(const multimap<Key, Compare, Allocator>& lhs,
1172 const multimap<Key, Compare, Allocator>& rhs)
1173 {
1174 return !(lhs == rhs);
1175 }
1176
1177 template<class Key, class Compare, class Allocator>
1178 bool operator>(const multimap<Key, Compare, Allocator>& lhs,
1179 const multimap<Key, Compare, Allocator>& rhs)
1180 {
1181 return rhs < lhs;
1182 }
1183
1184 template<class Key, class Compare, class Allocator>
1185 bool operator>=(const multimap<Key, Compare, Allocator>& lhs,
1186 const multimap<Key, Compare, Allocator>& rhs)
1187 {
1188 return !(lhs < rhs);
1189 }
1190
1191 template<class Key, class Compare, class Allocator>
1192 bool operator<=(const multimap<Key, Compare, Allocator>& lhs,
1193 const multimap<Key, Compare, Allocator>& rhs)
1194 {
1195 return !(rhs < lhs);
1196 }
1197}
1198
1199#endif
Note: See TracBrowser for help on using the repository browser.