2 //===----------------------------- map ------------------------------------===//
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
8 //===----------------------------------------------------------------------===//
20 template <class Key, class T, class Compare = less<Key>,
21 class Allocator = allocator<pair<const Key, T>>>
27 typedef T mapped_type;
28 typedef pair<const key_type, mapped_type> value_type;
29 typedef Compare key_compare;
30 typedef Allocator allocator_type;
31 typedef typename allocator_type::reference reference;
32 typedef typename allocator_type::const_reference const_reference;
33 typedef typename allocator_type::pointer pointer;
34 typedef typename allocator_type::const_pointer const_pointer;
35 typedef typename allocator_type::size_type size_type;
36 typedef typename allocator_type::difference_type difference_type;
38 typedef implementation-defined iterator;
39 typedef implementation-defined const_iterator;
40 typedef std::reverse_iterator<iterator> reverse_iterator;
41 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
42 typedef unspecified node_type; // C++17
43 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
46 : public binary_function<value_type, value_type, bool>
52 value_compare(key_compare c);
54 bool operator()(const value_type& x, const value_type& y) const;
57 // construct/copy/destroy:
60 is_nothrow_default_constructible<allocator_type>::value &&
61 is_nothrow_default_constructible<key_compare>::value &&
62 is_nothrow_copy_constructible<key_compare>::value);
63 explicit map(const key_compare& comp);
64 map(const key_compare& comp, const allocator_type& a);
65 template <class InputIterator>
66 map(InputIterator first, InputIterator last,
67 const key_compare& comp = key_compare());
68 template <class InputIterator>
69 map(InputIterator first, InputIterator last,
70 const key_compare& comp, const allocator_type& a);
74 is_nothrow_move_constructible<allocator_type>::value &&
75 is_nothrow_move_constructible<key_compare>::value);
76 explicit map(const allocator_type& a);
77 map(const map& m, const allocator_type& a);
78 map(map&& m, const allocator_type& a);
79 map(initializer_list<value_type> il, const key_compare& comp = key_compare());
80 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
81 template <class InputIterator>
82 map(InputIterator first, InputIterator last, const allocator_type& a)
83 : map(first, last, Compare(), a) {} // C++14
84 map(initializer_list<value_type> il, const allocator_type& a)
85 : map(il, Compare(), a) {} // C++14
88 map& operator=(const map& m);
89 map& operator=(map&& m)
91 allocator_type::propagate_on_container_move_assignment::value &&
92 is_nothrow_move_assignable<allocator_type>::value &&
93 is_nothrow_move_assignable<key_compare>::value);
94 map& operator=(initializer_list<value_type> il);
97 iterator begin() noexcept;
98 const_iterator begin() const noexcept;
99 iterator end() noexcept;
100 const_iterator end() const noexcept;
102 reverse_iterator rbegin() noexcept;
103 const_reverse_iterator rbegin() const noexcept;
104 reverse_iterator rend() noexcept;
105 const_reverse_iterator rend() const noexcept;
107 const_iterator cbegin() const noexcept;
108 const_iterator cend() const noexcept;
109 const_reverse_iterator crbegin() const noexcept;
110 const_reverse_iterator crend() const noexcept;
113 bool empty() const noexcept;
114 size_type size() const noexcept;
115 size_type max_size() const noexcept;
118 mapped_type& operator[](const key_type& k);
119 mapped_type& operator[](key_type&& k);
121 mapped_type& at(const key_type& k);
122 const mapped_type& at(const key_type& k) const;
125 template <class... Args>
126 pair<iterator, bool> emplace(Args&&... args);
127 template <class... Args>
128 iterator emplace_hint(const_iterator position, Args&&... args);
129 pair<iterator, bool> insert(const value_type& v);
130 pair<iterator, bool> insert( value_type&& v); // C++17
132 pair<iterator, bool> insert(P&& p);
133 iterator insert(const_iterator position, const value_type& v);
134 iterator insert(const_iterator position, value_type&& v); // C++17
136 iterator insert(const_iterator position, P&& p);
137 template <class InputIterator>
138 void insert(InputIterator first, InputIterator last);
139 void insert(initializer_list<value_type> il);
141 node_type extract(const_iterator position); // C++17
142 node_type extract(const key_type& x); // C++17
143 insert_return_type insert(node_type&& nh); // C++17
144 iterator insert(const_iterator hint, node_type&& nh); // C++17
146 template <class... Args>
147 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
148 template <class... Args>
149 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
150 template <class... Args>
151 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
152 template <class... Args>
153 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
155 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
157 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
159 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
161 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
163 iterator erase(const_iterator position);
164 iterator erase(iterator position); // C++14
165 size_type erase(const key_type& k);
166 iterator erase(const_iterator first, const_iterator last);
167 void clear() noexcept;
170 void merge(map<Key, T, C2, Allocator>& source); // C++17
172 void merge(map<Key, T, C2, Allocator>&& source); // C++17
174 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
176 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
179 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
180 is_nothrow_swappable<key_compare>::value); // C++17
183 allocator_type get_allocator() const noexcept;
184 key_compare key_comp() const;
185 value_compare value_comp() const;
188 iterator find(const key_type& k);
189 const_iterator find(const key_type& k) const;
191 iterator find(const K& x); // C++14
193 const_iterator find(const K& x) const; // C++14
195 size_type count(const K& x) const; // C++14
196 size_type count(const key_type& k) const;
197 bool contains(const key_type& x) const; // C++20
198 iterator lower_bound(const key_type& k);
199 const_iterator lower_bound(const key_type& k) const;
201 iterator lower_bound(const K& x); // C++14
203 const_iterator lower_bound(const K& x) const; // C++14
205 iterator upper_bound(const key_type& k);
206 const_iterator upper_bound(const key_type& k) const;
208 iterator upper_bound(const K& x); // C++14
210 const_iterator upper_bound(const K& x) const; // C++14
212 pair<iterator,iterator> equal_range(const key_type& k);
213 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
215 pair<iterator,iterator> equal_range(const K& x); // C++14
217 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
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 template <class Key, class T, class Compare, class Allocator>
237 operator> (const map<Key, T, Compare, Allocator>& x,
238 const map<Key, T, Compare, Allocator>& y);
240 template <class Key, class T, class Compare, class Allocator>
242 operator>=(const map<Key, T, Compare, Allocator>& x,
243 const map<Key, T, Compare, Allocator>& y);
245 template <class Key, class T, class Compare, class Allocator>
247 operator<=(const map<Key, T, Compare, Allocator>& x,
248 const map<Key, T, Compare, Allocator>& y);
250 // specialized algorithms:
251 template <class Key, class T, class Compare, class Allocator>
253 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
254 noexcept(noexcept(x.swap(y)));
256 template <class Key, class T, class Compare, class Allocator, class Predicate>
257 void erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
260 template <class Key, class T, class Compare = less<Key>,
261 class Allocator = allocator<pair<const Key, T>>>
266 typedef Key key_type;
267 typedef T mapped_type;
268 typedef pair<const key_type,mapped_type> value_type;
269 typedef Compare key_compare;
270 typedef Allocator allocator_type;
271 typedef typename allocator_type::reference reference;
272 typedef typename allocator_type::const_reference const_reference;
273 typedef typename allocator_type::size_type size_type;
274 typedef typename allocator_type::difference_type difference_type;
275 typedef typename allocator_type::pointer pointer;
276 typedef typename allocator_type::const_pointer const_pointer;
278 typedef implementation-defined iterator;
279 typedef implementation-defined const_iterator;
280 typedef std::reverse_iterator<iterator> reverse_iterator;
281 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
282 typedef unspecified node_type; // C++17
285 : public binary_function<value_type,value_type,bool>
287 friend class multimap;
290 value_compare(key_compare c);
292 bool operator()(const value_type& x, const value_type& y) const;
295 // construct/copy/destroy:
298 is_nothrow_default_constructible<allocator_type>::value &&
299 is_nothrow_default_constructible<key_compare>::value &&
300 is_nothrow_copy_constructible<key_compare>::value);
301 explicit multimap(const key_compare& comp);
302 multimap(const key_compare& comp, const allocator_type& a);
303 template <class InputIterator>
304 multimap(InputIterator first, InputIterator last, const key_compare& comp);
305 template <class InputIterator>
306 multimap(InputIterator first, InputIterator last, const key_compare& comp,
307 const allocator_type& a);
308 multimap(const multimap& m);
309 multimap(multimap&& m)
311 is_nothrow_move_constructible<allocator_type>::value &&
312 is_nothrow_move_constructible<key_compare>::value);
313 explicit multimap(const allocator_type& a);
314 multimap(const multimap& m, const allocator_type& a);
315 multimap(multimap&& m, const allocator_type& a);
316 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
317 multimap(initializer_list<value_type> il, const key_compare& comp,
318 const allocator_type& a);
319 template <class InputIterator>
320 multimap(InputIterator first, InputIterator last, const allocator_type& a)
321 : multimap(first, last, Compare(), a) {} // C++14
322 multimap(initializer_list<value_type> il, const allocator_type& a)
323 : multimap(il, Compare(), a) {} // C++14
326 multimap& operator=(const multimap& m);
327 multimap& operator=(multimap&& m)
329 allocator_type::propagate_on_container_move_assignment::value &&
330 is_nothrow_move_assignable<allocator_type>::value &&
331 is_nothrow_move_assignable<key_compare>::value);
332 multimap& operator=(initializer_list<value_type> il);
335 iterator begin() noexcept;
336 const_iterator begin() const noexcept;
337 iterator end() noexcept;
338 const_iterator end() const noexcept;
340 reverse_iterator rbegin() noexcept;
341 const_reverse_iterator rbegin() const noexcept;
342 reverse_iterator rend() noexcept;
343 const_reverse_iterator rend() const noexcept;
345 const_iterator cbegin() const noexcept;
346 const_iterator cend() const noexcept;
347 const_reverse_iterator crbegin() const noexcept;
348 const_reverse_iterator crend() const noexcept;
351 bool empty() const noexcept;
352 size_type size() const noexcept;
353 size_type max_size() const noexcept;
356 template <class... Args>
357 iterator emplace(Args&&... args);
358 template <class... Args>
359 iterator emplace_hint(const_iterator position, Args&&... args);
360 iterator insert(const value_type& v);
361 iterator insert( value_type&& v); // C++17
363 iterator insert(P&& p);
364 iterator insert(const_iterator position, const value_type& v);
365 iterator insert(const_iterator position, value_type&& v); // C++17
367 iterator insert(const_iterator position, P&& p);
368 template <class InputIterator>
369 void insert(InputIterator first, InputIterator last);
370 void insert(initializer_list<value_type> il);
372 node_type extract(const_iterator position); // C++17
373 node_type extract(const key_type& x); // C++17
374 iterator insert(node_type&& nh); // C++17
375 iterator insert(const_iterator hint, node_type&& nh); // C++17
377 iterator erase(const_iterator position);
378 iterator erase(iterator position); // C++14
379 size_type erase(const key_type& k);
380 iterator erase(const_iterator first, const_iterator last);
381 void clear() noexcept;
384 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
386 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
388 void merge(map<Key, T, C2, Allocator>& source); // C++17
390 void merge(map<Key, T, C2, Allocator>&& source); // C++17
392 void swap(multimap& m)
393 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
394 is_nothrow_swappable<key_compare>::value); // C++17
397 allocator_type get_allocator() const noexcept;
398 key_compare key_comp() const;
399 value_compare value_comp() const;
402 iterator find(const key_type& k);
403 const_iterator find(const key_type& k) const;
405 iterator find(const K& x); // C++14
407 const_iterator find(const K& x) const; // C++14
409 size_type count(const K& x) const; // C++14
410 size_type count(const key_type& k) const;
411 bool contains(const key_type& x) const; // C++20
412 iterator lower_bound(const key_type& k);
413 const_iterator lower_bound(const key_type& k) const;
415 iterator lower_bound(const K& x); // C++14
417 const_iterator lower_bound(const K& x) const; // C++14
419 iterator upper_bound(const key_type& k);
420 const_iterator upper_bound(const key_type& k) const;
422 iterator upper_bound(const K& x); // C++14
424 const_iterator upper_bound(const K& x) const; // C++14
426 pair<iterator,iterator> equal_range(const key_type& k);
427 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
429 pair<iterator,iterator> equal_range(const K& x); // C++14
431 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
434 template <class Key, class T, class Compare, class Allocator>
436 operator==(const multimap<Key, T, Compare, Allocator>& x,
437 const multimap<Key, T, Compare, Allocator>& y);
439 template <class Key, class T, class Compare, class Allocator>
441 operator< (const multimap<Key, T, Compare, Allocator>& x,
442 const multimap<Key, T, Compare, Allocator>& y);
444 template <class Key, class T, class Compare, class Allocator>
446 operator!=(const multimap<Key, T, Compare, Allocator>& x,
447 const multimap<Key, T, Compare, Allocator>& y);
449 template <class Key, class T, class Compare, class Allocator>
451 operator> (const multimap<Key, T, Compare, Allocator>& x,
452 const multimap<Key, T, Compare, Allocator>& y);
454 template <class Key, class T, class Compare, class Allocator>
456 operator>=(const multimap<Key, T, Compare, Allocator>& x,
457 const multimap<Key, T, Compare, Allocator>& y);
459 template <class Key, class T, class Compare, class Allocator>
461 operator<=(const multimap<Key, T, Compare, Allocator>& x,
462 const multimap<Key, T, Compare, Allocator>& y);
464 // specialized algorithms:
465 template <class Key, class T, class Compare, class Allocator>
467 swap(multimap<Key, T, Compare, Allocator>& x,
468 multimap<Key, T, Compare, Allocator>& y)
469 noexcept(noexcept(x.swap(y)));
471 template <class Key, class T, class Compare, class Allocator, class Predicate>
472 void erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
480 #include <__node_handle>
484 #include <functional>
485 #include <initializer_list>
486 #include <type_traits>
489 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
490 #pragma GCC system_header
493 _LIBCPP_BEGIN_NAMESPACE_STD
495 template <class _Key, class _CP, class _Compare,
496 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
497 class __map_value_compare
501 _LIBCPP_INLINE_VISIBILITY
502 __map_value_compare()
503 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
505 _LIBCPP_INLINE_VISIBILITY
506 __map_value_compare(_Compare c)
507 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
509 _LIBCPP_INLINE_VISIBILITY
510 const _Compare& key_comp() const _NOEXCEPT {return *this;}
511 _LIBCPP_INLINE_VISIBILITY
512 bool operator()(const _CP& __x, const _CP& __y) const
513 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);}
514 _LIBCPP_INLINE_VISIBILITY
515 bool operator()(const _CP& __x, const _Key& __y) const
516 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);}
517 _LIBCPP_INLINE_VISIBILITY
518 bool operator()(const _Key& __x, const _CP& __y) const
519 {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);}
520 void swap(__map_value_compare&__y)
521 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
524 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
527 #if _LIBCPP_STD_VER > 11
528 template <typename _K2>
529 _LIBCPP_INLINE_VISIBILITY
530 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
531 operator () ( const _K2& __x, const _CP& __y ) const
532 {return static_cast<const _Compare&>(*this) (__x, __y.__get_value().first);}
534 template <typename _K2>
535 _LIBCPP_INLINE_VISIBILITY
536 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
537 operator () (const _CP& __x, const _K2& __y) const
538 {return static_cast<const _Compare&>(*this) (__x.__get_value().first, __y);}
542 template <class _Key, class _CP, class _Compare>
543 class __map_value_compare<_Key, _CP, _Compare, false>
548 _LIBCPP_INLINE_VISIBILITY
549 __map_value_compare()
550 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
552 _LIBCPP_INLINE_VISIBILITY
553 __map_value_compare(_Compare c)
554 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
556 _LIBCPP_INLINE_VISIBILITY
557 const _Compare& key_comp() const _NOEXCEPT {return comp;}
559 _LIBCPP_INLINE_VISIBILITY
560 bool operator()(const _CP& __x, const _CP& __y) const
561 {return comp(__x.__get_value().first, __y.__get_value().first);}
562 _LIBCPP_INLINE_VISIBILITY
563 bool operator()(const _CP& __x, const _Key& __y) const
564 {return comp(__x.__get_value().first, __y);}
565 _LIBCPP_INLINE_VISIBILITY
566 bool operator()(const _Key& __x, const _CP& __y) const
567 {return comp(__x, __y.__get_value().first);}
568 void swap(__map_value_compare&__y)
569 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
572 swap(comp, __y.comp);
575 #if _LIBCPP_STD_VER > 11
576 template <typename _K2>
577 _LIBCPP_INLINE_VISIBILITY
578 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
579 operator () ( const _K2& __x, const _CP& __y ) const
580 {return comp (__x, __y.__get_value().first);}
582 template <typename _K2>
583 _LIBCPP_INLINE_VISIBILITY
584 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
585 operator () (const _CP& __x, const _K2& __y) const
586 {return comp (__x.__get_value().first, __y);}
590 template <class _Key, class _CP, class _Compare, bool __b>
591 inline _LIBCPP_INLINE_VISIBILITY
593 swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
594 __map_value_compare<_Key, _CP, _Compare, __b>& __y)
595 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
600 template <class _Allocator>
601 class __map_node_destructor
603 typedef _Allocator allocator_type;
604 typedef allocator_traits<allocator_type> __alloc_traits;
607 typedef typename __alloc_traits::pointer pointer;
610 allocator_type& __na_;
612 __map_node_destructor& operator=(const __map_node_destructor&);
615 bool __first_constructed;
616 bool __second_constructed;
618 _LIBCPP_INLINE_VISIBILITY
619 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
621 __first_constructed(false),
622 __second_constructed(false)
625 #ifndef _LIBCPP_CXX03_LANG
626 _LIBCPP_INLINE_VISIBILITY
627 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
629 __first_constructed(__x.__value_constructed),
630 __second_constructed(__x.__value_constructed)
632 __x.__value_constructed = false;
634 #endif // _LIBCPP_CXX03_LANG
636 _LIBCPP_INLINE_VISIBILITY
637 void operator()(pointer __p) _NOEXCEPT
639 if (__second_constructed)
640 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
641 if (__first_constructed)
642 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
644 __alloc_traits::deallocate(__na_, __p, 1);
648 template <class _Key, class _Tp, class _Compare, class _Allocator>
650 template <class _Key, class _Tp, class _Compare, class _Allocator>
652 template <class _TreeIterator> class __map_const_iterator;
654 #ifndef _LIBCPP_CXX03_LANG
656 template <class _Key, class _Tp>
659 typedef _Key key_type;
660 typedef _Tp mapped_type;
661 typedef pair<const key_type, mapped_type> value_type;
662 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
663 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
669 _LIBCPP_INLINE_VISIBILITY
670 value_type& __get_value()
672 #if _LIBCPP_STD_VER > 14
673 return *_VSTD::launder(_VSTD::addressof(__cc));
679 _LIBCPP_INLINE_VISIBILITY
680 const value_type& __get_value() const
682 #if _LIBCPP_STD_VER > 14
683 return *_VSTD::launder(_VSTD::addressof(__cc));
689 _LIBCPP_INLINE_VISIBILITY
690 __nc_ref_pair_type __ref()
692 value_type& __v = __get_value();
693 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
696 _LIBCPP_INLINE_VISIBILITY
697 __nc_rref_pair_type __move()
699 value_type& __v = __get_value();
700 return __nc_rref_pair_type(
701 _VSTD::move(const_cast<key_type&>(__v.first)),
702 _VSTD::move(__v.second));
705 _LIBCPP_INLINE_VISIBILITY
706 __value_type& operator=(const __value_type& __v)
708 __ref() = __v.__get_value();
712 _LIBCPP_INLINE_VISIBILITY
713 __value_type& operator=(__value_type&& __v)
715 __ref() = __v.__move();
719 template <class _ValueTp,
720 class = typename enable_if<
721 __is_same_uncvref<_ValueTp, value_type>::value
724 _LIBCPP_INLINE_VISIBILITY
725 __value_type& operator=(_ValueTp&& __v)
727 __ref() = _VSTD::forward<_ValueTp>(__v);
732 __value_type() _LIBCPP_EQUAL_DELETE;
733 ~__value_type() _LIBCPP_EQUAL_DELETE;
734 __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
735 __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
740 template <class _Key, class _Tp>
743 typedef _Key key_type;
744 typedef _Tp mapped_type;
745 typedef pair<const key_type, mapped_type> value_type;
751 _LIBCPP_INLINE_VISIBILITY
752 value_type& __get_value() { return __cc; }
753 _LIBCPP_INLINE_VISIBILITY
754 const value_type& __get_value() const { return __cc; }
758 __value_type(__value_type const&);
759 __value_type& operator=(__value_type const&);
763 #endif // _LIBCPP_CXX03_LANG
766 struct __extract_key_value_types;
768 template <class _Key, class _Tp>
769 struct __extract_key_value_types<__value_type<_Key, _Tp> >
771 typedef _Key const __key_type;
772 typedef _Tp __mapped_type;
775 template <class _TreeIterator>
776 class _LIBCPP_TEMPLATE_VIS __map_iterator
778 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
779 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
784 typedef bidirectional_iterator_tag iterator_category;
785 typedef typename _NodeTypes::__map_value_type value_type;
786 typedef typename _TreeIterator::difference_type difference_type;
787 typedef value_type& reference;
788 typedef typename _NodeTypes::__map_value_type_pointer pointer;
790 _LIBCPP_INLINE_VISIBILITY
791 __map_iterator() _NOEXCEPT {}
793 _LIBCPP_INLINE_VISIBILITY
794 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
796 _LIBCPP_INLINE_VISIBILITY
797 reference operator*() const {return __i_->__get_value();}
798 _LIBCPP_INLINE_VISIBILITY
799 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
801 _LIBCPP_INLINE_VISIBILITY
802 __map_iterator& operator++() {++__i_; return *this;}
803 _LIBCPP_INLINE_VISIBILITY
804 __map_iterator operator++(int)
806 __map_iterator __t(*this);
811 _LIBCPP_INLINE_VISIBILITY
812 __map_iterator& operator--() {--__i_; return *this;}
813 _LIBCPP_INLINE_VISIBILITY
814 __map_iterator operator--(int)
816 __map_iterator __t(*this);
821 friend _LIBCPP_INLINE_VISIBILITY
822 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
823 {return __x.__i_ == __y.__i_;}
825 _LIBCPP_INLINE_VISIBILITY
826 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
827 {return __x.__i_ != __y.__i_;}
829 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
830 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
831 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
834 template <class _TreeIterator>
835 class _LIBCPP_TEMPLATE_VIS __map_const_iterator
837 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
838 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
843 typedef bidirectional_iterator_tag iterator_category;
844 typedef typename _NodeTypes::__map_value_type value_type;
845 typedef typename _TreeIterator::difference_type difference_type;
846 typedef const value_type& reference;
847 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
849 _LIBCPP_INLINE_VISIBILITY
850 __map_const_iterator() _NOEXCEPT {}
852 _LIBCPP_INLINE_VISIBILITY
853 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
854 _LIBCPP_INLINE_VISIBILITY
855 __map_const_iterator(__map_iterator<
856 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
859 _LIBCPP_INLINE_VISIBILITY
860 reference operator*() const {return __i_->__get_value();}
861 _LIBCPP_INLINE_VISIBILITY
862 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
864 _LIBCPP_INLINE_VISIBILITY
865 __map_const_iterator& operator++() {++__i_; return *this;}
866 _LIBCPP_INLINE_VISIBILITY
867 __map_const_iterator operator++(int)
869 __map_const_iterator __t(*this);
874 _LIBCPP_INLINE_VISIBILITY
875 __map_const_iterator& operator--() {--__i_; return *this;}
876 _LIBCPP_INLINE_VISIBILITY
877 __map_const_iterator operator--(int)
879 __map_const_iterator __t(*this);
884 friend _LIBCPP_INLINE_VISIBILITY
885 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
886 {return __x.__i_ == __y.__i_;}
887 friend _LIBCPP_INLINE_VISIBILITY
888 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
889 {return __x.__i_ != __y.__i_;}
891 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
892 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
893 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
896 template <class _Key, class _Tp, class _Compare = less<_Key>,
897 class _Allocator = allocator<pair<const _Key, _Tp> > >
898 class _LIBCPP_TEMPLATE_VIS map
902 typedef _Key key_type;
903 typedef _Tp mapped_type;
904 typedef pair<const key_type, mapped_type> value_type;
905 typedef typename __identity<_Compare>::type key_compare;
906 typedef typename __identity<_Allocator>::type allocator_type;
907 typedef value_type& reference;
908 typedef const value_type& const_reference;
910 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
911 "Allocator::value_type must be same type as value_type");
913 class _LIBCPP_TEMPLATE_VIS value_compare
914 : public binary_function<value_type, value_type, bool>
920 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
922 _LIBCPP_INLINE_VISIBILITY
923 bool operator()(const value_type& __x, const value_type& __y) const
924 {return comp(__x.first, __y.first);}
929 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
930 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
931 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
932 __value_type>::type __allocator_type;
933 typedef __tree<__value_type, __vc, __allocator_type> __base;
934 typedef typename __base::__node_traits __node_traits;
935 typedef allocator_traits<allocator_type> __alloc_traits;
940 typedef typename __alloc_traits::pointer pointer;
941 typedef typename __alloc_traits::const_pointer const_pointer;
942 typedef typename __alloc_traits::size_type size_type;
943 typedef typename __alloc_traits::difference_type difference_type;
944 typedef __map_iterator<typename __base::iterator> iterator;
945 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
946 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
947 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
949 #if _LIBCPP_STD_VER > 14
950 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
951 typedef __insert_return_type<iterator, node_type> insert_return_type;
954 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
955 friend class _LIBCPP_TEMPLATE_VIS map;
956 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
957 friend class _LIBCPP_TEMPLATE_VIS multimap;
959 _LIBCPP_INLINE_VISIBILITY
962 is_nothrow_default_constructible<allocator_type>::value &&
963 is_nothrow_default_constructible<key_compare>::value &&
964 is_nothrow_copy_constructible<key_compare>::value)
965 : __tree_(__vc(key_compare())) {}
967 _LIBCPP_INLINE_VISIBILITY
968 explicit map(const key_compare& __comp)
970 is_nothrow_default_constructible<allocator_type>::value &&
971 is_nothrow_copy_constructible<key_compare>::value)
972 : __tree_(__vc(__comp)) {}
974 _LIBCPP_INLINE_VISIBILITY
975 explicit map(const key_compare& __comp, const allocator_type& __a)
976 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
978 template <class _InputIterator>
979 _LIBCPP_INLINE_VISIBILITY
980 map(_InputIterator __f, _InputIterator __l,
981 const key_compare& __comp = key_compare())
982 : __tree_(__vc(__comp))
987 template <class _InputIterator>
988 _LIBCPP_INLINE_VISIBILITY
989 map(_InputIterator __f, _InputIterator __l,
990 const key_compare& __comp, const allocator_type& __a)
991 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
996 #if _LIBCPP_STD_VER > 11
997 template <class _InputIterator>
998 _LIBCPP_INLINE_VISIBILITY
999 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1000 : map(__f, __l, key_compare(), __a) {}
1003 _LIBCPP_INLINE_VISIBILITY
1005 : __tree_(__m.__tree_)
1007 insert(__m.begin(), __m.end());
1010 _LIBCPP_INLINE_VISIBILITY
1011 map& operator=(const map& __m)
1013 #ifndef _LIBCPP_CXX03_LANG
1014 __tree_ = __m.__tree_;
1018 __tree_.value_comp() = __m.__tree_.value_comp();
1019 __tree_.__copy_assign_alloc(__m.__tree_);
1020 insert(__m.begin(), __m.end());
1026 #ifndef _LIBCPP_CXX03_LANG
1028 _LIBCPP_INLINE_VISIBILITY
1030 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1031 : __tree_(_VSTD::move(__m.__tree_))
1035 map(map&& __m, const allocator_type& __a);
1037 _LIBCPP_INLINE_VISIBILITY
1038 map& operator=(map&& __m)
1039 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1041 __tree_ = _VSTD::move(__m.__tree_);
1045 _LIBCPP_INLINE_VISIBILITY
1046 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1047 : __tree_(__vc(__comp))
1049 insert(__il.begin(), __il.end());
1052 _LIBCPP_INLINE_VISIBILITY
1053 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1054 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1056 insert(__il.begin(), __il.end());
1059 #if _LIBCPP_STD_VER > 11
1060 _LIBCPP_INLINE_VISIBILITY
1061 map(initializer_list<value_type> __il, const allocator_type& __a)
1062 : map(__il, key_compare(), __a) {}
1065 _LIBCPP_INLINE_VISIBILITY
1066 map& operator=(initializer_list<value_type> __il)
1068 __tree_.__assign_unique(__il.begin(), __il.end());
1072 #endif // _LIBCPP_CXX03_LANG
1074 _LIBCPP_INLINE_VISIBILITY
1075 explicit map(const allocator_type& __a)
1076 : __tree_(typename __base::allocator_type(__a))
1080 _LIBCPP_INLINE_VISIBILITY
1081 map(const map& __m, const allocator_type& __a)
1082 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1084 insert(__m.begin(), __m.end());
1087 _LIBCPP_INLINE_VISIBILITY
1089 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1092 _LIBCPP_INLINE_VISIBILITY
1093 iterator begin() _NOEXCEPT {return __tree_.begin();}
1094 _LIBCPP_INLINE_VISIBILITY
1095 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1096 _LIBCPP_INLINE_VISIBILITY
1097 iterator end() _NOEXCEPT {return __tree_.end();}
1098 _LIBCPP_INLINE_VISIBILITY
1099 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1101 _LIBCPP_INLINE_VISIBILITY
1102 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1103 _LIBCPP_INLINE_VISIBILITY
1104 const_reverse_iterator rbegin() const _NOEXCEPT
1105 {return const_reverse_iterator(end());}
1106 _LIBCPP_INLINE_VISIBILITY
1107 reverse_iterator rend() _NOEXCEPT
1108 {return reverse_iterator(begin());}
1109 _LIBCPP_INLINE_VISIBILITY
1110 const_reverse_iterator rend() const _NOEXCEPT
1111 {return const_reverse_iterator(begin());}
1113 _LIBCPP_INLINE_VISIBILITY
1114 const_iterator cbegin() const _NOEXCEPT {return begin();}
1115 _LIBCPP_INLINE_VISIBILITY
1116 const_iterator cend() const _NOEXCEPT {return end();}
1117 _LIBCPP_INLINE_VISIBILITY
1118 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1119 _LIBCPP_INLINE_VISIBILITY
1120 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1122 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1123 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1124 _LIBCPP_INLINE_VISIBILITY
1125 size_type size() const _NOEXCEPT {return __tree_.size();}
1126 _LIBCPP_INLINE_VISIBILITY
1127 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1129 mapped_type& operator[](const key_type& __k);
1130 #ifndef _LIBCPP_CXX03_LANG
1131 mapped_type& operator[](key_type&& __k);
1134 mapped_type& at(const key_type& __k);
1135 const mapped_type& at(const key_type& __k) const;
1137 _LIBCPP_INLINE_VISIBILITY
1138 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1139 _LIBCPP_INLINE_VISIBILITY
1140 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1141 _LIBCPP_INLINE_VISIBILITY
1142 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1144 #ifndef _LIBCPP_CXX03_LANG
1145 template <class ..._Args>
1146 _LIBCPP_INLINE_VISIBILITY
1147 pair<iterator, bool> emplace(_Args&& ...__args) {
1148 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1151 template <class ..._Args>
1152 _LIBCPP_INLINE_VISIBILITY
1153 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1154 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1157 template <class _Pp,
1158 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1159 _LIBCPP_INLINE_VISIBILITY
1160 pair<iterator, bool> insert(_Pp&& __p)
1161 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1163 template <class _Pp,
1164 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1165 _LIBCPP_INLINE_VISIBILITY
1166 iterator insert(const_iterator __pos, _Pp&& __p)
1167 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1169 #endif // _LIBCPP_CXX03_LANG
1171 _LIBCPP_INLINE_VISIBILITY
1172 pair<iterator, bool>
1173 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1175 _LIBCPP_INLINE_VISIBILITY
1177 insert(const_iterator __p, const value_type& __v)
1178 {return __tree_.__insert_unique(__p.__i_, __v);}
1180 #ifndef _LIBCPP_CXX03_LANG
1181 _LIBCPP_INLINE_VISIBILITY
1182 pair<iterator, bool>
1183 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
1185 _LIBCPP_INLINE_VISIBILITY
1186 iterator insert(const_iterator __p, value_type&& __v)
1187 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
1189 _LIBCPP_INLINE_VISIBILITY
1190 void insert(initializer_list<value_type> __il)
1191 {insert(__il.begin(), __il.end());}
1194 template <class _InputIterator>
1195 _LIBCPP_INLINE_VISIBILITY
1196 void insert(_InputIterator __f, _InputIterator __l)
1198 for (const_iterator __e = cend(); __f != __l; ++__f)
1199 insert(__e.__i_, *__f);
1202 #if _LIBCPP_STD_VER > 14
1204 template <class... _Args>
1205 _LIBCPP_INLINE_VISIBILITY
1206 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1208 return __tree_.__emplace_unique_key_args(__k,
1209 _VSTD::piecewise_construct,
1210 _VSTD::forward_as_tuple(__k),
1211 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1214 template <class... _Args>
1215 _LIBCPP_INLINE_VISIBILITY
1216 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1218 return __tree_.__emplace_unique_key_args(__k,
1219 _VSTD::piecewise_construct,
1220 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1221 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1224 template <class... _Args>
1225 _LIBCPP_INLINE_VISIBILITY
1226 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1228 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1229 _VSTD::piecewise_construct,
1230 _VSTD::forward_as_tuple(__k),
1231 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1234 template <class... _Args>
1235 _LIBCPP_INLINE_VISIBILITY
1236 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1238 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1239 _VSTD::piecewise_construct,
1240 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1241 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1244 template <class _Vp>
1245 _LIBCPP_INLINE_VISIBILITY
1246 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1248 iterator __p = lower_bound(__k);
1249 if ( __p != end() && !key_comp()(__k, __p->first))
1251 __p->second = _VSTD::forward<_Vp>(__v);
1252 return _VSTD::make_pair(__p, false);
1254 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1257 template <class _Vp>
1258 _LIBCPP_INLINE_VISIBILITY
1259 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1261 iterator __p = lower_bound(__k);
1262 if ( __p != end() && !key_comp()(__k, __p->first))
1264 __p->second = _VSTD::forward<_Vp>(__v);
1265 return _VSTD::make_pair(__p, false);
1267 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1270 template <class _Vp>
1271 _LIBCPP_INLINE_VISIBILITY
1272 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1274 iterator __p = lower_bound(__k);
1275 if ( __p != end() && !key_comp()(__k, __p->first))
1277 __p->second = _VSTD::forward<_Vp>(__v);
1280 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1283 template <class _Vp>
1284 _LIBCPP_INLINE_VISIBILITY
1285 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1287 iterator __p = lower_bound(__k);
1288 if ( __p != end() && !key_comp()(__k, __p->first))
1290 __p->second = _VSTD::forward<_Vp>(__v);
1293 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1296 #endif // _LIBCPP_STD_VER > 14
1298 _LIBCPP_INLINE_VISIBILITY
1299 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1300 _LIBCPP_INLINE_VISIBILITY
1301 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1302 _LIBCPP_INLINE_VISIBILITY
1303 size_type erase(const key_type& __k)
1304 {return __tree_.__erase_unique(__k);}
1305 _LIBCPP_INLINE_VISIBILITY
1306 iterator erase(const_iterator __f, const_iterator __l)
1307 {return __tree_.erase(__f.__i_, __l.__i_);}
1308 _LIBCPP_INLINE_VISIBILITY
1309 void clear() _NOEXCEPT {__tree_.clear();}
1311 #if _LIBCPP_STD_VER > 14
1312 _LIBCPP_INLINE_VISIBILITY
1313 insert_return_type insert(node_type&& __nh)
1315 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1316 "node_type with incompatible allocator passed to map::insert()");
1317 return __tree_.template __node_handle_insert_unique<
1318 node_type, insert_return_type>(_VSTD::move(__nh));
1320 _LIBCPP_INLINE_VISIBILITY
1321 iterator insert(const_iterator __hint, node_type&& __nh)
1323 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1324 "node_type with incompatible allocator passed to map::insert()");
1325 return __tree_.template __node_handle_insert_unique<node_type>(
1326 __hint.__i_, _VSTD::move(__nh));
1328 _LIBCPP_INLINE_VISIBILITY
1329 node_type extract(key_type const& __key)
1331 return __tree_.template __node_handle_extract<node_type>(__key);
1333 _LIBCPP_INLINE_VISIBILITY
1334 node_type extract(const_iterator __it)
1336 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1338 template <class _Compare2>
1339 _LIBCPP_INLINE_VISIBILITY
1340 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
1342 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1343 "merging container with incompatible allocator");
1344 __tree_.__node_handle_merge_unique(__source.__tree_);
1346 template <class _Compare2>
1347 _LIBCPP_INLINE_VISIBILITY
1348 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
1350 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1351 "merging container with incompatible allocator");
1352 __tree_.__node_handle_merge_unique(__source.__tree_);
1354 template <class _Compare2>
1355 _LIBCPP_INLINE_VISIBILITY
1356 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
1358 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1359 "merging container with incompatible allocator");
1360 __tree_.__node_handle_merge_unique(__source.__tree_);
1362 template <class _Compare2>
1363 _LIBCPP_INLINE_VISIBILITY
1364 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
1366 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1367 "merging container with incompatible allocator");
1368 __tree_.__node_handle_merge_unique(__source.__tree_);
1372 _LIBCPP_INLINE_VISIBILITY
1374 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1375 {__tree_.swap(__m.__tree_);}
1377 _LIBCPP_INLINE_VISIBILITY
1378 iterator find(const key_type& __k) {return __tree_.find(__k);}
1379 _LIBCPP_INLINE_VISIBILITY
1380 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1381 #if _LIBCPP_STD_VER > 11
1382 template <typename _K2>
1383 _LIBCPP_INLINE_VISIBILITY
1384 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1385 find(const _K2& __k) {return __tree_.find(__k);}
1386 template <typename _K2>
1387 _LIBCPP_INLINE_VISIBILITY
1388 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1389 find(const _K2& __k) const {return __tree_.find(__k);}
1392 _LIBCPP_INLINE_VISIBILITY
1393 size_type count(const key_type& __k) const
1394 {return __tree_.__count_unique(__k);}
1395 #if _LIBCPP_STD_VER > 11
1396 template <typename _K2>
1397 _LIBCPP_INLINE_VISIBILITY
1398 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1399 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
1402 #if _LIBCPP_STD_VER > 17
1403 _LIBCPP_INLINE_VISIBILITY
1404 bool contains(const key_type& __k) const {return find(__k) != end();}
1405 #endif // _LIBCPP_STD_VER > 17
1407 _LIBCPP_INLINE_VISIBILITY
1408 iterator lower_bound(const key_type& __k)
1409 {return __tree_.lower_bound(__k);}
1410 _LIBCPP_INLINE_VISIBILITY
1411 const_iterator lower_bound(const key_type& __k) const
1412 {return __tree_.lower_bound(__k);}
1413 #if _LIBCPP_STD_VER > 11
1414 template <typename _K2>
1415 _LIBCPP_INLINE_VISIBILITY
1416 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1417 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1419 template <typename _K2>
1420 _LIBCPP_INLINE_VISIBILITY
1421 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1422 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1425 _LIBCPP_INLINE_VISIBILITY
1426 iterator upper_bound(const key_type& __k)
1427 {return __tree_.upper_bound(__k);}
1428 _LIBCPP_INLINE_VISIBILITY
1429 const_iterator upper_bound(const key_type& __k) const
1430 {return __tree_.upper_bound(__k);}
1431 #if _LIBCPP_STD_VER > 11
1432 template <typename _K2>
1433 _LIBCPP_INLINE_VISIBILITY
1434 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1435 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1436 template <typename _K2>
1437 _LIBCPP_INLINE_VISIBILITY
1438 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1439 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1442 _LIBCPP_INLINE_VISIBILITY
1443 pair<iterator,iterator> equal_range(const key_type& __k)
1444 {return __tree_.__equal_range_unique(__k);}
1445 _LIBCPP_INLINE_VISIBILITY
1446 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1447 {return __tree_.__equal_range_unique(__k);}
1448 #if _LIBCPP_STD_VER > 11
1449 template <typename _K2>
1450 _LIBCPP_INLINE_VISIBILITY
1451 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1452 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1453 template <typename _K2>
1454 _LIBCPP_INLINE_VISIBILITY
1455 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1456 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1460 typedef typename __base::__node __node;
1461 typedef typename __base::__node_allocator __node_allocator;
1462 typedef typename __base::__node_pointer __node_pointer;
1463 typedef typename __base::__node_base_pointer __node_base_pointer;
1464 typedef typename __base::__parent_pointer __parent_pointer;
1466 typedef __map_node_destructor<__node_allocator> _Dp;
1467 typedef unique_ptr<__node, _Dp> __node_holder;
1469 #ifdef _LIBCPP_CXX03_LANG
1470 __node_holder __construct_node_with_key(const key_type& __k);
1474 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1475 template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
1476 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1477 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
1478 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
1479 map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1480 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1482 template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
1483 class _Allocator = allocator<pair<const _Key, _Tp>>,
1484 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
1485 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
1486 map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
1487 -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1489 template<class _InputIterator, class _Allocator,
1490 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
1491 map(_InputIterator, _InputIterator, _Allocator)
1492 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1493 less<__iter_key_type<_InputIterator>>, _Allocator>;
1495 template<class _Key, class _Tp, class _Allocator,
1496 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
1497 map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1498 -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1501 #ifndef _LIBCPP_CXX03_LANG
1502 template <class _Key, class _Tp, class _Compare, class _Allocator>
1503 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1504 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1506 if (__a != __m.get_allocator())
1508 const_iterator __e = cend();
1509 while (!__m.empty())
1510 __tree_.__insert_unique(__e.__i_,
1511 __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
1515 template <class _Key, class _Tp, class _Compare, class _Allocator>
1517 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1519 return __tree_.__emplace_unique_key_args(__k,
1520 _VSTD::piecewise_construct,
1521 _VSTD::forward_as_tuple(__k),
1522 _VSTD::forward_as_tuple()).first->__get_value().second;
1525 template <class _Key, class _Tp, class _Compare, class _Allocator>
1527 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1529 return __tree_.__emplace_unique_key_args(__k,
1530 _VSTD::piecewise_construct,
1531 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1532 _VSTD::forward_as_tuple()).first->__get_value().second;
1535 #else // _LIBCPP_CXX03_LANG
1537 template <class _Key, class _Tp, class _Compare, class _Allocator>
1538 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1539 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1541 __node_allocator& __na = __tree_.__node_alloc();
1542 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1543 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
1544 __h.get_deleter().__first_constructed = true;
1545 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
1546 __h.get_deleter().__second_constructed = true;
1547 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
1550 template <class _Key, class _Tp, class _Compare, class _Allocator>
1552 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1554 __parent_pointer __parent;
1555 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1556 __node_pointer __r = static_cast<__node_pointer>(__child);
1557 if (__child == nullptr)
1559 __node_holder __h = __construct_node_with_key(__k);
1560 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1561 __r = __h.release();
1563 return __r->__value_.__get_value().second;
1566 #endif // _LIBCPP_CXX03_LANG
1568 template <class _Key, class _Tp, class _Compare, class _Allocator>
1570 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1572 __parent_pointer __parent;
1573 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1574 if (__child == nullptr)
1575 __throw_out_of_range("map::at: key not found");
1576 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1579 template <class _Key, class _Tp, class _Compare, class _Allocator>
1581 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1583 __parent_pointer __parent;
1584 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1585 if (__child == nullptr)
1586 __throw_out_of_range("map::at: key not found");
1587 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1591 template <class _Key, class _Tp, class _Compare, class _Allocator>
1592 inline _LIBCPP_INLINE_VISIBILITY
1594 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1595 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1597 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1600 template <class _Key, class _Tp, class _Compare, class _Allocator>
1601 inline _LIBCPP_INLINE_VISIBILITY
1603 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1604 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1606 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1609 template <class _Key, class _Tp, class _Compare, class _Allocator>
1610 inline _LIBCPP_INLINE_VISIBILITY
1612 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1613 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1615 return !(__x == __y);
1618 template <class _Key, class _Tp, class _Compare, class _Allocator>
1619 inline _LIBCPP_INLINE_VISIBILITY
1621 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1622 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1627 template <class _Key, class _Tp, class _Compare, class _Allocator>
1628 inline _LIBCPP_INLINE_VISIBILITY
1630 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1631 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1633 return !(__x < __y);
1636 template <class _Key, class _Tp, class _Compare, class _Allocator>
1637 inline _LIBCPP_INLINE_VISIBILITY
1639 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1640 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1642 return !(__y < __x);
1645 template <class _Key, class _Tp, class _Compare, class _Allocator>
1646 inline _LIBCPP_INLINE_VISIBILITY
1648 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1649 map<_Key, _Tp, _Compare, _Allocator>& __y)
1650 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1655 #if _LIBCPP_STD_VER > 17
1656 template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
1657 inline _LIBCPP_INLINE_VISIBILITY
1658 void erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred)
1659 { __libcpp_erase_if_container(__c, __pred); }
1663 template <class _Key, class _Tp, class _Compare = less<_Key>,
1664 class _Allocator = allocator<pair<const _Key, _Tp> > >
1665 class _LIBCPP_TEMPLATE_VIS multimap
1669 typedef _Key key_type;
1670 typedef _Tp mapped_type;
1671 typedef pair<const key_type, mapped_type> value_type;
1672 typedef typename __identity<_Compare>::type key_compare;
1673 typedef typename __identity<_Allocator>::type allocator_type;
1674 typedef value_type& reference;
1675 typedef const value_type& const_reference;
1677 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1678 "Allocator::value_type must be same type as value_type");
1680 class _LIBCPP_TEMPLATE_VIS value_compare
1681 : public binary_function<value_type, value_type, bool>
1683 friend class multimap;
1687 _LIBCPP_INLINE_VISIBILITY
1688 value_compare(key_compare c) : comp(c) {}
1690 _LIBCPP_INLINE_VISIBILITY
1691 bool operator()(const value_type& __x, const value_type& __y) const
1692 {return comp(__x.first, __y.first);}
1697 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
1698 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1699 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1700 __value_type>::type __allocator_type;
1701 typedef __tree<__value_type, __vc, __allocator_type> __base;
1702 typedef typename __base::__node_traits __node_traits;
1703 typedef allocator_traits<allocator_type> __alloc_traits;
1708 typedef typename __alloc_traits::pointer pointer;
1709 typedef typename __alloc_traits::const_pointer const_pointer;
1710 typedef typename __alloc_traits::size_type size_type;
1711 typedef typename __alloc_traits::difference_type difference_type;
1712 typedef __map_iterator<typename __base::iterator> iterator;
1713 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1714 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1715 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1717 #if _LIBCPP_STD_VER > 14
1718 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1721 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1722 friend class _LIBCPP_TEMPLATE_VIS map;
1723 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1724 friend class _LIBCPP_TEMPLATE_VIS multimap;
1726 _LIBCPP_INLINE_VISIBILITY
1729 is_nothrow_default_constructible<allocator_type>::value &&
1730 is_nothrow_default_constructible<key_compare>::value &&
1731 is_nothrow_copy_constructible<key_compare>::value)
1732 : __tree_(__vc(key_compare())) {}
1734 _LIBCPP_INLINE_VISIBILITY
1735 explicit multimap(const key_compare& __comp)
1737 is_nothrow_default_constructible<allocator_type>::value &&
1738 is_nothrow_copy_constructible<key_compare>::value)
1739 : __tree_(__vc(__comp)) {}
1741 _LIBCPP_INLINE_VISIBILITY
1742 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1743 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1745 template <class _InputIterator>
1746 _LIBCPP_INLINE_VISIBILITY
1747 multimap(_InputIterator __f, _InputIterator __l,
1748 const key_compare& __comp = key_compare())
1749 : __tree_(__vc(__comp))
1754 template <class _InputIterator>
1755 _LIBCPP_INLINE_VISIBILITY
1756 multimap(_InputIterator __f, _InputIterator __l,
1757 const key_compare& __comp, const allocator_type& __a)
1758 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1763 #if _LIBCPP_STD_VER > 11
1764 template <class _InputIterator>
1765 _LIBCPP_INLINE_VISIBILITY
1766 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1767 : multimap(__f, __l, key_compare(), __a) {}
1770 _LIBCPP_INLINE_VISIBILITY
1771 multimap(const multimap& __m)
1772 : __tree_(__m.__tree_.value_comp(),
1773 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1775 insert(__m.begin(), __m.end());
1778 _LIBCPP_INLINE_VISIBILITY
1779 multimap& operator=(const multimap& __m)
1781 #ifndef _LIBCPP_CXX03_LANG
1782 __tree_ = __m.__tree_;
1786 __tree_.value_comp() = __m.__tree_.value_comp();
1787 __tree_.__copy_assign_alloc(__m.__tree_);
1788 insert(__m.begin(), __m.end());
1794 #ifndef _LIBCPP_CXX03_LANG
1796 _LIBCPP_INLINE_VISIBILITY
1797 multimap(multimap&& __m)
1798 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1799 : __tree_(_VSTD::move(__m.__tree_))
1803 multimap(multimap&& __m, const allocator_type& __a);
1805 _LIBCPP_INLINE_VISIBILITY
1806 multimap& operator=(multimap&& __m)
1807 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1809 __tree_ = _VSTD::move(__m.__tree_);
1813 _LIBCPP_INLINE_VISIBILITY
1814 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1815 : __tree_(__vc(__comp))
1817 insert(__il.begin(), __il.end());
1820 _LIBCPP_INLINE_VISIBILITY
1821 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1822 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1824 insert(__il.begin(), __il.end());
1827 #if _LIBCPP_STD_VER > 11
1828 _LIBCPP_INLINE_VISIBILITY
1829 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1830 : multimap(__il, key_compare(), __a) {}
1833 _LIBCPP_INLINE_VISIBILITY
1834 multimap& operator=(initializer_list<value_type> __il)
1836 __tree_.__assign_multi(__il.begin(), __il.end());
1840 #endif // _LIBCPP_CXX03_LANG
1842 _LIBCPP_INLINE_VISIBILITY
1843 explicit multimap(const allocator_type& __a)
1844 : __tree_(typename __base::allocator_type(__a))
1848 _LIBCPP_INLINE_VISIBILITY
1849 multimap(const multimap& __m, const allocator_type& __a)
1850 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1852 insert(__m.begin(), __m.end());
1855 _LIBCPP_INLINE_VISIBILITY
1857 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1860 _LIBCPP_INLINE_VISIBILITY
1861 iterator begin() _NOEXCEPT {return __tree_.begin();}
1862 _LIBCPP_INLINE_VISIBILITY
1863 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1864 _LIBCPP_INLINE_VISIBILITY
1865 iterator end() _NOEXCEPT {return __tree_.end();}
1866 _LIBCPP_INLINE_VISIBILITY
1867 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1869 _LIBCPP_INLINE_VISIBILITY
1870 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1871 _LIBCPP_INLINE_VISIBILITY
1872 const_reverse_iterator rbegin() const _NOEXCEPT
1873 {return const_reverse_iterator(end());}
1874 _LIBCPP_INLINE_VISIBILITY
1875 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1876 _LIBCPP_INLINE_VISIBILITY
1877 const_reverse_iterator rend() const _NOEXCEPT
1878 {return const_reverse_iterator(begin());}
1880 _LIBCPP_INLINE_VISIBILITY
1881 const_iterator cbegin() const _NOEXCEPT {return begin();}
1882 _LIBCPP_INLINE_VISIBILITY
1883 const_iterator cend() const _NOEXCEPT {return end();}
1884 _LIBCPP_INLINE_VISIBILITY
1885 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1886 _LIBCPP_INLINE_VISIBILITY
1887 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1889 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1890 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1891 _LIBCPP_INLINE_VISIBILITY
1892 size_type size() const _NOEXCEPT {return __tree_.size();}
1893 _LIBCPP_INLINE_VISIBILITY
1894 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1896 _LIBCPP_INLINE_VISIBILITY
1897 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1898 _LIBCPP_INLINE_VISIBILITY
1899 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1900 _LIBCPP_INLINE_VISIBILITY
1901 value_compare value_comp() const
1902 {return value_compare(__tree_.value_comp().key_comp());}
1904 #ifndef _LIBCPP_CXX03_LANG
1906 template <class ..._Args>
1907 _LIBCPP_INLINE_VISIBILITY
1908 iterator emplace(_Args&& ...__args) {
1909 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1912 template <class ..._Args>
1913 _LIBCPP_INLINE_VISIBILITY
1914 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1915 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1918 template <class _Pp,
1919 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1920 _LIBCPP_INLINE_VISIBILITY
1921 iterator insert(_Pp&& __p)
1922 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1924 template <class _Pp,
1925 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1926 _LIBCPP_INLINE_VISIBILITY
1927 iterator insert(const_iterator __pos, _Pp&& __p)
1928 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1930 _LIBCPP_INLINE_VISIBILITY
1931 iterator insert(value_type&& __v)
1932 {return __tree_.__insert_multi(_VSTD::move(__v));}
1934 _LIBCPP_INLINE_VISIBILITY
1935 iterator insert(const_iterator __p, value_type&& __v)
1936 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1939 _LIBCPP_INLINE_VISIBILITY
1940 void insert(initializer_list<value_type> __il)
1941 {insert(__il.begin(), __il.end());}
1943 #endif // _LIBCPP_CXX03_LANG
1945 _LIBCPP_INLINE_VISIBILITY
1946 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1948 _LIBCPP_INLINE_VISIBILITY
1949 iterator insert(const_iterator __p, const value_type& __v)
1950 {return __tree_.__insert_multi(__p.__i_, __v);}
1952 template <class _InputIterator>
1953 _LIBCPP_INLINE_VISIBILITY
1954 void insert(_InputIterator __f, _InputIterator __l)
1956 for (const_iterator __e = cend(); __f != __l; ++__f)
1957 __tree_.__insert_multi(__e.__i_, *__f);
1960 _LIBCPP_INLINE_VISIBILITY
1961 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1962 _LIBCPP_INLINE_VISIBILITY
1963 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1964 _LIBCPP_INLINE_VISIBILITY
1965 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1966 _LIBCPP_INLINE_VISIBILITY
1967 iterator erase(const_iterator __f, const_iterator __l)
1968 {return __tree_.erase(__f.__i_, __l.__i_);}
1970 #if _LIBCPP_STD_VER > 14
1971 _LIBCPP_INLINE_VISIBILITY
1972 iterator insert(node_type&& __nh)
1974 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1975 "node_type with incompatible allocator passed to multimap::insert()");
1976 return __tree_.template __node_handle_insert_multi<node_type>(
1979 _LIBCPP_INLINE_VISIBILITY
1980 iterator insert(const_iterator __hint, node_type&& __nh)
1982 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1983 "node_type with incompatible allocator passed to multimap::insert()");
1984 return __tree_.template __node_handle_insert_multi<node_type>(
1985 __hint.__i_, _VSTD::move(__nh));
1987 _LIBCPP_INLINE_VISIBILITY
1988 node_type extract(key_type const& __key)
1990 return __tree_.template __node_handle_extract<node_type>(__key);
1992 _LIBCPP_INLINE_VISIBILITY
1993 node_type extract(const_iterator __it)
1995 return __tree_.template __node_handle_extract<node_type>(
1998 template <class _Compare2>
1999 _LIBCPP_INLINE_VISIBILITY
2000 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
2002 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2003 "merging container with incompatible allocator");
2004 return __tree_.__node_handle_merge_multi(__source.__tree_);
2006 template <class _Compare2>
2007 _LIBCPP_INLINE_VISIBILITY
2008 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
2010 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2011 "merging container with incompatible allocator");
2012 return __tree_.__node_handle_merge_multi(__source.__tree_);
2014 template <class _Compare2>
2015 _LIBCPP_INLINE_VISIBILITY
2016 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
2018 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2019 "merging container with incompatible allocator");
2020 return __tree_.__node_handle_merge_multi(__source.__tree_);
2022 template <class _Compare2>
2023 _LIBCPP_INLINE_VISIBILITY
2024 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
2026 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2027 "merging container with incompatible allocator");
2028 return __tree_.__node_handle_merge_multi(__source.__tree_);
2032 _LIBCPP_INLINE_VISIBILITY
2033 void clear() _NOEXCEPT {__tree_.clear();}
2035 _LIBCPP_INLINE_VISIBILITY
2036 void swap(multimap& __m)
2037 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
2038 {__tree_.swap(__m.__tree_);}
2040 _LIBCPP_INLINE_VISIBILITY
2041 iterator find(const key_type& __k) {return __tree_.find(__k);}
2042 _LIBCPP_INLINE_VISIBILITY
2043 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
2044 #if _LIBCPP_STD_VER > 11
2045 template <typename _K2>
2046 _LIBCPP_INLINE_VISIBILITY
2047 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2048 find(const _K2& __k) {return __tree_.find(__k);}
2049 template <typename _K2>
2050 _LIBCPP_INLINE_VISIBILITY
2051 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2052 find(const _K2& __k) const {return __tree_.find(__k);}
2055 _LIBCPP_INLINE_VISIBILITY
2056 size_type count(const key_type& __k) const
2057 {return __tree_.__count_multi(__k);}
2058 #if _LIBCPP_STD_VER > 11
2059 template <typename _K2>
2060 _LIBCPP_INLINE_VISIBILITY
2061 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
2062 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
2065 #if _LIBCPP_STD_VER > 17
2066 _LIBCPP_INLINE_VISIBILITY
2067 bool contains(const key_type& __k) const {return find(__k) != end();}
2068 #endif // _LIBCPP_STD_VER > 17
2070 _LIBCPP_INLINE_VISIBILITY
2071 iterator lower_bound(const key_type& __k)
2072 {return __tree_.lower_bound(__k);}
2073 _LIBCPP_INLINE_VISIBILITY
2074 const_iterator lower_bound(const key_type& __k) const
2075 {return __tree_.lower_bound(__k);}
2076 #if _LIBCPP_STD_VER > 11
2077 template <typename _K2>
2078 _LIBCPP_INLINE_VISIBILITY
2079 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2080 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
2082 template <typename _K2>
2083 _LIBCPP_INLINE_VISIBILITY
2084 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2085 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
2088 _LIBCPP_INLINE_VISIBILITY
2089 iterator upper_bound(const key_type& __k)
2090 {return __tree_.upper_bound(__k);}
2091 _LIBCPP_INLINE_VISIBILITY
2092 const_iterator upper_bound(const key_type& __k) const
2093 {return __tree_.upper_bound(__k);}
2094 #if _LIBCPP_STD_VER > 11
2095 template <typename _K2>
2096 _LIBCPP_INLINE_VISIBILITY
2097 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2098 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
2099 template <typename _K2>
2100 _LIBCPP_INLINE_VISIBILITY
2101 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2102 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
2105 _LIBCPP_INLINE_VISIBILITY
2106 pair<iterator,iterator> equal_range(const key_type& __k)
2107 {return __tree_.__equal_range_multi(__k);}
2108 _LIBCPP_INLINE_VISIBILITY
2109 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
2110 {return __tree_.__equal_range_multi(__k);}
2111 #if _LIBCPP_STD_VER > 11
2112 template <typename _K2>
2113 _LIBCPP_INLINE_VISIBILITY
2114 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
2115 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
2116 template <typename _K2>
2117 _LIBCPP_INLINE_VISIBILITY
2118 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
2119 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
2123 typedef typename __base::__node __node;
2124 typedef typename __base::__node_allocator __node_allocator;
2125 typedef typename __base::__node_pointer __node_pointer;
2127 typedef __map_node_destructor<__node_allocator> _Dp;
2128 typedef unique_ptr<__node, _Dp> __node_holder;
2131 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
2132 template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
2133 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2134 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
2135 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
2136 multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
2137 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
2139 template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
2140 class _Allocator = allocator<pair<const _Key, _Tp>>,
2141 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
2142 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
2143 multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
2144 -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2146 template<class _InputIterator, class _Allocator,
2147 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
2148 multimap(_InputIterator, _InputIterator, _Allocator)
2149 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2150 less<__iter_key_type<_InputIterator>>, _Allocator>;
2152 template<class _Key, class _Tp, class _Allocator,
2153 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
2154 multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2155 -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
2158 #ifndef _LIBCPP_CXX03_LANG
2159 template <class _Key, class _Tp, class _Compare, class _Allocator>
2160 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
2161 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
2163 if (__a != __m.get_allocator())
2165 const_iterator __e = cend();
2166 while (!__m.empty())
2167 __tree_.__insert_multi(__e.__i_,
2168 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
2173 template <class _Key, class _Tp, class _Compare, class _Allocator>
2174 inline _LIBCPP_INLINE_VISIBILITY
2176 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2177 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2179 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2182 template <class _Key, class _Tp, class _Compare, class _Allocator>
2183 inline _LIBCPP_INLINE_VISIBILITY
2185 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2186 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2188 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2191 template <class _Key, class _Tp, class _Compare, class _Allocator>
2192 inline _LIBCPP_INLINE_VISIBILITY
2194 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2195 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2197 return !(__x == __y);
2200 template <class _Key, class _Tp, class _Compare, class _Allocator>
2201 inline _LIBCPP_INLINE_VISIBILITY
2203 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2204 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2209 template <class _Key, class _Tp, class _Compare, class _Allocator>
2210 inline _LIBCPP_INLINE_VISIBILITY
2212 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2213 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2215 return !(__x < __y);
2218 template <class _Key, class _Tp, class _Compare, class _Allocator>
2219 inline _LIBCPP_INLINE_VISIBILITY
2221 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2222 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2224 return !(__y < __x);
2227 template <class _Key, class _Tp, class _Compare, class _Allocator>
2228 inline _LIBCPP_INLINE_VISIBILITY
2230 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2231 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2232 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2237 #if _LIBCPP_STD_VER > 17
2238 template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
2239 inline _LIBCPP_INLINE_VISIBILITY
2240 void erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred)
2241 { __libcpp_erase_if_container(__c, __pred); }
2244 _LIBCPP_END_NAMESPACE_STD
2246 #endif // _LIBCPP_MAP