1 | // -*- C++ -*- |
2 | //===---------------------------- set -------------------------------------===// |
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_SET |
11 | #define _LIBCPP_SET |
12 | |
13 | /* |
14 | |
15 | set synopsis |
16 | |
17 | namespace std |
18 | { |
19 | |
20 | template <class Key, class Compare = less<Key>, |
21 | class Allocator = allocator<Key>> |
22 | class set |
23 | { |
24 | public: |
25 | // types: |
26 | typedef Key key_type; |
27 | typedef key_type value_type; |
28 | typedef Compare key_compare; |
29 | typedef key_compare value_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::size_type size_type; |
34 | typedef typename allocator_type::difference_type difference_type; |
35 | typedef typename allocator_type::pointer pointer; |
36 | typedef typename allocator_type::const_pointer const_pointer; |
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 | // construct/copy/destroy: |
46 | set() |
47 | noexcept( |
48 | is_nothrow_default_constructible<allocator_type>::value && |
49 | is_nothrow_default_constructible<key_compare>::value && |
50 | is_nothrow_copy_constructible<key_compare>::value); |
51 | explicit set(const value_compare& comp); |
52 | set(const value_compare& comp, const allocator_type& a); |
53 | template <class InputIterator> |
54 | set(InputIterator first, InputIterator last, |
55 | const value_compare& comp = value_compare()); |
56 | template <class InputIterator> |
57 | set(InputIterator first, InputIterator last, const value_compare& comp, |
58 | const allocator_type& a); |
59 | set(const set& s); |
60 | set(set&& s) |
61 | noexcept( |
62 | is_nothrow_move_constructible<allocator_type>::value && |
63 | is_nothrow_move_constructible<key_compare>::value); |
64 | explicit set(const allocator_type& a); |
65 | set(const set& s, const allocator_type& a); |
66 | set(set&& s, const allocator_type& a); |
67 | set(initializer_list<value_type> il, const value_compare& comp = value_compare()); |
68 | set(initializer_list<value_type> il, const value_compare& comp, |
69 | const allocator_type& a); |
70 | template <class InputIterator> |
71 | set(InputIterator first, InputIterator last, const allocator_type& a) |
72 | : set(first, last, Compare(), a) {} // C++14 |
73 | set(initializer_list<value_type> il, const allocator_type& a) |
74 | : set(il, Compare(), a) {} // C++14 |
75 | ~set(); |
76 | |
77 | set& operator=(const set& s); |
78 | set& operator=(set&& s) |
79 | noexcept( |
80 | allocator_type::propagate_on_container_move_assignment::value && |
81 | is_nothrow_move_assignable<allocator_type>::value && |
82 | is_nothrow_move_assignable<key_compare>::value); |
83 | set& operator=(initializer_list<value_type> il); |
84 | |
85 | // iterators: |
86 | iterator begin() noexcept; |
87 | const_iterator begin() const noexcept; |
88 | iterator end() noexcept; |
89 | const_iterator end() const noexcept; |
90 | |
91 | reverse_iterator rbegin() noexcept; |
92 | const_reverse_iterator rbegin() const noexcept; |
93 | reverse_iterator rend() noexcept; |
94 | const_reverse_iterator rend() const noexcept; |
95 | |
96 | const_iterator cbegin() const noexcept; |
97 | const_iterator cend() const noexcept; |
98 | const_reverse_iterator crbegin() const noexcept; |
99 | const_reverse_iterator crend() const noexcept; |
100 | |
101 | // capacity: |
102 | bool empty() const noexcept; |
103 | size_type size() const noexcept; |
104 | size_type max_size() const noexcept; |
105 | |
106 | // modifiers: |
107 | template <class... Args> |
108 | pair<iterator, bool> emplace(Args&&... args); |
109 | template <class... Args> |
110 | iterator emplace_hint(const_iterator position, Args&&... args); |
111 | pair<iterator,bool> insert(const value_type& v); |
112 | pair<iterator,bool> insert(value_type&& v); |
113 | iterator insert(const_iterator position, const value_type& v); |
114 | iterator insert(const_iterator position, value_type&& v); |
115 | template <class InputIterator> |
116 | void insert(InputIterator first, InputIterator last); |
117 | void insert(initializer_list<value_type> il); |
118 | |
119 | node_type extract(const_iterator position); // C++17 |
120 | node_type extract(const key_type& x); // C++17 |
121 | insert_return_type insert(node_type&& nh); // C++17 |
122 | iterator insert(const_iterator hint, node_type&& nh); // C++17 |
123 | |
124 | iterator erase(const_iterator position); |
125 | iterator erase(iterator position); // C++14 |
126 | size_type erase(const key_type& k); |
127 | iterator erase(const_iterator first, const_iterator last); |
128 | void clear() noexcept; |
129 | |
130 | template<class C2> |
131 | void merge(set<Key, C2, Allocator>& source); // C++17 |
132 | template<class C2> |
133 | void merge(set<Key, C2, Allocator>&& source); // C++17 |
134 | template<class C2> |
135 | void merge(multiset<Key, C2, Allocator>& source); // C++17 |
136 | template<class C2> |
137 | void merge(multiset<Key, C2, Allocator>&& source); // C++17 |
138 | |
139 | void swap(set& s) |
140 | noexcept( |
141 | __is_nothrow_swappable<key_compare>::value && |
142 | (!allocator_type::propagate_on_container_swap::value || |
143 | __is_nothrow_swappable<allocator_type>::value)); |
144 | |
145 | // observers: |
146 | allocator_type get_allocator() const noexcept; |
147 | key_compare key_comp() const; |
148 | value_compare value_comp() const; |
149 | |
150 | // set operations: |
151 | iterator find(const key_type& k); |
152 | const_iterator find(const key_type& k) const; |
153 | template<typename K> |
154 | iterator find(const K& x); |
155 | template<typename K> |
156 | const_iterator find(const K& x) const; // C++14 |
157 | template<typename K> |
158 | size_type count(const K& x) const; // C++14 |
159 | size_type count(const key_type& k) const; |
160 | bool contains(const key_type& x) const; // C++20 |
161 | iterator lower_bound(const key_type& k); |
162 | const_iterator lower_bound(const key_type& k) const; |
163 | template<typename K> |
164 | iterator lower_bound(const K& x); // C++14 |
165 | template<typename K> |
166 | const_iterator lower_bound(const K& x) const; // C++14 |
167 | |
168 | iterator upper_bound(const key_type& k); |
169 | const_iterator upper_bound(const key_type& k) const; |
170 | template<typename K> |
171 | iterator upper_bound(const K& x); // C++14 |
172 | template<typename K> |
173 | const_iterator upper_bound(const K& x) const; // C++14 |
174 | pair<iterator,iterator> equal_range(const key_type& k); |
175 | pair<const_iterator,const_iterator> equal_range(const key_type& k) const; |
176 | template<typename K> |
177 | pair<iterator,iterator> equal_range(const K& x); // C++14 |
178 | template<typename K> |
179 | pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 |
180 | }; |
181 | |
182 | template <class Key, class Compare, class Allocator> |
183 | bool |
184 | operator==(const set<Key, Compare, Allocator>& x, |
185 | const set<Key, Compare, Allocator>& y); |
186 | |
187 | template <class Key, class Compare, class Allocator> |
188 | bool |
189 | operator< (const set<Key, Compare, Allocator>& x, |
190 | const set<Key, Compare, Allocator>& y); |
191 | |
192 | template <class Key, class Compare, class Allocator> |
193 | bool |
194 | operator!=(const set<Key, Compare, Allocator>& x, |
195 | const set<Key, Compare, Allocator>& y); |
196 | |
197 | template <class Key, class Compare, class Allocator> |
198 | bool |
199 | operator> (const set<Key, Compare, Allocator>& x, |
200 | const set<Key, Compare, Allocator>& y); |
201 | |
202 | template <class Key, class Compare, class Allocator> |
203 | bool |
204 | operator>=(const set<Key, Compare, Allocator>& x, |
205 | const set<Key, Compare, Allocator>& y); |
206 | |
207 | template <class Key, class Compare, class Allocator> |
208 | bool |
209 | operator<=(const set<Key, Compare, Allocator>& x, |
210 | const set<Key, Compare, Allocator>& y); |
211 | |
212 | // specialized algorithms: |
213 | template <class Key, class Compare, class Allocator> |
214 | void |
215 | swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) |
216 | noexcept(noexcept(x.swap(y))); |
217 | |
218 | template <class Key, class Compare, class Allocator, class Predicate> |
219 | void erase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20 |
220 | |
221 | template <class Key, class Compare = less<Key>, |
222 | class Allocator = allocator<Key>> |
223 | class multiset |
224 | { |
225 | public: |
226 | // types: |
227 | typedef Key key_type; |
228 | typedef key_type value_type; |
229 | typedef Compare key_compare; |
230 | typedef key_compare value_compare; |
231 | typedef Allocator allocator_type; |
232 | typedef typename allocator_type::reference reference; |
233 | typedef typename allocator_type::const_reference const_reference; |
234 | typedef typename allocator_type::size_type size_type; |
235 | typedef typename allocator_type::difference_type difference_type; |
236 | typedef typename allocator_type::pointer pointer; |
237 | typedef typename allocator_type::const_pointer const_pointer; |
238 | |
239 | typedef implementation-defined iterator; |
240 | typedef implementation-defined const_iterator; |
241 | typedef std::reverse_iterator<iterator> reverse_iterator; |
242 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
243 | typedef unspecified node_type; // C++17 |
244 | |
245 | // construct/copy/destroy: |
246 | multiset() |
247 | noexcept( |
248 | is_nothrow_default_constructible<allocator_type>::value && |
249 | is_nothrow_default_constructible<key_compare>::value && |
250 | is_nothrow_copy_constructible<key_compare>::value); |
251 | explicit multiset(const value_compare& comp); |
252 | multiset(const value_compare& comp, const allocator_type& a); |
253 | template <class InputIterator> |
254 | multiset(InputIterator first, InputIterator last, |
255 | const value_compare& comp = value_compare()); |
256 | template <class InputIterator> |
257 | multiset(InputIterator first, InputIterator last, |
258 | const value_compare& comp, const allocator_type& a); |
259 | multiset(const multiset& s); |
260 | multiset(multiset&& s) |
261 | noexcept( |
262 | is_nothrow_move_constructible<allocator_type>::value && |
263 | is_nothrow_move_constructible<key_compare>::value); |
264 | explicit multiset(const allocator_type& a); |
265 | multiset(const multiset& s, const allocator_type& a); |
266 | multiset(multiset&& s, const allocator_type& a); |
267 | multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); |
268 | multiset(initializer_list<value_type> il, const value_compare& comp, |
269 | const allocator_type& a); |
270 | template <class InputIterator> |
271 | multiset(InputIterator first, InputIterator last, const allocator_type& a) |
272 | : set(first, last, Compare(), a) {} // C++14 |
273 | multiset(initializer_list<value_type> il, const allocator_type& a) |
274 | : set(il, Compare(), a) {} // C++14 |
275 | ~multiset(); |
276 | |
277 | multiset& operator=(const multiset& s); |
278 | multiset& operator=(multiset&& s) |
279 | noexcept( |
280 | allocator_type::propagate_on_container_move_assignment::value && |
281 | is_nothrow_move_assignable<allocator_type>::value && |
282 | is_nothrow_move_assignable<key_compare>::value); |
283 | multiset& operator=(initializer_list<value_type> il); |
284 | |
285 | // iterators: |
286 | iterator begin() noexcept; |
287 | const_iterator begin() const noexcept; |
288 | iterator end() noexcept; |
289 | const_iterator end() const noexcept; |
290 | |
291 | reverse_iterator rbegin() noexcept; |
292 | const_reverse_iterator rbegin() const noexcept; |
293 | reverse_iterator rend() noexcept; |
294 | const_reverse_iterator rend() const noexcept; |
295 | |
296 | const_iterator cbegin() const noexcept; |
297 | const_iterator cend() const noexcept; |
298 | const_reverse_iterator crbegin() const noexcept; |
299 | const_reverse_iterator crend() const noexcept; |
300 | |
301 | // capacity: |
302 | bool empty() const noexcept; |
303 | size_type size() const noexcept; |
304 | size_type max_size() const noexcept; |
305 | |
306 | // modifiers: |
307 | template <class... Args> |
308 | iterator emplace(Args&&... args); |
309 | template <class... Args> |
310 | iterator emplace_hint(const_iterator position, Args&&... args); |
311 | iterator insert(const value_type& v); |
312 | iterator insert(value_type&& v); |
313 | iterator insert(const_iterator position, const value_type& v); |
314 | iterator insert(const_iterator position, value_type&& v); |
315 | template <class InputIterator> |
316 | void insert(InputIterator first, InputIterator last); |
317 | void insert(initializer_list<value_type> il); |
318 | |
319 | node_type extract(const_iterator position); // C++17 |
320 | node_type extract(const key_type& x); // C++17 |
321 | iterator insert(node_type&& nh); // C++17 |
322 | iterator insert(const_iterator hint, node_type&& nh); // C++17 |
323 | |
324 | iterator erase(const_iterator position); |
325 | iterator erase(iterator position); // C++14 |
326 | size_type erase(const key_type& k); |
327 | iterator erase(const_iterator first, const_iterator last); |
328 | void clear() noexcept; |
329 | |
330 | template<class C2> |
331 | void merge(multiset<Key, C2, Allocator>& source); // C++17 |
332 | template<class C2> |
333 | void merge(multiset<Key, C2, Allocator>&& source); // C++17 |
334 | template<class C2> |
335 | void merge(set<Key, C2, Allocator>& source); // C++17 |
336 | template<class C2> |
337 | void merge(set<Key, C2, Allocator>&& source); // C++17 |
338 | |
339 | void swap(multiset& s) |
340 | noexcept( |
341 | __is_nothrow_swappable<key_compare>::value && |
342 | (!allocator_type::propagate_on_container_swap::value || |
343 | __is_nothrow_swappable<allocator_type>::value)); |
344 | |
345 | // observers: |
346 | allocator_type get_allocator() const noexcept; |
347 | key_compare key_comp() const; |
348 | value_compare value_comp() const; |
349 | |
350 | // set operations: |
351 | iterator find(const key_type& k); |
352 | const_iterator find(const key_type& k) const; |
353 | template<typename K> |
354 | iterator find(const K& x); |
355 | template<typename K> |
356 | const_iterator find(const K& x) const; // C++14 |
357 | template<typename K> |
358 | size_type count(const K& x) const; // C++14 |
359 | size_type count(const key_type& k) const; |
360 | bool contains(const key_type& x) const; // C++20 |
361 | iterator lower_bound(const key_type& k); |
362 | const_iterator lower_bound(const key_type& k) const; |
363 | template<typename K> |
364 | iterator lower_bound(const K& x); // C++14 |
365 | template<typename K> |
366 | const_iterator lower_bound(const K& x) const; // C++14 |
367 | |
368 | iterator upper_bound(const key_type& k); |
369 | const_iterator upper_bound(const key_type& k) const; |
370 | template<typename K> |
371 | iterator upper_bound(const K& x); // C++14 |
372 | template<typename K> |
373 | const_iterator upper_bound(const K& x) const; // C++14 |
374 | |
375 | pair<iterator,iterator> equal_range(const key_type& k); |
376 | pair<const_iterator,const_iterator> equal_range(const key_type& k) const; |
377 | template<typename K> |
378 | pair<iterator,iterator> equal_range(const K& x); // C++14 |
379 | template<typename K> |
380 | pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 |
381 | }; |
382 | |
383 | template <class Key, class Compare, class Allocator> |
384 | bool |
385 | operator==(const multiset<Key, Compare, Allocator>& x, |
386 | const multiset<Key, Compare, Allocator>& y); |
387 | |
388 | template <class Key, class Compare, class Allocator> |
389 | bool |
390 | operator< (const multiset<Key, Compare, Allocator>& x, |
391 | const multiset<Key, Compare, Allocator>& y); |
392 | |
393 | template <class Key, class Compare, class Allocator> |
394 | bool |
395 | operator!=(const multiset<Key, Compare, Allocator>& x, |
396 | const multiset<Key, Compare, Allocator>& y); |
397 | |
398 | template <class Key, class Compare, class Allocator> |
399 | bool |
400 | operator> (const multiset<Key, Compare, Allocator>& x, |
401 | const multiset<Key, Compare, Allocator>& y); |
402 | |
403 | template <class Key, class Compare, class Allocator> |
404 | bool |
405 | operator>=(const multiset<Key, Compare, Allocator>& x, |
406 | const multiset<Key, Compare, Allocator>& y); |
407 | |
408 | template <class Key, class Compare, class Allocator> |
409 | bool |
410 | operator<=(const multiset<Key, Compare, Allocator>& x, |
411 | const multiset<Key, Compare, Allocator>& y); |
412 | |
413 | // specialized algorithms: |
414 | template <class Key, class Compare, class Allocator> |
415 | void |
416 | swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) |
417 | noexcept(noexcept(x.swap(y))); |
418 | |
419 | template <class Key, class Compare, class Allocator, class Predicate> |
420 | void erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20 |
421 | |
422 | } // std |
423 | |
424 | */ |
425 | |
426 | #include <__config> |
427 | #include <__tree> |
428 | #include <__node_handle> |
429 | #include <functional> |
430 | #include <version> |
431 | |
432 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
433 | #pragma GCC system_header |
434 | #endif |
435 | |
436 | _LIBCPP_BEGIN_NAMESPACE_STD |
437 | |
438 | template <class _Key, class _Compare, class _Allocator> |
439 | class multiset; |
440 | |
441 | template <class _Key, class _Compare = less<_Key>, |
442 | class _Allocator = allocator<_Key> > |
443 | class _LIBCPP_TEMPLATE_VIS set |
444 | { |
445 | public: |
446 | // types: |
447 | typedef _Key key_type; |
448 | typedef key_type value_type; |
449 | typedef _Compare key_compare; |
450 | typedef key_compare value_compare; |
451 | typedef typename __identity<_Allocator>::type allocator_type; |
452 | typedef value_type& reference; |
453 | typedef const value_type& const_reference; |
454 | |
455 | static_assert((is_same<typename allocator_type::value_type, value_type>::value), |
456 | "Allocator::value_type must be same type as value_type" ); |
457 | |
458 | private: |
459 | typedef __tree<value_type, value_compare, allocator_type> __base; |
460 | typedef allocator_traits<allocator_type> __alloc_traits; |
461 | typedef typename __base::__node_holder __node_holder; |
462 | |
463 | __base __tree_; |
464 | |
465 | public: |
466 | typedef typename __base::pointer pointer; |
467 | typedef typename __base::const_pointer const_pointer; |
468 | typedef typename __base::size_type size_type; |
469 | typedef typename __base::difference_type difference_type; |
470 | typedef typename __base::const_iterator iterator; |
471 | typedef typename __base::const_iterator const_iterator; |
472 | typedef _VSTD::reverse_iterator<iterator> reverse_iterator; |
473 | typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; |
474 | |
475 | #if _LIBCPP_STD_VER > 14 |
476 | typedef __set_node_handle<typename __base::__node, allocator_type> node_type; |
477 | typedef __insert_return_type<iterator, node_type> insert_return_type; |
478 | #endif |
479 | |
480 | template <class _Key2, class _Compare2, class _Alloc2> |
481 | friend class _LIBCPP_TEMPLATE_VIS set; |
482 | template <class _Key2, class _Compare2, class _Alloc2> |
483 | friend class _LIBCPP_TEMPLATE_VIS multiset; |
484 | |
485 | _LIBCPP_INLINE_VISIBILITY |
486 | set() |
487 | _NOEXCEPT_( |
488 | is_nothrow_default_constructible<allocator_type>::value && |
489 | is_nothrow_default_constructible<key_compare>::value && |
490 | is_nothrow_copy_constructible<key_compare>::value) |
491 | : __tree_(value_compare()) {} |
492 | |
493 | _LIBCPP_INLINE_VISIBILITY |
494 | explicit set(const value_compare& __comp) |
495 | _NOEXCEPT_( |
496 | is_nothrow_default_constructible<allocator_type>::value && |
497 | is_nothrow_copy_constructible<key_compare>::value) |
498 | : __tree_(__comp) {} |
499 | |
500 | _LIBCPP_INLINE_VISIBILITY |
501 | explicit set(const value_compare& __comp, const allocator_type& __a) |
502 | : __tree_(__comp, __a) {} |
503 | template <class _InputIterator> |
504 | _LIBCPP_INLINE_VISIBILITY |
505 | set(_InputIterator __f, _InputIterator __l, |
506 | const value_compare& __comp = value_compare()) |
507 | : __tree_(__comp) |
508 | { |
509 | insert(__f, __l); |
510 | } |
511 | |
512 | template <class _InputIterator> |
513 | _LIBCPP_INLINE_VISIBILITY |
514 | set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, |
515 | const allocator_type& __a) |
516 | : __tree_(__comp, __a) |
517 | { |
518 | insert(__f, __l); |
519 | } |
520 | |
521 | #if _LIBCPP_STD_VER > 11 |
522 | template <class _InputIterator> |
523 | _LIBCPP_INLINE_VISIBILITY |
524 | set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) |
525 | : set(__f, __l, key_compare(), __a) {} |
526 | #endif |
527 | |
528 | _LIBCPP_INLINE_VISIBILITY |
529 | set(const set& __s) |
530 | : __tree_(__s.__tree_) |
531 | { |
532 | insert(__s.begin(), __s.end()); |
533 | } |
534 | |
535 | _LIBCPP_INLINE_VISIBILITY |
536 | set& operator=(const set& __s) |
537 | { |
538 | __tree_ = __s.__tree_; |
539 | return *this; |
540 | } |
541 | |
542 | #ifndef _LIBCPP_CXX03_LANG |
543 | _LIBCPP_INLINE_VISIBILITY |
544 | set(set&& __s) |
545 | _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) |
546 | : __tree_(_VSTD::move(__s.__tree_)) {} |
547 | #endif // _LIBCPP_CXX03_LANG |
548 | |
549 | _LIBCPP_INLINE_VISIBILITY |
550 | explicit set(const allocator_type& __a) |
551 | : __tree_(__a) {} |
552 | |
553 | _LIBCPP_INLINE_VISIBILITY |
554 | set(const set& __s, const allocator_type& __a) |
555 | : __tree_(__s.__tree_.value_comp(), __a) |
556 | { |
557 | insert(__s.begin(), __s.end()); |
558 | } |
559 | |
560 | #ifndef _LIBCPP_CXX03_LANG |
561 | set(set&& __s, const allocator_type& __a); |
562 | |
563 | _LIBCPP_INLINE_VISIBILITY |
564 | set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) |
565 | : __tree_(__comp) |
566 | { |
567 | insert(__il.begin(), __il.end()); |
568 | } |
569 | |
570 | _LIBCPP_INLINE_VISIBILITY |
571 | set(initializer_list<value_type> __il, const value_compare& __comp, |
572 | const allocator_type& __a) |
573 | : __tree_(__comp, __a) |
574 | { |
575 | insert(__il.begin(), __il.end()); |
576 | } |
577 | |
578 | #if _LIBCPP_STD_VER > 11 |
579 | _LIBCPP_INLINE_VISIBILITY |
580 | set(initializer_list<value_type> __il, const allocator_type& __a) |
581 | : set(__il, key_compare(), __a) {} |
582 | #endif |
583 | |
584 | _LIBCPP_INLINE_VISIBILITY |
585 | set& operator=(initializer_list<value_type> __il) |
586 | { |
587 | __tree_.__assign_unique(__il.begin(), __il.end()); |
588 | return *this; |
589 | } |
590 | |
591 | _LIBCPP_INLINE_VISIBILITY |
592 | set& operator=(set&& __s) |
593 | _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) |
594 | { |
595 | __tree_ = _VSTD::move(__s.__tree_); |
596 | return *this; |
597 | } |
598 | #endif // _LIBCPP_CXX03_LANG |
599 | |
600 | _LIBCPP_INLINE_VISIBILITY |
601 | ~set() { |
602 | static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "" ); |
603 | } |
604 | |
605 | _LIBCPP_INLINE_VISIBILITY |
606 | iterator begin() _NOEXCEPT {return __tree_.begin();} |
607 | _LIBCPP_INLINE_VISIBILITY |
608 | const_iterator begin() const _NOEXCEPT {return __tree_.begin();} |
609 | _LIBCPP_INLINE_VISIBILITY |
610 | iterator end() _NOEXCEPT {return __tree_.end();} |
611 | _LIBCPP_INLINE_VISIBILITY |
612 | const_iterator end() const _NOEXCEPT {return __tree_.end();} |
613 | |
614 | _LIBCPP_INLINE_VISIBILITY |
615 | reverse_iterator rbegin() _NOEXCEPT |
616 | {return reverse_iterator(end());} |
617 | _LIBCPP_INLINE_VISIBILITY |
618 | const_reverse_iterator rbegin() const _NOEXCEPT |
619 | {return const_reverse_iterator(end());} |
620 | _LIBCPP_INLINE_VISIBILITY |
621 | reverse_iterator rend() _NOEXCEPT |
622 | {return reverse_iterator(begin());} |
623 | _LIBCPP_INLINE_VISIBILITY |
624 | const_reverse_iterator rend() const _NOEXCEPT |
625 | {return const_reverse_iterator(begin());} |
626 | |
627 | _LIBCPP_INLINE_VISIBILITY |
628 | const_iterator cbegin() const _NOEXCEPT {return begin();} |
629 | _LIBCPP_INLINE_VISIBILITY |
630 | const_iterator cend() const _NOEXCEPT {return end();} |
631 | _LIBCPP_INLINE_VISIBILITY |
632 | const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} |
633 | _LIBCPP_INLINE_VISIBILITY |
634 | const_reverse_iterator crend() const _NOEXCEPT {return rend();} |
635 | |
636 | _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY |
637 | bool empty() const _NOEXCEPT {return __tree_.size() == 0;} |
638 | _LIBCPP_INLINE_VISIBILITY |
639 | size_type size() const _NOEXCEPT {return __tree_.size();} |
640 | _LIBCPP_INLINE_VISIBILITY |
641 | size_type max_size() const _NOEXCEPT {return __tree_.max_size();} |
642 | |
643 | // modifiers: |
644 | #ifndef _LIBCPP_CXX03_LANG |
645 | template <class... _Args> |
646 | _LIBCPP_INLINE_VISIBILITY |
647 | pair<iterator, bool> emplace(_Args&&... __args) |
648 | {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} |
649 | template <class... _Args> |
650 | _LIBCPP_INLINE_VISIBILITY |
651 | iterator emplace_hint(const_iterator __p, _Args&&... __args) |
652 | {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} |
653 | #endif // _LIBCPP_CXX03_LANG |
654 | |
655 | _LIBCPP_INLINE_VISIBILITY |
656 | pair<iterator,bool> insert(const value_type& __v) |
657 | {return __tree_.__insert_unique(__v);} |
658 | _LIBCPP_INLINE_VISIBILITY |
659 | iterator insert(const_iterator __p, const value_type& __v) |
660 | {return __tree_.__insert_unique(__p, __v);} |
661 | |
662 | template <class _InputIterator> |
663 | _LIBCPP_INLINE_VISIBILITY |
664 | void insert(_InputIterator __f, _InputIterator __l) |
665 | { |
666 | for (const_iterator __e = cend(); __f != __l; ++__f) |
667 | __tree_.__insert_unique(__e, *__f); |
668 | } |
669 | |
670 | #ifndef _LIBCPP_CXX03_LANG |
671 | _LIBCPP_INLINE_VISIBILITY |
672 | pair<iterator,bool> insert(value_type&& __v) |
673 | {return __tree_.__insert_unique(_VSTD::move(__v));} |
674 | |
675 | _LIBCPP_INLINE_VISIBILITY |
676 | iterator insert(const_iterator __p, value_type&& __v) |
677 | {return __tree_.__insert_unique(__p, _VSTD::move(__v));} |
678 | |
679 | _LIBCPP_INLINE_VISIBILITY |
680 | void insert(initializer_list<value_type> __il) |
681 | {insert(__il.begin(), __il.end());} |
682 | #endif // _LIBCPP_CXX03_LANG |
683 | |
684 | _LIBCPP_INLINE_VISIBILITY |
685 | iterator erase(const_iterator __p) {return __tree_.erase(__p);} |
686 | _LIBCPP_INLINE_VISIBILITY |
687 | size_type erase(const key_type& __k) |
688 | {return __tree_.__erase_unique(__k);} |
689 | _LIBCPP_INLINE_VISIBILITY |
690 | iterator erase(const_iterator __f, const_iterator __l) |
691 | {return __tree_.erase(__f, __l);} |
692 | _LIBCPP_INLINE_VISIBILITY |
693 | void clear() _NOEXCEPT {__tree_.clear();} |
694 | |
695 | #if _LIBCPP_STD_VER > 14 |
696 | _LIBCPP_INLINE_VISIBILITY |
697 | insert_return_type insert(node_type&& __nh) |
698 | { |
699 | _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), |
700 | "node_type with incompatible allocator passed to set::insert()" ); |
701 | return __tree_.template __node_handle_insert_unique< |
702 | node_type, insert_return_type>(_VSTD::move(__nh)); |
703 | } |
704 | _LIBCPP_INLINE_VISIBILITY |
705 | iterator insert(const_iterator __hint, node_type&& __nh) |
706 | { |
707 | _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), |
708 | "node_type with incompatible allocator passed to set::insert()" ); |
709 | return __tree_.template __node_handle_insert_unique<node_type>( |
710 | __hint, _VSTD::move(__nh)); |
711 | } |
712 | _LIBCPP_INLINE_VISIBILITY |
713 | node_type (key_type const& __key) |
714 | { |
715 | return __tree_.template __node_handle_extract<node_type>(__key); |
716 | } |
717 | _LIBCPP_INLINE_VISIBILITY |
718 | node_type (const_iterator __it) |
719 | { |
720 | return __tree_.template __node_handle_extract<node_type>(__it); |
721 | } |
722 | template <class _Compare2> |
723 | _LIBCPP_INLINE_VISIBILITY |
724 | void merge(set<key_type, _Compare2, allocator_type>& __source) |
725 | { |
726 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
727 | "merging container with incompatible allocator" ); |
728 | __tree_.__node_handle_merge_unique(__source.__tree_); |
729 | } |
730 | template <class _Compare2> |
731 | _LIBCPP_INLINE_VISIBILITY |
732 | void merge(set<key_type, _Compare2, allocator_type>&& __source) |
733 | { |
734 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
735 | "merging container with incompatible allocator" ); |
736 | __tree_.__node_handle_merge_unique(__source.__tree_); |
737 | } |
738 | template <class _Compare2> |
739 | _LIBCPP_INLINE_VISIBILITY |
740 | void merge(multiset<key_type, _Compare2, allocator_type>& __source) |
741 | { |
742 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
743 | "merging container with incompatible allocator" ); |
744 | __tree_.__node_handle_merge_unique(__source.__tree_); |
745 | } |
746 | template <class _Compare2> |
747 | _LIBCPP_INLINE_VISIBILITY |
748 | void merge(multiset<key_type, _Compare2, allocator_type>&& __source) |
749 | { |
750 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
751 | "merging container with incompatible allocator" ); |
752 | __tree_.__node_handle_merge_unique(__source.__tree_); |
753 | } |
754 | #endif |
755 | |
756 | _LIBCPP_INLINE_VISIBILITY |
757 | void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) |
758 | {__tree_.swap(__s.__tree_);} |
759 | |
760 | _LIBCPP_INLINE_VISIBILITY |
761 | allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} |
762 | _LIBCPP_INLINE_VISIBILITY |
763 | key_compare key_comp() const {return __tree_.value_comp();} |
764 | _LIBCPP_INLINE_VISIBILITY |
765 | value_compare value_comp() const {return __tree_.value_comp();} |
766 | |
767 | // set operations: |
768 | _LIBCPP_INLINE_VISIBILITY |
769 | iterator find(const key_type& __k) {return __tree_.find(__k);} |
770 | _LIBCPP_INLINE_VISIBILITY |
771 | const_iterator find(const key_type& __k) const {return __tree_.find(__k);} |
772 | #if _LIBCPP_STD_VER > 11 |
773 | template <typename _K2> |
774 | _LIBCPP_INLINE_VISIBILITY |
775 | typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
776 | find(const _K2& __k) {return __tree_.find(__k);} |
777 | template <typename _K2> |
778 | _LIBCPP_INLINE_VISIBILITY |
779 | typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type |
780 | find(const _K2& __k) const {return __tree_.find(__k);} |
781 | #endif |
782 | |
783 | _LIBCPP_INLINE_VISIBILITY |
784 | size_type count(const key_type& __k) const |
785 | {return __tree_.__count_unique(__k);} |
786 | #if _LIBCPP_STD_VER > 11 |
787 | template <typename _K2> |
788 | _LIBCPP_INLINE_VISIBILITY |
789 | typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type |
790 | count(const _K2& __k) const {return __tree_.__count_multi(__k);} |
791 | #endif |
792 | |
793 | #if _LIBCPP_STD_VER > 17 |
794 | _LIBCPP_INLINE_VISIBILITY |
795 | bool contains(const key_type& __k) const {return find(__k) != end();} |
796 | #endif // _LIBCPP_STD_VER > 17 |
797 | |
798 | _LIBCPP_INLINE_VISIBILITY |
799 | iterator lower_bound(const key_type& __k) |
800 | {return __tree_.lower_bound(__k);} |
801 | _LIBCPP_INLINE_VISIBILITY |
802 | const_iterator lower_bound(const key_type& __k) const |
803 | {return __tree_.lower_bound(__k);} |
804 | #if _LIBCPP_STD_VER > 11 |
805 | template <typename _K2> |
806 | _LIBCPP_INLINE_VISIBILITY |
807 | typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
808 | lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} |
809 | |
810 | template <typename _K2> |
811 | _LIBCPP_INLINE_VISIBILITY |
812 | typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type |
813 | lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} |
814 | #endif |
815 | |
816 | _LIBCPP_INLINE_VISIBILITY |
817 | iterator upper_bound(const key_type& __k) |
818 | {return __tree_.upper_bound(__k);} |
819 | _LIBCPP_INLINE_VISIBILITY |
820 | const_iterator upper_bound(const key_type& __k) const |
821 | {return __tree_.upper_bound(__k);} |
822 | #if _LIBCPP_STD_VER > 11 |
823 | template <typename _K2> |
824 | _LIBCPP_INLINE_VISIBILITY |
825 | typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
826 | upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} |
827 | template <typename _K2> |
828 | _LIBCPP_INLINE_VISIBILITY |
829 | typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type |
830 | upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} |
831 | #endif |
832 | |
833 | _LIBCPP_INLINE_VISIBILITY |
834 | pair<iterator,iterator> equal_range(const key_type& __k) |
835 | {return __tree_.__equal_range_unique(__k);} |
836 | _LIBCPP_INLINE_VISIBILITY |
837 | pair<const_iterator,const_iterator> equal_range(const key_type& __k) const |
838 | {return __tree_.__equal_range_unique(__k);} |
839 | #if _LIBCPP_STD_VER > 11 |
840 | template <typename _K2> |
841 | _LIBCPP_INLINE_VISIBILITY |
842 | typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type |
843 | equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} |
844 | template <typename _K2> |
845 | _LIBCPP_INLINE_VISIBILITY |
846 | typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type |
847 | equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} |
848 | #endif |
849 | }; |
850 | |
851 | #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES |
852 | template<class _InputIterator, |
853 | class _Compare = less<typename iterator_traits<_InputIterator>::value_type>, |
854 | class _Allocator = allocator<typename iterator_traits<_InputIterator>::value_type>, |
855 | class = _EnableIf<__is_allocator<_Allocator>::value, void>, |
856 | class = _EnableIf<!__is_allocator<_Compare>::value, void>> |
857 | set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) |
858 | -> set<typename iterator_traits<_InputIterator>::value_type, _Compare, _Allocator>; |
859 | |
860 | template<class _Key, class _Compare = less<_Key>, |
861 | class _Allocator = allocator<_Key>, |
862 | class = _EnableIf<__is_allocator<_Allocator>::value, void>, |
863 | class = _EnableIf<!__is_allocator<_Compare>::value, void>> |
864 | set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) |
865 | -> set<_Key, _Compare, _Allocator>; |
866 | |
867 | template<class _InputIterator, class _Allocator, |
868 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
869 | set(_InputIterator, _InputIterator, _Allocator) |
870 | -> set<typename iterator_traits<_InputIterator>::value_type, |
871 | less<typename iterator_traits<_InputIterator>::value_type>, _Allocator>; |
872 | |
873 | template<class _Key, class _Allocator, |
874 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
875 | set(initializer_list<_Key>, _Allocator) |
876 | -> set<_Key, less<_Key>, _Allocator>; |
877 | #endif |
878 | |
879 | #ifndef _LIBCPP_CXX03_LANG |
880 | |
881 | template <class _Key, class _Compare, class _Allocator> |
882 | set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) |
883 | : __tree_(_VSTD::move(__s.__tree_), __a) |
884 | { |
885 | if (__a != __s.get_allocator()) |
886 | { |
887 | const_iterator __e = cend(); |
888 | while (!__s.empty()) |
889 | insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); |
890 | } |
891 | } |
892 | |
893 | #endif // _LIBCPP_CXX03_LANG |
894 | |
895 | template <class _Key, class _Compare, class _Allocator> |
896 | inline _LIBCPP_INLINE_VISIBILITY |
897 | bool |
898 | operator==(const set<_Key, _Compare, _Allocator>& __x, |
899 | const set<_Key, _Compare, _Allocator>& __y) |
900 | { |
901 | return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); |
902 | } |
903 | |
904 | template <class _Key, class _Compare, class _Allocator> |
905 | inline _LIBCPP_INLINE_VISIBILITY |
906 | bool |
907 | operator< (const set<_Key, _Compare, _Allocator>& __x, |
908 | const set<_Key, _Compare, _Allocator>& __y) |
909 | { |
910 | return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); |
911 | } |
912 | |
913 | template <class _Key, class _Compare, class _Allocator> |
914 | inline _LIBCPP_INLINE_VISIBILITY |
915 | bool |
916 | operator!=(const set<_Key, _Compare, _Allocator>& __x, |
917 | const set<_Key, _Compare, _Allocator>& __y) |
918 | { |
919 | return !(__x == __y); |
920 | } |
921 | |
922 | template <class _Key, class _Compare, class _Allocator> |
923 | inline _LIBCPP_INLINE_VISIBILITY |
924 | bool |
925 | operator> (const set<_Key, _Compare, _Allocator>& __x, |
926 | const set<_Key, _Compare, _Allocator>& __y) |
927 | { |
928 | return __y < __x; |
929 | } |
930 | |
931 | template <class _Key, class _Compare, class _Allocator> |
932 | inline _LIBCPP_INLINE_VISIBILITY |
933 | bool |
934 | operator>=(const set<_Key, _Compare, _Allocator>& __x, |
935 | const set<_Key, _Compare, _Allocator>& __y) |
936 | { |
937 | return !(__x < __y); |
938 | } |
939 | |
940 | template <class _Key, class _Compare, class _Allocator> |
941 | inline _LIBCPP_INLINE_VISIBILITY |
942 | bool |
943 | operator<=(const set<_Key, _Compare, _Allocator>& __x, |
944 | const set<_Key, _Compare, _Allocator>& __y) |
945 | { |
946 | return !(__y < __x); |
947 | } |
948 | |
949 | // specialized algorithms: |
950 | template <class _Key, class _Compare, class _Allocator> |
951 | inline _LIBCPP_INLINE_VISIBILITY |
952 | void |
953 | swap(set<_Key, _Compare, _Allocator>& __x, |
954 | set<_Key, _Compare, _Allocator>& __y) |
955 | _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
956 | { |
957 | __x.swap(__y); |
958 | } |
959 | |
960 | #if _LIBCPP_STD_VER > 17 |
961 | template <class _Key, class _Compare, class _Allocator, class _Predicate> |
962 | inline _LIBCPP_INLINE_VISIBILITY |
963 | void erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) |
964 | { __libcpp_erase_if_container(__c, __pred); } |
965 | #endif |
966 | |
967 | template <class _Key, class _Compare = less<_Key>, |
968 | class _Allocator = allocator<_Key> > |
969 | class _LIBCPP_TEMPLATE_VIS multiset |
970 | { |
971 | public: |
972 | // types: |
973 | typedef _Key key_type; |
974 | typedef key_type value_type; |
975 | typedef _Compare key_compare; |
976 | typedef key_compare value_compare; |
977 | typedef typename __identity<_Allocator>::type 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 | private: |
985 | typedef __tree<value_type, value_compare, allocator_type> __base; |
986 | typedef allocator_traits<allocator_type> __alloc_traits; |
987 | typedef typename __base::__node_holder __node_holder; |
988 | |
989 | __base __tree_; |
990 | |
991 | public: |
992 | typedef typename __base::pointer pointer; |
993 | typedef typename __base::const_pointer const_pointer; |
994 | typedef typename __base::size_type size_type; |
995 | typedef typename __base::difference_type difference_type; |
996 | typedef typename __base::const_iterator iterator; |
997 | typedef typename __base::const_iterator const_iterator; |
998 | typedef _VSTD::reverse_iterator<iterator> reverse_iterator; |
999 | typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; |
1000 | |
1001 | #if _LIBCPP_STD_VER > 14 |
1002 | typedef __set_node_handle<typename __base::__node, allocator_type> node_type; |
1003 | #endif |
1004 | |
1005 | template <class _Key2, class _Compare2, class _Alloc2> |
1006 | friend class _LIBCPP_TEMPLATE_VIS set; |
1007 | template <class _Key2, class _Compare2, class _Alloc2> |
1008 | friend class _LIBCPP_TEMPLATE_VIS multiset; |
1009 | |
1010 | // construct/copy/destroy: |
1011 | _LIBCPP_INLINE_VISIBILITY |
1012 | multiset() |
1013 | _NOEXCEPT_( |
1014 | is_nothrow_default_constructible<allocator_type>::value && |
1015 | is_nothrow_default_constructible<key_compare>::value && |
1016 | is_nothrow_copy_constructible<key_compare>::value) |
1017 | : __tree_(value_compare()) {} |
1018 | |
1019 | _LIBCPP_INLINE_VISIBILITY |
1020 | explicit multiset(const value_compare& __comp) |
1021 | _NOEXCEPT_( |
1022 | is_nothrow_default_constructible<allocator_type>::value && |
1023 | is_nothrow_copy_constructible<key_compare>::value) |
1024 | : __tree_(__comp) {} |
1025 | |
1026 | _LIBCPP_INLINE_VISIBILITY |
1027 | explicit multiset(const value_compare& __comp, const allocator_type& __a) |
1028 | : __tree_(__comp, __a) {} |
1029 | template <class _InputIterator> |
1030 | _LIBCPP_INLINE_VISIBILITY |
1031 | multiset(_InputIterator __f, _InputIterator __l, |
1032 | const value_compare& __comp = value_compare()) |
1033 | : __tree_(__comp) |
1034 | { |
1035 | insert(__f, __l); |
1036 | } |
1037 | |
1038 | #if _LIBCPP_STD_VER > 11 |
1039 | template <class _InputIterator> |
1040 | _LIBCPP_INLINE_VISIBILITY |
1041 | multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) |
1042 | : multiset(__f, __l, key_compare(), __a) {} |
1043 | #endif |
1044 | |
1045 | template <class _InputIterator> |
1046 | _LIBCPP_INLINE_VISIBILITY |
1047 | multiset(_InputIterator __f, _InputIterator __l, |
1048 | const value_compare& __comp, const allocator_type& __a) |
1049 | : __tree_(__comp, __a) |
1050 | { |
1051 | insert(__f, __l); |
1052 | } |
1053 | |
1054 | _LIBCPP_INLINE_VISIBILITY |
1055 | multiset(const multiset& __s) |
1056 | : __tree_(__s.__tree_.value_comp(), |
1057 | __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) |
1058 | { |
1059 | insert(__s.begin(), __s.end()); |
1060 | } |
1061 | |
1062 | _LIBCPP_INLINE_VISIBILITY |
1063 | multiset& operator=(const multiset& __s) |
1064 | { |
1065 | __tree_ = __s.__tree_; |
1066 | return *this; |
1067 | } |
1068 | |
1069 | #ifndef _LIBCPP_CXX03_LANG |
1070 | _LIBCPP_INLINE_VISIBILITY |
1071 | multiset(multiset&& __s) |
1072 | _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) |
1073 | : __tree_(_VSTD::move(__s.__tree_)) {} |
1074 | |
1075 | multiset(multiset&& __s, const allocator_type& __a); |
1076 | #endif // _LIBCPP_CXX03_LANG |
1077 | _LIBCPP_INLINE_VISIBILITY |
1078 | explicit multiset(const allocator_type& __a) |
1079 | : __tree_(__a) {} |
1080 | _LIBCPP_INLINE_VISIBILITY |
1081 | multiset(const multiset& __s, const allocator_type& __a) |
1082 | : __tree_(__s.__tree_.value_comp(), __a) |
1083 | { |
1084 | insert(__s.begin(), __s.end()); |
1085 | } |
1086 | |
1087 | #ifndef _LIBCPP_CXX03_LANG |
1088 | _LIBCPP_INLINE_VISIBILITY |
1089 | multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) |
1090 | : __tree_(__comp) |
1091 | { |
1092 | insert(__il.begin(), __il.end()); |
1093 | } |
1094 | |
1095 | _LIBCPP_INLINE_VISIBILITY |
1096 | multiset(initializer_list<value_type> __il, const value_compare& __comp, |
1097 | const allocator_type& __a) |
1098 | : __tree_(__comp, __a) |
1099 | { |
1100 | insert(__il.begin(), __il.end()); |
1101 | } |
1102 | |
1103 | #if _LIBCPP_STD_VER > 11 |
1104 | _LIBCPP_INLINE_VISIBILITY |
1105 | multiset(initializer_list<value_type> __il, const allocator_type& __a) |
1106 | : multiset(__il, key_compare(), __a) {} |
1107 | #endif |
1108 | |
1109 | _LIBCPP_INLINE_VISIBILITY |
1110 | multiset& operator=(initializer_list<value_type> __il) |
1111 | { |
1112 | __tree_.__assign_multi(__il.begin(), __il.end()); |
1113 | return *this; |
1114 | } |
1115 | |
1116 | _LIBCPP_INLINE_VISIBILITY |
1117 | multiset& operator=(multiset&& __s) |
1118 | _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) |
1119 | { |
1120 | __tree_ = _VSTD::move(__s.__tree_); |
1121 | return *this; |
1122 | } |
1123 | #endif // _LIBCPP_CXX03_LANG |
1124 | |
1125 | _LIBCPP_INLINE_VISIBILITY |
1126 | ~multiset() { |
1127 | static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "" ); |
1128 | } |
1129 | |
1130 | _LIBCPP_INLINE_VISIBILITY |
1131 | iterator begin() _NOEXCEPT {return __tree_.begin();} |
1132 | _LIBCPP_INLINE_VISIBILITY |
1133 | const_iterator begin() const _NOEXCEPT {return __tree_.begin();} |
1134 | _LIBCPP_INLINE_VISIBILITY |
1135 | iterator end() _NOEXCEPT {return __tree_.end();} |
1136 | _LIBCPP_INLINE_VISIBILITY |
1137 | const_iterator end() const _NOEXCEPT {return __tree_.end();} |
1138 | |
1139 | _LIBCPP_INLINE_VISIBILITY |
1140 | reverse_iterator rbegin() _NOEXCEPT |
1141 | {return reverse_iterator(end());} |
1142 | _LIBCPP_INLINE_VISIBILITY |
1143 | const_reverse_iterator rbegin() const _NOEXCEPT |
1144 | {return const_reverse_iterator(end());} |
1145 | _LIBCPP_INLINE_VISIBILITY |
1146 | reverse_iterator rend() _NOEXCEPT |
1147 | {return reverse_iterator(begin());} |
1148 | _LIBCPP_INLINE_VISIBILITY |
1149 | const_reverse_iterator rend() const _NOEXCEPT |
1150 | {return const_reverse_iterator(begin());} |
1151 | |
1152 | _LIBCPP_INLINE_VISIBILITY |
1153 | const_iterator cbegin() const _NOEXCEPT {return begin();} |
1154 | _LIBCPP_INLINE_VISIBILITY |
1155 | const_iterator cend() const _NOEXCEPT {return end();} |
1156 | _LIBCPP_INLINE_VISIBILITY |
1157 | const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} |
1158 | _LIBCPP_INLINE_VISIBILITY |
1159 | const_reverse_iterator crend() const _NOEXCEPT {return rend();} |
1160 | |
1161 | _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY |
1162 | bool empty() const _NOEXCEPT {return __tree_.size() == 0;} |
1163 | _LIBCPP_INLINE_VISIBILITY |
1164 | size_type size() const _NOEXCEPT {return __tree_.size();} |
1165 | _LIBCPP_INLINE_VISIBILITY |
1166 | size_type max_size() const _NOEXCEPT {return __tree_.max_size();} |
1167 | |
1168 | // modifiers: |
1169 | #ifndef _LIBCPP_CXX03_LANG |
1170 | template <class... _Args> |
1171 | _LIBCPP_INLINE_VISIBILITY |
1172 | iterator emplace(_Args&&... __args) |
1173 | {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} |
1174 | template <class... _Args> |
1175 | _LIBCPP_INLINE_VISIBILITY |
1176 | iterator emplace_hint(const_iterator __p, _Args&&... __args) |
1177 | {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} |
1178 | #endif // _LIBCPP_CXX03_LANG |
1179 | |
1180 | _LIBCPP_INLINE_VISIBILITY |
1181 | iterator insert(const value_type& __v) |
1182 | {return __tree_.__insert_multi(__v);} |
1183 | _LIBCPP_INLINE_VISIBILITY |
1184 | iterator insert(const_iterator __p, const value_type& __v) |
1185 | {return __tree_.__insert_multi(__p, __v);} |
1186 | |
1187 | template <class _InputIterator> |
1188 | _LIBCPP_INLINE_VISIBILITY |
1189 | void insert(_InputIterator __f, _InputIterator __l) |
1190 | { |
1191 | for (const_iterator __e = cend(); __f != __l; ++__f) |
1192 | __tree_.__insert_multi(__e, *__f); |
1193 | } |
1194 | |
1195 | #ifndef _LIBCPP_CXX03_LANG |
1196 | _LIBCPP_INLINE_VISIBILITY |
1197 | iterator insert(value_type&& __v) |
1198 | {return __tree_.__insert_multi(_VSTD::move(__v));} |
1199 | |
1200 | _LIBCPP_INLINE_VISIBILITY |
1201 | iterator insert(const_iterator __p, value_type&& __v) |
1202 | {return __tree_.__insert_multi(__p, _VSTD::move(__v));} |
1203 | |
1204 | _LIBCPP_INLINE_VISIBILITY |
1205 | void insert(initializer_list<value_type> __il) |
1206 | {insert(__il.begin(), __il.end());} |
1207 | #endif // _LIBCPP_CXX03_LANG |
1208 | |
1209 | _LIBCPP_INLINE_VISIBILITY |
1210 | iterator erase(const_iterator __p) {return __tree_.erase(__p);} |
1211 | _LIBCPP_INLINE_VISIBILITY |
1212 | size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} |
1213 | _LIBCPP_INLINE_VISIBILITY |
1214 | iterator erase(const_iterator __f, const_iterator __l) |
1215 | {return __tree_.erase(__f, __l);} |
1216 | _LIBCPP_INLINE_VISIBILITY |
1217 | void clear() _NOEXCEPT {__tree_.clear();} |
1218 | |
1219 | #if _LIBCPP_STD_VER > 14 |
1220 | _LIBCPP_INLINE_VISIBILITY |
1221 | iterator insert(node_type&& __nh) |
1222 | { |
1223 | _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), |
1224 | "node_type with incompatible allocator passed to multiset::insert()" ); |
1225 | return __tree_.template __node_handle_insert_multi<node_type>( |
1226 | _VSTD::move(__nh)); |
1227 | } |
1228 | _LIBCPP_INLINE_VISIBILITY |
1229 | iterator insert(const_iterator __hint, node_type&& __nh) |
1230 | { |
1231 | _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), |
1232 | "node_type with incompatible allocator passed to multiset::insert()" ); |
1233 | return __tree_.template __node_handle_insert_multi<node_type>( |
1234 | __hint, _VSTD::move(__nh)); |
1235 | } |
1236 | _LIBCPP_INLINE_VISIBILITY |
1237 | node_type (key_type const& __key) |
1238 | { |
1239 | return __tree_.template __node_handle_extract<node_type>(__key); |
1240 | } |
1241 | _LIBCPP_INLINE_VISIBILITY |
1242 | node_type (const_iterator __it) |
1243 | { |
1244 | return __tree_.template __node_handle_extract<node_type>(__it); |
1245 | } |
1246 | template <class _Compare2> |
1247 | _LIBCPP_INLINE_VISIBILITY |
1248 | void merge(multiset<key_type, _Compare2, allocator_type>& __source) |
1249 | { |
1250 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
1251 | "merging container with incompatible allocator" ); |
1252 | __tree_.__node_handle_merge_multi(__source.__tree_); |
1253 | } |
1254 | template <class _Compare2> |
1255 | _LIBCPP_INLINE_VISIBILITY |
1256 | void merge(multiset<key_type, _Compare2, allocator_type>&& __source) |
1257 | { |
1258 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
1259 | "merging container with incompatible allocator" ); |
1260 | __tree_.__node_handle_merge_multi(__source.__tree_); |
1261 | } |
1262 | template <class _Compare2> |
1263 | _LIBCPP_INLINE_VISIBILITY |
1264 | void merge(set<key_type, _Compare2, allocator_type>& __source) |
1265 | { |
1266 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
1267 | "merging container with incompatible allocator" ); |
1268 | __tree_.__node_handle_merge_multi(__source.__tree_); |
1269 | } |
1270 | template <class _Compare2> |
1271 | _LIBCPP_INLINE_VISIBILITY |
1272 | void merge(set<key_type, _Compare2, allocator_type>&& __source) |
1273 | { |
1274 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
1275 | "merging container with incompatible allocator" ); |
1276 | __tree_.__node_handle_merge_multi(__source.__tree_); |
1277 | } |
1278 | #endif |
1279 | |
1280 | _LIBCPP_INLINE_VISIBILITY |
1281 | void swap(multiset& __s) |
1282 | _NOEXCEPT_(__is_nothrow_swappable<__base>::value) |
1283 | {__tree_.swap(__s.__tree_);} |
1284 | |
1285 | _LIBCPP_INLINE_VISIBILITY |
1286 | allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} |
1287 | _LIBCPP_INLINE_VISIBILITY |
1288 | key_compare key_comp() const {return __tree_.value_comp();} |
1289 | _LIBCPP_INLINE_VISIBILITY |
1290 | value_compare value_comp() const {return __tree_.value_comp();} |
1291 | |
1292 | // set operations: |
1293 | _LIBCPP_INLINE_VISIBILITY |
1294 | iterator find(const key_type& __k) {return __tree_.find(__k);} |
1295 | _LIBCPP_INLINE_VISIBILITY |
1296 | const_iterator find(const key_type& __k) const {return __tree_.find(__k);} |
1297 | #if _LIBCPP_STD_VER > 11 |
1298 | template <typename _K2> |
1299 | _LIBCPP_INLINE_VISIBILITY |
1300 | typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type |
1301 | find(const _K2& __k) {return __tree_.find(__k);} |
1302 | template <typename _K2> |
1303 | _LIBCPP_INLINE_VISIBILITY |
1304 | typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type |
1305 | find(const _K2& __k) const {return __tree_.find(__k);} |
1306 | #endif |
1307 | |
1308 | _LIBCPP_INLINE_VISIBILITY |
1309 | size_type count(const key_type& __k) const |
1310 | {return __tree_.__count_multi(__k);} |
1311 | #if _LIBCPP_STD_VER > 11 |
1312 | template <typename _K2> |
1313 | _LIBCPP_INLINE_VISIBILITY |
1314 | typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type |
1315 | count(const _K2& __k) const {return __tree_.__count_multi(__k);} |
1316 | #endif |
1317 | |
1318 | #if _LIBCPP_STD_VER > 17 |
1319 | _LIBCPP_INLINE_VISIBILITY |
1320 | bool contains(const key_type& __k) const {return find(__k) != end();} |
1321 | #endif // _LIBCPP_STD_VER > 17 |
1322 | |
1323 | _LIBCPP_INLINE_VISIBILITY |
1324 | iterator lower_bound(const key_type& __k) |
1325 | {return __tree_.lower_bound(__k);} |
1326 | _LIBCPP_INLINE_VISIBILITY |
1327 | const_iterator lower_bound(const key_type& __k) const |
1328 | {return __tree_.lower_bound(__k);} |
1329 | #if _LIBCPP_STD_VER > 11 |
1330 | template <typename _K2> |
1331 | _LIBCPP_INLINE_VISIBILITY |
1332 | typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type |
1333 | lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} |
1334 | |
1335 | template <typename _K2> |
1336 | _LIBCPP_INLINE_VISIBILITY |
1337 | typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type |
1338 | lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} |
1339 | #endif |
1340 | |
1341 | _LIBCPP_INLINE_VISIBILITY |
1342 | iterator upper_bound(const key_type& __k) |
1343 | {return __tree_.upper_bound(__k);} |
1344 | _LIBCPP_INLINE_VISIBILITY |
1345 | const_iterator upper_bound(const key_type& __k) const |
1346 | {return __tree_.upper_bound(__k);} |
1347 | #if _LIBCPP_STD_VER > 11 |
1348 | template <typename _K2> |
1349 | _LIBCPP_INLINE_VISIBILITY |
1350 | typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type |
1351 | upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} |
1352 | template <typename _K2> |
1353 | _LIBCPP_INLINE_VISIBILITY |
1354 | typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type |
1355 | upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} |
1356 | #endif |
1357 | |
1358 | _LIBCPP_INLINE_VISIBILITY |
1359 | pair<iterator,iterator> equal_range(const key_type& __k) |
1360 | {return __tree_.__equal_range_multi(__k);} |
1361 | _LIBCPP_INLINE_VISIBILITY |
1362 | pair<const_iterator,const_iterator> equal_range(const key_type& __k) const |
1363 | {return __tree_.__equal_range_multi(__k);} |
1364 | #if _LIBCPP_STD_VER > 11 |
1365 | template <typename _K2> |
1366 | _LIBCPP_INLINE_VISIBILITY |
1367 | typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type |
1368 | equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} |
1369 | template <typename _K2> |
1370 | _LIBCPP_INLINE_VISIBILITY |
1371 | typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type |
1372 | equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} |
1373 | #endif |
1374 | }; |
1375 | |
1376 | #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES |
1377 | template<class _InputIterator, |
1378 | class _Compare = less<typename iterator_traits<_InputIterator>::value_type>, |
1379 | class _Allocator = allocator<typename iterator_traits<_InputIterator>::value_type>, |
1380 | class = _EnableIf<__is_allocator<_Allocator>::value, void>, |
1381 | class = _EnableIf<!__is_allocator<_Compare>::value, void>> |
1382 | multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) |
1383 | -> multiset<typename iterator_traits<_InputIterator>::value_type, _Compare, _Allocator>; |
1384 | |
1385 | template<class _Key, class _Compare = less<_Key>, |
1386 | class _Allocator = allocator<_Key>, |
1387 | class = _EnableIf<__is_allocator<_Allocator>::value, void>, |
1388 | class = _EnableIf<!__is_allocator<_Compare>::value, void>> |
1389 | multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) |
1390 | -> multiset<_Key, _Compare, _Allocator>; |
1391 | |
1392 | template<class _InputIterator, class _Allocator, |
1393 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
1394 | multiset(_InputIterator, _InputIterator, _Allocator) |
1395 | -> multiset<typename iterator_traits<_InputIterator>::value_type, |
1396 | less<typename iterator_traits<_InputIterator>::value_type>, _Allocator>; |
1397 | |
1398 | template<class _Key, class _Allocator, |
1399 | class = _EnableIf<__is_allocator<_Allocator>::value, void>> |
1400 | multiset(initializer_list<_Key>, _Allocator) |
1401 | -> multiset<_Key, less<_Key>, _Allocator>; |
1402 | #endif |
1403 | |
1404 | #ifndef _LIBCPP_CXX03_LANG |
1405 | |
1406 | template <class _Key, class _Compare, class _Allocator> |
1407 | multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) |
1408 | : __tree_(_VSTD::move(__s.__tree_), __a) |
1409 | { |
1410 | if (__a != __s.get_allocator()) |
1411 | { |
1412 | const_iterator __e = cend(); |
1413 | while (!__s.empty()) |
1414 | insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); |
1415 | } |
1416 | } |
1417 | |
1418 | #endif // _LIBCPP_CXX03_LANG |
1419 | |
1420 | template <class _Key, class _Compare, class _Allocator> |
1421 | inline _LIBCPP_INLINE_VISIBILITY |
1422 | bool |
1423 | operator==(const multiset<_Key, _Compare, _Allocator>& __x, |
1424 | const multiset<_Key, _Compare, _Allocator>& __y) |
1425 | { |
1426 | return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); |
1427 | } |
1428 | |
1429 | template <class _Key, class _Compare, class _Allocator> |
1430 | inline _LIBCPP_INLINE_VISIBILITY |
1431 | bool |
1432 | operator< (const multiset<_Key, _Compare, _Allocator>& __x, |
1433 | const multiset<_Key, _Compare, _Allocator>& __y) |
1434 | { |
1435 | return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); |
1436 | } |
1437 | |
1438 | template <class _Key, class _Compare, class _Allocator> |
1439 | inline _LIBCPP_INLINE_VISIBILITY |
1440 | bool |
1441 | operator!=(const multiset<_Key, _Compare, _Allocator>& __x, |
1442 | const multiset<_Key, _Compare, _Allocator>& __y) |
1443 | { |
1444 | return !(__x == __y); |
1445 | } |
1446 | |
1447 | template <class _Key, class _Compare, class _Allocator> |
1448 | inline _LIBCPP_INLINE_VISIBILITY |
1449 | bool |
1450 | operator> (const multiset<_Key, _Compare, _Allocator>& __x, |
1451 | const multiset<_Key, _Compare, _Allocator>& __y) |
1452 | { |
1453 | return __y < __x; |
1454 | } |
1455 | |
1456 | template <class _Key, class _Compare, class _Allocator> |
1457 | inline _LIBCPP_INLINE_VISIBILITY |
1458 | bool |
1459 | operator>=(const multiset<_Key, _Compare, _Allocator>& __x, |
1460 | const multiset<_Key, _Compare, _Allocator>& __y) |
1461 | { |
1462 | return !(__x < __y); |
1463 | } |
1464 | |
1465 | template <class _Key, class _Compare, class _Allocator> |
1466 | inline _LIBCPP_INLINE_VISIBILITY |
1467 | bool |
1468 | operator<=(const multiset<_Key, _Compare, _Allocator>& __x, |
1469 | const multiset<_Key, _Compare, _Allocator>& __y) |
1470 | { |
1471 | return !(__y < __x); |
1472 | } |
1473 | |
1474 | template <class _Key, class _Compare, class _Allocator> |
1475 | inline _LIBCPP_INLINE_VISIBILITY |
1476 | void |
1477 | swap(multiset<_Key, _Compare, _Allocator>& __x, |
1478 | multiset<_Key, _Compare, _Allocator>& __y) |
1479 | _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
1480 | { |
1481 | __x.swap(__y); |
1482 | } |
1483 | |
1484 | #if _LIBCPP_STD_VER > 17 |
1485 | template <class _Key, class _Compare, class _Allocator, class _Predicate> |
1486 | inline _LIBCPP_INLINE_VISIBILITY |
1487 | void erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) |
1488 | { __libcpp_erase_if_container(__c, __pred); } |
1489 | #endif |
1490 | |
1491 | _LIBCPP_END_NAMESPACE_STD |
1492 | |
1493 | #endif // _LIBCPP_SET |
1494 | |