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);
129 pair<iterator, bool> insert( value_type&& v); // C++17
131 pair<iterator, bool> insert(P&& p);
132 iterator insert(const_iterator position, const value_type& v);
133 iterator insert(const_iterator position, value_type&& v); // C++17
135 iterator insert(const_iterator position, P&& p);
136 template <class InputIterator>
137 void insert(InputIterator first, InputIterator last);
138 void insert(initializer_list<value_type> il);
140 template <class... Args>
141 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
142 template <class... Args>
143 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
144 template <class... Args>
145 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
146 template <class... Args>
147 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
149 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
151 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
153 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
155 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
157 iterator erase(const_iterator position);
158 iterator erase(iterator position); // C++14
159 size_type erase(const key_type& k);
160 iterator erase(const_iterator first, const_iterator last);
161 void clear() noexcept;
164 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
165 __is_nothrow_swappable<key_compare>::value); // C++17
168 allocator_type get_allocator() const noexcept;
169 key_compare key_comp() const;
170 value_compare value_comp() const;
173 iterator find(const key_type& k);
174 const_iterator find(const key_type& k) const;
176 iterator find(const K& x); // C++14
178 const_iterator find(const K& x) const; // C++14
180 size_type count(const K& x) const; // C++14
182 size_type count(const key_type& k) const;
183 iterator lower_bound(const key_type& k);
184 const_iterator lower_bound(const key_type& k) const;
186 iterator lower_bound(const K& x); // C++14
188 const_iterator lower_bound(const K& x) const; // C++14
190 iterator upper_bound(const key_type& k);
191 const_iterator upper_bound(const key_type& k) const;
193 iterator upper_bound(const K& x); // C++14
195 const_iterator upper_bound(const K& x) const; // C++14
197 pair<iterator,iterator> equal_range(const key_type& k);
198 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
200 pair<iterator,iterator> equal_range(const K& x); // C++14
202 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
205 template <class Key, class T, class Compare, class Allocator>
207 operator==(const map<Key, T, Compare, Allocator>& x,
208 const map<Key, T, Compare, Allocator>& y);
210 template <class Key, class T, class Compare, class Allocator>
212 operator< (const map<Key, T, Compare, Allocator>& x,
213 const map<Key, T, Compare, Allocator>& y);
215 template <class Key, class T, class Compare, class Allocator>
217 operator!=(const map<Key, T, Compare, Allocator>& x,
218 const map<Key, T, Compare, Allocator>& y);
220 template <class Key, class T, class Compare, class Allocator>
222 operator> (const map<Key, T, Compare, Allocator>& x,
223 const map<Key, T, Compare, Allocator>& y);
225 template <class Key, class T, class Compare, class Allocator>
227 operator>=(const map<Key, T, Compare, Allocator>& x,
228 const map<Key, T, Compare, Allocator>& y);
230 template <class Key, class T, class Compare, class Allocator>
232 operator<=(const map<Key, T, Compare, Allocator>& x,
233 const map<Key, T, Compare, Allocator>& y);
235 // specialized algorithms:
236 template <class Key, class T, class Compare, class Allocator>
238 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
239 noexcept(noexcept(x.swap(y)));
241 template <class Key, class T, class Compare = less<Key>,
242 class Allocator = allocator<pair<const Key, T>>>
247 typedef Key key_type;
248 typedef T mapped_type;
249 typedef pair<const key_type,mapped_type> value_type;
250 typedef Compare key_compare;
251 typedef Allocator allocator_type;
252 typedef typename allocator_type::reference reference;
253 typedef typename allocator_type::const_reference const_reference;
254 typedef typename allocator_type::size_type size_type;
255 typedef typename allocator_type::difference_type difference_type;
256 typedef typename allocator_type::pointer pointer;
257 typedef typename allocator_type::const_pointer const_pointer;
259 typedef implementation-defined iterator;
260 typedef implementation-defined const_iterator;
261 typedef std::reverse_iterator<iterator> reverse_iterator;
262 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
265 : public binary_function<value_type,value_type,bool>
267 friend class multimap;
270 value_compare(key_compare c);
272 bool operator()(const value_type& x, const value_type& y) const;
275 // construct/copy/destroy:
278 is_nothrow_default_constructible<allocator_type>::value &&
279 is_nothrow_default_constructible<key_compare>::value &&
280 is_nothrow_copy_constructible<key_compare>::value);
281 explicit multimap(const key_compare& comp);
282 multimap(const key_compare& comp, const allocator_type& a);
283 template <class InputIterator>
284 multimap(InputIterator first, InputIterator last, const key_compare& comp);
285 template <class InputIterator>
286 multimap(InputIterator first, InputIterator last, const key_compare& comp,
287 const allocator_type& a);
288 multimap(const multimap& m);
289 multimap(multimap&& m)
291 is_nothrow_move_constructible<allocator_type>::value &&
292 is_nothrow_move_constructible<key_compare>::value);
293 explicit multimap(const allocator_type& a);
294 multimap(const multimap& m, const allocator_type& a);
295 multimap(multimap&& m, const allocator_type& a);
296 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
297 multimap(initializer_list<value_type> il, const key_compare& comp,
298 const allocator_type& a);
299 template <class InputIterator>
300 multimap(InputIterator first, InputIterator last, const allocator_type& a)
301 : multimap(first, last, Compare(), a) {} // C++14
302 multimap(initializer_list<value_type> il, const allocator_type& a)
303 : multimap(il, Compare(), a) {} // C++14
306 multimap& operator=(const multimap& m);
307 multimap& operator=(multimap&& m)
309 allocator_type::propagate_on_container_move_assignment::value &&
310 is_nothrow_move_assignable<allocator_type>::value &&
311 is_nothrow_move_assignable<key_compare>::value);
312 multimap& operator=(initializer_list<value_type> il);
315 iterator begin() noexcept;
316 const_iterator begin() const noexcept;
317 iterator end() noexcept;
318 const_iterator end() const noexcept;
320 reverse_iterator rbegin() noexcept;
321 const_reverse_iterator rbegin() const noexcept;
322 reverse_iterator rend() noexcept;
323 const_reverse_iterator rend() const noexcept;
325 const_iterator cbegin() const noexcept;
326 const_iterator cend() const noexcept;
327 const_reverse_iterator crbegin() const noexcept;
328 const_reverse_iterator crend() const noexcept;
331 bool empty() const noexcept;
332 size_type size() const noexcept;
333 size_type max_size() const noexcept;
336 template <class... Args>
337 iterator emplace(Args&&... args);
338 template <class... Args>
339 iterator emplace_hint(const_iterator position, Args&&... args);
340 iterator insert(const value_type& v);
341 iterator insert( value_type&& v); // C++17
343 iterator insert(P&& p);
344 iterator insert(const_iterator position, const value_type& v);
345 iterator insert(const_iterator position, value_type&& v); // C++17
347 iterator insert(const_iterator position, P&& p);
348 template <class InputIterator>
349 void insert(InputIterator first, InputIterator last);
350 void insert(initializer_list<value_type> il);
352 iterator erase(const_iterator position);
353 iterator erase(iterator position); // C++14
354 size_type erase(const key_type& k);
355 iterator erase(const_iterator first, const_iterator last);
356 void clear() noexcept;
358 void swap(multimap& m)
359 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
360 __is_nothrow_swappable<key_compare>::value); // C++17
363 allocator_type get_allocator() const noexcept;
364 key_compare key_comp() const;
365 value_compare value_comp() const;
368 iterator find(const key_type& k);
369 const_iterator find(const key_type& k) const;
371 iterator find(const K& x); // C++14
373 const_iterator find(const K& x) const; // C++14
375 size_type count(const K& x) const; // C++14
377 size_type count(const key_type& k) const;
378 iterator lower_bound(const key_type& k);
379 const_iterator lower_bound(const key_type& k) const;
381 iterator lower_bound(const K& x); // C++14
383 const_iterator lower_bound(const K& x) const; // C++14
385 iterator upper_bound(const key_type& k);
386 const_iterator upper_bound(const key_type& k) const;
388 iterator upper_bound(const K& x); // C++14
390 const_iterator upper_bound(const K& x) const; // C++14
392 pair<iterator,iterator> equal_range(const key_type& k);
393 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
395 pair<iterator,iterator> equal_range(const K& x); // C++14
397 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
400 template <class Key, class T, class Compare, class Allocator>
402 operator==(const multimap<Key, T, Compare, Allocator>& x,
403 const multimap<Key, T, Compare, Allocator>& y);
405 template <class Key, class T, class Compare, class Allocator>
407 operator< (const multimap<Key, T, Compare, Allocator>& x,
408 const multimap<Key, T, Compare, Allocator>& y);
410 template <class Key, class T, class Compare, class Allocator>
412 operator!=(const multimap<Key, T, Compare, Allocator>& x,
413 const multimap<Key, T, Compare, Allocator>& y);
415 template <class Key, class T, class Compare, class Allocator>
417 operator> (const multimap<Key, T, Compare, Allocator>& x,
418 const multimap<Key, T, Compare, Allocator>& y);
420 template <class Key, class T, class Compare, class Allocator>
422 operator>=(const multimap<Key, T, Compare, Allocator>& x,
423 const multimap<Key, T, Compare, Allocator>& y);
425 template <class Key, class T, class Compare, class Allocator>
427 operator<=(const multimap<Key, T, Compare, Allocator>& x,
428 const multimap<Key, T, Compare, Allocator>& y);
430 // specialized algorithms:
431 template <class Key, class T, class Compare, class Allocator>
433 swap(multimap<Key, T, Compare, Allocator>& x,
434 multimap<Key, T, Compare, Allocator>& y)
435 noexcept(noexcept(x.swap(y)));
446 #include <functional>
447 #include <initializer_list>
448 #include <type_traits>
450 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
451 #pragma GCC system_header
454 _LIBCPP_BEGIN_NAMESPACE_STD
456 template <class _Key, class _CP, class _Compare,
457 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value
459 class __map_value_compare
463 _LIBCPP_INLINE_VISIBILITY
464 __map_value_compare()
465 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
467 _LIBCPP_INLINE_VISIBILITY
468 __map_value_compare(_Compare c)
469 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
471 _LIBCPP_INLINE_VISIBILITY
472 const _Compare& key_comp() const _NOEXCEPT {return *this;}
473 _LIBCPP_INLINE_VISIBILITY
474 bool operator()(const _CP& __x, const _CP& __y) const
475 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y.__cc.first);}
476 _LIBCPP_INLINE_VISIBILITY
477 bool operator()(const _CP& __x, const _Key& __y) const
478 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y);}
479 _LIBCPP_INLINE_VISIBILITY
480 bool operator()(const _Key& __x, const _CP& __y) const
481 {return static_cast<const _Compare&>(*this)(__x, __y.__cc.first);}
482 void swap(__map_value_compare&__y)
483 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
486 swap(static_cast<const _Compare&>(*this), static_cast<const _Compare&>(__y));
489 #if _LIBCPP_STD_VER > 11
490 template <typename _K2>
491 _LIBCPP_INLINE_VISIBILITY
492 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
493 operator () ( const _K2& __x, const _CP& __y ) const
494 {return static_cast<const _Compare&>(*this) (__x, __y.__cc.first);}
496 template <typename _K2>
497 _LIBCPP_INLINE_VISIBILITY
498 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
499 operator () (const _CP& __x, const _K2& __y) const
500 {return static_cast<const _Compare&>(*this) (__x.__cc.first, __y);}
504 template <class _Key, class _CP, class _Compare>
505 class __map_value_compare<_Key, _CP, _Compare, false>
510 _LIBCPP_INLINE_VISIBILITY
511 __map_value_compare()
512 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
514 _LIBCPP_INLINE_VISIBILITY
515 __map_value_compare(_Compare c)
516 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
518 _LIBCPP_INLINE_VISIBILITY
519 const _Compare& key_comp() const _NOEXCEPT {return comp;}
521 _LIBCPP_INLINE_VISIBILITY
522 bool operator()(const _CP& __x, const _CP& __y) const
523 {return comp(__x.__cc.first, __y.__cc.first);}
524 _LIBCPP_INLINE_VISIBILITY
525 bool operator()(const _CP& __x, const _Key& __y) const
526 {return comp(__x.__cc.first, __y);}
527 _LIBCPP_INLINE_VISIBILITY
528 bool operator()(const _Key& __x, const _CP& __y) const
529 {return comp(__x, __y.__cc.first);}
530 void swap(__map_value_compare&__y)
531 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
534 swap(comp, __y.comp);
537 #if _LIBCPP_STD_VER > 11
538 template <typename _K2>
539 _LIBCPP_INLINE_VISIBILITY
540 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
541 operator () ( const _K2& __x, const _CP& __y ) const
542 {return comp (__x, __y.__cc.first);}
544 template <typename _K2>
545 _LIBCPP_INLINE_VISIBILITY
546 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
547 operator () (const _CP& __x, const _K2& __y) const
548 {return comp (__x.__cc.first, __y);}
552 template <class _Key, class _CP, class _Compare, bool __b>
553 inline _LIBCPP_INLINE_VISIBILITY
555 swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
556 __map_value_compare<_Key, _CP, _Compare, __b>& __y)
557 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
562 template <class _Allocator>
563 class __map_node_destructor
565 typedef _Allocator allocator_type;
566 typedef allocator_traits<allocator_type> __alloc_traits;
567 typedef typename __alloc_traits::value_type::value_type value_type;
569 typedef typename __alloc_traits::pointer pointer;
571 typedef typename value_type::value_type::first_type first_type;
572 typedef typename value_type::value_type::second_type second_type;
574 allocator_type& __na_;
576 __map_node_destructor& operator=(const __map_node_destructor&);
579 bool __first_constructed;
580 bool __second_constructed;
582 _LIBCPP_INLINE_VISIBILITY
583 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
585 __first_constructed(false),
586 __second_constructed(false)
589 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
590 _LIBCPP_INLINE_VISIBILITY
591 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
593 __first_constructed(__x.__value_constructed),
594 __second_constructed(__x.__value_constructed)
596 __x.__value_constructed = false;
598 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
600 _LIBCPP_INLINE_VISIBILITY
601 void operator()(pointer __p) _NOEXCEPT
603 if (__second_constructed)
604 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
605 if (__first_constructed)
606 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
608 __alloc_traits::deallocate(__na_, __p, 1);
612 template <class _Key, class _Tp, class _Compare, class _Allocator>
614 template <class _Key, class _Tp, class _Compare, class _Allocator>
616 template <class _TreeIterator> class __map_const_iterator;
618 #if __cplusplus >= 201103L
620 template <class _Key, class _Tp>
623 typedef _Key key_type;
624 typedef _Tp mapped_type;
625 typedef pair<const key_type, mapped_type> value_type;
626 typedef pair<key_type, mapped_type> __nc_value_type;
629 __nc_value_type __nc;
631 template <class ..._Args>
632 _LIBCPP_INLINE_VISIBILITY
633 __value_type(_Args&& ...__args)
634 : __cc(std::forward<_Args>(__args)...) {}
636 _LIBCPP_INLINE_VISIBILITY
637 __value_type(const __value_type& __v)
640 _LIBCPP_INLINE_VISIBILITY
641 __value_type(__value_type& __v)
644 _LIBCPP_INLINE_VISIBILITY
645 __value_type(__value_type&& __v)
646 : __nc(std::move(__v.__nc)) {}
648 _LIBCPP_INLINE_VISIBILITY
649 __value_type& operator=(const __value_type& __v)
650 {__nc = __v.__cc; return *this;}
652 _LIBCPP_INLINE_VISIBILITY
653 __value_type& operator=(__value_type&& __v)
654 {__nc = std::move(__v.__nc); return *this;}
656 _LIBCPP_INLINE_VISIBILITY
657 ~__value_type() {__cc.~value_type();}
662 template <class _Key, class _Tp>
665 typedef _Key key_type;
666 typedef _Tp mapped_type;
667 typedef pair<const key_type, mapped_type> value_type;
671 _LIBCPP_INLINE_VISIBILITY
675 _LIBCPP_INLINE_VISIBILITY
676 __value_type(const _A0& __a0)
679 template <class _A0, class _A1>
680 _LIBCPP_INLINE_VISIBILITY
681 __value_type(const _A0& __a0, const _A1& __a1)
682 : __cc(__a0, __a1) {}
688 struct __extract_key_value_types;
690 template <class _Key, class _Tp>
691 struct __extract_key_value_types<__value_type<_Key, _Tp> >
693 typedef _Key const __key_type;
694 typedef _Tp __mapped_type;
697 template <class _TreeIterator>
698 class _LIBCPP_TYPE_VIS_ONLY __map_iterator
702 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
703 typedef typename _TreeIterator::value_type __value_type;
704 typedef typename __extract_key_value_types<__value_type>::__key_type __key_type;
705 typedef typename __extract_key_value_types<__value_type>::__mapped_type __mapped_type;
707 typedef bidirectional_iterator_tag iterator_category;
708 typedef pair<__key_type, __mapped_type> value_type;
709 typedef typename _TreeIterator::difference_type difference_type;
710 typedef value_type& reference;
711 typedef typename __rebind_pointer<typename __pointer_traits::pointer, value_type>::type
714 _LIBCPP_INLINE_VISIBILITY
715 __map_iterator() _NOEXCEPT {}
717 _LIBCPP_INLINE_VISIBILITY
718 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
720 _LIBCPP_INLINE_VISIBILITY
721 reference operator*() const {return __i_->__cc;}
722 _LIBCPP_INLINE_VISIBILITY
723 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
725 _LIBCPP_INLINE_VISIBILITY
726 __map_iterator& operator++() {++__i_; return *this;}
727 _LIBCPP_INLINE_VISIBILITY
728 __map_iterator operator++(int)
730 __map_iterator __t(*this);
735 _LIBCPP_INLINE_VISIBILITY
736 __map_iterator& operator--() {--__i_; return *this;}
737 _LIBCPP_INLINE_VISIBILITY
738 __map_iterator operator--(int)
740 __map_iterator __t(*this);
745 friend _LIBCPP_INLINE_VISIBILITY
746 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
747 {return __x.__i_ == __y.__i_;}
749 _LIBCPP_INLINE_VISIBILITY
750 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
751 {return __x.__i_ != __y.__i_;}
753 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
754 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
755 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
758 template <class _TreeIterator>
759 class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator
763 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
764 typedef typename _TreeIterator::value_type __value_type;
765 typedef typename __extract_key_value_types<__value_type>::__key_type __key_type;
766 typedef typename __extract_key_value_types<__value_type>::__mapped_type __mapped_type;
768 typedef bidirectional_iterator_tag iterator_category;
769 typedef pair<__key_type, __mapped_type> value_type;
770 typedef typename _TreeIterator::difference_type difference_type;
771 typedef const value_type& reference;
772 typedef typename __rebind_pointer<typename __pointer_traits::pointer, const value_type>::type
775 _LIBCPP_INLINE_VISIBILITY
776 __map_const_iterator() _NOEXCEPT {}
778 _LIBCPP_INLINE_VISIBILITY
779 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
780 _LIBCPP_INLINE_VISIBILITY
781 __map_const_iterator(__map_iterator<
782 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
785 _LIBCPP_INLINE_VISIBILITY
786 reference operator*() const {return __i_->__cc;}
787 _LIBCPP_INLINE_VISIBILITY
788 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
790 _LIBCPP_INLINE_VISIBILITY
791 __map_const_iterator& operator++() {++__i_; return *this;}
792 _LIBCPP_INLINE_VISIBILITY
793 __map_const_iterator operator++(int)
795 __map_const_iterator __t(*this);
800 _LIBCPP_INLINE_VISIBILITY
801 __map_const_iterator& operator--() {--__i_; return *this;}
802 _LIBCPP_INLINE_VISIBILITY
803 __map_const_iterator operator--(int)
805 __map_const_iterator __t(*this);
810 friend _LIBCPP_INLINE_VISIBILITY
811 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
812 {return __x.__i_ == __y.__i_;}
813 friend _LIBCPP_INLINE_VISIBILITY
814 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
815 {return __x.__i_ != __y.__i_;}
817 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
818 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
819 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
822 template <class _Key, class _Tp, class _Compare = less<_Key>,
823 class _Allocator = allocator<pair<const _Key, _Tp> > >
824 class _LIBCPP_TYPE_VIS_ONLY map
828 typedef _Key key_type;
829 typedef _Tp mapped_type;
830 typedef pair<const key_type, mapped_type> value_type;
831 typedef pair<key_type, mapped_type> __nc_value_type;
832 typedef _Compare key_compare;
833 typedef _Allocator allocator_type;
834 typedef value_type& reference;
835 typedef const value_type& const_reference;
837 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
838 "Allocator::value_type must be same type as value_type");
840 class _LIBCPP_TYPE_VIS_ONLY value_compare
841 : public binary_function<value_type, value_type, bool>
847 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
849 _LIBCPP_INLINE_VISIBILITY
850 bool operator()(const value_type& __x, const value_type& __y) const
851 {return comp(__x.first, __y.first);}
856 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
857 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
858 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
859 __value_type>::type __allocator_type;
860 typedef __tree<__value_type, __vc, __allocator_type> __base;
861 typedef typename __base::__node_traits __node_traits;
862 typedef allocator_traits<allocator_type> __alloc_traits;
867 typedef typename __alloc_traits::pointer pointer;
868 typedef typename __alloc_traits::const_pointer const_pointer;
869 typedef typename __alloc_traits::size_type size_type;
870 typedef typename __alloc_traits::difference_type difference_type;
871 typedef __map_iterator<typename __base::iterator> iterator;
872 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
873 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
874 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
876 _LIBCPP_INLINE_VISIBILITY
879 is_nothrow_default_constructible<allocator_type>::value &&
880 is_nothrow_default_constructible<key_compare>::value &&
881 is_nothrow_copy_constructible<key_compare>::value)
882 : __tree_(__vc(key_compare())) {}
884 _LIBCPP_INLINE_VISIBILITY
885 explicit map(const key_compare& __comp)
887 is_nothrow_default_constructible<allocator_type>::value &&
888 is_nothrow_copy_constructible<key_compare>::value)
889 : __tree_(__vc(__comp)) {}
891 _LIBCPP_INLINE_VISIBILITY
892 explicit map(const key_compare& __comp, const allocator_type& __a)
893 : __tree_(__vc(__comp), __a) {}
895 template <class _InputIterator>
896 _LIBCPP_INLINE_VISIBILITY
897 map(_InputIterator __f, _InputIterator __l,
898 const key_compare& __comp = key_compare())
899 : __tree_(__vc(__comp))
904 template <class _InputIterator>
905 _LIBCPP_INLINE_VISIBILITY
906 map(_InputIterator __f, _InputIterator __l,
907 const key_compare& __comp, const allocator_type& __a)
908 : __tree_(__vc(__comp), __a)
913 #if _LIBCPP_STD_VER > 11
914 template <class _InputIterator>
915 _LIBCPP_INLINE_VISIBILITY
916 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
917 : map(__f, __l, key_compare(), __a) {}
920 _LIBCPP_INLINE_VISIBILITY
922 : __tree_(__m.__tree_)
924 insert(__m.begin(), __m.end());
927 _LIBCPP_INLINE_VISIBILITY
928 map& operator=(const map& __m)
930 #if __cplusplus >= 201103L
931 __tree_ = __m.__tree_;
935 __tree_.value_comp() = __m.__tree_.value_comp();
936 __tree_.__copy_assign_alloc(__m.__tree_);
937 insert(__m.begin(), __m.end());
943 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
945 _LIBCPP_INLINE_VISIBILITY
947 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
948 : __tree_(_VSTD::move(__m.__tree_))
952 map(map&& __m, const allocator_type& __a);
954 _LIBCPP_INLINE_VISIBILITY
955 map& operator=(map&& __m)
956 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
958 __tree_ = _VSTD::move(__m.__tree_);
962 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
964 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
966 _LIBCPP_INLINE_VISIBILITY
967 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
968 : __tree_(__vc(__comp))
970 insert(__il.begin(), __il.end());
973 _LIBCPP_INLINE_VISIBILITY
974 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
975 : __tree_(__vc(__comp), __a)
977 insert(__il.begin(), __il.end());
980 #if _LIBCPP_STD_VER > 11
981 _LIBCPP_INLINE_VISIBILITY
982 map(initializer_list<value_type> __il, const allocator_type& __a)
983 : map(__il, key_compare(), __a) {}
986 _LIBCPP_INLINE_VISIBILITY
987 map& operator=(initializer_list<value_type> __il)
989 __tree_.__assign_unique(__il.begin(), __il.end());
993 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
995 _LIBCPP_INLINE_VISIBILITY
996 explicit map(const allocator_type& __a)
1001 _LIBCPP_INLINE_VISIBILITY
1002 map(const map& __m, const allocator_type& __a)
1003 : __tree_(__m.__tree_.value_comp(), __a)
1005 insert(__m.begin(), __m.end());
1008 _LIBCPP_INLINE_VISIBILITY
1009 iterator begin() _NOEXCEPT {return __tree_.begin();}
1010 _LIBCPP_INLINE_VISIBILITY
1011 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1012 _LIBCPP_INLINE_VISIBILITY
1013 iterator end() _NOEXCEPT {return __tree_.end();}
1014 _LIBCPP_INLINE_VISIBILITY
1015 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1017 _LIBCPP_INLINE_VISIBILITY
1018 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1019 _LIBCPP_INLINE_VISIBILITY
1020 const_reverse_iterator rbegin() const _NOEXCEPT
1021 {return const_reverse_iterator(end());}
1022 _LIBCPP_INLINE_VISIBILITY
1023 reverse_iterator rend() _NOEXCEPT
1024 {return reverse_iterator(begin());}
1025 _LIBCPP_INLINE_VISIBILITY
1026 const_reverse_iterator rend() const _NOEXCEPT
1027 {return const_reverse_iterator(begin());}
1029 _LIBCPP_INLINE_VISIBILITY
1030 const_iterator cbegin() const _NOEXCEPT {return begin();}
1031 _LIBCPP_INLINE_VISIBILITY
1032 const_iterator cend() const _NOEXCEPT {return end();}
1033 _LIBCPP_INLINE_VISIBILITY
1034 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1035 _LIBCPP_INLINE_VISIBILITY
1036 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1038 _LIBCPP_INLINE_VISIBILITY
1039 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1040 _LIBCPP_INLINE_VISIBILITY
1041 size_type size() const _NOEXCEPT {return __tree_.size();}
1042 _LIBCPP_INLINE_VISIBILITY
1043 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1045 mapped_type& operator[](const key_type& __k);
1046 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1047 mapped_type& operator[](key_type&& __k);
1050 mapped_type& at(const key_type& __k);
1051 const mapped_type& at(const key_type& __k) const;
1053 _LIBCPP_INLINE_VISIBILITY
1054 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1055 _LIBCPP_INLINE_VISIBILITY
1056 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1057 _LIBCPP_INLINE_VISIBILITY
1058 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1060 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1061 #ifndef _LIBCPP_HAS_NO_VARIADICS
1063 template <class ..._Args>
1064 pair<iterator, bool>
1065 emplace(_Args&& ...__args);
1067 template <class ..._Args>
1069 emplace_hint(const_iterator __p, _Args&& ...__args);
1071 #endif // _LIBCPP_HAS_NO_VARIADICS
1073 template <class _Pp,
1074 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1075 _LIBCPP_INLINE_VISIBILITY
1076 pair<iterator, bool> insert(_Pp&& __p)
1077 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1079 template <class _Pp,
1080 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1081 _LIBCPP_INLINE_VISIBILITY
1082 iterator insert(const_iterator __pos, _Pp&& __p)
1083 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1085 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1087 _LIBCPP_INLINE_VISIBILITY
1088 pair<iterator, bool>
1089 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1091 _LIBCPP_INLINE_VISIBILITY
1093 insert(const_iterator __p, const value_type& __v)
1094 {return __tree_.__insert_unique(__p.__i_, __v);}
1096 #if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1097 _LIBCPP_INLINE_VISIBILITY
1098 pair<iterator, bool>
1099 insert( value_type&& __v) {return __tree_.__insert_unique(_VSTD::forward<value_type>(__v));}
1101 _LIBCPP_INLINE_VISIBILITY
1103 insert(const_iterator __p, value_type&& __v)
1104 {return __tree_.__insert_unique(__p.__i_, _VSTD::forward<value_type>(__v));}
1107 template <class _InputIterator>
1108 _LIBCPP_INLINE_VISIBILITY
1109 void insert(_InputIterator __f, _InputIterator __l)
1111 for (const_iterator __e = cend(); __f != __l; ++__f)
1112 insert(__e.__i_, *__f);
1115 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1117 _LIBCPP_INLINE_VISIBILITY
1118 void insert(initializer_list<value_type> __il)
1119 {insert(__il.begin(), __il.end());}
1121 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1123 #if _LIBCPP_STD_VER > 14
1124 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1125 #ifndef _LIBCPP_HAS_NO_VARIADICS
1126 template <class... _Args>
1127 _LIBCPP_INLINE_VISIBILITY
1128 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1130 iterator __p = lower_bound(__k);
1131 if ( __p != end() && !key_comp()(__k, __p->first))
1132 return _VSTD::make_pair(__p, false);
1134 return _VSTD::make_pair(
1136 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k),
1137 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
1141 template <class... _Args>
1142 _LIBCPP_INLINE_VISIBILITY
1143 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1145 iterator __p = lower_bound(__k);
1146 if ( __p != end() && !key_comp()(__k, __p->first))
1147 return _VSTD::make_pair(__p, false);
1149 return _VSTD::make_pair(
1151 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),
1152 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
1156 template <class... _Args>
1157 _LIBCPP_INLINE_VISIBILITY
1158 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1160 iterator __p = lower_bound(__k);
1161 if ( __p != end() && !key_comp()(__k, __p->first))
1164 return emplace_hint(__p,
1165 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k),
1166 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1169 template <class... _Args>
1170 _LIBCPP_INLINE_VISIBILITY
1171 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1173 iterator __p = lower_bound(__k);
1174 if ( __p != end() && !key_comp()(__k, __p->first))
1177 return emplace_hint(__p,
1178 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),
1179 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1182 template <class _Vp>
1183 _LIBCPP_INLINE_VISIBILITY
1184 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1186 iterator __p = lower_bound(__k);
1187 if ( __p != end() && !key_comp()(__k, __p->first))
1189 __p->second = _VSTD::forward<_Vp>(__v);
1190 return _VSTD::make_pair(__p, false);
1192 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1195 template <class _Vp>
1196 _LIBCPP_INLINE_VISIBILITY
1197 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1199 iterator __p = lower_bound(__k);
1200 if ( __p != end() && !key_comp()(__k, __p->first))
1202 __p->second = _VSTD::forward<_Vp>(__v);
1203 return _VSTD::make_pair(__p, false);
1205 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1208 template <class _Vp>
1209 _LIBCPP_INLINE_VISIBILITY
1210 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1212 iterator __p = lower_bound(__k);
1213 if ( __p != end() && !key_comp()(__k, __p->first))
1215 __p->second = _VSTD::forward<_Vp>(__v);
1218 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1221 template <class _Vp>
1222 _LIBCPP_INLINE_VISIBILITY
1223 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1225 iterator __p = lower_bound(__k);
1226 if ( __p != end() && !key_comp()(__k, __p->first))
1228 __p->second = _VSTD::forward<_Vp>(__v);
1231 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1237 _LIBCPP_INLINE_VISIBILITY
1238 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1239 _LIBCPP_INLINE_VISIBILITY
1240 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1241 _LIBCPP_INLINE_VISIBILITY
1242 size_type erase(const key_type& __k)
1243 {return __tree_.__erase_unique(__k);}
1244 _LIBCPP_INLINE_VISIBILITY
1245 iterator erase(const_iterator __f, const_iterator __l)
1246 {return __tree_.erase(__f.__i_, __l.__i_);}
1247 _LIBCPP_INLINE_VISIBILITY
1248 void clear() _NOEXCEPT {__tree_.clear();}
1250 _LIBCPP_INLINE_VISIBILITY
1252 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1253 {__tree_.swap(__m.__tree_);}
1255 _LIBCPP_INLINE_VISIBILITY
1256 iterator find(const key_type& __k) {return __tree_.find(__k);}
1257 _LIBCPP_INLINE_VISIBILITY
1258 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1259 #if _LIBCPP_STD_VER > 11
1260 template <typename _K2>
1261 _LIBCPP_INLINE_VISIBILITY
1262 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1263 find(const _K2& __k) {return __tree_.find(__k);}
1264 template <typename _K2>
1265 _LIBCPP_INLINE_VISIBILITY
1266 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1267 find(const _K2& __k) const {return __tree_.find(__k);}
1270 _LIBCPP_INLINE_VISIBILITY
1271 size_type count(const key_type& __k) const
1272 {return __tree_.__count_unique(__k);}
1273 #if _LIBCPP_STD_VER > 11
1274 template <typename _K2>
1275 _LIBCPP_INLINE_VISIBILITY
1276 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1277 count(const _K2& __k) const {return __tree_.__count_unique(__k);}
1279 _LIBCPP_INLINE_VISIBILITY
1280 iterator lower_bound(const key_type& __k)
1281 {return __tree_.lower_bound(__k);}
1282 _LIBCPP_INLINE_VISIBILITY
1283 const_iterator lower_bound(const key_type& __k) const
1284 {return __tree_.lower_bound(__k);}
1285 #if _LIBCPP_STD_VER > 11
1286 template <typename _K2>
1287 _LIBCPP_INLINE_VISIBILITY
1288 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1289 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1291 template <typename _K2>
1292 _LIBCPP_INLINE_VISIBILITY
1293 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1294 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1297 _LIBCPP_INLINE_VISIBILITY
1298 iterator upper_bound(const key_type& __k)
1299 {return __tree_.upper_bound(__k);}
1300 _LIBCPP_INLINE_VISIBILITY
1301 const_iterator upper_bound(const key_type& __k) const
1302 {return __tree_.upper_bound(__k);}
1303 #if _LIBCPP_STD_VER > 11
1304 template <typename _K2>
1305 _LIBCPP_INLINE_VISIBILITY
1306 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1307 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1308 template <typename _K2>
1309 _LIBCPP_INLINE_VISIBILITY
1310 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1311 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1314 _LIBCPP_INLINE_VISIBILITY
1315 pair<iterator,iterator> equal_range(const key_type& __k)
1316 {return __tree_.__equal_range_unique(__k);}
1317 _LIBCPP_INLINE_VISIBILITY
1318 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1319 {return __tree_.__equal_range_unique(__k);}
1320 #if _LIBCPP_STD_VER > 11
1321 template <typename _K2>
1322 _LIBCPP_INLINE_VISIBILITY
1323 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1324 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
1325 template <typename _K2>
1326 _LIBCPP_INLINE_VISIBILITY
1327 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1328 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1332 typedef typename __base::__node __node;
1333 typedef typename __base::__node_allocator __node_allocator;
1334 typedef typename __base::__node_pointer __node_pointer;
1335 typedef typename __base::__node_const_pointer __node_const_pointer;
1336 typedef typename __base::__node_base_pointer __node_base_pointer;
1337 typedef typename __base::__node_base_const_pointer __node_base_const_pointer;
1338 typedef __map_node_destructor<__node_allocator> _Dp;
1339 typedef unique_ptr<__node, _Dp> __node_holder;
1341 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1342 __node_holder __construct_node();
1343 template <class _A0>
1344 __node_holder __construct_node(_A0&& __a0);
1345 __node_holder __construct_node_with_key(key_type&& __k);
1346 #ifndef _LIBCPP_HAS_NO_VARIADICS
1347 template <class _A0, class _A1, class ..._Args>
1348 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1349 #endif // _LIBCPP_HAS_NO_VARIADICS
1351 __node_holder __construct_node_with_key(const key_type& __k);
1353 __node_base_pointer&
1354 __find_equal_key(__node_base_pointer& __parent, const key_type& __k);
1355 __node_base_const_pointer
1356 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
1359 // Find place to insert if __k doesn't exist
1360 // Set __parent to parent of null leaf
1361 // Return reference to null leaf
1362 // If __k exists, set parent to node of __k and return reference to node of __k
1363 template <class _Key, class _Tp, class _Compare, class _Allocator>
1364 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1365 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
1366 const key_type& __k)
1368 __node_pointer __nd = __tree_.__root();
1369 if (__nd != nullptr)
1373 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1375 if (__nd->__left_ != nullptr)
1376 __nd = static_cast<__node_pointer>(__nd->__left_);
1379 __parent = static_cast<__node_base_pointer>(__nd);
1380 return __parent->__left_;
1383 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1385 if (__nd->__right_ != nullptr)
1386 __nd = static_cast<__node_pointer>(__nd->__right_);
1389 __parent = static_cast<__node_base_pointer>(__nd);
1390 return __parent->__right_;
1395 __parent = static_cast<__node_base_pointer>(__nd);
1400 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1401 return __parent->__left_;
1405 // Set __parent to parent of null leaf and
1406 // return reference to null leaf iv __k does not exist.
1407 // If __k exists, set parent to node of __k and return reference to node of __k
1408 template <class _Key, class _Tp, class _Compare, class _Allocator>
1409 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer
1410 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent,
1411 const key_type& __k) const
1413 __node_const_pointer __nd = __tree_.__root();
1414 if (__nd != nullptr)
1418 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1420 if (__nd->__left_ != nullptr)
1421 __nd = static_cast<__node_pointer>(__nd->__left_);
1424 __parent = static_cast<__node_base_pointer>(__nd);
1425 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1428 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1430 if (__nd->__right_ != nullptr)
1431 __nd = static_cast<__node_pointer>(__nd->__right_);
1434 __parent = static_cast<__node_base_pointer>(__nd);
1435 return const_cast<const __node_base_const_pointer&>(__parent->__right_);
1440 __parent = static_cast<__node_base_pointer>(__nd);
1445 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1446 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1449 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1451 template <class _Key, class _Tp, class _Compare, class _Allocator>
1452 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1453 : __tree_(_VSTD::move(__m.__tree_), __a)
1455 if (__a != __m.get_allocator())
1457 const_iterator __e = cend();
1458 while (!__m.empty())
1459 __tree_.__insert_unique(__e.__i_,
1460 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1464 template <class _Key, class _Tp, class _Compare, class _Allocator>
1465 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1466 map<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1468 __node_allocator& __na = __tree_.__node_alloc();
1469 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1470 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
1471 __h.get_deleter().__first_constructed = true;
1472 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1473 __h.get_deleter().__second_constructed = true;
1477 template <class _Key, class _Tp, class _Compare, class _Allocator>
1478 template <class _A0>
1479 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1480 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1482 __node_allocator& __na = __tree_.__node_alloc();
1483 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1484 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1485 __h.get_deleter().__first_constructed = true;
1486 __h.get_deleter().__second_constructed = true;
1490 template <class _Key, class _Tp, class _Compare, class _Allocator>
1491 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1492 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k)
1494 __node_allocator& __na = __tree_.__node_alloc();
1495 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1496 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1497 __h.get_deleter().__first_constructed = true;
1498 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1499 __h.get_deleter().__second_constructed = true;
1503 #ifndef _LIBCPP_HAS_NO_VARIADICS
1505 template <class _Key, class _Tp, class _Compare, class _Allocator>
1506 template <class _A0, class _A1, class ..._Args>
1507 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1508 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1510 __node_allocator& __na = __tree_.__node_alloc();
1511 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1512 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1513 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1514 _VSTD::forward<_Args>(__args)...);
1515 __h.get_deleter().__first_constructed = true;
1516 __h.get_deleter().__second_constructed = true;
1520 #endif // _LIBCPP_HAS_NO_VARIADICS
1522 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1524 template <class _Key, class _Tp, class _Compare, class _Allocator>
1525 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1526 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1528 __node_allocator& __na = __tree_.__node_alloc();
1529 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1530 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1531 __h.get_deleter().__first_constructed = true;
1532 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1533 __h.get_deleter().__second_constructed = true;
1534 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
1537 template <class _Key, class _Tp, class _Compare, class _Allocator>
1539 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1541 __node_base_pointer __parent;
1542 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1543 __node_pointer __r = static_cast<__node_pointer>(__child);
1544 if (__child == nullptr)
1546 __node_holder __h = __construct_node_with_key(__k);
1547 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1548 __r = __h.release();
1550 return __r->__value_.__cc.second;
1553 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1555 template <class _Key, class _Tp, class _Compare, class _Allocator>
1557 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1559 __node_base_pointer __parent;
1560 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1561 __node_pointer __r = static_cast<__node_pointer>(__child);
1562 if (__child == nullptr)
1564 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1565 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1566 __r = __h.release();
1568 return __r->__value_.__cc.second;
1571 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1573 template <class _Key, class _Tp, class _Compare, class _Allocator>
1575 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1577 __node_base_pointer __parent;
1578 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1579 #ifndef _LIBCPP_NO_EXCEPTIONS
1580 if (__child == nullptr)
1581 throw out_of_range("map::at: key not found");
1582 #endif // _LIBCPP_NO_EXCEPTIONS
1583 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1586 template <class _Key, class _Tp, class _Compare, class _Allocator>
1588 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1590 __node_base_const_pointer __parent;
1591 __node_base_const_pointer __child = __find_equal_key(__parent, __k);
1592 #ifndef _LIBCPP_NO_EXCEPTIONS
1593 if (__child == nullptr)
1594 throw out_of_range("map::at: key not found");
1595 #endif // _LIBCPP_NO_EXCEPTIONS
1596 return static_cast<__node_const_pointer>(__child)->__value_.__cc.second;
1599 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1601 template <class _Key, class _Tp, class _Compare, class _Allocator>
1602 template <class ..._Args>
1603 pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
1604 map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1606 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1607 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
1613 template <class _Key, class _Tp, class _Compare, class _Allocator>
1614 template <class ..._Args>
1615 typename map<_Key, _Tp, _Compare, _Allocator>::iterator
1616 map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1619 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1620 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get());
1621 if (__r.__i_.__ptr_ == __h.get())
1626 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1628 template <class _Key, class _Tp, class _Compare, class _Allocator>
1629 inline _LIBCPP_INLINE_VISIBILITY
1631 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1632 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1634 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1637 template <class _Key, class _Tp, class _Compare, class _Allocator>
1638 inline _LIBCPP_INLINE_VISIBILITY
1640 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1641 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1643 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1646 template <class _Key, class _Tp, class _Compare, class _Allocator>
1647 inline _LIBCPP_INLINE_VISIBILITY
1649 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1650 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1652 return !(__x == __y);
1655 template <class _Key, class _Tp, class _Compare, class _Allocator>
1656 inline _LIBCPP_INLINE_VISIBILITY
1658 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1659 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1664 template <class _Key, class _Tp, class _Compare, class _Allocator>
1665 inline _LIBCPP_INLINE_VISIBILITY
1667 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1668 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1670 return !(__x < __y);
1673 template <class _Key, class _Tp, class _Compare, class _Allocator>
1674 inline _LIBCPP_INLINE_VISIBILITY
1676 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1677 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1679 return !(__y < __x);
1682 template <class _Key, class _Tp, class _Compare, class _Allocator>
1683 inline _LIBCPP_INLINE_VISIBILITY
1685 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1686 map<_Key, _Tp, _Compare, _Allocator>& __y)
1687 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1692 template <class _Key, class _Tp, class _Compare = less<_Key>,
1693 class _Allocator = allocator<pair<const _Key, _Tp> > >
1694 class _LIBCPP_TYPE_VIS_ONLY multimap
1698 typedef _Key key_type;
1699 typedef _Tp mapped_type;
1700 typedef pair<const key_type, mapped_type> value_type;
1701 typedef pair<key_type, mapped_type> __nc_value_type;
1702 typedef _Compare key_compare;
1703 typedef _Allocator allocator_type;
1704 typedef value_type& reference;
1705 typedef const value_type& const_reference;
1707 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1708 "Allocator::value_type must be same type as value_type");
1710 class _LIBCPP_TYPE_VIS_ONLY value_compare
1711 : public binary_function<value_type, value_type, bool>
1713 friend class multimap;
1717 _LIBCPP_INLINE_VISIBILITY
1718 value_compare(key_compare c) : comp(c) {}
1720 _LIBCPP_INLINE_VISIBILITY
1721 bool operator()(const value_type& __x, const value_type& __y) const
1722 {return comp(__x.first, __y.first);}
1727 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
1728 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1729 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1730 __value_type>::type __allocator_type;
1731 typedef __tree<__value_type, __vc, __allocator_type> __base;
1732 typedef typename __base::__node_traits __node_traits;
1733 typedef allocator_traits<allocator_type> __alloc_traits;
1738 typedef typename __alloc_traits::pointer pointer;
1739 typedef typename __alloc_traits::const_pointer const_pointer;
1740 typedef typename __alloc_traits::size_type size_type;
1741 typedef typename __alloc_traits::difference_type difference_type;
1742 typedef __map_iterator<typename __base::iterator> iterator;
1743 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1744 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1745 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1747 _LIBCPP_INLINE_VISIBILITY
1750 is_nothrow_default_constructible<allocator_type>::value &&
1751 is_nothrow_default_constructible<key_compare>::value &&
1752 is_nothrow_copy_constructible<key_compare>::value)
1753 : __tree_(__vc(key_compare())) {}
1755 _LIBCPP_INLINE_VISIBILITY
1756 explicit multimap(const key_compare& __comp)
1758 is_nothrow_default_constructible<allocator_type>::value &&
1759 is_nothrow_copy_constructible<key_compare>::value)
1760 : __tree_(__vc(__comp)) {}
1762 _LIBCPP_INLINE_VISIBILITY
1763 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1764 : __tree_(__vc(__comp), __a) {}
1766 template <class _InputIterator>
1767 _LIBCPP_INLINE_VISIBILITY
1768 multimap(_InputIterator __f, _InputIterator __l,
1769 const key_compare& __comp = key_compare())
1770 : __tree_(__vc(__comp))
1775 template <class _InputIterator>
1776 _LIBCPP_INLINE_VISIBILITY
1777 multimap(_InputIterator __f, _InputIterator __l,
1778 const key_compare& __comp, const allocator_type& __a)
1779 : __tree_(__vc(__comp), __a)
1784 #if _LIBCPP_STD_VER > 11
1785 template <class _InputIterator>
1786 _LIBCPP_INLINE_VISIBILITY
1787 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1788 : multimap(__f, __l, key_compare(), __a) {}
1791 _LIBCPP_INLINE_VISIBILITY
1792 multimap(const multimap& __m)
1793 : __tree_(__m.__tree_.value_comp(),
1794 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1796 insert(__m.begin(), __m.end());
1799 _LIBCPP_INLINE_VISIBILITY
1800 multimap& operator=(const multimap& __m)
1802 #if __cplusplus >= 201103L
1803 __tree_ = __m.__tree_;
1807 __tree_.value_comp() = __m.__tree_.value_comp();
1808 __tree_.__copy_assign_alloc(__m.__tree_);
1809 insert(__m.begin(), __m.end());
1815 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1817 _LIBCPP_INLINE_VISIBILITY
1818 multimap(multimap&& __m)
1819 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1820 : __tree_(_VSTD::move(__m.__tree_))
1824 multimap(multimap&& __m, const allocator_type& __a);
1826 _LIBCPP_INLINE_VISIBILITY
1827 multimap& operator=(multimap&& __m)
1828 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1830 __tree_ = _VSTD::move(__m.__tree_);
1834 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1836 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1838 _LIBCPP_INLINE_VISIBILITY
1839 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1840 : __tree_(__vc(__comp))
1842 insert(__il.begin(), __il.end());
1845 _LIBCPP_INLINE_VISIBILITY
1846 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1847 : __tree_(__vc(__comp), __a)
1849 insert(__il.begin(), __il.end());
1852 #if _LIBCPP_STD_VER > 11
1853 _LIBCPP_INLINE_VISIBILITY
1854 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1855 : multimap(__il, key_compare(), __a) {}
1858 _LIBCPP_INLINE_VISIBILITY
1859 multimap& operator=(initializer_list<value_type> __il)
1861 __tree_.__assign_multi(__il.begin(), __il.end());
1865 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1867 _LIBCPP_INLINE_VISIBILITY
1868 explicit multimap(const allocator_type& __a)
1873 _LIBCPP_INLINE_VISIBILITY
1874 multimap(const multimap& __m, const allocator_type& __a)
1875 : __tree_(__m.__tree_.value_comp(), __a)
1877 insert(__m.begin(), __m.end());
1880 _LIBCPP_INLINE_VISIBILITY
1881 iterator begin() _NOEXCEPT {return __tree_.begin();}
1882 _LIBCPP_INLINE_VISIBILITY
1883 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1884 _LIBCPP_INLINE_VISIBILITY
1885 iterator end() _NOEXCEPT {return __tree_.end();}
1886 _LIBCPP_INLINE_VISIBILITY
1887 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1889 _LIBCPP_INLINE_VISIBILITY
1890 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1891 _LIBCPP_INLINE_VISIBILITY
1892 const_reverse_iterator rbegin() const _NOEXCEPT
1893 {return const_reverse_iterator(end());}
1894 _LIBCPP_INLINE_VISIBILITY
1895 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1896 _LIBCPP_INLINE_VISIBILITY
1897 const_reverse_iterator rend() const _NOEXCEPT
1898 {return const_reverse_iterator(begin());}
1900 _LIBCPP_INLINE_VISIBILITY
1901 const_iterator cbegin() const _NOEXCEPT {return begin();}
1902 _LIBCPP_INLINE_VISIBILITY
1903 const_iterator cend() const _NOEXCEPT {return end();}
1904 _LIBCPP_INLINE_VISIBILITY
1905 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1906 _LIBCPP_INLINE_VISIBILITY
1907 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1909 _LIBCPP_INLINE_VISIBILITY
1910 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1911 _LIBCPP_INLINE_VISIBILITY
1912 size_type size() const _NOEXCEPT {return __tree_.size();}
1913 _LIBCPP_INLINE_VISIBILITY
1914 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1916 _LIBCPP_INLINE_VISIBILITY
1917 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1918 _LIBCPP_INLINE_VISIBILITY
1919 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1920 _LIBCPP_INLINE_VISIBILITY
1921 value_compare value_comp() const
1922 {return value_compare(__tree_.value_comp().key_comp());}
1924 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1925 #ifndef _LIBCPP_HAS_NO_VARIADICS
1927 template <class ..._Args>
1929 emplace(_Args&& ...__args);
1931 template <class ..._Args>
1933 emplace_hint(const_iterator __p, _Args&& ...__args);
1935 #endif // _LIBCPP_HAS_NO_VARIADICS
1937 template <class _Pp,
1938 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1939 _LIBCPP_INLINE_VISIBILITY
1940 iterator insert(_Pp&& __p)
1941 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1943 template <class _Pp,
1944 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1945 _LIBCPP_INLINE_VISIBILITY
1946 iterator insert(const_iterator __pos, _Pp&& __p)
1947 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1949 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1951 _LIBCPP_INLINE_VISIBILITY
1952 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1954 _LIBCPP_INLINE_VISIBILITY
1955 iterator insert(const_iterator __p, const value_type& __v)
1956 {return __tree_.__insert_multi(__p.__i_, __v);}
1958 #if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1959 _LIBCPP_INLINE_VISIBILITY
1960 iterator insert( value_type&& __v) {return __tree_.__insert_multi(_VSTD::forward<value_type>(__v));}
1962 _LIBCPP_INLINE_VISIBILITY
1963 iterator insert(const_iterator __p, value_type&& __v)
1964 {return __tree_.__insert_multi(__p.__i_, _VSTD::forward<value_type>(__v));}
1967 template <class _InputIterator>
1968 _LIBCPP_INLINE_VISIBILITY
1969 void insert(_InputIterator __f, _InputIterator __l)
1971 for (const_iterator __e = cend(); __f != __l; ++__f)
1972 __tree_.__insert_multi(__e.__i_, *__f);
1975 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1977 _LIBCPP_INLINE_VISIBILITY
1978 void insert(initializer_list<value_type> __il)
1979 {insert(__il.begin(), __il.end());}
1981 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1983 _LIBCPP_INLINE_VISIBILITY
1984 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1985 _LIBCPP_INLINE_VISIBILITY
1986 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1987 _LIBCPP_INLINE_VISIBILITY
1988 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1989 _LIBCPP_INLINE_VISIBILITY
1990 iterator erase(const_iterator __f, const_iterator __l)
1991 {return __tree_.erase(__f.__i_, __l.__i_);}
1992 _LIBCPP_INLINE_VISIBILITY
1993 void clear() {__tree_.clear();}
1995 _LIBCPP_INLINE_VISIBILITY
1996 void swap(multimap& __m)
1997 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1998 {__tree_.swap(__m.__tree_);}
2000 _LIBCPP_INLINE_VISIBILITY
2001 iterator find(const key_type& __k) {return __tree_.find(__k);}
2002 _LIBCPP_INLINE_VISIBILITY
2003 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
2004 #if _LIBCPP_STD_VER > 11
2005 template <typename _K2>
2006 _LIBCPP_INLINE_VISIBILITY
2007 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2008 find(const _K2& __k) {return __tree_.find(__k);}
2009 template <typename _K2>
2010 _LIBCPP_INLINE_VISIBILITY
2011 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2012 find(const _K2& __k) const {return __tree_.find(__k);}
2015 _LIBCPP_INLINE_VISIBILITY
2016 size_type count(const key_type& __k) const
2017 {return __tree_.__count_multi(__k);}
2018 #if _LIBCPP_STD_VER > 11
2019 template <typename _K2>
2020 _LIBCPP_INLINE_VISIBILITY
2021 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
2022 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
2024 _LIBCPP_INLINE_VISIBILITY
2025 iterator lower_bound(const key_type& __k)
2026 {return __tree_.lower_bound(__k);}
2027 _LIBCPP_INLINE_VISIBILITY
2028 const_iterator lower_bound(const key_type& __k) const
2029 {return __tree_.lower_bound(__k);}
2030 #if _LIBCPP_STD_VER > 11
2031 template <typename _K2>
2032 _LIBCPP_INLINE_VISIBILITY
2033 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2034 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
2036 template <typename _K2>
2037 _LIBCPP_INLINE_VISIBILITY
2038 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2039 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
2042 _LIBCPP_INLINE_VISIBILITY
2043 iterator upper_bound(const key_type& __k)
2044 {return __tree_.upper_bound(__k);}
2045 _LIBCPP_INLINE_VISIBILITY
2046 const_iterator upper_bound(const key_type& __k) const
2047 {return __tree_.upper_bound(__k);}
2048 #if _LIBCPP_STD_VER > 11
2049 template <typename _K2>
2050 _LIBCPP_INLINE_VISIBILITY
2051 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2052 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
2053 template <typename _K2>
2054 _LIBCPP_INLINE_VISIBILITY
2055 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2056 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
2059 _LIBCPP_INLINE_VISIBILITY
2060 pair<iterator,iterator> equal_range(const key_type& __k)
2061 {return __tree_.__equal_range_multi(__k);}
2062 _LIBCPP_INLINE_VISIBILITY
2063 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
2064 {return __tree_.__equal_range_multi(__k);}
2065 #if _LIBCPP_STD_VER > 11
2066 template <typename _K2>
2067 _LIBCPP_INLINE_VISIBILITY
2068 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
2069 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
2070 template <typename _K2>
2071 _LIBCPP_INLINE_VISIBILITY
2072 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
2073 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
2077 typedef typename __base::__node __node;
2078 typedef typename __base::__node_allocator __node_allocator;
2079 typedef typename __base::__node_pointer __node_pointer;
2080 typedef typename __base::__node_const_pointer __node_const_pointer;
2081 typedef __map_node_destructor<__node_allocator> _Dp;
2082 typedef unique_ptr<__node, _Dp> __node_holder;
2084 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2085 __node_holder __construct_node();
2086 template <class _A0>
2088 __construct_node(_A0&& __a0);
2089 #ifndef _LIBCPP_HAS_NO_VARIADICS
2090 template <class _A0, class _A1, class ..._Args>
2091 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
2092 #endif // _LIBCPP_HAS_NO_VARIADICS
2093 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2096 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2098 template <class _Key, class _Tp, class _Compare, class _Allocator>
2099 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
2100 : __tree_(_VSTD::move(__m.__tree_), __a)
2102 if (__a != __m.get_allocator())
2104 const_iterator __e = cend();
2105 while (!__m.empty())
2106 __tree_.__insert_multi(__e.__i_,
2107 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
2111 template <class _Key, class _Tp, class _Compare, class _Allocator>
2112 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
2113 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node()
2115 __node_allocator& __na = __tree_.__node_alloc();
2116 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2117 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
2118 __h.get_deleter().__first_constructed = true;
2119 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
2120 __h.get_deleter().__second_constructed = true;
2124 template <class _Key, class _Tp, class _Compare, class _Allocator>
2125 template <class _A0>
2126 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
2127 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
2129 __node_allocator& __na = __tree_.__node_alloc();
2130 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2131 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
2132 __h.get_deleter().__first_constructed = true;
2133 __h.get_deleter().__second_constructed = true;
2137 #ifndef _LIBCPP_HAS_NO_VARIADICS
2139 template <class _Key, class _Tp, class _Compare, class _Allocator>
2140 template <class _A0, class _A1, class ..._Args>
2141 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
2142 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
2144 __node_allocator& __na = __tree_.__node_alloc();
2145 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2146 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
2147 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
2148 _VSTD::forward<_Args>(__args)...);
2149 __h.get_deleter().__first_constructed = true;
2150 __h.get_deleter().__second_constructed = true;
2154 #endif // _LIBCPP_HAS_NO_VARIADICS
2155 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2157 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
2159 template <class _Key, class _Tp, class _Compare, class _Allocator>
2160 template <class ..._Args>
2161 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
2162 multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
2164 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2165 iterator __r = __tree_.__node_insert_multi(__h.get());
2170 template <class _Key, class _Tp, class _Compare, class _Allocator>
2171 template <class ..._Args>
2172 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
2173 multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
2176 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2177 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get());
2182 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
2184 template <class _Key, class _Tp, class _Compare, class _Allocator>
2185 inline _LIBCPP_INLINE_VISIBILITY
2187 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2188 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2190 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2193 template <class _Key, class _Tp, class _Compare, class _Allocator>
2194 inline _LIBCPP_INLINE_VISIBILITY
2196 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2197 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2199 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2202 template <class _Key, class _Tp, class _Compare, class _Allocator>
2203 inline _LIBCPP_INLINE_VISIBILITY
2205 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2206 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2208 return !(__x == __y);
2211 template <class _Key, class _Tp, class _Compare, class _Allocator>
2212 inline _LIBCPP_INLINE_VISIBILITY
2214 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2215 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2220 template <class _Key, class _Tp, class _Compare, class _Allocator>
2221 inline _LIBCPP_INLINE_VISIBILITY
2223 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2224 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2226 return !(__x < __y);
2229 template <class _Key, class _Tp, class _Compare, class _Allocator>
2230 inline _LIBCPP_INLINE_VISIBILITY
2232 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2233 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2235 return !(__y < __x);
2238 template <class _Key, class _Tp, class _Compare, class _Allocator>
2239 inline _LIBCPP_INLINE_VISIBILITY
2241 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2242 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2243 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2248 _LIBCPP_END_NAMESPACE_STD
2250 #endif // _LIBCPP_MAP