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 | |
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 | : 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 | |
220 | template <class Key, class T, class Compare, class Allocator> |
221 | bool |
222 | operator==(const map<Key, T, Compare, Allocator>& x, |
223 | const map<Key, T, Compare, Allocator>& y); |
224 | |
225 | template <class Key, class T, class Compare, class Allocator> |
226 | bool |
227 | operator< (const map<Key, T, Compare, Allocator>& x, |
228 | const map<Key, T, Compare, Allocator>& y); |
229 | |
230 | template <class Key, class T, class Compare, class Allocator> |
231 | bool |
232 | operator!=(const map<Key, T, Compare, Allocator>& x, |
233 | const map<Key, T, Compare, Allocator>& y); |
234 | |
235 | template <class Key, class T, class Compare, class Allocator> |
236 | bool |
237 | operator> (const map<Key, T, Compare, Allocator>& x, |
238 | const map<Key, T, Compare, Allocator>& y); |
239 | |
240 | template <class Key, class T, class Compare, class Allocator> |
241 | bool |
242 | operator>=(const map<Key, T, Compare, Allocator>& x, |
243 | const map<Key, T, Compare, Allocator>& y); |
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 | // specialized algorithms: |
251 | template <class Key, class T, class Compare, class Allocator> |
252 | void |
253 | swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y) |
254 | noexcept(noexcept(x.swap(y))); |
255 | |
256 | template <class Key, class T, class Compare, class Allocator, class Predicate> |
257 | void erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20 |
258 | |
259 | |
260 | template <class Key, class T, class Compare = less<Key>, |
261 | class Allocator = allocator<pair<const Key, T>>> |
262 | class multimap |
263 | { |
264 | public: |
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 | |
434 | template <class Key, class T, class Compare, class Allocator> |
435 | bool |
436 | operator==(const multimap<Key, T, Compare, Allocator>& x, |
437 | const multimap<Key, T, Compare, Allocator>& y); |
438 | |
439 | template <class Key, class T, class Compare, class Allocator> |
440 | bool |
441 | operator< (const multimap<Key, T, Compare, Allocator>& x, |
442 | const multimap<Key, T, Compare, Allocator>& y); |
443 | |
444 | template <class Key, class T, class Compare, class Allocator> |
445 | bool |
446 | operator!=(const multimap<Key, T, Compare, Allocator>& x, |
447 | const multimap<Key, T, Compare, Allocator>& y); |
448 | |
449 | template <class Key, class T, class Compare, class Allocator> |
450 | bool |
451 | operator> (const multimap<Key, T, Compare, Allocator>& x, |
452 | const multimap<Key, T, Compare, Allocator>& y); |
453 | |
454 | template <class Key, class T, class Compare, class Allocator> |
455 | bool |
456 | operator>=(const multimap<Key, T, Compare, Allocator>& x, |
457 | const multimap<Key, T, Compare, Allocator>& y); |
458 | |
459 | template <class Key, class T, class Compare, class Allocator> |
460 | bool |
461 | operator<=(const multimap<Key, T, Compare, Allocator>& x, |
462 | const multimap<Key, T, Compare, Allocator>& y); |
463 | |
464 | // specialized algorithms: |
465 | template <class Key, class T, class Compare, class Allocator> |
466 | void |
467 | swap(multimap<Key, T, Compare, Allocator>& x, |
468 | multimap<Key, T, Compare, Allocator>& y) |
469 | noexcept(noexcept(x.swap(y))); |
470 | |
471 | template <class Key, class T, class Compare, class Allocator, class Predicate> |
472 | void erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20 |
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 | |
495 | template <class _Key, class _CP, class _Compare, |
496 | bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value> |
497 | class __map_value_compare |
498 | : private _Compare |
499 | { |
500 | public: |
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 | |
542 | template <class _Key, class _CP, class _Compare> |
543 | class __map_value_compare<_Key, _CP, _Compare, false> |
544 | { |
545 | _Compare comp; |
546 | |
547 | public: |
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 | |
590 | template <class _Key, class _CP, class _Compare, bool __b> |
591 | inline _LIBCPP_INLINE_VISIBILITY |
592 | void |
593 | swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, |
594 | __map_value_compare<_Key, _CP, _Compare, __b>& __y) |
595 | _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
596 | { |
597 | __x.swap(__y); |
598 | } |
599 | |
600 | template <class _Allocator> |
601 | class __map_node_destructor |
602 | { |
603 | typedef _Allocator allocator_type; |
604 | typedef allocator_traits<allocator_type> __alloc_traits; |
605 | |
606 | public: |
607 | typedef typename __alloc_traits::pointer pointer; |
608 | |
609 | private: |
610 | allocator_type& __na_; |
611 | |
612 | __map_node_destructor& operator=(const __map_node_destructor&); |
613 | |
614 | public: |
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 | |
648 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
649 | class map; |
650 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
651 | class multimap; |
652 | template <class _TreeIterator> class __map_const_iterator; |
653 | |
654 | #ifndef _LIBCPP_CXX03_LANG |
655 | |
656 | template <class _Key, class _Tp> |
657 | struct __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 | |
665 | private: |
666 | value_type __cc; |
667 | |
668 | public: |
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 | |
731 | private: |
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 | |
740 | template <class _Key, class _Tp> |
741 | struct __value_type |
742 | { |
743 | typedef _Key key_type; |
744 | typedef _Tp mapped_type; |
745 | typedef pair<const key_type, mapped_type> value_type; |
746 | |
747 | private: |
748 | value_type __cc; |
749 | |
750 | public: |
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 | |
756 | private: |
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 | |
765 | template <class _Tp> |
766 | struct ; |
767 | |
768 | template <class _Key, class _Tp> |
769 | struct <__value_type<_Key, _Tp> > |
770 | { |
771 | typedef _Key const ; |
772 | typedef _Tp ; |
773 | }; |
774 | |
775 | template <class _TreeIterator> |
776 | class _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 | |
783 | public: |
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 | |
834 | template <class _TreeIterator> |
835 | class _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 | |
842 | public: |
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 | |
896 | template <class _Key, class _Tp, class _Compare = less<_Key>, |
897 | class _Allocator = allocator<pair<const _Key, _Tp> > > |
898 | class _LIBCPP_TEMPLATE_VIS map |
899 | { |
900 | public: |
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 | |
927 | private: |
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 | |
939 | public: |
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 (key_type const& __key) |
1330 | { |
1331 | return __tree_.template __node_handle_extract<node_type>(__key); |
1332 | } |
1333 | _LIBCPP_INLINE_VISIBILITY |
1334 | node_type (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 | |
1459 | private: |
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 |
1475 | template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>, |
1476 | class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, |
1477 | class = _EnableIf<!__is_allocator<_Compare>::value, void>, |
1478 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
1479 | map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) |
1480 | -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; |
1481 | |
1482 | template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>, |
1483 | class _Allocator = allocator<pair<const _Key, _Tp>>, |
1484 | class = _EnableIf<!__is_allocator<_Compare>::value, void>, |
1485 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
1486 | map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator()) |
1487 | -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; |
1488 | |
1489 | template<class _InputIterator, class _Allocator, |
1490 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
1491 | map(_InputIterator, _InputIterator, _Allocator) |
1492 | -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, |
1493 | less<__iter_key_type<_InputIterator>>, _Allocator>; |
1494 | |
1495 | template<class _Key, class _Tp, class _Allocator, |
1496 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
1497 | map(initializer_list<pair<_Key, _Tp>>, _Allocator) |
1498 | -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; |
1499 | #endif |
1500 | |
1501 | #ifndef _LIBCPP_CXX03_LANG |
1502 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1503 | map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) |
1504 | : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) |
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 | |
1515 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1516 | _Tp& |
1517 | map<_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 | |
1525 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1526 | _Tp& |
1527 | map<_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 | |
1537 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1538 | typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder |
1539 | map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) |
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 | |
1550 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1551 | _Tp& |
1552 | map<_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 | |
1568 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1569 | _Tp& |
1570 | map<_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 | |
1579 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1580 | const _Tp& |
1581 | map<_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 | |
1591 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1592 | inline _LIBCPP_INLINE_VISIBILITY |
1593 | bool |
1594 | operator==(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 | |
1600 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1601 | inline _LIBCPP_INLINE_VISIBILITY |
1602 | bool |
1603 | operator< (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 | |
1609 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1610 | inline _LIBCPP_INLINE_VISIBILITY |
1611 | bool |
1612 | operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, |
1613 | const map<_Key, _Tp, _Compare, _Allocator>& __y) |
1614 | { |
1615 | return !(__x == __y); |
1616 | } |
1617 | |
1618 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1619 | inline _LIBCPP_INLINE_VISIBILITY |
1620 | bool |
1621 | operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x, |
1622 | const map<_Key, _Tp, _Compare, _Allocator>& __y) |
1623 | { |
1624 | return __y < __x; |
1625 | } |
1626 | |
1627 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1628 | inline _LIBCPP_INLINE_VISIBILITY |
1629 | bool |
1630 | operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, |
1631 | const map<_Key, _Tp, _Compare, _Allocator>& __y) |
1632 | { |
1633 | return !(__x < __y); |
1634 | } |
1635 | |
1636 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1637 | inline _LIBCPP_INLINE_VISIBILITY |
1638 | bool |
1639 | operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, |
1640 | const map<_Key, _Tp, _Compare, _Allocator>& __y) |
1641 | { |
1642 | return !(__y < __x); |
1643 | } |
1644 | |
1645 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
1646 | inline _LIBCPP_INLINE_VISIBILITY |
1647 | void |
1648 | swap(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 |
1656 | template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate> |
1657 | inline _LIBCPP_INLINE_VISIBILITY |
1658 | void erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) |
1659 | { __libcpp_erase_if_container(__c, __pred); } |
1660 | #endif |
1661 | |
1662 | |
1663 | template <class _Key, class _Tp, class _Compare = less<_Key>, |
1664 | class _Allocator = allocator<pair<const _Key, _Tp> > > |
1665 | class _LIBCPP_TEMPLATE_VIS multimap |
1666 | { |
1667 | public: |
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 | |
1695 | private: |
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 | |
1707 | public: |
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 (key_type const& __key) |
1989 | { |
1990 | return __tree_.template __node_handle_extract<node_type>(__key); |
1991 | } |
1992 | _LIBCPP_INLINE_VISIBILITY |
1993 | node_type (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 | |
2122 | private: |
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 |
2132 | template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>, |
2133 | class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, |
2134 | class = _EnableIf<!__is_allocator<_Compare>::value, void>, |
2135 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
2136 | multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) |
2137 | -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; |
2138 | |
2139 | template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>, |
2140 | class _Allocator = allocator<pair<const _Key, _Tp>>, |
2141 | class = _EnableIf<!__is_allocator<_Compare>::value, void>, |
2142 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
2143 | multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator()) |
2144 | -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; |
2145 | |
2146 | template<class _InputIterator, class _Allocator, |
2147 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
2148 | multimap(_InputIterator, _InputIterator, _Allocator) |
2149 | -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, |
2150 | less<__iter_key_type<_InputIterator>>, _Allocator>; |
2151 | |
2152 | template<class _Key, class _Tp, class _Allocator, |
2153 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
2154 | multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) |
2155 | -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; |
2156 | #endif |
2157 | |
2158 | #ifndef _LIBCPP_CXX03_LANG |
2159 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
2160 | multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) |
2161 | : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a)) |
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 | |
2173 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
2174 | inline _LIBCPP_INLINE_VISIBILITY |
2175 | bool |
2176 | operator==(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 | |
2182 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
2183 | inline _LIBCPP_INLINE_VISIBILITY |
2184 | bool |
2185 | operator< (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 | |
2191 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
2192 | inline _LIBCPP_INLINE_VISIBILITY |
2193 | bool |
2194 | operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
2195 | const multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
2196 | { |
2197 | return !(__x == __y); |
2198 | } |
2199 | |
2200 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
2201 | inline _LIBCPP_INLINE_VISIBILITY |
2202 | bool |
2203 | operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
2204 | const multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
2205 | { |
2206 | return __y < __x; |
2207 | } |
2208 | |
2209 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
2210 | inline _LIBCPP_INLINE_VISIBILITY |
2211 | bool |
2212 | operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
2213 | const multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
2214 | { |
2215 | return !(__x < __y); |
2216 | } |
2217 | |
2218 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
2219 | inline _LIBCPP_INLINE_VISIBILITY |
2220 | bool |
2221 | operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
2222 | const multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
2223 | { |
2224 | return !(__y < __x); |
2225 | } |
2226 | |
2227 | template <class _Key, class _Tp, class _Compare, class _Allocator> |
2228 | inline _LIBCPP_INLINE_VISIBILITY |
2229 | void |
2230 | swap(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 |
2238 | template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate> |
2239 | inline _LIBCPP_INLINE_VISIBILITY |
2240 | void erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) |
2241 | { __libcpp_erase_if_container(__c, __pred); } |
2242 | #endif |
2243 | |
2244 | _LIBCPP_END_NAMESPACE_STD |
2245 | |
2246 | #endif // _LIBCPP_MAP |
2247 | |