1// -*- C++ -*-
2//===----------------------------- map ------------------------------------===//
3//
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
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_MAP
11#define _LIBCPP_MAP
12
13/*
14
15 map synopsis
16
17namespace std
18{
19
20template <class Key, class T, class Compare = less<Key>,
21 class Allocator = allocator<pair<const Key, T>>>
22class map
23{
24public:
25 // types:
26 typedef Key key_type;
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;
37
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
44
45 class value_compare
46 : public binary_function<value_type, value_type, bool>
47 {
48 friend class map;
49 protected:
50 key_compare comp;
51
52 value_compare(key_compare c);
53 public:
54 bool operator()(const value_type& x, const value_type& y) const;
55 };
56
57 // construct/copy/destroy:
58 map()
59 noexcept(
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);
71 map(const map& m);
72 map(map&& m)
73 noexcept(
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
86 ~map();
87
88 map& operator=(const map& m);
89 map& operator=(map&& m)
90 noexcept(
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);
95
96 // iterators:
97 iterator begin() noexcept;
98 const_iterator begin() const noexcept;
99 iterator end() noexcept;
100 const_iterator end() const noexcept;
101
102 reverse_iterator rbegin() noexcept;
103 const_reverse_iterator rbegin() const noexcept;
104 reverse_iterator rend() noexcept;
105 const_reverse_iterator rend() const noexcept;
106
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;
111
112 // capacity:
113 bool empty() const noexcept;
114 size_type size() const noexcept;
115 size_type max_size() const noexcept;
116
117 // element access:
118 mapped_type& operator[](const key_type& k);
119 mapped_type& operator[](key_type&& k);
120
121 mapped_type& at(const key_type& k);
122 const mapped_type& at(const key_type& k) const;
123
124 // modifiers:
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
131 template <class P>
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
135 template <class P>
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);
140
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
145
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
154 template <class M>
155 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
156 template <class M>
157 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
158 template <class M>
159 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
160 template <class M>
161 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
162
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;
168
169 template<class C2>
170 void merge(map<Key, T, C2, Allocator>& source); // C++17
171 template<class C2>
172 void merge(map<Key, T, C2, Allocator>&& source); // C++17
173 template<class C2>
174 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
175 template<class C2>
176 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
177
178 void swap(map& m)
179 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
180 is_nothrow_swappable<key_compare>::value); // C++17
181
182 // observers:
183 allocator_type get_allocator() const noexcept;
184 key_compare key_comp() const;
185 value_compare value_comp() const;
186
187 // map operations:
188 iterator find(const key_type& k);
189 const_iterator find(const key_type& k) const;
190 template<typename K>
191 iterator find(const K& x); // C++14
192 template<typename K>
193 const_iterator find(const K& x) const; // C++14
194 template<typename K>
195 size_type count(const K& x) const; // C++14
196
197 size_type count(const key_type& k) const;
198 iterator lower_bound(const key_type& k);
199 const_iterator lower_bound(const key_type& k) const;
200 template<typename K>
201 iterator lower_bound(const K& x); // C++14
202 template<typename K>
203 const_iterator lower_bound(const K& x) const; // C++14
204
205 iterator upper_bound(const key_type& k);
206 const_iterator upper_bound(const key_type& k) const;
207 template<typename K>
208 iterator upper_bound(const K& x); // C++14
209 template<typename K>
210 const_iterator upper_bound(const K& x) const; // C++14
211
212 pair<iterator,iterator> equal_range(const key_type& k);
213 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
214 template<typename K>
215 pair<iterator,iterator> equal_range(const K& x); // C++14
216 template<typename K>
217 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
218};
219
220template <class Key, class T, class Compare, class Allocator>
221bool
222operator==(const map<Key, T, Compare, Allocator>& x,
223 const map<Key, T, Compare, Allocator>& y);
224
225template <class Key, class T, class Compare, class Allocator>
226bool
227operator< (const map<Key, T, Compare, Allocator>& x,
228 const map<Key, T, Compare, Allocator>& y);
229
230template <class Key, class T, class Compare, class Allocator>
231bool
232operator!=(const map<Key, T, Compare, Allocator>& x,
233 const map<Key, T, Compare, Allocator>& y);
234
235template <class Key, class T, class Compare, class Allocator>
236bool
237operator> (const map<Key, T, Compare, Allocator>& x,
238 const map<Key, T, Compare, Allocator>& y);
239
240template <class Key, class T, class Compare, class Allocator>
241bool
242operator>=(const map<Key, T, Compare, Allocator>& x,
243 const map<Key, T, Compare, Allocator>& y);
244
245template <class Key, class T, class Compare, class Allocator>
246bool
247operator<=(const map<Key, T, Compare, Allocator>& x,
248 const map<Key, T, Compare, Allocator>& y);
249
250// specialized algorithms:
251template <class Key, class T, class Compare, class Allocator>
252void
253swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
254 noexcept(noexcept(x.swap(y)));
255
256template <class Key, class T, class Compare, class Allocator, class Predicate>
257 void erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
258
259
260template <class Key, class T, class Compare = less<Key>,
261 class Allocator = allocator<pair<const Key, T>>>
262class multimap
263{
264public:
265 // types:
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;
277
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
283
284 class value_compare
285 : public binary_function<value_type,value_type,bool>
286 {
287 friend class multimap;
288 protected:
289 key_compare comp;
290 value_compare(key_compare c);
291 public:
292 bool operator()(const value_type& x, const value_type& y) const;
293 };
294
295 // construct/copy/destroy:
296 multimap()
297 noexcept(
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)
310 noexcept(
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
324 ~multimap();
325
326 multimap& operator=(const multimap& m);
327 multimap& operator=(multimap&& m)
328 noexcept(
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);
333
334 // iterators:
335 iterator begin() noexcept;
336 const_iterator begin() const noexcept;
337 iterator end() noexcept;
338 const_iterator end() const noexcept;
339
340 reverse_iterator rbegin() noexcept;
341 const_reverse_iterator rbegin() const noexcept;
342 reverse_iterator rend() noexcept;
343 const_reverse_iterator rend() const noexcept;
344
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;
349
350 // capacity:
351 bool empty() const noexcept;
352 size_type size() const noexcept;
353 size_type max_size() const noexcept;
354
355 // modifiers:
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
362 template <class P>
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
366 template <class P>
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);
371
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
376
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;
382
383 template<class C2>
384 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
385 template<class C2>
386 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
387 template<class C2>
388 void merge(map<Key, T, C2, Allocator>& source); // C++17
389 template<class C2>
390 void merge(map<Key, T, C2, Allocator>&& source); // C++17
391
392 void swap(multimap& m)
393 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
394 is_nothrow_swappable<key_compare>::value); // C++17
395
396 // observers:
397 allocator_type get_allocator() const noexcept;
398 key_compare key_comp() const;
399 value_compare value_comp() const;
400
401 // map operations:
402 iterator find(const key_type& k);
403 const_iterator find(const key_type& k) const;
404 template<typename K>
405 iterator find(const K& x); // C++14
406 template<typename K>
407 const_iterator find(const K& x) const; // C++14
408 template<typename K>
409 size_type count(const K& x) const; // C++14
410
411 size_type count(const key_type& k) const;
412 iterator lower_bound(const key_type& k);
413 const_iterator lower_bound(const key_type& k) const;
414 template<typename K>
415 iterator lower_bound(const K& x); // C++14
416 template<typename K>
417 const_iterator lower_bound(const K& x) const; // C++14
418
419 iterator upper_bound(const key_type& k);
420 const_iterator upper_bound(const key_type& k) const;
421 template<typename K>
422 iterator upper_bound(const K& x); // C++14
423 template<typename K>
424 const_iterator upper_bound(const K& x) const; // C++14
425
426 pair<iterator,iterator> equal_range(const key_type& k);
427 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
428 template<typename K>
429 pair<iterator,iterator> equal_range(const K& x); // C++14
430 template<typename K>
431 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
432};
433
434template <class Key, class T, class Compare, class Allocator>
435bool
436operator==(const multimap<Key, T, Compare, Allocator>& x,
437 const multimap<Key, T, Compare, Allocator>& y);
438
439template <class Key, class T, class Compare, class Allocator>
440bool
441operator< (const multimap<Key, T, Compare, Allocator>& x,
442 const multimap<Key, T, Compare, Allocator>& y);
443
444template <class Key, class T, class Compare, class Allocator>
445bool
446operator!=(const multimap<Key, T, Compare, Allocator>& x,
447 const multimap<Key, T, Compare, Allocator>& y);
448
449template <class Key, class T, class Compare, class Allocator>
450bool
451operator> (const multimap<Key, T, Compare, Allocator>& x,
452 const multimap<Key, T, Compare, Allocator>& y);
453
454template <class Key, class T, class Compare, class Allocator>
455bool
456operator>=(const multimap<Key, T, Compare, Allocator>& x,
457 const multimap<Key, T, Compare, Allocator>& y);
458
459template <class Key, class T, class Compare, class Allocator>
460bool
461operator<=(const multimap<Key, T, Compare, Allocator>& x,
462 const multimap<Key, T, Compare, Allocator>& y);
463
464// specialized algorithms:
465template <class Key, class T, class Compare, class Allocator>
466void
467swap(multimap<Key, T, Compare, Allocator>& x,
468 multimap<Key, T, Compare, Allocator>& y)
469 noexcept(noexcept(x.swap(y)));
470
471template <class Key, class T, class Compare, class Allocator, class Predicate>
472 void erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
473
474} // std
475
476*/
477
478#include <__config>
479#include <__tree>
480#include <__node_handle>
481#include <iterator>
482#include <memory>
483#include <utility>
484#include <functional>
485#include <initializer_list>
486#include <type_traits>
487#include <version>
488
489#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
490#pragma GCC system_header
491#endif
492
493_LIBCPP_BEGIN_NAMESPACE_STD
494
495template <class _Key, class _CP, class _Compare,
496 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
497class __map_value_compare
498 : private _Compare
499{
500public:
501 _LIBCPP_INLINE_VISIBILITY
502 __map_value_compare()
503 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
504 : _Compare() {}
505 _LIBCPP_INLINE_VISIBILITY
506 __map_value_compare(_Compare c)
507 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
508 : _Compare(c) {}
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)
522 {
523 using _VSTD::swap;
524 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
525 }
526
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);}
533
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);}
539#endif
540};
541
542template <class _Key, class _CP, class _Compare>
543class __map_value_compare<_Key, _CP, _Compare, false>
544{
545 _Compare comp;
546
547public:
548 _LIBCPP_INLINE_VISIBILITY
549 __map_value_compare()
550 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
551 : comp() {}
552 _LIBCPP_INLINE_VISIBILITY
553 __map_value_compare(_Compare c)
554 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
555 : comp(c) {}
556 _LIBCPP_INLINE_VISIBILITY
557 const _Compare& key_comp() const _NOEXCEPT {return comp;}
558
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)
570 {
571 using _VSTD::swap;
572 swap(comp, __y.comp);
573 }
574
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);}
581
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);}
587#endif
588};
589
590template <class _Key, class _CP, class _Compare, bool __b>
591inline _LIBCPP_INLINE_VISIBILITY
592void
593swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
594 __map_value_compare<_Key, _CP, _Compare, __b>& __y)
595 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
596{
597 __x.swap(__y);
598}
599
600template <class _Allocator>
601class __map_node_destructor
602{
603 typedef _Allocator allocator_type;
604 typedef allocator_traits<allocator_type> __alloc_traits;
605
606public:
607 typedef typename __alloc_traits::pointer pointer;
608
609private:
610 allocator_type& __na_;
611
612 __map_node_destructor& operator=(const __map_node_destructor&);
613
614public:
615 bool __first_constructed;
616 bool __second_constructed;
617
618 _LIBCPP_INLINE_VISIBILITY
619 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
620 : __na_(__na),
621 __first_constructed(false),
622 __second_constructed(false)
623 {}
624
625#ifndef _LIBCPP_CXX03_LANG
626 _LIBCPP_INLINE_VISIBILITY
627 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
628 : __na_(__x.__na_),
629 __first_constructed(__x.__value_constructed),
630 __second_constructed(__x.__value_constructed)
631 {
632 __x.__value_constructed = false;
633 }
634#endif // _LIBCPP_CXX03_LANG
635
636 _LIBCPP_INLINE_VISIBILITY
637 void operator()(pointer __p) _NOEXCEPT
638 {
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));
643 if (__p)
644 __alloc_traits::deallocate(__na_, __p, 1);
645 }
646};
647
648template <class _Key, class _Tp, class _Compare, class _Allocator>
649 class map;
650template <class _Key, class _Tp, class _Compare, class _Allocator>
651 class multimap;
652template <class _TreeIterator> class __map_const_iterator;
653
654#ifndef _LIBCPP_CXX03_LANG
655
656template <class _Key, class _Tp>
657struct __value_type
658{
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;
664
665private:
666 value_type __cc;
667
668public:
669 _LIBCPP_INLINE_VISIBILITY
670 value_type& __get_value()
671 {
672#if _LIBCPP_STD_VER > 14
673 return *_VSTD::launder(_VSTD::addressof(__cc));
674#else
675 return __cc;
676#endif
677 }
678
679 _LIBCPP_INLINE_VISIBILITY
680 const value_type& __get_value() const
681 {
682#if _LIBCPP_STD_VER > 14
683 return *_VSTD::launder(_VSTD::addressof(__cc));
684#else
685 return __cc;
686#endif
687 }
688
689 _LIBCPP_INLINE_VISIBILITY
690 __nc_ref_pair_type __ref()
691 {
692 value_type& __v = __get_value();
693 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
694 }
695
696 _LIBCPP_INLINE_VISIBILITY
697 __nc_rref_pair_type __move()
698 {
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));
703 }
704
705 _LIBCPP_INLINE_VISIBILITY
706 __value_type& operator=(const __value_type& __v)
707 {
708 __ref() = __v.__get_value();
709 return *this;
710 }
711
712 _LIBCPP_INLINE_VISIBILITY
713 __value_type& operator=(__value_type&& __v)
714 {
715 __ref() = __v.__move();
716 return *this;
717 }
718
719 template <class _ValueTp,
720 class = typename enable_if<
721 __is_same_uncvref<_ValueTp, value_type>::value
722 >::type
723 >
724 _LIBCPP_INLINE_VISIBILITY
725 __value_type& operator=(_ValueTp&& __v)
726 {
727 __ref() = _VSTD::forward<_ValueTp>(__v);
728 return *this;
729 }
730
731private:
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;
736};
737
738#else
739
740template <class _Key, class _Tp>
741struct __value_type
742{
743 typedef _Key key_type;
744 typedef _Tp mapped_type;
745 typedef pair<const key_type, mapped_type> value_type;
746
747private:
748 value_type __cc;
749
750public:
751 _LIBCPP_INLINE_VISIBILITY
752 value_type& __get_value() { return __cc; }
753 _LIBCPP_INLINE_VISIBILITY
754 const value_type& __get_value() const { return __cc; }
755
756private:
757 __value_type();
758 __value_type(__value_type const&);
759 __value_type& operator=(__value_type const&);
760 ~__value_type();
761};
762
763#endif // _LIBCPP_CXX03_LANG
764
765template <class _Tp>
766struct __extract_key_value_types;
767
768template <class _Key, class _Tp>
769struct __extract_key_value_types<__value_type<_Key, _Tp> >
770{
771 typedef _Key const __key_type;
772 typedef _Tp __mapped_type;
773};
774
775template <class _TreeIterator>
776class _LIBCPP_TEMPLATE_VIS __map_iterator
777{
778 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
779 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
780
781 _TreeIterator __i_;
782
783public:
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;
789
790 _LIBCPP_INLINE_VISIBILITY
791 __map_iterator() _NOEXCEPT {}
792
793 _LIBCPP_INLINE_VISIBILITY
794 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
795
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());}
800
801 _LIBCPP_INLINE_VISIBILITY
802 __map_iterator& operator++() {++__i_; return *this;}
803 _LIBCPP_INLINE_VISIBILITY
804 __map_iterator operator++(int)
805 {
806 __map_iterator __t(*this);
807 ++(*this);
808 return __t;
809 }
810
811 _LIBCPP_INLINE_VISIBILITY
812 __map_iterator& operator--() {--__i_; return *this;}
813 _LIBCPP_INLINE_VISIBILITY
814 __map_iterator operator--(int)
815 {
816 __map_iterator __t(*this);
817 --(*this);
818 return __t;
819 }
820
821 friend _LIBCPP_INLINE_VISIBILITY
822 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
823 {return __x.__i_ == __y.__i_;}
824 friend
825 _LIBCPP_INLINE_VISIBILITY
826 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
827 {return __x.__i_ != __y.__i_;}
828
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;
832};
833
834template <class _TreeIterator>
835class _LIBCPP_TEMPLATE_VIS __map_const_iterator
836{
837 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
838 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
839
840 _TreeIterator __i_;
841
842public:
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;
848
849 _LIBCPP_INLINE_VISIBILITY
850 __map_const_iterator() _NOEXCEPT {}
851
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
857 : __i_(__i.__i_) {}
858
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());}
863
864 _LIBCPP_INLINE_VISIBILITY
865 __map_const_iterator& operator++() {++__i_; return *this;}
866 _LIBCPP_INLINE_VISIBILITY
867 __map_const_iterator operator++(int)
868 {
869 __map_const_iterator __t(*this);
870 ++(*this);
871 return __t;
872 }
873
874 _LIBCPP_INLINE_VISIBILITY
875 __map_const_iterator& operator--() {--__i_; return *this;}
876 _LIBCPP_INLINE_VISIBILITY
877 __map_const_iterator operator--(int)
878 {
879 __map_const_iterator __t(*this);
880 --(*this);
881 return __t;
882 }
883
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_;}
890
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;
894};
895
896template <class _Key, class _Tp, class _Compare = less<_Key>,
897 class _Allocator = allocator<pair<const _Key, _Tp> > >
898class _LIBCPP_TEMPLATE_VIS map
899{
900public:
901 // types:
902 typedef _Key key_type;
903 typedef _Tp mapped_type;
904 typedef pair<const key_type, mapped_type> value_type;
905 typedef _Compare key_compare;
906 typedef _Allocator allocator_type;
907 typedef value_type& reference;
908 typedef const value_type& const_reference;
909
910 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
911 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
912 "Allocator::value_type must be same type as value_type");
913
914 class _LIBCPP_TEMPLATE_VIS value_compare
915 : public binary_function<value_type, value_type, bool>
916 {
917 friend class map;
918 protected:
919 key_compare comp;
920
921 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
922 public:
923 _LIBCPP_INLINE_VISIBILITY
924 bool operator()(const value_type& __x, const value_type& __y) const
925 {return comp(__x.first, __y.first);}
926 };
927
928private:
929
930 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
931 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
932 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
933 __value_type>::type __allocator_type;
934 typedef __tree<__value_type, __vc, __allocator_type> __base;
935 typedef typename __base::__node_traits __node_traits;
936 typedef allocator_traits<allocator_type> __alloc_traits;
937
938 __base __tree_;
939
940public:
941 typedef typename __alloc_traits::pointer pointer;
942 typedef typename __alloc_traits::const_pointer const_pointer;
943 typedef typename __alloc_traits::size_type size_type;
944 typedef typename __alloc_traits::difference_type difference_type;
945 typedef __map_iterator<typename __base::iterator> iterator;
946 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
947 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
948 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
949
950#if _LIBCPP_STD_VER > 14
951 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
952 typedef __insert_return_type<iterator, node_type> insert_return_type;
953#endif
954
955 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
956 friend class _LIBCPP_TEMPLATE_VIS map;
957 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
958 friend class _LIBCPP_TEMPLATE_VIS multimap;
959
960 _LIBCPP_INLINE_VISIBILITY
961 map()
962 _NOEXCEPT_(
963 is_nothrow_default_constructible<allocator_type>::value &&
964 is_nothrow_default_constructible<key_compare>::value &&
965 is_nothrow_copy_constructible<key_compare>::value)
966 : __tree_(__vc(key_compare())) {}
967
968 _LIBCPP_INLINE_VISIBILITY
969 explicit map(const key_compare& __comp)
970 _NOEXCEPT_(
971 is_nothrow_default_constructible<allocator_type>::value &&
972 is_nothrow_copy_constructible<key_compare>::value)
973 : __tree_(__vc(__comp)) {}
974
975 _LIBCPP_INLINE_VISIBILITY
976 explicit map(const key_compare& __comp, const allocator_type& __a)
977 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
978
979 template <class _InputIterator>
980 _LIBCPP_INLINE_VISIBILITY
981 map(_InputIterator __f, _InputIterator __l,
982 const key_compare& __comp = key_compare())
983 : __tree_(__vc(__comp))
984 {
985 insert(__f, __l);
986 }
987
988 template <class _InputIterator>
989 _LIBCPP_INLINE_VISIBILITY
990 map(_InputIterator __f, _InputIterator __l,
991 const key_compare& __comp, const allocator_type& __a)
992 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
993 {
994 insert(__f, __l);
995 }
996
997#if _LIBCPP_STD_VER > 11
998 template <class _InputIterator>
999 _LIBCPP_INLINE_VISIBILITY
1000 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1001 : map(__f, __l, key_compare(), __a) {}
1002#endif
1003
1004 _LIBCPP_INLINE_VISIBILITY
1005 map(const map& __m)
1006 : __tree_(__m.__tree_)
1007 {
1008 insert(__m.begin(), __m.end());
1009 }
1010
1011 _LIBCPP_INLINE_VISIBILITY
1012 map& operator=(const map& __m)
1013 {
1014#ifndef _LIBCPP_CXX03_LANG
1015 __tree_ = __m.__tree_;
1016#else
1017 if (this != &__m) {
1018 __tree_.clear();
1019 __tree_.value_comp() = __m.__tree_.value_comp();
1020 __tree_.__copy_assign_alloc(__m.__tree_);
1021 insert(__m.begin(), __m.end());
1022 }
1023#endif
1024 return *this;
1025 }
1026
1027#ifndef _LIBCPP_CXX03_LANG
1028
1029 _LIBCPP_INLINE_VISIBILITY
1030 map(map&& __m)
1031 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1032 : __tree_(_VSTD::move(__m.__tree_))
1033 {
1034 }
1035
1036 map(map&& __m, const allocator_type& __a);
1037
1038 _LIBCPP_INLINE_VISIBILITY
1039 map& operator=(map&& __m)
1040 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1041 {
1042 __tree_ = _VSTD::move(__m.__tree_);
1043 return *this;
1044 }
1045
1046 _LIBCPP_INLINE_VISIBILITY
1047 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1048 : __tree_(__vc(__comp))
1049 {
1050 insert(__il.begin(), __il.end());
1051 }
1052
1053 _LIBCPP_INLINE_VISIBILITY
1054 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1055 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1056 {
1057 insert(__il.begin(), __il.end());
1058 }
1059
1060#if _LIBCPP_STD_VER > 11
1061 _LIBCPP_INLINE_VISIBILITY
1062 map(initializer_list<value_type> __il, const allocator_type& __a)
1063 : map(__il, key_compare(), __a) {}
1064#endif
1065
1066 _LIBCPP_INLINE_VISIBILITY
1067 map& operator=(initializer_list<value_type> __il)
1068 {
1069 __tree_.__assign_unique(__il.begin(), __il.end());
1070 return *this;
1071 }
1072
1073#endif // _LIBCPP_CXX03_LANG
1074
1075 _LIBCPP_INLINE_VISIBILITY
1076 explicit map(const allocator_type& __a)
1077 : __tree_(typename __base::allocator_type(__a))
1078 {
1079 }
1080
1081 _LIBCPP_INLINE_VISIBILITY
1082 map(const map& __m, const allocator_type& __a)
1083 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1084 {
1085 insert(__m.begin(), __m.end());
1086 }
1087
1088 _LIBCPP_INLINE_VISIBILITY
1089 iterator begin() _NOEXCEPT {return __tree_.begin();}
1090 _LIBCPP_INLINE_VISIBILITY
1091 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1092 _LIBCPP_INLINE_VISIBILITY
1093 iterator end() _NOEXCEPT {return __tree_.end();}
1094 _LIBCPP_INLINE_VISIBILITY
1095 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1096
1097 _LIBCPP_INLINE_VISIBILITY
1098 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1099 _LIBCPP_INLINE_VISIBILITY
1100 const_reverse_iterator rbegin() const _NOEXCEPT
1101 {return const_reverse_iterator(end());}
1102 _LIBCPP_INLINE_VISIBILITY
1103 reverse_iterator rend() _NOEXCEPT
1104 {return reverse_iterator(begin());}
1105 _LIBCPP_INLINE_VISIBILITY
1106 const_reverse_iterator rend() const _NOEXCEPT
1107 {return const_reverse_iterator(begin());}
1108
1109 _LIBCPP_INLINE_VISIBILITY
1110 const_iterator cbegin() const _NOEXCEPT {return begin();}
1111 _LIBCPP_INLINE_VISIBILITY
1112 const_iterator cend() const _NOEXCEPT {return end();}
1113 _LIBCPP_INLINE_VISIBILITY
1114 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1115 _LIBCPP_INLINE_VISIBILITY
1116 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1117
1118 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1119 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1120 _LIBCPP_INLINE_VISIBILITY
1121 size_type size() const _NOEXCEPT {return __tree_.size();}
1122 _LIBCPP_INLINE_VISIBILITY
1123 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1124
1125 mapped_type& operator[](const key_type& __k);
1126#ifndef _LIBCPP_CXX03_LANG
1127 mapped_type& operator[](key_type&& __k);
1128#endif
1129
1130 mapped_type& at(const key_type& __k);
1131 const mapped_type& at(const key_type& __k) const;
1132
1133 _LIBCPP_INLINE_VISIBILITY
1134 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1135 _LIBCPP_INLINE_VISIBILITY
1136 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1137 _LIBCPP_INLINE_VISIBILITY
1138 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1139
1140#ifndef _LIBCPP_CXX03_LANG
1141 template <class ..._Args>
1142 _LIBCPP_INLINE_VISIBILITY
1143 pair<iterator, bool> emplace(_Args&& ...__args) {
1144 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1145 }
1146
1147 template <class ..._Args>
1148 _LIBCPP_INLINE_VISIBILITY
1149 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1150 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1151 }
1152
1153 template <class _Pp,
1154 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1155 _LIBCPP_INLINE_VISIBILITY
1156 pair<iterator, bool> insert(_Pp&& __p)
1157 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1158
1159 template <class _Pp,
1160 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1161 _LIBCPP_INLINE_VISIBILITY
1162 iterator insert(const_iterator __pos, _Pp&& __p)
1163 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1164
1165#endif // _LIBCPP_CXX03_LANG
1166
1167 _LIBCPP_INLINE_VISIBILITY
1168 pair<iterator, bool>
1169 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1170
1171 _LIBCPP_INLINE_VISIBILITY
1172 iterator
1173 insert(const_iterator __p, const value_type& __v)
1174 {return __tree_.__insert_unique(__p.__i_, __v);}
1175
1176#ifndef _LIBCPP_CXX03_LANG
1177 _LIBCPP_INLINE_VISIBILITY
1178 pair<iterator, bool>
1179 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
1180
1181 _LIBCPP_INLINE_VISIBILITY
1182 iterator insert(const_iterator __p, value_type&& __v)
1183 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
1184
1185 _LIBCPP_INLINE_VISIBILITY
1186 void insert(initializer_list<value_type> __il)
1187 {insert(__il.begin(), __il.end());}
1188#endif
1189
1190 template <class _InputIterator>
1191 _LIBCPP_INLINE_VISIBILITY
1192 void insert(_InputIterator __f, _InputIterator __l)
1193 {
1194 for (const_iterator __e = cend(); __f != __l; ++__f)
1195 insert(__e.__i_, *__f);
1196 }
1197
1198#if _LIBCPP_STD_VER > 14
1199
1200 template <class... _Args>
1201 _LIBCPP_INLINE_VISIBILITY
1202 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1203 {
1204 return __tree_.__emplace_unique_key_args(__k,
1205 _VSTD::piecewise_construct,
1206 _VSTD::forward_as_tuple(__k),
1207 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1208 }
1209
1210 template <class... _Args>
1211 _LIBCPP_INLINE_VISIBILITY
1212 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1213 {
1214 return __tree_.__emplace_unique_key_args(__k,
1215 _VSTD::piecewise_construct,
1216 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1217 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1218 }
1219
1220 template <class... _Args>
1221 _LIBCPP_INLINE_VISIBILITY
1222 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1223 {
1224 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1225 _VSTD::piecewise_construct,
1226 _VSTD::forward_as_tuple(__k),
1227 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1228 }
1229
1230 template <class... _Args>
1231 _LIBCPP_INLINE_VISIBILITY
1232 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1233 {
1234 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1235 _VSTD::piecewise_construct,
1236 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1237 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1238 }
1239
1240 template <class _Vp>
1241 _LIBCPP_INLINE_VISIBILITY
1242 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1243 {
1244 iterator __p = lower_bound(__k);
1245 if ( __p != end() && !key_comp()(__k, __p->first))
1246 {
1247 __p->second = _VSTD::forward<_Vp>(__v);
1248 return _VSTD::make_pair(__p, false);
1249 }
1250 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1251 }
1252
1253 template <class _Vp>
1254 _LIBCPP_INLINE_VISIBILITY
1255 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1256 {
1257 iterator __p = lower_bound(__k);
1258 if ( __p != end() && !key_comp()(__k, __p->first))
1259 {
1260 __p->second = _VSTD::forward<_Vp>(__v);
1261 return _VSTD::make_pair(__p, false);
1262 }
1263 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1264 }
1265
1266 template <class _Vp>
1267 _LIBCPP_INLINE_VISIBILITY
1268 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1269 {
1270 iterator __p = lower_bound(__k);
1271 if ( __p != end() && !key_comp()(__k, __p->first))
1272 {
1273 __p->second = _VSTD::forward<_Vp>(__v);
1274 return __p;
1275 }
1276 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1277 }
1278
1279 template <class _Vp>
1280 _LIBCPP_INLINE_VISIBILITY
1281 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1282 {
1283 iterator __p = lower_bound(__k);
1284 if ( __p != end() && !key_comp()(__k, __p->first))
1285 {
1286 __p->second = _VSTD::forward<_Vp>(__v);
1287 return __p;
1288 }
1289 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1290 }
1291
1292#endif // _LIBCPP_STD_VER > 14
1293
1294 _LIBCPP_INLINE_VISIBILITY
1295 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1296 _LIBCPP_INLINE_VISIBILITY
1297 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1298 _LIBCPP_INLINE_VISIBILITY
1299 size_type erase(const key_type& __k)
1300 {return __tree_.__erase_unique(__k);}
1301 _LIBCPP_INLINE_VISIBILITY
1302 iterator erase(const_iterator __f, const_iterator __l)
1303 {return __tree_.erase(__f.__i_, __l.__i_);}
1304 _LIBCPP_INLINE_VISIBILITY
1305 void clear() _NOEXCEPT {__tree_.clear();}
1306
1307#if _LIBCPP_STD_VER > 14
1308 _LIBCPP_INLINE_VISIBILITY
1309 insert_return_type insert(node_type&& __nh)
1310 {
1311 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1312 "node_type with incompatible allocator passed to map::insert()");
1313 return __tree_.template __node_handle_insert_unique<
1314 node_type, insert_return_type>(_VSTD::move(__nh));
1315 }
1316 _LIBCPP_INLINE_VISIBILITY
1317 iterator insert(const_iterator __hint, node_type&& __nh)
1318 {
1319 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1320 "node_type with incompatible allocator passed to map::insert()");
1321 return __tree_.template __node_handle_insert_unique<node_type>(
1322 __hint.__i_, _VSTD::move(__nh));
1323 }
1324 _LIBCPP_INLINE_VISIBILITY
1325 node_type extract(key_type const& __key)
1326 {
1327 return __tree_.template __node_handle_extract<node_type>(__key);
1328 }
1329 _LIBCPP_INLINE_VISIBILITY
1330 node_type extract(const_iterator __it)
1331 {
1332 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1333 }
1334 template <class _Compare2>
1335 _LIBCPP_INLINE_VISIBILITY
1336 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
1337 {
1338 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1339 "merging container with incompatible allocator");
1340 __tree_.__node_handle_merge_unique(__source.__tree_);
1341 }
1342 template <class _Compare2>
1343 _LIBCPP_INLINE_VISIBILITY
1344 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
1345 {
1346 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1347 "merging container with incompatible allocator");
1348 __tree_.__node_handle_merge_unique(__source.__tree_);
1349 }
1350 template <class _Compare2>
1351 _LIBCPP_INLINE_VISIBILITY
1352 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
1353 {
1354 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1355 "merging container with incompatible allocator");
1356 __tree_.__node_handle_merge_unique(__source.__tree_);
1357 }
1358 template <class _Compare2>
1359 _LIBCPP_INLINE_VISIBILITY
1360 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
1361 {
1362 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1363 "merging container with incompatible allocator");
1364 __tree_.__node_handle_merge_unique(__source.__tree_);
1365 }
1366#endif
1367
1368 _LIBCPP_INLINE_VISIBILITY
1369 void swap(map& __m)
1370 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1371 {__tree_.swap(__m.__tree_);}
1372
1373 _LIBCPP_INLINE_VISIBILITY
1374 iterator find(const key_type& __k) {return __tree_.find(__k);}
1375 _LIBCPP_INLINE_VISIBILITY
1376 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1377#if _LIBCPP_STD_VER > 11
1378 template <typename _K2>
1379 _LIBCPP_INLINE_VISIBILITY
1380 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1381 find(const _K2& __k) {return __tree_.find(__k);}
1382 template <typename _K2>
1383 _LIBCPP_INLINE_VISIBILITY
1384 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1385 find(const _K2& __k) const {return __tree_.find(__k);}
1386#endif
1387
1388 _LIBCPP_INLINE_VISIBILITY
1389 size_type count(const key_type& __k) const
1390 {return __tree_.__count_unique(__k);}
1391#if _LIBCPP_STD_VER > 11
1392 template <typename _K2>
1393 _LIBCPP_INLINE_VISIBILITY
1394 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1395 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
1396#endif
1397 _LIBCPP_INLINE_VISIBILITY
1398 iterator lower_bound(const key_type& __k)
1399 {return __tree_.lower_bound(__k);}
1400 _LIBCPP_INLINE_VISIBILITY
1401 const_iterator lower_bound(const key_type& __k) const
1402 {return __tree_.lower_bound(__k);}
1403#if _LIBCPP_STD_VER > 11
1404 template <typename _K2>
1405 _LIBCPP_INLINE_VISIBILITY
1406 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1407 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1408
1409 template <typename _K2>
1410 _LIBCPP_INLINE_VISIBILITY
1411 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1412 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1413#endif
1414
1415 _LIBCPP_INLINE_VISIBILITY
1416 iterator upper_bound(const key_type& __k)
1417 {return __tree_.upper_bound(__k);}
1418 _LIBCPP_INLINE_VISIBILITY
1419 const_iterator upper_bound(const key_type& __k) const
1420 {return __tree_.upper_bound(__k);}
1421#if _LIBCPP_STD_VER > 11
1422 template <typename _K2>
1423 _LIBCPP_INLINE_VISIBILITY
1424 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1425 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1426 template <typename _K2>
1427 _LIBCPP_INLINE_VISIBILITY
1428 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1429 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1430#endif
1431
1432 _LIBCPP_INLINE_VISIBILITY
1433 pair<iterator,iterator> equal_range(const key_type& __k)
1434 {return __tree_.__equal_range_unique(__k);}
1435 _LIBCPP_INLINE_VISIBILITY
1436 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1437 {return __tree_.__equal_range_unique(__k);}
1438#if _LIBCPP_STD_VER > 11
1439 template <typename _K2>
1440 _LIBCPP_INLINE_VISIBILITY
1441 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1442 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1443 template <typename _K2>
1444 _LIBCPP_INLINE_VISIBILITY
1445 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1446 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1447#endif
1448
1449private:
1450 typedef typename __base::__node __node;
1451 typedef typename __base::__node_allocator __node_allocator;
1452 typedef typename __base::__node_pointer __node_pointer;
1453 typedef typename __base::__node_base_pointer __node_base_pointer;
1454 typedef typename __base::__parent_pointer __parent_pointer;
1455
1456 typedef __map_node_destructor<__node_allocator> _Dp;
1457 typedef unique_ptr<__node, _Dp> __node_holder;
1458
1459#ifdef _LIBCPP_CXX03_LANG
1460 __node_holder __construct_node_with_key(const key_type& __k);
1461#endif
1462};
1463
1464
1465#ifndef _LIBCPP_CXX03_LANG
1466template <class _Key, class _Tp, class _Compare, class _Allocator>
1467map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1468 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1469{
1470 if (__a != __m.get_allocator())
1471 {
1472 const_iterator __e = cend();
1473 while (!__m.empty())
1474 __tree_.__insert_unique(__e.__i_,
1475 __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
1476 }
1477}
1478
1479template <class _Key, class _Tp, class _Compare, class _Allocator>
1480_Tp&
1481map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1482{
1483 return __tree_.__emplace_unique_key_args(__k,
1484 _VSTD::piecewise_construct,
1485 _VSTD::forward_as_tuple(__k),
1486 _VSTD::forward_as_tuple()).first->__get_value().second;
1487}
1488
1489template <class _Key, class _Tp, class _Compare, class _Allocator>
1490_Tp&
1491map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1492{
1493 return __tree_.__emplace_unique_key_args(__k,
1494 _VSTD::piecewise_construct,
1495 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1496 _VSTD::forward_as_tuple()).first->__get_value().second;
1497}
1498
1499#else // _LIBCPP_CXX03_LANG
1500
1501template <class _Key, class _Tp, class _Compare, class _Allocator>
1502typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1503map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1504{
1505 __node_allocator& __na = __tree_.__node_alloc();
1506 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1507 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
1508 __h.get_deleter().__first_constructed = true;
1509 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
1510 __h.get_deleter().__second_constructed = true;
1511 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
1512}
1513
1514template <class _Key, class _Tp, class _Compare, class _Allocator>
1515_Tp&
1516map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1517{
1518 __parent_pointer __parent;
1519 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1520 __node_pointer __r = static_cast<__node_pointer>(__child);
1521 if (__child == nullptr)
1522 {
1523 __node_holder __h = __construct_node_with_key(__k);
1524 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1525 __r = __h.release();
1526 }
1527 return __r->__value_.__get_value().second;
1528}
1529
1530#endif // _LIBCPP_CXX03_LANG
1531
1532template <class _Key, class _Tp, class _Compare, class _Allocator>
1533_Tp&
1534map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1535{
1536 __parent_pointer __parent;
1537 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1538 if (__child == nullptr)
1539 __throw_out_of_range("map::at: key not found");
1540 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1541}
1542
1543template <class _Key, class _Tp, class _Compare, class _Allocator>
1544const _Tp&
1545map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1546{
1547 __parent_pointer __parent;
1548 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1549 if (__child == nullptr)
1550 __throw_out_of_range("map::at: key not found");
1551 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1552}
1553
1554
1555template <class _Key, class _Tp, class _Compare, class _Allocator>
1556inline _LIBCPP_INLINE_VISIBILITY
1557bool
1558operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1559 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1560{
1561 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1562}
1563
1564template <class _Key, class _Tp, class _Compare, class _Allocator>
1565inline _LIBCPP_INLINE_VISIBILITY
1566bool
1567operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1568 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1569{
1570 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1571}
1572
1573template <class _Key, class _Tp, class _Compare, class _Allocator>
1574inline _LIBCPP_INLINE_VISIBILITY
1575bool
1576operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1577 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1578{
1579 return !(__x == __y);
1580}
1581
1582template <class _Key, class _Tp, class _Compare, class _Allocator>
1583inline _LIBCPP_INLINE_VISIBILITY
1584bool
1585operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1586 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1587{
1588 return __y < __x;
1589}
1590
1591template <class _Key, class _Tp, class _Compare, class _Allocator>
1592inline _LIBCPP_INLINE_VISIBILITY
1593bool
1594operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1595 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1596{
1597 return !(__x < __y);
1598}
1599
1600template <class _Key, class _Tp, class _Compare, class _Allocator>
1601inline _LIBCPP_INLINE_VISIBILITY
1602bool
1603operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1604 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1605{
1606 return !(__y < __x);
1607}
1608
1609template <class _Key, class _Tp, class _Compare, class _Allocator>
1610inline _LIBCPP_INLINE_VISIBILITY
1611void
1612swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1613 map<_Key, _Tp, _Compare, _Allocator>& __y)
1614 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1615{
1616 __x.swap(__y);
1617}
1618
1619#if _LIBCPP_STD_VER > 17
1620template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
1621inline _LIBCPP_INLINE_VISIBILITY
1622void erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred)
1623{ __libcpp_erase_if_container(__c, __pred); }
1624#endif
1625
1626
1627template <class _Key, class _Tp, class _Compare = less<_Key>,
1628 class _Allocator = allocator<pair<const _Key, _Tp> > >
1629class _LIBCPP_TEMPLATE_VIS multimap
1630{
1631public:
1632 // types:
1633 typedef _Key key_type;
1634 typedef _Tp mapped_type;
1635 typedef pair<const key_type, mapped_type> value_type;
1636 typedef _Compare key_compare;
1637 typedef _Allocator allocator_type;
1638 typedef value_type& reference;
1639 typedef const value_type& const_reference;
1640
1641 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1642 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1643 "Allocator::value_type must be same type as value_type");
1644
1645 class _LIBCPP_TEMPLATE_VIS value_compare
1646 : public binary_function<value_type, value_type, bool>
1647 {
1648 friend class multimap;
1649 protected:
1650 key_compare comp;
1651
1652 _LIBCPP_INLINE_VISIBILITY
1653 value_compare(key_compare c) : comp(c) {}
1654 public:
1655 _LIBCPP_INLINE_VISIBILITY
1656 bool operator()(const value_type& __x, const value_type& __y) const
1657 {return comp(__x.first, __y.first);}
1658 };
1659
1660private:
1661
1662 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
1663 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1664 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1665 __value_type>::type __allocator_type;
1666 typedef __tree<__value_type, __vc, __allocator_type> __base;
1667 typedef typename __base::__node_traits __node_traits;
1668 typedef allocator_traits<allocator_type> __alloc_traits;
1669
1670 __base __tree_;
1671
1672public:
1673 typedef typename __alloc_traits::pointer pointer;
1674 typedef typename __alloc_traits::const_pointer const_pointer;
1675 typedef typename __alloc_traits::size_type size_type;
1676 typedef typename __alloc_traits::difference_type difference_type;
1677 typedef __map_iterator<typename __base::iterator> iterator;
1678 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1679 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1680 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1681
1682#if _LIBCPP_STD_VER > 14
1683 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1684#endif
1685
1686 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1687 friend class _LIBCPP_TEMPLATE_VIS map;
1688 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1689 friend class _LIBCPP_TEMPLATE_VIS multimap;
1690
1691 _LIBCPP_INLINE_VISIBILITY
1692 multimap()
1693 _NOEXCEPT_(
1694 is_nothrow_default_constructible<allocator_type>::value &&
1695 is_nothrow_default_constructible<key_compare>::value &&
1696 is_nothrow_copy_constructible<key_compare>::value)
1697 : __tree_(__vc(key_compare())) {}
1698
1699 _LIBCPP_INLINE_VISIBILITY
1700 explicit multimap(const key_compare& __comp)
1701 _NOEXCEPT_(
1702 is_nothrow_default_constructible<allocator_type>::value &&
1703 is_nothrow_copy_constructible<key_compare>::value)
1704 : __tree_(__vc(__comp)) {}
1705
1706 _LIBCPP_INLINE_VISIBILITY
1707 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1708 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1709
1710 template <class _InputIterator>
1711 _LIBCPP_INLINE_VISIBILITY
1712 multimap(_InputIterator __f, _InputIterator __l,
1713 const key_compare& __comp = key_compare())
1714 : __tree_(__vc(__comp))
1715 {
1716 insert(__f, __l);
1717 }
1718
1719 template <class _InputIterator>
1720 _LIBCPP_INLINE_VISIBILITY
1721 multimap(_InputIterator __f, _InputIterator __l,
1722 const key_compare& __comp, const allocator_type& __a)
1723 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1724 {
1725 insert(__f, __l);
1726 }
1727
1728#if _LIBCPP_STD_VER > 11
1729 template <class _InputIterator>
1730 _LIBCPP_INLINE_VISIBILITY
1731 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1732 : multimap(__f, __l, key_compare(), __a) {}
1733#endif
1734
1735 _LIBCPP_INLINE_VISIBILITY
1736 multimap(const multimap& __m)
1737 : __tree_(__m.__tree_.value_comp(),
1738 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1739 {
1740 insert(__m.begin(), __m.end());
1741 }
1742
1743 _LIBCPP_INLINE_VISIBILITY
1744 multimap& operator=(const multimap& __m)
1745 {
1746#ifndef _LIBCPP_CXX03_LANG
1747 __tree_ = __m.__tree_;
1748#else
1749 if (this != &__m) {
1750 __tree_.clear();
1751 __tree_.value_comp() = __m.__tree_.value_comp();
1752 __tree_.__copy_assign_alloc(__m.__tree_);
1753 insert(__m.begin(), __m.end());
1754 }
1755#endif
1756 return *this;
1757 }
1758
1759#ifndef _LIBCPP_CXX03_LANG
1760
1761 _LIBCPP_INLINE_VISIBILITY
1762 multimap(multimap&& __m)
1763 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1764 : __tree_(_VSTD::move(__m.__tree_))
1765 {
1766 }
1767
1768 multimap(multimap&& __m, const allocator_type& __a);
1769
1770 _LIBCPP_INLINE_VISIBILITY
1771 multimap& operator=(multimap&& __m)
1772 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1773 {
1774 __tree_ = _VSTD::move(__m.__tree_);
1775 return *this;
1776 }
1777
1778 _LIBCPP_INLINE_VISIBILITY
1779 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1780 : __tree_(__vc(__comp))
1781 {
1782 insert(__il.begin(), __il.end());
1783 }
1784
1785 _LIBCPP_INLINE_VISIBILITY
1786 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1787 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1788 {
1789 insert(__il.begin(), __il.end());
1790 }
1791
1792#if _LIBCPP_STD_VER > 11
1793 _LIBCPP_INLINE_VISIBILITY
1794 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1795 : multimap(__il, key_compare(), __a) {}
1796#endif
1797
1798 _LIBCPP_INLINE_VISIBILITY
1799 multimap& operator=(initializer_list<value_type> __il)
1800 {
1801 __tree_.__assign_multi(__il.begin(), __il.end());
1802 return *this;
1803 }
1804
1805#endif // _LIBCPP_CXX03_LANG
1806
1807 _LIBCPP_INLINE_VISIBILITY
1808 explicit multimap(const allocator_type& __a)
1809 : __tree_(typename __base::allocator_type(__a))
1810 {
1811 }
1812
1813 _LIBCPP_INLINE_VISIBILITY
1814 multimap(const multimap& __m, const allocator_type& __a)
1815 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1816 {
1817 insert(__m.begin(), __m.end());
1818 }
1819
1820 _LIBCPP_INLINE_VISIBILITY
1821 iterator begin() _NOEXCEPT {return __tree_.begin();}
1822 _LIBCPP_INLINE_VISIBILITY
1823 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1824 _LIBCPP_INLINE_VISIBILITY
1825 iterator end() _NOEXCEPT {return __tree_.end();}
1826 _LIBCPP_INLINE_VISIBILITY
1827 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1828
1829 _LIBCPP_INLINE_VISIBILITY
1830 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1831 _LIBCPP_INLINE_VISIBILITY
1832 const_reverse_iterator rbegin() const _NOEXCEPT
1833 {return const_reverse_iterator(end());}
1834 _LIBCPP_INLINE_VISIBILITY
1835 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1836 _LIBCPP_INLINE_VISIBILITY
1837 const_reverse_iterator rend() const _NOEXCEPT
1838 {return const_reverse_iterator(begin());}
1839
1840 _LIBCPP_INLINE_VISIBILITY
1841 const_iterator cbegin() const _NOEXCEPT {return begin();}
1842 _LIBCPP_INLINE_VISIBILITY
1843 const_iterator cend() const _NOEXCEPT {return end();}
1844 _LIBCPP_INLINE_VISIBILITY
1845 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1846 _LIBCPP_INLINE_VISIBILITY
1847 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1848
1849 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1850 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1851 _LIBCPP_INLINE_VISIBILITY
1852 size_type size() const _NOEXCEPT {return __tree_.size();}
1853 _LIBCPP_INLINE_VISIBILITY
1854 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1855
1856 _LIBCPP_INLINE_VISIBILITY
1857 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1858 _LIBCPP_INLINE_VISIBILITY
1859 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1860 _LIBCPP_INLINE_VISIBILITY
1861 value_compare value_comp() const
1862 {return value_compare(__tree_.value_comp().key_comp());}
1863
1864#ifndef _LIBCPP_CXX03_LANG
1865
1866 template <class ..._Args>
1867 _LIBCPP_INLINE_VISIBILITY
1868 iterator emplace(_Args&& ...__args) {
1869 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1870 }
1871
1872 template <class ..._Args>
1873 _LIBCPP_INLINE_VISIBILITY
1874 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1875 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1876 }
1877
1878 template <class _Pp,
1879 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1880 _LIBCPP_INLINE_VISIBILITY
1881 iterator insert(_Pp&& __p)
1882 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1883
1884 template <class _Pp,
1885 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1886 _LIBCPP_INLINE_VISIBILITY
1887 iterator insert(const_iterator __pos, _Pp&& __p)
1888 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1889
1890 _LIBCPP_INLINE_VISIBILITY
1891 iterator insert(value_type&& __v)
1892 {return __tree_.__insert_multi(_VSTD::move(__v));}
1893
1894 _LIBCPP_INLINE_VISIBILITY
1895 iterator insert(const_iterator __p, value_type&& __v)
1896 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1897
1898
1899 _LIBCPP_INLINE_VISIBILITY
1900 void insert(initializer_list<value_type> __il)
1901 {insert(__il.begin(), __il.end());}
1902
1903#endif // _LIBCPP_CXX03_LANG
1904
1905 _LIBCPP_INLINE_VISIBILITY
1906 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1907
1908 _LIBCPP_INLINE_VISIBILITY
1909 iterator insert(const_iterator __p, const value_type& __v)
1910 {return __tree_.__insert_multi(__p.__i_, __v);}
1911
1912 template <class _InputIterator>
1913 _LIBCPP_INLINE_VISIBILITY
1914 void insert(_InputIterator __f, _InputIterator __l)
1915 {
1916 for (const_iterator __e = cend(); __f != __l; ++__f)
1917 __tree_.__insert_multi(__e.__i_, *__f);
1918 }
1919
1920 _LIBCPP_INLINE_VISIBILITY
1921 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1922 _LIBCPP_INLINE_VISIBILITY
1923 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1924 _LIBCPP_INLINE_VISIBILITY
1925 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1926 _LIBCPP_INLINE_VISIBILITY
1927 iterator erase(const_iterator __f, const_iterator __l)
1928 {return __tree_.erase(__f.__i_, __l.__i_);}
1929
1930#if _LIBCPP_STD_VER > 14
1931 _LIBCPP_INLINE_VISIBILITY
1932 iterator insert(node_type&& __nh)
1933 {
1934 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1935 "node_type with incompatible allocator passed to multimap::insert()");
1936 return __tree_.template __node_handle_insert_multi<node_type>(
1937 _VSTD::move(__nh));
1938 }
1939 _LIBCPP_INLINE_VISIBILITY
1940 iterator insert(const_iterator __hint, node_type&& __nh)
1941 {
1942 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1943 "node_type with incompatible allocator passed to multimap::insert()");
1944 return __tree_.template __node_handle_insert_multi<node_type>(
1945 __hint.__i_, _VSTD::move(__nh));
1946 }
1947 _LIBCPP_INLINE_VISIBILITY
1948 node_type extract(key_type const& __key)
1949 {
1950 return __tree_.template __node_handle_extract<node_type>(__key);
1951 }
1952 _LIBCPP_INLINE_VISIBILITY
1953 node_type extract(const_iterator __it)
1954 {
1955 return __tree_.template __node_handle_extract<node_type>(
1956 __it.__i_);
1957 }
1958 template <class _Compare2>
1959 _LIBCPP_INLINE_VISIBILITY
1960 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
1961 {
1962 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1963 "merging container with incompatible allocator");
1964 return __tree_.__node_handle_merge_multi(__source.__tree_);
1965 }
1966 template <class _Compare2>
1967 _LIBCPP_INLINE_VISIBILITY
1968 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
1969 {
1970 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1971 "merging container with incompatible allocator");
1972 return __tree_.__node_handle_merge_multi(__source.__tree_);
1973 }
1974 template <class _Compare2>
1975 _LIBCPP_INLINE_VISIBILITY
1976 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
1977 {
1978 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1979 "merging container with incompatible allocator");
1980 return __tree_.__node_handle_merge_multi(__source.__tree_);
1981 }
1982 template <class _Compare2>
1983 _LIBCPP_INLINE_VISIBILITY
1984 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
1985 {
1986 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1987 "merging container with incompatible allocator");
1988 return __tree_.__node_handle_merge_multi(__source.__tree_);
1989 }
1990#endif
1991
1992 _LIBCPP_INLINE_VISIBILITY
1993 void clear() _NOEXCEPT {__tree_.clear();}
1994
1995 _LIBCPP_INLINE_VISIBILITY
1996 void swap(multimap& __m)
1997 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1998 {__tree_.swap(__m.__tree_);}
1999
2000 _LIBCPP_INLINE_VISIBILITY
2001 iterator find(const key_type& __k) {return __tree_.find(__k);}
2002 _LIBCPP_INLINE_VISIBILITY
2003 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
2004#if _LIBCPP_STD_VER > 11
2005 template <typename _K2>
2006 _LIBCPP_INLINE_VISIBILITY
2007 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2008 find(const _K2& __k) {return __tree_.find(__k);}
2009 template <typename _K2>
2010 _LIBCPP_INLINE_VISIBILITY
2011 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2012 find(const _K2& __k) const {return __tree_.find(__k);}
2013#endif
2014
2015 _LIBCPP_INLINE_VISIBILITY
2016 size_type count(const key_type& __k) const
2017 {return __tree_.__count_multi(__k);}
2018#if _LIBCPP_STD_VER > 11
2019 template <typename _K2>
2020 _LIBCPP_INLINE_VISIBILITY
2021 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
2022 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
2023#endif
2024 _LIBCPP_INLINE_VISIBILITY
2025 iterator lower_bound(const key_type& __k)
2026 {return __tree_.lower_bound(__k);}
2027 _LIBCPP_INLINE_VISIBILITY
2028 const_iterator lower_bound(const key_type& __k) const
2029 {return __tree_.lower_bound(__k);}
2030#if _LIBCPP_STD_VER > 11
2031 template <typename _K2>
2032 _LIBCPP_INLINE_VISIBILITY
2033 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2034 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
2035
2036 template <typename _K2>
2037 _LIBCPP_INLINE_VISIBILITY
2038 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2039 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
2040#endif
2041
2042 _LIBCPP_INLINE_VISIBILITY
2043 iterator upper_bound(const key_type& __k)
2044 {return __tree_.upper_bound(__k);}
2045 _LIBCPP_INLINE_VISIBILITY
2046 const_iterator upper_bound(const key_type& __k) const
2047 {return __tree_.upper_bound(__k);}
2048#if _LIBCPP_STD_VER > 11
2049 template <typename _K2>
2050 _LIBCPP_INLINE_VISIBILITY
2051 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2052 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
2053 template <typename _K2>
2054 _LIBCPP_INLINE_VISIBILITY
2055 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2056 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
2057#endif
2058
2059 _LIBCPP_INLINE_VISIBILITY
2060 pair<iterator,iterator> equal_range(const key_type& __k)
2061 {return __tree_.__equal_range_multi(__k);}
2062 _LIBCPP_INLINE_VISIBILITY
2063 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
2064 {return __tree_.__equal_range_multi(__k);}
2065#if _LIBCPP_STD_VER > 11
2066 template <typename _K2>
2067 _LIBCPP_INLINE_VISIBILITY
2068 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
2069 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
2070 template <typename _K2>
2071 _LIBCPP_INLINE_VISIBILITY
2072 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
2073 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
2074#endif
2075
2076private:
2077 typedef typename __base::__node __node;
2078 typedef typename __base::__node_allocator __node_allocator;
2079 typedef typename __base::__node_pointer __node_pointer;
2080
2081 typedef __map_node_destructor<__node_allocator> _Dp;
2082 typedef unique_ptr<__node, _Dp> __node_holder;
2083};
2084
2085#ifndef _LIBCPP_CXX03_LANG
2086template <class _Key, class _Tp, class _Compare, class _Allocator>
2087multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
2088 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
2089{
2090 if (__a != __m.get_allocator())
2091 {
2092 const_iterator __e = cend();
2093 while (!__m.empty())
2094 __tree_.__insert_multi(__e.__i_,
2095 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
2096 }
2097}
2098#endif
2099
2100template <class _Key, class _Tp, class _Compare, class _Allocator>
2101inline _LIBCPP_INLINE_VISIBILITY
2102bool
2103operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2104 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2105{
2106 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2107}
2108
2109template <class _Key, class _Tp, class _Compare, class _Allocator>
2110inline _LIBCPP_INLINE_VISIBILITY
2111bool
2112operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2113 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2114{
2115 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2116}
2117
2118template <class _Key, class _Tp, class _Compare, class _Allocator>
2119inline _LIBCPP_INLINE_VISIBILITY
2120bool
2121operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2122 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2123{
2124 return !(__x == __y);
2125}
2126
2127template <class _Key, class _Tp, class _Compare, class _Allocator>
2128inline _LIBCPP_INLINE_VISIBILITY
2129bool
2130operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2131 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2132{
2133 return __y < __x;
2134}
2135
2136template <class _Key, class _Tp, class _Compare, class _Allocator>
2137inline _LIBCPP_INLINE_VISIBILITY
2138bool
2139operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2140 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2141{
2142 return !(__x < __y);
2143}
2144
2145template <class _Key, class _Tp, class _Compare, class _Allocator>
2146inline _LIBCPP_INLINE_VISIBILITY
2147bool
2148operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2149 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2150{
2151 return !(__y < __x);
2152}
2153
2154template <class _Key, class _Tp, class _Compare, class _Allocator>
2155inline _LIBCPP_INLINE_VISIBILITY
2156void
2157swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2158 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2159 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2160{
2161 __x.swap(__y);
2162}
2163
2164#if _LIBCPP_STD_VER > 17
2165template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
2166inline _LIBCPP_INLINE_VISIBILITY
2167void erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred)
2168{ __libcpp_erase_if_container(__c, __pred); }
2169#endif
2170
2171_LIBCPP_END_NAMESPACE_STD
2172
2173#endif // _LIBCPP_MAP
2174