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