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