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
838 explicit map(const key_compare& __comp = key_compare())
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(__comp)) {}
845 _LIBCPP_INLINE_VISIBILITY
846 explicit map(const key_compare& __comp, const allocator_type& __a)
847 : __tree_(__vc(__comp), __a) {}
849 template <class _InputIterator>
850 _LIBCPP_INLINE_VISIBILITY
851 map(_InputIterator __f, _InputIterator __l,
852 const key_compare& __comp = key_compare())
853 : __tree_(__vc(__comp))
858 template <class _InputIterator>
859 _LIBCPP_INLINE_VISIBILITY
860 map(_InputIterator __f, _InputIterator __l,
861 const key_compare& __comp, const allocator_type& __a)
862 : __tree_(__vc(__comp), __a)
867 #if _LIBCPP_STD_VER > 11
868 template <class _InputIterator>
869 _LIBCPP_INLINE_VISIBILITY
870 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
871 : map(__f, __l, key_compare(), __a) {}
874 _LIBCPP_INLINE_VISIBILITY
876 : __tree_(__m.__tree_)
878 insert(__m.begin(), __m.end());
881 _LIBCPP_INLINE_VISIBILITY
882 map& operator=(const map& __m)
884 #if __cplusplus >= 201103L
885 __tree_ = __m.__tree_;
888 __tree_.value_comp() = __m.__tree_.value_comp();
889 __tree_.__copy_assign_alloc(__m.__tree_);
890 insert(__m.begin(), __m.end());
895 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
897 _LIBCPP_INLINE_VISIBILITY
899 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
900 : __tree_(_VSTD::move(__m.__tree_))
904 map(map&& __m, const allocator_type& __a);
906 _LIBCPP_INLINE_VISIBILITY
907 map& operator=(map&& __m)
908 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
910 __tree_ = _VSTD::move(__m.__tree_);
914 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
916 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
918 _LIBCPP_INLINE_VISIBILITY
919 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
920 : __tree_(__vc(__comp))
922 insert(__il.begin(), __il.end());
925 _LIBCPP_INLINE_VISIBILITY
926 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
927 : __tree_(__vc(__comp), __a)
929 insert(__il.begin(), __il.end());
932 #if _LIBCPP_STD_VER > 11
933 _LIBCPP_INLINE_VISIBILITY
934 map(initializer_list<value_type> __il, const allocator_type& __a)
935 : map(__il, key_compare(), __a) {}
938 _LIBCPP_INLINE_VISIBILITY
939 map& operator=(initializer_list<value_type> __il)
941 __tree_.__assign_unique(__il.begin(), __il.end());
945 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
947 _LIBCPP_INLINE_VISIBILITY
948 explicit map(const allocator_type& __a)
953 _LIBCPP_INLINE_VISIBILITY
954 map(const map& __m, const allocator_type& __a)
955 : __tree_(__m.__tree_.value_comp(), __a)
957 insert(__m.begin(), __m.end());
960 _LIBCPP_INLINE_VISIBILITY
961 iterator begin() _NOEXCEPT {return __tree_.begin();}
962 _LIBCPP_INLINE_VISIBILITY
963 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
964 _LIBCPP_INLINE_VISIBILITY
965 iterator end() _NOEXCEPT {return __tree_.end();}
966 _LIBCPP_INLINE_VISIBILITY
967 const_iterator end() const _NOEXCEPT {return __tree_.end();}
969 _LIBCPP_INLINE_VISIBILITY
970 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
971 _LIBCPP_INLINE_VISIBILITY
972 const_reverse_iterator rbegin() const _NOEXCEPT
973 {return const_reverse_iterator(end());}
974 _LIBCPP_INLINE_VISIBILITY
975 reverse_iterator rend() _NOEXCEPT
976 {return reverse_iterator(begin());}
977 _LIBCPP_INLINE_VISIBILITY
978 const_reverse_iterator rend() const _NOEXCEPT
979 {return const_reverse_iterator(begin());}
981 _LIBCPP_INLINE_VISIBILITY
982 const_iterator cbegin() const _NOEXCEPT {return begin();}
983 _LIBCPP_INLINE_VISIBILITY
984 const_iterator cend() const _NOEXCEPT {return end();}
985 _LIBCPP_INLINE_VISIBILITY
986 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
987 _LIBCPP_INLINE_VISIBILITY
988 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
990 _LIBCPP_INLINE_VISIBILITY
991 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
992 _LIBCPP_INLINE_VISIBILITY
993 size_type size() const _NOEXCEPT {return __tree_.size();}
994 _LIBCPP_INLINE_VISIBILITY
995 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
997 mapped_type& operator[](const key_type& __k);
998 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
999 mapped_type& operator[](key_type&& __k);
1002 mapped_type& at(const key_type& __k);
1003 const mapped_type& at(const key_type& __k) const;
1005 _LIBCPP_INLINE_VISIBILITY
1006 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1007 _LIBCPP_INLINE_VISIBILITY
1008 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1009 _LIBCPP_INLINE_VISIBILITY
1010 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1012 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1013 #ifndef _LIBCPP_HAS_NO_VARIADICS
1015 template <class ..._Args>
1016 pair<iterator, bool>
1017 emplace(_Args&& ...__args);
1019 template <class ..._Args>
1021 emplace_hint(const_iterator __p, _Args&& ...__args);
1023 #endif // _LIBCPP_HAS_NO_VARIADICS
1025 template <class _Pp,
1026 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1027 _LIBCPP_INLINE_VISIBILITY
1028 pair<iterator, bool> insert(_Pp&& __p)
1029 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1031 template <class _Pp,
1032 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1033 _LIBCPP_INLINE_VISIBILITY
1034 iterator insert(const_iterator __pos, _Pp&& __p)
1035 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1037 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1039 _LIBCPP_INLINE_VISIBILITY
1040 pair<iterator, bool>
1041 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1043 _LIBCPP_INLINE_VISIBILITY
1045 insert(const_iterator __p, const value_type& __v)
1046 {return __tree_.__insert_unique(__p.__i_, __v);}
1048 template <class _InputIterator>
1049 _LIBCPP_INLINE_VISIBILITY
1050 void insert(_InputIterator __f, _InputIterator __l)
1052 for (const_iterator __e = cend(); __f != __l; ++__f)
1053 insert(__e.__i_, *__f);
1056 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1058 _LIBCPP_INLINE_VISIBILITY
1059 void insert(initializer_list<value_type> __il)
1060 {insert(__il.begin(), __il.end());}
1062 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1064 _LIBCPP_INLINE_VISIBILITY
1065 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1066 _LIBCPP_INLINE_VISIBILITY
1067 size_type erase(const key_type& __k)
1068 {return __tree_.__erase_unique(__k);}
1069 _LIBCPP_INLINE_VISIBILITY
1070 iterator erase(const_iterator __f, const_iterator __l)
1071 {return __tree_.erase(__f.__i_, __l.__i_);}
1072 _LIBCPP_INLINE_VISIBILITY
1073 void clear() _NOEXCEPT {__tree_.clear();}
1075 _LIBCPP_INLINE_VISIBILITY
1077 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1078 {__tree_.swap(__m.__tree_);}
1080 _LIBCPP_INLINE_VISIBILITY
1081 iterator find(const key_type& __k) {return __tree_.find(__k);}
1082 _LIBCPP_INLINE_VISIBILITY
1083 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1084 #if _LIBCPP_STD_VER > 11
1085 template <typename _K2>
1086 _LIBCPP_INLINE_VISIBILITY
1087 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1088 find(const _K2& __k) {return __tree_.find(__k);}
1089 template <typename _K2>
1090 _LIBCPP_INLINE_VISIBILITY
1091 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1092 find(const _K2& __k) const {return __tree_.find(__k);}
1095 _LIBCPP_INLINE_VISIBILITY
1096 size_type count(const key_type& __k) const
1097 {return __tree_.__count_unique(__k);}
1098 _LIBCPP_INLINE_VISIBILITY
1099 iterator lower_bound(const key_type& __k)
1100 {return __tree_.lower_bound(__k);}
1101 _LIBCPP_INLINE_VISIBILITY
1102 const_iterator lower_bound(const key_type& __k) const
1103 {return __tree_.lower_bound(__k);}
1104 #if _LIBCPP_STD_VER > 11
1105 template <typename _K2>
1106 _LIBCPP_INLINE_VISIBILITY
1107 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1108 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1110 template <typename _K2>
1111 _LIBCPP_INLINE_VISIBILITY
1112 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1113 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1116 _LIBCPP_INLINE_VISIBILITY
1117 iterator upper_bound(const key_type& __k)
1118 {return __tree_.upper_bound(__k);}
1119 _LIBCPP_INLINE_VISIBILITY
1120 const_iterator upper_bound(const key_type& __k) const
1121 {return __tree_.upper_bound(__k);}
1122 #if _LIBCPP_STD_VER > 11
1123 template <typename _K2>
1124 _LIBCPP_INLINE_VISIBILITY
1125 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1126 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1127 template <typename _K2>
1128 _LIBCPP_INLINE_VISIBILITY
1129 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1130 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1133 _LIBCPP_INLINE_VISIBILITY
1134 pair<iterator,iterator> equal_range(const key_type& __k)
1135 {return __tree_.__equal_range_unique(__k);}
1136 _LIBCPP_INLINE_VISIBILITY
1137 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1138 {return __tree_.__equal_range_unique(__k);}
1139 #if _LIBCPP_STD_VER > 11
1140 template <typename _K2>
1141 _LIBCPP_INLINE_VISIBILITY
1142 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1143 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
1144 template <typename _K2>
1145 _LIBCPP_INLINE_VISIBILITY
1146 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1147 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1151 typedef typename __base::__node __node;
1152 typedef typename __base::__node_allocator __node_allocator;
1153 typedef typename __base::__node_pointer __node_pointer;
1154 typedef typename __base::__node_const_pointer __node_const_pointer;
1155 typedef typename __base::__node_base_pointer __node_base_pointer;
1156 typedef typename __base::__node_base_const_pointer __node_base_const_pointer;
1157 typedef __map_node_destructor<__node_allocator> _Dp;
1158 typedef unique_ptr<__node, _Dp> __node_holder;
1160 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1161 __node_holder __construct_node();
1162 template <class _A0>
1163 __node_holder __construct_node(_A0&& __a0);
1164 __node_holder __construct_node_with_key(key_type&& __k);
1165 #ifndef _LIBCPP_HAS_NO_VARIADICS
1166 template <class _A0, class _A1, class ..._Args>
1167 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1168 #endif // _LIBCPP_HAS_NO_VARIADICS
1170 __node_holder __construct_node_with_key(const key_type& __k);
1172 __node_base_pointer&
1173 __find_equal_key(__node_base_pointer& __parent, const key_type& __k);
1174 __node_base_const_pointer
1175 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
1178 // Find place to insert if __k doesn't exist
1179 // Set __parent to parent of null leaf
1180 // Return reference to null leaf
1181 // If __k exists, set parent to node of __k and return reference to node of __k
1182 template <class _Key, class _Tp, class _Compare, class _Allocator>
1183 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1184 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
1185 const key_type& __k)
1187 __node_pointer __nd = __tree_.__root();
1188 if (__nd != nullptr)
1192 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1194 if (__nd->__left_ != nullptr)
1195 __nd = static_cast<__node_pointer>(__nd->__left_);
1198 __parent = static_cast<__node_base_pointer>(__nd);
1199 return __parent->__left_;
1202 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1204 if (__nd->__right_ != nullptr)
1205 __nd = static_cast<__node_pointer>(__nd->__right_);
1208 __parent = static_cast<__node_base_pointer>(__nd);
1209 return __parent->__right_;
1214 __parent = static_cast<__node_base_pointer>(__nd);
1219 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1220 return __parent->__left_;
1224 // Set __parent to parent of null leaf and
1225 // return reference to null leaf iv __k does not exist.
1226 // If __k exists, set parent to node of __k and return reference to node of __k
1227 template <class _Key, class _Tp, class _Compare, class _Allocator>
1228 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer
1229 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent,
1230 const key_type& __k) const
1232 __node_const_pointer __nd = __tree_.__root();
1233 if (__nd != nullptr)
1237 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1239 if (__nd->__left_ != nullptr)
1240 __nd = static_cast<__node_pointer>(__nd->__left_);
1243 __parent = static_cast<__node_base_pointer>(__nd);
1244 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1247 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1249 if (__nd->__right_ != nullptr)
1250 __nd = static_cast<__node_pointer>(__nd->__right_);
1253 __parent = static_cast<__node_base_pointer>(__nd);
1254 return const_cast<const __node_base_const_pointer&>(__parent->__right_);
1259 __parent = static_cast<__node_base_pointer>(__nd);
1264 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1265 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1268 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1270 template <class _Key, class _Tp, class _Compare, class _Allocator>
1271 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1272 : __tree_(_VSTD::move(__m.__tree_), __a)
1274 if (__a != __m.get_allocator())
1276 const_iterator __e = cend();
1277 while (!__m.empty())
1278 __tree_.__insert_unique(__e.__i_,
1279 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1283 template <class _Key, class _Tp, class _Compare, class _Allocator>
1284 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1285 map<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1287 __node_allocator& __na = __tree_.__node_alloc();
1288 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1289 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
1290 __h.get_deleter().__first_constructed = true;
1291 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1292 __h.get_deleter().__second_constructed = true;
1296 template <class _Key, class _Tp, class _Compare, class _Allocator>
1297 template <class _A0>
1298 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1299 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1301 __node_allocator& __na = __tree_.__node_alloc();
1302 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1303 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1304 __h.get_deleter().__first_constructed = true;
1305 __h.get_deleter().__second_constructed = true;
1309 template <class _Key, class _Tp, class _Compare, class _Allocator>
1310 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1311 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k)
1313 __node_allocator& __na = __tree_.__node_alloc();
1314 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1315 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1316 __h.get_deleter().__first_constructed = true;
1317 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1318 __h.get_deleter().__second_constructed = true;
1322 #ifndef _LIBCPP_HAS_NO_VARIADICS
1324 template <class _Key, class _Tp, class _Compare, class _Allocator>
1325 template <class _A0, class _A1, class ..._Args>
1326 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1327 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1329 __node_allocator& __na = __tree_.__node_alloc();
1330 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1331 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1332 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1333 _VSTD::forward<_Args>(__args)...);
1334 __h.get_deleter().__first_constructed = true;
1335 __h.get_deleter().__second_constructed = true;
1339 #endif // _LIBCPP_HAS_NO_VARIADICS
1341 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1343 template <class _Key, class _Tp, class _Compare, class _Allocator>
1344 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1345 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1347 __node_allocator& __na = __tree_.__node_alloc();
1348 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1349 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1350 __h.get_deleter().__first_constructed = true;
1351 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1352 __h.get_deleter().__second_constructed = true;
1353 return _VSTD::move(__h); // explicitly moved for C++03
1356 template <class _Key, class _Tp, class _Compare, class _Allocator>
1358 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1360 __node_base_pointer __parent;
1361 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1362 __node_pointer __r = static_cast<__node_pointer>(__child);
1363 if (__child == nullptr)
1365 __node_holder __h = __construct_node_with_key(__k);
1366 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1367 __r = __h.release();
1369 return __r->__value_.__cc.second;
1372 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1374 template <class _Key, class _Tp, class _Compare, class _Allocator>
1376 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1378 __node_base_pointer __parent;
1379 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1380 __node_pointer __r = static_cast<__node_pointer>(__child);
1381 if (__child == nullptr)
1383 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1384 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1385 __r = __h.release();
1387 return __r->__value_.__cc.second;
1390 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1392 template <class _Key, class _Tp, class _Compare, class _Allocator>
1394 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1396 __node_base_pointer __parent;
1397 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1398 #ifndef _LIBCPP_NO_EXCEPTIONS
1399 if (__child == nullptr)
1400 throw out_of_range("map::at: key not found");
1401 #endif // _LIBCPP_NO_EXCEPTIONS
1402 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1405 template <class _Key, class _Tp, class _Compare, class _Allocator>
1407 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1409 __node_base_const_pointer __parent;
1410 __node_base_const_pointer __child = __find_equal_key(__parent, __k);
1411 #ifndef _LIBCPP_NO_EXCEPTIONS
1412 if (__child == nullptr)
1413 throw out_of_range("map::at: key not found");
1414 #endif // _LIBCPP_NO_EXCEPTIONS
1415 return static_cast<__node_const_pointer>(__child)->__value_.__cc.second;
1418 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1420 template <class _Key, class _Tp, class _Compare, class _Allocator>
1421 template <class ..._Args>
1422 pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
1423 map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1425 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1426 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
1432 template <class _Key, class _Tp, class _Compare, class _Allocator>
1433 template <class ..._Args>
1434 typename map<_Key, _Tp, _Compare, _Allocator>::iterator
1435 map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1438 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1439 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get());
1440 if (__r.__i_.__ptr_ == __h.get())
1445 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1447 template <class _Key, class _Tp, class _Compare, class _Allocator>
1448 inline _LIBCPP_INLINE_VISIBILITY
1450 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1451 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1453 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1456 template <class _Key, class _Tp, class _Compare, class _Allocator>
1457 inline _LIBCPP_INLINE_VISIBILITY
1459 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1460 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1462 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1465 template <class _Key, class _Tp, class _Compare, class _Allocator>
1466 inline _LIBCPP_INLINE_VISIBILITY
1468 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1469 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1471 return !(__x == __y);
1474 template <class _Key, class _Tp, class _Compare, class _Allocator>
1475 inline _LIBCPP_INLINE_VISIBILITY
1477 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1478 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1483 template <class _Key, class _Tp, class _Compare, class _Allocator>
1484 inline _LIBCPP_INLINE_VISIBILITY
1486 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1487 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1489 return !(__x < __y);
1492 template <class _Key, class _Tp, class _Compare, class _Allocator>
1493 inline _LIBCPP_INLINE_VISIBILITY
1495 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1496 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1498 return !(__y < __x);
1501 template <class _Key, class _Tp, class _Compare, class _Allocator>
1502 inline _LIBCPP_INLINE_VISIBILITY
1504 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1505 map<_Key, _Tp, _Compare, _Allocator>& __y)
1506 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1511 template <class _Key, class _Tp, class _Compare = less<_Key>,
1512 class _Allocator = allocator<pair<const _Key, _Tp> > >
1513 class _LIBCPP_TYPE_VIS_ONLY multimap
1517 typedef _Key key_type;
1518 typedef _Tp mapped_type;
1519 typedef pair<const key_type, mapped_type> value_type;
1520 typedef pair<key_type, mapped_type> __nc_value_type;
1521 typedef _Compare key_compare;
1522 typedef _Allocator allocator_type;
1523 typedef value_type& reference;
1524 typedef const value_type& const_reference;
1526 class _LIBCPP_TYPE_VIS_ONLY value_compare
1527 : public binary_function<value_type, value_type, bool>
1529 friend class multimap;
1533 _LIBCPP_INLINE_VISIBILITY
1534 value_compare(key_compare c) : comp(c) {}
1536 _LIBCPP_INLINE_VISIBILITY
1537 bool operator()(const value_type& __x, const value_type& __y) const
1538 {return comp(__x.first, __y.first);}
1543 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
1544 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1545 typedef typename allocator_traits<allocator_type>::template
1546 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1547 rebind_alloc<__value_type>
1549 rebind_alloc<__value_type>::other
1552 typedef __tree<__value_type, __vc, __allocator_type> __base;
1553 typedef typename __base::__node_traits __node_traits;
1554 typedef allocator_traits<allocator_type> __alloc_traits;
1559 typedef typename __alloc_traits::pointer pointer;
1560 typedef typename __alloc_traits::const_pointer const_pointer;
1561 typedef typename __alloc_traits::size_type size_type;
1562 typedef typename __alloc_traits::difference_type difference_type;
1563 typedef __map_iterator<typename __base::iterator> iterator;
1564 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1565 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1566 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1568 _LIBCPP_INLINE_VISIBILITY
1569 explicit multimap(const key_compare& __comp = key_compare())
1571 is_nothrow_default_constructible<allocator_type>::value &&
1572 is_nothrow_default_constructible<key_compare>::value &&
1573 is_nothrow_copy_constructible<key_compare>::value)
1574 : __tree_(__vc(__comp)) {}
1576 _LIBCPP_INLINE_VISIBILITY
1577 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1578 : __tree_(__vc(__comp), __a) {}
1580 template <class _InputIterator>
1581 _LIBCPP_INLINE_VISIBILITY
1582 multimap(_InputIterator __f, _InputIterator __l,
1583 const key_compare& __comp = key_compare())
1584 : __tree_(__vc(__comp))
1589 template <class _InputIterator>
1590 _LIBCPP_INLINE_VISIBILITY
1591 multimap(_InputIterator __f, _InputIterator __l,
1592 const key_compare& __comp, const allocator_type& __a)
1593 : __tree_(__vc(__comp), __a)
1598 #if _LIBCPP_STD_VER > 11
1599 template <class _InputIterator>
1600 _LIBCPP_INLINE_VISIBILITY
1601 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1602 : multimap(__f, __l, key_compare(), __a) {}
1605 _LIBCPP_INLINE_VISIBILITY
1606 multimap(const multimap& __m)
1607 : __tree_(__m.__tree_.value_comp(),
1608 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1610 insert(__m.begin(), __m.end());
1613 _LIBCPP_INLINE_VISIBILITY
1614 multimap& operator=(const multimap& __m)
1616 #if __cplusplus >= 201103L
1617 __tree_ = __m.__tree_;
1620 __tree_.value_comp() = __m.__tree_.value_comp();
1621 __tree_.__copy_assign_alloc(__m.__tree_);
1622 insert(__m.begin(), __m.end());
1627 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1629 _LIBCPP_INLINE_VISIBILITY
1630 multimap(multimap&& __m)
1631 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1632 : __tree_(_VSTD::move(__m.__tree_))
1636 multimap(multimap&& __m, const allocator_type& __a);
1638 _LIBCPP_INLINE_VISIBILITY
1639 multimap& operator=(multimap&& __m)
1640 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1642 __tree_ = _VSTD::move(__m.__tree_);
1646 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1648 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1650 _LIBCPP_INLINE_VISIBILITY
1651 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1652 : __tree_(__vc(__comp))
1654 insert(__il.begin(), __il.end());
1657 _LIBCPP_INLINE_VISIBILITY
1658 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1659 : __tree_(__vc(__comp), __a)
1661 insert(__il.begin(), __il.end());
1664 #if _LIBCPP_STD_VER > 11
1665 _LIBCPP_INLINE_VISIBILITY
1666 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1667 : multimap(__il, key_compare(), __a) {}
1670 _LIBCPP_INLINE_VISIBILITY
1671 multimap& operator=(initializer_list<value_type> __il)
1673 __tree_.__assign_multi(__il.begin(), __il.end());
1677 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1679 _LIBCPP_INLINE_VISIBILITY
1680 explicit multimap(const allocator_type& __a)
1685 _LIBCPP_INLINE_VISIBILITY
1686 multimap(const multimap& __m, const allocator_type& __a)
1687 : __tree_(__m.__tree_.value_comp(), __a)
1689 insert(__m.begin(), __m.end());
1692 _LIBCPP_INLINE_VISIBILITY
1693 iterator begin() _NOEXCEPT {return __tree_.begin();}
1694 _LIBCPP_INLINE_VISIBILITY
1695 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1696 _LIBCPP_INLINE_VISIBILITY
1697 iterator end() _NOEXCEPT {return __tree_.end();}
1698 _LIBCPP_INLINE_VISIBILITY
1699 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1701 _LIBCPP_INLINE_VISIBILITY
1702 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1703 _LIBCPP_INLINE_VISIBILITY
1704 const_reverse_iterator rbegin() const _NOEXCEPT
1705 {return const_reverse_iterator(end());}
1706 _LIBCPP_INLINE_VISIBILITY
1707 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1708 _LIBCPP_INLINE_VISIBILITY
1709 const_reverse_iterator rend() const _NOEXCEPT
1710 {return const_reverse_iterator(begin());}
1712 _LIBCPP_INLINE_VISIBILITY
1713 const_iterator cbegin() const _NOEXCEPT {return begin();}
1714 _LIBCPP_INLINE_VISIBILITY
1715 const_iterator cend() const _NOEXCEPT {return end();}
1716 _LIBCPP_INLINE_VISIBILITY
1717 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1718 _LIBCPP_INLINE_VISIBILITY
1719 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1721 _LIBCPP_INLINE_VISIBILITY
1722 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1723 _LIBCPP_INLINE_VISIBILITY
1724 size_type size() const _NOEXCEPT {return __tree_.size();}
1725 _LIBCPP_INLINE_VISIBILITY
1726 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1728 _LIBCPP_INLINE_VISIBILITY
1729 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1730 _LIBCPP_INLINE_VISIBILITY
1731 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1732 _LIBCPP_INLINE_VISIBILITY
1733 value_compare value_comp() const
1734 {return value_compare(__tree_.value_comp().key_comp());}
1736 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1737 #ifndef _LIBCPP_HAS_NO_VARIADICS
1739 template <class ..._Args>
1741 emplace(_Args&& ...__args);
1743 template <class ..._Args>
1745 emplace_hint(const_iterator __p, _Args&& ...__args);
1747 #endif // _LIBCPP_HAS_NO_VARIADICS
1749 template <class _Pp,
1750 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1751 _LIBCPP_INLINE_VISIBILITY
1752 iterator insert(_Pp&& __p)
1753 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1755 template <class _Pp,
1756 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1757 _LIBCPP_INLINE_VISIBILITY
1758 iterator insert(const_iterator __pos, _Pp&& __p)
1759 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1761 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1763 _LIBCPP_INLINE_VISIBILITY
1764 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1766 _LIBCPP_INLINE_VISIBILITY
1767 iterator insert(const_iterator __p, const value_type& __v)
1768 {return __tree_.__insert_multi(__p.__i_, __v);}
1770 template <class _InputIterator>
1771 _LIBCPP_INLINE_VISIBILITY
1772 void insert(_InputIterator __f, _InputIterator __l)
1774 for (const_iterator __e = cend(); __f != __l; ++__f)
1775 __tree_.__insert_multi(__e.__i_, *__f);
1778 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1780 _LIBCPP_INLINE_VISIBILITY
1781 void insert(initializer_list<value_type> __il)
1782 {insert(__il.begin(), __il.end());}
1784 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1786 _LIBCPP_INLINE_VISIBILITY
1787 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1788 _LIBCPP_INLINE_VISIBILITY
1789 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1790 _LIBCPP_INLINE_VISIBILITY
1791 iterator erase(const_iterator __f, const_iterator __l)
1792 {return __tree_.erase(__f.__i_, __l.__i_);}
1793 _LIBCPP_INLINE_VISIBILITY
1794 void clear() {__tree_.clear();}
1796 _LIBCPP_INLINE_VISIBILITY
1797 void swap(multimap& __m)
1798 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1799 {__tree_.swap(__m.__tree_);}
1801 _LIBCPP_INLINE_VISIBILITY
1802 iterator find(const key_type& __k) {return __tree_.find(__k);}
1803 _LIBCPP_INLINE_VISIBILITY
1804 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1805 #if _LIBCPP_STD_VER > 11
1806 template <typename _K2>
1807 _LIBCPP_INLINE_VISIBILITY
1808 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1809 find(const _K2& __k) {return __tree_.find(__k);}
1810 template <typename _K2>
1811 _LIBCPP_INLINE_VISIBILITY
1812 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1813 find(const _K2& __k) const {return __tree_.find(__k);}
1816 _LIBCPP_INLINE_VISIBILITY
1817 size_type count(const key_type& __k) const
1818 {return __tree_.__count_multi(__k);}
1819 _LIBCPP_INLINE_VISIBILITY
1820 iterator lower_bound(const key_type& __k)
1821 {return __tree_.lower_bound(__k);}
1822 _LIBCPP_INLINE_VISIBILITY
1823 const_iterator lower_bound(const key_type& __k) const
1824 {return __tree_.lower_bound(__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 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1831 template <typename _K2>
1832 _LIBCPP_INLINE_VISIBILITY
1833 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1834 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1837 _LIBCPP_INLINE_VISIBILITY
1838 iterator upper_bound(const key_type& __k)
1839 {return __tree_.upper_bound(__k);}
1840 _LIBCPP_INLINE_VISIBILITY
1841 const_iterator upper_bound(const key_type& __k) const
1842 {return __tree_.upper_bound(__k);}
1843 #if _LIBCPP_STD_VER > 11
1844 template <typename _K2>
1845 _LIBCPP_INLINE_VISIBILITY
1846 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1847 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1848 template <typename _K2>
1849 _LIBCPP_INLINE_VISIBILITY
1850 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1851 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1854 _LIBCPP_INLINE_VISIBILITY
1855 pair<iterator,iterator> equal_range(const key_type& __k)
1856 {return __tree_.__equal_range_multi(__k);}
1857 _LIBCPP_INLINE_VISIBILITY
1858 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1859 {return __tree_.__equal_range_multi(__k);}
1860 #if _LIBCPP_STD_VER > 11
1861 template <typename _K2>
1862 _LIBCPP_INLINE_VISIBILITY
1863 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1864 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1865 template <typename _K2>
1866 _LIBCPP_INLINE_VISIBILITY
1867 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1868 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1872 typedef typename __base::__node __node;
1873 typedef typename __base::__node_allocator __node_allocator;
1874 typedef typename __base::__node_pointer __node_pointer;
1875 typedef typename __base::__node_const_pointer __node_const_pointer;
1876 typedef __map_node_destructor<__node_allocator> _Dp;
1877 typedef unique_ptr<__node, _Dp> __node_holder;
1879 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1880 __node_holder __construct_node();
1881 template <class _A0>
1883 __construct_node(_A0&& __a0);
1884 #ifndef _LIBCPP_HAS_NO_VARIADICS
1885 template <class _A0, class _A1, class ..._Args>
1886 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1887 #endif // _LIBCPP_HAS_NO_VARIADICS
1888 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1891 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1893 template <class _Key, class _Tp, class _Compare, class _Allocator>
1894 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1895 : __tree_(_VSTD::move(__m.__tree_), __a)
1897 if (__a != __m.get_allocator())
1899 const_iterator __e = cend();
1900 while (!__m.empty())
1901 __tree_.__insert_multi(__e.__i_,
1902 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1906 template <class _Key, class _Tp, class _Compare, class _Allocator>
1907 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1908 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1910 __node_allocator& __na = __tree_.__node_alloc();
1911 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1912 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
1913 __h.get_deleter().__first_constructed = true;
1914 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1915 __h.get_deleter().__second_constructed = true;
1919 template <class _Key, class _Tp, class _Compare, class _Allocator>
1920 template <class _A0>
1921 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1922 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1924 __node_allocator& __na = __tree_.__node_alloc();
1925 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1926 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1927 __h.get_deleter().__first_constructed = true;
1928 __h.get_deleter().__second_constructed = true;
1932 #ifndef _LIBCPP_HAS_NO_VARIADICS
1934 template <class _Key, class _Tp, class _Compare, class _Allocator>
1935 template <class _A0, class _A1, class ..._Args>
1936 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1937 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1939 __node_allocator& __na = __tree_.__node_alloc();
1940 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1941 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1942 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1943 _VSTD::forward<_Args>(__args)...);
1944 __h.get_deleter().__first_constructed = true;
1945 __h.get_deleter().__second_constructed = true;
1949 #endif // _LIBCPP_HAS_NO_VARIADICS
1950 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1952 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1954 template <class _Key, class _Tp, class _Compare, class _Allocator>
1955 template <class ..._Args>
1956 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1957 multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1959 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1960 iterator __r = __tree_.__node_insert_multi(__h.get());
1965 template <class _Key, class _Tp, class _Compare, class _Allocator>
1966 template <class ..._Args>
1967 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1968 multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1971 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1972 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get());
1977 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1979 template <class _Key, class _Tp, class _Compare, class _Allocator>
1980 inline _LIBCPP_INLINE_VISIBILITY
1982 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1983 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1985 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1988 template <class _Key, class _Tp, class _Compare, class _Allocator>
1989 inline _LIBCPP_INLINE_VISIBILITY
1991 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1992 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1994 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1997 template <class _Key, class _Tp, class _Compare, class _Allocator>
1998 inline _LIBCPP_INLINE_VISIBILITY
2000 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2001 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2003 return !(__x == __y);
2006 template <class _Key, class _Tp, class _Compare, class _Allocator>
2007 inline _LIBCPP_INLINE_VISIBILITY
2009 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2010 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2015 template <class _Key, class _Tp, class _Compare, class _Allocator>
2016 inline _LIBCPP_INLINE_VISIBILITY
2018 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2019 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2021 return !(__x < __y);
2024 template <class _Key, class _Tp, class _Compare, class _Allocator>
2025 inline _LIBCPP_INLINE_VISIBILITY
2027 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2028 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2030 return !(__y < __x);
2033 template <class _Key, class _Tp, class _Compare, class _Allocator>
2034 inline _LIBCPP_INLINE_VISIBILITY
2036 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2037 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2038 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2043 _LIBCPP_END_NAMESPACE_STD
2045 #endif // _LIBCPP_MAP