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;
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;
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_default_constructible<key_compare>::value &&
850 is_nothrow_copy_constructible<key_compare>::value)
851 : __tree_(__vc(__comp)) {}
853 _LIBCPP_INLINE_VISIBILITY
854 explicit map(const key_compare& __comp, const allocator_type& __a)
855 : __tree_(__vc(__comp), __a) {}
857 template <class _InputIterator>
858 _LIBCPP_INLINE_VISIBILITY
859 map(_InputIterator __f, _InputIterator __l,
860 const key_compare& __comp = key_compare())
861 : __tree_(__vc(__comp))
866 template <class _InputIterator>
867 _LIBCPP_INLINE_VISIBILITY
868 map(_InputIterator __f, _InputIterator __l,
869 const key_compare& __comp, const allocator_type& __a)
870 : __tree_(__vc(__comp), __a)
875 #if _LIBCPP_STD_VER > 11
876 template <class _InputIterator>
877 _LIBCPP_INLINE_VISIBILITY
878 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
879 : map(__f, __l, key_compare(), __a) {}
882 _LIBCPP_INLINE_VISIBILITY
884 : __tree_(__m.__tree_)
886 insert(__m.begin(), __m.end());
889 _LIBCPP_INLINE_VISIBILITY
890 map& operator=(const map& __m)
892 #if __cplusplus >= 201103L
893 __tree_ = __m.__tree_;
897 __tree_.value_comp() = __m.__tree_.value_comp();
898 __tree_.__copy_assign_alloc(__m.__tree_);
899 insert(__m.begin(), __m.end());
905 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
907 _LIBCPP_INLINE_VISIBILITY
909 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
910 : __tree_(_VSTD::move(__m.__tree_))
914 map(map&& __m, const allocator_type& __a);
916 _LIBCPP_INLINE_VISIBILITY
917 map& operator=(map&& __m)
918 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
920 __tree_ = _VSTD::move(__m.__tree_);
924 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
926 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
928 _LIBCPP_INLINE_VISIBILITY
929 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
930 : __tree_(__vc(__comp))
932 insert(__il.begin(), __il.end());
935 _LIBCPP_INLINE_VISIBILITY
936 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
937 : __tree_(__vc(__comp), __a)
939 insert(__il.begin(), __il.end());
942 #if _LIBCPP_STD_VER > 11
943 _LIBCPP_INLINE_VISIBILITY
944 map(initializer_list<value_type> __il, const allocator_type& __a)
945 : map(__il, key_compare(), __a) {}
948 _LIBCPP_INLINE_VISIBILITY
949 map& operator=(initializer_list<value_type> __il)
951 __tree_.__assign_unique(__il.begin(), __il.end());
955 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
957 _LIBCPP_INLINE_VISIBILITY
958 explicit map(const allocator_type& __a)
963 _LIBCPP_INLINE_VISIBILITY
964 map(const map& __m, const allocator_type& __a)
965 : __tree_(__m.__tree_.value_comp(), __a)
967 insert(__m.begin(), __m.end());
970 _LIBCPP_INLINE_VISIBILITY
971 iterator begin() _NOEXCEPT {return __tree_.begin();}
972 _LIBCPP_INLINE_VISIBILITY
973 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
974 _LIBCPP_INLINE_VISIBILITY
975 iterator end() _NOEXCEPT {return __tree_.end();}
976 _LIBCPP_INLINE_VISIBILITY
977 const_iterator end() const _NOEXCEPT {return __tree_.end();}
979 _LIBCPP_INLINE_VISIBILITY
980 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
981 _LIBCPP_INLINE_VISIBILITY
982 const_reverse_iterator rbegin() const _NOEXCEPT
983 {return const_reverse_iterator(end());}
984 _LIBCPP_INLINE_VISIBILITY
985 reverse_iterator rend() _NOEXCEPT
986 {return reverse_iterator(begin());}
987 _LIBCPP_INLINE_VISIBILITY
988 const_reverse_iterator rend() const _NOEXCEPT
989 {return const_reverse_iterator(begin());}
991 _LIBCPP_INLINE_VISIBILITY
992 const_iterator cbegin() const _NOEXCEPT {return begin();}
993 _LIBCPP_INLINE_VISIBILITY
994 const_iterator cend() const _NOEXCEPT {return end();}
995 _LIBCPP_INLINE_VISIBILITY
996 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
997 _LIBCPP_INLINE_VISIBILITY
998 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1000 _LIBCPP_INLINE_VISIBILITY
1001 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1002 _LIBCPP_INLINE_VISIBILITY
1003 size_type size() const _NOEXCEPT {return __tree_.size();}
1004 _LIBCPP_INLINE_VISIBILITY
1005 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1007 mapped_type& operator[](const key_type& __k);
1008 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1009 mapped_type& operator[](key_type&& __k);
1012 mapped_type& at(const key_type& __k);
1013 const mapped_type& at(const key_type& __k) const;
1015 _LIBCPP_INLINE_VISIBILITY
1016 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1017 _LIBCPP_INLINE_VISIBILITY
1018 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1019 _LIBCPP_INLINE_VISIBILITY
1020 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1022 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1023 #ifndef _LIBCPP_HAS_NO_VARIADICS
1025 template <class ..._Args>
1026 pair<iterator, bool>
1027 emplace(_Args&& ...__args);
1029 template <class ..._Args>
1031 emplace_hint(const_iterator __p, _Args&& ...__args);
1033 #endif // _LIBCPP_HAS_NO_VARIADICS
1035 template <class _Pp,
1036 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1037 _LIBCPP_INLINE_VISIBILITY
1038 pair<iterator, bool> insert(_Pp&& __p)
1039 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1041 template <class _Pp,
1042 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1043 _LIBCPP_INLINE_VISIBILITY
1044 iterator insert(const_iterator __pos, _Pp&& __p)
1045 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1047 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1049 _LIBCPP_INLINE_VISIBILITY
1050 pair<iterator, bool>
1051 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1053 _LIBCPP_INLINE_VISIBILITY
1055 insert(const_iterator __p, const value_type& __v)
1056 {return __tree_.__insert_unique(__p.__i_, __v);}
1058 template <class _InputIterator>
1059 _LIBCPP_INLINE_VISIBILITY
1060 void insert(_InputIterator __f, _InputIterator __l)
1062 for (const_iterator __e = cend(); __f != __l; ++__f)
1063 insert(__e.__i_, *__f);
1066 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1068 _LIBCPP_INLINE_VISIBILITY
1069 void insert(initializer_list<value_type> __il)
1070 {insert(__il.begin(), __il.end());}
1072 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1074 _LIBCPP_INLINE_VISIBILITY
1075 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1076 _LIBCPP_INLINE_VISIBILITY
1077 size_type erase(const key_type& __k)
1078 {return __tree_.__erase_unique(__k);}
1079 _LIBCPP_INLINE_VISIBILITY
1080 iterator erase(const_iterator __f, const_iterator __l)
1081 {return __tree_.erase(__f.__i_, __l.__i_);}
1082 _LIBCPP_INLINE_VISIBILITY
1083 void clear() _NOEXCEPT {__tree_.clear();}
1085 _LIBCPP_INLINE_VISIBILITY
1087 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1088 {__tree_.swap(__m.__tree_);}
1090 _LIBCPP_INLINE_VISIBILITY
1091 iterator find(const key_type& __k) {return __tree_.find(__k);}
1092 _LIBCPP_INLINE_VISIBILITY
1093 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1094 #if _LIBCPP_STD_VER > 11
1095 template <typename _K2>
1096 _LIBCPP_INLINE_VISIBILITY
1097 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1098 find(const _K2& __k) {return __tree_.find(__k);}
1099 template <typename _K2>
1100 _LIBCPP_INLINE_VISIBILITY
1101 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1102 find(const _K2& __k) const {return __tree_.find(__k);}
1105 _LIBCPP_INLINE_VISIBILITY
1106 size_type count(const key_type& __k) const
1107 {return __tree_.__count_unique(__k);}
1108 _LIBCPP_INLINE_VISIBILITY
1109 iterator lower_bound(const key_type& __k)
1110 {return __tree_.lower_bound(__k);}
1111 _LIBCPP_INLINE_VISIBILITY
1112 const_iterator lower_bound(const key_type& __k) const
1113 {return __tree_.lower_bound(__k);}
1114 #if _LIBCPP_STD_VER > 11
1115 template <typename _K2>
1116 _LIBCPP_INLINE_VISIBILITY
1117 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1118 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1120 template <typename _K2>
1121 _LIBCPP_INLINE_VISIBILITY
1122 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1123 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1126 _LIBCPP_INLINE_VISIBILITY
1127 iterator upper_bound(const key_type& __k)
1128 {return __tree_.upper_bound(__k);}
1129 _LIBCPP_INLINE_VISIBILITY
1130 const_iterator upper_bound(const key_type& __k) const
1131 {return __tree_.upper_bound(__k);}
1132 #if _LIBCPP_STD_VER > 11
1133 template <typename _K2>
1134 _LIBCPP_INLINE_VISIBILITY
1135 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1136 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1137 template <typename _K2>
1138 _LIBCPP_INLINE_VISIBILITY
1139 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1140 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1143 _LIBCPP_INLINE_VISIBILITY
1144 pair<iterator,iterator> equal_range(const key_type& __k)
1145 {return __tree_.__equal_range_unique(__k);}
1146 _LIBCPP_INLINE_VISIBILITY
1147 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1148 {return __tree_.__equal_range_unique(__k);}
1149 #if _LIBCPP_STD_VER > 11
1150 template <typename _K2>
1151 _LIBCPP_INLINE_VISIBILITY
1152 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1153 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
1154 template <typename _K2>
1155 _LIBCPP_INLINE_VISIBILITY
1156 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1157 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1161 typedef typename __base::__node __node;
1162 typedef typename __base::__node_allocator __node_allocator;
1163 typedef typename __base::__node_pointer __node_pointer;
1164 typedef typename __base::__node_const_pointer __node_const_pointer;
1165 typedef typename __base::__node_base_pointer __node_base_pointer;
1166 typedef typename __base::__node_base_const_pointer __node_base_const_pointer;
1167 typedef __map_node_destructor<__node_allocator> _Dp;
1168 typedef unique_ptr<__node, _Dp> __node_holder;
1170 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1171 __node_holder __construct_node();
1172 template <class _A0>
1173 __node_holder __construct_node(_A0&& __a0);
1174 __node_holder __construct_node_with_key(key_type&& __k);
1175 #ifndef _LIBCPP_HAS_NO_VARIADICS
1176 template <class _A0, class _A1, class ..._Args>
1177 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1178 #endif // _LIBCPP_HAS_NO_VARIADICS
1180 __node_holder __construct_node_with_key(const key_type& __k);
1182 __node_base_pointer&
1183 __find_equal_key(__node_base_pointer& __parent, const key_type& __k);
1184 __node_base_const_pointer
1185 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
1188 // Find place to insert if __k doesn't exist
1189 // Set __parent to parent of null leaf
1190 // Return reference to null leaf
1191 // If __k exists, set parent to node of __k and return reference to node of __k
1192 template <class _Key, class _Tp, class _Compare, class _Allocator>
1193 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1194 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
1195 const key_type& __k)
1197 __node_pointer __nd = __tree_.__root();
1198 if (__nd != nullptr)
1202 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1204 if (__nd->__left_ != nullptr)
1205 __nd = static_cast<__node_pointer>(__nd->__left_);
1208 __parent = static_cast<__node_base_pointer>(__nd);
1209 return __parent->__left_;
1212 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1214 if (__nd->__right_ != nullptr)
1215 __nd = static_cast<__node_pointer>(__nd->__right_);
1218 __parent = static_cast<__node_base_pointer>(__nd);
1219 return __parent->__right_;
1224 __parent = static_cast<__node_base_pointer>(__nd);
1229 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1230 return __parent->__left_;
1234 // Set __parent to parent of null leaf and
1235 // return reference to null leaf iv __k does not exist.
1236 // If __k exists, set parent to node of __k and return reference to node of __k
1237 template <class _Key, class _Tp, class _Compare, class _Allocator>
1238 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer
1239 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent,
1240 const key_type& __k) const
1242 __node_const_pointer __nd = __tree_.__root();
1243 if (__nd != nullptr)
1247 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1249 if (__nd->__left_ != nullptr)
1250 __nd = static_cast<__node_pointer>(__nd->__left_);
1253 __parent = static_cast<__node_base_pointer>(__nd);
1254 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1257 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1259 if (__nd->__right_ != nullptr)
1260 __nd = static_cast<__node_pointer>(__nd->__right_);
1263 __parent = static_cast<__node_base_pointer>(__nd);
1264 return const_cast<const __node_base_const_pointer&>(__parent->__right_);
1269 __parent = static_cast<__node_base_pointer>(__nd);
1274 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1275 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1278 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1280 template <class _Key, class _Tp, class _Compare, class _Allocator>
1281 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1282 : __tree_(_VSTD::move(__m.__tree_), __a)
1284 if (__a != __m.get_allocator())
1286 const_iterator __e = cend();
1287 while (!__m.empty())
1288 __tree_.__insert_unique(__e.__i_,
1289 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1293 template <class _Key, class _Tp, class _Compare, class _Allocator>
1294 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1295 map<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1297 __node_allocator& __na = __tree_.__node_alloc();
1298 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1299 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
1300 __h.get_deleter().__first_constructed = true;
1301 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1302 __h.get_deleter().__second_constructed = true;
1306 template <class _Key, class _Tp, class _Compare, class _Allocator>
1307 template <class _A0>
1308 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1309 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1311 __node_allocator& __na = __tree_.__node_alloc();
1312 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1313 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1314 __h.get_deleter().__first_constructed = true;
1315 __h.get_deleter().__second_constructed = true;
1319 template <class _Key, class _Tp, class _Compare, class _Allocator>
1320 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1321 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k)
1323 __node_allocator& __na = __tree_.__node_alloc();
1324 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1325 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1326 __h.get_deleter().__first_constructed = true;
1327 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1328 __h.get_deleter().__second_constructed = true;
1332 #ifndef _LIBCPP_HAS_NO_VARIADICS
1334 template <class _Key, class _Tp, class _Compare, class _Allocator>
1335 template <class _A0, class _A1, class ..._Args>
1336 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1337 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1339 __node_allocator& __na = __tree_.__node_alloc();
1340 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1341 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1342 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1343 _VSTD::forward<_Args>(__args)...);
1344 __h.get_deleter().__first_constructed = true;
1345 __h.get_deleter().__second_constructed = true;
1349 #endif // _LIBCPP_HAS_NO_VARIADICS
1351 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1353 template <class _Key, class _Tp, class _Compare, class _Allocator>
1354 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1355 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1357 __node_allocator& __na = __tree_.__node_alloc();
1358 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1359 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1360 __h.get_deleter().__first_constructed = true;
1361 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1362 __h.get_deleter().__second_constructed = true;
1363 return _VSTD::move(__h); // explicitly moved for C++03
1366 template <class _Key, class _Tp, class _Compare, class _Allocator>
1368 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1370 __node_base_pointer __parent;
1371 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1372 __node_pointer __r = static_cast<__node_pointer>(__child);
1373 if (__child == nullptr)
1375 __node_holder __h = __construct_node_with_key(__k);
1376 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1377 __r = __h.release();
1379 return __r->__value_.__cc.second;
1382 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1384 template <class _Key, class _Tp, class _Compare, class _Allocator>
1386 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1388 __node_base_pointer __parent;
1389 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1390 __node_pointer __r = static_cast<__node_pointer>(__child);
1391 if (__child == nullptr)
1393 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1394 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1395 __r = __h.release();
1397 return __r->__value_.__cc.second;
1400 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1402 template <class _Key, class _Tp, class _Compare, class _Allocator>
1404 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1406 __node_base_pointer __parent;
1407 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1408 #ifndef _LIBCPP_NO_EXCEPTIONS
1409 if (__child == nullptr)
1410 throw out_of_range("map::at: key not found");
1411 #endif // _LIBCPP_NO_EXCEPTIONS
1412 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1415 template <class _Key, class _Tp, class _Compare, class _Allocator>
1417 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1419 __node_base_const_pointer __parent;
1420 __node_base_const_pointer __child = __find_equal_key(__parent, __k);
1421 #ifndef _LIBCPP_NO_EXCEPTIONS
1422 if (__child == nullptr)
1423 throw out_of_range("map::at: key not found");
1424 #endif // _LIBCPP_NO_EXCEPTIONS
1425 return static_cast<__node_const_pointer>(__child)->__value_.__cc.second;
1428 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1430 template <class _Key, class _Tp, class _Compare, class _Allocator>
1431 template <class ..._Args>
1432 pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
1433 map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1435 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1436 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
1442 template <class _Key, class _Tp, class _Compare, class _Allocator>
1443 template <class ..._Args>
1444 typename map<_Key, _Tp, _Compare, _Allocator>::iterator
1445 map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1448 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1449 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get());
1450 if (__r.__i_.__ptr_ == __h.get())
1455 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1457 template <class _Key, class _Tp, class _Compare, class _Allocator>
1458 inline _LIBCPP_INLINE_VISIBILITY
1460 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1461 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1463 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1466 template <class _Key, class _Tp, class _Compare, class _Allocator>
1467 inline _LIBCPP_INLINE_VISIBILITY
1469 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1470 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1472 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1475 template <class _Key, class _Tp, class _Compare, class _Allocator>
1476 inline _LIBCPP_INLINE_VISIBILITY
1478 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1479 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1481 return !(__x == __y);
1484 template <class _Key, class _Tp, class _Compare, class _Allocator>
1485 inline _LIBCPP_INLINE_VISIBILITY
1487 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1488 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1493 template <class _Key, class _Tp, class _Compare, class _Allocator>
1494 inline _LIBCPP_INLINE_VISIBILITY
1496 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1497 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1499 return !(__x < __y);
1502 template <class _Key, class _Tp, class _Compare, class _Allocator>
1503 inline _LIBCPP_INLINE_VISIBILITY
1505 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1506 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1508 return !(__y < __x);
1511 template <class _Key, class _Tp, class _Compare, class _Allocator>
1512 inline _LIBCPP_INLINE_VISIBILITY
1514 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1515 map<_Key, _Tp, _Compare, _Allocator>& __y)
1516 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1521 template <class _Key, class _Tp, class _Compare = less<_Key>,
1522 class _Allocator = allocator<pair<const _Key, _Tp> > >
1523 class _LIBCPP_TYPE_VIS_ONLY multimap
1527 typedef _Key key_type;
1528 typedef _Tp mapped_type;
1529 typedef pair<const key_type, mapped_type> value_type;
1530 typedef pair<key_type, mapped_type> __nc_value_type;
1531 typedef _Compare key_compare;
1532 typedef _Allocator allocator_type;
1533 typedef value_type& reference;
1534 typedef const value_type& const_reference;
1536 class _LIBCPP_TYPE_VIS_ONLY value_compare
1537 : public binary_function<value_type, value_type, bool>
1539 friend class multimap;
1543 _LIBCPP_INLINE_VISIBILITY
1544 value_compare(key_compare c) : comp(c) {}
1546 _LIBCPP_INLINE_VISIBILITY
1547 bool operator()(const value_type& __x, const value_type& __y) const
1548 {return comp(__x.first, __y.first);}
1553 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
1554 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1555 typedef typename allocator_traits<allocator_type>::template
1556 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1557 rebind_alloc<__value_type>
1559 rebind_alloc<__value_type>::other
1562 typedef __tree<__value_type, __vc, __allocator_type> __base;
1563 typedef typename __base::__node_traits __node_traits;
1564 typedef allocator_traits<allocator_type> __alloc_traits;
1569 typedef typename __alloc_traits::pointer pointer;
1570 typedef typename __alloc_traits::const_pointer const_pointer;
1571 typedef typename __alloc_traits::size_type size_type;
1572 typedef typename __alloc_traits::difference_type difference_type;
1573 typedef __map_iterator<typename __base::iterator> iterator;
1574 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1575 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1576 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1578 _LIBCPP_INLINE_VISIBILITY
1581 is_nothrow_default_constructible<allocator_type>::value &&
1582 is_nothrow_default_constructible<key_compare>::value &&
1583 is_nothrow_copy_constructible<key_compare>::value)
1584 : __tree_(__vc(key_compare())) {}
1586 _LIBCPP_INLINE_VISIBILITY
1587 explicit multimap(const key_compare& __comp)
1589 is_nothrow_default_constructible<allocator_type>::value &&
1590 is_nothrow_default_constructible<key_compare>::value &&
1591 is_nothrow_copy_constructible<key_compare>::value)
1592 : __tree_(__vc(__comp)) {}
1594 _LIBCPP_INLINE_VISIBILITY
1595 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1596 : __tree_(__vc(__comp), __a) {}
1598 template <class _InputIterator>
1599 _LIBCPP_INLINE_VISIBILITY
1600 multimap(_InputIterator __f, _InputIterator __l,
1601 const key_compare& __comp = key_compare())
1602 : __tree_(__vc(__comp))
1607 template <class _InputIterator>
1608 _LIBCPP_INLINE_VISIBILITY
1609 multimap(_InputIterator __f, _InputIterator __l,
1610 const key_compare& __comp, const allocator_type& __a)
1611 : __tree_(__vc(__comp), __a)
1616 #if _LIBCPP_STD_VER > 11
1617 template <class _InputIterator>
1618 _LIBCPP_INLINE_VISIBILITY
1619 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1620 : multimap(__f, __l, key_compare(), __a) {}
1623 _LIBCPP_INLINE_VISIBILITY
1624 multimap(const multimap& __m)
1625 : __tree_(__m.__tree_.value_comp(),
1626 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1628 insert(__m.begin(), __m.end());
1631 _LIBCPP_INLINE_VISIBILITY
1632 multimap& operator=(const multimap& __m)
1634 #if __cplusplus >= 201103L
1635 __tree_ = __m.__tree_;
1639 __tree_.value_comp() = __m.__tree_.value_comp();
1640 __tree_.__copy_assign_alloc(__m.__tree_);
1641 insert(__m.begin(), __m.end());
1647 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1649 _LIBCPP_INLINE_VISIBILITY
1650 multimap(multimap&& __m)
1651 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1652 : __tree_(_VSTD::move(__m.__tree_))
1656 multimap(multimap&& __m, const allocator_type& __a);
1658 _LIBCPP_INLINE_VISIBILITY
1659 multimap& operator=(multimap&& __m)
1660 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1662 __tree_ = _VSTD::move(__m.__tree_);
1666 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1668 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1670 _LIBCPP_INLINE_VISIBILITY
1671 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1672 : __tree_(__vc(__comp))
1674 insert(__il.begin(), __il.end());
1677 _LIBCPP_INLINE_VISIBILITY
1678 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1679 : __tree_(__vc(__comp), __a)
1681 insert(__il.begin(), __il.end());
1684 #if _LIBCPP_STD_VER > 11
1685 _LIBCPP_INLINE_VISIBILITY
1686 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1687 : multimap(__il, key_compare(), __a) {}
1690 _LIBCPP_INLINE_VISIBILITY
1691 multimap& operator=(initializer_list<value_type> __il)
1693 __tree_.__assign_multi(__il.begin(), __il.end());
1697 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1699 _LIBCPP_INLINE_VISIBILITY
1700 explicit multimap(const allocator_type& __a)
1705 _LIBCPP_INLINE_VISIBILITY
1706 multimap(const multimap& __m, const allocator_type& __a)
1707 : __tree_(__m.__tree_.value_comp(), __a)
1709 insert(__m.begin(), __m.end());
1712 _LIBCPP_INLINE_VISIBILITY
1713 iterator begin() _NOEXCEPT {return __tree_.begin();}
1714 _LIBCPP_INLINE_VISIBILITY
1715 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1716 _LIBCPP_INLINE_VISIBILITY
1717 iterator end() _NOEXCEPT {return __tree_.end();}
1718 _LIBCPP_INLINE_VISIBILITY
1719 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1721 _LIBCPP_INLINE_VISIBILITY
1722 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1723 _LIBCPP_INLINE_VISIBILITY
1724 const_reverse_iterator rbegin() const _NOEXCEPT
1725 {return const_reverse_iterator(end());}
1726 _LIBCPP_INLINE_VISIBILITY
1727 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1728 _LIBCPP_INLINE_VISIBILITY
1729 const_reverse_iterator rend() const _NOEXCEPT
1730 {return const_reverse_iterator(begin());}
1732 _LIBCPP_INLINE_VISIBILITY
1733 const_iterator cbegin() const _NOEXCEPT {return begin();}
1734 _LIBCPP_INLINE_VISIBILITY
1735 const_iterator cend() const _NOEXCEPT {return end();}
1736 _LIBCPP_INLINE_VISIBILITY
1737 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1738 _LIBCPP_INLINE_VISIBILITY
1739 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1741 _LIBCPP_INLINE_VISIBILITY
1742 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1743 _LIBCPP_INLINE_VISIBILITY
1744 size_type size() const _NOEXCEPT {return __tree_.size();}
1745 _LIBCPP_INLINE_VISIBILITY
1746 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1748 _LIBCPP_INLINE_VISIBILITY
1749 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1750 _LIBCPP_INLINE_VISIBILITY
1751 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1752 _LIBCPP_INLINE_VISIBILITY
1753 value_compare value_comp() const
1754 {return value_compare(__tree_.value_comp().key_comp());}
1756 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1757 #ifndef _LIBCPP_HAS_NO_VARIADICS
1759 template <class ..._Args>
1761 emplace(_Args&& ...__args);
1763 template <class ..._Args>
1765 emplace_hint(const_iterator __p, _Args&& ...__args);
1767 #endif // _LIBCPP_HAS_NO_VARIADICS
1769 template <class _Pp,
1770 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1771 _LIBCPP_INLINE_VISIBILITY
1772 iterator insert(_Pp&& __p)
1773 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1775 template <class _Pp,
1776 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1777 _LIBCPP_INLINE_VISIBILITY
1778 iterator insert(const_iterator __pos, _Pp&& __p)
1779 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1781 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1783 _LIBCPP_INLINE_VISIBILITY
1784 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1786 _LIBCPP_INLINE_VISIBILITY
1787 iterator insert(const_iterator __p, const value_type& __v)
1788 {return __tree_.__insert_multi(__p.__i_, __v);}
1790 template <class _InputIterator>
1791 _LIBCPP_INLINE_VISIBILITY
1792 void insert(_InputIterator __f, _InputIterator __l)
1794 for (const_iterator __e = cend(); __f != __l; ++__f)
1795 __tree_.__insert_multi(__e.__i_, *__f);
1798 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1800 _LIBCPP_INLINE_VISIBILITY
1801 void insert(initializer_list<value_type> __il)
1802 {insert(__il.begin(), __il.end());}
1804 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1806 _LIBCPP_INLINE_VISIBILITY
1807 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1808 _LIBCPP_INLINE_VISIBILITY
1809 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1810 _LIBCPP_INLINE_VISIBILITY
1811 iterator erase(const_iterator __f, const_iterator __l)
1812 {return __tree_.erase(__f.__i_, __l.__i_);}
1813 _LIBCPP_INLINE_VISIBILITY
1814 void clear() {__tree_.clear();}
1816 _LIBCPP_INLINE_VISIBILITY
1817 void swap(multimap& __m)
1818 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1819 {__tree_.swap(__m.__tree_);}
1821 _LIBCPP_INLINE_VISIBILITY
1822 iterator find(const key_type& __k) {return __tree_.find(__k);}
1823 _LIBCPP_INLINE_VISIBILITY
1824 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1825 #if _LIBCPP_STD_VER > 11
1826 template <typename _K2>
1827 _LIBCPP_INLINE_VISIBILITY
1828 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1829 find(const _K2& __k) {return __tree_.find(__k);}
1830 template <typename _K2>
1831 _LIBCPP_INLINE_VISIBILITY
1832 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1833 find(const _K2& __k) const {return __tree_.find(__k);}
1836 _LIBCPP_INLINE_VISIBILITY
1837 size_type count(const key_type& __k) const
1838 {return __tree_.__count_multi(__k);}
1839 _LIBCPP_INLINE_VISIBILITY
1840 iterator lower_bound(const key_type& __k)
1841 {return __tree_.lower_bound(__k);}
1842 _LIBCPP_INLINE_VISIBILITY
1843 const_iterator lower_bound(const key_type& __k) const
1844 {return __tree_.lower_bound(__k);}
1845 #if _LIBCPP_STD_VER > 11
1846 template <typename _K2>
1847 _LIBCPP_INLINE_VISIBILITY
1848 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1849 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1851 template <typename _K2>
1852 _LIBCPP_INLINE_VISIBILITY
1853 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1854 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1857 _LIBCPP_INLINE_VISIBILITY
1858 iterator upper_bound(const key_type& __k)
1859 {return __tree_.upper_bound(__k);}
1860 _LIBCPP_INLINE_VISIBILITY
1861 const_iterator upper_bound(const key_type& __k) const
1862 {return __tree_.upper_bound(__k);}
1863 #if _LIBCPP_STD_VER > 11
1864 template <typename _K2>
1865 _LIBCPP_INLINE_VISIBILITY
1866 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1867 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1868 template <typename _K2>
1869 _LIBCPP_INLINE_VISIBILITY
1870 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1871 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1874 _LIBCPP_INLINE_VISIBILITY
1875 pair<iterator,iterator> equal_range(const key_type& __k)
1876 {return __tree_.__equal_range_multi(__k);}
1877 _LIBCPP_INLINE_VISIBILITY
1878 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1879 {return __tree_.__equal_range_multi(__k);}
1880 #if _LIBCPP_STD_VER > 11
1881 template <typename _K2>
1882 _LIBCPP_INLINE_VISIBILITY
1883 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1884 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1885 template <typename _K2>
1886 _LIBCPP_INLINE_VISIBILITY
1887 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1888 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1892 typedef typename __base::__node __node;
1893 typedef typename __base::__node_allocator __node_allocator;
1894 typedef typename __base::__node_pointer __node_pointer;
1895 typedef typename __base::__node_const_pointer __node_const_pointer;
1896 typedef __map_node_destructor<__node_allocator> _Dp;
1897 typedef unique_ptr<__node, _Dp> __node_holder;
1899 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1900 __node_holder __construct_node();
1901 template <class _A0>
1903 __construct_node(_A0&& __a0);
1904 #ifndef _LIBCPP_HAS_NO_VARIADICS
1905 template <class _A0, class _A1, class ..._Args>
1906 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1907 #endif // _LIBCPP_HAS_NO_VARIADICS
1908 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1911 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1913 template <class _Key, class _Tp, class _Compare, class _Allocator>
1914 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1915 : __tree_(_VSTD::move(__m.__tree_), __a)
1917 if (__a != __m.get_allocator())
1919 const_iterator __e = cend();
1920 while (!__m.empty())
1921 __tree_.__insert_multi(__e.__i_,
1922 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1926 template <class _Key, class _Tp, class _Compare, class _Allocator>
1927 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1928 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1930 __node_allocator& __na = __tree_.__node_alloc();
1931 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1932 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
1933 __h.get_deleter().__first_constructed = true;
1934 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1935 __h.get_deleter().__second_constructed = true;
1939 template <class _Key, class _Tp, class _Compare, class _Allocator>
1940 template <class _A0>
1941 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1942 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1944 __node_allocator& __na = __tree_.__node_alloc();
1945 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1946 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1947 __h.get_deleter().__first_constructed = true;
1948 __h.get_deleter().__second_constructed = true;
1952 #ifndef _LIBCPP_HAS_NO_VARIADICS
1954 template <class _Key, class _Tp, class _Compare, class _Allocator>
1955 template <class _A0, class _A1, class ..._Args>
1956 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1957 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1959 __node_allocator& __na = __tree_.__node_alloc();
1960 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1961 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1962 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1963 _VSTD::forward<_Args>(__args)...);
1964 __h.get_deleter().__first_constructed = true;
1965 __h.get_deleter().__second_constructed = true;
1969 #endif // _LIBCPP_HAS_NO_VARIADICS
1970 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1972 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1974 template <class _Key, class _Tp, class _Compare, class _Allocator>
1975 template <class ..._Args>
1976 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1977 multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1979 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1980 iterator __r = __tree_.__node_insert_multi(__h.get());
1985 template <class _Key, class _Tp, class _Compare, class _Allocator>
1986 template <class ..._Args>
1987 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1988 multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1991 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1992 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get());
1997 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1999 template <class _Key, class _Tp, class _Compare, class _Allocator>
2000 inline _LIBCPP_INLINE_VISIBILITY
2002 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2003 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2005 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2008 template <class _Key, class _Tp, class _Compare, class _Allocator>
2009 inline _LIBCPP_INLINE_VISIBILITY
2011 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2012 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2014 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2017 template <class _Key, class _Tp, class _Compare, class _Allocator>
2018 inline _LIBCPP_INLINE_VISIBILITY
2020 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2021 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2023 return !(__x == __y);
2026 template <class _Key, class _Tp, class _Compare, class _Allocator>
2027 inline _LIBCPP_INLINE_VISIBILITY
2029 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2030 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2035 template <class _Key, class _Tp, class _Compare, class _Allocator>
2036 inline _LIBCPP_INLINE_VISIBILITY
2038 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2039 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2041 return !(__x < __y);
2044 template <class _Key, class _Tp, class _Compare, class _Allocator>
2045 inline _LIBCPP_INLINE_VISIBILITY
2047 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2048 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2050 return !(__y < __x);
2053 template <class _Key, class _Tp, class _Compare, class _Allocator>
2054 inline _LIBCPP_INLINE_VISIBILITY
2056 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2057 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2058 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2063 _LIBCPP_END_NAMESPACE_STD
2065 #endif // _LIBCPP_MAP