libstdc++
stl_set.h
Go to the documentation of this file.
00001 // Set implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
00004 // 2011 Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /*
00027  *
00028  * Copyright (c) 1994
00029  * Hewlett-Packard Company
00030  *
00031  * Permission to use, copy, modify, distribute and sell this software
00032  * and its documentation for any purpose is hereby granted without fee,
00033  * provided that the above copyright notice appear in all copies and
00034  * that both that copyright notice and this permission notice appear
00035  * in supporting documentation.  Hewlett-Packard Company makes no
00036  * representations about the suitability of this software for any
00037  * purpose.  It is provided "as is" without express or implied warranty.
00038  *
00039  *
00040  * Copyright (c) 1996,1997
00041  * Silicon Graphics Computer Systems, Inc.
00042  *
00043  * Permission to use, copy, modify, distribute and sell this software
00044  * and its documentation for any purpose is hereby granted without fee,
00045  * provided that the above copyright notice appear in all copies and
00046  * that both that copyright notice and this permission notice appear
00047  * in supporting documentation.  Silicon Graphics makes no
00048  * representations about the suitability of this software for any
00049  * purpose.  It is provided "as is" without express or implied warranty.
00050  */
00051 
00052 /** @file bits/stl_set.h
00053  *  This is an internal header file, included by other library headers.
00054  *  Do not attempt to use it directly. @headername{set}
00055  */
00056 
00057 #ifndef _STL_SET_H
00058 #define _STL_SET_H 1
00059 
00060 #include <bits/concept_check.h>
00061 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00062 #include <initializer_list>
00063 #endif
00064 
00065 namespace std _GLIBCXX_VISIBILITY(default)
00066 {
00067 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00068 
00069   /**
00070    *  @brief A standard container made up of unique keys, which can be
00071    *  retrieved in logarithmic time.
00072    *
00073    *  @ingroup associative_containers
00074    *
00075    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00076    *  <a href="tables.html#66">reversible container</a>, and an
00077    *  <a href="tables.html#69">associative container</a> (using unique keys).
00078    *
00079    *  Sets support bidirectional iterators.
00080    *
00081    *  @tparam  _Key  Type of key objects.
00082    *  @tparam  _Compare  Comparison function object type, defaults to less<Key>.
00083    *  @tparam  _Alloc  Allocator type, defaults to allocator<Key>.
00084    *
00085    *  The private tree data is declared exactly the same way for set and
00086    *  multiset; the distinction is made entirely in how the tree functions are
00087    *  called (*_unique versus *_equal, same as the standard).
00088   */
00089   template<typename _Key, typename _Compare = std::less<_Key>,
00090        typename _Alloc = std::allocator<_Key> >
00091     class set
00092     {
00093       // concept requirements
00094       typedef typename _Alloc::value_type                   _Alloc_value_type;
00095       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
00096       __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00097                 _BinaryFunctionConcept)
00098       __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
00099 
00100     public:
00101       // typedefs:
00102       //@{
00103       /// Public typedefs.
00104       typedef _Key     key_type;
00105       typedef _Key     value_type;
00106       typedef _Compare key_compare;
00107       typedef _Compare value_compare;
00108       typedef _Alloc   allocator_type;
00109       //@}
00110 
00111     private:
00112       typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
00113 
00114       typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
00115                key_compare, _Key_alloc_type> _Rep_type;
00116       _Rep_type _M_t;  // Red-black tree representing set.
00117 
00118     public:
00119       //@{
00120       ///  Iterator-related typedefs.
00121       typedef typename _Key_alloc_type::pointer             pointer;
00122       typedef typename _Key_alloc_type::const_pointer       const_pointer;
00123       typedef typename _Key_alloc_type::reference           reference;
00124       typedef typename _Key_alloc_type::const_reference     const_reference;
00125       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00126       // DR 103. set::iterator is required to be modifiable,
00127       // but this allows modification of keys.
00128       typedef typename _Rep_type::const_iterator            iterator;
00129       typedef typename _Rep_type::const_iterator            const_iterator;
00130       typedef typename _Rep_type::const_reverse_iterator    reverse_iterator;
00131       typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00132       typedef typename _Rep_type::size_type                 size_type;
00133       typedef typename _Rep_type::difference_type           difference_type;
00134       //@}
00135 
00136       // allocation/deallocation
00137       /**
00138        *  @brief  Default constructor creates no elements.
00139        */
00140       set()
00141       : _M_t() { }
00142 
00143       /**
00144        *  @brief  Creates a %set with no elements.
00145        *  @param  __comp  Comparator to use.
00146        *  @param  __a  An allocator object.
00147        */
00148       explicit
00149       set(const _Compare& __comp,
00150       const allocator_type& __a = allocator_type())
00151       : _M_t(__comp, _Key_alloc_type(__a)) { }
00152 
00153       /**
00154        *  @brief  Builds a %set from a range.
00155        *  @param  __first  An input iterator.
00156        *  @param  __last  An input iterator.
00157        *
00158        *  Create a %set consisting of copies of the elements from
00159        *  [__first,__last).  This is linear in N if the range is
00160        *  already sorted, and NlogN otherwise (where N is
00161        *  distance(__first,__last)).
00162        */
00163       template<typename _InputIterator>
00164     set(_InputIterator __first, _InputIterator __last)
00165     : _M_t()
00166     { _M_t._M_insert_unique(__first, __last); }
00167 
00168       /**
00169        *  @brief  Builds a %set from a range.
00170        *  @param  __first  An input iterator.
00171        *  @param  __last  An input iterator.
00172        *  @param  __comp  A comparison functor.
00173        *  @param  __a  An allocator object.
00174        *
00175        *  Create a %set consisting of copies of the elements from
00176        *  [__first,__last).  This is linear in N if the range is
00177        *  already sorted, and NlogN otherwise (where N is
00178        *  distance(__first,__last)).
00179        */
00180       template<typename _InputIterator>
00181     set(_InputIterator __first, _InputIterator __last,
00182         const _Compare& __comp,
00183         const allocator_type& __a = allocator_type())
00184     : _M_t(__comp, _Key_alloc_type(__a))
00185         { _M_t._M_insert_unique(__first, __last); }
00186 
00187       /**
00188        *  @brief  %Set copy constructor.
00189        *  @param  __x  A %set of identical element and allocator types.
00190        *
00191        *  The newly-created %set uses a copy of the allocation object used
00192        *  by @a __x.
00193        */
00194       set(const set& __x)
00195       : _M_t(__x._M_t) { }
00196 
00197 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00198      /**
00199        *  @brief %Set move constructor
00200        *  @param __x  A %set of identical element and allocator types.
00201        *
00202        *  The newly-created %set contains the exact contents of @a x.
00203        *  The contents of @a x are a valid, but unspecified %set.
00204        */
00205       set(set&& __x)
00206       noexcept(is_nothrow_copy_constructible<_Compare>::value)
00207       : _M_t(std::move(__x._M_t)) { }
00208 
00209       /**
00210        *  @brief  Builds a %set from an initializer_list.
00211        *  @param  __l  An initializer_list.
00212        *  @param  __comp  A comparison functor.
00213        *  @param  __a  An allocator object.
00214        *
00215        *  Create a %set consisting of copies of the elements in the list.
00216        *  This is linear in N if the list is already sorted, and NlogN
00217        *  otherwise (where N is @a __l.size()).
00218        */
00219       set(initializer_list<value_type> __l,
00220       const _Compare& __comp = _Compare(),
00221       const allocator_type& __a = allocator_type())
00222       : _M_t(__comp, _Key_alloc_type(__a))
00223       { _M_t._M_insert_unique(__l.begin(), __l.end()); }
00224 #endif
00225 
00226       /**
00227        *  @brief  %Set assignment operator.
00228        *  @param  __x  A %set of identical element and allocator types.
00229        *
00230        *  All the elements of @a __x are copied, but unlike the copy
00231        *  constructor, the allocator object is not copied.
00232        */
00233       set&
00234       operator=(const set& __x)
00235       {
00236     _M_t = __x._M_t;
00237     return *this;
00238       }
00239 
00240 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00241       /**
00242        *  @brief %Set move assignment operator.
00243        *  @param __x  A %set of identical element and allocator types.
00244        *
00245        *  The contents of @a __x are moved into this %set (without copying).
00246        *  @a __x is a valid, but unspecified %set.
00247        */
00248       set&
00249       operator=(set&& __x)
00250       {
00251     // NB: DR 1204.
00252     // NB: DR 675.
00253     this->clear();
00254     this->swap(__x);
00255         return *this;
00256       }
00257 
00258       /**
00259        *  @brief  %Set list assignment operator.
00260        *  @param  __l  An initializer_list.
00261        *
00262        *  This function fills a %set with copies of the elements in the
00263        *  initializer list @a __l.
00264        *
00265        *  Note that the assignment completely changes the %set and
00266        *  that the resulting %set's size is the same as the number
00267        *  of elements assigned.  Old data may be lost.
00268        */
00269       set&
00270       operator=(initializer_list<value_type> __l)
00271       {
00272     this->clear();
00273     this->insert(__l.begin(), __l.end());
00274     return *this;
00275       }
00276 #endif
00277 
00278       // accessors:
00279 
00280       ///  Returns the comparison object with which the %set was constructed.
00281       key_compare
00282       key_comp() const
00283       { return _M_t.key_comp(); }
00284       ///  Returns the comparison object with which the %set was constructed.
00285       value_compare
00286       value_comp() const
00287       { return _M_t.key_comp(); }
00288       ///  Returns the allocator object with which the %set was constructed.
00289       allocator_type
00290       get_allocator() const _GLIBCXX_NOEXCEPT
00291       { return allocator_type(_M_t.get_allocator()); }
00292 
00293       /**
00294        *  Returns a read-only (constant) iterator that points to the first
00295        *  element in the %set.  Iteration is done in ascending order according
00296        *  to the keys.
00297        */
00298       iterator
00299       begin() const _GLIBCXX_NOEXCEPT
00300       { return _M_t.begin(); }
00301 
00302       /**
00303        *  Returns a read-only (constant) iterator that points one past the last
00304        *  element in the %set.  Iteration is done in ascending order according
00305        *  to the keys.
00306        */
00307       iterator
00308       end() const _GLIBCXX_NOEXCEPT
00309       { return _M_t.end(); }
00310 
00311       /**
00312        *  Returns a read-only (constant) iterator that points to the last
00313        *  element in the %set.  Iteration is done in descending order according
00314        *  to the keys.
00315        */
00316       reverse_iterator
00317       rbegin() const _GLIBCXX_NOEXCEPT
00318       { return _M_t.rbegin(); }
00319 
00320       /**
00321        *  Returns a read-only (constant) reverse iterator that points to the
00322        *  last pair in the %set.  Iteration is done in descending order
00323        *  according to the keys.
00324        */
00325       reverse_iterator
00326       rend() const _GLIBCXX_NOEXCEPT
00327       { return _M_t.rend(); }
00328 
00329 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00330       /**
00331        *  Returns a read-only (constant) iterator that points to the first
00332        *  element in the %set.  Iteration is done in ascending order according
00333        *  to the keys.
00334        */
00335       iterator
00336       cbegin() const noexcept
00337       { return _M_t.begin(); }
00338 
00339       /**
00340        *  Returns a read-only (constant) iterator that points one past the last
00341        *  element in the %set.  Iteration is done in ascending order according
00342        *  to the keys.
00343        */
00344       iterator
00345       cend() const noexcept
00346       { return _M_t.end(); }
00347 
00348       /**
00349        *  Returns a read-only (constant) iterator that points to the last
00350        *  element in the %set.  Iteration is done in descending order according
00351        *  to the keys.
00352        */
00353       reverse_iterator
00354       crbegin() const noexcept
00355       { return _M_t.rbegin(); }
00356 
00357       /**
00358        *  Returns a read-only (constant) reverse iterator that points to the
00359        *  last pair in the %set.  Iteration is done in descending order
00360        *  according to the keys.
00361        */
00362       reverse_iterator
00363       crend() const noexcept
00364       { return _M_t.rend(); }
00365 #endif
00366 
00367       ///  Returns true if the %set is empty.
00368       bool
00369       empty() const _GLIBCXX_NOEXCEPT
00370       { return _M_t.empty(); }
00371 
00372       ///  Returns the size of the %set.
00373       size_type
00374       size() const _GLIBCXX_NOEXCEPT
00375       { return _M_t.size(); }
00376 
00377       ///  Returns the maximum size of the %set.
00378       size_type
00379       max_size() const _GLIBCXX_NOEXCEPT
00380       { return _M_t.max_size(); }
00381 
00382       /**
00383        *  @brief  Swaps data with another %set.
00384        *  @param  __x  A %set of the same element and allocator types.
00385        *
00386        *  This exchanges the elements between two sets in constant
00387        *  time.  (It is only swapping a pointer, an integer, and an
00388        *  instance of the @c Compare type (which itself is often
00389        *  stateless and empty), so it should be quite fast.)  Note
00390        *  that the global std::swap() function is specialized such
00391        *  that std::swap(s1,s2) will feed to this function.
00392        */
00393       void
00394       swap(set& __x)
00395       { _M_t.swap(__x._M_t); }
00396 
00397       // insert/erase
00398       /**
00399        *  @brief Attempts to insert an element into the %set.
00400        *  @param  __x  Element to be inserted.
00401        *  @return  A pair, of which the first element is an iterator that points
00402        *           to the possibly inserted element, and the second is a bool
00403        *           that is true if the element was actually inserted.
00404        *
00405        *  This function attempts to insert an element into the %set.  A %set
00406        *  relies on unique keys and thus an element is only inserted if it is
00407        *  not already present in the %set.
00408        *
00409        *  Insertion requires logarithmic time.
00410        */
00411       std::pair<iterator, bool>
00412       insert(const value_type& __x)
00413       {
00414     std::pair<typename _Rep_type::iterator, bool> __p =
00415       _M_t._M_insert_unique(__x);
00416     return std::pair<iterator, bool>(__p.first, __p.second);
00417       }
00418 
00419 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00420       std::pair<iterator, bool>
00421       insert(value_type&& __x)
00422       {
00423     std::pair<typename _Rep_type::iterator, bool> __p =
00424       _M_t._M_insert_unique(std::move(__x));
00425     return std::pair<iterator, bool>(__p.first, __p.second);
00426       }
00427 #endif
00428 
00429       /**
00430        *  @brief Attempts to insert an element into the %set.
00431        *  @param  __position  An iterator that serves as a hint as to where the
00432        *                    element should be inserted.
00433        *  @param  __x  Element to be inserted.
00434        *  @return An iterator that points to the element with key of
00435        *           @a __x (may or may not be the element passed in).
00436        *
00437        *  This function is not concerned about whether the insertion took place,
00438        *  and thus does not return a boolean like the single-argument insert()
00439        *  does.  Note that the first parameter is only a hint and can
00440        *  potentially improve the performance of the insertion process.  A bad
00441        *  hint would cause no gains in efficiency.
00442        *
00443        *  For more on @a hinting, see:
00444        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
00445        *
00446        *  Insertion requires logarithmic time (if the hint is not taken).
00447        */
00448       iterator
00449       insert(const_iterator __position, const value_type& __x)
00450       { return _M_t._M_insert_unique_(__position, __x); }
00451 
00452 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00453       iterator
00454       insert(const_iterator __position, value_type&& __x)
00455       { return _M_t._M_insert_unique_(__position, std::move(__x)); }
00456 #endif
00457 
00458       /**
00459        *  @brief A template function that attempts to insert a range
00460        *  of elements.
00461        *  @param  __first  Iterator pointing to the start of the range to be
00462        *                   inserted.
00463        *  @param  __last  Iterator pointing to the end of the range.
00464        *
00465        *  Complexity similar to that of the range constructor.
00466        */
00467       template<typename _InputIterator>
00468     void
00469     insert(_InputIterator __first, _InputIterator __last)
00470     { _M_t._M_insert_unique(__first, __last); }
00471 
00472 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00473       /**
00474        *  @brief Attempts to insert a list of elements into the %set.
00475        *  @param  __l  A std::initializer_list<value_type> of elements
00476        *               to be inserted.
00477        *
00478        *  Complexity similar to that of the range constructor.
00479        */
00480       void
00481       insert(initializer_list<value_type> __l)
00482       { this->insert(__l.begin(), __l.end()); }
00483 #endif
00484 
00485 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00486       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00487       // DR 130. Associative erase should return an iterator.
00488       /**
00489        *  @brief Erases an element from a %set.
00490        *  @param  __position  An iterator pointing to the element to be erased.
00491        *  @return An iterator pointing to the element immediately following
00492        *          @a __position prior to the element being erased. If no such
00493        *          element exists, end() is returned.
00494        *
00495        *  This function erases an element, pointed to by the given iterator,
00496        *  from a %set.  Note that this function only erases the element, and
00497        *  that if the element is itself a pointer, the pointed-to memory is not
00498        *  touched in any way.  Managing the pointer is the user's
00499        *  responsibility.
00500        */
00501       iterator
00502       erase(const_iterator __position)
00503       { return _M_t.erase(__position); }
00504 #else
00505       /**
00506        *  @brief Erases an element from a %set.
00507        *  @param  position  An iterator pointing to the element to be erased.
00508        *
00509        *  This function erases an element, pointed to by the given iterator,
00510        *  from a %set.  Note that this function only erases the element, and
00511        *  that if the element is itself a pointer, the pointed-to memory is not
00512        *  touched in any way.  Managing the pointer is the user's
00513        *  responsibility.
00514        */
00515       void
00516       erase(iterator __position)
00517       { _M_t.erase(__position); }
00518 #endif
00519 
00520       /**
00521        *  @brief Erases elements according to the provided key.
00522        *  @param  __x  Key of element to be erased.
00523        *  @return  The number of elements erased.
00524        *
00525        *  This function erases all the elements located by the given key from
00526        *  a %set.
00527        *  Note that this function only erases the element, and that if
00528        *  the element is itself a pointer, the pointed-to memory is not touched
00529        *  in any way.  Managing the pointer is the user's responsibility.
00530        */
00531       size_type
00532       erase(const key_type& __x)
00533       { return _M_t.erase(__x); }
00534 
00535 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00536       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00537       // DR 130. Associative erase should return an iterator.
00538       /**
00539        *  @brief Erases a [__first,__last) range of elements from a %set.
00540        *  @param  __first  Iterator pointing to the start of the range to be
00541        *                 erased.
00542 
00543        *  @param __last Iterator pointing to the end of the range to
00544        *  be erased.
00545        *  @return The iterator @a __last.
00546        *
00547        *  This function erases a sequence of elements from a %set.
00548        *  Note that this function only erases the element, and that if
00549        *  the element is itself a pointer, the pointed-to memory is not touched
00550        *  in any way.  Managing the pointer is the user's responsibility.
00551        */
00552       iterator
00553       erase(const_iterator __first, const_iterator __last)
00554       { return _M_t.erase(__first, __last); }
00555 #else
00556       /**
00557        *  @brief Erases a [first,last) range of elements from a %set.
00558        *  @param  __first  Iterator pointing to the start of the range to be
00559        *                 erased.
00560        *  @param __last Iterator pointing to the end of the range to
00561        *  be erased.
00562        *
00563        *  This function erases a sequence of elements from a %set.
00564        *  Note that this function only erases the element, and that if
00565        *  the element is itself a pointer, the pointed-to memory is not touched
00566        *  in any way.  Managing the pointer is the user's responsibility.
00567        */
00568       void
00569       erase(iterator __first, iterator __last)
00570       { _M_t.erase(__first, __last); }
00571 #endif
00572 
00573       /**
00574        *  Erases all elements in a %set.  Note that this function only erases
00575        *  the elements, and that if the elements themselves are pointers, the
00576        *  pointed-to memory is not touched in any way.  Managing the pointer is
00577        *  the user's responsibility.
00578        */
00579       void
00580       clear() _GLIBCXX_NOEXCEPT
00581       { _M_t.clear(); }
00582 
00583       // set operations:
00584 
00585       /**
00586        *  @brief  Finds the number of elements.
00587        *  @param  __x  Element to located.
00588        *  @return  Number of elements with specified key.
00589        *
00590        *  This function only makes sense for multisets; for set the result will
00591        *  either be 0 (not present) or 1 (present).
00592        */
00593       size_type
00594       count(const key_type& __x) const
00595       { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
00596 
00597       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00598       // 214.  set::find() missing const overload
00599       //@{
00600       /**
00601        *  @brief Tries to locate an element in a %set.
00602        *  @param  __x  Element to be located.
00603        *  @return  Iterator pointing to sought-after element, or end() if not
00604        *           found.
00605        *
00606        *  This function takes a key and tries to locate the element with which
00607        *  the key matches.  If successful the function returns an iterator
00608        *  pointing to the sought after element.  If unsuccessful it returns the
00609        *  past-the-end ( @c end() ) iterator.
00610        */
00611       iterator
00612       find(const key_type& __x)
00613       { return _M_t.find(__x); }
00614 
00615       const_iterator
00616       find(const key_type& __x) const
00617       { return _M_t.find(__x); }
00618       //@}
00619 
00620       //@{
00621       /**
00622        *  @brief Finds the beginning of a subsequence matching given key.
00623        *  @param  __x  Key to be located.
00624        *  @return  Iterator pointing to first element equal to or greater
00625        *           than key, or end().
00626        *
00627        *  This function returns the first element of a subsequence of elements
00628        *  that matches the given key.  If unsuccessful it returns an iterator
00629        *  pointing to the first element that has a greater value than given key
00630        *  or end() if no such element exists.
00631        */
00632       iterator
00633       lower_bound(const key_type& __x)
00634       { return _M_t.lower_bound(__x); }
00635 
00636       const_iterator
00637       lower_bound(const key_type& __x) const
00638       { return _M_t.lower_bound(__x); }
00639       //@}
00640 
00641       //@{
00642       /**
00643        *  @brief Finds the end of a subsequence matching given key.
00644        *  @param  __x  Key to be located.
00645        *  @return Iterator pointing to the first element
00646        *          greater than key, or end().
00647        */
00648       iterator
00649       upper_bound(const key_type& __x)
00650       { return _M_t.upper_bound(__x); }
00651 
00652       const_iterator
00653       upper_bound(const key_type& __x) const
00654       { return _M_t.upper_bound(__x); }
00655       //@}
00656 
00657       //@{
00658       /**
00659        *  @brief Finds a subsequence matching given key.
00660        *  @param  __x  Key to be located.
00661        *  @return  Pair of iterators that possibly points to the subsequence
00662        *           matching given key.
00663        *
00664        *  This function is equivalent to
00665        *  @code
00666        *    std::make_pair(c.lower_bound(val),
00667        *                   c.upper_bound(val))
00668        *  @endcode
00669        *  (but is faster than making the calls separately).
00670        *
00671        *  This function probably only makes sense for multisets.
00672        */
00673       std::pair<iterator, iterator>
00674       equal_range(const key_type& __x)
00675       { return _M_t.equal_range(__x); }
00676 
00677       std::pair<const_iterator, const_iterator>
00678       equal_range(const key_type& __x) const
00679       { return _M_t.equal_range(__x); }
00680       //@}
00681 
00682       template<typename _K1, typename _C1, typename _A1>
00683     friend bool
00684     operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
00685 
00686       template<typename _K1, typename _C1, typename _A1>
00687     friend bool
00688     operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
00689     };
00690 
00691 
00692   /**
00693    *  @brief  Set equality comparison.
00694    *  @param  __x  A %set.
00695    *  @param  __y  A %set of the same type as @a x.
00696    *  @return  True iff the size and elements of the sets are equal.
00697    *
00698    *  This is an equivalence relation.  It is linear in the size of the sets.
00699    *  Sets are considered equivalent if their sizes are equal, and if
00700    *  corresponding elements compare equal.
00701   */
00702   template<typename _Key, typename _Compare, typename _Alloc>
00703     inline bool
00704     operator==(const set<_Key, _Compare, _Alloc>& __x,
00705            const set<_Key, _Compare, _Alloc>& __y)
00706     { return __x._M_t == __y._M_t; }
00707 
00708   /**
00709    *  @brief  Set ordering relation.
00710    *  @param  __x  A %set.
00711    *  @param  __y  A %set of the same type as @a x.
00712    *  @return  True iff @a __x is lexicographically less than @a __y.
00713    *
00714    *  This is a total ordering relation.  It is linear in the size of the
00715    *  maps.  The elements must be comparable with @c <.
00716    *
00717    *  See std::lexicographical_compare() for how the determination is made.
00718   */
00719   template<typename _Key, typename _Compare, typename _Alloc>
00720     inline bool
00721     operator<(const set<_Key, _Compare, _Alloc>& __x,
00722           const set<_Key, _Compare, _Alloc>& __y)
00723     { return __x._M_t < __y._M_t; }
00724 
00725   ///  Returns !(x == y).
00726   template<typename _Key, typename _Compare, typename _Alloc>
00727     inline bool
00728     operator!=(const set<_Key, _Compare, _Alloc>& __x,
00729            const set<_Key, _Compare, _Alloc>& __y)
00730     { return !(__x == __y); }
00731 
00732   ///  Returns y < x.
00733   template<typename _Key, typename _Compare, typename _Alloc>
00734     inline bool
00735     operator>(const set<_Key, _Compare, _Alloc>& __x,
00736           const set<_Key, _Compare, _Alloc>& __y)
00737     { return __y < __x; }
00738 
00739   ///  Returns !(y < x)
00740   template<typename _Key, typename _Compare, typename _Alloc>
00741     inline bool
00742     operator<=(const set<_Key, _Compare, _Alloc>& __x,
00743            const set<_Key, _Compare, _Alloc>& __y)
00744     { return !(__y < __x); }
00745 
00746   ///  Returns !(x < y)
00747   template<typename _Key, typename _Compare, typename _Alloc>
00748     inline bool
00749     operator>=(const set<_Key, _Compare, _Alloc>& __x,
00750            const set<_Key, _Compare, _Alloc>& __y)
00751     { return !(__x < __y); }
00752 
00753   /// See std::set::swap().
00754   template<typename _Key, typename _Compare, typename _Alloc>
00755     inline void
00756     swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y)
00757     { __x.swap(__y); }
00758 
00759 _GLIBCXX_END_NAMESPACE_CONTAINER
00760 } //namespace std
00761 #endif /* _STL_SET_H */