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