Debian Codegraph @

libcxx/include/__cxx03/set

raw
1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef _LIBCPP___CXX03_SET
11 #define _LIBCPP___CXX03_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 template<container-compatible-range<value_type> R>
60 set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
61 set(const set& s);
62 set(set&& s)
63 noexcept(
64 is_nothrow_move_constructible<allocator_type>::value &&
65 is_nothrow_move_constructible<key_compare>::value);
66 explicit set(const allocator_type& a);
67 set(const set& s, const allocator_type& a);
68 set(set&& s, const allocator_type& a);
69 set(initializer_list<value_type> il, const value_compare& comp = value_compare());
70 set(initializer_list<value_type> il, const value_compare& comp,
71 const allocator_type& a);
72 template <class InputIterator>
73 set(InputIterator first, InputIterator last, const allocator_type& a)
74 : set(first, last, Compare(), a) {} // C++14
75 template<container-compatible-range<value_type> R>
76 set(from_range_t, R&& rg, const Allocator& a))
77 : set(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
78 set(initializer_list<value_type> il, const allocator_type& a)
79 : set(il, Compare(), a) {} // C++14
80 ~set();
81
82 set& operator=(const set& s);
83 set& operator=(set&& s)
84 noexcept(
85 allocator_type::propagate_on_container_move_assignment::value &&
86 is_nothrow_move_assignable<allocator_type>::value &&
87 is_nothrow_move_assignable<key_compare>::value);
88 set& operator=(initializer_list<value_type> il);
89
90 // iterators:
91 iterator begin() noexcept;
92 const_iterator begin() const noexcept;
93 iterator end() noexcept;
94 const_iterator end() const noexcept;
95
96 reverse_iterator rbegin() noexcept;
97 const_reverse_iterator rbegin() const noexcept;
98 reverse_iterator rend() noexcept;
99 const_reverse_iterator rend() const noexcept;
100
101 const_iterator cbegin() const noexcept;
102 const_iterator cend() const noexcept;
103 const_reverse_iterator crbegin() const noexcept;
104 const_reverse_iterator crend() const noexcept;
105
106 // capacity:
107 bool empty() const noexcept;
108 size_type size() const noexcept;
109 size_type max_size() const noexcept;
110
111 // modifiers:
112 template <class... Args>
113 pair<iterator, bool> emplace(Args&&... args);
114 template <class... Args>
115 iterator emplace_hint(const_iterator position, Args&&... args);
116 pair<iterator,bool> insert(const value_type& v);
117 pair<iterator,bool> insert(value_type&& v);
118 iterator insert(const_iterator position, const value_type& v);
119 iterator insert(const_iterator position, value_type&& v);
120 template <class InputIterator>
121 void insert(InputIterator first, InputIterator last);
122 template<container-compatible-range<value_type> R>
123 void insert_range(R&& rg); // C++23
124 void insert(initializer_list<value_type> il);
125
126 node_type extract(const_iterator position); // C++17
127 node_type extract(const key_type& x); // C++17
128 insert_return_type insert(node_type&& nh); // C++17
129 iterator insert(const_iterator hint, node_type&& nh); // C++17
130
131 iterator erase(const_iterator position);
132 iterator erase(iterator position); // C++14
133 size_type erase(const key_type& k);
134 iterator erase(const_iterator first, const_iterator last);
135 void clear() noexcept;
136
137 template<class C2>
138 void merge(set<Key, C2, Allocator>& source); // C++17
139 template<class C2>
140 void merge(set<Key, C2, Allocator>&& source); // C++17
141 template<class C2>
142 void merge(multiset<Key, C2, Allocator>& source); // C++17
143 template<class C2>
144 void merge(multiset<Key, C2, Allocator>&& source); // C++17
145
146 void swap(set& s)
147 noexcept(
148 __is_nothrow_swappable<key_compare>::value &&
149 (!allocator_type::propagate_on_container_swap::value ||
150 __is_nothrow_swappable<allocator_type>::value));
151
152 // observers:
153 allocator_type get_allocator() const noexcept;
154 key_compare key_comp() const;
155 value_compare value_comp() const;
156
157 // set operations:
158 iterator find(const key_type& k);
159 const_iterator find(const key_type& k) const;
160 template<typename K>
161 iterator find(const K& x);
162 template<typename K>
163 const_iterator find(const K& x) const; // C++14
164
165 template<typename K>
166 size_type count(const K& x) const; // C++14
167 size_type count(const key_type& k) const;
168
169 bool contains(const key_type& x) const; // C++20
170 template<class K> bool contains(const K& x) const; // C++20
171
172 iterator lower_bound(const key_type& k);
173 const_iterator lower_bound(const key_type& k) const;
174 template<typename K>
175 iterator lower_bound(const K& x); // C++14
176 template<typename K>
177 const_iterator lower_bound(const K& x) const; // C++14
178
179 iterator upper_bound(const key_type& k);
180 const_iterator upper_bound(const key_type& k) const;
181 template<typename K>
182 iterator upper_bound(const K& x); // C++14
183 template<typename K>
184 const_iterator upper_bound(const K& x) const; // C++14
185 pair<iterator,iterator> equal_range(const key_type& k);
186 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
187 template<typename K>
188 pair<iterator,iterator> equal_range(const K& x); // C++14
189 template<typename K>
190 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
191 };
192
193 template <class InputIterator,
194 class Compare = less<typename iterator_traits<InputIterator>::value_type>,
195 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
196 set(InputIterator, InputIterator,
197 Compare = Compare(), Allocator = Allocator())
198 -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17
199
200 template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
201 class Allocator = allocator<ranges::range_value_t<R>>>
202 set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
203 -> set<ranges::range_value_t<R>, Compare, Allocator>; // C++23
204
205 template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
206 set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
207 -> set<Key, Compare, Allocator>; // C++17
208
209 template<class InputIterator, class Allocator>
210 set(InputIterator, InputIterator, Allocator)
211 -> set<typename iterator_traits<InputIterator>::value_type,
212 less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
213
214 template<ranges::input_range R, class Allocator>
215 set(from_range_t, R&&, Allocator)
216 -> set<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>; // C++23
217
218 template<class Key, class Allocator>
219 set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>; // C++17
220
221 template <class Key, class Compare, class Allocator>
222 bool
223 operator==(const set<Key, Compare, Allocator>& x,
224 const set<Key, Compare, Allocator>& y);
225
226 template <class Key, class Compare, class Allocator>
227 bool
228 operator< (const set<Key, Compare, Allocator>& x,
229 const set<Key, Compare, Allocator>& y); // removed in C++20
230
231 template <class Key, class Compare, class Allocator>
232 bool
233 operator!=(const set<Key, Compare, Allocator>& x,
234 const set<Key, Compare, Allocator>& y); // removed in C++20
235
236 template <class Key, class Compare, class Allocator>
237 bool
238 operator> (const set<Key, Compare, Allocator>& x,
239 const set<Key, Compare, Allocator>& y); // removed in C++20
240
241 template <class Key, class Compare, class Allocator>
242 bool
243 operator>=(const set<Key, Compare, Allocator>& x,
244 const set<Key, Compare, Allocator>& y); // removed in C++20
245
246 template <class Key, class Compare, class Allocator>
247 bool
248 operator<=(const set<Key, Compare, Allocator>& x,
249 const set<Key, Compare, Allocator>& y); // removed in C++20
250
251 template<class Key, class Compare, class Allocator>
252 synth-three-way-result<Key> operator<=>(const set<Key, Compare, Allocator>& x,
253 const set<Key, Compare, Allocator>& y); // since C++20
254
255 // specialized algorithms:
256 template <class Key, class Compare, class Allocator>
257 void
258 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
259 noexcept(noexcept(x.swap(y)));
260
261 template <class Key, class Compare, class Allocator, class Predicate>
262 typename set<Key, Compare, Allocator>::size_type
263 erase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20
264
265 template <class Key, class Compare = less<Key>,
266 class Allocator = allocator<Key>>
267 class multiset
268 {
269 public:
270 // types:
271 typedef Key key_type;
272 typedef key_type value_type;
273 typedef Compare key_compare;
274 typedef key_compare value_compare;
275 typedef Allocator allocator_type;
276 typedef typename allocator_type::reference reference;
277 typedef typename allocator_type::const_reference const_reference;
278 typedef typename allocator_type::size_type size_type;
279 typedef typename allocator_type::difference_type difference_type;
280 typedef typename allocator_type::pointer pointer;
281 typedef typename allocator_type::const_pointer const_pointer;
282
283 typedef implementation-defined iterator;
284 typedef implementation-defined const_iterator;
285 typedef std::reverse_iterator<iterator> reverse_iterator;
286 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
287 typedef unspecified node_type; // C++17
288
289 // construct/copy/destroy:
290 multiset()
291 noexcept(
292 is_nothrow_default_constructible<allocator_type>::value &&
293 is_nothrow_default_constructible<key_compare>::value &&
294 is_nothrow_copy_constructible<key_compare>::value);
295 explicit multiset(const value_compare& comp);
296 multiset(const value_compare& comp, const allocator_type& a);
297 template <class InputIterator>
298 multiset(InputIterator first, InputIterator last,
299 const value_compare& comp = value_compare());
300 template <class InputIterator>
301 multiset(InputIterator first, InputIterator last,
302 const value_compare& comp, const allocator_type& a);
303 template<container-compatible-range<value_type> R>
304 multiset(from_range_t, R&& rg,
305 const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
306 multiset(const multiset& s);
307 multiset(multiset&& s)
308 noexcept(
309 is_nothrow_move_constructible<allocator_type>::value &&
310 is_nothrow_move_constructible<key_compare>::value);
311 explicit multiset(const allocator_type& a);
312 multiset(const multiset& s, const allocator_type& a);
313 multiset(multiset&& s, const allocator_type& a);
314 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
315 multiset(initializer_list<value_type> il, const value_compare& comp,
316 const allocator_type& a);
317 template <class InputIterator>
318 multiset(InputIterator first, InputIterator last, const allocator_type& a)
319 : set(first, last, Compare(), a) {} // C++14
320 template<container-compatible-range<value_type> R>
321 multiset(from_range_t, R&& rg, const Allocator& a))
322 : multiset(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
323 multiset(initializer_list<value_type> il, const allocator_type& a)
324 : set(il, Compare(), a) {} // C++14
325 ~multiset();
326
327 multiset& operator=(const multiset& s);
328 multiset& operator=(multiset&& s)
329 noexcept(
330 allocator_type::propagate_on_container_move_assignment::value &&
331 is_nothrow_move_assignable<allocator_type>::value &&
332 is_nothrow_move_assignable<key_compare>::value);
333 multiset& operator=(initializer_list<value_type> il);
334
335 // iterators:
336 iterator begin() noexcept;
337 const_iterator begin() const noexcept;
338 iterator end() noexcept;
339 const_iterator end() const noexcept;
340
341 reverse_iterator rbegin() noexcept;
342 const_reverse_iterator rbegin() const noexcept;
343 reverse_iterator rend() noexcept;
344 const_reverse_iterator rend() const noexcept;
345
346 const_iterator cbegin() const noexcept;
347 const_iterator cend() const noexcept;
348 const_reverse_iterator crbegin() const noexcept;
349 const_reverse_iterator crend() const noexcept;
350
351 // capacity:
352 bool empty() const noexcept;
353 size_type size() const noexcept;
354 size_type max_size() const noexcept;
355
356 // modifiers:
357 template <class... Args>
358 iterator emplace(Args&&... args);
359 template <class... Args>
360 iterator emplace_hint(const_iterator position, Args&&... args);
361 iterator insert(const value_type& v);
362 iterator insert(value_type&& v);
363 iterator insert(const_iterator position, const value_type& v);
364 iterator insert(const_iterator position, value_type&& v);
365 template <class InputIterator>
366 void insert(InputIterator first, InputIterator last);
367 template<container-compatible-range<value_type> R>
368 void insert_range(R&& rg); // C++23
369 void insert(initializer_list<value_type> il);
370
371 node_type extract(const_iterator position); // C++17
372 node_type extract(const key_type& x); // C++17
373 iterator insert(node_type&& nh); // C++17
374 iterator insert(const_iterator hint, node_type&& nh); // C++17
375
376 iterator erase(const_iterator position);
377 iterator erase(iterator position); // C++14
378 size_type erase(const key_type& k);
379 iterator erase(const_iterator first, const_iterator last);
380 void clear() noexcept;
381
382 template<class C2>
383 void merge(multiset<Key, C2, Allocator>& source); // C++17
384 template<class C2>
385 void merge(multiset<Key, C2, Allocator>&& source); // C++17
386 template<class C2>
387 void merge(set<Key, C2, Allocator>& source); // C++17
388 template<class C2>
389 void merge(set<Key, C2, Allocator>&& source); // C++17
390
391 void swap(multiset& s)
392 noexcept(
393 __is_nothrow_swappable<key_compare>::value &&
394 (!allocator_type::propagate_on_container_swap::value ||
395 __is_nothrow_swappable<allocator_type>::value));
396
397 // observers:
398 allocator_type get_allocator() const noexcept;
399 key_compare key_comp() const;
400 value_compare value_comp() const;
401
402 // set operations:
403 iterator find(const key_type& k);
404 const_iterator find(const key_type& k) const;
405 template<typename K>
406 iterator find(const K& x);
407 template<typename K>
408 const_iterator find(const K& x) const; // C++14
409
410 template<typename K>
411 size_type count(const K& x) const; // C++14
412 size_type count(const key_type& k) const;
413
414 bool contains(const key_type& x) const; // C++20
415 template<class K> bool contains(const K& x) const; // C++20
416
417 iterator lower_bound(const key_type& k);
418 const_iterator lower_bound(const key_type& k) const;
419 template<typename K>
420 iterator lower_bound(const K& x); // C++14
421 template<typename K>
422 const_iterator lower_bound(const K& x) const; // C++14
423
424 iterator upper_bound(const key_type& k);
425 const_iterator upper_bound(const key_type& k) const;
426 template<typename K>
427 iterator upper_bound(const K& x); // C++14
428 template<typename K>
429 const_iterator upper_bound(const K& x) const; // C++14
430
431 pair<iterator,iterator> equal_range(const key_type& k);
432 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
433 template<typename K>
434 pair<iterator,iterator> equal_range(const K& x); // C++14
435 template<typename K>
436 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
437 };
438
439 template <class InputIterator,
440 class Compare = less<typename iterator_traits<InputIterator>::value_type>,
441 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
442 multiset(InputIterator, InputIterator,
443 Compare = Compare(), Allocator = Allocator())
444 -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17
445
446 template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
447 class Allocator = allocator<ranges::range_value_t<R>>>
448 multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
449 -> multiset<ranges::range_value_t<R>, Compare, Allocator>;
450
451 template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
452 multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
453 -> multiset<Key, Compare, Allocator>; // C++17
454
455 template<class InputIterator, class Allocator>
456 multiset(InputIterator, InputIterator, Allocator)
457 -> multiset<typename iterator_traits<InputIterator>::value_type,
458 less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
459
460 template<ranges::input_range R, class Allocator>
461 multiset(from_range_t, R&&, Allocator)
462 -> multiset<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>;
463
464 template<class Key, class Allocator>
465 multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>; // C++17
466
467 template <class Key, class Compare, class Allocator>
468 bool
469 operator==(const multiset<Key, Compare, Allocator>& x,
470 const multiset<Key, Compare, Allocator>& y);
471
472 template <class Key, class Compare, class Allocator>
473 bool
474 operator< (const multiset<Key, Compare, Allocator>& x,
475 const multiset<Key, Compare, Allocator>& y); // removed in C++20
476
477 template <class Key, class Compare, class Allocator>
478 bool
479 operator!=(const multiset<Key, Compare, Allocator>& x,
480 const multiset<Key, Compare, Allocator>& y); // removed in C++20
481
482 template <class Key, class Compare, class Allocator>
483 bool
484 operator> (const multiset<Key, Compare, Allocator>& x,
485 const multiset<Key, Compare, Allocator>& y); // removed in C++20
486
487 template <class Key, class Compare, class Allocator>
488 bool
489 operator>=(const multiset<Key, Compare, Allocator>& x,
490 const multiset<Key, Compare, Allocator>& y); // removed in C++20
491
492 template <class Key, class Compare, class Allocator>
493 bool
494 operator<=(const multiset<Key, Compare, Allocator>& x,
495 const multiset<Key, Compare, Allocator>& y); // removed in C++20
496
497 template<class Key, class Compare, class Allocator>
498 synth-three-way-result<Key> operator<=>(const multiset<Key, Compare, Allocator>& x,
499 const multiset<Key, Compare, Allocator>& y); // since C++20
500
501 // specialized algorithms:
502 template <class Key, class Compare, class Allocator>
503 void
504 swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
505 noexcept(noexcept(x.swap(y)));
506
507 template <class Key, class Compare, class Allocator, class Predicate>
508 typename multiset<Key, Compare, Allocator>::size_type
509 erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20
510
511 } // std
512
513 */
514
515 #include <__cxx03/__algorithm/equal.h>
516 #include <__cxx03/__algorithm/lexicographical_compare.h>
517 #include <__cxx03/__assert>
518 #include <__cxx03/__config>
519 #include <__cxx03/__functional/operations.h>
520 #include <__cxx03/__iterator/erase_if_container.h>
521 #include <__cxx03/__iterator/iterator_traits.h>
522 #include <__cxx03/__iterator/reverse_iterator.h>
523 #include <__cxx03/__memory/allocator.h>
524 #include <__cxx03/__tree>
525 #include <__cxx03/__type_traits/is_allocator.h>
526 #include <__cxx03/__utility/forward.h>
527 #include <__cxx03/version>
528
529 // standard-mandated includes
530
531 // [iterator.range]
532 #include <__cxx03/__iterator/access.h>
533
534 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
535 # pragma GCC system_header
536 #endif
537
538 _LIBCPP_PUSH_MACROS
539 #include <__cxx03/__undef_macros>
540
541 _LIBCPP_BEGIN_NAMESPACE_STD
542
543 template <class _Key, class _Compare, class _Allocator>
544 class multiset;
545
546 template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
547 class _LIBCPP_TEMPLATE_VIS set {
548 public:
549 // types:
550 typedef _Key key_type;
551 typedef key_type value_type;
552 typedef __type_identity_t<_Compare> key_compare;
553 typedef key_compare value_compare;
554 typedef __type_identity_t<_Allocator> allocator_type;
555 typedef value_type& reference;
556 typedef const value_type& const_reference;
557
558 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
559 "Allocator::value_type must be same type as value_type");
560
561 private:
562 typedef __tree<value_type, value_compare, allocator_type> __base;
563 typedef allocator_traits<allocator_type> __alloc_traits;
564
565 static_assert(__check_valid_allocator<allocator_type>::value, "");
566
567 __base __tree_;
568
569 public:
570 typedef typename __base::pointer pointer;
571 typedef typename __base::const_pointer const_pointer;
572 typedef typename __base::size_type size_type;
573 typedef typename __base::difference_type difference_type;
574 typedef typename __base::const_iterator iterator;
575 typedef typename __base::const_iterator const_iterator;
576 typedef std::reverse_iterator<iterator> reverse_iterator;
577 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
578
579 template <class _Key2, class _Compare2, class _Alloc2>
580 friend class _LIBCPP_TEMPLATE_VIS set;
581 template <class _Key2, class _Compare2, class _Alloc2>
582 friend class _LIBCPP_TEMPLATE_VIS multiset;
583
584 _LIBCPP_HIDE_FROM_ABI set() : __tree_(value_compare()) {}
585
586 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp) : __tree_(__comp) {}
587
588 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {}
589 template <class _InputIterator>
590 _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
591 : __tree_(__comp) {
592 insert(__f, __l);
593 }
594
595 template <class _InputIterator>
596 _LIBCPP_HIDE_FROM_ABI
597 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
598 : __tree_(__comp, __a) {
599 insert(__f, __l);
600 }
601
602 _LIBCPP_HIDE_FROM_ABI set(const set& __s) : __tree_(__s.__tree_) { insert(__s.begin(), __s.end()); }
603
604 _LIBCPP_HIDE_FROM_ABI set& operator=(const set& __s) {
605 __tree_ = __s.__tree_;
606 return *this;
607 }
608
609 _LIBCPP_HIDE_FROM_ABI explicit set(const allocator_type& __a) : __tree_(__a) {}
610
611 _LIBCPP_HIDE_FROM_ABI set(const set& __s, const allocator_type& __a) : __tree_(__s.__tree_.value_comp(), __a) {
612 insert(__s.begin(), __s.end());
613 }
614
615 _LIBCPP_HIDE_FROM_ABI ~set() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
616
617 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
618 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
619 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
620 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
621
622 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
623 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
624 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
625 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
626
627 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
628 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
629 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
630 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
631
632 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
633 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
634 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
635
636 // modifiers:
637 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
638 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
639 return __tree_.__insert_unique(__p, __v);
640 }
641
642 template <class _InputIterator>
643 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
644 for (const_iterator __e = cend(); __f != __l; ++__f)
645 __tree_.__insert_unique(__e, *__f);
646 }
647
648 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
649 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
650 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
651 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
652
653 _LIBCPP_HIDE_FROM_ABI void swap(set& __s) { __tree_.swap(__s.__tree_); }
654
655 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
656 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
657 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
658
659 // set operations:
660 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
661 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
662
663 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
664
665 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
666 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
667
668 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
669 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
670
671 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
672 return __tree_.__equal_range_unique(__k);
673 }
674 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
675 return __tree_.__equal_range_unique(__k);
676 }
677 };
678
679 template <class _Key, class _Compare, class _Allocator>
680 inline _LIBCPP_HIDE_FROM_ABI bool
681 operator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
682 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
683 }
684
685 template <class _Key, class _Compare, class _Allocator>
686 inline _LIBCPP_HIDE_FROM_ABI bool
687 operator<(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
688 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
689 }
690
691 template <class _Key, class _Compare, class _Allocator>
692 inline _LIBCPP_HIDE_FROM_ABI bool
693 operator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
694 return !(__x == __y);
695 }
696
697 template <class _Key, class _Compare, class _Allocator>
698 inline _LIBCPP_HIDE_FROM_ABI bool
699 operator>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
700 return __y < __x;
701 }
702
703 template <class _Key, class _Compare, class _Allocator>
704 inline _LIBCPP_HIDE_FROM_ABI bool
705 operator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
706 return !(__x < __y);
707 }
708
709 template <class _Key, class _Compare, class _Allocator>
710 inline _LIBCPP_HIDE_FROM_ABI bool
711 operator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
712 return !(__y < __x);
713 }
714
715 // specialized algorithms:
716 template <class _Key, class _Compare, class _Allocator>
717 inline _LIBCPP_HIDE_FROM_ABI void swap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y) {
718 __x.swap(__y);
719 }
720
721 template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
722 class _LIBCPP_TEMPLATE_VIS multiset {
723 public:
724 // types:
725 typedef _Key key_type;
726 typedef key_type value_type;
727 typedef __type_identity_t<_Compare> key_compare;
728 typedef key_compare value_compare;
729 typedef __type_identity_t<_Allocator> allocator_type;
730 typedef value_type& reference;
731 typedef const value_type& const_reference;
732
733 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
734 "Allocator::value_type must be same type as value_type");
735
736 private:
737 typedef __tree<value_type, value_compare, allocator_type> __base;
738 typedef allocator_traits<allocator_type> __alloc_traits;
739
740 static_assert(__check_valid_allocator<allocator_type>::value, "");
741
742 __base __tree_;
743
744 public:
745 typedef typename __base::pointer pointer;
746 typedef typename __base::const_pointer const_pointer;
747 typedef typename __base::size_type size_type;
748 typedef typename __base::difference_type difference_type;
749 typedef typename __base::const_iterator iterator;
750 typedef typename __base::const_iterator const_iterator;
751 typedef std::reverse_iterator<iterator> reverse_iterator;
752 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
753
754 template <class _Key2, class _Compare2, class _Alloc2>
755 friend class _LIBCPP_TEMPLATE_VIS set;
756 template <class _Key2, class _Compare2, class _Alloc2>
757 friend class _LIBCPP_TEMPLATE_VIS multiset;
758
759 // construct/copy/destroy:
760 _LIBCPP_HIDE_FROM_ABI multiset() : __tree_(value_compare()) {}
761
762 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp) : __tree_(__comp) {}
763
764 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp, const allocator_type& __a)
765 : __tree_(__comp, __a) {}
766 template <class _InputIterator>
767 _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
768 : __tree_(__comp) {
769 insert(__f, __l);
770 }
771
772 template <class _InputIterator>
773 _LIBCPP_HIDE_FROM_ABI
774 multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
775 : __tree_(__comp, __a) {
776 insert(__f, __l);
777 }
778
779 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s)
780 : __tree_(__s.__tree_.value_comp(),
781 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) {
782 insert(__s.begin(), __s.end());
783 }
784
785 _LIBCPP_HIDE_FROM_ABI multiset& operator=(const multiset& __s) {
786 __tree_ = __s.__tree_;
787 return *this;
788 }
789
790 _LIBCPP_HIDE_FROM_ABI explicit multiset(const allocator_type& __a) : __tree_(__a) {}
791 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s, const allocator_type& __a)
792 : __tree_(__s.__tree_.value_comp(), __a) {
793 insert(__s.begin(), __s.end());
794 }
795
796 _LIBCPP_HIDE_FROM_ABI ~multiset() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
797
798 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
799 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
800 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
801 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
802
803 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
804 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
805 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
806 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
807
808 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
809 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
810 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
811 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
812
813 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
814 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
815 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
816
817 // modifiers:
818 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
819 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
820 return __tree_.__insert_multi(__p, __v);
821 }
822
823 template <class _InputIterator>
824 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
825 for (const_iterator __e = cend(); __f != __l; ++__f)
826 __tree_.__insert_multi(__e, *__f);
827 }
828
829 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
830 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
831 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
832 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
833
834 _LIBCPP_HIDE_FROM_ABI void swap(multiset& __s) { __tree_.swap(__s.__tree_); }
835
836 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
837 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
838 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
839
840 // set operations:
841 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
842 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
843
844 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
845
846 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
847 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
848
849 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
850 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
851
852 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
853 return __tree_.__equal_range_multi(__k);
854 }
855 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
856 return __tree_.__equal_range_multi(__k);
857 }
858 };
859
860 template <class _Key, class _Compare, class _Allocator>
861 inline _LIBCPP_HIDE_FROM_ABI bool
862 operator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
863 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
864 }
865
866 template <class _Key, class _Compare, class _Allocator>
867 inline _LIBCPP_HIDE_FROM_ABI bool
868 operator<(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
869 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
870 }
871
872 template <class _Key, class _Compare, class _Allocator>
873 inline _LIBCPP_HIDE_FROM_ABI bool
874 operator!=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
875 return !(__x == __y);
876 }
877
878 template <class _Key, class _Compare, class _Allocator>
879 inline _LIBCPP_HIDE_FROM_ABI bool
880 operator>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
881 return __y < __x;
882 }
883
884 template <class _Key, class _Compare, class _Allocator>
885 inline _LIBCPP_HIDE_FROM_ABI bool
886 operator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
887 return !(__x < __y);
888 }
889
890 template <class _Key, class _Compare, class _Allocator>
891 inline _LIBCPP_HIDE_FROM_ABI bool
892 operator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
893 return !(__y < __x);
894 }
895
896 template <class _Key, class _Compare, class _Allocator>
897 inline _LIBCPP_HIDE_FROM_ABI void
898 swap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y) {
899 __x.swap(__y);
900 }
901
902 _LIBCPP_END_NAMESPACE_STD
903
904 _LIBCPP_POP_MACROS
905
906 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)
907 # include <__cxx03/cstdlib>
908 # include <__cxx03/functional>
909 # include <__cxx03/iterator>
910 # include <__cxx03/stdexcept>
911 # include <__cxx03/type_traits>
912 #endif
913
914 #endif // _LIBCPP___CXX03_SET