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