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