libstdc++
stl_set.h
Go to the documentation of this file.
1 // Set implementation -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation. Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose. It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996,1997
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation. Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose. It is provided "as is" without express or implied warranty.
50  */
51 
52 /** @file bits/stl_set.h
53  * This is an internal header file, included by other library headers.
54  * Do not attempt to use it directly. @headername{set}
55  */
56 
57 #ifndef _STL_SET_H
58 #define _STL_SET_H 1
59 
60 #include <bits/concept_check.h>
61 #ifdef __GXX_EXPERIMENTAL_CXX0X__
62 #include <initializer_list>
63 #endif
64 
65 namespace std _GLIBCXX_VISIBILITY(default)
66 {
67 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
68 
69  /**
70  * @brief A standard container made up of unique keys, which can be
71  * retrieved in logarithmic time.
72  *
73  * @ingroup associative_containers
74  *
75  * Meets the requirements of a <a href="tables.html#65">container</a>, a
76  * <a href="tables.html#66">reversible container</a>, and an
77  * <a href="tables.html#69">associative container</a> (using unique keys).
78  *
79  * Sets support bidirectional iterators.
80  *
81  * @tparam _Key Type of key objects.
82  * @tparam _Compare Comparison function object type, defaults to less<Key>.
83  * @tparam _Alloc Allocator type, defaults to allocator<Key>.
84  *
85  * The private tree data is declared exactly the same way for set and
86  * multiset; the distinction is made entirely in how the tree functions are
87  * called (*_unique versus *_equal, same as the standard).
88  */
89  template<typename _Key, typename _Compare = std::less<_Key>,
90  typename _Alloc = std::allocator<_Key> >
91  class set
92  {
93  // concept requirements
94  typedef typename _Alloc::value_type _Alloc_value_type;
95  __glibcxx_class_requires(_Key, _SGIAssignableConcept)
96  __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
97  _BinaryFunctionConcept)
98  __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
99 
100  public:
101  // typedefs:
102  //@{
103  /// Public typedefs.
104  typedef _Key key_type;
105  typedef _Key value_type;
106  typedef _Compare key_compare;
107  typedef _Compare value_compare;
108  typedef _Alloc allocator_type;
109  //@}
110 
111  private:
112  typedef typename _Alloc::template 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 
118  public:
119  //@{
120  /// Iterator-related typedefs.
121  typedef typename _Key_alloc_type::pointer pointer;
122  typedef typename _Key_alloc_type::const_pointer const_pointer;
123  typedef typename _Key_alloc_type::reference reference;
124  typedef typename _Key_alloc_type::const_reference const_reference;
125  // _GLIBCXX_RESOLVE_LIB_DEFECTS
126  // DR 103. set::iterator is required to be modifiable,
127  // but this allows modification of keys.
128  typedef typename _Rep_type::const_iterator iterator;
129  typedef typename _Rep_type::const_iterator const_iterator;
132  typedef typename _Rep_type::size_type size_type;
133  typedef typename _Rep_type::difference_type difference_type;
134  //@}
135 
136  // allocation/deallocation
137  /**
138  * @brief Default constructor creates no elements.
139  */
140  set()
141  : _M_t() { }
142 
143  /**
144  * @brief Creates a %set with no elements.
145  * @param __comp Comparator to use.
146  * @param __a An allocator object.
147  */
148  explicit
149  set(const _Compare& __comp,
150  const allocator_type& __a = allocator_type())
151  : _M_t(__comp, _Key_alloc_type(__a)) { }
152 
153  /**
154  * @brief Builds a %set from a range.
155  * @param __first An input iterator.
156  * @param __last An input iterator.
157  *
158  * Create a %set consisting of copies of the elements from
159  * [__first,__last). This is linear in N if the range is
160  * already sorted, and NlogN otherwise (where N is
161  * distance(__first,__last)).
162  */
163  template<typename _InputIterator>
164  set(_InputIterator __first, _InputIterator __last)
165  : _M_t()
166  { _M_t._M_insert_unique(__first, __last); }
167 
168  /**
169  * @brief Builds a %set from a range.
170  * @param __first An input iterator.
171  * @param __last An input iterator.
172  * @param __comp A comparison functor.
173  * @param __a An allocator object.
174  *
175  * Create a %set consisting of copies of the elements from
176  * [__first,__last). This is linear in N if the range is
177  * already sorted, and NlogN otherwise (where N is
178  * distance(__first,__last)).
179  */
180  template<typename _InputIterator>
181  set(_InputIterator __first, _InputIterator __last,
182  const _Compare& __comp,
183  const allocator_type& __a = allocator_type())
184  : _M_t(__comp, _Key_alloc_type(__a))
185  { _M_t._M_insert_unique(__first, __last); }
186 
187  /**
188  * @brief %Set copy constructor.
189  * @param __x A %set of identical element and allocator types.
190  *
191  * The newly-created %set uses a copy of the allocation object used
192  * by @a __x.
193  */
194  set(const set& __x)
195  : _M_t(__x._M_t) { }
196 
197 #ifdef __GXX_EXPERIMENTAL_CXX0X__
198  /**
199  * @brief %Set move constructor
200  * @param __x A %set of identical element and allocator types.
201  *
202  * The newly-created %set contains the exact contents of @a x.
203  * The contents of @a x are a valid, but unspecified %set.
204  */
205  set(set&& __x)
207  : _M_t(std::move(__x._M_t)) { }
208 
209  /**
210  * @brief Builds a %set from an initializer_list.
211  * @param __l An initializer_list.
212  * @param __comp A comparison functor.
213  * @param __a An allocator object.
214  *
215  * Create a %set consisting of copies of the elements in the list.
216  * This is linear in N if the list is already sorted, and NlogN
217  * otherwise (where N is @a __l.size()).
218  */
220  const _Compare& __comp = _Compare(),
221  const allocator_type& __a = allocator_type())
222  : _M_t(__comp, _Key_alloc_type(__a))
223  { _M_t._M_insert_unique(__l.begin(), __l.end()); }
224 #endif
225 
226  /**
227  * @brief %Set assignment operator.
228  * @param __x A %set of identical element and allocator types.
229  *
230  * All the elements of @a __x are copied, but unlike the copy
231  * constructor, the allocator object is not copied.
232  */
233  set&
234  operator=(const set& __x)
235  {
236  _M_t = __x._M_t;
237  return *this;
238  }
239 
240 #ifdef __GXX_EXPERIMENTAL_CXX0X__
241  /**
242  * @brief %Set move assignment operator.
243  * @param __x A %set of identical element and allocator types.
244  *
245  * The contents of @a __x are moved into this %set (without copying).
246  * @a __x is a valid, but unspecified %set.
247  */
248  set&
249  operator=(set&& __x)
250  {
251  // NB: DR 1204.
252  // NB: DR 675.
253  this->clear();
254  this->swap(__x);
255  return *this;
256  }
257 
258  /**
259  * @brief %Set list assignment operator.
260  * @param __l An initializer_list.
261  *
262  * This function fills a %set with copies of the elements in the
263  * initializer list @a __l.
264  *
265  * Note that the assignment completely changes the %set and
266  * that the resulting %set's size is the same as the number
267  * of elements assigned. Old data may be lost.
268  */
269  set&
271  {
272  this->clear();
273  this->insert(__l.begin(), __l.end());
274  return *this;
275  }
276 #endif
277 
278  // accessors:
279 
280  /// Returns the comparison object with which the %set was constructed.
282  key_comp() const
283  { return _M_t.key_comp(); }
284  /// Returns the comparison object with which the %set was constructed.
286  value_comp() const
287  { return _M_t.key_comp(); }
288  /// Returns the allocator object with which the %set was constructed.
290  get_allocator() const _GLIBCXX_NOEXCEPT
291  { return allocator_type(_M_t.get_allocator()); }
292 
293  /**
294  * Returns a read-only (constant) iterator that points to the first
295  * element in the %set. Iteration is done in ascending order according
296  * to the keys.
297  */
298  iterator
299  begin() const _GLIBCXX_NOEXCEPT
300  { return _M_t.begin(); }
301 
302  /**
303  * Returns a read-only (constant) iterator that points one past the last
304  * element in the %set. Iteration is done in ascending order according
305  * to the keys.
306  */
307  iterator
308  end() const _GLIBCXX_NOEXCEPT
309  { return _M_t.end(); }
310 
311  /**
312  * Returns a read-only (constant) iterator that points to the last
313  * element in the %set. Iteration is done in descending order according
314  * to the keys.
315  */
317  rbegin() const _GLIBCXX_NOEXCEPT
318  { return _M_t.rbegin(); }
319 
320  /**
321  * Returns a read-only (constant) reverse iterator that points to the
322  * last pair in the %set. Iteration is done in descending order
323  * according to the keys.
324  */
326  rend() const _GLIBCXX_NOEXCEPT
327  { return _M_t.rend(); }
328 
329 #ifdef __GXX_EXPERIMENTAL_CXX0X__
330  /**
331  * Returns a read-only (constant) iterator that points to the first
332  * element in the %set. Iteration is done in ascending order according
333  * to the keys.
334  */
335  iterator
336  cbegin() const noexcept
337  { return _M_t.begin(); }
338 
339  /**
340  * Returns a read-only (constant) iterator that points one past the last
341  * element in the %set. Iteration is done in ascending order according
342  * to the keys.
343  */
344  iterator
345  cend() const noexcept
346  { return _M_t.end(); }
347 
348  /**
349  * Returns a read-only (constant) iterator that points to the last
350  * element in the %set. Iteration is done in descending order according
351  * to the keys.
352  */
354  crbegin() const noexcept
355  { return _M_t.rbegin(); }
356 
357  /**
358  * Returns a read-only (constant) reverse iterator that points to the
359  * last pair in the %set. Iteration is done in descending order
360  * according to the keys.
361  */
363  crend() const noexcept
364  { return _M_t.rend(); }
365 #endif
366 
367  /// Returns true if the %set is empty.
368  bool
369  empty() const _GLIBCXX_NOEXCEPT
370  { return _M_t.empty(); }
371 
372  /// Returns the size of the %set.
373  size_type
374  size() const _GLIBCXX_NOEXCEPT
375  { return _M_t.size(); }
376 
377  /// Returns the maximum size of the %set.
378  size_type
379  max_size() const _GLIBCXX_NOEXCEPT
380  { return _M_t.max_size(); }
381 
382  /**
383  * @brief Swaps data with another %set.
384  * @param __x A %set of the same element and allocator types.
385  *
386  * This exchanges the elements between two sets in constant
387  * time. (It is only swapping a pointer, an integer, and an
388  * instance of the @c Compare type (which itself is often
389  * stateless and empty), so it should be quite fast.) Note
390  * that the global std::swap() function is specialized such
391  * that std::swap(s1,s2) will feed to this function.
392  */
393  void
394  swap(set& __x)
395  { _M_t.swap(__x._M_t); }
396 
397  // insert/erase
398  /**
399  * @brief Attempts to insert an element into the %set.
400  * @param __x Element to be inserted.
401  * @return A pair, of which the first element is an iterator that points
402  * to the possibly inserted element, and the second is a bool
403  * that is true if the element was actually inserted.
404  *
405  * This function attempts to insert an element into the %set. A %set
406  * relies on unique keys and thus an element is only inserted if it is
407  * not already present in the %set.
408  *
409  * Insertion requires logarithmic time.
410  */
412  insert(const value_type& __x)
413  {
415  _M_t._M_insert_unique(__x);
416  return std::pair<iterator, bool>(__p.first, __p.second);
417  }
418 
419 #ifdef __GXX_EXPERIMENTAL_CXX0X__
421  insert(value_type&& __x)
422  {
424  _M_t._M_insert_unique(std::move(__x));
425  return std::pair<iterator, bool>(__p.first, __p.second);
426  }
427 #endif
428 
429  /**
430  * @brief Attempts to insert an element into the %set.
431  * @param __position An iterator that serves as a hint as to where the
432  * element should be inserted.
433  * @param __x Element to be inserted.
434  * @return An iterator that points to the element with key of
435  * @a __x (may or may not be the element passed in).
436  *
437  * This function is not concerned about whether the insertion took place,
438  * and thus does not return a boolean like the single-argument insert()
439  * does. Note that the first parameter is only a hint and can
440  * potentially improve the performance of the insertion process. A bad
441  * hint would cause no gains in efficiency.
442  *
443  * For more on @a hinting, see:
444  * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
445  *
446  * Insertion requires logarithmic time (if the hint is not taken).
447  */
448  iterator
449  insert(const_iterator __position, const value_type& __x)
450  { return _M_t._M_insert_unique_(__position, __x); }
451 
452 #ifdef __GXX_EXPERIMENTAL_CXX0X__
453  iterator
454  insert(const_iterator __position, value_type&& __x)
455  { return _M_t._M_insert_unique_(__position, std::move(__x)); }
456 #endif
457 
458  /**
459  * @brief A template function that attempts to insert a range
460  * of elements.
461  * @param __first Iterator pointing to the start of the range to be
462  * inserted.
463  * @param __last Iterator pointing to the end of the range.
464  *
465  * Complexity similar to that of the range constructor.
466  */
467  template<typename _InputIterator>
468  void
469  insert(_InputIterator __first, _InputIterator __last)
470  { _M_t._M_insert_unique(__first, __last); }
471 
472 #ifdef __GXX_EXPERIMENTAL_CXX0X__
473  /**
474  * @brief Attempts to insert a list of elements into the %set.
475  * @param __l A std::initializer_list<value_type> of elements
476  * to be inserted.
477  *
478  * Complexity similar to that of the range constructor.
479  */
480  void
482  { this->insert(__l.begin(), __l.end()); }
483 #endif
484 
485 #ifdef __GXX_EXPERIMENTAL_CXX0X__
486  // _GLIBCXX_RESOLVE_LIB_DEFECTS
487  // DR 130. Associative erase should return an iterator.
488  /**
489  * @brief Erases an element from a %set.
490  * @param __position An iterator pointing to the element to be erased.
491  * @return An iterator pointing to the element immediately following
492  * @a __position prior to the element being erased. If no such
493  * element exists, end() is returned.
494  *
495  * This function erases an element, pointed to by the given iterator,
496  * from a %set. Note that this function only erases the element, and
497  * that if the element is itself a pointer, the pointed-to memory is not
498  * touched in any way. Managing the pointer is the user's
499  * responsibility.
500  */
501  iterator
502  erase(const_iterator __position)
503  { return _M_t.erase(__position); }
504 #else
505  /**
506  * @brief Erases an element from a %set.
507  * @param position An iterator pointing to the element to be erased.
508  *
509  * This function erases an element, pointed to by the given iterator,
510  * from a %set. Note that this function only erases the element, and
511  * that if the element is itself a pointer, the pointed-to memory is not
512  * touched in any way. Managing the pointer is the user's
513  * responsibility.
514  */
515  void
516  erase(iterator __position)
517  { _M_t.erase(__position); }
518 #endif
519 
520  /**
521  * @brief Erases elements according to the provided key.
522  * @param __x Key of element to be erased.
523  * @return The number of elements erased.
524  *
525  * This function erases all the elements located by the given key from
526  * a %set.
527  * Note that this function only erases the element, and that if
528  * the element is itself a pointer, the pointed-to memory is not touched
529  * in any way. Managing the pointer is the user's responsibility.
530  */
531  size_type
532  erase(const key_type& __x)
533  { return _M_t.erase(__x); }
534 
535 #ifdef __GXX_EXPERIMENTAL_CXX0X__
536  // _GLIBCXX_RESOLVE_LIB_DEFECTS
537  // DR 130. Associative erase should return an iterator.
538  /**
539  * @brief Erases a [__first,__last) range of elements from a %set.
540  * @param __first Iterator pointing to the start of the range to be
541  * erased.
542 
543  * @param __last Iterator pointing to the end of the range to
544  * be erased.
545  * @return The iterator @a __last.
546  *
547  * This function erases a sequence of elements from a %set.
548  * Note that this function only erases the element, and that if
549  * the element is itself a pointer, the pointed-to memory is not touched
550  * in any way. Managing the pointer is the user's responsibility.
551  */
552  iterator
554  { return _M_t.erase(__first, __last); }
555 #else
556  /**
557  * @brief Erases a [first,last) range of elements from a %set.
558  * @param __first Iterator pointing to the start of the range to be
559  * erased.
560  * @param __last Iterator pointing to the end of the range to
561  * be erased.
562  *
563  * This function erases a sequence of elements from a %set.
564  * Note that this function only erases the element, and that if
565  * the element is itself a pointer, the pointed-to memory is not touched
566  * in any way. Managing the pointer is the user's responsibility.
567  */
568  void
569  erase(iterator __first, iterator __last)
570  { _M_t.erase(__first, __last); }
571 #endif
572 
573  /**
574  * Erases all elements in a %set. Note that this function only erases
575  * the elements, and that if the elements themselves are pointers, the
576  * pointed-to memory is not touched in any way. Managing the pointer is
577  * the user's responsibility.
578  */
579  void
580  clear() _GLIBCXX_NOEXCEPT
581  { _M_t.clear(); }
582 
583  // set operations:
584 
585  /**
586  * @brief Finds the number of elements.
587  * @param __x Element to located.
588  * @return Number of elements with specified key.
589  *
590  * This function only makes sense for multisets; for set the result will
591  * either be 0 (not present) or 1 (present).
592  */
593  size_type
594  count(const key_type& __x) const
595  { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
596 
597  // _GLIBCXX_RESOLVE_LIB_DEFECTS
598  // 214. set::find() missing const overload
599  //@{
600  /**
601  * @brief Tries to locate an element in a %set.
602  * @param __x Element to be located.
603  * @return Iterator pointing to sought-after element, or end() if not
604  * found.
605  *
606  * This function takes a key and tries to locate the element with which
607  * the key matches. If successful the function returns an iterator
608  * pointing to the sought after element. If unsuccessful it returns the
609  * past-the-end ( @c end() ) iterator.
610  */
611  iterator
612  find(const key_type& __x)
613  { return _M_t.find(__x); }
614 
616  find(const key_type& __x) const
617  { return _M_t.find(__x); }
618  //@}
619 
620  //@{
621  /**
622  * @brief Finds the beginning of a subsequence matching given key.
623  * @param __x Key to be located.
624  * @return Iterator pointing to first element equal to or greater
625  * than key, or end().
626  *
627  * This function returns the first element of a subsequence of elements
628  * that matches the given key. If unsuccessful it returns an iterator
629  * pointing to the first element that has a greater value than given key
630  * or end() if no such element exists.
631  */
632  iterator
633  lower_bound(const key_type& __x)
634  { return _M_t.lower_bound(__x); }
635 
637  lower_bound(const key_type& __x) const
638  { return _M_t.lower_bound(__x); }
639  //@}
640 
641  //@{
642  /**
643  * @brief Finds the end of a subsequence matching given key.
644  * @param __x Key to be located.
645  * @return Iterator pointing to the first element
646  * greater than key, or end().
647  */
648  iterator
649  upper_bound(const key_type& __x)
650  { return _M_t.upper_bound(__x); }
651 
653  upper_bound(const key_type& __x) const
654  { return _M_t.upper_bound(__x); }
655  //@}
656 
657  //@{
658  /**
659  * @brief Finds a subsequence matching given key.
660  * @param __x Key to be located.
661  * @return Pair of iterators that possibly points to the subsequence
662  * matching given key.
663  *
664  * This function is equivalent to
665  * @code
666  * std::make_pair(c.lower_bound(val),
667  * c.upper_bound(val))
668  * @endcode
669  * (but is faster than making the calls separately).
670  *
671  * This function probably only makes sense for multisets.
672  */
674  equal_range(const key_type& __x)
675  { return _M_t.equal_range(__x); }
676 
678  equal_range(const key_type& __x) const
679  { return _M_t.equal_range(__x); }
680  //@}
681 
682  template<typename _K1, typename _C1, typename _A1>
683  friend bool
684  operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
685 
686  template<typename _K1, typename _C1, typename _A1>
687  friend bool
688  operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
689  };
690 
691 
692  /**
693  * @brief Set equality comparison.
694  * @param __x A %set.
695  * @param __y A %set of the same type as @a x.
696  * @return True iff the size and elements of the sets are equal.
697  *
698  * This is an equivalence relation. It is linear in the size of the sets.
699  * Sets are considered equivalent if their sizes are equal, and if
700  * corresponding elements compare equal.
701  */
702  template<typename _Key, typename _Compare, typename _Alloc>
703  inline bool
704  operator==(const set<_Key, _Compare, _Alloc>& __x,
705  const set<_Key, _Compare, _Alloc>& __y)
706  { return __x._M_t == __y._M_t; }
707 
708  /**
709  * @brief Set ordering relation.
710  * @param __x A %set.
711  * @param __y A %set of the same type as @a x.
712  * @return True iff @a __x is lexicographically less than @a __y.
713  *
714  * This is a total ordering relation. It is linear in the size of the
715  * maps. The elements must be comparable with @c <.
716  *
717  * See std::lexicographical_compare() for how the determination is made.
718  */
719  template<typename _Key, typename _Compare, typename _Alloc>
720  inline bool
721  operator<(const set<_Key, _Compare, _Alloc>& __x,
722  const set<_Key, _Compare, _Alloc>& __y)
723  { return __x._M_t < __y._M_t; }
724 
725  /// Returns !(x == y).
726  template<typename _Key, typename _Compare, typename _Alloc>
727  inline bool
728  operator!=(const set<_Key, _Compare, _Alloc>& __x,
729  const set<_Key, _Compare, _Alloc>& __y)
730  { return !(__x == __y); }
731 
732  /// Returns y < x.
733  template<typename _Key, typename _Compare, typename _Alloc>
734  inline bool
735  operator>(const set<_Key, _Compare, _Alloc>& __x,
736  const set<_Key, _Compare, _Alloc>& __y)
737  { return __y < __x; }
738 
739  /// Returns !(y < x)
740  template<typename _Key, typename _Compare, typename _Alloc>
741  inline bool
742  operator<=(const set<_Key, _Compare, _Alloc>& __x,
743  const set<_Key, _Compare, _Alloc>& __y)
744  { return !(__y < __x); }
745 
746  /// Returns !(x < y)
747  template<typename _Key, typename _Compare, typename _Alloc>
748  inline bool
749  operator>=(const set<_Key, _Compare, _Alloc>& __x,
750  const set<_Key, _Compare, _Alloc>& __y)
751  { return !(__x < __y); }
752 
753  /// See std::set::swap().
754  template<typename _Key, typename _Compare, typename _Alloc>
755  inline void
757  { __x.swap(__y); }
758 
759 _GLIBCXX_END_NAMESPACE_CONTAINER
760 } //namespace std
761 #endif /* _STL_SET_H */