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