2 //===----------------------------- map ------------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
21 template <class Key, class T, class Compare = less<Key>,
22 class Allocator = allocator<pair<const Key, T>>>
28 typedef T mapped_type;
29 typedef pair<const key_type, mapped_type> value_type;
30 typedef Compare key_compare;
31 typedef Allocator allocator_type;
32 typedef typename allocator_type::reference reference;
33 typedef typename allocator_type::const_reference const_reference;
34 typedef typename allocator_type::pointer pointer;
35 typedef typename allocator_type::const_pointer const_pointer;
36 typedef typename allocator_type::size_type size_type;
37 typedef typename allocator_type::difference_type difference_type;
39 typedef implementation-defined iterator;
40 typedef implementation-defined const_iterator;
41 typedef std::reverse_iterator<iterator> reverse_iterator;
42 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
45 : public binary_function<value_type, value_type, bool>
51 value_compare(key_compare c);
53 bool operator()(const value_type& x, const value_type& y) const;
56 // construct/copy/destroy:
59 is_nothrow_default_constructible<allocator_type>::value &&
60 is_nothrow_default_constructible<key_compare>::value &&
61 is_nothrow_copy_constructible<key_compare>::value);
62 explicit map(const key_compare& comp);
63 map(const key_compare& comp, const allocator_type& a);
64 template <class InputIterator>
65 map(InputIterator first, InputIterator last,
66 const key_compare& comp = key_compare());
67 template <class InputIterator>
68 map(InputIterator first, InputIterator last,
69 const key_compare& comp, const allocator_type& a);
73 is_nothrow_move_constructible<allocator_type>::value &&
74 is_nothrow_move_constructible<key_compare>::value);
75 explicit map(const allocator_type& a);
76 map(const map& m, const allocator_type& a);
77 map(map&& m, const allocator_type& a);
78 map(initializer_list<value_type> il, const key_compare& comp = key_compare());
79 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
80 template <class InputIterator>
81 map(InputIterator first, InputIterator last, const allocator_type& a)
82 : map(first, last, Compare(), a) {} // C++14
83 map(initializer_list<value_type> il, const allocator_type& a)
84 : map(il, Compare(), a) {} // C++14
87 map& operator=(const map& m);
88 map& operator=(map&& m)
90 allocator_type::propagate_on_container_move_assignment::value &&
91 is_nothrow_move_assignable<allocator_type>::value &&
92 is_nothrow_move_assignable<key_compare>::value);
93 map& operator=(initializer_list<value_type> il);
96 iterator begin() noexcept;
97 const_iterator begin() const noexcept;
98 iterator end() noexcept;
99 const_iterator end() const noexcept;
101 reverse_iterator rbegin() noexcept;
102 const_reverse_iterator rbegin() const noexcept;
103 reverse_iterator rend() noexcept;
104 const_reverse_iterator rend() const noexcept;
106 const_iterator cbegin() const noexcept;
107 const_iterator cend() const noexcept;
108 const_reverse_iterator crbegin() const noexcept;
109 const_reverse_iterator crend() const noexcept;
112 bool empty() const noexcept;
113 size_type size() const noexcept;
114 size_type max_size() const noexcept;
117 mapped_type& operator[](const key_type& k);
118 mapped_type& operator[](key_type&& k);
120 mapped_type& at(const key_type& k);
121 const mapped_type& at(const key_type& k) const;
124 template <class... Args>
125 pair<iterator, bool> emplace(Args&&... args);
126 template <class... Args>
127 iterator emplace_hint(const_iterator position, Args&&... args);
128 pair<iterator, bool> insert(const value_type& v);
130 pair<iterator, bool> insert(P&& p);
131 iterator insert(const_iterator position, const value_type& v);
133 iterator insert(const_iterator position, P&& p);
134 template <class InputIterator>
135 void insert(InputIterator first, InputIterator last);
136 void insert(initializer_list<value_type> il);
138 iterator erase(const_iterator position);
139 size_type erase(const key_type& k);
140 iterator erase(const_iterator first, const_iterator last);
141 void clear() noexcept;
145 __is_nothrow_swappable<key_compare>::value &&
146 (!allocator_type::propagate_on_container_swap::value ||
147 __is_nothrow_swappable<allocator_type>::value));
150 allocator_type get_allocator() const noexcept;
151 key_compare key_comp() const;
152 value_compare value_comp() const;
155 iterator find(const key_type& k);
156 const_iterator find(const key_type& k) const;
158 iterator find(const K& x); // C++14
160 const_iterator find(const K& x) const; // C++14
162 size_type count(const K& x) const; // C++14
164 size_type count(const key_type& k) const;
165 iterator lower_bound(const key_type& k);
166 const_iterator lower_bound(const key_type& k) const;
168 iterator lower_bound(const K& x); // C++14
170 const_iterator lower_bound(const K& x) const; // C++14
172 iterator upper_bound(const key_type& k);
173 const_iterator upper_bound(const key_type& k) const;
175 iterator upper_bound(const K& x); // C++14
177 const_iterator upper_bound(const K& x) const; // C++14
179 pair<iterator,iterator> equal_range(const key_type& k);
180 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
182 pair<iterator,iterator> equal_range(const K& x); // C++14
184 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
187 template <class Key, class T, class Compare, class Allocator>
189 operator==(const map<Key, T, Compare, Allocator>& x,
190 const map<Key, T, Compare, Allocator>& y);
192 template <class Key, class T, class Compare, class Allocator>
194 operator< (const map<Key, T, Compare, Allocator>& x,
195 const map<Key, T, Compare, Allocator>& y);
197 template <class Key, class T, class Compare, class Allocator>
199 operator!=(const map<Key, T, Compare, Allocator>& x,
200 const map<Key, T, Compare, Allocator>& y);
202 template <class Key, class T, class Compare, class Allocator>
204 operator> (const map<Key, T, Compare, Allocator>& x,
205 const map<Key, T, Compare, Allocator>& y);
207 template <class Key, class T, class Compare, class Allocator>
209 operator>=(const map<Key, T, Compare, Allocator>& x,
210 const map<Key, T, Compare, Allocator>& y);
212 template <class Key, class T, class Compare, class Allocator>
214 operator<=(const map<Key, T, Compare, Allocator>& x,
215 const map<Key, T, Compare, Allocator>& y);
217 // specialized algorithms:
218 template <class Key, class T, class Compare, class Allocator>
220 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
221 noexcept(noexcept(x.swap(y)));
223 template <class Key, class T, class Compare = less<Key>,
224 class Allocator = allocator<pair<const Key, T>>>
229 typedef Key key_type;
230 typedef T mapped_type;
231 typedef pair<const key_type,mapped_type> value_type;
232 typedef Compare key_compare;
233 typedef Allocator allocator_type;
234 typedef typename allocator_type::reference reference;
235 typedef typename allocator_type::const_reference const_reference;
236 typedef typename allocator_type::size_type size_type;
237 typedef typename allocator_type::difference_type difference_type;
238 typedef typename allocator_type::pointer pointer;
239 typedef typename allocator_type::const_pointer const_pointer;
241 typedef implementation-defined iterator;
242 typedef implementation-defined const_iterator;
243 typedef std::reverse_iterator<iterator> reverse_iterator;
244 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
247 : public binary_function<value_type,value_type,bool>
249 friend class multimap;
252 value_compare(key_compare c);
254 bool operator()(const value_type& x, const value_type& y) const;
257 // construct/copy/destroy:
260 is_nothrow_default_constructible<allocator_type>::value &&
261 is_nothrow_default_constructible<key_compare>::value &&
262 is_nothrow_copy_constructible<key_compare>::value);
263 explicit multimap(const key_compare& comp);
264 multimap(const key_compare& comp, const allocator_type& a);
265 template <class InputIterator>
266 multimap(InputIterator first, InputIterator last, const key_compare& comp);
267 template <class InputIterator>
268 multimap(InputIterator first, InputIterator last, const key_compare& comp,
269 const allocator_type& a);
270 multimap(const multimap& m);
271 multimap(multimap&& m)
273 is_nothrow_move_constructible<allocator_type>::value &&
274 is_nothrow_move_constructible<key_compare>::value);
275 explicit multimap(const allocator_type& a);
276 multimap(const multimap& m, const allocator_type& a);
277 multimap(multimap&& m, const allocator_type& a);
278 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
279 multimap(initializer_list<value_type> il, const key_compare& comp,
280 const allocator_type& a);
281 template <class InputIterator>
282 multimap(InputIterator first, InputIterator last, const allocator_type& a)
283 : multimap(first, last, Compare(), a) {} // C++14
284 multimap(initializer_list<value_type> il, const allocator_type& a)
285 : multimap(il, Compare(), a) {} // C++14
288 multimap& operator=(const multimap& m);
289 multimap& operator=(multimap&& m)
291 allocator_type::propagate_on_container_move_assignment::value &&
292 is_nothrow_move_assignable<allocator_type>::value &&
293 is_nothrow_move_assignable<key_compare>::value);
294 multimap& operator=(initializer_list<value_type> il);
297 iterator begin() noexcept;
298 const_iterator begin() const noexcept;
299 iterator end() noexcept;
300 const_iterator end() const noexcept;
302 reverse_iterator rbegin() noexcept;
303 const_reverse_iterator rbegin() const noexcept;
304 reverse_iterator rend() noexcept;
305 const_reverse_iterator rend() const noexcept;
307 const_iterator cbegin() const noexcept;
308 const_iterator cend() const noexcept;
309 const_reverse_iterator crbegin() const noexcept;
310 const_reverse_iterator crend() const noexcept;
313 bool empty() const noexcept;
314 size_type size() const noexcept;
315 size_type max_size() const noexcept;
318 template <class... Args>
319 iterator emplace(Args&&... args);
320 template <class... Args>
321 iterator emplace_hint(const_iterator position, Args&&... args);
322 iterator insert(const value_type& v);
324 iterator insert(P&& p);
325 iterator insert(const_iterator position, const value_type& v);
327 iterator insert(const_iterator position, P&& p);
328 template <class InputIterator>
329 void insert(InputIterator first, InputIterator last);
330 void insert(initializer_list<value_type> il);
332 iterator erase(const_iterator position);
333 size_type erase(const key_type& k);
334 iterator erase(const_iterator first, const_iterator last);
335 void clear() noexcept;
337 void swap(multimap& m)
339 __is_nothrow_swappable<key_compare>::value &&
340 (!allocator_type::propagate_on_container_swap::value ||
341 __is_nothrow_swappable<allocator_type>::value));
344 allocator_type get_allocator() const noexcept;
345 key_compare key_comp() const;
346 value_compare value_comp() const;
349 iterator find(const key_type& k);
350 const_iterator find(const key_type& k) const;
352 iterator find(const K& x); // C++14
354 const_iterator find(const K& x) const; // C++14
356 size_type count(const K& x) const; // C++14
358 size_type count(const key_type& k) const;
359 iterator lower_bound(const key_type& k);
360 const_iterator lower_bound(const key_type& k) const;
362 iterator lower_bound(const K& x); // C++14
364 const_iterator lower_bound(const K& x) const; // C++14
366 iterator upper_bound(const key_type& k);
367 const_iterator upper_bound(const key_type& k) const;
369 iterator upper_bound(const K& x); // C++14
371 const_iterator upper_bound(const K& x) const; // C++14
373 pair<iterator,iterator> equal_range(const key_type& k);
374 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
376 pair<iterator,iterator> equal_range(const K& x); // C++14
378 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
381 template <class Key, class T, class Compare, class Allocator>
383 operator==(const multimap<Key, T, Compare, Allocator>& x,
384 const multimap<Key, T, Compare, Allocator>& y);
386 template <class Key, class T, class Compare, class Allocator>
388 operator< (const multimap<Key, T, Compare, Allocator>& x,
389 const multimap<Key, T, Compare, Allocator>& y);
391 template <class Key, class T, class Compare, class Allocator>
393 operator!=(const multimap<Key, T, Compare, Allocator>& x,
394 const multimap<Key, T, Compare, Allocator>& y);
396 template <class Key, class T, class Compare, class Allocator>
398 operator> (const multimap<Key, T, Compare, Allocator>& x,
399 const multimap<Key, T, Compare, Allocator>& y);
401 template <class Key, class T, class Compare, class Allocator>
403 operator>=(const multimap<Key, T, Compare, Allocator>& x,
404 const multimap<Key, T, Compare, Allocator>& y);
406 template <class Key, class T, class Compare, class Allocator>
408 operator<=(const multimap<Key, T, Compare, Allocator>& x,
409 const multimap<Key, T, Compare, Allocator>& y);
411 // specialized algorithms:
412 template <class Key, class T, class Compare, class Allocator>
414 swap(multimap<Key, T, Compare, Allocator>& x,
415 multimap<Key, T, Compare, Allocator>& y)
416 noexcept(noexcept(x.swap(y)));
427 #include <functional>
428 #include <initializer_list>
430 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
431 #pragma GCC system_header
434 _LIBCPP_BEGIN_NAMESPACE_STD
436 template <class _Key, class _CP, class _Compare, bool = is_empty<_Compare>::value
437 #if __has_feature(is_final)
438 && !__is_final(_Compare)
441 class __map_value_compare
445 _LIBCPP_INLINE_VISIBILITY
446 __map_value_compare()
447 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
449 _LIBCPP_INLINE_VISIBILITY
450 __map_value_compare(_Compare c)
451 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
453 _LIBCPP_INLINE_VISIBILITY
454 const _Compare& key_comp() const _NOEXCEPT {return *this;}
455 _LIBCPP_INLINE_VISIBILITY
456 bool operator()(const _CP& __x, const _CP& __y) const
457 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y.__cc.first);}
458 _LIBCPP_INLINE_VISIBILITY
459 bool operator()(const _CP& __x, const _Key& __y) const
460 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y);}
461 _LIBCPP_INLINE_VISIBILITY
462 bool operator()(const _Key& __x, const _CP& __y) const
463 {return static_cast<const _Compare&>(*this)(__x, __y.__cc.first);}
465 #if _LIBCPP_STD_VER > 11
466 template <typename _K2>
467 _LIBCPP_INLINE_VISIBILITY
468 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
469 operator () ( const _K2& __x, const _CP& __y ) const
470 {return static_cast<const _Compare&>(*this) (__x, __y.__cc.first);}
472 template <typename _K2>
473 _LIBCPP_INLINE_VISIBILITY
474 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
475 operator () (const _CP& __x, const _K2& __y) const
476 {return static_cast<const _Compare&>(*this) (__x.__cc.first, __y);}
480 template <class _Key, class _CP, class _Compare>
481 class __map_value_compare<_Key, _CP, _Compare, false>
486 _LIBCPP_INLINE_VISIBILITY
487 __map_value_compare()
488 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
490 _LIBCPP_INLINE_VISIBILITY
491 __map_value_compare(_Compare c)
492 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
494 _LIBCPP_INLINE_VISIBILITY
495 const _Compare& key_comp() const _NOEXCEPT {return comp;}
497 _LIBCPP_INLINE_VISIBILITY
498 bool operator()(const _CP& __x, const _CP& __y) const
499 {return comp(__x.__cc.first, __y.__cc.first);}
500 _LIBCPP_INLINE_VISIBILITY
501 bool operator()(const _CP& __x, const _Key& __y) const
502 {return comp(__x.__cc.first, __y);}
503 _LIBCPP_INLINE_VISIBILITY
504 bool operator()(const _Key& __x, const _CP& __y) const
505 {return comp(__x, __y.__cc.first);}
507 #if _LIBCPP_STD_VER > 11
508 template <typename _K2>
509 _LIBCPP_INLINE_VISIBILITY
510 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
511 operator () ( const _K2& __x, const _CP& __y ) const
512 {return comp (__x, __y.__cc.first);}
514 template <typename _K2>
515 _LIBCPP_INLINE_VISIBILITY
516 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
517 operator () (const _CP& __x, const _K2& __y) const
518 {return comp (__x.__cc.first, __y);}
522 template <class _Allocator>
523 class __map_node_destructor
525 typedef _Allocator allocator_type;
526 typedef allocator_traits<allocator_type> __alloc_traits;
527 typedef typename __alloc_traits::value_type::value_type value_type;
529 typedef typename __alloc_traits::pointer pointer;
531 typedef typename value_type::value_type::first_type first_type;
532 typedef typename value_type::value_type::second_type second_type;
534 allocator_type& __na_;
536 __map_node_destructor& operator=(const __map_node_destructor&);
539 bool __first_constructed;
540 bool __second_constructed;
542 _LIBCPP_INLINE_VISIBILITY
543 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
545 __first_constructed(false),
546 __second_constructed(false)
549 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
550 _LIBCPP_INLINE_VISIBILITY
551 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
553 __first_constructed(__x.__value_constructed),
554 __second_constructed(__x.__value_constructed)
556 __x.__value_constructed = false;
558 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
560 _LIBCPP_INLINE_VISIBILITY
561 void operator()(pointer __p) _NOEXCEPT
563 if (__second_constructed)
564 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
565 if (__first_constructed)
566 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
568 __alloc_traits::deallocate(__na_, __p, 1);
572 template <class _Key, class _Tp, class _Compare, class _Allocator>
574 template <class _Key, class _Tp, class _Compare, class _Allocator>
576 template <class _TreeIterator> class __map_const_iterator;
578 #if __cplusplus >= 201103L
580 template <class _Key, class _Tp>
583 typedef _Key key_type;
584 typedef _Tp mapped_type;
585 typedef pair<const key_type, mapped_type> value_type;
586 typedef pair<key_type, mapped_type> __nc_value_type;
589 __nc_value_type __nc;
591 template <class ..._Args>
592 _LIBCPP_INLINE_VISIBILITY
593 __value_type(_Args&& ...__args)
594 : __cc(std::forward<_Args>(__args)...) {}
596 _LIBCPP_INLINE_VISIBILITY
597 __value_type(const __value_type& __v)
600 _LIBCPP_INLINE_VISIBILITY
601 __value_type(__value_type& __v)
604 _LIBCPP_INLINE_VISIBILITY
605 __value_type(__value_type&& __v)
606 : __nc(std::move(__v.__nc)) {}
608 _LIBCPP_INLINE_VISIBILITY
609 __value_type& operator=(const __value_type& __v)
610 {__nc = __v.__cc; return *this;}
612 _LIBCPP_INLINE_VISIBILITY
613 __value_type& operator=(__value_type&& __v)
614 {__nc = std::move(__v.__nc); return *this;}
616 _LIBCPP_INLINE_VISIBILITY
617 ~__value_type() {__cc.~value_type();}
622 template <class _Key, class _Tp>
625 typedef _Key key_type;
626 typedef _Tp mapped_type;
627 typedef pair<const key_type, mapped_type> value_type;
631 _LIBCPP_INLINE_VISIBILITY
635 _LIBCPP_INLINE_VISIBILITY
636 __value_type(const _A0& __a0)
639 template <class _A0, class _A1>
640 _LIBCPP_INLINE_VISIBILITY
641 __value_type(const _A0& __a0, const _A1& __a1)
642 : __cc(__a0, __a1) {}
647 template <class _TreeIterator>
648 class _LIBCPP_TYPE_VIS_ONLY __map_iterator
652 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
653 typedef const typename _TreeIterator::value_type::value_type::first_type __key_type;
654 typedef typename _TreeIterator::value_type::value_type::second_type __mapped_type;
656 typedef bidirectional_iterator_tag iterator_category;
657 typedef pair<__key_type, __mapped_type> value_type;
658 typedef typename _TreeIterator::difference_type difference_type;
659 typedef value_type& reference;
660 typedef typename __pointer_traits::template
661 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
664 rebind<value_type>::other
668 _LIBCPP_INLINE_VISIBILITY
669 __map_iterator() _NOEXCEPT {}
671 _LIBCPP_INLINE_VISIBILITY
672 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
674 _LIBCPP_INLINE_VISIBILITY
675 reference operator*() const {return __i_->__cc;}
676 _LIBCPP_INLINE_VISIBILITY
677 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
679 _LIBCPP_INLINE_VISIBILITY
680 __map_iterator& operator++() {++__i_; return *this;}
681 _LIBCPP_INLINE_VISIBILITY
682 __map_iterator operator++(int)
684 __map_iterator __t(*this);
689 _LIBCPP_INLINE_VISIBILITY
690 __map_iterator& operator--() {--__i_; return *this;}
691 _LIBCPP_INLINE_VISIBILITY
692 __map_iterator operator--(int)
694 __map_iterator __t(*this);
699 friend _LIBCPP_INLINE_VISIBILITY
700 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
701 {return __x.__i_ == __y.__i_;}
703 _LIBCPP_INLINE_VISIBILITY
704 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
705 {return __x.__i_ != __y.__i_;}
707 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
708 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
709 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
712 template <class _TreeIterator>
713 class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator
717 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
718 typedef const typename _TreeIterator::value_type::value_type::first_type __key_type;
719 typedef typename _TreeIterator::value_type::value_type::second_type __mapped_type;
721 typedef bidirectional_iterator_tag iterator_category;
722 typedef pair<__key_type, __mapped_type> value_type;
723 typedef typename _TreeIterator::difference_type difference_type;
724 typedef const value_type& reference;
725 typedef typename __pointer_traits::template
726 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
727 rebind<const value_type>
729 rebind<const value_type>::other
733 _LIBCPP_INLINE_VISIBILITY
734 __map_const_iterator() _NOEXCEPT {}
736 _LIBCPP_INLINE_VISIBILITY
737 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
738 _LIBCPP_INLINE_VISIBILITY
739 __map_const_iterator(
740 __map_iterator<typename _TreeIterator::__non_const_iterator> __i)
744 _LIBCPP_INLINE_VISIBILITY
745 reference operator*() const {return __i_->__cc;}
746 _LIBCPP_INLINE_VISIBILITY
747 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
749 _LIBCPP_INLINE_VISIBILITY
750 __map_const_iterator& operator++() {++__i_; return *this;}
751 _LIBCPP_INLINE_VISIBILITY
752 __map_const_iterator operator++(int)
754 __map_const_iterator __t(*this);
759 _LIBCPP_INLINE_VISIBILITY
760 __map_const_iterator& operator--() {--__i_; return *this;}
761 _LIBCPP_INLINE_VISIBILITY
762 __map_const_iterator operator--(int)
764 __map_const_iterator __t(*this);
769 friend _LIBCPP_INLINE_VISIBILITY
770 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
771 {return __x.__i_ == __y.__i_;}
772 friend _LIBCPP_INLINE_VISIBILITY
773 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
774 {return __x.__i_ != __y.__i_;}
776 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
777 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
778 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
781 template <class _Key, class _Tp, class _Compare = less<_Key>,
782 class _Allocator = allocator<pair<const _Key, _Tp> > >
783 class _LIBCPP_TYPE_VIS_ONLY map
787 typedef _Key key_type;
788 typedef _Tp mapped_type;
789 typedef pair<const key_type, mapped_type> value_type;
790 typedef pair<key_type, mapped_type> __nc_value_type;
791 typedef _Compare key_compare;
792 typedef _Allocator allocator_type;
793 typedef value_type& reference;
794 typedef const value_type& const_reference;
796 class _LIBCPP_TYPE_VIS_ONLY value_compare
797 : public binary_function<value_type, value_type, bool>
803 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
805 _LIBCPP_INLINE_VISIBILITY
806 bool operator()(const value_type& __x, const value_type& __y) const
807 {return comp(__x.first, __y.first);}
812 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
813 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
814 typedef typename allocator_traits<allocator_type>::template
815 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
816 rebind_alloc<__value_type>
818 rebind_alloc<__value_type>::other
821 typedef __tree<__value_type, __vc, __allocator_type> __base;
822 typedef typename __base::__node_traits __node_traits;
823 typedef allocator_traits<allocator_type> __alloc_traits;
828 typedef typename __alloc_traits::pointer pointer;
829 typedef typename __alloc_traits::const_pointer const_pointer;
830 typedef typename __alloc_traits::size_type size_type;
831 typedef typename __alloc_traits::difference_type difference_type;
832 typedef __map_iterator<typename __base::iterator> iterator;
833 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
834 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
835 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
837 _LIBCPP_INLINE_VISIBILITY
840 is_nothrow_default_constructible<allocator_type>::value &&
841 is_nothrow_default_constructible<key_compare>::value &&
842 is_nothrow_copy_constructible<key_compare>::value)
843 : __tree_(__vc(key_compare())) {}
845 _LIBCPP_INLINE_VISIBILITY
846 explicit map(const key_compare& __comp)
848 is_nothrow_default_constructible<allocator_type>::value &&
849 is_nothrow_copy_constructible<key_compare>::value)
850 : __tree_(__vc(__comp)) {}
852 _LIBCPP_INLINE_VISIBILITY
853 explicit map(const key_compare& __comp, const allocator_type& __a)
854 : __tree_(__vc(__comp), __a) {}
856 template <class _InputIterator>
857 _LIBCPP_INLINE_VISIBILITY
858 map(_InputIterator __f, _InputIterator __l,
859 const key_compare& __comp = key_compare())
860 : __tree_(__vc(__comp))
865 template <class _InputIterator>
866 _LIBCPP_INLINE_VISIBILITY
867 map(_InputIterator __f, _InputIterator __l,
868 const key_compare& __comp, const allocator_type& __a)
869 : __tree_(__vc(__comp), __a)
874 #if _LIBCPP_STD_VER > 11
875 template <class _InputIterator>
876 _LIBCPP_INLINE_VISIBILITY
877 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
878 : map(__f, __l, key_compare(), __a) {}
881 _LIBCPP_INLINE_VISIBILITY
883 : __tree_(__m.__tree_)
885 insert(__m.begin(), __m.end());
888 _LIBCPP_INLINE_VISIBILITY
889 map& operator=(const map& __m)
891 #if __cplusplus >= 201103L
892 __tree_ = __m.__tree_;
896 __tree_.value_comp() = __m.__tree_.value_comp();
897 __tree_.__copy_assign_alloc(__m.__tree_);
898 insert(__m.begin(), __m.end());
904 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
906 _LIBCPP_INLINE_VISIBILITY
908 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
909 : __tree_(_VSTD::move(__m.__tree_))
913 map(map&& __m, const allocator_type& __a);
915 _LIBCPP_INLINE_VISIBILITY
916 map& operator=(map&& __m)
917 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
919 __tree_ = _VSTD::move(__m.__tree_);
923 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
925 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
927 _LIBCPP_INLINE_VISIBILITY
928 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
929 : __tree_(__vc(__comp))
931 insert(__il.begin(), __il.end());
934 _LIBCPP_INLINE_VISIBILITY
935 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
936 : __tree_(__vc(__comp), __a)
938 insert(__il.begin(), __il.end());
941 #if _LIBCPP_STD_VER > 11
942 _LIBCPP_INLINE_VISIBILITY
943 map(initializer_list<value_type> __il, const allocator_type& __a)
944 : map(__il, key_compare(), __a) {}
947 _LIBCPP_INLINE_VISIBILITY
948 map& operator=(initializer_list<value_type> __il)
950 __tree_.__assign_unique(__il.begin(), __il.end());
954 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
956 _LIBCPP_INLINE_VISIBILITY
957 explicit map(const allocator_type& __a)
962 _LIBCPP_INLINE_VISIBILITY
963 map(const map& __m, const allocator_type& __a)
964 : __tree_(__m.__tree_.value_comp(), __a)
966 insert(__m.begin(), __m.end());
969 _LIBCPP_INLINE_VISIBILITY
970 iterator begin() _NOEXCEPT {return __tree_.begin();}
971 _LIBCPP_INLINE_VISIBILITY
972 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
973 _LIBCPP_INLINE_VISIBILITY
974 iterator end() _NOEXCEPT {return __tree_.end();}
975 _LIBCPP_INLINE_VISIBILITY
976 const_iterator end() const _NOEXCEPT {return __tree_.end();}
978 _LIBCPP_INLINE_VISIBILITY
979 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
980 _LIBCPP_INLINE_VISIBILITY
981 const_reverse_iterator rbegin() const _NOEXCEPT
982 {return const_reverse_iterator(end());}
983 _LIBCPP_INLINE_VISIBILITY
984 reverse_iterator rend() _NOEXCEPT
985 {return reverse_iterator(begin());}
986 _LIBCPP_INLINE_VISIBILITY
987 const_reverse_iterator rend() const _NOEXCEPT
988 {return const_reverse_iterator(begin());}
990 _LIBCPP_INLINE_VISIBILITY
991 const_iterator cbegin() const _NOEXCEPT {return begin();}
992 _LIBCPP_INLINE_VISIBILITY
993 const_iterator cend() const _NOEXCEPT {return end();}
994 _LIBCPP_INLINE_VISIBILITY
995 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
996 _LIBCPP_INLINE_VISIBILITY
997 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
999 _LIBCPP_INLINE_VISIBILITY
1000 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1001 _LIBCPP_INLINE_VISIBILITY
1002 size_type size() const _NOEXCEPT {return __tree_.size();}
1003 _LIBCPP_INLINE_VISIBILITY
1004 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1006 mapped_type& operator[](const key_type& __k);
1007 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1008 mapped_type& operator[](key_type&& __k);
1011 mapped_type& at(const key_type& __k);
1012 const mapped_type& at(const key_type& __k) const;
1014 _LIBCPP_INLINE_VISIBILITY
1015 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1016 _LIBCPP_INLINE_VISIBILITY
1017 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1018 _LIBCPP_INLINE_VISIBILITY
1019 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1021 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1022 #ifndef _LIBCPP_HAS_NO_VARIADICS
1024 template <class ..._Args>
1025 pair<iterator, bool>
1026 emplace(_Args&& ...__args);
1028 template <class ..._Args>
1030 emplace_hint(const_iterator __p, _Args&& ...__args);
1032 #endif // _LIBCPP_HAS_NO_VARIADICS
1034 template <class _Pp,
1035 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1036 _LIBCPP_INLINE_VISIBILITY
1037 pair<iterator, bool> insert(_Pp&& __p)
1038 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1040 template <class _Pp,
1041 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1042 _LIBCPP_INLINE_VISIBILITY
1043 iterator insert(const_iterator __pos, _Pp&& __p)
1044 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1046 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1048 _LIBCPP_INLINE_VISIBILITY
1049 pair<iterator, bool>
1050 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1052 _LIBCPP_INLINE_VISIBILITY
1054 insert(const_iterator __p, const value_type& __v)
1055 {return __tree_.__insert_unique(__p.__i_, __v);}
1057 template <class _InputIterator>
1058 _LIBCPP_INLINE_VISIBILITY
1059 void insert(_InputIterator __f, _InputIterator __l)
1061 for (const_iterator __e = cend(); __f != __l; ++__f)
1062 insert(__e.__i_, *__f);
1065 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1067 _LIBCPP_INLINE_VISIBILITY
1068 void insert(initializer_list<value_type> __il)
1069 {insert(__il.begin(), __il.end());}
1071 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1073 _LIBCPP_INLINE_VISIBILITY
1074 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1075 _LIBCPP_INLINE_VISIBILITY
1076 size_type erase(const key_type& __k)
1077 {return __tree_.__erase_unique(__k);}
1078 _LIBCPP_INLINE_VISIBILITY
1079 iterator erase(const_iterator __f, const_iterator __l)
1080 {return __tree_.erase(__f.__i_, __l.__i_);}
1081 _LIBCPP_INLINE_VISIBILITY
1082 void clear() _NOEXCEPT {__tree_.clear();}
1084 _LIBCPP_INLINE_VISIBILITY
1086 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1087 {__tree_.swap(__m.__tree_);}
1089 _LIBCPP_INLINE_VISIBILITY
1090 iterator find(const key_type& __k) {return __tree_.find(__k);}
1091 _LIBCPP_INLINE_VISIBILITY
1092 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1093 #if _LIBCPP_STD_VER > 11
1094 template <typename _K2>
1095 _LIBCPP_INLINE_VISIBILITY
1096 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1097 find(const _K2& __k) {return __tree_.find(__k);}
1098 template <typename _K2>
1099 _LIBCPP_INLINE_VISIBILITY
1100 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1101 find(const _K2& __k) const {return __tree_.find(__k);}
1104 _LIBCPP_INLINE_VISIBILITY
1105 size_type count(const key_type& __k) const
1106 {return __tree_.__count_unique(__k);}
1107 #if _LIBCPP_STD_VER > 11
1108 template <typename _K2>
1109 _LIBCPP_INLINE_VISIBILITY
1110 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1111 count(const _K2& __k) {return __tree_.__count_unique(__k);}
1113 _LIBCPP_INLINE_VISIBILITY
1114 iterator lower_bound(const key_type& __k)
1115 {return __tree_.lower_bound(__k);}
1116 _LIBCPP_INLINE_VISIBILITY
1117 const_iterator lower_bound(const key_type& __k) const
1118 {return __tree_.lower_bound(__k);}
1119 #if _LIBCPP_STD_VER > 11
1120 template <typename _K2>
1121 _LIBCPP_INLINE_VISIBILITY
1122 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1123 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1125 template <typename _K2>
1126 _LIBCPP_INLINE_VISIBILITY
1127 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1128 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1131 _LIBCPP_INLINE_VISIBILITY
1132 iterator upper_bound(const key_type& __k)
1133 {return __tree_.upper_bound(__k);}
1134 _LIBCPP_INLINE_VISIBILITY
1135 const_iterator upper_bound(const key_type& __k) const
1136 {return __tree_.upper_bound(__k);}
1137 #if _LIBCPP_STD_VER > 11
1138 template <typename _K2>
1139 _LIBCPP_INLINE_VISIBILITY
1140 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1141 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1142 template <typename _K2>
1143 _LIBCPP_INLINE_VISIBILITY
1144 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1145 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1148 _LIBCPP_INLINE_VISIBILITY
1149 pair<iterator,iterator> equal_range(const key_type& __k)
1150 {return __tree_.__equal_range_unique(__k);}
1151 _LIBCPP_INLINE_VISIBILITY
1152 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1153 {return __tree_.__equal_range_unique(__k);}
1154 #if _LIBCPP_STD_VER > 11
1155 template <typename _K2>
1156 _LIBCPP_INLINE_VISIBILITY
1157 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1158 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
1159 template <typename _K2>
1160 _LIBCPP_INLINE_VISIBILITY
1161 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1162 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1166 typedef typename __base::__node __node;
1167 typedef typename __base::__node_allocator __node_allocator;
1168 typedef typename __base::__node_pointer __node_pointer;
1169 typedef typename __base::__node_const_pointer __node_const_pointer;
1170 typedef typename __base::__node_base_pointer __node_base_pointer;
1171 typedef typename __base::__node_base_const_pointer __node_base_const_pointer;
1172 typedef __map_node_destructor<__node_allocator> _Dp;
1173 typedef unique_ptr<__node, _Dp> __node_holder;
1175 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1176 __node_holder __construct_node();
1177 template <class _A0>
1178 __node_holder __construct_node(_A0&& __a0);
1179 __node_holder __construct_node_with_key(key_type&& __k);
1180 #ifndef _LIBCPP_HAS_NO_VARIADICS
1181 template <class _A0, class _A1, class ..._Args>
1182 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1183 #endif // _LIBCPP_HAS_NO_VARIADICS
1185 __node_holder __construct_node_with_key(const key_type& __k);
1187 __node_base_pointer&
1188 __find_equal_key(__node_base_pointer& __parent, const key_type& __k);
1189 __node_base_const_pointer
1190 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
1193 // Find place to insert if __k doesn't exist
1194 // Set __parent to parent of null leaf
1195 // Return reference to null leaf
1196 // If __k exists, set parent to node of __k and return reference to node of __k
1197 template <class _Key, class _Tp, class _Compare, class _Allocator>
1198 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1199 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
1200 const key_type& __k)
1202 __node_pointer __nd = __tree_.__root();
1203 if (__nd != nullptr)
1207 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1209 if (__nd->__left_ != nullptr)
1210 __nd = static_cast<__node_pointer>(__nd->__left_);
1213 __parent = static_cast<__node_base_pointer>(__nd);
1214 return __parent->__left_;
1217 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1219 if (__nd->__right_ != nullptr)
1220 __nd = static_cast<__node_pointer>(__nd->__right_);
1223 __parent = static_cast<__node_base_pointer>(__nd);
1224 return __parent->__right_;
1229 __parent = static_cast<__node_base_pointer>(__nd);
1234 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1235 return __parent->__left_;
1239 // Set __parent to parent of null leaf and
1240 // return reference to null leaf iv __k does not exist.
1241 // If __k exists, set parent to node of __k and return reference to node of __k
1242 template <class _Key, class _Tp, class _Compare, class _Allocator>
1243 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer
1244 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent,
1245 const key_type& __k) const
1247 __node_const_pointer __nd = __tree_.__root();
1248 if (__nd != nullptr)
1252 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1254 if (__nd->__left_ != nullptr)
1255 __nd = static_cast<__node_pointer>(__nd->__left_);
1258 __parent = static_cast<__node_base_pointer>(__nd);
1259 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1262 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1264 if (__nd->__right_ != nullptr)
1265 __nd = static_cast<__node_pointer>(__nd->__right_);
1268 __parent = static_cast<__node_base_pointer>(__nd);
1269 return const_cast<const __node_base_const_pointer&>(__parent->__right_);
1274 __parent = static_cast<__node_base_pointer>(__nd);
1279 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1280 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1283 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1285 template <class _Key, class _Tp, class _Compare, class _Allocator>
1286 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1287 : __tree_(_VSTD::move(__m.__tree_), __a)
1289 if (__a != __m.get_allocator())
1291 const_iterator __e = cend();
1292 while (!__m.empty())
1293 __tree_.__insert_unique(__e.__i_,
1294 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1298 template <class _Key, class _Tp, class _Compare, class _Allocator>
1299 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1300 map<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1302 __node_allocator& __na = __tree_.__node_alloc();
1303 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1304 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
1305 __h.get_deleter().__first_constructed = true;
1306 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1307 __h.get_deleter().__second_constructed = true;
1311 template <class _Key, class _Tp, class _Compare, class _Allocator>
1312 template <class _A0>
1313 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1314 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1316 __node_allocator& __na = __tree_.__node_alloc();
1317 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1318 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1319 __h.get_deleter().__first_constructed = true;
1320 __h.get_deleter().__second_constructed = true;
1324 template <class _Key, class _Tp, class _Compare, class _Allocator>
1325 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1326 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k)
1328 __node_allocator& __na = __tree_.__node_alloc();
1329 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1330 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1331 __h.get_deleter().__first_constructed = true;
1332 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1333 __h.get_deleter().__second_constructed = true;
1337 #ifndef _LIBCPP_HAS_NO_VARIADICS
1339 template <class _Key, class _Tp, class _Compare, class _Allocator>
1340 template <class _A0, class _A1, class ..._Args>
1341 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1342 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1344 __node_allocator& __na = __tree_.__node_alloc();
1345 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1346 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1347 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1348 _VSTD::forward<_Args>(__args)...);
1349 __h.get_deleter().__first_constructed = true;
1350 __h.get_deleter().__second_constructed = true;
1354 #endif // _LIBCPP_HAS_NO_VARIADICS
1356 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1358 template <class _Key, class _Tp, class _Compare, class _Allocator>
1359 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1360 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1362 __node_allocator& __na = __tree_.__node_alloc();
1363 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1364 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1365 __h.get_deleter().__first_constructed = true;
1366 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1367 __h.get_deleter().__second_constructed = true;
1368 return _VSTD::move(__h); // explicitly moved for C++03
1371 template <class _Key, class _Tp, class _Compare, class _Allocator>
1373 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1375 __node_base_pointer __parent;
1376 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1377 __node_pointer __r = static_cast<__node_pointer>(__child);
1378 if (__child == nullptr)
1380 __node_holder __h = __construct_node_with_key(__k);
1381 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1382 __r = __h.release();
1384 return __r->__value_.__cc.second;
1387 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1389 template <class _Key, class _Tp, class _Compare, class _Allocator>
1391 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1393 __node_base_pointer __parent;
1394 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1395 __node_pointer __r = static_cast<__node_pointer>(__child);
1396 if (__child == nullptr)
1398 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1399 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1400 __r = __h.release();
1402 return __r->__value_.__cc.second;
1405 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1407 template <class _Key, class _Tp, class _Compare, class _Allocator>
1409 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1411 __node_base_pointer __parent;
1412 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1413 #ifndef _LIBCPP_NO_EXCEPTIONS
1414 if (__child == nullptr)
1415 throw out_of_range("map::at: key not found");
1416 #endif // _LIBCPP_NO_EXCEPTIONS
1417 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1420 template <class _Key, class _Tp, class _Compare, class _Allocator>
1422 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1424 __node_base_const_pointer __parent;
1425 __node_base_const_pointer __child = __find_equal_key(__parent, __k);
1426 #ifndef _LIBCPP_NO_EXCEPTIONS
1427 if (__child == nullptr)
1428 throw out_of_range("map::at: key not found");
1429 #endif // _LIBCPP_NO_EXCEPTIONS
1430 return static_cast<__node_const_pointer>(__child)->__value_.__cc.second;
1433 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1435 template <class _Key, class _Tp, class _Compare, class _Allocator>
1436 template <class ..._Args>
1437 pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
1438 map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1440 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1441 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
1447 template <class _Key, class _Tp, class _Compare, class _Allocator>
1448 template <class ..._Args>
1449 typename map<_Key, _Tp, _Compare, _Allocator>::iterator
1450 map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1453 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1454 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get());
1455 if (__r.__i_.__ptr_ == __h.get())
1460 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1462 template <class _Key, class _Tp, class _Compare, class _Allocator>
1463 inline _LIBCPP_INLINE_VISIBILITY
1465 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1466 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1468 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1471 template <class _Key, class _Tp, class _Compare, class _Allocator>
1472 inline _LIBCPP_INLINE_VISIBILITY
1474 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1475 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1477 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1480 template <class _Key, class _Tp, class _Compare, class _Allocator>
1481 inline _LIBCPP_INLINE_VISIBILITY
1483 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1484 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1486 return !(__x == __y);
1489 template <class _Key, class _Tp, class _Compare, class _Allocator>
1490 inline _LIBCPP_INLINE_VISIBILITY
1492 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1493 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1498 template <class _Key, class _Tp, class _Compare, class _Allocator>
1499 inline _LIBCPP_INLINE_VISIBILITY
1501 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1502 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1504 return !(__x < __y);
1507 template <class _Key, class _Tp, class _Compare, class _Allocator>
1508 inline _LIBCPP_INLINE_VISIBILITY
1510 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1511 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1513 return !(__y < __x);
1516 template <class _Key, class _Tp, class _Compare, class _Allocator>
1517 inline _LIBCPP_INLINE_VISIBILITY
1519 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1520 map<_Key, _Tp, _Compare, _Allocator>& __y)
1521 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1526 template <class _Key, class _Tp, class _Compare = less<_Key>,
1527 class _Allocator = allocator<pair<const _Key, _Tp> > >
1528 class _LIBCPP_TYPE_VIS_ONLY multimap
1532 typedef _Key key_type;
1533 typedef _Tp mapped_type;
1534 typedef pair<const key_type, mapped_type> value_type;
1535 typedef pair<key_type, mapped_type> __nc_value_type;
1536 typedef _Compare key_compare;
1537 typedef _Allocator allocator_type;
1538 typedef value_type& reference;
1539 typedef const value_type& const_reference;
1541 class _LIBCPP_TYPE_VIS_ONLY value_compare
1542 : public binary_function<value_type, value_type, bool>
1544 friend class multimap;
1548 _LIBCPP_INLINE_VISIBILITY
1549 value_compare(key_compare c) : comp(c) {}
1551 _LIBCPP_INLINE_VISIBILITY
1552 bool operator()(const value_type& __x, const value_type& __y) const
1553 {return comp(__x.first, __y.first);}
1558 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
1559 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1560 typedef typename allocator_traits<allocator_type>::template
1561 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1562 rebind_alloc<__value_type>
1564 rebind_alloc<__value_type>::other
1567 typedef __tree<__value_type, __vc, __allocator_type> __base;
1568 typedef typename __base::__node_traits __node_traits;
1569 typedef allocator_traits<allocator_type> __alloc_traits;
1574 typedef typename __alloc_traits::pointer pointer;
1575 typedef typename __alloc_traits::const_pointer const_pointer;
1576 typedef typename __alloc_traits::size_type size_type;
1577 typedef typename __alloc_traits::difference_type difference_type;
1578 typedef __map_iterator<typename __base::iterator> iterator;
1579 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1580 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1581 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1583 _LIBCPP_INLINE_VISIBILITY
1586 is_nothrow_default_constructible<allocator_type>::value &&
1587 is_nothrow_default_constructible<key_compare>::value &&
1588 is_nothrow_copy_constructible<key_compare>::value)
1589 : __tree_(__vc(key_compare())) {}
1591 _LIBCPP_INLINE_VISIBILITY
1592 explicit multimap(const key_compare& __comp)
1594 is_nothrow_default_constructible<allocator_type>::value &&
1595 is_nothrow_copy_constructible<key_compare>::value)
1596 : __tree_(__vc(__comp)) {}
1598 _LIBCPP_INLINE_VISIBILITY
1599 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1600 : __tree_(__vc(__comp), __a) {}
1602 template <class _InputIterator>
1603 _LIBCPP_INLINE_VISIBILITY
1604 multimap(_InputIterator __f, _InputIterator __l,
1605 const key_compare& __comp = key_compare())
1606 : __tree_(__vc(__comp))
1611 template <class _InputIterator>
1612 _LIBCPP_INLINE_VISIBILITY
1613 multimap(_InputIterator __f, _InputIterator __l,
1614 const key_compare& __comp, const allocator_type& __a)
1615 : __tree_(__vc(__comp), __a)
1620 #if _LIBCPP_STD_VER > 11
1621 template <class _InputIterator>
1622 _LIBCPP_INLINE_VISIBILITY
1623 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1624 : multimap(__f, __l, key_compare(), __a) {}
1627 _LIBCPP_INLINE_VISIBILITY
1628 multimap(const multimap& __m)
1629 : __tree_(__m.__tree_.value_comp(),
1630 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1632 insert(__m.begin(), __m.end());
1635 _LIBCPP_INLINE_VISIBILITY
1636 multimap& operator=(const multimap& __m)
1638 #if __cplusplus >= 201103L
1639 __tree_ = __m.__tree_;
1643 __tree_.value_comp() = __m.__tree_.value_comp();
1644 __tree_.__copy_assign_alloc(__m.__tree_);
1645 insert(__m.begin(), __m.end());
1651 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1653 _LIBCPP_INLINE_VISIBILITY
1654 multimap(multimap&& __m)
1655 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1656 : __tree_(_VSTD::move(__m.__tree_))
1660 multimap(multimap&& __m, const allocator_type& __a);
1662 _LIBCPP_INLINE_VISIBILITY
1663 multimap& operator=(multimap&& __m)
1664 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1666 __tree_ = _VSTD::move(__m.__tree_);
1670 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1672 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1674 _LIBCPP_INLINE_VISIBILITY
1675 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1676 : __tree_(__vc(__comp))
1678 insert(__il.begin(), __il.end());
1681 _LIBCPP_INLINE_VISIBILITY
1682 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1683 : __tree_(__vc(__comp), __a)
1685 insert(__il.begin(), __il.end());
1688 #if _LIBCPP_STD_VER > 11
1689 _LIBCPP_INLINE_VISIBILITY
1690 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1691 : multimap(__il, key_compare(), __a) {}
1694 _LIBCPP_INLINE_VISIBILITY
1695 multimap& operator=(initializer_list<value_type> __il)
1697 __tree_.__assign_multi(__il.begin(), __il.end());
1701 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1703 _LIBCPP_INLINE_VISIBILITY
1704 explicit multimap(const allocator_type& __a)
1709 _LIBCPP_INLINE_VISIBILITY
1710 multimap(const multimap& __m, const allocator_type& __a)
1711 : __tree_(__m.__tree_.value_comp(), __a)
1713 insert(__m.begin(), __m.end());
1716 _LIBCPP_INLINE_VISIBILITY
1717 iterator begin() _NOEXCEPT {return __tree_.begin();}
1718 _LIBCPP_INLINE_VISIBILITY
1719 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1720 _LIBCPP_INLINE_VISIBILITY
1721 iterator end() _NOEXCEPT {return __tree_.end();}
1722 _LIBCPP_INLINE_VISIBILITY
1723 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1725 _LIBCPP_INLINE_VISIBILITY
1726 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1727 _LIBCPP_INLINE_VISIBILITY
1728 const_reverse_iterator rbegin() const _NOEXCEPT
1729 {return const_reverse_iterator(end());}
1730 _LIBCPP_INLINE_VISIBILITY
1731 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1732 _LIBCPP_INLINE_VISIBILITY
1733 const_reverse_iterator rend() const _NOEXCEPT
1734 {return const_reverse_iterator(begin());}
1736 _LIBCPP_INLINE_VISIBILITY
1737 const_iterator cbegin() const _NOEXCEPT {return begin();}
1738 _LIBCPP_INLINE_VISIBILITY
1739 const_iterator cend() const _NOEXCEPT {return end();}
1740 _LIBCPP_INLINE_VISIBILITY
1741 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1742 _LIBCPP_INLINE_VISIBILITY
1743 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1745 _LIBCPP_INLINE_VISIBILITY
1746 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1747 _LIBCPP_INLINE_VISIBILITY
1748 size_type size() const _NOEXCEPT {return __tree_.size();}
1749 _LIBCPP_INLINE_VISIBILITY
1750 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1752 _LIBCPP_INLINE_VISIBILITY
1753 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1754 _LIBCPP_INLINE_VISIBILITY
1755 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1756 _LIBCPP_INLINE_VISIBILITY
1757 value_compare value_comp() const
1758 {return value_compare(__tree_.value_comp().key_comp());}
1760 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1761 #ifndef _LIBCPP_HAS_NO_VARIADICS
1763 template <class ..._Args>
1765 emplace(_Args&& ...__args);
1767 template <class ..._Args>
1769 emplace_hint(const_iterator __p, _Args&& ...__args);
1771 #endif // _LIBCPP_HAS_NO_VARIADICS
1773 template <class _Pp,
1774 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1775 _LIBCPP_INLINE_VISIBILITY
1776 iterator insert(_Pp&& __p)
1777 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1779 template <class _Pp,
1780 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1781 _LIBCPP_INLINE_VISIBILITY
1782 iterator insert(const_iterator __pos, _Pp&& __p)
1783 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1785 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1787 _LIBCPP_INLINE_VISIBILITY
1788 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1790 _LIBCPP_INLINE_VISIBILITY
1791 iterator insert(const_iterator __p, const value_type& __v)
1792 {return __tree_.__insert_multi(__p.__i_, __v);}
1794 template <class _InputIterator>
1795 _LIBCPP_INLINE_VISIBILITY
1796 void insert(_InputIterator __f, _InputIterator __l)
1798 for (const_iterator __e = cend(); __f != __l; ++__f)
1799 __tree_.__insert_multi(__e.__i_, *__f);
1802 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1804 _LIBCPP_INLINE_VISIBILITY
1805 void insert(initializer_list<value_type> __il)
1806 {insert(__il.begin(), __il.end());}
1808 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1810 _LIBCPP_INLINE_VISIBILITY
1811 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1812 _LIBCPP_INLINE_VISIBILITY
1813 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1814 _LIBCPP_INLINE_VISIBILITY
1815 iterator erase(const_iterator __f, const_iterator __l)
1816 {return __tree_.erase(__f.__i_, __l.__i_);}
1817 _LIBCPP_INLINE_VISIBILITY
1818 void clear() {__tree_.clear();}
1820 _LIBCPP_INLINE_VISIBILITY
1821 void swap(multimap& __m)
1822 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1823 {__tree_.swap(__m.__tree_);}
1825 _LIBCPP_INLINE_VISIBILITY
1826 iterator find(const key_type& __k) {return __tree_.find(__k);}
1827 _LIBCPP_INLINE_VISIBILITY
1828 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1829 #if _LIBCPP_STD_VER > 11
1830 template <typename _K2>
1831 _LIBCPP_INLINE_VISIBILITY
1832 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1833 find(const _K2& __k) {return __tree_.find(__k);}
1834 template <typename _K2>
1835 _LIBCPP_INLINE_VISIBILITY
1836 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1837 find(const _K2& __k) const {return __tree_.find(__k);}
1840 _LIBCPP_INLINE_VISIBILITY
1841 size_type count(const key_type& __k) const
1842 {return __tree_.__count_multi(__k);}
1843 #if _LIBCPP_STD_VER > 11
1844 template <typename _K2>
1845 _LIBCPP_INLINE_VISIBILITY
1846 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1847 count(const _K2& __k) {return __tree_.__count_multi(__k);}
1849 _LIBCPP_INLINE_VISIBILITY
1850 iterator lower_bound(const key_type& __k)
1851 {return __tree_.lower_bound(__k);}
1852 _LIBCPP_INLINE_VISIBILITY
1853 const_iterator lower_bound(const key_type& __k) const
1854 {return __tree_.lower_bound(__k);}
1855 #if _LIBCPP_STD_VER > 11
1856 template <typename _K2>
1857 _LIBCPP_INLINE_VISIBILITY
1858 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1859 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1861 template <typename _K2>
1862 _LIBCPP_INLINE_VISIBILITY
1863 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1864 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1867 _LIBCPP_INLINE_VISIBILITY
1868 iterator upper_bound(const key_type& __k)
1869 {return __tree_.upper_bound(__k);}
1870 _LIBCPP_INLINE_VISIBILITY
1871 const_iterator upper_bound(const key_type& __k) const
1872 {return __tree_.upper_bound(__k);}
1873 #if _LIBCPP_STD_VER > 11
1874 template <typename _K2>
1875 _LIBCPP_INLINE_VISIBILITY
1876 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1877 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1878 template <typename _K2>
1879 _LIBCPP_INLINE_VISIBILITY
1880 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1881 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1884 _LIBCPP_INLINE_VISIBILITY
1885 pair<iterator,iterator> equal_range(const key_type& __k)
1886 {return __tree_.__equal_range_multi(__k);}
1887 _LIBCPP_INLINE_VISIBILITY
1888 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1889 {return __tree_.__equal_range_multi(__k);}
1890 #if _LIBCPP_STD_VER > 11
1891 template <typename _K2>
1892 _LIBCPP_INLINE_VISIBILITY
1893 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1894 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1895 template <typename _K2>
1896 _LIBCPP_INLINE_VISIBILITY
1897 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1898 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1902 typedef typename __base::__node __node;
1903 typedef typename __base::__node_allocator __node_allocator;
1904 typedef typename __base::__node_pointer __node_pointer;
1905 typedef typename __base::__node_const_pointer __node_const_pointer;
1906 typedef __map_node_destructor<__node_allocator> _Dp;
1907 typedef unique_ptr<__node, _Dp> __node_holder;
1909 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1910 __node_holder __construct_node();
1911 template <class _A0>
1913 __construct_node(_A0&& __a0);
1914 #ifndef _LIBCPP_HAS_NO_VARIADICS
1915 template <class _A0, class _A1, class ..._Args>
1916 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1917 #endif // _LIBCPP_HAS_NO_VARIADICS
1918 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1921 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1923 template <class _Key, class _Tp, class _Compare, class _Allocator>
1924 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1925 : __tree_(_VSTD::move(__m.__tree_), __a)
1927 if (__a != __m.get_allocator())
1929 const_iterator __e = cend();
1930 while (!__m.empty())
1931 __tree_.__insert_multi(__e.__i_,
1932 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1936 template <class _Key, class _Tp, class _Compare, class _Allocator>
1937 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1938 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1940 __node_allocator& __na = __tree_.__node_alloc();
1941 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1942 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
1943 __h.get_deleter().__first_constructed = true;
1944 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1945 __h.get_deleter().__second_constructed = true;
1949 template <class _Key, class _Tp, class _Compare, class _Allocator>
1950 template <class _A0>
1951 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1952 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1954 __node_allocator& __na = __tree_.__node_alloc();
1955 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1956 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1957 __h.get_deleter().__first_constructed = true;
1958 __h.get_deleter().__second_constructed = true;
1962 #ifndef _LIBCPP_HAS_NO_VARIADICS
1964 template <class _Key, class _Tp, class _Compare, class _Allocator>
1965 template <class _A0, class _A1, class ..._Args>
1966 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1967 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1969 __node_allocator& __na = __tree_.__node_alloc();
1970 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1971 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1972 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1973 _VSTD::forward<_Args>(__args)...);
1974 __h.get_deleter().__first_constructed = true;
1975 __h.get_deleter().__second_constructed = true;
1979 #endif // _LIBCPP_HAS_NO_VARIADICS
1980 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1982 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1984 template <class _Key, class _Tp, class _Compare, class _Allocator>
1985 template <class ..._Args>
1986 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1987 multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1989 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1990 iterator __r = __tree_.__node_insert_multi(__h.get());
1995 template <class _Key, class _Tp, class _Compare, class _Allocator>
1996 template <class ..._Args>
1997 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1998 multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
2001 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2002 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get());
2007 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
2009 template <class _Key, class _Tp, class _Compare, class _Allocator>
2010 inline _LIBCPP_INLINE_VISIBILITY
2012 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2013 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2015 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2018 template <class _Key, class _Tp, class _Compare, class _Allocator>
2019 inline _LIBCPP_INLINE_VISIBILITY
2021 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2022 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2024 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2027 template <class _Key, class _Tp, class _Compare, class _Allocator>
2028 inline _LIBCPP_INLINE_VISIBILITY
2030 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2031 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2033 return !(__x == __y);
2036 template <class _Key, class _Tp, class _Compare, class _Allocator>
2037 inline _LIBCPP_INLINE_VISIBILITY
2039 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2040 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2045 template <class _Key, class _Tp, class _Compare, class _Allocator>
2046 inline _LIBCPP_INLINE_VISIBILITY
2048 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2049 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2051 return !(__x < __y);
2054 template <class _Key, class _Tp, class _Compare, class _Allocator>
2055 inline _LIBCPP_INLINE_VISIBILITY
2057 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2058 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2060 return !(__y < __x);
2063 template <class _Key, class _Tp, class _Compare, class _Allocator>
2064 inline _LIBCPP_INLINE_VISIBILITY
2066 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2067 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2068 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2073 _LIBCPP_END_NAMESPACE_STD
2075 #endif // _LIBCPP_MAP