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_;
889 __tree_.value_comp() = __m.__tree_.value_comp();
890 __tree_.__copy_assign_alloc(__m.__tree_);
891 insert(__m.begin(), __m.end());
897 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
899 _LIBCPP_INLINE_VISIBILITY
901 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
902 : __tree_(_VSTD::move(__m.__tree_))
906 map(map&& __m, const allocator_type& __a);
908 _LIBCPP_INLINE_VISIBILITY
909 map& operator=(map&& __m)
910 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
912 __tree_ = _VSTD::move(__m.__tree_);
916 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
918 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
920 _LIBCPP_INLINE_VISIBILITY
921 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
922 : __tree_(__vc(__comp))
924 insert(__il.begin(), __il.end());
927 _LIBCPP_INLINE_VISIBILITY
928 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
929 : __tree_(__vc(__comp), __a)
931 insert(__il.begin(), __il.end());
934 #if _LIBCPP_STD_VER > 11
935 _LIBCPP_INLINE_VISIBILITY
936 map(initializer_list<value_type> __il, const allocator_type& __a)
937 : map(__il, key_compare(), __a) {}
940 _LIBCPP_INLINE_VISIBILITY
941 map& operator=(initializer_list<value_type> __il)
943 __tree_.__assign_unique(__il.begin(), __il.end());
947 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
949 _LIBCPP_INLINE_VISIBILITY
950 explicit map(const allocator_type& __a)
955 _LIBCPP_INLINE_VISIBILITY
956 map(const map& __m, const allocator_type& __a)
957 : __tree_(__m.__tree_.value_comp(), __a)
959 insert(__m.begin(), __m.end());
962 _LIBCPP_INLINE_VISIBILITY
963 iterator begin() _NOEXCEPT {return __tree_.begin();}
964 _LIBCPP_INLINE_VISIBILITY
965 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
966 _LIBCPP_INLINE_VISIBILITY
967 iterator end() _NOEXCEPT {return __tree_.end();}
968 _LIBCPP_INLINE_VISIBILITY
969 const_iterator end() const _NOEXCEPT {return __tree_.end();}
971 _LIBCPP_INLINE_VISIBILITY
972 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
973 _LIBCPP_INLINE_VISIBILITY
974 const_reverse_iterator rbegin() const _NOEXCEPT
975 {return const_reverse_iterator(end());}
976 _LIBCPP_INLINE_VISIBILITY
977 reverse_iterator rend() _NOEXCEPT
978 {return reverse_iterator(begin());}
979 _LIBCPP_INLINE_VISIBILITY
980 const_reverse_iterator rend() const _NOEXCEPT
981 {return const_reverse_iterator(begin());}
983 _LIBCPP_INLINE_VISIBILITY
984 const_iterator cbegin() const _NOEXCEPT {return begin();}
985 _LIBCPP_INLINE_VISIBILITY
986 const_iterator cend() const _NOEXCEPT {return end();}
987 _LIBCPP_INLINE_VISIBILITY
988 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
989 _LIBCPP_INLINE_VISIBILITY
990 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
992 _LIBCPP_INLINE_VISIBILITY
993 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
994 _LIBCPP_INLINE_VISIBILITY
995 size_type size() const _NOEXCEPT {return __tree_.size();}
996 _LIBCPP_INLINE_VISIBILITY
997 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
999 mapped_type& operator[](const key_type& __k);
1000 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1001 mapped_type& operator[](key_type&& __k);
1004 mapped_type& at(const key_type& __k);
1005 const mapped_type& at(const key_type& __k) const;
1007 _LIBCPP_INLINE_VISIBILITY
1008 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1009 _LIBCPP_INLINE_VISIBILITY
1010 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1011 _LIBCPP_INLINE_VISIBILITY
1012 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1014 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1015 #ifndef _LIBCPP_HAS_NO_VARIADICS
1017 template <class ..._Args>
1018 pair<iterator, bool>
1019 emplace(_Args&& ...__args);
1021 template <class ..._Args>
1023 emplace_hint(const_iterator __p, _Args&& ...__args);
1025 #endif // _LIBCPP_HAS_NO_VARIADICS
1027 template <class _Pp,
1028 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1029 _LIBCPP_INLINE_VISIBILITY
1030 pair<iterator, bool> insert(_Pp&& __p)
1031 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1033 template <class _Pp,
1034 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1035 _LIBCPP_INLINE_VISIBILITY
1036 iterator insert(const_iterator __pos, _Pp&& __p)
1037 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1039 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1041 _LIBCPP_INLINE_VISIBILITY
1042 pair<iterator, bool>
1043 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1045 _LIBCPP_INLINE_VISIBILITY
1047 insert(const_iterator __p, const value_type& __v)
1048 {return __tree_.__insert_unique(__p.__i_, __v);}
1050 template <class _InputIterator>
1051 _LIBCPP_INLINE_VISIBILITY
1052 void insert(_InputIterator __f, _InputIterator __l)
1054 for (const_iterator __e = cend(); __f != __l; ++__f)
1055 insert(__e.__i_, *__f);
1058 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1060 _LIBCPP_INLINE_VISIBILITY
1061 void insert(initializer_list<value_type> __il)
1062 {insert(__il.begin(), __il.end());}
1064 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1066 _LIBCPP_INLINE_VISIBILITY
1067 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1068 _LIBCPP_INLINE_VISIBILITY
1069 size_type erase(const key_type& __k)
1070 {return __tree_.__erase_unique(__k);}
1071 _LIBCPP_INLINE_VISIBILITY
1072 iterator erase(const_iterator __f, const_iterator __l)
1073 {return __tree_.erase(__f.__i_, __l.__i_);}
1074 _LIBCPP_INLINE_VISIBILITY
1075 void clear() _NOEXCEPT {__tree_.clear();}
1077 _LIBCPP_INLINE_VISIBILITY
1079 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1080 {__tree_.swap(__m.__tree_);}
1082 _LIBCPP_INLINE_VISIBILITY
1083 iterator find(const key_type& __k) {return __tree_.find(__k);}
1084 _LIBCPP_INLINE_VISIBILITY
1085 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1086 #if _LIBCPP_STD_VER > 11
1087 template <typename _K2>
1088 _LIBCPP_INLINE_VISIBILITY
1089 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1090 find(const _K2& __k) {return __tree_.find(__k);}
1091 template <typename _K2>
1092 _LIBCPP_INLINE_VISIBILITY
1093 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1094 find(const _K2& __k) const {return __tree_.find(__k);}
1097 _LIBCPP_INLINE_VISIBILITY
1098 size_type count(const key_type& __k) const
1099 {return __tree_.__count_unique(__k);}
1100 _LIBCPP_INLINE_VISIBILITY
1101 iterator lower_bound(const key_type& __k)
1102 {return __tree_.lower_bound(__k);}
1103 _LIBCPP_INLINE_VISIBILITY
1104 const_iterator lower_bound(const key_type& __k) const
1105 {return __tree_.lower_bound(__k);}
1106 #if _LIBCPP_STD_VER > 11
1107 template <typename _K2>
1108 _LIBCPP_INLINE_VISIBILITY
1109 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1110 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1112 template <typename _K2>
1113 _LIBCPP_INLINE_VISIBILITY
1114 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1115 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1118 _LIBCPP_INLINE_VISIBILITY
1119 iterator upper_bound(const key_type& __k)
1120 {return __tree_.upper_bound(__k);}
1121 _LIBCPP_INLINE_VISIBILITY
1122 const_iterator upper_bound(const key_type& __k) const
1123 {return __tree_.upper_bound(__k);}
1124 #if _LIBCPP_STD_VER > 11
1125 template <typename _K2>
1126 _LIBCPP_INLINE_VISIBILITY
1127 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1128 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1129 template <typename _K2>
1130 _LIBCPP_INLINE_VISIBILITY
1131 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1132 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1135 _LIBCPP_INLINE_VISIBILITY
1136 pair<iterator,iterator> equal_range(const key_type& __k)
1137 {return __tree_.__equal_range_unique(__k);}
1138 _LIBCPP_INLINE_VISIBILITY
1139 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1140 {return __tree_.__equal_range_unique(__k);}
1141 #if _LIBCPP_STD_VER > 11
1142 template <typename _K2>
1143 _LIBCPP_INLINE_VISIBILITY
1144 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1145 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
1146 template <typename _K2>
1147 _LIBCPP_INLINE_VISIBILITY
1148 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1149 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1153 typedef typename __base::__node __node;
1154 typedef typename __base::__node_allocator __node_allocator;
1155 typedef typename __base::__node_pointer __node_pointer;
1156 typedef typename __base::__node_const_pointer __node_const_pointer;
1157 typedef typename __base::__node_base_pointer __node_base_pointer;
1158 typedef typename __base::__node_base_const_pointer __node_base_const_pointer;
1159 typedef __map_node_destructor<__node_allocator> _Dp;
1160 typedef unique_ptr<__node, _Dp> __node_holder;
1162 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1163 __node_holder __construct_node();
1164 template <class _A0>
1165 __node_holder __construct_node(_A0&& __a0);
1166 __node_holder __construct_node_with_key(key_type&& __k);
1167 #ifndef _LIBCPP_HAS_NO_VARIADICS
1168 template <class _A0, class _A1, class ..._Args>
1169 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1170 #endif // _LIBCPP_HAS_NO_VARIADICS
1172 __node_holder __construct_node_with_key(const key_type& __k);
1174 __node_base_pointer&
1175 __find_equal_key(__node_base_pointer& __parent, const key_type& __k);
1176 __node_base_const_pointer
1177 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
1180 // Find place to insert if __k doesn't exist
1181 // Set __parent to parent of null leaf
1182 // Return reference to null leaf
1183 // If __k exists, set parent to node of __k and return reference to node of __k
1184 template <class _Key, class _Tp, class _Compare, class _Allocator>
1185 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1186 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
1187 const key_type& __k)
1189 __node_pointer __nd = __tree_.__root();
1190 if (__nd != nullptr)
1194 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1196 if (__nd->__left_ != nullptr)
1197 __nd = static_cast<__node_pointer>(__nd->__left_);
1200 __parent = static_cast<__node_base_pointer>(__nd);
1201 return __parent->__left_;
1204 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1206 if (__nd->__right_ != nullptr)
1207 __nd = static_cast<__node_pointer>(__nd->__right_);
1210 __parent = static_cast<__node_base_pointer>(__nd);
1211 return __parent->__right_;
1216 __parent = static_cast<__node_base_pointer>(__nd);
1221 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1222 return __parent->__left_;
1226 // Set __parent to parent of null leaf and
1227 // return reference to null leaf iv __k does not exist.
1228 // If __k exists, set parent to node of __k and return reference to node of __k
1229 template <class _Key, class _Tp, class _Compare, class _Allocator>
1230 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer
1231 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent,
1232 const key_type& __k) const
1234 __node_const_pointer __nd = __tree_.__root();
1235 if (__nd != nullptr)
1239 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1241 if (__nd->__left_ != nullptr)
1242 __nd = static_cast<__node_pointer>(__nd->__left_);
1245 __parent = static_cast<__node_base_pointer>(__nd);
1246 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1249 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1251 if (__nd->__right_ != nullptr)
1252 __nd = static_cast<__node_pointer>(__nd->__right_);
1255 __parent = static_cast<__node_base_pointer>(__nd);
1256 return const_cast<const __node_base_const_pointer&>(__parent->__right_);
1261 __parent = static_cast<__node_base_pointer>(__nd);
1266 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1267 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1270 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1272 template <class _Key, class _Tp, class _Compare, class _Allocator>
1273 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1274 : __tree_(_VSTD::move(__m.__tree_), __a)
1276 if (__a != __m.get_allocator())
1278 const_iterator __e = cend();
1279 while (!__m.empty())
1280 __tree_.__insert_unique(__e.__i_,
1281 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1285 template <class _Key, class _Tp, class _Compare, class _Allocator>
1286 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1287 map<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1289 __node_allocator& __na = __tree_.__node_alloc();
1290 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1291 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
1292 __h.get_deleter().__first_constructed = true;
1293 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1294 __h.get_deleter().__second_constructed = true;
1298 template <class _Key, class _Tp, class _Compare, class _Allocator>
1299 template <class _A0>
1300 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1301 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1303 __node_allocator& __na = __tree_.__node_alloc();
1304 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1305 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1306 __h.get_deleter().__first_constructed = true;
1307 __h.get_deleter().__second_constructed = true;
1311 template <class _Key, class _Tp, class _Compare, class _Allocator>
1312 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1313 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k)
1315 __node_allocator& __na = __tree_.__node_alloc();
1316 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1317 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1318 __h.get_deleter().__first_constructed = true;
1319 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1320 __h.get_deleter().__second_constructed = true;
1324 #ifndef _LIBCPP_HAS_NO_VARIADICS
1326 template <class _Key, class _Tp, class _Compare, class _Allocator>
1327 template <class _A0, class _A1, class ..._Args>
1328 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1329 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1331 __node_allocator& __na = __tree_.__node_alloc();
1332 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1333 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1334 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1335 _VSTD::forward<_Args>(__args)...);
1336 __h.get_deleter().__first_constructed = true;
1337 __h.get_deleter().__second_constructed = true;
1341 #endif // _LIBCPP_HAS_NO_VARIADICS
1343 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1345 template <class _Key, class _Tp, class _Compare, class _Allocator>
1346 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1347 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1349 __node_allocator& __na = __tree_.__node_alloc();
1350 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1351 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1352 __h.get_deleter().__first_constructed = true;
1353 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1354 __h.get_deleter().__second_constructed = true;
1355 return _VSTD::move(__h); // explicitly moved for C++03
1358 template <class _Key, class _Tp, class _Compare, class _Allocator>
1360 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1362 __node_base_pointer __parent;
1363 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1364 __node_pointer __r = static_cast<__node_pointer>(__child);
1365 if (__child == nullptr)
1367 __node_holder __h = __construct_node_with_key(__k);
1368 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1369 __r = __h.release();
1371 return __r->__value_.__cc.second;
1374 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1376 template <class _Key, class _Tp, class _Compare, class _Allocator>
1378 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1380 __node_base_pointer __parent;
1381 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1382 __node_pointer __r = static_cast<__node_pointer>(__child);
1383 if (__child == nullptr)
1385 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1386 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1387 __r = __h.release();
1389 return __r->__value_.__cc.second;
1392 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1394 template <class _Key, class _Tp, class _Compare, class _Allocator>
1396 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1398 __node_base_pointer __parent;
1399 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1400 #ifndef _LIBCPP_NO_EXCEPTIONS
1401 if (__child == nullptr)
1402 throw out_of_range("map::at: key not found");
1403 #endif // _LIBCPP_NO_EXCEPTIONS
1404 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1407 template <class _Key, class _Tp, class _Compare, class _Allocator>
1409 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1411 __node_base_const_pointer __parent;
1412 __node_base_const_pointer __child = __find_equal_key(__parent, __k);
1413 #ifndef _LIBCPP_NO_EXCEPTIONS
1414 if (__child == nullptr)
1415 throw out_of_range("map::at: key not found");
1416 #endif // _LIBCPP_NO_EXCEPTIONS
1417 return static_cast<__node_const_pointer>(__child)->__value_.__cc.second;
1420 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1422 template <class _Key, class _Tp, class _Compare, class _Allocator>
1423 template <class ..._Args>
1424 pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
1425 map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1427 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1428 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
1434 template <class _Key, class _Tp, class _Compare, class _Allocator>
1435 template <class ..._Args>
1436 typename map<_Key, _Tp, _Compare, _Allocator>::iterator
1437 map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1440 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1441 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get());
1442 if (__r.__i_.__ptr_ == __h.get())
1447 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1449 template <class _Key, class _Tp, class _Compare, class _Allocator>
1450 inline _LIBCPP_INLINE_VISIBILITY
1452 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1453 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1455 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1458 template <class _Key, class _Tp, class _Compare, class _Allocator>
1459 inline _LIBCPP_INLINE_VISIBILITY
1461 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1462 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1464 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1467 template <class _Key, class _Tp, class _Compare, class _Allocator>
1468 inline _LIBCPP_INLINE_VISIBILITY
1470 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1471 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1473 return !(__x == __y);
1476 template <class _Key, class _Tp, class _Compare, class _Allocator>
1477 inline _LIBCPP_INLINE_VISIBILITY
1479 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1480 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1485 template <class _Key, class _Tp, class _Compare, class _Allocator>
1486 inline _LIBCPP_INLINE_VISIBILITY
1488 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1489 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1491 return !(__x < __y);
1494 template <class _Key, class _Tp, class _Compare, class _Allocator>
1495 inline _LIBCPP_INLINE_VISIBILITY
1497 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1498 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1500 return !(__y < __x);
1503 template <class _Key, class _Tp, class _Compare, class _Allocator>
1504 inline _LIBCPP_INLINE_VISIBILITY
1506 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1507 map<_Key, _Tp, _Compare, _Allocator>& __y)
1508 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1513 template <class _Key, class _Tp, class _Compare = less<_Key>,
1514 class _Allocator = allocator<pair<const _Key, _Tp> > >
1515 class _LIBCPP_TYPE_VIS_ONLY multimap
1519 typedef _Key key_type;
1520 typedef _Tp mapped_type;
1521 typedef pair<const key_type, mapped_type> value_type;
1522 typedef pair<key_type, mapped_type> __nc_value_type;
1523 typedef _Compare key_compare;
1524 typedef _Allocator allocator_type;
1525 typedef value_type& reference;
1526 typedef const value_type& const_reference;
1528 class _LIBCPP_TYPE_VIS_ONLY value_compare
1529 : public binary_function<value_type, value_type, bool>
1531 friend class multimap;
1535 _LIBCPP_INLINE_VISIBILITY
1536 value_compare(key_compare c) : comp(c) {}
1538 _LIBCPP_INLINE_VISIBILITY
1539 bool operator()(const value_type& __x, const value_type& __y) const
1540 {return comp(__x.first, __y.first);}
1545 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
1546 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1547 typedef typename allocator_traits<allocator_type>::template
1548 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1549 rebind_alloc<__value_type>
1551 rebind_alloc<__value_type>::other
1554 typedef __tree<__value_type, __vc, __allocator_type> __base;
1555 typedef typename __base::__node_traits __node_traits;
1556 typedef allocator_traits<allocator_type> __alloc_traits;
1561 typedef typename __alloc_traits::pointer pointer;
1562 typedef typename __alloc_traits::const_pointer const_pointer;
1563 typedef typename __alloc_traits::size_type size_type;
1564 typedef typename __alloc_traits::difference_type difference_type;
1565 typedef __map_iterator<typename __base::iterator> iterator;
1566 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1567 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1568 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1570 _LIBCPP_INLINE_VISIBILITY
1571 explicit multimap(const key_compare& __comp = key_compare())
1573 is_nothrow_default_constructible<allocator_type>::value &&
1574 is_nothrow_default_constructible<key_compare>::value &&
1575 is_nothrow_copy_constructible<key_compare>::value)
1576 : __tree_(__vc(__comp)) {}
1578 _LIBCPP_INLINE_VISIBILITY
1579 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1580 : __tree_(__vc(__comp), __a) {}
1582 template <class _InputIterator>
1583 _LIBCPP_INLINE_VISIBILITY
1584 multimap(_InputIterator __f, _InputIterator __l,
1585 const key_compare& __comp = key_compare())
1586 : __tree_(__vc(__comp))
1591 template <class _InputIterator>
1592 _LIBCPP_INLINE_VISIBILITY
1593 multimap(_InputIterator __f, _InputIterator __l,
1594 const key_compare& __comp, const allocator_type& __a)
1595 : __tree_(__vc(__comp), __a)
1600 #if _LIBCPP_STD_VER > 11
1601 template <class _InputIterator>
1602 _LIBCPP_INLINE_VISIBILITY
1603 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1604 : multimap(__f, __l, key_compare(), __a) {}
1607 _LIBCPP_INLINE_VISIBILITY
1608 multimap(const multimap& __m)
1609 : __tree_(__m.__tree_.value_comp(),
1610 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1612 insert(__m.begin(), __m.end());
1615 _LIBCPP_INLINE_VISIBILITY
1616 multimap& operator=(const multimap& __m)
1618 #if __cplusplus >= 201103L
1619 __tree_ = __m.__tree_;
1623 __tree_.value_comp() = __m.__tree_.value_comp();
1624 __tree_.__copy_assign_alloc(__m.__tree_);
1625 insert(__m.begin(), __m.end());
1631 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1633 _LIBCPP_INLINE_VISIBILITY
1634 multimap(multimap&& __m)
1635 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1636 : __tree_(_VSTD::move(__m.__tree_))
1640 multimap(multimap&& __m, const allocator_type& __a);
1642 _LIBCPP_INLINE_VISIBILITY
1643 multimap& operator=(multimap&& __m)
1644 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1646 __tree_ = _VSTD::move(__m.__tree_);
1650 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1652 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1654 _LIBCPP_INLINE_VISIBILITY
1655 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1656 : __tree_(__vc(__comp))
1658 insert(__il.begin(), __il.end());
1661 _LIBCPP_INLINE_VISIBILITY
1662 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1663 : __tree_(__vc(__comp), __a)
1665 insert(__il.begin(), __il.end());
1668 #if _LIBCPP_STD_VER > 11
1669 _LIBCPP_INLINE_VISIBILITY
1670 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1671 : multimap(__il, key_compare(), __a) {}
1674 _LIBCPP_INLINE_VISIBILITY
1675 multimap& operator=(initializer_list<value_type> __il)
1677 __tree_.__assign_multi(__il.begin(), __il.end());
1681 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1683 _LIBCPP_INLINE_VISIBILITY
1684 explicit multimap(const allocator_type& __a)
1689 _LIBCPP_INLINE_VISIBILITY
1690 multimap(const multimap& __m, const allocator_type& __a)
1691 : __tree_(__m.__tree_.value_comp(), __a)
1693 insert(__m.begin(), __m.end());
1696 _LIBCPP_INLINE_VISIBILITY
1697 iterator begin() _NOEXCEPT {return __tree_.begin();}
1698 _LIBCPP_INLINE_VISIBILITY
1699 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1700 _LIBCPP_INLINE_VISIBILITY
1701 iterator end() _NOEXCEPT {return __tree_.end();}
1702 _LIBCPP_INLINE_VISIBILITY
1703 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1705 _LIBCPP_INLINE_VISIBILITY
1706 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1707 _LIBCPP_INLINE_VISIBILITY
1708 const_reverse_iterator rbegin() const _NOEXCEPT
1709 {return const_reverse_iterator(end());}
1710 _LIBCPP_INLINE_VISIBILITY
1711 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1712 _LIBCPP_INLINE_VISIBILITY
1713 const_reverse_iterator rend() const _NOEXCEPT
1714 {return const_reverse_iterator(begin());}
1716 _LIBCPP_INLINE_VISIBILITY
1717 const_iterator cbegin() const _NOEXCEPT {return begin();}
1718 _LIBCPP_INLINE_VISIBILITY
1719 const_iterator cend() const _NOEXCEPT {return end();}
1720 _LIBCPP_INLINE_VISIBILITY
1721 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1722 _LIBCPP_INLINE_VISIBILITY
1723 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1725 _LIBCPP_INLINE_VISIBILITY
1726 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1727 _LIBCPP_INLINE_VISIBILITY
1728 size_type size() const _NOEXCEPT {return __tree_.size();}
1729 _LIBCPP_INLINE_VISIBILITY
1730 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1732 _LIBCPP_INLINE_VISIBILITY
1733 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1734 _LIBCPP_INLINE_VISIBILITY
1735 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1736 _LIBCPP_INLINE_VISIBILITY
1737 value_compare value_comp() const
1738 {return value_compare(__tree_.value_comp().key_comp());}
1740 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1741 #ifndef _LIBCPP_HAS_NO_VARIADICS
1743 template <class ..._Args>
1745 emplace(_Args&& ...__args);
1747 template <class ..._Args>
1749 emplace_hint(const_iterator __p, _Args&& ...__args);
1751 #endif // _LIBCPP_HAS_NO_VARIADICS
1753 template <class _Pp,
1754 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1755 _LIBCPP_INLINE_VISIBILITY
1756 iterator insert(_Pp&& __p)
1757 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1759 template <class _Pp,
1760 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1761 _LIBCPP_INLINE_VISIBILITY
1762 iterator insert(const_iterator __pos, _Pp&& __p)
1763 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1765 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1767 _LIBCPP_INLINE_VISIBILITY
1768 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1770 _LIBCPP_INLINE_VISIBILITY
1771 iterator insert(const_iterator __p, const value_type& __v)
1772 {return __tree_.__insert_multi(__p.__i_, __v);}
1774 template <class _InputIterator>
1775 _LIBCPP_INLINE_VISIBILITY
1776 void insert(_InputIterator __f, _InputIterator __l)
1778 for (const_iterator __e = cend(); __f != __l; ++__f)
1779 __tree_.__insert_multi(__e.__i_, *__f);
1782 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1784 _LIBCPP_INLINE_VISIBILITY
1785 void insert(initializer_list<value_type> __il)
1786 {insert(__il.begin(), __il.end());}
1788 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1790 _LIBCPP_INLINE_VISIBILITY
1791 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1792 _LIBCPP_INLINE_VISIBILITY
1793 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1794 _LIBCPP_INLINE_VISIBILITY
1795 iterator erase(const_iterator __f, const_iterator __l)
1796 {return __tree_.erase(__f.__i_, __l.__i_);}
1797 _LIBCPP_INLINE_VISIBILITY
1798 void clear() {__tree_.clear();}
1800 _LIBCPP_INLINE_VISIBILITY
1801 void swap(multimap& __m)
1802 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1803 {__tree_.swap(__m.__tree_);}
1805 _LIBCPP_INLINE_VISIBILITY
1806 iterator find(const key_type& __k) {return __tree_.find(__k);}
1807 _LIBCPP_INLINE_VISIBILITY
1808 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1809 #if _LIBCPP_STD_VER > 11
1810 template <typename _K2>
1811 _LIBCPP_INLINE_VISIBILITY
1812 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1813 find(const _K2& __k) {return __tree_.find(__k);}
1814 template <typename _K2>
1815 _LIBCPP_INLINE_VISIBILITY
1816 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1817 find(const _K2& __k) const {return __tree_.find(__k);}
1820 _LIBCPP_INLINE_VISIBILITY
1821 size_type count(const key_type& __k) const
1822 {return __tree_.__count_multi(__k);}
1823 _LIBCPP_INLINE_VISIBILITY
1824 iterator lower_bound(const key_type& __k)
1825 {return __tree_.lower_bound(__k);}
1826 _LIBCPP_INLINE_VISIBILITY
1827 const_iterator lower_bound(const key_type& __k) const
1828 {return __tree_.lower_bound(__k);}
1829 #if _LIBCPP_STD_VER > 11
1830 template <typename _K2>
1831 _LIBCPP_INLINE_VISIBILITY
1832 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1833 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1835 template <typename _K2>
1836 _LIBCPP_INLINE_VISIBILITY
1837 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1838 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1841 _LIBCPP_INLINE_VISIBILITY
1842 iterator upper_bound(const key_type& __k)
1843 {return __tree_.upper_bound(__k);}
1844 _LIBCPP_INLINE_VISIBILITY
1845 const_iterator upper_bound(const key_type& __k) const
1846 {return __tree_.upper_bound(__k);}
1847 #if _LIBCPP_STD_VER > 11
1848 template <typename _K2>
1849 _LIBCPP_INLINE_VISIBILITY
1850 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1851 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1852 template <typename _K2>
1853 _LIBCPP_INLINE_VISIBILITY
1854 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1855 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1858 _LIBCPP_INLINE_VISIBILITY
1859 pair<iterator,iterator> equal_range(const key_type& __k)
1860 {return __tree_.__equal_range_multi(__k);}
1861 _LIBCPP_INLINE_VISIBILITY
1862 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1863 {return __tree_.__equal_range_multi(__k);}
1864 #if _LIBCPP_STD_VER > 11
1865 template <typename _K2>
1866 _LIBCPP_INLINE_VISIBILITY
1867 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1868 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1869 template <typename _K2>
1870 _LIBCPP_INLINE_VISIBILITY
1871 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1872 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1876 typedef typename __base::__node __node;
1877 typedef typename __base::__node_allocator __node_allocator;
1878 typedef typename __base::__node_pointer __node_pointer;
1879 typedef typename __base::__node_const_pointer __node_const_pointer;
1880 typedef __map_node_destructor<__node_allocator> _Dp;
1881 typedef unique_ptr<__node, _Dp> __node_holder;
1883 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1884 __node_holder __construct_node();
1885 template <class _A0>
1887 __construct_node(_A0&& __a0);
1888 #ifndef _LIBCPP_HAS_NO_VARIADICS
1889 template <class _A0, class _A1, class ..._Args>
1890 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1891 #endif // _LIBCPP_HAS_NO_VARIADICS
1892 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1895 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1897 template <class _Key, class _Tp, class _Compare, class _Allocator>
1898 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1899 : __tree_(_VSTD::move(__m.__tree_), __a)
1901 if (__a != __m.get_allocator())
1903 const_iterator __e = cend();
1904 while (!__m.empty())
1905 __tree_.__insert_multi(__e.__i_,
1906 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1910 template <class _Key, class _Tp, class _Compare, class _Allocator>
1911 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1912 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1914 __node_allocator& __na = __tree_.__node_alloc();
1915 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1916 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
1917 __h.get_deleter().__first_constructed = true;
1918 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1919 __h.get_deleter().__second_constructed = true;
1923 template <class _Key, class _Tp, class _Compare, class _Allocator>
1924 template <class _A0>
1925 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1926 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1928 __node_allocator& __na = __tree_.__node_alloc();
1929 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1930 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1931 __h.get_deleter().__first_constructed = true;
1932 __h.get_deleter().__second_constructed = true;
1936 #ifndef _LIBCPP_HAS_NO_VARIADICS
1938 template <class _Key, class _Tp, class _Compare, class _Allocator>
1939 template <class _A0, class _A1, class ..._Args>
1940 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1941 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1943 __node_allocator& __na = __tree_.__node_alloc();
1944 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1945 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1946 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1947 _VSTD::forward<_Args>(__args)...);
1948 __h.get_deleter().__first_constructed = true;
1949 __h.get_deleter().__second_constructed = true;
1953 #endif // _LIBCPP_HAS_NO_VARIADICS
1954 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1956 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1958 template <class _Key, class _Tp, class _Compare, class _Allocator>
1959 template <class ..._Args>
1960 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1961 multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1963 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1964 iterator __r = __tree_.__node_insert_multi(__h.get());
1969 template <class _Key, class _Tp, class _Compare, class _Allocator>
1970 template <class ..._Args>
1971 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1972 multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1975 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1976 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get());
1981 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1983 template <class _Key, class _Tp, class _Compare, class _Allocator>
1984 inline _LIBCPP_INLINE_VISIBILITY
1986 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1987 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1989 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1992 template <class _Key, class _Tp, class _Compare, class _Allocator>
1993 inline _LIBCPP_INLINE_VISIBILITY
1995 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1996 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1998 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2001 template <class _Key, class _Tp, class _Compare, class _Allocator>
2002 inline _LIBCPP_INLINE_VISIBILITY
2004 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2005 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2007 return !(__x == __y);
2010 template <class _Key, class _Tp, class _Compare, class _Allocator>
2011 inline _LIBCPP_INLINE_VISIBILITY
2013 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2014 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2019 template <class _Key, class _Tp, class _Compare, class _Allocator>
2020 inline _LIBCPP_INLINE_VISIBILITY
2022 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2023 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2025 return !(__x < __y);
2028 template <class _Key, class _Tp, class _Compare, class _Allocator>
2029 inline _LIBCPP_INLINE_VISIBILITY
2031 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2032 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2034 return !(__y < __x);
2037 template <class _Key, class _Tp, class _Compare, class _Allocator>
2038 inline _LIBCPP_INLINE_VISIBILITY
2040 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2041 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2042 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2047 _LIBCPP_END_NAMESPACE_STD
2049 #endif // _LIBCPP_MAP