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;
43 typedef unspecified node_type; // C++17
44 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
47 : public binary_function<value_type, value_type, bool>
53 value_compare(key_compare c);
55 bool operator()(const value_type& x, const value_type& y) const;
58 // construct/copy/destroy:
61 is_nothrow_default_constructible<allocator_type>::value &&
62 is_nothrow_default_constructible<key_compare>::value &&
63 is_nothrow_copy_constructible<key_compare>::value);
64 explicit map(const key_compare& comp);
65 map(const key_compare& comp, const allocator_type& a);
66 template <class InputIterator>
67 map(InputIterator first, InputIterator last,
68 const key_compare& comp = key_compare());
69 template <class InputIterator>
70 map(InputIterator first, InputIterator last,
71 const key_compare& comp, const allocator_type& a);
75 is_nothrow_move_constructible<allocator_type>::value &&
76 is_nothrow_move_constructible<key_compare>::value);
77 explicit map(const allocator_type& a);
78 map(const map& m, const allocator_type& a);
79 map(map&& m, const allocator_type& a);
80 map(initializer_list<value_type> il, const key_compare& comp = key_compare());
81 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
82 template <class InputIterator>
83 map(InputIterator first, InputIterator last, const allocator_type& a)
84 : map(first, last, Compare(), a) {} // C++14
85 map(initializer_list<value_type> il, const allocator_type& a)
86 : map(il, Compare(), a) {} // C++14
89 map& operator=(const map& m);
90 map& operator=(map&& m)
92 allocator_type::propagate_on_container_move_assignment::value &&
93 is_nothrow_move_assignable<allocator_type>::value &&
94 is_nothrow_move_assignable<key_compare>::value);
95 map& operator=(initializer_list<value_type> il);
98 iterator begin() noexcept;
99 const_iterator begin() const noexcept;
100 iterator end() noexcept;
101 const_iterator end() const noexcept;
103 reverse_iterator rbegin() noexcept;
104 const_reverse_iterator rbegin() const noexcept;
105 reverse_iterator rend() noexcept;
106 const_reverse_iterator rend() const noexcept;
108 const_iterator cbegin() const noexcept;
109 const_iterator cend() const noexcept;
110 const_reverse_iterator crbegin() const noexcept;
111 const_reverse_iterator crend() const noexcept;
114 bool empty() const noexcept;
115 size_type size() const noexcept;
116 size_type max_size() const noexcept;
119 mapped_type& operator[](const key_type& k);
120 mapped_type& operator[](key_type&& k);
122 mapped_type& at(const key_type& k);
123 const mapped_type& at(const key_type& k) const;
126 template <class... Args>
127 pair<iterator, bool> emplace(Args&&... args);
128 template <class... Args>
129 iterator emplace_hint(const_iterator position, Args&&... args);
130 pair<iterator, bool> insert(const value_type& v);
131 pair<iterator, bool> insert( value_type&& v); // C++17
133 pair<iterator, bool> insert(P&& p);
134 iterator insert(const_iterator position, const value_type& v);
135 iterator insert(const_iterator position, value_type&& v); // C++17
137 iterator insert(const_iterator position, P&& p);
138 template <class InputIterator>
139 void insert(InputIterator first, InputIterator last);
140 void insert(initializer_list<value_type> il);
142 node_type extract(const_iterator position); // C++17
143 node_type extract(const key_type& x); // C++17
144 insert_return_type insert(node_type&& nh); // C++17
145 iterator insert(const_iterator hint, node_type&& nh); // C++17
147 template <class... Args>
148 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
149 template <class... Args>
150 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
151 template <class... Args>
152 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
153 template <class... Args>
154 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
156 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
158 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
160 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
162 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
164 iterator erase(const_iterator position);
165 iterator erase(iterator position); // C++14
166 size_type erase(const key_type& k);
167 iterator erase(const_iterator first, const_iterator last);
168 void clear() noexcept;
171 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
172 is_nothrow_swappable<key_compare>::value); // C++17
175 allocator_type get_allocator() const noexcept;
176 key_compare key_comp() const;
177 value_compare value_comp() const;
180 iterator find(const key_type& k);
181 const_iterator find(const key_type& k) const;
183 iterator find(const K& x); // C++14
185 const_iterator find(const K& x) const; // C++14
187 size_type count(const K& x) const; // C++14
189 size_type count(const key_type& k) const;
190 iterator lower_bound(const key_type& k);
191 const_iterator lower_bound(const key_type& k) const;
193 iterator lower_bound(const K& x); // C++14
195 const_iterator lower_bound(const K& x) const; // C++14
197 iterator upper_bound(const key_type& k);
198 const_iterator upper_bound(const key_type& k) const;
200 iterator upper_bound(const K& x); // C++14
202 const_iterator upper_bound(const K& x) const; // C++14
204 pair<iterator,iterator> equal_range(const key_type& k);
205 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
207 pair<iterator,iterator> equal_range(const K& x); // C++14
209 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
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 template <class Key, class T, class Compare, class Allocator>
219 operator< (const map<Key, T, Compare, Allocator>& x,
220 const map<Key, T, Compare, Allocator>& y);
222 template <class Key, class T, class Compare, class Allocator>
224 operator!=(const map<Key, T, Compare, Allocator>& x,
225 const map<Key, T, Compare, Allocator>& y);
227 template <class Key, class T, class Compare, class Allocator>
229 operator> (const map<Key, T, Compare, Allocator>& x,
230 const map<Key, T, Compare, Allocator>& y);
232 template <class Key, class T, class Compare, class Allocator>
234 operator>=(const map<Key, T, Compare, Allocator>& x,
235 const map<Key, T, Compare, Allocator>& y);
237 template <class Key, class T, class Compare, class Allocator>
239 operator<=(const map<Key, T, Compare, Allocator>& x,
240 const map<Key, T, Compare, Allocator>& y);
242 // specialized algorithms:
243 template <class Key, class T, class Compare, class Allocator>
245 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
246 noexcept(noexcept(x.swap(y)));
248 template <class Key, class T, class Compare = less<Key>,
249 class Allocator = allocator<pair<const Key, T>>>
254 typedef Key key_type;
255 typedef T mapped_type;
256 typedef pair<const key_type,mapped_type> value_type;
257 typedef Compare key_compare;
258 typedef Allocator allocator_type;
259 typedef typename allocator_type::reference reference;
260 typedef typename allocator_type::const_reference const_reference;
261 typedef typename allocator_type::size_type size_type;
262 typedef typename allocator_type::difference_type difference_type;
263 typedef typename allocator_type::pointer pointer;
264 typedef typename allocator_type::const_pointer const_pointer;
266 typedef implementation-defined iterator;
267 typedef implementation-defined const_iterator;
268 typedef std::reverse_iterator<iterator> reverse_iterator;
269 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
270 typedef unspecified node_type; // C++17
273 : public binary_function<value_type,value_type,bool>
275 friend class multimap;
278 value_compare(key_compare c);
280 bool operator()(const value_type& x, const value_type& y) const;
283 // construct/copy/destroy:
286 is_nothrow_default_constructible<allocator_type>::value &&
287 is_nothrow_default_constructible<key_compare>::value &&
288 is_nothrow_copy_constructible<key_compare>::value);
289 explicit multimap(const key_compare& comp);
290 multimap(const key_compare& comp, const allocator_type& a);
291 template <class InputIterator>
292 multimap(InputIterator first, InputIterator last, const key_compare& comp);
293 template <class InputIterator>
294 multimap(InputIterator first, InputIterator last, const key_compare& comp,
295 const allocator_type& a);
296 multimap(const multimap& m);
297 multimap(multimap&& m)
299 is_nothrow_move_constructible<allocator_type>::value &&
300 is_nothrow_move_constructible<key_compare>::value);
301 explicit multimap(const allocator_type& a);
302 multimap(const multimap& m, const allocator_type& a);
303 multimap(multimap&& m, const allocator_type& a);
304 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
305 multimap(initializer_list<value_type> il, const key_compare& comp,
306 const allocator_type& a);
307 template <class InputIterator>
308 multimap(InputIterator first, InputIterator last, const allocator_type& a)
309 : multimap(first, last, Compare(), a) {} // C++14
310 multimap(initializer_list<value_type> il, const allocator_type& a)
311 : multimap(il, Compare(), a) {} // C++14
314 multimap& operator=(const multimap& m);
315 multimap& operator=(multimap&& m)
317 allocator_type::propagate_on_container_move_assignment::value &&
318 is_nothrow_move_assignable<allocator_type>::value &&
319 is_nothrow_move_assignable<key_compare>::value);
320 multimap& operator=(initializer_list<value_type> il);
323 iterator begin() noexcept;
324 const_iterator begin() const noexcept;
325 iterator end() noexcept;
326 const_iterator end() const noexcept;
328 reverse_iterator rbegin() noexcept;
329 const_reverse_iterator rbegin() const noexcept;
330 reverse_iterator rend() noexcept;
331 const_reverse_iterator rend() const noexcept;
333 const_iterator cbegin() const noexcept;
334 const_iterator cend() const noexcept;
335 const_reverse_iterator crbegin() const noexcept;
336 const_reverse_iterator crend() const noexcept;
339 bool empty() const noexcept;
340 size_type size() const noexcept;
341 size_type max_size() const noexcept;
344 template <class... Args>
345 iterator emplace(Args&&... args);
346 template <class... Args>
347 iterator emplace_hint(const_iterator position, Args&&... args);
348 iterator insert(const value_type& v);
349 iterator insert( value_type&& v); // C++17
351 iterator insert(P&& p);
352 iterator insert(const_iterator position, const value_type& v);
353 iterator insert(const_iterator position, value_type&& v); // C++17
355 iterator insert(const_iterator position, P&& p);
356 template <class InputIterator>
357 void insert(InputIterator first, InputIterator last);
358 void insert(initializer_list<value_type> il);
360 node_type extract(const_iterator position); // C++17
361 node_type extract(const key_type& x); // C++17
362 iterator insert(node_type&& nh); // C++17
363 iterator insert(const_iterator hint, node_type&& nh); // C++17
365 iterator erase(const_iterator position);
366 iterator erase(iterator position); // C++14
367 size_type erase(const key_type& k);
368 iterator erase(const_iterator first, const_iterator last);
369 void clear() noexcept;
371 void swap(multimap& m)
372 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
373 is_nothrow_swappable<key_compare>::value); // C++17
376 allocator_type get_allocator() const noexcept;
377 key_compare key_comp() const;
378 value_compare value_comp() const;
381 iterator find(const key_type& k);
382 const_iterator find(const key_type& k) const;
384 iterator find(const K& x); // C++14
386 const_iterator find(const K& x) const; // C++14
388 size_type count(const K& x) const; // C++14
390 size_type count(const key_type& k) const;
391 iterator lower_bound(const key_type& k);
392 const_iterator lower_bound(const key_type& k) const;
394 iterator lower_bound(const K& x); // C++14
396 const_iterator lower_bound(const K& x) const; // C++14
398 iterator upper_bound(const key_type& k);
399 const_iterator upper_bound(const key_type& k) const;
401 iterator upper_bound(const K& x); // C++14
403 const_iterator upper_bound(const K& x) const; // C++14
405 pair<iterator,iterator> equal_range(const key_type& k);
406 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
408 pair<iterator,iterator> equal_range(const K& x); // C++14
410 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
413 template <class Key, class T, class Compare, class Allocator>
415 operator==(const multimap<Key, T, Compare, Allocator>& x,
416 const multimap<Key, T, Compare, Allocator>& y);
418 template <class Key, class T, class Compare, class Allocator>
420 operator< (const multimap<Key, T, Compare, Allocator>& x,
421 const multimap<Key, T, Compare, Allocator>& y);
423 template <class Key, class T, class Compare, class Allocator>
425 operator!=(const multimap<Key, T, Compare, Allocator>& x,
426 const multimap<Key, T, Compare, Allocator>& y);
428 template <class Key, class T, class Compare, class Allocator>
430 operator> (const multimap<Key, T, Compare, Allocator>& x,
431 const multimap<Key, T, Compare, Allocator>& y);
433 template <class Key, class T, class Compare, class Allocator>
435 operator>=(const multimap<Key, T, Compare, Allocator>& x,
436 const multimap<Key, T, Compare, Allocator>& y);
438 template <class Key, class T, class Compare, class Allocator>
440 operator<=(const multimap<Key, T, Compare, Allocator>& x,
441 const multimap<Key, T, Compare, Allocator>& y);
443 // specialized algorithms:
444 template <class Key, class T, class Compare, class Allocator>
446 swap(multimap<Key, T, Compare, Allocator>& x,
447 multimap<Key, T, Compare, Allocator>& y)
448 noexcept(noexcept(x.swap(y)));
456 #include <__node_handle>
460 #include <functional>
461 #include <initializer_list>
462 #include <type_traits>
464 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
465 #pragma GCC system_header
468 _LIBCPP_BEGIN_NAMESPACE_STD
470 template <class _Key, class _CP, class _Compare, bool _IsSmall>
471 class __map_value_compare
475 _LIBCPP_INLINE_VISIBILITY
476 __map_value_compare()
477 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
479 _LIBCPP_INLINE_VISIBILITY
480 __map_value_compare(_Compare c)
481 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
483 _LIBCPP_INLINE_VISIBILITY
484 const _Compare& key_comp() const _NOEXCEPT {return *this;}
485 _LIBCPP_INLINE_VISIBILITY
486 bool operator()(const _CP& __x, const _CP& __y) const
487 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);}
488 _LIBCPP_INLINE_VISIBILITY
489 bool operator()(const _CP& __x, const _Key& __y) const
490 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);}
491 _LIBCPP_INLINE_VISIBILITY
492 bool operator()(const _Key& __x, const _CP& __y) const
493 {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);}
494 void swap(__map_value_compare&__y)
495 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
498 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
501 #if _LIBCPP_STD_VER > 11
502 template <typename _K2>
503 _LIBCPP_INLINE_VISIBILITY
504 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
505 operator () ( const _K2& __x, const _CP& __y ) const
506 {return static_cast<const _Compare&>(*this) (__x, __y.__get_value().first);}
508 template <typename _K2>
509 _LIBCPP_INLINE_VISIBILITY
510 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
511 operator () (const _CP& __x, const _K2& __y) const
512 {return static_cast<const _Compare&>(*this) (__x.__get_value().first, __y);}
516 template <class _Key, class _CP, class _Compare>
517 class __map_value_compare<_Key, _CP, _Compare, false>
522 _LIBCPP_INLINE_VISIBILITY
523 __map_value_compare()
524 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
526 _LIBCPP_INLINE_VISIBILITY
527 __map_value_compare(_Compare c)
528 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
530 _LIBCPP_INLINE_VISIBILITY
531 const _Compare& key_comp() const _NOEXCEPT {return comp;}
533 _LIBCPP_INLINE_VISIBILITY
534 bool operator()(const _CP& __x, const _CP& __y) const
535 {return comp(__x.__get_value().first, __y.__get_value().first);}
536 _LIBCPP_INLINE_VISIBILITY
537 bool operator()(const _CP& __x, const _Key& __y) const
538 {return comp(__x.__get_value().first, __y);}
539 _LIBCPP_INLINE_VISIBILITY
540 bool operator()(const _Key& __x, const _CP& __y) const
541 {return comp(__x, __y.__get_value().first);}
542 void swap(__map_value_compare&__y)
543 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
546 swap(comp, __y.comp);
549 #if _LIBCPP_STD_VER > 11
550 template <typename _K2>
551 _LIBCPP_INLINE_VISIBILITY
552 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
553 operator () ( const _K2& __x, const _CP& __y ) const
554 {return comp (__x, __y.__get_value().first);}
556 template <typename _K2>
557 _LIBCPP_INLINE_VISIBILITY
558 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
559 operator () (const _CP& __x, const _K2& __y) const
560 {return comp (__x.__get_value().first, __y);}
564 template <class _Key, class _CP, class _Compare, bool __b>
565 inline _LIBCPP_INLINE_VISIBILITY
567 swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
568 __map_value_compare<_Key, _CP, _Compare, __b>& __y)
569 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
574 template <class _Allocator>
575 class __map_node_destructor
577 typedef _Allocator allocator_type;
578 typedef allocator_traits<allocator_type> __alloc_traits;
581 typedef typename __alloc_traits::pointer pointer;
584 allocator_type& __na_;
586 __map_node_destructor& operator=(const __map_node_destructor&);
589 bool __first_constructed;
590 bool __second_constructed;
592 _LIBCPP_INLINE_VISIBILITY
593 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
595 __first_constructed(false),
596 __second_constructed(false)
599 #ifndef _LIBCPP_CXX03_LANG
600 _LIBCPP_INLINE_VISIBILITY
601 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
603 __first_constructed(__x.__value_constructed),
604 __second_constructed(__x.__value_constructed)
606 __x.__value_constructed = false;
608 #endif // _LIBCPP_CXX03_LANG
610 _LIBCPP_INLINE_VISIBILITY
611 void operator()(pointer __p) _NOEXCEPT
613 if (__second_constructed)
614 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
615 if (__first_constructed)
616 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
618 __alloc_traits::deallocate(__na_, __p, 1);
622 template <class _Key, class _Tp, class _Compare, class _Allocator>
624 template <class _Key, class _Tp, class _Compare, class _Allocator>
626 template <class _TreeIterator> class __map_const_iterator;
628 #ifndef _LIBCPP_CXX03_LANG
630 template <class _Key, class _Tp>
633 typedef _Key key_type;
634 typedef _Tp mapped_type;
635 typedef pair<const key_type, mapped_type> value_type;
636 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
637 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
643 _LIBCPP_INLINE_VISIBILITY
644 value_type& __get_value()
646 #if _LIBCPP_STD_VER > 14
647 return *_VSTD::launder(_VSTD::addressof(__cc));
653 _LIBCPP_INLINE_VISIBILITY
654 const value_type& __get_value() const
656 #if _LIBCPP_STD_VER > 14
657 return *_VSTD::launder(_VSTD::addressof(__cc));
663 _LIBCPP_INLINE_VISIBILITY
664 __nc_ref_pair_type __ref()
666 value_type& __v = __get_value();
667 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
670 _LIBCPP_INLINE_VISIBILITY
671 __nc_rref_pair_type __move()
673 value_type& __v = __get_value();
674 return __nc_rref_pair_type(
675 _VSTD::move(const_cast<key_type&>(__v.first)),
676 _VSTD::move(__v.second));
679 _LIBCPP_INLINE_VISIBILITY
680 __value_type& operator=(const __value_type& __v)
682 __ref() = __v.__get_value();
686 _LIBCPP_INLINE_VISIBILITY
687 __value_type& operator=(__value_type&& __v)
689 __ref() = __v.__move();
693 template <class _ValueTp,
694 class = typename enable_if<
695 __is_same_uncvref<_ValueTp, value_type>::value
698 _LIBCPP_INLINE_VISIBILITY
699 __value_type& operator=(_ValueTp&& __v)
701 __ref() = _VSTD::forward<_ValueTp>(__v);
706 __value_type() _LIBCPP_EQUAL_DELETE;
707 ~__value_type() _LIBCPP_EQUAL_DELETE;
708 __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
709 __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
714 template <class _Key, class _Tp>
717 typedef _Key key_type;
718 typedef _Tp mapped_type;
719 typedef pair<const key_type, mapped_type> value_type;
725 _LIBCPP_INLINE_VISIBILITY
726 value_type& __get_value() { return __cc; }
727 _LIBCPP_INLINE_VISIBILITY
728 const value_type& __get_value() const { return __cc; }
732 __value_type(__value_type const&);
733 __value_type& operator=(__value_type const&);
737 #endif // _LIBCPP_CXX03_LANG
740 struct __extract_key_value_types;
742 template <class _Key, class _Tp>
743 struct __extract_key_value_types<__value_type<_Key, _Tp> >
745 typedef _Key const __key_type;
746 typedef _Tp __mapped_type;
749 template <class _TreeIterator>
750 class _LIBCPP_TEMPLATE_VIS __map_iterator
752 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
753 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
758 typedef bidirectional_iterator_tag iterator_category;
759 typedef typename _NodeTypes::__map_value_type value_type;
760 typedef typename _TreeIterator::difference_type difference_type;
761 typedef value_type& reference;
762 typedef typename _NodeTypes::__map_value_type_pointer pointer;
764 _LIBCPP_INLINE_VISIBILITY
765 __map_iterator() _NOEXCEPT {}
767 _LIBCPP_INLINE_VISIBILITY
768 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
770 _LIBCPP_INLINE_VISIBILITY
771 reference operator*() const {return __i_->__get_value();}
772 _LIBCPP_INLINE_VISIBILITY
773 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
775 _LIBCPP_INLINE_VISIBILITY
776 __map_iterator& operator++() {++__i_; return *this;}
777 _LIBCPP_INLINE_VISIBILITY
778 __map_iterator operator++(int)
780 __map_iterator __t(*this);
785 _LIBCPP_INLINE_VISIBILITY
786 __map_iterator& operator--() {--__i_; return *this;}
787 _LIBCPP_INLINE_VISIBILITY
788 __map_iterator operator--(int)
790 __map_iterator __t(*this);
795 friend _LIBCPP_INLINE_VISIBILITY
796 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
797 {return __x.__i_ == __y.__i_;}
799 _LIBCPP_INLINE_VISIBILITY
800 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
801 {return __x.__i_ != __y.__i_;}
803 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
804 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
805 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
808 template <class _TreeIterator>
809 class _LIBCPP_TEMPLATE_VIS __map_const_iterator
811 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
812 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
817 typedef bidirectional_iterator_tag iterator_category;
818 typedef typename _NodeTypes::__map_value_type value_type;
819 typedef typename _TreeIterator::difference_type difference_type;
820 typedef const value_type& reference;
821 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
823 _LIBCPP_INLINE_VISIBILITY
824 __map_const_iterator() _NOEXCEPT {}
826 _LIBCPP_INLINE_VISIBILITY
827 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
828 _LIBCPP_INLINE_VISIBILITY
829 __map_const_iterator(__map_iterator<
830 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
833 _LIBCPP_INLINE_VISIBILITY
834 reference operator*() const {return __i_->__get_value();}
835 _LIBCPP_INLINE_VISIBILITY
836 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
838 _LIBCPP_INLINE_VISIBILITY
839 __map_const_iterator& operator++() {++__i_; return *this;}
840 _LIBCPP_INLINE_VISIBILITY
841 __map_const_iterator operator++(int)
843 __map_const_iterator __t(*this);
848 _LIBCPP_INLINE_VISIBILITY
849 __map_const_iterator& operator--() {--__i_; return *this;}
850 _LIBCPP_INLINE_VISIBILITY
851 __map_const_iterator operator--(int)
853 __map_const_iterator __t(*this);
858 friend _LIBCPP_INLINE_VISIBILITY
859 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
860 {return __x.__i_ == __y.__i_;}
861 friend _LIBCPP_INLINE_VISIBILITY
862 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
863 {return __x.__i_ != __y.__i_;}
865 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
866 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
867 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
870 template <class _Key, class _Tp, class _Compare = less<_Key>,
871 class _Allocator = allocator<pair<const _Key, _Tp> > >
872 class _LIBCPP_TEMPLATE_VIS map
876 typedef _Key key_type;
877 typedef _Tp mapped_type;
878 typedef pair<const key_type, mapped_type> value_type;
879 typedef _Compare key_compare;
880 typedef _Allocator allocator_type;
881 typedef value_type& reference;
882 typedef const value_type& const_reference;
884 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
885 "Allocator::value_type must be same type as value_type");
887 class _LIBCPP_TEMPLATE_VIS value_compare
888 : public binary_function<value_type, value_type, bool>
894 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
896 _LIBCPP_INLINE_VISIBILITY
897 bool operator()(const value_type& __x, const value_type& __y) const
898 {return comp(__x.first, __y.first);}
903 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
904 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
905 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
906 __value_type>::type __allocator_type;
907 typedef __tree<__value_type, __vc, __allocator_type> __base;
908 typedef typename __base::__node_traits __node_traits;
909 typedef allocator_traits<allocator_type> __alloc_traits;
914 typedef typename __alloc_traits::pointer pointer;
915 typedef typename __alloc_traits::const_pointer const_pointer;
916 typedef typename __alloc_traits::size_type size_type;
917 typedef typename __alloc_traits::difference_type difference_type;
918 typedef __map_iterator<typename __base::iterator> iterator;
919 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
920 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
921 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
923 #if _LIBCPP_STD_VER > 14
924 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
925 typedef __insert_return_type<iterator, node_type> insert_return_type;
928 _LIBCPP_INLINE_VISIBILITY
931 is_nothrow_default_constructible<allocator_type>::value &&
932 is_nothrow_default_constructible<key_compare>::value &&
933 is_nothrow_copy_constructible<key_compare>::value)
934 : __tree_(__vc(key_compare())) {}
936 _LIBCPP_INLINE_VISIBILITY
937 explicit map(const key_compare& __comp)
939 is_nothrow_default_constructible<allocator_type>::value &&
940 is_nothrow_copy_constructible<key_compare>::value)
941 : __tree_(__vc(__comp)) {}
943 _LIBCPP_INLINE_VISIBILITY
944 explicit map(const key_compare& __comp, const allocator_type& __a)
945 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
947 template <class _InputIterator>
948 _LIBCPP_INLINE_VISIBILITY
949 map(_InputIterator __f, _InputIterator __l,
950 const key_compare& __comp = key_compare())
951 : __tree_(__vc(__comp))
956 template <class _InputIterator>
957 _LIBCPP_INLINE_VISIBILITY
958 map(_InputIterator __f, _InputIterator __l,
959 const key_compare& __comp, const allocator_type& __a)
960 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
965 #if _LIBCPP_STD_VER > 11
966 template <class _InputIterator>
967 _LIBCPP_INLINE_VISIBILITY
968 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
969 : map(__f, __l, key_compare(), __a) {}
972 _LIBCPP_INLINE_VISIBILITY
974 : __tree_(__m.__tree_)
976 insert(__m.begin(), __m.end());
979 _LIBCPP_INLINE_VISIBILITY
980 map& operator=(const map& __m)
982 #ifndef _LIBCPP_CXX03_LANG
983 __tree_ = __m.__tree_;
987 __tree_.value_comp() = __m.__tree_.value_comp();
988 __tree_.__copy_assign_alloc(__m.__tree_);
989 insert(__m.begin(), __m.end());
995 #ifndef _LIBCPP_CXX03_LANG
997 _LIBCPP_INLINE_VISIBILITY
999 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1000 : __tree_(_VSTD::move(__m.__tree_))
1004 map(map&& __m, const allocator_type& __a);
1006 _LIBCPP_INLINE_VISIBILITY
1007 map& operator=(map&& __m)
1008 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1010 __tree_ = _VSTD::move(__m.__tree_);
1014 _LIBCPP_INLINE_VISIBILITY
1015 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1016 : __tree_(__vc(__comp))
1018 insert(__il.begin(), __il.end());
1021 _LIBCPP_INLINE_VISIBILITY
1022 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1023 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1025 insert(__il.begin(), __il.end());
1028 #if _LIBCPP_STD_VER > 11
1029 _LIBCPP_INLINE_VISIBILITY
1030 map(initializer_list<value_type> __il, const allocator_type& __a)
1031 : map(__il, key_compare(), __a) {}
1034 _LIBCPP_INLINE_VISIBILITY
1035 map& operator=(initializer_list<value_type> __il)
1037 __tree_.__assign_unique(__il.begin(), __il.end());
1041 #endif // _LIBCPP_CXX03_LANG
1043 _LIBCPP_INLINE_VISIBILITY
1044 explicit map(const allocator_type& __a)
1045 : __tree_(typename __base::allocator_type(__a))
1049 _LIBCPP_INLINE_VISIBILITY
1050 map(const map& __m, const allocator_type& __a)
1051 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1053 insert(__m.begin(), __m.end());
1056 _LIBCPP_INLINE_VISIBILITY
1057 iterator begin() _NOEXCEPT {return __tree_.begin();}
1058 _LIBCPP_INLINE_VISIBILITY
1059 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1060 _LIBCPP_INLINE_VISIBILITY
1061 iterator end() _NOEXCEPT {return __tree_.end();}
1062 _LIBCPP_INLINE_VISIBILITY
1063 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1065 _LIBCPP_INLINE_VISIBILITY
1066 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1067 _LIBCPP_INLINE_VISIBILITY
1068 const_reverse_iterator rbegin() const _NOEXCEPT
1069 {return const_reverse_iterator(end());}
1070 _LIBCPP_INLINE_VISIBILITY
1071 reverse_iterator rend() _NOEXCEPT
1072 {return reverse_iterator(begin());}
1073 _LIBCPP_INLINE_VISIBILITY
1074 const_reverse_iterator rend() const _NOEXCEPT
1075 {return const_reverse_iterator(begin());}
1077 _LIBCPP_INLINE_VISIBILITY
1078 const_iterator cbegin() const _NOEXCEPT {return begin();}
1079 _LIBCPP_INLINE_VISIBILITY
1080 const_iterator cend() const _NOEXCEPT {return end();}
1081 _LIBCPP_INLINE_VISIBILITY
1082 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1083 _LIBCPP_INLINE_VISIBILITY
1084 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1086 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1087 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1088 _LIBCPP_INLINE_VISIBILITY
1089 size_type size() const _NOEXCEPT {return __tree_.size();}
1090 _LIBCPP_INLINE_VISIBILITY
1091 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1093 mapped_type& operator[](const key_type& __k);
1094 #ifndef _LIBCPP_CXX03_LANG
1095 mapped_type& operator[](key_type&& __k);
1098 mapped_type& at(const key_type& __k);
1099 const mapped_type& at(const key_type& __k) const;
1101 _LIBCPP_INLINE_VISIBILITY
1102 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1103 _LIBCPP_INLINE_VISIBILITY
1104 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1105 _LIBCPP_INLINE_VISIBILITY
1106 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1108 #ifndef _LIBCPP_CXX03_LANG
1109 template <class ..._Args>
1110 _LIBCPP_INLINE_VISIBILITY
1111 pair<iterator, bool> emplace(_Args&& ...__args) {
1112 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1115 template <class ..._Args>
1116 _LIBCPP_INLINE_VISIBILITY
1117 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1118 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1121 template <class _Pp,
1122 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1123 _LIBCPP_INLINE_VISIBILITY
1124 pair<iterator, bool> insert(_Pp&& __p)
1125 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1127 template <class _Pp,
1128 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1129 _LIBCPP_INLINE_VISIBILITY
1130 iterator insert(const_iterator __pos, _Pp&& __p)
1131 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1133 #endif // _LIBCPP_CXX03_LANG
1135 _LIBCPP_INLINE_VISIBILITY
1136 pair<iterator, bool>
1137 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1139 _LIBCPP_INLINE_VISIBILITY
1141 insert(const_iterator __p, const value_type& __v)
1142 {return __tree_.__insert_unique(__p.__i_, __v);}
1144 #ifndef _LIBCPP_CXX03_LANG
1145 _LIBCPP_INLINE_VISIBILITY
1146 pair<iterator, bool>
1147 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
1149 _LIBCPP_INLINE_VISIBILITY
1150 iterator insert(const_iterator __p, value_type&& __v)
1151 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
1153 _LIBCPP_INLINE_VISIBILITY
1154 void insert(initializer_list<value_type> __il)
1155 {insert(__il.begin(), __il.end());}
1158 template <class _InputIterator>
1159 _LIBCPP_INLINE_VISIBILITY
1160 void insert(_InputIterator __f, _InputIterator __l)
1162 for (const_iterator __e = cend(); __f != __l; ++__f)
1163 insert(__e.__i_, *__f);
1166 #if _LIBCPP_STD_VER > 14
1168 template <class... _Args>
1169 _LIBCPP_INLINE_VISIBILITY
1170 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1172 return __tree_.__emplace_unique_key_args(__k,
1173 _VSTD::piecewise_construct,
1174 _VSTD::forward_as_tuple(__k),
1175 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1178 template <class... _Args>
1179 _LIBCPP_INLINE_VISIBILITY
1180 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1182 return __tree_.__emplace_unique_key_args(__k,
1183 _VSTD::piecewise_construct,
1184 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1185 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1188 template <class... _Args>
1189 _LIBCPP_INLINE_VISIBILITY
1190 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1192 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1193 _VSTD::piecewise_construct,
1194 _VSTD::forward_as_tuple(__k),
1195 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1198 template <class... _Args>
1199 _LIBCPP_INLINE_VISIBILITY
1200 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1202 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1203 _VSTD::piecewise_construct,
1204 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1205 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1208 template <class _Vp>
1209 _LIBCPP_INLINE_VISIBILITY
1210 pair<iterator, bool> insert_or_assign(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);
1216 return _VSTD::make_pair(__p, false);
1218 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1221 template <class _Vp>
1222 _LIBCPP_INLINE_VISIBILITY
1223 pair<iterator, bool> insert_or_assign(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);
1229 return _VSTD::make_pair(__p, false);
1231 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1234 template <class _Vp>
1235 _LIBCPP_INLINE_VISIBILITY
1236 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1238 iterator __p = lower_bound(__k);
1239 if ( __p != end() && !key_comp()(__k, __p->first))
1241 __p->second = _VSTD::forward<_Vp>(__v);
1244 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1247 template <class _Vp>
1248 _LIBCPP_INLINE_VISIBILITY
1249 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1251 iterator __p = lower_bound(__k);
1252 if ( __p != end() && !key_comp()(__k, __p->first))
1254 __p->second = _VSTD::forward<_Vp>(__v);
1257 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1260 #endif // _LIBCPP_STD_VER > 14
1262 _LIBCPP_INLINE_VISIBILITY
1263 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1264 _LIBCPP_INLINE_VISIBILITY
1265 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1266 _LIBCPP_INLINE_VISIBILITY
1267 size_type erase(const key_type& __k)
1268 {return __tree_.__erase_unique(__k);}
1269 _LIBCPP_INLINE_VISIBILITY
1270 iterator erase(const_iterator __f, const_iterator __l)
1271 {return __tree_.erase(__f.__i_, __l.__i_);}
1272 _LIBCPP_INLINE_VISIBILITY
1273 void clear() _NOEXCEPT {__tree_.clear();}
1275 #if _LIBCPP_STD_VER > 14
1276 _LIBCPP_INLINE_VISIBILITY
1277 insert_return_type insert(node_type&& __nh)
1279 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1280 "node_type with incompatible allocator passed to map::insert()");
1281 return __tree_.template __node_handle_insert_unique<
1282 node_type, insert_return_type>(_VSTD::move(__nh));
1284 _LIBCPP_INLINE_VISIBILITY
1285 iterator insert(const_iterator __hint, node_type&& __nh)
1287 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1288 "node_type with incompatible allocator passed to map::insert()");
1289 return __tree_.template __node_handle_insert_unique<node_type>(
1290 __hint.__i_, _VSTD::move(__nh));
1292 _LIBCPP_INLINE_VISIBILITY
1293 node_type extract(key_type const& __key)
1295 return __tree_.template __node_handle_extract<node_type>(__key);
1297 _LIBCPP_INLINE_VISIBILITY
1298 node_type extract(const_iterator __it)
1300 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1304 _LIBCPP_INLINE_VISIBILITY
1306 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1307 {__tree_.swap(__m.__tree_);}
1309 _LIBCPP_INLINE_VISIBILITY
1310 iterator find(const key_type& __k) {return __tree_.find(__k);}
1311 _LIBCPP_INLINE_VISIBILITY
1312 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1313 #if _LIBCPP_STD_VER > 11
1314 template <typename _K2>
1315 _LIBCPP_INLINE_VISIBILITY
1316 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1317 find(const _K2& __k) {return __tree_.find(__k);}
1318 template <typename _K2>
1319 _LIBCPP_INLINE_VISIBILITY
1320 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1321 find(const _K2& __k) const {return __tree_.find(__k);}
1324 _LIBCPP_INLINE_VISIBILITY
1325 size_type count(const key_type& __k) const
1326 {return __tree_.__count_unique(__k);}
1327 #if _LIBCPP_STD_VER > 11
1328 template <typename _K2>
1329 _LIBCPP_INLINE_VISIBILITY
1330 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1331 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
1333 _LIBCPP_INLINE_VISIBILITY
1334 iterator lower_bound(const key_type& __k)
1335 {return __tree_.lower_bound(__k);}
1336 _LIBCPP_INLINE_VISIBILITY
1337 const_iterator lower_bound(const key_type& __k) const
1338 {return __tree_.lower_bound(__k);}
1339 #if _LIBCPP_STD_VER > 11
1340 template <typename _K2>
1341 _LIBCPP_INLINE_VISIBILITY
1342 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1343 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1345 template <typename _K2>
1346 _LIBCPP_INLINE_VISIBILITY
1347 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1348 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1351 _LIBCPP_INLINE_VISIBILITY
1352 iterator upper_bound(const key_type& __k)
1353 {return __tree_.upper_bound(__k);}
1354 _LIBCPP_INLINE_VISIBILITY
1355 const_iterator upper_bound(const key_type& __k) const
1356 {return __tree_.upper_bound(__k);}
1357 #if _LIBCPP_STD_VER > 11
1358 template <typename _K2>
1359 _LIBCPP_INLINE_VISIBILITY
1360 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1361 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1362 template <typename _K2>
1363 _LIBCPP_INLINE_VISIBILITY
1364 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1365 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1368 _LIBCPP_INLINE_VISIBILITY
1369 pair<iterator,iterator> equal_range(const key_type& __k)
1370 {return __tree_.__equal_range_unique(__k);}
1371 _LIBCPP_INLINE_VISIBILITY
1372 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1373 {return __tree_.__equal_range_unique(__k);}
1374 #if _LIBCPP_STD_VER > 11
1375 template <typename _K2>
1376 _LIBCPP_INLINE_VISIBILITY
1377 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1378 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1379 template <typename _K2>
1380 _LIBCPP_INLINE_VISIBILITY
1381 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1382 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1386 typedef typename __base::__node __node;
1387 typedef typename __base::__node_allocator __node_allocator;
1388 typedef typename __base::__node_pointer __node_pointer;
1389 typedef typename __base::__node_base_pointer __node_base_pointer;
1390 typedef typename __base::__parent_pointer __parent_pointer;
1392 typedef __map_node_destructor<__node_allocator> _Dp;
1393 typedef unique_ptr<__node, _Dp> __node_holder;
1395 #ifdef _LIBCPP_CXX03_LANG
1396 __node_holder __construct_node_with_key(const key_type& __k);
1401 #ifndef _LIBCPP_CXX03_LANG
1402 template <class _Key, class _Tp, class _Compare, class _Allocator>
1403 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1404 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1406 if (__a != __m.get_allocator())
1408 const_iterator __e = cend();
1409 while (!__m.empty())
1410 __tree_.__insert_unique(__e.__i_,
1411 __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
1415 template <class _Key, class _Tp, class _Compare, class _Allocator>
1417 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1419 return __tree_.__emplace_unique_key_args(__k,
1420 _VSTD::piecewise_construct,
1421 _VSTD::forward_as_tuple(__k),
1422 _VSTD::forward_as_tuple()).first->__get_value().second;
1425 template <class _Key, class _Tp, class _Compare, class _Allocator>
1427 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1429 return __tree_.__emplace_unique_key_args(__k,
1430 _VSTD::piecewise_construct,
1431 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1432 _VSTD::forward_as_tuple()).first->__get_value().second;
1435 #else // _LIBCPP_CXX03_LANG
1437 template <class _Key, class _Tp, class _Compare, class _Allocator>
1438 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1439 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1441 __node_allocator& __na = __tree_.__node_alloc();
1442 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1443 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
1444 __h.get_deleter().__first_constructed = true;
1445 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
1446 __h.get_deleter().__second_constructed = true;
1447 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
1450 template <class _Key, class _Tp, class _Compare, class _Allocator>
1452 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1454 __parent_pointer __parent;
1455 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1456 __node_pointer __r = static_cast<__node_pointer>(__child);
1457 if (__child == nullptr)
1459 __node_holder __h = __construct_node_with_key(__k);
1460 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1461 __r = __h.release();
1463 return __r->__value_.__get_value().second;
1466 #endif // _LIBCPP_CXX03_LANG
1468 template <class _Key, class _Tp, class _Compare, class _Allocator>
1470 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1472 __parent_pointer __parent;
1473 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1474 #ifndef _LIBCPP_NO_EXCEPTIONS
1475 if (__child == nullptr)
1476 throw out_of_range("map::at: key not found");
1477 #endif // _LIBCPP_NO_EXCEPTIONS
1478 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1481 template <class _Key, class _Tp, class _Compare, class _Allocator>
1483 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1485 __parent_pointer __parent;
1486 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1487 #ifndef _LIBCPP_NO_EXCEPTIONS
1488 if (__child == nullptr)
1489 throw out_of_range("map::at: key not found");
1490 #endif // _LIBCPP_NO_EXCEPTIONS
1491 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1495 template <class _Key, class _Tp, class _Compare, class _Allocator>
1496 inline _LIBCPP_INLINE_VISIBILITY
1498 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1499 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1501 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1504 template <class _Key, class _Tp, class _Compare, class _Allocator>
1505 inline _LIBCPP_INLINE_VISIBILITY
1507 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1508 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1510 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1513 template <class _Key, class _Tp, class _Compare, class _Allocator>
1514 inline _LIBCPP_INLINE_VISIBILITY
1516 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1517 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1519 return !(__x == __y);
1522 template <class _Key, class _Tp, class _Compare, class _Allocator>
1523 inline _LIBCPP_INLINE_VISIBILITY
1525 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1526 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1531 template <class _Key, class _Tp, class _Compare, class _Allocator>
1532 inline _LIBCPP_INLINE_VISIBILITY
1534 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1535 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1537 return !(__x < __y);
1540 template <class _Key, class _Tp, class _Compare, class _Allocator>
1541 inline _LIBCPP_INLINE_VISIBILITY
1543 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1544 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1546 return !(__y < __x);
1549 template <class _Key, class _Tp, class _Compare, class _Allocator>
1550 inline _LIBCPP_INLINE_VISIBILITY
1552 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1553 map<_Key, _Tp, _Compare, _Allocator>& __y)
1554 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1559 template <class _Key, class _Tp, class _Compare = less<_Key>,
1560 class _Allocator = allocator<pair<const _Key, _Tp> > >
1561 class _LIBCPP_TEMPLATE_VIS multimap
1565 typedef _Key key_type;
1566 typedef _Tp mapped_type;
1567 typedef pair<const key_type, mapped_type> value_type;
1568 typedef _Compare key_compare;
1569 typedef _Allocator allocator_type;
1570 typedef value_type& reference;
1571 typedef const value_type& const_reference;
1573 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1574 "Allocator::value_type must be same type as value_type");
1576 class _LIBCPP_TEMPLATE_VIS value_compare
1577 : public binary_function<value_type, value_type, bool>
1579 friend class multimap;
1583 _LIBCPP_INLINE_VISIBILITY
1584 value_compare(key_compare c) : comp(c) {}
1586 _LIBCPP_INLINE_VISIBILITY
1587 bool operator()(const value_type& __x, const value_type& __y) const
1588 {return comp(__x.first, __y.first);}
1593 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
1594 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1595 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1596 __value_type>::type __allocator_type;
1597 typedef __tree<__value_type, __vc, __allocator_type> __base;
1598 typedef typename __base::__node_traits __node_traits;
1599 typedef allocator_traits<allocator_type> __alloc_traits;
1604 typedef typename __alloc_traits::pointer pointer;
1605 typedef typename __alloc_traits::const_pointer const_pointer;
1606 typedef typename __alloc_traits::size_type size_type;
1607 typedef typename __alloc_traits::difference_type difference_type;
1608 typedef __map_iterator<typename __base::iterator> iterator;
1609 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1610 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1611 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1613 #if _LIBCPP_STD_VER > 14
1614 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1617 _LIBCPP_INLINE_VISIBILITY
1620 is_nothrow_default_constructible<allocator_type>::value &&
1621 is_nothrow_default_constructible<key_compare>::value &&
1622 is_nothrow_copy_constructible<key_compare>::value)
1623 : __tree_(__vc(key_compare())) {}
1625 _LIBCPP_INLINE_VISIBILITY
1626 explicit multimap(const key_compare& __comp)
1628 is_nothrow_default_constructible<allocator_type>::value &&
1629 is_nothrow_copy_constructible<key_compare>::value)
1630 : __tree_(__vc(__comp)) {}
1632 _LIBCPP_INLINE_VISIBILITY
1633 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1634 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1636 template <class _InputIterator>
1637 _LIBCPP_INLINE_VISIBILITY
1638 multimap(_InputIterator __f, _InputIterator __l,
1639 const key_compare& __comp = key_compare())
1640 : __tree_(__vc(__comp))
1645 template <class _InputIterator>
1646 _LIBCPP_INLINE_VISIBILITY
1647 multimap(_InputIterator __f, _InputIterator __l,
1648 const key_compare& __comp, const allocator_type& __a)
1649 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1654 #if _LIBCPP_STD_VER > 11
1655 template <class _InputIterator>
1656 _LIBCPP_INLINE_VISIBILITY
1657 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1658 : multimap(__f, __l, key_compare(), __a) {}
1661 _LIBCPP_INLINE_VISIBILITY
1662 multimap(const multimap& __m)
1663 : __tree_(__m.__tree_.value_comp(),
1664 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1666 insert(__m.begin(), __m.end());
1669 _LIBCPP_INLINE_VISIBILITY
1670 multimap& operator=(const multimap& __m)
1672 #ifndef _LIBCPP_CXX03_LANG
1673 __tree_ = __m.__tree_;
1677 __tree_.value_comp() = __m.__tree_.value_comp();
1678 __tree_.__copy_assign_alloc(__m.__tree_);
1679 insert(__m.begin(), __m.end());
1685 #ifndef _LIBCPP_CXX03_LANG
1687 _LIBCPP_INLINE_VISIBILITY
1688 multimap(multimap&& __m)
1689 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1690 : __tree_(_VSTD::move(__m.__tree_))
1694 multimap(multimap&& __m, const allocator_type& __a);
1696 _LIBCPP_INLINE_VISIBILITY
1697 multimap& operator=(multimap&& __m)
1698 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1700 __tree_ = _VSTD::move(__m.__tree_);
1704 _LIBCPP_INLINE_VISIBILITY
1705 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1706 : __tree_(__vc(__comp))
1708 insert(__il.begin(), __il.end());
1711 _LIBCPP_INLINE_VISIBILITY
1712 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1713 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1715 insert(__il.begin(), __il.end());
1718 #if _LIBCPP_STD_VER > 11
1719 _LIBCPP_INLINE_VISIBILITY
1720 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1721 : multimap(__il, key_compare(), __a) {}
1724 _LIBCPP_INLINE_VISIBILITY
1725 multimap& operator=(initializer_list<value_type> __il)
1727 __tree_.__assign_multi(__il.begin(), __il.end());
1731 #endif // _LIBCPP_CXX03_LANG
1733 _LIBCPP_INLINE_VISIBILITY
1734 explicit multimap(const allocator_type& __a)
1735 : __tree_(typename __base::allocator_type(__a))
1739 _LIBCPP_INLINE_VISIBILITY
1740 multimap(const multimap& __m, const allocator_type& __a)
1741 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1743 insert(__m.begin(), __m.end());
1746 _LIBCPP_INLINE_VISIBILITY
1747 iterator begin() _NOEXCEPT {return __tree_.begin();}
1748 _LIBCPP_INLINE_VISIBILITY
1749 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1750 _LIBCPP_INLINE_VISIBILITY
1751 iterator end() _NOEXCEPT {return __tree_.end();}
1752 _LIBCPP_INLINE_VISIBILITY
1753 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1755 _LIBCPP_INLINE_VISIBILITY
1756 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1757 _LIBCPP_INLINE_VISIBILITY
1758 const_reverse_iterator rbegin() const _NOEXCEPT
1759 {return const_reverse_iterator(end());}
1760 _LIBCPP_INLINE_VISIBILITY
1761 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1762 _LIBCPP_INLINE_VISIBILITY
1763 const_reverse_iterator rend() const _NOEXCEPT
1764 {return const_reverse_iterator(begin());}
1766 _LIBCPP_INLINE_VISIBILITY
1767 const_iterator cbegin() const _NOEXCEPT {return begin();}
1768 _LIBCPP_INLINE_VISIBILITY
1769 const_iterator cend() const _NOEXCEPT {return end();}
1770 _LIBCPP_INLINE_VISIBILITY
1771 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1772 _LIBCPP_INLINE_VISIBILITY
1773 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1775 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1776 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1777 _LIBCPP_INLINE_VISIBILITY
1778 size_type size() const _NOEXCEPT {return __tree_.size();}
1779 _LIBCPP_INLINE_VISIBILITY
1780 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1782 _LIBCPP_INLINE_VISIBILITY
1783 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1784 _LIBCPP_INLINE_VISIBILITY
1785 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1786 _LIBCPP_INLINE_VISIBILITY
1787 value_compare value_comp() const
1788 {return value_compare(__tree_.value_comp().key_comp());}
1790 #ifndef _LIBCPP_CXX03_LANG
1792 template <class ..._Args>
1793 _LIBCPP_INLINE_VISIBILITY
1794 iterator emplace(_Args&& ...__args) {
1795 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1798 template <class ..._Args>
1799 _LIBCPP_INLINE_VISIBILITY
1800 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1801 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1804 template <class _Pp,
1805 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1806 _LIBCPP_INLINE_VISIBILITY
1807 iterator insert(_Pp&& __p)
1808 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1810 template <class _Pp,
1811 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1812 _LIBCPP_INLINE_VISIBILITY
1813 iterator insert(const_iterator __pos, _Pp&& __p)
1814 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1816 _LIBCPP_INLINE_VISIBILITY
1817 iterator insert(value_type&& __v)
1818 {return __tree_.__insert_multi(_VSTD::move(__v));}
1820 _LIBCPP_INLINE_VISIBILITY
1821 iterator insert(const_iterator __p, value_type&& __v)
1822 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1825 _LIBCPP_INLINE_VISIBILITY
1826 void insert(initializer_list<value_type> __il)
1827 {insert(__il.begin(), __il.end());}
1829 #endif // _LIBCPP_CXX03_LANG
1831 _LIBCPP_INLINE_VISIBILITY
1832 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1834 _LIBCPP_INLINE_VISIBILITY
1835 iterator insert(const_iterator __p, const value_type& __v)
1836 {return __tree_.__insert_multi(__p.__i_, __v);}
1838 template <class _InputIterator>
1839 _LIBCPP_INLINE_VISIBILITY
1840 void insert(_InputIterator __f, _InputIterator __l)
1842 for (const_iterator __e = cend(); __f != __l; ++__f)
1843 __tree_.__insert_multi(__e.__i_, *__f);
1846 _LIBCPP_INLINE_VISIBILITY
1847 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1848 _LIBCPP_INLINE_VISIBILITY
1849 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1850 _LIBCPP_INLINE_VISIBILITY
1851 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1852 _LIBCPP_INLINE_VISIBILITY
1853 iterator erase(const_iterator __f, const_iterator __l)
1854 {return __tree_.erase(__f.__i_, __l.__i_);}
1856 #if _LIBCPP_STD_VER > 14
1857 _LIBCPP_INLINE_VISIBILITY
1858 iterator insert(node_type&& __nh)
1860 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1861 "node_type with incompatible allocator passed to multimap::insert()");
1862 return __tree_.template __node_handle_insert_multi<node_type>(
1865 _LIBCPP_INLINE_VISIBILITY
1866 iterator insert(const_iterator __hint, node_type&& __nh)
1868 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1869 "node_type with incompatible allocator passed to multimap::insert()");
1870 return __tree_.template __node_handle_insert_multi<node_type>(
1871 __hint.__i_, _VSTD::move(__nh));
1873 _LIBCPP_INLINE_VISIBILITY
1874 node_type extract(key_type const& __key)
1876 return __tree_.template __node_handle_extract<node_type>(__key);
1878 _LIBCPP_INLINE_VISIBILITY
1879 node_type extract(const_iterator __it)
1881 return __tree_.template __node_handle_extract<node_type>(
1886 _LIBCPP_INLINE_VISIBILITY
1887 void clear() {__tree_.clear();}
1889 _LIBCPP_INLINE_VISIBILITY
1890 void swap(multimap& __m)
1891 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1892 {__tree_.swap(__m.__tree_);}
1894 _LIBCPP_INLINE_VISIBILITY
1895 iterator find(const key_type& __k) {return __tree_.find(__k);}
1896 _LIBCPP_INLINE_VISIBILITY
1897 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1898 #if _LIBCPP_STD_VER > 11
1899 template <typename _K2>
1900 _LIBCPP_INLINE_VISIBILITY
1901 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1902 find(const _K2& __k) {return __tree_.find(__k);}
1903 template <typename _K2>
1904 _LIBCPP_INLINE_VISIBILITY
1905 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1906 find(const _K2& __k) const {return __tree_.find(__k);}
1909 _LIBCPP_INLINE_VISIBILITY
1910 size_type count(const key_type& __k) const
1911 {return __tree_.__count_multi(__k);}
1912 #if _LIBCPP_STD_VER > 11
1913 template <typename _K2>
1914 _LIBCPP_INLINE_VISIBILITY
1915 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1916 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
1918 _LIBCPP_INLINE_VISIBILITY
1919 iterator lower_bound(const key_type& __k)
1920 {return __tree_.lower_bound(__k);}
1921 _LIBCPP_INLINE_VISIBILITY
1922 const_iterator lower_bound(const key_type& __k) const
1923 {return __tree_.lower_bound(__k);}
1924 #if _LIBCPP_STD_VER > 11
1925 template <typename _K2>
1926 _LIBCPP_INLINE_VISIBILITY
1927 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1928 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1930 template <typename _K2>
1931 _LIBCPP_INLINE_VISIBILITY
1932 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1933 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1936 _LIBCPP_INLINE_VISIBILITY
1937 iterator upper_bound(const key_type& __k)
1938 {return __tree_.upper_bound(__k);}
1939 _LIBCPP_INLINE_VISIBILITY
1940 const_iterator upper_bound(const key_type& __k) const
1941 {return __tree_.upper_bound(__k);}
1942 #if _LIBCPP_STD_VER > 11
1943 template <typename _K2>
1944 _LIBCPP_INLINE_VISIBILITY
1945 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1946 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1947 template <typename _K2>
1948 _LIBCPP_INLINE_VISIBILITY
1949 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1950 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1953 _LIBCPP_INLINE_VISIBILITY
1954 pair<iterator,iterator> equal_range(const key_type& __k)
1955 {return __tree_.__equal_range_multi(__k);}
1956 _LIBCPP_INLINE_VISIBILITY
1957 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1958 {return __tree_.__equal_range_multi(__k);}
1959 #if _LIBCPP_STD_VER > 11
1960 template <typename _K2>
1961 _LIBCPP_INLINE_VISIBILITY
1962 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1963 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1964 template <typename _K2>
1965 _LIBCPP_INLINE_VISIBILITY
1966 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1967 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1971 typedef typename __base::__node __node;
1972 typedef typename __base::__node_allocator __node_allocator;
1973 typedef typename __base::__node_pointer __node_pointer;
1975 typedef __map_node_destructor<__node_allocator> _Dp;
1976 typedef unique_ptr<__node, _Dp> __node_holder;
1979 #ifndef _LIBCPP_CXX03_LANG
1980 template <class _Key, class _Tp, class _Compare, class _Allocator>
1981 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1982 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1984 if (__a != __m.get_allocator())
1986 const_iterator __e = cend();
1987 while (!__m.empty())
1988 __tree_.__insert_multi(__e.__i_,
1989 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
1994 template <class _Key, class _Tp, class _Compare, class _Allocator>
1995 inline _LIBCPP_INLINE_VISIBILITY
1997 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1998 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2000 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2003 template <class _Key, class _Tp, class _Compare, class _Allocator>
2004 inline _LIBCPP_INLINE_VISIBILITY
2006 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2007 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2009 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2012 template <class _Key, class _Tp, class _Compare, class _Allocator>
2013 inline _LIBCPP_INLINE_VISIBILITY
2015 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2016 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2018 return !(__x == __y);
2021 template <class _Key, class _Tp, class _Compare, class _Allocator>
2022 inline _LIBCPP_INLINE_VISIBILITY
2024 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2025 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2030 template <class _Key, class _Tp, class _Compare, class _Allocator>
2031 inline _LIBCPP_INLINE_VISIBILITY
2033 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2034 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2036 return !(__x < __y);
2039 template <class _Key, class _Tp, class _Compare, class _Allocator>
2040 inline _LIBCPP_INLINE_VISIBILITY
2042 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2043 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2045 return !(__y < __x);
2048 template <class _Key, class _Tp, class _Compare, class _Allocator>
2049 inline _LIBCPP_INLINE_VISIBILITY
2051 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2052 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2053 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2058 _LIBCPP_END_NAMESPACE_STD
2060 #endif // _LIBCPP_MAP