2 //===----------------------------- map ------------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
21 template <class Key, class T, class Compare = less<Key>,
22 class Allocator = allocator<pair<const Key, T>>>
28 typedef T mapped_type;
29 typedef pair<const key_type, mapped_type> value_type;
30 typedef Compare key_compare;
31 typedef Allocator allocator_type;
32 typedef typename allocator_type::reference reference;
33 typedef typename allocator_type::const_reference const_reference;
34 typedef typename allocator_type::pointer pointer;
35 typedef typename allocator_type::const_pointer const_pointer;
36 typedef typename allocator_type::size_type size_type;
37 typedef typename allocator_type::difference_type difference_type;
39 typedef implementation-defined iterator;
40 typedef implementation-defined const_iterator;
41 typedef std::reverse_iterator<iterator> reverse_iterator;
42 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
45 : public binary_function<value_type, value_type, bool>
51 value_compare(key_compare c);
53 bool operator()(const value_type& x, const value_type& y) const;
56 // construct/copy/destroy:
59 is_nothrow_default_constructible<allocator_type>::value &&
60 is_nothrow_default_constructible<key_compare>::value &&
61 is_nothrow_copy_constructible<key_compare>::value);
62 explicit map(const key_compare& comp);
63 map(const key_compare& comp, const allocator_type& a);
64 template <class InputIterator>
65 map(InputIterator first, InputIterator last,
66 const key_compare& comp = key_compare());
67 template <class InputIterator>
68 map(InputIterator first, InputIterator last,
69 const key_compare& comp, const allocator_type& a);
73 is_nothrow_move_constructible<allocator_type>::value &&
74 is_nothrow_move_constructible<key_compare>::value);
75 explicit map(const allocator_type& a);
76 map(const map& m, const allocator_type& a);
77 map(map&& m, const allocator_type& a);
78 map(initializer_list<value_type> il, const key_compare& comp = key_compare());
79 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
80 template <class InputIterator>
81 map(InputIterator first, InputIterator last, const allocator_type& a)
82 : map(first, last, Compare(), a) {} // C++14
83 map(initializer_list<value_type> il, const allocator_type& a)
84 : map(il, Compare(), a) {} // C++14
87 map& operator=(const map& m);
88 map& operator=(map&& m)
90 allocator_type::propagate_on_container_move_assignment::value &&
91 is_nothrow_move_assignable<allocator_type>::value &&
92 is_nothrow_move_assignable<key_compare>::value);
93 map& operator=(initializer_list<value_type> il);
96 iterator begin() noexcept;
97 const_iterator begin() const noexcept;
98 iterator end() noexcept;
99 const_iterator end() const noexcept;
101 reverse_iterator rbegin() noexcept;
102 const_reverse_iterator rbegin() const noexcept;
103 reverse_iterator rend() noexcept;
104 const_reverse_iterator rend() const noexcept;
106 const_iterator cbegin() const noexcept;
107 const_iterator cend() const noexcept;
108 const_reverse_iterator crbegin() const noexcept;
109 const_reverse_iterator crend() const noexcept;
112 bool empty() const noexcept;
113 size_type size() const noexcept;
114 size_type max_size() const noexcept;
117 mapped_type& operator[](const key_type& k);
118 mapped_type& operator[](key_type&& k);
120 mapped_type& at(const key_type& k);
121 const mapped_type& at(const key_type& k) const;
124 template <class... Args>
125 pair<iterator, bool> emplace(Args&&... args);
126 template <class... Args>
127 iterator emplace_hint(const_iterator position, Args&&... args);
128 pair<iterator, bool> insert(const value_type& v);
129 pair<iterator, bool> insert( value_type&& v); // C++17
131 pair<iterator, bool> insert(P&& p);
132 iterator insert(const_iterator position, const value_type& v);
133 iterator insert(const_iterator position, value_type&& v); // C++17
135 iterator insert(const_iterator position, P&& p);
136 template <class InputIterator>
137 void insert(InputIterator first, InputIterator last);
138 void insert(initializer_list<value_type> il);
140 template <class... Args>
141 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
142 template <class... Args>
143 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
144 template <class... Args>
145 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
146 template <class... Args>
147 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
149 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
151 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
153 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
155 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
157 iterator erase(const_iterator position);
158 iterator erase(iterator position); // C++14
159 size_type erase(const key_type& k);
160 iterator erase(const_iterator first, const_iterator last);
161 void clear() noexcept;
164 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
165 is_nothrow_swappable<key_compare>::value); // C++17
168 allocator_type get_allocator() const noexcept;
169 key_compare key_comp() const;
170 value_compare value_comp() const;
173 iterator find(const key_type& k);
174 const_iterator find(const key_type& k) const;
176 iterator find(const K& x); // C++14
178 const_iterator find(const K& x) const; // C++14
180 size_type count(const K& x) const; // C++14
182 size_type count(const key_type& k) const;
183 iterator lower_bound(const key_type& k);
184 const_iterator lower_bound(const key_type& k) const;
186 iterator lower_bound(const K& x); // C++14
188 const_iterator lower_bound(const K& x) const; // C++14
190 iterator upper_bound(const key_type& k);
191 const_iterator upper_bound(const key_type& k) const;
193 iterator upper_bound(const K& x); // C++14
195 const_iterator upper_bound(const K& x) const; // C++14
197 pair<iterator,iterator> equal_range(const key_type& k);
198 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
200 pair<iterator,iterator> equal_range(const K& x); // C++14
202 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
205 template <class Key, class T, class Compare, class Allocator>
207 operator==(const map<Key, T, Compare, Allocator>& x,
208 const map<Key, T, Compare, Allocator>& y);
210 template <class Key, class T, class Compare, class Allocator>
212 operator< (const map<Key, T, Compare, Allocator>& x,
213 const map<Key, T, Compare, Allocator>& y);
215 template <class Key, class T, class Compare, class Allocator>
217 operator!=(const map<Key, T, Compare, Allocator>& x,
218 const map<Key, T, Compare, Allocator>& y);
220 template <class Key, class T, class Compare, class Allocator>
222 operator> (const map<Key, T, Compare, Allocator>& x,
223 const map<Key, T, Compare, Allocator>& y);
225 template <class Key, class T, class Compare, class Allocator>
227 operator>=(const map<Key, T, Compare, Allocator>& x,
228 const map<Key, T, Compare, Allocator>& y);
230 template <class Key, class T, class Compare, class Allocator>
232 operator<=(const map<Key, T, Compare, Allocator>& x,
233 const map<Key, T, Compare, Allocator>& y);
235 // specialized algorithms:
236 template <class Key, class T, class Compare, class Allocator>
238 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
239 noexcept(noexcept(x.swap(y)));
241 template <class Key, class T, class Compare = less<Key>,
242 class Allocator = allocator<pair<const Key, T>>>
247 typedef Key key_type;
248 typedef T mapped_type;
249 typedef pair<const key_type,mapped_type> value_type;
250 typedef Compare key_compare;
251 typedef Allocator allocator_type;
252 typedef typename allocator_type::reference reference;
253 typedef typename allocator_type::const_reference const_reference;
254 typedef typename allocator_type::size_type size_type;
255 typedef typename allocator_type::difference_type difference_type;
256 typedef typename allocator_type::pointer pointer;
257 typedef typename allocator_type::const_pointer const_pointer;
259 typedef implementation-defined iterator;
260 typedef implementation-defined const_iterator;
261 typedef std::reverse_iterator<iterator> reverse_iterator;
262 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
265 : public binary_function<value_type,value_type,bool>
267 friend class multimap;
270 value_compare(key_compare c);
272 bool operator()(const value_type& x, const value_type& y) const;
275 // construct/copy/destroy:
278 is_nothrow_default_constructible<allocator_type>::value &&
279 is_nothrow_default_constructible<key_compare>::value &&
280 is_nothrow_copy_constructible<key_compare>::value);
281 explicit multimap(const key_compare& comp);
282 multimap(const key_compare& comp, const allocator_type& a);
283 template <class InputIterator>
284 multimap(InputIterator first, InputIterator last, const key_compare& comp);
285 template <class InputIterator>
286 multimap(InputIterator first, InputIterator last, const key_compare& comp,
287 const allocator_type& a);
288 multimap(const multimap& m);
289 multimap(multimap&& m)
291 is_nothrow_move_constructible<allocator_type>::value &&
292 is_nothrow_move_constructible<key_compare>::value);
293 explicit multimap(const allocator_type& a);
294 multimap(const multimap& m, const allocator_type& a);
295 multimap(multimap&& m, const allocator_type& a);
296 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
297 multimap(initializer_list<value_type> il, const key_compare& comp,
298 const allocator_type& a);
299 template <class InputIterator>
300 multimap(InputIterator first, InputIterator last, const allocator_type& a)
301 : multimap(first, last, Compare(), a) {} // C++14
302 multimap(initializer_list<value_type> il, const allocator_type& a)
303 : multimap(il, Compare(), a) {} // C++14
306 multimap& operator=(const multimap& m);
307 multimap& operator=(multimap&& m)
309 allocator_type::propagate_on_container_move_assignment::value &&
310 is_nothrow_move_assignable<allocator_type>::value &&
311 is_nothrow_move_assignable<key_compare>::value);
312 multimap& operator=(initializer_list<value_type> il);
315 iterator begin() noexcept;
316 const_iterator begin() const noexcept;
317 iterator end() noexcept;
318 const_iterator end() const noexcept;
320 reverse_iterator rbegin() noexcept;
321 const_reverse_iterator rbegin() const noexcept;
322 reverse_iterator rend() noexcept;
323 const_reverse_iterator rend() const noexcept;
325 const_iterator cbegin() const noexcept;
326 const_iterator cend() const noexcept;
327 const_reverse_iterator crbegin() const noexcept;
328 const_reverse_iterator crend() const noexcept;
331 bool empty() const noexcept;
332 size_type size() const noexcept;
333 size_type max_size() const noexcept;
336 template <class... Args>
337 iterator emplace(Args&&... args);
338 template <class... Args>
339 iterator emplace_hint(const_iterator position, Args&&... args);
340 iterator insert(const value_type& v);
341 iterator insert( value_type&& v); // C++17
343 iterator insert(P&& p);
344 iterator insert(const_iterator position, const value_type& v);
345 iterator insert(const_iterator position, value_type&& v); // C++17
347 iterator insert(const_iterator position, P&& p);
348 template <class InputIterator>
349 void insert(InputIterator first, InputIterator last);
350 void insert(initializer_list<value_type> il);
352 iterator erase(const_iterator position);
353 iterator erase(iterator position); // C++14
354 size_type erase(const key_type& k);
355 iterator erase(const_iterator first, const_iterator last);
356 void clear() noexcept;
358 void swap(multimap& m)
359 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
360 is_nothrow_swappable<key_compare>::value); // C++17
363 allocator_type get_allocator() const noexcept;
364 key_compare key_comp() const;
365 value_compare value_comp() const;
368 iterator find(const key_type& k);
369 const_iterator find(const key_type& k) const;
371 iterator find(const K& x); // C++14
373 const_iterator find(const K& x) const; // C++14
375 size_type count(const K& x) const; // C++14
377 size_type count(const key_type& k) const;
378 iterator lower_bound(const key_type& k);
379 const_iterator lower_bound(const key_type& k) const;
381 iterator lower_bound(const K& x); // C++14
383 const_iterator lower_bound(const K& x) const; // C++14
385 iterator upper_bound(const key_type& k);
386 const_iterator upper_bound(const key_type& k) const;
388 iterator upper_bound(const K& x); // C++14
390 const_iterator upper_bound(const K& x) const; // C++14
392 pair<iterator,iterator> equal_range(const key_type& k);
393 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
395 pair<iterator,iterator> equal_range(const K& x); // C++14
397 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
400 template <class Key, class T, class Compare, class Allocator>
402 operator==(const multimap<Key, T, Compare, Allocator>& x,
403 const multimap<Key, T, Compare, Allocator>& y);
405 template <class Key, class T, class Compare, class Allocator>
407 operator< (const multimap<Key, T, Compare, Allocator>& x,
408 const multimap<Key, T, Compare, Allocator>& y);
410 template <class Key, class T, class Compare, class Allocator>
412 operator!=(const multimap<Key, T, Compare, Allocator>& x,
413 const multimap<Key, T, Compare, Allocator>& y);
415 template <class Key, class T, class Compare, class Allocator>
417 operator> (const multimap<Key, T, Compare, Allocator>& x,
418 const multimap<Key, T, Compare, Allocator>& y);
420 template <class Key, class T, class Compare, class Allocator>
422 operator>=(const multimap<Key, T, Compare, Allocator>& x,
423 const multimap<Key, T, Compare, Allocator>& y);
425 template <class Key, class T, class Compare, class Allocator>
427 operator<=(const multimap<Key, T, Compare, Allocator>& x,
428 const multimap<Key, T, Compare, Allocator>& y);
430 // specialized algorithms:
431 template <class Key, class T, class Compare, class Allocator>
433 swap(multimap<Key, T, Compare, Allocator>& x,
434 multimap<Key, T, Compare, Allocator>& y)
435 noexcept(noexcept(x.swap(y)));
446 #include <functional>
447 #include <initializer_list>
448 #include <type_traits>
450 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
451 #pragma GCC system_header
454 _LIBCPP_BEGIN_NAMESPACE_STD
456 template <class _Key, class _CP, class _Compare,
457 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value
459 class __map_value_compare
463 _LIBCPP_INLINE_VISIBILITY
464 __map_value_compare()
465 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
467 _LIBCPP_INLINE_VISIBILITY
468 __map_value_compare(_Compare c)
469 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
471 _LIBCPP_INLINE_VISIBILITY
472 const _Compare& key_comp() const _NOEXCEPT {return *this;}
473 _LIBCPP_INLINE_VISIBILITY
474 bool operator()(const _CP& __x, const _CP& __y) const
475 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y.__cc.first);}
476 _LIBCPP_INLINE_VISIBILITY
477 bool operator()(const _CP& __x, const _Key& __y) const
478 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y);}
479 _LIBCPP_INLINE_VISIBILITY
480 bool operator()(const _Key& __x, const _CP& __y) const
481 {return static_cast<const _Compare&>(*this)(__x, __y.__cc.first);}
482 void swap(__map_value_compare&__y)
483 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
486 swap(static_cast<const _Compare&>(*this), static_cast<const _Compare&>(__y));
489 #if _LIBCPP_STD_VER > 11
490 template <typename _K2>
491 _LIBCPP_INLINE_VISIBILITY
492 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
493 operator () ( const _K2& __x, const _CP& __y ) const
494 {return static_cast<const _Compare&>(*this) (__x, __y.__cc.first);}
496 template <typename _K2>
497 _LIBCPP_INLINE_VISIBILITY
498 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
499 operator () (const _CP& __x, const _K2& __y) const
500 {return static_cast<const _Compare&>(*this) (__x.__cc.first, __y);}
504 template <class _Key, class _CP, class _Compare>
505 class __map_value_compare<_Key, _CP, _Compare, false>
510 _LIBCPP_INLINE_VISIBILITY
511 __map_value_compare()
512 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
514 _LIBCPP_INLINE_VISIBILITY
515 __map_value_compare(_Compare c)
516 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
518 _LIBCPP_INLINE_VISIBILITY
519 const _Compare& key_comp() const _NOEXCEPT {return comp;}
521 _LIBCPP_INLINE_VISIBILITY
522 bool operator()(const _CP& __x, const _CP& __y) const
523 {return comp(__x.__cc.first, __y.__cc.first);}
524 _LIBCPP_INLINE_VISIBILITY
525 bool operator()(const _CP& __x, const _Key& __y) const
526 {return comp(__x.__cc.first, __y);}
527 _LIBCPP_INLINE_VISIBILITY
528 bool operator()(const _Key& __x, const _CP& __y) const
529 {return comp(__x, __y.__cc.first);}
530 void swap(__map_value_compare&__y)
531 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
534 swap(comp, __y.comp);
537 #if _LIBCPP_STD_VER > 11
538 template <typename _K2>
539 _LIBCPP_INLINE_VISIBILITY
540 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
541 operator () ( const _K2& __x, const _CP& __y ) const
542 {return comp (__x, __y.__cc.first);}
544 template <typename _K2>
545 _LIBCPP_INLINE_VISIBILITY
546 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
547 operator () (const _CP& __x, const _K2& __y) const
548 {return comp (__x.__cc.first, __y);}
552 template <class _Key, class _CP, class _Compare, bool __b>
553 inline _LIBCPP_INLINE_VISIBILITY
555 swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
556 __map_value_compare<_Key, _CP, _Compare, __b>& __y)
557 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
562 template <class _Allocator>
563 class __map_node_destructor
565 typedef _Allocator allocator_type;
566 typedef allocator_traits<allocator_type> __alloc_traits;
569 typedef typename __alloc_traits::pointer pointer;
572 allocator_type& __na_;
574 __map_node_destructor& operator=(const __map_node_destructor&);
577 bool __first_constructed;
578 bool __second_constructed;
580 _LIBCPP_INLINE_VISIBILITY
581 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
583 __first_constructed(false),
584 __second_constructed(false)
587 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
588 _LIBCPP_INLINE_VISIBILITY
589 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
591 __first_constructed(__x.__value_constructed),
592 __second_constructed(__x.__value_constructed)
594 __x.__value_constructed = false;
596 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
598 _LIBCPP_INLINE_VISIBILITY
599 void operator()(pointer __p) _NOEXCEPT
601 if (__second_constructed)
602 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
603 if (__first_constructed)
604 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
606 __alloc_traits::deallocate(__na_, __p, 1);
610 template <class _Key, class _Tp, class _Compare, class _Allocator>
612 template <class _Key, class _Tp, class _Compare, class _Allocator>
614 template <class _TreeIterator> class __map_const_iterator;
616 #ifndef _LIBCPP_CXX03_LANG
618 template <class _Key, class _Tp>
621 typedef _Key key_type;
622 typedef _Tp mapped_type;
623 typedef pair<const key_type, mapped_type> value_type;
624 typedef pair<key_type, mapped_type> __nc_value_type;
627 __nc_value_type __nc;
629 _LIBCPP_INLINE_VISIBILITY
630 __value_type& operator=(const __value_type& __v)
631 {__nc = __v.__cc; return *this;}
633 _LIBCPP_INLINE_VISIBILITY
634 __value_type& operator=(__value_type&& __v)
635 {__nc = _VSTD::move(__v.__nc); return *this;}
637 template <class _ValueTp,
638 class = typename enable_if<
639 __is_same_uncvref<_ValueTp, value_type>::value
642 _LIBCPP_INLINE_VISIBILITY
643 __value_type& operator=(_ValueTp&& __v) {
644 __nc = _VSTD::forward<_ValueTp>(__v); return *this;
648 __value_type() _LIBCPP_EQUAL_DELETE;
649 ~__value_type() _LIBCPP_EQUAL_DELETE;
650 __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
651 __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
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;
667 __value_type(__value_type const&);
668 __value_type& operator=(__value_type const&);
675 struct __extract_key_value_types;
677 template <class _Key, class _Tp>
678 struct __extract_key_value_types<__value_type<_Key, _Tp> >
680 typedef _Key const __key_type;
681 typedef _Tp __mapped_type;
684 template <class _TreeIterator>
685 class _LIBCPP_TEMPLATE_VIS __map_iterator
687 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
688 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
693 typedef bidirectional_iterator_tag iterator_category;
694 typedef typename _NodeTypes::__map_value_type value_type;
695 typedef typename _TreeIterator::difference_type difference_type;
696 typedef value_type& reference;
697 typedef typename _NodeTypes::__map_value_type_pointer pointer;
699 _LIBCPP_INLINE_VISIBILITY
700 __map_iterator() _NOEXCEPT {}
702 _LIBCPP_INLINE_VISIBILITY
703 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
705 _LIBCPP_INLINE_VISIBILITY
706 reference operator*() const {return __i_->__cc;}
707 _LIBCPP_INLINE_VISIBILITY
708 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
710 _LIBCPP_INLINE_VISIBILITY
711 __map_iterator& operator++() {++__i_; return *this;}
712 _LIBCPP_INLINE_VISIBILITY
713 __map_iterator operator++(int)
715 __map_iterator __t(*this);
720 _LIBCPP_INLINE_VISIBILITY
721 __map_iterator& operator--() {--__i_; return *this;}
722 _LIBCPP_INLINE_VISIBILITY
723 __map_iterator operator--(int)
725 __map_iterator __t(*this);
730 friend _LIBCPP_INLINE_VISIBILITY
731 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
732 {return __x.__i_ == __y.__i_;}
734 _LIBCPP_INLINE_VISIBILITY
735 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
736 {return __x.__i_ != __y.__i_;}
738 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
739 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
740 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
743 template <class _TreeIterator>
744 class _LIBCPP_TEMPLATE_VIS __map_const_iterator
746 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
747 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
752 typedef bidirectional_iterator_tag iterator_category;
753 typedef typename _NodeTypes::__map_value_type value_type;
754 typedef typename _TreeIterator::difference_type difference_type;
755 typedef const value_type& reference;
756 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
758 _LIBCPP_INLINE_VISIBILITY
759 __map_const_iterator() _NOEXCEPT {}
761 _LIBCPP_INLINE_VISIBILITY
762 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
763 _LIBCPP_INLINE_VISIBILITY
764 __map_const_iterator(__map_iterator<
765 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
768 _LIBCPP_INLINE_VISIBILITY
769 reference operator*() const {return __i_->__cc;}
770 _LIBCPP_INLINE_VISIBILITY
771 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
773 _LIBCPP_INLINE_VISIBILITY
774 __map_const_iterator& operator++() {++__i_; return *this;}
775 _LIBCPP_INLINE_VISIBILITY
776 __map_const_iterator operator++(int)
778 __map_const_iterator __t(*this);
783 _LIBCPP_INLINE_VISIBILITY
784 __map_const_iterator& operator--() {--__i_; return *this;}
785 _LIBCPP_INLINE_VISIBILITY
786 __map_const_iterator operator--(int)
788 __map_const_iterator __t(*this);
793 friend _LIBCPP_INLINE_VISIBILITY
794 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
795 {return __x.__i_ == __y.__i_;}
796 friend _LIBCPP_INLINE_VISIBILITY
797 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
798 {return __x.__i_ != __y.__i_;}
800 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
801 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
802 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
805 template <class _Key, class _Tp, class _Compare = less<_Key>,
806 class _Allocator = allocator<pair<const _Key, _Tp> > >
807 class _LIBCPP_TEMPLATE_VIS map
811 typedef _Key key_type;
812 typedef _Tp mapped_type;
813 typedef pair<const key_type, mapped_type> value_type;
814 typedef pair<key_type, mapped_type> __nc_value_type;
815 typedef _Compare key_compare;
816 typedef _Allocator allocator_type;
817 typedef value_type& reference;
818 typedef const value_type& const_reference;
820 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
821 "Allocator::value_type must be same type as value_type");
823 class _LIBCPP_TEMPLATE_VIS value_compare
824 : public binary_function<value_type, value_type, bool>
830 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
832 _LIBCPP_INLINE_VISIBILITY
833 bool operator()(const value_type& __x, const value_type& __y) const
834 {return comp(__x.first, __y.first);}
839 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
840 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
841 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
842 __value_type>::type __allocator_type;
843 typedef __tree<__value_type, __vc, __allocator_type> __base;
844 typedef typename __base::__node_traits __node_traits;
845 typedef allocator_traits<allocator_type> __alloc_traits;
850 typedef typename __alloc_traits::pointer pointer;
851 typedef typename __alloc_traits::const_pointer const_pointer;
852 typedef typename __alloc_traits::size_type size_type;
853 typedef typename __alloc_traits::difference_type difference_type;
854 typedef __map_iterator<typename __base::iterator> iterator;
855 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
856 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
857 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
859 _LIBCPP_INLINE_VISIBILITY
862 is_nothrow_default_constructible<allocator_type>::value &&
863 is_nothrow_default_constructible<key_compare>::value &&
864 is_nothrow_copy_constructible<key_compare>::value)
865 : __tree_(__vc(key_compare())) {}
867 _LIBCPP_INLINE_VISIBILITY
868 explicit map(const key_compare& __comp)
870 is_nothrow_default_constructible<allocator_type>::value &&
871 is_nothrow_copy_constructible<key_compare>::value)
872 : __tree_(__vc(__comp)) {}
874 _LIBCPP_INLINE_VISIBILITY
875 explicit map(const key_compare& __comp, const allocator_type& __a)
876 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
878 template <class _InputIterator>
879 _LIBCPP_INLINE_VISIBILITY
880 map(_InputIterator __f, _InputIterator __l,
881 const key_compare& __comp = key_compare())
882 : __tree_(__vc(__comp))
887 template <class _InputIterator>
888 _LIBCPP_INLINE_VISIBILITY
889 map(_InputIterator __f, _InputIterator __l,
890 const key_compare& __comp, const allocator_type& __a)
891 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
896 #if _LIBCPP_STD_VER > 11
897 template <class _InputIterator>
898 _LIBCPP_INLINE_VISIBILITY
899 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
900 : map(__f, __l, key_compare(), __a) {}
903 _LIBCPP_INLINE_VISIBILITY
905 : __tree_(__m.__tree_)
907 insert(__m.begin(), __m.end());
910 _LIBCPP_INLINE_VISIBILITY
911 map& operator=(const map& __m)
913 #ifndef _LIBCPP_CXX03_LANG
914 __tree_ = __m.__tree_;
918 __tree_.value_comp() = __m.__tree_.value_comp();
919 __tree_.__copy_assign_alloc(__m.__tree_);
920 insert(__m.begin(), __m.end());
926 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
928 _LIBCPP_INLINE_VISIBILITY
930 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
931 : __tree_(_VSTD::move(__m.__tree_))
935 map(map&& __m, const allocator_type& __a);
937 _LIBCPP_INLINE_VISIBILITY
938 map& operator=(map&& __m)
939 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
941 __tree_ = _VSTD::move(__m.__tree_);
945 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
947 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
949 _LIBCPP_INLINE_VISIBILITY
950 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
951 : __tree_(__vc(__comp))
953 insert(__il.begin(), __il.end());
956 _LIBCPP_INLINE_VISIBILITY
957 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
958 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
960 insert(__il.begin(), __il.end());
963 #if _LIBCPP_STD_VER > 11
964 _LIBCPP_INLINE_VISIBILITY
965 map(initializer_list<value_type> __il, const allocator_type& __a)
966 : map(__il, key_compare(), __a) {}
969 _LIBCPP_INLINE_VISIBILITY
970 map& operator=(initializer_list<value_type> __il)
972 __tree_.__assign_unique(__il.begin(), __il.end());
976 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
978 _LIBCPP_INLINE_VISIBILITY
979 explicit map(const allocator_type& __a)
980 : __tree_(typename __base::allocator_type(__a))
984 _LIBCPP_INLINE_VISIBILITY
985 map(const map& __m, const allocator_type& __a)
986 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
988 insert(__m.begin(), __m.end());
991 _LIBCPP_INLINE_VISIBILITY
992 iterator begin() _NOEXCEPT {return __tree_.begin();}
993 _LIBCPP_INLINE_VISIBILITY
994 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
995 _LIBCPP_INLINE_VISIBILITY
996 iterator end() _NOEXCEPT {return __tree_.end();}
997 _LIBCPP_INLINE_VISIBILITY
998 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1000 _LIBCPP_INLINE_VISIBILITY
1001 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1002 _LIBCPP_INLINE_VISIBILITY
1003 const_reverse_iterator rbegin() const _NOEXCEPT
1004 {return const_reverse_iterator(end());}
1005 _LIBCPP_INLINE_VISIBILITY
1006 reverse_iterator rend() _NOEXCEPT
1007 {return reverse_iterator(begin());}
1008 _LIBCPP_INLINE_VISIBILITY
1009 const_reverse_iterator rend() const _NOEXCEPT
1010 {return const_reverse_iterator(begin());}
1012 _LIBCPP_INLINE_VISIBILITY
1013 const_iterator cbegin() const _NOEXCEPT {return begin();}
1014 _LIBCPP_INLINE_VISIBILITY
1015 const_iterator cend() const _NOEXCEPT {return end();}
1016 _LIBCPP_INLINE_VISIBILITY
1017 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1018 _LIBCPP_INLINE_VISIBILITY
1019 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1021 _LIBCPP_INLINE_VISIBILITY
1022 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1023 _LIBCPP_INLINE_VISIBILITY
1024 size_type size() const _NOEXCEPT {return __tree_.size();}
1025 _LIBCPP_INLINE_VISIBILITY
1026 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1028 mapped_type& operator[](const key_type& __k);
1029 #ifndef _LIBCPP_CXX03_LANG
1030 mapped_type& operator[](key_type&& __k);
1033 mapped_type& at(const key_type& __k);
1034 const mapped_type& at(const key_type& __k) const;
1036 _LIBCPP_INLINE_VISIBILITY
1037 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1038 _LIBCPP_INLINE_VISIBILITY
1039 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1040 _LIBCPP_INLINE_VISIBILITY
1041 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1043 #ifndef _LIBCPP_CXX03_LANG
1044 template <class ..._Args>
1045 _LIBCPP_INLINE_VISIBILITY
1046 pair<iterator, bool> emplace(_Args&& ...__args) {
1047 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1050 template <class ..._Args>
1051 _LIBCPP_INLINE_VISIBILITY
1052 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1053 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1056 template <class _Pp,
1057 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1058 _LIBCPP_INLINE_VISIBILITY
1059 pair<iterator, bool> insert(_Pp&& __p)
1060 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1062 template <class _Pp,
1063 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1064 _LIBCPP_INLINE_VISIBILITY
1065 iterator insert(const_iterator __pos, _Pp&& __p)
1066 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1068 #endif // _LIBCPP_CXX03_LANG
1070 _LIBCPP_INLINE_VISIBILITY
1071 pair<iterator, bool>
1072 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1074 _LIBCPP_INLINE_VISIBILITY
1076 insert(const_iterator __p, const value_type& __v)
1077 {return __tree_.__insert_unique(__p.__i_, __v);}
1079 #ifndef _LIBCPP_CXX03_LANG
1080 _LIBCPP_INLINE_VISIBILITY
1081 pair<iterator, bool>
1082 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
1084 _LIBCPP_INLINE_VISIBILITY
1085 iterator insert(const_iterator __p, value_type&& __v)
1086 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
1089 template <class _InputIterator>
1090 _LIBCPP_INLINE_VISIBILITY
1091 void insert(_InputIterator __f, _InputIterator __l)
1093 for (const_iterator __e = cend(); __f != __l; ++__f)
1094 insert(__e.__i_, *__f);
1097 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1099 _LIBCPP_INLINE_VISIBILITY
1100 void insert(initializer_list<value_type> __il)
1101 {insert(__il.begin(), __il.end());}
1103 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1105 #if _LIBCPP_STD_VER > 14
1107 template <class... _Args>
1108 _LIBCPP_INLINE_VISIBILITY
1109 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1111 return __tree_.__emplace_unique_key_args(__k,
1112 _VSTD::piecewise_construct,
1113 _VSTD::forward_as_tuple(__k),
1114 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1117 template <class... _Args>
1118 _LIBCPP_INLINE_VISIBILITY
1119 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1121 return __tree_.__emplace_unique_key_args(__k,
1122 _VSTD::piecewise_construct,
1123 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1124 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1127 template <class... _Args>
1128 _LIBCPP_INLINE_VISIBILITY
1129 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1131 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1132 _VSTD::piecewise_construct,
1133 _VSTD::forward_as_tuple(__k),
1134 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1137 template <class... _Args>
1138 _LIBCPP_INLINE_VISIBILITY
1139 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1141 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1142 _VSTD::piecewise_construct,
1143 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1144 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1147 template <class _Vp>
1148 _LIBCPP_INLINE_VISIBILITY
1149 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1151 iterator __p = lower_bound(__k);
1152 if ( __p != end() && !key_comp()(__k, __p->first))
1154 __p->second = _VSTD::forward<_Vp>(__v);
1155 return _VSTD::make_pair(__p, false);
1157 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1160 template <class _Vp>
1161 _LIBCPP_INLINE_VISIBILITY
1162 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1164 iterator __p = lower_bound(__k);
1165 if ( __p != end() && !key_comp()(__k, __p->first))
1167 __p->second = _VSTD::forward<_Vp>(__v);
1168 return _VSTD::make_pair(__p, false);
1170 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1173 template <class _Vp>
1174 _LIBCPP_INLINE_VISIBILITY
1175 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1177 iterator __p = lower_bound(__k);
1178 if ( __p != end() && !key_comp()(__k, __p->first))
1180 __p->second = _VSTD::forward<_Vp>(__v);
1183 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1186 template <class _Vp>
1187 _LIBCPP_INLINE_VISIBILITY
1188 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1190 iterator __p = lower_bound(__k);
1191 if ( __p != end() && !key_comp()(__k, __p->first))
1193 __p->second = _VSTD::forward<_Vp>(__v);
1196 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1201 _LIBCPP_INLINE_VISIBILITY
1202 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1203 _LIBCPP_INLINE_VISIBILITY
1204 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1205 _LIBCPP_INLINE_VISIBILITY
1206 size_type erase(const key_type& __k)
1207 {return __tree_.__erase_unique(__k);}
1208 _LIBCPP_INLINE_VISIBILITY
1209 iterator erase(const_iterator __f, const_iterator __l)
1210 {return __tree_.erase(__f.__i_, __l.__i_);}
1211 _LIBCPP_INLINE_VISIBILITY
1212 void clear() _NOEXCEPT {__tree_.clear();}
1214 _LIBCPP_INLINE_VISIBILITY
1216 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1217 {__tree_.swap(__m.__tree_);}
1219 _LIBCPP_INLINE_VISIBILITY
1220 iterator find(const key_type& __k) {return __tree_.find(__k);}
1221 _LIBCPP_INLINE_VISIBILITY
1222 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1223 #if _LIBCPP_STD_VER > 11
1224 template <typename _K2>
1225 _LIBCPP_INLINE_VISIBILITY
1226 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1227 find(const _K2& __k) {return __tree_.find(__k);}
1228 template <typename _K2>
1229 _LIBCPP_INLINE_VISIBILITY
1230 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1231 find(const _K2& __k) const {return __tree_.find(__k);}
1234 _LIBCPP_INLINE_VISIBILITY
1235 size_type count(const key_type& __k) const
1236 {return __tree_.__count_unique(__k);}
1237 #if _LIBCPP_STD_VER > 11
1238 template <typename _K2>
1239 _LIBCPP_INLINE_VISIBILITY
1240 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1241 count(const _K2& __k) const {return __tree_.__count_unique(__k);}
1243 _LIBCPP_INLINE_VISIBILITY
1244 iterator lower_bound(const key_type& __k)
1245 {return __tree_.lower_bound(__k);}
1246 _LIBCPP_INLINE_VISIBILITY
1247 const_iterator lower_bound(const key_type& __k) const
1248 {return __tree_.lower_bound(__k);}
1249 #if _LIBCPP_STD_VER > 11
1250 template <typename _K2>
1251 _LIBCPP_INLINE_VISIBILITY
1252 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1253 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1255 template <typename _K2>
1256 _LIBCPP_INLINE_VISIBILITY
1257 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1258 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1261 _LIBCPP_INLINE_VISIBILITY
1262 iterator upper_bound(const key_type& __k)
1263 {return __tree_.upper_bound(__k);}
1264 _LIBCPP_INLINE_VISIBILITY
1265 const_iterator upper_bound(const key_type& __k) const
1266 {return __tree_.upper_bound(__k);}
1267 #if _LIBCPP_STD_VER > 11
1268 template <typename _K2>
1269 _LIBCPP_INLINE_VISIBILITY
1270 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1271 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1272 template <typename _K2>
1273 _LIBCPP_INLINE_VISIBILITY
1274 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1275 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1278 _LIBCPP_INLINE_VISIBILITY
1279 pair<iterator,iterator> equal_range(const key_type& __k)
1280 {return __tree_.__equal_range_unique(__k);}
1281 _LIBCPP_INLINE_VISIBILITY
1282 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1283 {return __tree_.__equal_range_unique(__k);}
1284 #if _LIBCPP_STD_VER > 11
1285 template <typename _K2>
1286 _LIBCPP_INLINE_VISIBILITY
1287 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1288 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
1289 template <typename _K2>
1290 _LIBCPP_INLINE_VISIBILITY
1291 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1292 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1296 typedef typename __base::__node __node;
1297 typedef typename __base::__node_allocator __node_allocator;
1298 typedef typename __base::__node_pointer __node_pointer;
1299 typedef typename __base::__node_base_pointer __node_base_pointer;
1300 typedef typename __base::__parent_pointer __parent_pointer;
1302 typedef __map_node_destructor<__node_allocator> _Dp;
1303 typedef unique_ptr<__node, _Dp> __node_holder;
1305 #ifdef _LIBCPP_CXX03_LANG
1306 __node_holder __construct_node_with_key(const key_type& __k);
1311 #ifndef _LIBCPP_CXX03_LANG
1313 template <class _Key, class _Tp, class _Compare, class _Allocator>
1314 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1315 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1317 if (__a != __m.get_allocator())
1319 const_iterator __e = cend();
1320 while (!__m.empty())
1321 __tree_.__insert_unique(__e.__i_,
1322 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
1326 #endif // !_LIBCPP_CXX03_LANG
1329 #ifdef _LIBCPP_CXX03_LANG
1331 template <class _Key, class _Tp, class _Compare, class _Allocator>
1332 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1333 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1335 __node_allocator& __na = __tree_.__node_alloc();
1336 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1337 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1338 __h.get_deleter().__first_constructed = true;
1339 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1340 __h.get_deleter().__second_constructed = true;
1341 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
1344 template <class _Key, class _Tp, class _Compare, class _Allocator>
1346 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1348 __parent_pointer __parent;
1349 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1350 __node_pointer __r = static_cast<__node_pointer>(__child);
1351 if (__child == nullptr)
1353 __node_holder __h = __construct_node_with_key(__k);
1354 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1355 __r = __h.release();
1357 return __r->__value_.__cc.second;
1362 template <class _Key, class _Tp, class _Compare, class _Allocator>
1364 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1366 return __tree_.__emplace_unique_key_args(__k,
1367 _VSTD::piecewise_construct,
1368 _VSTD::forward_as_tuple(__k),
1369 _VSTD::forward_as_tuple()).first->__cc.second;
1372 template <class _Key, class _Tp, class _Compare, class _Allocator>
1374 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1376 return __tree_.__emplace_unique_key_args(__k,
1377 _VSTD::piecewise_construct,
1378 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1379 _VSTD::forward_as_tuple()).first->__cc.second;
1382 #endif // !_LIBCPP_CXX03_LANG
1384 template <class _Key, class _Tp, class _Compare, class _Allocator>
1386 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1388 __parent_pointer __parent;
1389 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1390 #ifndef _LIBCPP_NO_EXCEPTIONS
1391 if (__child == nullptr)
1392 throw out_of_range("map::at: key not found");
1393 #endif // _LIBCPP_NO_EXCEPTIONS
1394 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1397 template <class _Key, class _Tp, class _Compare, class _Allocator>
1399 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1401 __parent_pointer __parent;
1402 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1403 #ifndef _LIBCPP_NO_EXCEPTIONS
1404 if (__child == nullptr)
1405 throw out_of_range("map::at: key not found");
1406 #endif // _LIBCPP_NO_EXCEPTIONS
1407 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1411 template <class _Key, class _Tp, class _Compare, class _Allocator>
1412 inline _LIBCPP_INLINE_VISIBILITY
1414 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1415 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1417 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1420 template <class _Key, class _Tp, class _Compare, class _Allocator>
1421 inline _LIBCPP_INLINE_VISIBILITY
1423 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1424 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1426 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1429 template <class _Key, class _Tp, class _Compare, class _Allocator>
1430 inline _LIBCPP_INLINE_VISIBILITY
1432 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1433 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1435 return !(__x == __y);
1438 template <class _Key, class _Tp, class _Compare, class _Allocator>
1439 inline _LIBCPP_INLINE_VISIBILITY
1441 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1442 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1447 template <class _Key, class _Tp, class _Compare, class _Allocator>
1448 inline _LIBCPP_INLINE_VISIBILITY
1450 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1451 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1453 return !(__x < __y);
1456 template <class _Key, class _Tp, class _Compare, class _Allocator>
1457 inline _LIBCPP_INLINE_VISIBILITY
1459 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1460 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1462 return !(__y < __x);
1465 template <class _Key, class _Tp, class _Compare, class _Allocator>
1466 inline _LIBCPP_INLINE_VISIBILITY
1468 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1469 map<_Key, _Tp, _Compare, _Allocator>& __y)
1470 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1475 template <class _Key, class _Tp, class _Compare = less<_Key>,
1476 class _Allocator = allocator<pair<const _Key, _Tp> > >
1477 class _LIBCPP_TEMPLATE_VIS multimap
1481 typedef _Key key_type;
1482 typedef _Tp mapped_type;
1483 typedef pair<const key_type, mapped_type> value_type;
1484 typedef pair<key_type, mapped_type> __nc_value_type;
1485 typedef _Compare key_compare;
1486 typedef _Allocator allocator_type;
1487 typedef value_type& reference;
1488 typedef const value_type& const_reference;
1490 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1491 "Allocator::value_type must be same type as value_type");
1493 class _LIBCPP_TEMPLATE_VIS value_compare
1494 : public binary_function<value_type, value_type, bool>
1496 friend class multimap;
1500 _LIBCPP_INLINE_VISIBILITY
1501 value_compare(key_compare c) : comp(c) {}
1503 _LIBCPP_INLINE_VISIBILITY
1504 bool operator()(const value_type& __x, const value_type& __y) const
1505 {return comp(__x.first, __y.first);}
1510 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
1511 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1512 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1513 __value_type>::type __allocator_type;
1514 typedef __tree<__value_type, __vc, __allocator_type> __base;
1515 typedef typename __base::__node_traits __node_traits;
1516 typedef allocator_traits<allocator_type> __alloc_traits;
1521 typedef typename __alloc_traits::pointer pointer;
1522 typedef typename __alloc_traits::const_pointer const_pointer;
1523 typedef typename __alloc_traits::size_type size_type;
1524 typedef typename __alloc_traits::difference_type difference_type;
1525 typedef __map_iterator<typename __base::iterator> iterator;
1526 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1527 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1528 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1530 _LIBCPP_INLINE_VISIBILITY
1533 is_nothrow_default_constructible<allocator_type>::value &&
1534 is_nothrow_default_constructible<key_compare>::value &&
1535 is_nothrow_copy_constructible<key_compare>::value)
1536 : __tree_(__vc(key_compare())) {}
1538 _LIBCPP_INLINE_VISIBILITY
1539 explicit multimap(const key_compare& __comp)
1541 is_nothrow_default_constructible<allocator_type>::value &&
1542 is_nothrow_copy_constructible<key_compare>::value)
1543 : __tree_(__vc(__comp)) {}
1545 _LIBCPP_INLINE_VISIBILITY
1546 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1547 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1549 template <class _InputIterator>
1550 _LIBCPP_INLINE_VISIBILITY
1551 multimap(_InputIterator __f, _InputIterator __l,
1552 const key_compare& __comp = key_compare())
1553 : __tree_(__vc(__comp))
1558 template <class _InputIterator>
1559 _LIBCPP_INLINE_VISIBILITY
1560 multimap(_InputIterator __f, _InputIterator __l,
1561 const key_compare& __comp, const allocator_type& __a)
1562 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1567 #if _LIBCPP_STD_VER > 11
1568 template <class _InputIterator>
1569 _LIBCPP_INLINE_VISIBILITY
1570 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1571 : multimap(__f, __l, key_compare(), __a) {}
1574 _LIBCPP_INLINE_VISIBILITY
1575 multimap(const multimap& __m)
1576 : __tree_(__m.__tree_.value_comp(),
1577 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1579 insert(__m.begin(), __m.end());
1582 _LIBCPP_INLINE_VISIBILITY
1583 multimap& operator=(const multimap& __m)
1585 #ifndef _LIBCPP_CXX03_LANG
1586 __tree_ = __m.__tree_;
1590 __tree_.value_comp() = __m.__tree_.value_comp();
1591 __tree_.__copy_assign_alloc(__m.__tree_);
1592 insert(__m.begin(), __m.end());
1598 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1600 _LIBCPP_INLINE_VISIBILITY
1601 multimap(multimap&& __m)
1602 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1603 : __tree_(_VSTD::move(__m.__tree_))
1607 multimap(multimap&& __m, const allocator_type& __a);
1609 _LIBCPP_INLINE_VISIBILITY
1610 multimap& operator=(multimap&& __m)
1611 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1613 __tree_ = _VSTD::move(__m.__tree_);
1617 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1619 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1621 _LIBCPP_INLINE_VISIBILITY
1622 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1623 : __tree_(__vc(__comp))
1625 insert(__il.begin(), __il.end());
1628 _LIBCPP_INLINE_VISIBILITY
1629 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1630 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1632 insert(__il.begin(), __il.end());
1635 #if _LIBCPP_STD_VER > 11
1636 _LIBCPP_INLINE_VISIBILITY
1637 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1638 : multimap(__il, key_compare(), __a) {}
1641 _LIBCPP_INLINE_VISIBILITY
1642 multimap& operator=(initializer_list<value_type> __il)
1644 __tree_.__assign_multi(__il.begin(), __il.end());
1648 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1650 _LIBCPP_INLINE_VISIBILITY
1651 explicit multimap(const allocator_type& __a)
1652 : __tree_(typename __base::allocator_type(__a))
1656 _LIBCPP_INLINE_VISIBILITY
1657 multimap(const multimap& __m, const allocator_type& __a)
1658 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1660 insert(__m.begin(), __m.end());
1663 _LIBCPP_INLINE_VISIBILITY
1664 iterator begin() _NOEXCEPT {return __tree_.begin();}
1665 _LIBCPP_INLINE_VISIBILITY
1666 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1667 _LIBCPP_INLINE_VISIBILITY
1668 iterator end() _NOEXCEPT {return __tree_.end();}
1669 _LIBCPP_INLINE_VISIBILITY
1670 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1672 _LIBCPP_INLINE_VISIBILITY
1673 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1674 _LIBCPP_INLINE_VISIBILITY
1675 const_reverse_iterator rbegin() const _NOEXCEPT
1676 {return const_reverse_iterator(end());}
1677 _LIBCPP_INLINE_VISIBILITY
1678 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1679 _LIBCPP_INLINE_VISIBILITY
1680 const_reverse_iterator rend() const _NOEXCEPT
1681 {return const_reverse_iterator(begin());}
1683 _LIBCPP_INLINE_VISIBILITY
1684 const_iterator cbegin() const _NOEXCEPT {return begin();}
1685 _LIBCPP_INLINE_VISIBILITY
1686 const_iterator cend() const _NOEXCEPT {return end();}
1687 _LIBCPP_INLINE_VISIBILITY
1688 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1689 _LIBCPP_INLINE_VISIBILITY
1690 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1692 _LIBCPP_INLINE_VISIBILITY
1693 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1694 _LIBCPP_INLINE_VISIBILITY
1695 size_type size() const _NOEXCEPT {return __tree_.size();}
1696 _LIBCPP_INLINE_VISIBILITY
1697 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1699 _LIBCPP_INLINE_VISIBILITY
1700 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1701 _LIBCPP_INLINE_VISIBILITY
1702 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1703 _LIBCPP_INLINE_VISIBILITY
1704 value_compare value_comp() const
1705 {return value_compare(__tree_.value_comp().key_comp());}
1707 #ifndef _LIBCPP_CXX03_LANG
1709 template <class ..._Args>
1710 _LIBCPP_INLINE_VISIBILITY
1711 iterator emplace(_Args&& ...__args) {
1712 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1715 template <class ..._Args>
1716 _LIBCPP_INLINE_VISIBILITY
1717 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1718 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1721 template <class _Pp,
1722 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1723 _LIBCPP_INLINE_VISIBILITY
1724 iterator insert(_Pp&& __p)
1725 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1727 template <class _Pp,
1728 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1729 _LIBCPP_INLINE_VISIBILITY
1730 iterator insert(const_iterator __pos, _Pp&& __p)
1731 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1733 _LIBCPP_INLINE_VISIBILITY
1734 iterator insert(value_type&& __v)
1735 {return __tree_.__insert_multi(_VSTD::move(__v));}
1737 _LIBCPP_INLINE_VISIBILITY
1738 iterator insert(const_iterator __p, value_type&& __v)
1739 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1741 #endif // _LIBCPP_CXX03_LANG
1743 _LIBCPP_INLINE_VISIBILITY
1744 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1746 _LIBCPP_INLINE_VISIBILITY
1747 iterator insert(const_iterator __p, const value_type& __v)
1748 {return __tree_.__insert_multi(__p.__i_, __v);}
1750 template <class _InputIterator>
1751 _LIBCPP_INLINE_VISIBILITY
1752 void insert(_InputIterator __f, _InputIterator __l)
1754 for (const_iterator __e = cend(); __f != __l; ++__f)
1755 __tree_.__insert_multi(__e.__i_, *__f);
1758 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1760 _LIBCPP_INLINE_VISIBILITY
1761 void insert(initializer_list<value_type> __il)
1762 {insert(__il.begin(), __il.end());}
1764 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1766 _LIBCPP_INLINE_VISIBILITY
1767 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1768 _LIBCPP_INLINE_VISIBILITY
1769 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1770 _LIBCPP_INLINE_VISIBILITY
1771 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1772 _LIBCPP_INLINE_VISIBILITY
1773 iterator erase(const_iterator __f, const_iterator __l)
1774 {return __tree_.erase(__f.__i_, __l.__i_);}
1775 _LIBCPP_INLINE_VISIBILITY
1776 void clear() {__tree_.clear();}
1778 _LIBCPP_INLINE_VISIBILITY
1779 void swap(multimap& __m)
1780 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1781 {__tree_.swap(__m.__tree_);}
1783 _LIBCPP_INLINE_VISIBILITY
1784 iterator find(const key_type& __k) {return __tree_.find(__k);}
1785 _LIBCPP_INLINE_VISIBILITY
1786 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1787 #if _LIBCPP_STD_VER > 11
1788 template <typename _K2>
1789 _LIBCPP_INLINE_VISIBILITY
1790 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1791 find(const _K2& __k) {return __tree_.find(__k);}
1792 template <typename _K2>
1793 _LIBCPP_INLINE_VISIBILITY
1794 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1795 find(const _K2& __k) const {return __tree_.find(__k);}
1798 _LIBCPP_INLINE_VISIBILITY
1799 size_type count(const key_type& __k) const
1800 {return __tree_.__count_multi(__k);}
1801 #if _LIBCPP_STD_VER > 11
1802 template <typename _K2>
1803 _LIBCPP_INLINE_VISIBILITY
1804 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1805 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
1807 _LIBCPP_INLINE_VISIBILITY
1808 iterator lower_bound(const key_type& __k)
1809 {return __tree_.lower_bound(__k);}
1810 _LIBCPP_INLINE_VISIBILITY
1811 const_iterator lower_bound(const key_type& __k) const
1812 {return __tree_.lower_bound(__k);}
1813 #if _LIBCPP_STD_VER > 11
1814 template <typename _K2>
1815 _LIBCPP_INLINE_VISIBILITY
1816 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1817 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1819 template <typename _K2>
1820 _LIBCPP_INLINE_VISIBILITY
1821 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1822 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1825 _LIBCPP_INLINE_VISIBILITY
1826 iterator upper_bound(const key_type& __k)
1827 {return __tree_.upper_bound(__k);}
1828 _LIBCPP_INLINE_VISIBILITY
1829 const_iterator upper_bound(const key_type& __k) const
1830 {return __tree_.upper_bound(__k);}
1831 #if _LIBCPP_STD_VER > 11
1832 template <typename _K2>
1833 _LIBCPP_INLINE_VISIBILITY
1834 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1835 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1836 template <typename _K2>
1837 _LIBCPP_INLINE_VISIBILITY
1838 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1839 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1842 _LIBCPP_INLINE_VISIBILITY
1843 pair<iterator,iterator> equal_range(const key_type& __k)
1844 {return __tree_.__equal_range_multi(__k);}
1845 _LIBCPP_INLINE_VISIBILITY
1846 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1847 {return __tree_.__equal_range_multi(__k);}
1848 #if _LIBCPP_STD_VER > 11
1849 template <typename _K2>
1850 _LIBCPP_INLINE_VISIBILITY
1851 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1852 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1853 template <typename _K2>
1854 _LIBCPP_INLINE_VISIBILITY
1855 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1856 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1860 typedef typename __base::__node __node;
1861 typedef typename __base::__node_allocator __node_allocator;
1862 typedef typename __base::__node_pointer __node_pointer;
1864 typedef __map_node_destructor<__node_allocator> _Dp;
1865 typedef unique_ptr<__node, _Dp> __node_holder;
1868 #ifndef _LIBCPP_CXX03_LANG
1869 template <class _Key, class _Tp, class _Compare, class _Allocator>
1870 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1871 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1873 if (__a != __m.get_allocator())
1875 const_iterator __e = cend();
1876 while (!__m.empty())
1877 __tree_.__insert_multi(__e.__i_,
1878 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
1883 template <class _Key, class _Tp, class _Compare, class _Allocator>
1884 inline _LIBCPP_INLINE_VISIBILITY
1886 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1887 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1889 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1892 template <class _Key, class _Tp, class _Compare, class _Allocator>
1893 inline _LIBCPP_INLINE_VISIBILITY
1895 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1896 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1898 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1901 template <class _Key, class _Tp, class _Compare, class _Allocator>
1902 inline _LIBCPP_INLINE_VISIBILITY
1904 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1905 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1907 return !(__x == __y);
1910 template <class _Key, class _Tp, class _Compare, class _Allocator>
1911 inline _LIBCPP_INLINE_VISIBILITY
1913 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1914 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1919 template <class _Key, class _Tp, class _Compare, class _Allocator>
1920 inline _LIBCPP_INLINE_VISIBILITY
1922 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1923 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1925 return !(__x < __y);
1928 template <class _Key, class _Tp, class _Compare, class _Allocator>
1929 inline _LIBCPP_INLINE_VISIBILITY
1931 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1932 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1934 return !(__y < __x);
1937 template <class _Key, class _Tp, class _Compare, class _Allocator>
1938 inline _LIBCPP_INLINE_VISIBILITY
1940 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1941 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1942 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1947 _LIBCPP_END_NAMESPACE_STD
1949 #endif // _LIBCPP_MAP