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 size_type count(const key_type& k) const;
197 bool contains(const key_type& x) const; // C++20
198 iterator lower_bound(const key_type& k);
199 const_iterator lower_bound(const key_type& k) const;
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 size_type count(const key_type& k) const;
411 bool contains(const key_type& x) const; // C++20
412 iterator lower_bound(const key_type& k);
413 const_iterator lower_bound(const key_type& k) const;
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 typename __identity<_Compare>::type key_compare;
906 typedef typename __identity<_Allocator>::type allocator_type;
907 typedef value_type& reference;
908 typedef const value_type& const_reference;
909
910 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
911 "Allocator::value_type must be same type as value_type");
912
913 class _LIBCPP_TEMPLATE_VIS value_compare
914 : public binary_function<value_type, value_type, bool>
915 {
916 friend class map;
917 protected:
918 key_compare comp;
919
920 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
921 public:
922 _LIBCPP_INLINE_VISIBILITY
923 bool operator()(const value_type& __x, const value_type& __y) const
924 {return comp(__x.first, __y.first);}
925 };
926
927private:
928
929 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
930 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
931 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
932 __value_type>::type __allocator_type;
933 typedef __tree<__value_type, __vc, __allocator_type> __base;
934 typedef typename __base::__node_traits __node_traits;
935 typedef allocator_traits<allocator_type> __alloc_traits;
936
937 __base __tree_;
938
939public:
940 typedef typename __alloc_traits::pointer pointer;
941 typedef typename __alloc_traits::const_pointer const_pointer;
942 typedef typename __alloc_traits::size_type size_type;
943 typedef typename __alloc_traits::difference_type difference_type;
944 typedef __map_iterator<typename __base::iterator> iterator;
945 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
946 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
947 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
948
949#if _LIBCPP_STD_VER > 14
950 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
951 typedef __insert_return_type<iterator, node_type> insert_return_type;
952#endif
953
954 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
955 friend class _LIBCPP_TEMPLATE_VIS map;
956 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
957 friend class _LIBCPP_TEMPLATE_VIS multimap;
958
959 _LIBCPP_INLINE_VISIBILITY
960 map()
961 _NOEXCEPT_(
962 is_nothrow_default_constructible<allocator_type>::value &&
963 is_nothrow_default_constructible<key_compare>::value &&
964 is_nothrow_copy_constructible<key_compare>::value)
965 : __tree_(__vc(key_compare())) {}
966
967 _LIBCPP_INLINE_VISIBILITY
968 explicit map(const key_compare& __comp)
969 _NOEXCEPT_(
970 is_nothrow_default_constructible<allocator_type>::value &&
971 is_nothrow_copy_constructible<key_compare>::value)
972 : __tree_(__vc(__comp)) {}
973
974 _LIBCPP_INLINE_VISIBILITY
975 explicit map(const key_compare& __comp, const allocator_type& __a)
976 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
977
978 template <class _InputIterator>
979 _LIBCPP_INLINE_VISIBILITY
980 map(_InputIterator __f, _InputIterator __l,
981 const key_compare& __comp = key_compare())
982 : __tree_(__vc(__comp))
983 {
984 insert(__f, __l);
985 }
986
987 template <class _InputIterator>
988 _LIBCPP_INLINE_VISIBILITY
989 map(_InputIterator __f, _InputIterator __l,
990 const key_compare& __comp, const allocator_type& __a)
991 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
992 {
993 insert(__f, __l);
994 }
995
996#if _LIBCPP_STD_VER > 11
997 template <class _InputIterator>
998 _LIBCPP_INLINE_VISIBILITY
999 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1000 : map(__f, __l, key_compare(), __a) {}
1001#endif
1002
1003 _LIBCPP_INLINE_VISIBILITY
1004 map(const map& __m)
1005 : __tree_(__m.__tree_)
1006 {
1007 insert(__m.begin(), __m.end());
1008 }
1009
1010 _LIBCPP_INLINE_VISIBILITY
1011 map& operator=(const map& __m)
1012 {
1013#ifndef _LIBCPP_CXX03_LANG
1014 __tree_ = __m.__tree_;
1015#else
1016 if (this != &__m) {
1017 __tree_.clear();
1018 __tree_.value_comp() = __m.__tree_.value_comp();
1019 __tree_.__copy_assign_alloc(__m.__tree_);
1020 insert(__m.begin(), __m.end());
1021 }
1022#endif
1023 return *this;
1024 }
1025
1026#ifndef _LIBCPP_CXX03_LANG
1027
1028 _LIBCPP_INLINE_VISIBILITY
1029 map(map&& __m)
1030 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1031 : __tree_(_VSTD::move(__m.__tree_))
1032 {
1033 }
1034
1035 map(map&& __m, const allocator_type& __a);
1036
1037 _LIBCPP_INLINE_VISIBILITY
1038 map& operator=(map&& __m)
1039 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1040 {
1041 __tree_ = _VSTD::move(__m.__tree_);
1042 return *this;
1043 }
1044
1045 _LIBCPP_INLINE_VISIBILITY
1046 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1047 : __tree_(__vc(__comp))
1048 {
1049 insert(__il.begin(), __il.end());
1050 }
1051
1052 _LIBCPP_INLINE_VISIBILITY
1053 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1054 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1055 {
1056 insert(__il.begin(), __il.end());
1057 }
1058
1059#if _LIBCPP_STD_VER > 11
1060 _LIBCPP_INLINE_VISIBILITY
1061 map(initializer_list<value_type> __il, const allocator_type& __a)
1062 : map(__il, key_compare(), __a) {}
1063#endif
1064
1065 _LIBCPP_INLINE_VISIBILITY
1066 map& operator=(initializer_list<value_type> __il)
1067 {
1068 __tree_.__assign_unique(__il.begin(), __il.end());
1069 return *this;
1070 }
1071
1072#endif // _LIBCPP_CXX03_LANG
1073
1074 _LIBCPP_INLINE_VISIBILITY
1075 explicit map(const allocator_type& __a)
1076 : __tree_(typename __base::allocator_type(__a))
1077 {
1078 }
1079
1080 _LIBCPP_INLINE_VISIBILITY
1081 map(const map& __m, const allocator_type& __a)
1082 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1083 {
1084 insert(__m.begin(), __m.end());
1085 }
1086
1087 _LIBCPP_INLINE_VISIBILITY
1088 ~map() {
1089 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1090 }
1091
1092 _LIBCPP_INLINE_VISIBILITY
1093 iterator begin() _NOEXCEPT {return __tree_.begin();}
1094 _LIBCPP_INLINE_VISIBILITY
1095 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1096 _LIBCPP_INLINE_VISIBILITY
1097 iterator end() _NOEXCEPT {return __tree_.end();}
1098 _LIBCPP_INLINE_VISIBILITY
1099 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1100
1101 _LIBCPP_INLINE_VISIBILITY
1102 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1103 _LIBCPP_INLINE_VISIBILITY
1104 const_reverse_iterator rbegin() const _NOEXCEPT
1105 {return const_reverse_iterator(end());}
1106 _LIBCPP_INLINE_VISIBILITY
1107 reverse_iterator rend() _NOEXCEPT
1108 {return reverse_iterator(begin());}
1109 _LIBCPP_INLINE_VISIBILITY
1110 const_reverse_iterator rend() const _NOEXCEPT
1111 {return const_reverse_iterator(begin());}
1112
1113 _LIBCPP_INLINE_VISIBILITY
1114 const_iterator cbegin() const _NOEXCEPT {return begin();}
1115 _LIBCPP_INLINE_VISIBILITY
1116 const_iterator cend() const _NOEXCEPT {return end();}
1117 _LIBCPP_INLINE_VISIBILITY
1118 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1119 _LIBCPP_INLINE_VISIBILITY
1120 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1121
1122 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1123 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1124 _LIBCPP_INLINE_VISIBILITY
1125 size_type size() const _NOEXCEPT {return __tree_.size();}
1126 _LIBCPP_INLINE_VISIBILITY
1127 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1128
1129 mapped_type& operator[](const key_type& __k);
1130#ifndef _LIBCPP_CXX03_LANG
1131 mapped_type& operator[](key_type&& __k);
1132#endif
1133
1134 mapped_type& at(const key_type& __k);
1135 const mapped_type& at(const key_type& __k) const;
1136
1137 _LIBCPP_INLINE_VISIBILITY
1138 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1139 _LIBCPP_INLINE_VISIBILITY
1140 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1141 _LIBCPP_INLINE_VISIBILITY
1142 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1143
1144#ifndef _LIBCPP_CXX03_LANG
1145 template <class ..._Args>
1146 _LIBCPP_INLINE_VISIBILITY
1147 pair<iterator, bool> emplace(_Args&& ...__args) {
1148 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1149 }
1150
1151 template <class ..._Args>
1152 _LIBCPP_INLINE_VISIBILITY
1153 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1154 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1155 }
1156
1157 template <class _Pp,
1158 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1159 _LIBCPP_INLINE_VISIBILITY
1160 pair<iterator, bool> insert(_Pp&& __p)
1161 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1162
1163 template <class _Pp,
1164 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1165 _LIBCPP_INLINE_VISIBILITY
1166 iterator insert(const_iterator __pos, _Pp&& __p)
1167 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1168
1169#endif // _LIBCPP_CXX03_LANG
1170
1171 _LIBCPP_INLINE_VISIBILITY
1172 pair<iterator, bool>
1173 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1174
1175 _LIBCPP_INLINE_VISIBILITY
1176 iterator
1177 insert(const_iterator __p, const value_type& __v)
1178 {return __tree_.__insert_unique(__p.__i_, __v);}
1179
1180#ifndef _LIBCPP_CXX03_LANG
1181 _LIBCPP_INLINE_VISIBILITY
1182 pair<iterator, bool>
1183 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
1184
1185 _LIBCPP_INLINE_VISIBILITY
1186 iterator insert(const_iterator __p, value_type&& __v)
1187 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
1188
1189 _LIBCPP_INLINE_VISIBILITY
1190 void insert(initializer_list<value_type> __il)
1191 {insert(__il.begin(), __il.end());}
1192#endif
1193
1194 template <class _InputIterator>
1195 _LIBCPP_INLINE_VISIBILITY
1196 void insert(_InputIterator __f, _InputIterator __l)
1197 {
1198 for (const_iterator __e = cend(); __f != __l; ++__f)
1199 insert(__e.__i_, *__f);
1200 }
1201
1202#if _LIBCPP_STD_VER > 14
1203
1204 template <class... _Args>
1205 _LIBCPP_INLINE_VISIBILITY
1206 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1207 {
1208 return __tree_.__emplace_unique_key_args(__k,
1209 _VSTD::piecewise_construct,
1210 _VSTD::forward_as_tuple(__k),
1211 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1212 }
1213
1214 template <class... _Args>
1215 _LIBCPP_INLINE_VISIBILITY
1216 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1217 {
1218 return __tree_.__emplace_unique_key_args(__k,
1219 _VSTD::piecewise_construct,
1220 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1221 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1222 }
1223
1224 template <class... _Args>
1225 _LIBCPP_INLINE_VISIBILITY
1226 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1227 {
1228 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1229 _VSTD::piecewise_construct,
1230 _VSTD::forward_as_tuple(__k),
1231 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1232 }
1233
1234 template <class... _Args>
1235 _LIBCPP_INLINE_VISIBILITY
1236 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1237 {
1238 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1239 _VSTD::piecewise_construct,
1240 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1241 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1242 }
1243
1244 template <class _Vp>
1245 _LIBCPP_INLINE_VISIBILITY
1246 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1247 {
1248 iterator __p = lower_bound(__k);
1249 if ( __p != end() && !key_comp()(__k, __p->first))
1250 {
1251 __p->second = _VSTD::forward<_Vp>(__v);
1252 return _VSTD::make_pair(__p, false);
1253 }
1254 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1255 }
1256
1257 template <class _Vp>
1258 _LIBCPP_INLINE_VISIBILITY
1259 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1260 {
1261 iterator __p = lower_bound(__k);
1262 if ( __p != end() && !key_comp()(__k, __p->first))
1263 {
1264 __p->second = _VSTD::forward<_Vp>(__v);
1265 return _VSTD::make_pair(__p, false);
1266 }
1267 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1268 }
1269
1270 template <class _Vp>
1271 _LIBCPP_INLINE_VISIBILITY
1272 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1273 {
1274 iterator __p = lower_bound(__k);
1275 if ( __p != end() && !key_comp()(__k, __p->first))
1276 {
1277 __p->second = _VSTD::forward<_Vp>(__v);
1278 return __p;
1279 }
1280 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1281 }
1282
1283 template <class _Vp>
1284 _LIBCPP_INLINE_VISIBILITY
1285 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1286 {
1287 iterator __p = lower_bound(__k);
1288 if ( __p != end() && !key_comp()(__k, __p->first))
1289 {
1290 __p->second = _VSTD::forward<_Vp>(__v);
1291 return __p;
1292 }
1293 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1294 }
1295
1296#endif // _LIBCPP_STD_VER > 14
1297
1298 _LIBCPP_INLINE_VISIBILITY
1299 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1300 _LIBCPP_INLINE_VISIBILITY
1301 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1302 _LIBCPP_INLINE_VISIBILITY
1303 size_type erase(const key_type& __k)
1304 {return __tree_.__erase_unique(__k);}
1305 _LIBCPP_INLINE_VISIBILITY
1306 iterator erase(const_iterator __f, const_iterator __l)
1307 {return __tree_.erase(__f.__i_, __l.__i_);}
1308 _LIBCPP_INLINE_VISIBILITY
1309 void clear() _NOEXCEPT {__tree_.clear();}
1310
1311#if _LIBCPP_STD_VER > 14
1312 _LIBCPP_INLINE_VISIBILITY
1313 insert_return_type insert(node_type&& __nh)
1314 {
1315 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1316 "node_type with incompatible allocator passed to map::insert()");
1317 return __tree_.template __node_handle_insert_unique<
1318 node_type, insert_return_type>(_VSTD::move(__nh));
1319 }
1320 _LIBCPP_INLINE_VISIBILITY
1321 iterator insert(const_iterator __hint, node_type&& __nh)
1322 {
1323 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1324 "node_type with incompatible allocator passed to map::insert()");
1325 return __tree_.template __node_handle_insert_unique<node_type>(
1326 __hint.__i_, _VSTD::move(__nh));
1327 }
1328 _LIBCPP_INLINE_VISIBILITY
1329 node_type extract(key_type const& __key)
1330 {
1331 return __tree_.template __node_handle_extract<node_type>(__key);
1332 }
1333 _LIBCPP_INLINE_VISIBILITY
1334 node_type extract(const_iterator __it)
1335 {
1336 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1337 }
1338 template <class _Compare2>
1339 _LIBCPP_INLINE_VISIBILITY
1340 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
1341 {
1342 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1343 "merging container with incompatible allocator");
1344 __tree_.__node_handle_merge_unique(__source.__tree_);
1345 }
1346 template <class _Compare2>
1347 _LIBCPP_INLINE_VISIBILITY
1348 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
1349 {
1350 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1351 "merging container with incompatible allocator");
1352 __tree_.__node_handle_merge_unique(__source.__tree_);
1353 }
1354 template <class _Compare2>
1355 _LIBCPP_INLINE_VISIBILITY
1356 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
1357 {
1358 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1359 "merging container with incompatible allocator");
1360 __tree_.__node_handle_merge_unique(__source.__tree_);
1361 }
1362 template <class _Compare2>
1363 _LIBCPP_INLINE_VISIBILITY
1364 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
1365 {
1366 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1367 "merging container with incompatible allocator");
1368 __tree_.__node_handle_merge_unique(__source.__tree_);
1369 }
1370#endif
1371
1372 _LIBCPP_INLINE_VISIBILITY
1373 void swap(map& __m)
1374 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1375 {__tree_.swap(__m.__tree_);}
1376
1377 _LIBCPP_INLINE_VISIBILITY
1378 iterator find(const key_type& __k) {return __tree_.find(__k);}
1379 _LIBCPP_INLINE_VISIBILITY
1380 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1381#if _LIBCPP_STD_VER > 11
1382 template <typename _K2>
1383 _LIBCPP_INLINE_VISIBILITY
1384 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1385 find(const _K2& __k) {return __tree_.find(__k);}
1386 template <typename _K2>
1387 _LIBCPP_INLINE_VISIBILITY
1388 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1389 find(const _K2& __k) const {return __tree_.find(__k);}
1390#endif
1391
1392 _LIBCPP_INLINE_VISIBILITY
1393 size_type count(const key_type& __k) const
1394 {return __tree_.__count_unique(__k);}
1395#if _LIBCPP_STD_VER > 11
1396 template <typename _K2>
1397 _LIBCPP_INLINE_VISIBILITY
1398 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1399 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
1400#endif
1401
1402#if _LIBCPP_STD_VER > 17
1403 _LIBCPP_INLINE_VISIBILITY
1404 bool contains(const key_type& __k) const {return find(__k) != end();}
1405#endif // _LIBCPP_STD_VER > 17
1406
1407 _LIBCPP_INLINE_VISIBILITY
1408 iterator lower_bound(const key_type& __k)
1409 {return __tree_.lower_bound(__k);}
1410 _LIBCPP_INLINE_VISIBILITY
1411 const_iterator lower_bound(const key_type& __k) const
1412 {return __tree_.lower_bound(__k);}
1413#if _LIBCPP_STD_VER > 11
1414 template <typename _K2>
1415 _LIBCPP_INLINE_VISIBILITY
1416 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1417 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1418
1419 template <typename _K2>
1420 _LIBCPP_INLINE_VISIBILITY
1421 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1422 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1423#endif
1424
1425 _LIBCPP_INLINE_VISIBILITY
1426 iterator upper_bound(const key_type& __k)
1427 {return __tree_.upper_bound(__k);}
1428 _LIBCPP_INLINE_VISIBILITY
1429 const_iterator upper_bound(const key_type& __k) const
1430 {return __tree_.upper_bound(__k);}
1431#if _LIBCPP_STD_VER > 11
1432 template <typename _K2>
1433 _LIBCPP_INLINE_VISIBILITY
1434 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1435 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1436 template <typename _K2>
1437 _LIBCPP_INLINE_VISIBILITY
1438 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1439 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1440#endif
1441
1442 _LIBCPP_INLINE_VISIBILITY
1443 pair<iterator,iterator> equal_range(const key_type& __k)
1444 {return __tree_.__equal_range_unique(__k);}
1445 _LIBCPP_INLINE_VISIBILITY
1446 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1447 {return __tree_.__equal_range_unique(__k);}
1448#if _LIBCPP_STD_VER > 11
1449 template <typename _K2>
1450 _LIBCPP_INLINE_VISIBILITY
1451 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1452 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1453 template <typename _K2>
1454 _LIBCPP_INLINE_VISIBILITY
1455 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1456 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1457#endif
1458
1459private:
1460 typedef typename __base::__node __node;
1461 typedef typename __base::__node_allocator __node_allocator;
1462 typedef typename __base::__node_pointer __node_pointer;
1463 typedef typename __base::__node_base_pointer __node_base_pointer;
1464 typedef typename __base::__parent_pointer __parent_pointer;
1465
1466 typedef __map_node_destructor<__node_allocator> _Dp;
1467 typedef unique_ptr<__node, _Dp> __node_holder;
1468
1469#ifdef _LIBCPP_CXX03_LANG
1470 __node_holder __construct_node_with_key(const key_type& __k);
1471#endif
1472};
1473
1474#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1475template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
1476 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1477 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1478 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1479map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1480 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1481
1482template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
1483 class _Allocator = allocator<pair<const _Key, _Tp>>,
1484 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1485 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1486map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
1487 -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1488
1489template<class _InputIterator, class _Allocator,
1490 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1491map(_InputIterator, _InputIterator, _Allocator)
1492 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1493 less<__iter_key_type<_InputIterator>>, _Allocator>;
1494
1495template<class _Key, class _Tp, class _Allocator,
1496 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1497map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1498 -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1499#endif
1500
1501#ifndef _LIBCPP_CXX03_LANG
1502template <class _Key, class _Tp, class _Compare, class _Allocator>
1503map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1504 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
1505{
1506 if (__a != __m.get_allocator())
1507 {
1508 const_iterator __e = cend();
1509 while (!__m.empty())
1510 __tree_.__insert_unique(__e.__i_,
1511 __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
1512 }
1513}
1514
1515template <class _Key, class _Tp, class _Compare, class _Allocator>
1516_Tp&
1517map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1518{
1519 return __tree_.__emplace_unique_key_args(__k,
1520 _VSTD::piecewise_construct,
1521 _VSTD::forward_as_tuple(__k),
1522 _VSTD::forward_as_tuple()).first->__get_value().second;
1523}
1524
1525template <class _Key, class _Tp, class _Compare, class _Allocator>
1526_Tp&
1527map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1528{
1529 return __tree_.__emplace_unique_key_args(__k,
1530 _VSTD::piecewise_construct,
1531 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1532 _VSTD::forward_as_tuple()).first->__get_value().second;
1533}
1534
1535#else // _LIBCPP_CXX03_LANG
1536
1537template <class _Key, class _Tp, class _Compare, class _Allocator>
1538typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1539map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1540{
1541 __node_allocator& __na = __tree_.__node_alloc();
1542 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1543 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
1544 __h.get_deleter().__first_constructed = true;
1545 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
1546 __h.get_deleter().__second_constructed = true;
1547 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
1548}
1549
1550template <class _Key, class _Tp, class _Compare, class _Allocator>
1551_Tp&
1552map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1553{
1554 __parent_pointer __parent;
1555 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1556 __node_pointer __r = static_cast<__node_pointer>(__child);
1557 if (__child == nullptr)
1558 {
1559 __node_holder __h = __construct_node_with_key(__k);
1560 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1561 __r = __h.release();
1562 }
1563 return __r->__value_.__get_value().second;
1564}
1565
1566#endif // _LIBCPP_CXX03_LANG
1567
1568template <class _Key, class _Tp, class _Compare, class _Allocator>
1569_Tp&
1570map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1571{
1572 __parent_pointer __parent;
1573 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1574 if (__child == nullptr)
1575 __throw_out_of_range("map::at: key not found");
1576 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1577}
1578
1579template <class _Key, class _Tp, class _Compare, class _Allocator>
1580const _Tp&
1581map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1582{
1583 __parent_pointer __parent;
1584 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1585 if (__child == nullptr)
1586 __throw_out_of_range("map::at: key not found");
1587 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1588}
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.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
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 _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1607}
1608
1609template <class _Key, class _Tp, class _Compare, class _Allocator>
1610inline _LIBCPP_INLINE_VISIBILITY
1611bool
1612operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1613 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1614{
1615 return !(__x == __y);
1616}
1617
1618template <class _Key, class _Tp, class _Compare, class _Allocator>
1619inline _LIBCPP_INLINE_VISIBILITY
1620bool
1621operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1622 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1623{
1624 return __y < __x;
1625}
1626
1627template <class _Key, class _Tp, class _Compare, class _Allocator>
1628inline _LIBCPP_INLINE_VISIBILITY
1629bool
1630operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1631 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1632{
1633 return !(__x < __y);
1634}
1635
1636template <class _Key, class _Tp, class _Compare, class _Allocator>
1637inline _LIBCPP_INLINE_VISIBILITY
1638bool
1639operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1640 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1641{
1642 return !(__y < __x);
1643}
1644
1645template <class _Key, class _Tp, class _Compare, class _Allocator>
1646inline _LIBCPP_INLINE_VISIBILITY
1647void
1648swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1649 map<_Key, _Tp, _Compare, _Allocator>& __y)
1650 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1651{
1652 __x.swap(__y);
1653}
1654
1655#if _LIBCPP_STD_VER > 17
1656template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
1657inline _LIBCPP_INLINE_VISIBILITY
1658void erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred)
1659{ __libcpp_erase_if_container(__c, __pred); }
1660#endif
1661
1662
1663template <class _Key, class _Tp, class _Compare = less<_Key>,
1664 class _Allocator = allocator<pair<const _Key, _Tp> > >
1665class _LIBCPP_TEMPLATE_VIS multimap
1666{
1667public:
1668 // types:
1669 typedef _Key key_type;
1670 typedef _Tp mapped_type;
1671 typedef pair<const key_type, mapped_type> value_type;
1672 typedef typename __identity<_Compare>::type key_compare;
1673 typedef typename __identity<_Allocator>::type allocator_type;
1674 typedef value_type& reference;
1675 typedef const value_type& const_reference;
1676
1677 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1678 "Allocator::value_type must be same type as value_type");
1679
1680 class _LIBCPP_TEMPLATE_VIS value_compare
1681 : public binary_function<value_type, value_type, bool>
1682 {
1683 friend class multimap;
1684 protected:
1685 key_compare comp;
1686
1687 _LIBCPP_INLINE_VISIBILITY
1688 value_compare(key_compare c) : comp(c) {}
1689 public:
1690 _LIBCPP_INLINE_VISIBILITY
1691 bool operator()(const value_type& __x, const value_type& __y) const
1692 {return comp(__x.first, __y.first);}
1693 };
1694
1695private:
1696
1697 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
1698 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1699 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1700 __value_type>::type __allocator_type;
1701 typedef __tree<__value_type, __vc, __allocator_type> __base;
1702 typedef typename __base::__node_traits __node_traits;
1703 typedef allocator_traits<allocator_type> __alloc_traits;
1704
1705 __base __tree_;
1706
1707public:
1708 typedef typename __alloc_traits::pointer pointer;
1709 typedef typename __alloc_traits::const_pointer const_pointer;
1710 typedef typename __alloc_traits::size_type size_type;
1711 typedef typename __alloc_traits::difference_type difference_type;
1712 typedef __map_iterator<typename __base::iterator> iterator;
1713 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1714 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1715 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1716
1717#if _LIBCPP_STD_VER > 14
1718 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1719#endif
1720
1721 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1722 friend class _LIBCPP_TEMPLATE_VIS map;
1723 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1724 friend class _LIBCPP_TEMPLATE_VIS multimap;
1725
1726 _LIBCPP_INLINE_VISIBILITY
1727 multimap()
1728 _NOEXCEPT_(
1729 is_nothrow_default_constructible<allocator_type>::value &&
1730 is_nothrow_default_constructible<key_compare>::value &&
1731 is_nothrow_copy_constructible<key_compare>::value)
1732 : __tree_(__vc(key_compare())) {}
1733
1734 _LIBCPP_INLINE_VISIBILITY
1735 explicit multimap(const key_compare& __comp)
1736 _NOEXCEPT_(
1737 is_nothrow_default_constructible<allocator_type>::value &&
1738 is_nothrow_copy_constructible<key_compare>::value)
1739 : __tree_(__vc(__comp)) {}
1740
1741 _LIBCPP_INLINE_VISIBILITY
1742 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1743 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1744
1745 template <class _InputIterator>
1746 _LIBCPP_INLINE_VISIBILITY
1747 multimap(_InputIterator __f, _InputIterator __l,
1748 const key_compare& __comp = key_compare())
1749 : __tree_(__vc(__comp))
1750 {
1751 insert(__f, __l);
1752 }
1753
1754 template <class _InputIterator>
1755 _LIBCPP_INLINE_VISIBILITY
1756 multimap(_InputIterator __f, _InputIterator __l,
1757 const key_compare& __comp, const allocator_type& __a)
1758 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1759 {
1760 insert(__f, __l);
1761 }
1762
1763#if _LIBCPP_STD_VER > 11
1764 template <class _InputIterator>
1765 _LIBCPP_INLINE_VISIBILITY
1766 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1767 : multimap(__f, __l, key_compare(), __a) {}
1768#endif
1769
1770 _LIBCPP_INLINE_VISIBILITY
1771 multimap(const multimap& __m)
1772 : __tree_(__m.__tree_.value_comp(),
1773 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1774 {
1775 insert(__m.begin(), __m.end());
1776 }
1777
1778 _LIBCPP_INLINE_VISIBILITY
1779 multimap& operator=(const multimap& __m)
1780 {
1781#ifndef _LIBCPP_CXX03_LANG
1782 __tree_ = __m.__tree_;
1783#else
1784 if (this != &__m) {
1785 __tree_.clear();
1786 __tree_.value_comp() = __m.__tree_.value_comp();
1787 __tree_.__copy_assign_alloc(__m.__tree_);
1788 insert(__m.begin(), __m.end());
1789 }
1790#endif
1791 return *this;
1792 }
1793
1794#ifndef _LIBCPP_CXX03_LANG
1795
1796 _LIBCPP_INLINE_VISIBILITY
1797 multimap(multimap&& __m)
1798 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1799 : __tree_(_VSTD::move(__m.__tree_))
1800 {
1801 }
1802
1803 multimap(multimap&& __m, const allocator_type& __a);
1804
1805 _LIBCPP_INLINE_VISIBILITY
1806 multimap& operator=(multimap&& __m)
1807 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1808 {
1809 __tree_ = _VSTD::move(__m.__tree_);
1810 return *this;
1811 }
1812
1813 _LIBCPP_INLINE_VISIBILITY
1814 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1815 : __tree_(__vc(__comp))
1816 {
1817 insert(__il.begin(), __il.end());
1818 }
1819
1820 _LIBCPP_INLINE_VISIBILITY
1821 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1822 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
1823 {
1824 insert(__il.begin(), __il.end());
1825 }
1826
1827#if _LIBCPP_STD_VER > 11
1828 _LIBCPP_INLINE_VISIBILITY
1829 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1830 : multimap(__il, key_compare(), __a) {}
1831#endif
1832
1833 _LIBCPP_INLINE_VISIBILITY
1834 multimap& operator=(initializer_list<value_type> __il)
1835 {
1836 __tree_.__assign_multi(__il.begin(), __il.end());
1837 return *this;
1838 }
1839
1840#endif // _LIBCPP_CXX03_LANG
1841
1842 _LIBCPP_INLINE_VISIBILITY
1843 explicit multimap(const allocator_type& __a)
1844 : __tree_(typename __base::allocator_type(__a))
1845 {
1846 }
1847
1848 _LIBCPP_INLINE_VISIBILITY
1849 multimap(const multimap& __m, const allocator_type& __a)
1850 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
1851 {
1852 insert(__m.begin(), __m.end());
1853 }
1854
1855 _LIBCPP_INLINE_VISIBILITY
1856 ~multimap() {
1857 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1858 }
1859
1860 _LIBCPP_INLINE_VISIBILITY
1861 iterator begin() _NOEXCEPT {return __tree_.begin();}
1862 _LIBCPP_INLINE_VISIBILITY
1863 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1864 _LIBCPP_INLINE_VISIBILITY
1865 iterator end() _NOEXCEPT {return __tree_.end();}
1866 _LIBCPP_INLINE_VISIBILITY
1867 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1868
1869 _LIBCPP_INLINE_VISIBILITY
1870 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1871 _LIBCPP_INLINE_VISIBILITY
1872 const_reverse_iterator rbegin() const _NOEXCEPT
1873 {return const_reverse_iterator(end());}
1874 _LIBCPP_INLINE_VISIBILITY
1875 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1876 _LIBCPP_INLINE_VISIBILITY
1877 const_reverse_iterator rend() const _NOEXCEPT
1878 {return const_reverse_iterator(begin());}
1879
1880 _LIBCPP_INLINE_VISIBILITY
1881 const_iterator cbegin() const _NOEXCEPT {return begin();}
1882 _LIBCPP_INLINE_VISIBILITY
1883 const_iterator cend() const _NOEXCEPT {return end();}
1884 _LIBCPP_INLINE_VISIBILITY
1885 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1886 _LIBCPP_INLINE_VISIBILITY
1887 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1888
1889 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1890 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1891 _LIBCPP_INLINE_VISIBILITY
1892 size_type size() const _NOEXCEPT {return __tree_.size();}
1893 _LIBCPP_INLINE_VISIBILITY
1894 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1895
1896 _LIBCPP_INLINE_VISIBILITY
1897 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
1898 _LIBCPP_INLINE_VISIBILITY
1899 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
1900 _LIBCPP_INLINE_VISIBILITY
1901 value_compare value_comp() const
1902 {return value_compare(__tree_.value_comp().key_comp());}
1903
1904#ifndef _LIBCPP_CXX03_LANG
1905
1906 template <class ..._Args>
1907 _LIBCPP_INLINE_VISIBILITY
1908 iterator emplace(_Args&& ...__args) {
1909 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1910 }
1911
1912 template <class ..._Args>
1913 _LIBCPP_INLINE_VISIBILITY
1914 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1915 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1916 }
1917
1918 template <class _Pp,
1919 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1920 _LIBCPP_INLINE_VISIBILITY
1921 iterator insert(_Pp&& __p)
1922 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1923
1924 template <class _Pp,
1925 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1926 _LIBCPP_INLINE_VISIBILITY
1927 iterator insert(const_iterator __pos, _Pp&& __p)
1928 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1929
1930 _LIBCPP_INLINE_VISIBILITY
1931 iterator insert(value_type&& __v)
1932 {return __tree_.__insert_multi(_VSTD::move(__v));}
1933
1934 _LIBCPP_INLINE_VISIBILITY
1935 iterator insert(const_iterator __p, value_type&& __v)
1936 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1937
1938
1939 _LIBCPP_INLINE_VISIBILITY
1940 void insert(initializer_list<value_type> __il)
1941 {insert(__il.begin(), __il.end());}
1942
1943#endif // _LIBCPP_CXX03_LANG
1944
1945 _LIBCPP_INLINE_VISIBILITY
1946 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1947
1948 _LIBCPP_INLINE_VISIBILITY
1949 iterator insert(const_iterator __p, const value_type& __v)
1950 {return __tree_.__insert_multi(__p.__i_, __v);}
1951
1952 template <class _InputIterator>
1953 _LIBCPP_INLINE_VISIBILITY
1954 void insert(_InputIterator __f, _InputIterator __l)
1955 {
1956 for (const_iterator __e = cend(); __f != __l; ++__f)
1957 __tree_.__insert_multi(__e.__i_, *__f);
1958 }
1959
1960 _LIBCPP_INLINE_VISIBILITY
1961 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1962 _LIBCPP_INLINE_VISIBILITY
1963 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1964 _LIBCPP_INLINE_VISIBILITY
1965 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1966 _LIBCPP_INLINE_VISIBILITY
1967 iterator erase(const_iterator __f, const_iterator __l)
1968 {return __tree_.erase(__f.__i_, __l.__i_);}
1969
1970#if _LIBCPP_STD_VER > 14
1971 _LIBCPP_INLINE_VISIBILITY
1972 iterator insert(node_type&& __nh)
1973 {
1974 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1975 "node_type with incompatible allocator passed to multimap::insert()");
1976 return __tree_.template __node_handle_insert_multi<node_type>(
1977 _VSTD::move(__nh));
1978 }
1979 _LIBCPP_INLINE_VISIBILITY
1980 iterator insert(const_iterator __hint, node_type&& __nh)
1981 {
1982 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1983 "node_type with incompatible allocator passed to multimap::insert()");
1984 return __tree_.template __node_handle_insert_multi<node_type>(
1985 __hint.__i_, _VSTD::move(__nh));
1986 }
1987 _LIBCPP_INLINE_VISIBILITY
1988 node_type extract(key_type const& __key)
1989 {
1990 return __tree_.template __node_handle_extract<node_type>(__key);
1991 }
1992 _LIBCPP_INLINE_VISIBILITY
1993 node_type extract(const_iterator __it)
1994 {
1995 return __tree_.template __node_handle_extract<node_type>(
1996 __it.__i_);
1997 }
1998 template <class _Compare2>
1999 _LIBCPP_INLINE_VISIBILITY
2000 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
2001 {
2002 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2003 "merging container with incompatible allocator");
2004 return __tree_.__node_handle_merge_multi(__source.__tree_);
2005 }
2006 template <class _Compare2>
2007 _LIBCPP_INLINE_VISIBILITY
2008 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
2009 {
2010 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2011 "merging container with incompatible allocator");
2012 return __tree_.__node_handle_merge_multi(__source.__tree_);
2013 }
2014 template <class _Compare2>
2015 _LIBCPP_INLINE_VISIBILITY
2016 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
2017 {
2018 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2019 "merging container with incompatible allocator");
2020 return __tree_.__node_handle_merge_multi(__source.__tree_);
2021 }
2022 template <class _Compare2>
2023 _LIBCPP_INLINE_VISIBILITY
2024 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
2025 {
2026 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2027 "merging container with incompatible allocator");
2028 return __tree_.__node_handle_merge_multi(__source.__tree_);
2029 }
2030#endif
2031
2032 _LIBCPP_INLINE_VISIBILITY
2033 void clear() _NOEXCEPT {__tree_.clear();}
2034
2035 _LIBCPP_INLINE_VISIBILITY
2036 void swap(multimap& __m)
2037 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
2038 {__tree_.swap(__m.__tree_);}
2039
2040 _LIBCPP_INLINE_VISIBILITY
2041 iterator find(const key_type& __k) {return __tree_.find(__k);}
2042 _LIBCPP_INLINE_VISIBILITY
2043 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
2044#if _LIBCPP_STD_VER > 11
2045 template <typename _K2>
2046 _LIBCPP_INLINE_VISIBILITY
2047 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2048 find(const _K2& __k) {return __tree_.find(__k);}
2049 template <typename _K2>
2050 _LIBCPP_INLINE_VISIBILITY
2051 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2052 find(const _K2& __k) const {return __tree_.find(__k);}
2053#endif
2054
2055 _LIBCPP_INLINE_VISIBILITY
2056 size_type count(const key_type& __k) const
2057 {return __tree_.__count_multi(__k);}
2058#if _LIBCPP_STD_VER > 11
2059 template <typename _K2>
2060 _LIBCPP_INLINE_VISIBILITY
2061 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
2062 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
2063#endif
2064
2065#if _LIBCPP_STD_VER > 17
2066 _LIBCPP_INLINE_VISIBILITY
2067 bool contains(const key_type& __k) const {return find(__k) != end();}
2068#endif // _LIBCPP_STD_VER > 17
2069
2070 _LIBCPP_INLINE_VISIBILITY
2071 iterator lower_bound(const key_type& __k)
2072 {return __tree_.lower_bound(__k);}
2073 _LIBCPP_INLINE_VISIBILITY
2074 const_iterator lower_bound(const key_type& __k) const
2075 {return __tree_.lower_bound(__k);}
2076#if _LIBCPP_STD_VER > 11
2077 template <typename _K2>
2078 _LIBCPP_INLINE_VISIBILITY
2079 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2080 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
2081
2082 template <typename _K2>
2083 _LIBCPP_INLINE_VISIBILITY
2084 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2085 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
2086#endif
2087
2088 _LIBCPP_INLINE_VISIBILITY
2089 iterator upper_bound(const key_type& __k)
2090 {return __tree_.upper_bound(__k);}
2091 _LIBCPP_INLINE_VISIBILITY
2092 const_iterator upper_bound(const key_type& __k) const
2093 {return __tree_.upper_bound(__k);}
2094#if _LIBCPP_STD_VER > 11
2095 template <typename _K2>
2096 _LIBCPP_INLINE_VISIBILITY
2097 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2098 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
2099 template <typename _K2>
2100 _LIBCPP_INLINE_VISIBILITY
2101 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2102 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
2103#endif
2104
2105 _LIBCPP_INLINE_VISIBILITY
2106 pair<iterator,iterator> equal_range(const key_type& __k)
2107 {return __tree_.__equal_range_multi(__k);}
2108 _LIBCPP_INLINE_VISIBILITY
2109 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
2110 {return __tree_.__equal_range_multi(__k);}
2111#if _LIBCPP_STD_VER > 11
2112 template <typename _K2>
2113 _LIBCPP_INLINE_VISIBILITY
2114 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
2115 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
2116 template <typename _K2>
2117 _LIBCPP_INLINE_VISIBILITY
2118 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
2119 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
2120#endif
2121
2122private:
2123 typedef typename __base::__node __node;
2124 typedef typename __base::__node_allocator __node_allocator;
2125 typedef typename __base::__node_pointer __node_pointer;
2126
2127 typedef __map_node_destructor<__node_allocator> _Dp;
2128 typedef unique_ptr<__node, _Dp> __node_holder;
2129};
2130
2131#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
2132template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
2133 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2134 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
2135 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2136multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
2137 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
2138
2139template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
2140 class _Allocator = allocator<pair<const _Key, _Tp>>,
2141 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
2142 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2143multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
2144 -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2145
2146template<class _InputIterator, class _Allocator,
2147 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2148multimap(_InputIterator, _InputIterator, _Allocator)
2149 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2150 less<__iter_key_type<_InputIterator>>, _Allocator>;
2151
2152template<class _Key, class _Tp, class _Allocator,
2153 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2154multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2155 -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
2156#endif
2157
2158#ifndef _LIBCPP_CXX03_LANG
2159template <class _Key, class _Tp, class _Compare, class _Allocator>
2160multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
2161 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
2162{
2163 if (__a != __m.get_allocator())
2164 {
2165 const_iterator __e = cend();
2166 while (!__m.empty())
2167 __tree_.__insert_multi(__e.__i_,
2168 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
2169 }
2170}
2171#endif
2172
2173template <class _Key, class _Tp, class _Compare, class _Allocator>
2174inline _LIBCPP_INLINE_VISIBILITY
2175bool
2176operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2177 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2178{
2179 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2180}
2181
2182template <class _Key, class _Tp, class _Compare, class _Allocator>
2183inline _LIBCPP_INLINE_VISIBILITY
2184bool
2185operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2186 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2187{
2188 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2189}
2190
2191template <class _Key, class _Tp, class _Compare, class _Allocator>
2192inline _LIBCPP_INLINE_VISIBILITY
2193bool
2194operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2195 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2196{
2197 return !(__x == __y);
2198}
2199
2200template <class _Key, class _Tp, class _Compare, class _Allocator>
2201inline _LIBCPP_INLINE_VISIBILITY
2202bool
2203operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2204 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2205{
2206 return __y < __x;
2207}
2208
2209template <class _Key, class _Tp, class _Compare, class _Allocator>
2210inline _LIBCPP_INLINE_VISIBILITY
2211bool
2212operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2213 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2214{
2215 return !(__x < __y);
2216}
2217
2218template <class _Key, class _Tp, class _Compare, class _Allocator>
2219inline _LIBCPP_INLINE_VISIBILITY
2220bool
2221operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2222 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2223{
2224 return !(__y < __x);
2225}
2226
2227template <class _Key, class _Tp, class _Compare, class _Allocator>
2228inline _LIBCPP_INLINE_VISIBILITY
2229void
2230swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2231 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2232 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2233{
2234 __x.swap(__y);
2235}
2236
2237#if _LIBCPP_STD_VER > 17
2238template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
2239inline _LIBCPP_INLINE_VISIBILITY
2240void erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred)
2241{ __libcpp_erase_if_container(__c, __pred); }
2242#endif
2243
2244_LIBCPP_END_NAMESPACE_STD
2245
2246#endif // _LIBCPP_MAP
2247