1 // Set implementation -*- C++ -*-
2
3 // Copyright (C) 2001-2022 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996,1997
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51 /** @file bits/stl_set.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{set}
54 */
55
56 #ifndef _STL_SET_H
57 #define _STL_SET_H 1
58
59 #include <bits/concept_check.h>
60 #if __cplusplus >= 201103L
61 #include <initializer_list>
62 #endif
63
_GLIBCXX_VISIBILITY(default)64 namespace std _GLIBCXX_VISIBILITY(default)
65 {
66 _GLIBCXX_BEGIN_NAMESPACE_VERSION
67 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
68
69 template<typename _Key, typename _Compare, typename _Alloc>
70 class multiset;
71
72 /**
73 * @brief A standard container made up of unique keys, which can be
74 * retrieved in logarithmic time.
75 *
76 * @ingroup associative_containers
77 * @headerfile set
78 * @since C++98
79 *
80 * @tparam _Key Type of key objects.
81 * @tparam _Compare Comparison function object type, defaults to less<_Key>.
82 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
83 *
84 * Meets the requirements of a <a href="tables.html#65">container</a>, a
85 * <a href="tables.html#66">reversible container</a>, and an
86 * <a href="tables.html#69">associative container</a> (using unique keys).
87 *
88 * Sets support bidirectional iterators.
89 *
90 * The private tree data is declared exactly the same way for set and
91 * multiset; the distinction is made entirely in how the tree functions are
92 * called (*_unique versus *_equal, same as the standard).
93 */
94 template<typename _Key, typename _Compare = std::less<_Key>,
95 typename _Alloc = std::allocator<_Key> >
96 class set
97 {
98 #ifdef _GLIBCXX_CONCEPT_CHECKS
99 // concept requirements
100 typedef typename _Alloc::value_type _Alloc_value_type;
101 # if __cplusplus < 201103L
102 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
103 # endif
104 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
105 _BinaryFunctionConcept)
106 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
107 #endif
108
109 #if __cplusplus >= 201103L
110 static_assert(is_same<typename remove_cv<_Key>::type, _Key>::value,
111 "std::set must have a non-const, non-volatile value_type");
112 # if __cplusplus > 201703L || defined __STRICT_ANSI__
113 static_assert(is_same<typename _Alloc::value_type, _Key>::value,
114 "std::set must have the same value_type as its allocator");
115 # endif
116 #endif
117
118 public:
119 // typedefs:
120 ///@{
121 /// Public typedefs.
122 typedef _Key key_type;
123 typedef _Key value_type;
124 typedef _Compare key_compare;
125 typedef _Compare value_compare;
126 typedef _Alloc allocator_type;
127 ///@}
128
129 private:
130 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
131 rebind<_Key>::other _Key_alloc_type;
132
133 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
134 key_compare, _Key_alloc_type> _Rep_type;
135 _Rep_type _M_t; // Red-black tree representing set.
136
137 typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;
138
139 public:
140 ///@{
141 /// Iterator-related typedefs.
142 typedef typename _Alloc_traits::pointer pointer;
143 typedef typename _Alloc_traits::const_pointer const_pointer;
144 typedef typename _Alloc_traits::reference reference;
145 typedef typename _Alloc_traits::const_reference const_reference;
146 // _GLIBCXX_RESOLVE_LIB_DEFECTS
147 // DR 103. set::iterator is required to be modifiable,
148 // but this allows modification of keys.
149 typedef typename _Rep_type::const_iterator iterator;
150 typedef typename _Rep_type::const_iterator const_iterator;
151 typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
152 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
153 typedef typename _Rep_type::size_type size_type;
154 typedef typename _Rep_type::difference_type difference_type;
155 ///@}
156
157 #if __cplusplus > 201402L
158 using node_type = typename _Rep_type::node_type;
159 using insert_return_type = typename _Rep_type::insert_return_type;
160 #endif
161
162 // allocation/deallocation
163 /**
164 * @brief Default constructor creates no elements.
165 */
166 #if __cplusplus < 201103L
167 set() : _M_t() { }
168 #else
169 set() = default;
170 #endif
171
172 /**
173 * @brief Creates a %set with no elements.
174 * @param __comp Comparator to use.
175 * @param __a An allocator object.
176 */
177 explicit
178 set(const _Compare& __comp,
179 const allocator_type& __a = allocator_type())
180 : _M_t(__comp, _Key_alloc_type(__a)) { }
181
182 /**
183 * @brief Builds a %set from a range.
184 * @param __first An input iterator.
185 * @param __last An input iterator.
186 *
187 * Create a %set consisting of copies of the elements from
188 * [__first,__last). This is linear in N if the range is
189 * already sorted, and NlogN otherwise (where N is
190 * distance(__first,__last)).
191 */
192 template<typename _InputIterator>
193 set(_InputIterator __first, _InputIterator __last)
194 : _M_t()
195 { _M_t._M_insert_range_unique(__first, __last); }
196
197 /**
198 * @brief Builds a %set from a range.
199 * @param __first An input iterator.
200 * @param __last An input iterator.
201 * @param __comp A comparison functor.
202 * @param __a An allocator object.
203 *
204 * Create a %set consisting of copies of the elements from
205 * [__first,__last). This is linear in N if the range is
206 * already sorted, and NlogN otherwise (where N is
207 * distance(__first,__last)).
208 */
209 template<typename _InputIterator>
210 set(_InputIterator __first, _InputIterator __last,
211 const _Compare& __comp,
212 const allocator_type& __a = allocator_type())
213 : _M_t(__comp, _Key_alloc_type(__a))
214 { _M_t._M_insert_range_unique(__first, __last); }
215
216 /**
217 * @brief %Set copy constructor.
218 *
219 * Whether the allocator is copied depends on the allocator traits.
220 */
221 #if __cplusplus < 201103L
222 set(const set& __x)
223 : _M_t(__x._M_t) { }
224 #else
225 set(const set&) = default;
226
227 /**
228 * @brief %Set move constructor
229 *
230 * The newly-created %set contains the exact contents of the moved
231 * instance. The moved instance is a valid, but unspecified, %set.
232 */
233 set(set&&) = default;
234
235 /**
236 * @brief Builds a %set from an initializer_list.
237 * @param __l An initializer_list.
238 * @param __comp A comparison functor.
239 * @param __a An allocator object.
240 *
241 * Create a %set consisting of copies of the elements in the list.
242 * This is linear in N if the list is already sorted, and NlogN
243 * otherwise (where N is @a __l.size()).
244 */
245 set(initializer_list<value_type> __l,
246 const _Compare& __comp = _Compare(),
247 const allocator_type& __a = allocator_type())
248 : _M_t(__comp, _Key_alloc_type(__a))
249 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); }
250
251 /// Allocator-extended default constructor.
252 explicit
253 set(const allocator_type& __a)
254 : _M_t(_Key_alloc_type(__a)) { }
255
256 /// Allocator-extended copy constructor.
257 set(const set& __x, const __type_identity_t<allocator_type>& __a)
258 : _M_t(__x._M_t, _Key_alloc_type(__a)) { }
259
260 /// Allocator-extended move constructor.
261 set(set&& __x, const __type_identity_t<allocator_type>& __a)
262 noexcept(is_nothrow_copy_constructible<_Compare>::value
263 && _Alloc_traits::_S_always_equal())
264 : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
265
266 /// Allocator-extended initialier-list constructor.
267 set(initializer_list<value_type> __l, const allocator_type& __a)
268 : _M_t(_Key_alloc_type(__a))
269 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); }
270
271 /// Allocator-extended range constructor.
272 template<typename _InputIterator>
273 set(_InputIterator __first, _InputIterator __last,
274 const allocator_type& __a)
275 : _M_t(_Key_alloc_type(__a))
276 { _M_t._M_insert_range_unique(__first, __last); }
277
278 /**
279 * The dtor only erases the elements, and note that if the elements
280 * themselves are pointers, the pointed-to memory is not touched in any
281 * way. Managing the pointer is the user's responsibility.
282 */
283 ~set() = default;
284 #endif
285
286 /**
287 * @brief %Set assignment operator.
288 *
289 * Whether the allocator is copied depends on the allocator traits.
290 */
291 #if __cplusplus < 201103L
292 set&
293 operator=(const set& __x)
294 {
295 _M_t = __x._M_t;
296 return *this;
297 }
298 #else
299 set&
300 operator=(const set&) = default;
301
302 /// Move assignment operator.
303 set&
304 operator=(set&&) = default;
305
306 /**
307 * @brief %Set list assignment operator.
308 * @param __l An initializer_list.
309 *
310 * This function fills a %set with copies of the elements in the
311 * initializer list @a __l.
312 *
313 * Note that the assignment completely changes the %set and
314 * that the resulting %set's size is the same as the number
315 * of elements assigned.
316 */
317 set&
318 operator=(initializer_list<value_type> __l)
319 {
320 _M_t._M_assign_unique(__l.begin(), __l.end());
321 return *this;
322 }
323 #endif
324
325 // accessors:
326
327 /// Returns the comparison object with which the %set was constructed.
328 key_compare
329 key_comp() const
330 { return _M_t.key_comp(); }
331 /// Returns the comparison object with which the %set was constructed.
332 value_compare
333 value_comp() const
334 { return _M_t.key_comp(); }
335 /// Returns the allocator object with which the %set was constructed.
336 allocator_type
337 get_allocator() const _GLIBCXX_NOEXCEPT
338 { return allocator_type(_M_t.get_allocator()); }
339
340 /**
341 * Returns a read-only (constant) iterator that points to the first
342 * element in the %set. Iteration is done in ascending order according
343 * to the keys.
344 */
345 iterator
346 begin() const _GLIBCXX_NOEXCEPT
347 { return _M_t.begin(); }
348
349 /**
350 * Returns a read-only (constant) iterator that points one past the last
351 * element in the %set. Iteration is done in ascending order according
352 * to the keys.
353 */
354 iterator
355 end() const _GLIBCXX_NOEXCEPT
356 { return _M_t.end(); }
357
358 /**
359 * Returns a read-only (constant) iterator that points to the last
360 * element in the %set. Iteration is done in descending order according
361 * to the keys.
362 */
363 reverse_iterator
364 rbegin() const _GLIBCXX_NOEXCEPT
365 { return _M_t.rbegin(); }
366
367 /**
368 * Returns a read-only (constant) reverse iterator that points to the
369 * last pair in the %set. Iteration is done in descending order
370 * according to the keys.
371 */
372 reverse_iterator
373 rend() const _GLIBCXX_NOEXCEPT
374 { return _M_t.rend(); }
375
376 #if __cplusplus >= 201103L
377 /**
378 * Returns a read-only (constant) iterator that points to the first
379 * element in the %set. Iteration is done in ascending order according
380 * to the keys.
381 */
382 iterator
383 cbegin() const noexcept
384 { return _M_t.begin(); }
385
386 /**
387 * Returns a read-only (constant) iterator that points one past the last
388 * element in the %set. Iteration is done in ascending order according
389 * to the keys.
390 */
391 iterator
392 cend() const noexcept
393 { return _M_t.end(); }
394
395 /**
396 * Returns a read-only (constant) iterator that points to the last
397 * element in the %set. Iteration is done in descending order according
398 * to the keys.
399 */
400 reverse_iterator
401 crbegin() const noexcept
402 { return _M_t.rbegin(); }
403
404 /**
405 * Returns a read-only (constant) reverse iterator that points to the
406 * last pair in the %set. Iteration is done in descending order
407 * according to the keys.
408 */
409 reverse_iterator
410 crend() const noexcept
411 { return _M_t.rend(); }
412 #endif
413
414 /// Returns true if the %set is empty.
415 _GLIBCXX_NODISCARD bool
416 empty() const _GLIBCXX_NOEXCEPT
417 { return _M_t.empty(); }
418
419 /// Returns the size of the %set.
420 size_type
421 size() const _GLIBCXX_NOEXCEPT
422 { return _M_t.size(); }
423
424 /// Returns the maximum size of the %set.
425 size_type
426 max_size() const _GLIBCXX_NOEXCEPT
427 { return _M_t.max_size(); }
428
429 /**
430 * @brief Swaps data with another %set.
431 * @param __x A %set of the same element and allocator types.
432 *
433 * This exchanges the elements between two sets in constant
434 * time. (It is only swapping a pointer, an integer, and an
435 * instance of the @c Compare type (which itself is often
436 * stateless and empty), so it should be quite fast.) Note
437 * that the global std::swap() function is specialized such
438 * that std::swap(s1,s2) will feed to this function.
439 *
440 * Whether the allocators are swapped depends on the allocator traits.
441 */
442 void
443 swap(set& __x)
444 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
445 { _M_t.swap(__x._M_t); }
446
447 // insert/erase
448 #if __cplusplus >= 201103L
449 /**
450 * @brief Attempts to build and insert an element into the %set.
451 * @param __args Arguments used to generate an element.
452 * @return A pair, of which the first element is an iterator that points
453 * to the possibly inserted element, and the second is a bool
454 * that is true if the element was actually inserted.
455 *
456 * This function attempts to build and insert an element into the %set.
457 * A %set relies on unique keys and thus an element is only inserted if
458 * it is not already present in the %set.
459 *
460 * Insertion requires logarithmic time.
461 */
462 template<typename... _Args>
463 std::pair<iterator, bool>
464 emplace(_Args&&... __args)
465 { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
466
467 /**
468 * @brief Attempts to insert an element into the %set.
469 * @param __pos An iterator that serves as a hint as to where the
470 * element should be inserted.
471 * @param __args Arguments used to generate the element to be
472 * inserted.
473 * @return An iterator that points to the element with key equivalent to
474 * the one generated from @a __args (may or may not be the
475 * element itself).
476 *
477 * This function is not concerned about whether the insertion took place,
478 * and thus does not return a boolean like the single-argument emplace()
479 * does. Note that the first parameter is only a hint and can
480 * potentially improve the performance of the insertion process. A bad
481 * hint would cause no gains in efficiency.
482 *
483 * For more on @a hinting, see:
484 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
485 *
486 * Insertion requires logarithmic time (if the hint is not taken).
487 */
488 template<typename... _Args>
489 iterator
490 emplace_hint(const_iterator __pos, _Args&&... __args)
491 {
492 return _M_t._M_emplace_hint_unique(__pos,
493 std::forward<_Args>(__args)...);
494 }
495 #endif
496
497 /**
498 * @brief Attempts to insert an element into the %set.
499 * @param __x Element to be inserted.
500 * @return A pair, of which the first element is an iterator that points
501 * to the possibly inserted element, and the second is a bool
502 * that is true if the element was actually inserted.
503 *
504 * This function attempts to insert an element into the %set. A %set
505 * relies on unique keys and thus an element is only inserted if it is
506 * not already present in the %set.
507 *
508 * Insertion requires logarithmic time.
509 */
510 std::pair<iterator, bool>
511 insert(const value_type& __x)
512 {
513 std::pair<typename _Rep_type::iterator, bool> __p =
514 _M_t._M_insert_unique(__x);
515 return std::pair<iterator, bool>(__p.first, __p.second);
516 }
517
518 #if __cplusplus >= 201103L
519 std::pair<iterator, bool>
520 insert(value_type&& __x)
521 {
522 std::pair<typename _Rep_type::iterator, bool> __p =
523 _M_t._M_insert_unique(std::move(__x));
524 return std::pair<iterator, bool>(__p.first, __p.second);
525 }
526 #endif
527
528 /**
529 * @brief Attempts to insert an element into the %set.
530 * @param __position An iterator that serves as a hint as to where the
531 * element should be inserted.
532 * @param __x Element to be inserted.
533 * @return An iterator that points to the element with key of
534 * @a __x (may or may not be the element passed in).
535 *
536 * This function is not concerned about whether the insertion took place,
537 * and thus does not return a boolean like the single-argument insert()
538 * does. Note that the first parameter is only a hint and can
539 * potentially improve the performance of the insertion process. A bad
540 * hint would cause no gains in efficiency.
541 *
542 * For more on @a hinting, see:
543 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
544 *
545 * Insertion requires logarithmic time (if the hint is not taken).
546 */
547 iterator
548 insert(const_iterator __position, const value_type& __x)
549 { return _M_t._M_insert_unique_(__position, __x); }
550
551 #if __cplusplus >= 201103L
552 iterator
553 insert(const_iterator __position, value_type&& __x)
554 { return _M_t._M_insert_unique_(__position, std::move(__x)); }
555 #endif
556
557 /**
558 * @brief A template function that attempts to insert a range
559 * of elements.
560 * @param __first Iterator pointing to the start of the range to be
561 * inserted.
562 * @param __last Iterator pointing to the end of the range.
563 *
564 * Complexity similar to that of the range constructor.
565 */
566 template<typename _InputIterator>
567 void
568 insert(_InputIterator __first, _InputIterator __last)
569 { _M_t._M_insert_range_unique(__first, __last); }
570
571 #if __cplusplus >= 201103L
572 /**
573 * @brief Attempts to insert a list of elements into the %set.
574 * @param __l A std::initializer_list<value_type> of elements
575 * to be inserted.
576 *
577 * Complexity similar to that of the range constructor.
578 */
579 void
580 insert(initializer_list<value_type> __l)
581 { this->insert(__l.begin(), __l.end()); }
582 #endif
583
584 #if __cplusplus > 201402L
585 /// Extract a node.
586 node_type
587 extract(const_iterator __pos)
588 {
589 __glibcxx_assert(__pos != end());
590 return _M_t.extract(__pos);
591 }
592
593 /// Extract a node.
594 node_type
595 extract(const key_type& __x)
596 { return _M_t.extract(__x); }
597
598 /// Re-insert an extracted node.
599 insert_return_type
600 insert(node_type&& __nh)
601 { return _M_t._M_reinsert_node_unique(std::move(__nh)); }
602
603 /// Re-insert an extracted node.
604 iterator
605 insert(const_iterator __hint, node_type&& __nh)
606 { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); }
607
608 template<typename, typename>
609 friend struct std::_Rb_tree_merge_helper;
610
611 template<typename _Compare1>
612 void
613 merge(set<_Key, _Compare1, _Alloc>& __source)
614 {
615 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>;
616 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
617 }
618
619 template<typename _Compare1>
620 void
621 merge(set<_Key, _Compare1, _Alloc>&& __source)
622 { merge(__source); }
623
624 template<typename _Compare1>
625 void
626 merge(multiset<_Key, _Compare1, _Alloc>& __source)
627 {
628 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>;
629 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
630 }
631
632 template<typename _Compare1>
633 void
634 merge(multiset<_Key, _Compare1, _Alloc>&& __source)
635 { merge(__source); }
636 #endif // C++17
637
638 #if __cplusplus >= 201103L
639 // _GLIBCXX_RESOLVE_LIB_DEFECTS
640 // DR 130. Associative erase should return an iterator.
641 /**
642 * @brief Erases an element from a %set.
643 * @param __position An iterator pointing to the element to be erased.
644 * @return An iterator pointing to the element immediately following
645 * @a __position prior to the element being erased. If no such
646 * element exists, end() is returned.
647 *
648 * This function erases an element, pointed to by the given iterator,
649 * from a %set. Note that this function only erases the element, and
650 * that if the element is itself a pointer, the pointed-to memory is not
651 * touched in any way. Managing the pointer is the user's
652 * responsibility.
653 */
654 _GLIBCXX_ABI_TAG_CXX11
655 iterator
656 erase(const_iterator __position)
657 { return _M_t.erase(__position); }
658 #else
659 /**
660 * @brief Erases an element from a %set.
661 * @param position An iterator pointing to the element to be erased.
662 *
663 * This function erases an element, pointed to by the given iterator,
664 * from a %set. Note that this function only erases the element, and
665 * that if the element is itself a pointer, the pointed-to memory is not
666 * touched in any way. Managing the pointer is the user's
667 * responsibility.
668 */
669 void
670 erase(iterator __position)
671 { _M_t.erase(__position); }
672 #endif
673
674 /**
675 * @brief Erases elements according to the provided key.
676 * @param __x Key of element to be erased.
677 * @return The number of elements erased.
678 *
679 * This function erases all the elements located by the given key from
680 * a %set.
681 * Note that this function only erases the element, and that if
682 * the element is itself a pointer, the pointed-to memory is not touched
683 * in any way. Managing the pointer is the user's responsibility.
684 */
685 size_type
686 erase(const key_type& __x)
687 { return _M_t.erase(__x); }
688
689 #if __cplusplus >= 201103L
690 // _GLIBCXX_RESOLVE_LIB_DEFECTS
691 // DR 130. Associative erase should return an iterator.
692 /**
693 * @brief Erases a [__first,__last) range of elements from a %set.
694 * @param __first Iterator pointing to the start of the range to be
695 * erased.
696
697 * @param __last Iterator pointing to the end of the range to
698 * be erased.
699 * @return The iterator @a __last.
700 *
701 * This function erases a sequence of elements from a %set.
702 * Note that this function only erases the element, and that if
703 * the element is itself a pointer, the pointed-to memory is not touched
704 * in any way. Managing the pointer is the user's responsibility.
705 */
706 _GLIBCXX_ABI_TAG_CXX11
707 iterator
708 erase(const_iterator __first, const_iterator __last)
709 { return _M_t.erase(__first, __last); }
710 #else
711 /**
712 * @brief Erases a [first,last) range of elements from a %set.
713 * @param __first Iterator pointing to the start of the range to be
714 * erased.
715 * @param __last Iterator pointing to the end of the range to
716 * be erased.
717 *
718 * This function erases a sequence of elements from a %set.
719 * Note that this function only erases the element, and that if
720 * the element is itself a pointer, the pointed-to memory is not touched
721 * in any way. Managing the pointer is the user's responsibility.
722 */
723 void
724 erase(iterator __first, iterator __last)
725 { _M_t.erase(__first, __last); }
726 #endif
727
728 /**
729 * Erases all elements in a %set. Note that this function only erases
730 * the elements, and that if the elements themselves are pointers, the
731 * pointed-to memory is not touched in any way. Managing the pointer is
732 * the user's responsibility.
733 */
734 void
735 clear() _GLIBCXX_NOEXCEPT
736 { _M_t.clear(); }
737
738 // set operations:
739
740 ///@{
741 /**
742 * @brief Finds the number of elements.
743 * @param __x Element to located.
744 * @return Number of elements with specified key.
745 *
746 * This function only makes sense for multisets; for set the result will
747 * either be 0 (not present) or 1 (present).
748 */
749 size_type
750 count(const key_type& __x) const
751 { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
752
753 #if __cplusplus > 201103L
754 template<typename _Kt>
755 auto
756 count(const _Kt& __x) const
757 -> decltype(_M_t._M_count_tr(__x))
758 { return _M_t._M_count_tr(__x); }
759 #endif
760 ///@}
761
762 #if __cplusplus > 201703L
763 ///@{
764 /**
765 * @brief Finds whether an element with the given key exists.
766 * @param __x Key of elements to be located.
767 * @return True if there is an element with the specified key.
768 */
769 bool
770 contains(const key_type& __x) const
771 { return _M_t.find(__x) != _M_t.end(); }
772
773 template<typename _Kt>
774 auto
775 contains(const _Kt& __x) const
776 -> decltype(_M_t._M_find_tr(__x), void(), true)
777 { return _M_t._M_find_tr(__x) != _M_t.end(); }
778 ///@}
779 #endif
780
781 // _GLIBCXX_RESOLVE_LIB_DEFECTS
782 // 214. set::find() missing const overload
783 ///@{
784 /**
785 * @brief Tries to locate an element in a %set.
786 * @param __x Element to be located.
787 * @return Iterator pointing to sought-after element, or end() if not
788 * found.
789 *
790 * This function takes a key and tries to locate the element with which
791 * the key matches. If successful the function returns an iterator
792 * pointing to the sought after element. If unsuccessful it returns the
793 * past-the-end ( @c end() ) iterator.
794 */
795 iterator
796 find(const key_type& __x)
797 { return _M_t.find(__x); }
798
799 const_iterator
800 find(const key_type& __x) const
801 { return _M_t.find(__x); }
802
803 #if __cplusplus > 201103L
804 template<typename _Kt>
805 auto
806 find(const _Kt& __x)
807 -> decltype(iterator{_M_t._M_find_tr(__x)})
808 { return iterator{_M_t._M_find_tr(__x)}; }
809
810 template<typename _Kt>
811 auto
812 find(const _Kt& __x) const
813 -> decltype(const_iterator{_M_t._M_find_tr(__x)})
814 { return const_iterator{_M_t._M_find_tr(__x)}; }
815 #endif
816 ///@}
817
818 ///@{
819 /**
820 * @brief Finds the beginning of a subsequence matching given key.
821 * @param __x Key to be located.
822 * @return Iterator pointing to first element equal to or greater
823 * than key, or end().
824 *
825 * This function returns the first element of a subsequence of elements
826 * that matches the given key. If unsuccessful it returns an iterator
827 * pointing to the first element that has a greater value than given key
828 * or end() if no such element exists.
829 */
830 iterator
831 lower_bound(const key_type& __x)
832 { return _M_t.lower_bound(__x); }
833
834 const_iterator
835 lower_bound(const key_type& __x) const
836 { return _M_t.lower_bound(__x); }
837
838 #if __cplusplus > 201103L
839 template<typename _Kt>
840 auto
841 lower_bound(const _Kt& __x)
842 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
843 { return iterator(_M_t._M_lower_bound_tr(__x)); }
844
845 template<typename _Kt>
846 auto
847 lower_bound(const _Kt& __x) const
848 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
849 { return const_iterator(_M_t._M_lower_bound_tr(__x)); }
850 #endif
851 ///@}
852
853 ///@{
854 /**
855 * @brief Finds the end of a subsequence matching given key.
856 * @param __x Key to be located.
857 * @return Iterator pointing to the first element
858 * greater than key, or end().
859 */
860 iterator
861 upper_bound(const key_type& __x)
862 { return _M_t.upper_bound(__x); }
863
864 const_iterator
865 upper_bound(const key_type& __x) const
866 { return _M_t.upper_bound(__x); }
867
868 #if __cplusplus > 201103L
869 template<typename _Kt>
870 auto
871 upper_bound(const _Kt& __x)
872 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
873 { return iterator(_M_t._M_upper_bound_tr(__x)); }
874
875 template<typename _Kt>
876 auto
877 upper_bound(const _Kt& __x) const
878 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
879 { return const_iterator(_M_t._M_upper_bound_tr(__x)); }
880 #endif
881 ///@}
882
883 ///@{
884 /**
885 * @brief Finds a subsequence matching given key.
886 * @param __x Key to be located.
887 * @return Pair of iterators that possibly points to the subsequence
888 * matching given key.
889 *
890 * This function is equivalent to
891 * @code
892 * std::make_pair(c.lower_bound(val),
893 * c.upper_bound(val))
894 * @endcode
895 * (but is faster than making the calls separately).
896 *
897 * This function probably only makes sense for multisets.
898 */
899 std::pair<iterator, iterator>
900 equal_range(const key_type& __x)
901 { return _M_t.equal_range(__x); }
902
903 std::pair<const_iterator, const_iterator>
904 equal_range(const key_type& __x) const
905 { return _M_t.equal_range(__x); }
906
907 #if __cplusplus > 201103L
908 template<typename _Kt>
909 auto
910 equal_range(const _Kt& __x)
911 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
912 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
913
914 template<typename _Kt>
915 auto
916 equal_range(const _Kt& __x) const
917 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
918 { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
919 #endif
920 ///@}
921
922 template<typename _K1, typename _C1, typename _A1>
923 friend bool
924 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
925
926 #if __cpp_lib_three_way_comparison
927 template<typename _K1, typename _C1, typename _A1>
928 friend __detail::__synth3way_t<_K1>
929 operator<=>(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
930 #else
931 template<typename _K1, typename _C1, typename _A1>
932 friend bool
933 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
934 #endif
935 };
936
937 #if __cpp_deduction_guides >= 201606
938
939 template<typename _InputIterator,
940 typename _Compare =
941 less<typename iterator_traits<_InputIterator>::value_type>,
942 typename _Allocator =
943 allocator<typename iterator_traits<_InputIterator>::value_type>,
944 typename = _RequireInputIter<_InputIterator>,
945 typename = _RequireNotAllocator<_Compare>,
946 typename = _RequireAllocator<_Allocator>>
947 set(_InputIterator, _InputIterator,
948 _Compare = _Compare(), _Allocator = _Allocator())
949 -> set<typename iterator_traits<_InputIterator>::value_type,
950 _Compare, _Allocator>;
951
952 template<typename _Key, typename _Compare = less<_Key>,
953 typename _Allocator = allocator<_Key>,
954 typename = _RequireNotAllocator<_Compare>,
955 typename = _RequireAllocator<_Allocator>>
956 set(initializer_list<_Key>,
957 _Compare = _Compare(), _Allocator = _Allocator())
958 -> set<_Key, _Compare, _Allocator>;
959
960 template<typename _InputIterator, typename _Allocator,
961 typename = _RequireInputIter<_InputIterator>,
962 typename = _RequireAllocator<_Allocator>>
963 set(_InputIterator, _InputIterator, _Allocator)
964 -> set<typename iterator_traits<_InputIterator>::value_type,
965 less<typename iterator_traits<_InputIterator>::value_type>,
966 _Allocator>;
967
968 template<typename _Key, typename _Allocator,
969 typename = _RequireAllocator<_Allocator>>
970 set(initializer_list<_Key>, _Allocator)
971 -> set<_Key, less<_Key>, _Allocator>;
972
973 #endif // deduction guides
974
975 /**
976 * @brief Set equality comparison.
977 * @param __x A %set.
978 * @param __y A %set of the same type as @a x.
979 * @return True iff the size and elements of the sets are equal.
980 *
981 * This is an equivalence relation. It is linear in the size of the sets.
982 * Sets are considered equivalent if their sizes are equal, and if
983 * corresponding elements compare equal.
984 */
985 template<typename _Key, typename _Compare, typename _Alloc>
986 inline bool
987 operator==(const set<_Key, _Compare, _Alloc>& __x,
988 const set<_Key, _Compare, _Alloc>& __y)
989 { return __x._M_t == __y._M_t; }
990
991 #if __cpp_lib_three_way_comparison
992 /**
993 * @brief Set ordering relation.
994 * @param __x A `set`.
995 * @param __y A `set` of the same type as `x`.
996 * @return A value indicating whether `__x` is less than, equal to,
997 * greater than, or incomparable with `__y`.
998 *
999 * This is a total ordering relation. It is linear in the size of the
1000 * maps. The elements must be comparable with @c <.
1001 *
1002 * See `std::lexicographical_compare_three_way()` for how the determination
1003 * is made. This operator is used to synthesize relational operators like
1004 * `<` and `>=` etc.
1005 */
1006 template<typename _Key, typename _Compare, typename _Alloc>
1007 inline __detail::__synth3way_t<_Key>
1008 operator<=>(const set<_Key, _Compare, _Alloc>& __x,
1009 const set<_Key, _Compare, _Alloc>& __y)
1010 { return __x._M_t <=> __y._M_t; }
1011 #else
1012 /**
1013 * @brief Set ordering relation.
1014 * @param __x A %set.
1015 * @param __y A %set of the same type as @a x.
1016 * @return True iff @a __x is lexicographically less than @a __y.
1017 *
1018 * This is a total ordering relation. It is linear in the size of the
1019 * sets. The elements must be comparable with @c <.
1020 *
1021 * See std::lexicographical_compare() for how the determination is made.
1022 */
1023 template<typename _Key, typename _Compare, typename _Alloc>
1024 inline bool
1025 operator<(const set<_Key, _Compare, _Alloc>& __x,
1026 const set<_Key, _Compare, _Alloc>& __y)
1027 { return __x._M_t < __y._M_t; }
1028
1029 /// Returns !(x == y).
1030 template<typename _Key, typename _Compare, typename _Alloc>
1031 inline bool
1032 operator!=(const set<_Key, _Compare, _Alloc>& __x,
1033 const set<_Key, _Compare, _Alloc>& __y)
1034 { return !(__x == __y); }
1035
1036 /// Returns y < x.
1037 template<typename _Key, typename _Compare, typename _Alloc>
1038 inline bool
1039 operator>(const set<_Key, _Compare, _Alloc>& __x,
1040 const set<_Key, _Compare, _Alloc>& __y)
1041 { return __y < __x; }
1042
1043 /// Returns !(y < x)
1044 template<typename _Key, typename _Compare, typename _Alloc>
1045 inline bool
1046 operator<=(const set<_Key, _Compare, _Alloc>& __x,
1047 const set<_Key, _Compare, _Alloc>& __y)
1048 { return !(__y < __x); }
1049
1050 /// Returns !(x < y)
1051 template<typename _Key, typename _Compare, typename _Alloc>
1052 inline bool
1053 operator>=(const set<_Key, _Compare, _Alloc>& __x,
1054 const set<_Key, _Compare, _Alloc>& __y)
1055 { return !(__x < __y); }
1056 #endif // three-way comparison
1057
1058 /// See std::set::swap().
1059 template<typename _Key, typename _Compare, typename _Alloc>
1060 inline void
1061 swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y)
1062 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1063 { __x.swap(__y); }
1064
1065 _GLIBCXX_END_NAMESPACE_CONTAINER
1066
1067 #if __cplusplus > 201402L
1068 // Allow std::set access to internals of compatible sets.
1069 template<typename _Val, typename _Cmp1, typename _Alloc, typename _Cmp2>
1070 struct
1071 _Rb_tree_merge_helper<_GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>, _Cmp2>
1072 {
1073 private:
1074 friend class _GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>;
1075
1076 static auto&
1077 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set)
1078 { return __set._M_t; }
1079
1080 static auto&
1081 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set)
1082 { return __set._M_t; }
1083 };
1084 #endif // C++17
1085
1086 _GLIBCXX_END_NAMESPACE_VERSION
1087 } //namespace std
1088 #endif /* _STL_SET_H */
1089