stl_set.h

Go to the documentation of this file.
00001 // Set implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1996,1997
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00056 /** @file stl_set.h
00057  *  This is an internal header file, included by other library headers.
00058  *  You should not attempt to use it directly.
00059  */
00060 
00061 #ifndef _SET_H
00062 #define _SET_H 1
00063 
00064 #include <bits/concept_check.h>
00065 
00066 namespace _GLIBCXX_STD
00067 {
00068   // Forward declarations of operators < and ==, needed for friend declaration.
00069   template<class _Key, class _Compare = std::less<_Key>,
00070        class _Alloc = std::allocator<_Key> >
00071     class set;
00072 
00073   template<class _Key, class _Compare, class _Alloc>
00074     inline bool
00075     operator==(const set<_Key,_Compare,_Alloc>& __x,
00076            const set<_Key,_Compare,_Alloc>& __y);
00077 
00078   template<class _Key, class _Compare, class _Alloc>
00079     inline bool
00080     operator<(const set<_Key,_Compare,_Alloc>& __x,
00081           const set<_Key,_Compare,_Alloc>& __y);
00082 
00083   /**
00084    *  @brief A standard container made up of unique keys, which can be
00085    *  retrieved in logarithmic time.
00086    *
00087    *  @ingroup Containers
00088    *  @ingroup Assoc_containers
00089    *
00090    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00091    *  <a href="tables.html#66">reversible container</a>, and an
00092    *  <a href="tables.html#69">associative container</a> (using unique keys).
00093    *
00094    *  Sets support bidirectional iterators.
00095    *
00096    *  @param  Key  Type of key objects.
00097    *  @param  Compare  Comparison function object type, defaults to less<Key>.
00098    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
00099    *
00100    *  @if maint
00101    *  The private tree data is declared exactly the same way for set and
00102    *  multiset; the distinction is made entirely in how the tree functions are
00103    *  called (*_unique versus *_equal, same as the standard).
00104    *  @endif
00105   */
00106   template<class _Key, class _Compare, class _Alloc>
00107     class set
00108     {
00109       // concept requirements
00110       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
00111       __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
00112                 _BinaryFunctionConcept)
00113 
00114     public:
00115       // typedefs:
00116       //@{
00117       /// Public typedefs.
00118       typedef _Key     key_type;
00119       typedef _Key     value_type;
00120       typedef _Compare key_compare;
00121       typedef _Compare value_compare;
00122       //@}
00123 
00124     private:
00125       typedef _Rb_tree<key_type, value_type,
00126                _Identity<value_type>, key_compare, _Alloc> _Rep_type;
00127       _Rep_type _M_t;  // red-black tree representing set
00128     public:
00129       //@{
00130       ///  Iterator-related typedefs.
00131       typedef typename _Alloc::pointer pointer;
00132       typedef typename _Alloc::const_pointer const_pointer;
00133       typedef typename _Alloc::reference reference;
00134       typedef typename _Alloc::const_reference const_reference;
00135       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00136       // DR 103. set::iterator is required to be modifiable,
00137       // but this allows modification of keys.
00138       typedef typename _Rep_type::const_iterator iterator;
00139       typedef typename _Rep_type::const_iterator const_iterator;
00140       typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
00141       typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
00142       typedef typename _Rep_type::size_type size_type;
00143       typedef typename _Rep_type::difference_type difference_type;
00144       typedef typename _Rep_type::allocator_type allocator_type;
00145       //@}
00146 
00147       // allocation/deallocation
00148       ///  Default constructor creates no elements.
00149       set()
00150       : _M_t(_Compare(), allocator_type()) {}
00151 
00152       /**
00153        *  @brief  Default constructor creates no elements.
00154        *
00155        *  @param  comp  Comparator to use.
00156        *  @param  a  Allocator to use.
00157        */
00158       explicit set(const _Compare& __comp,
00159            const allocator_type& __a = allocator_type())
00160       : _M_t(__comp, __a) {}
00161 
00162       /**
00163        *  @brief  Builds a %set from a range.
00164        *  @param  first  An input iterator.
00165        *  @param  last  An input iterator.
00166        *
00167        *  Create a %set consisting of copies of the elements from [first,last).
00168        *  This is linear in N if the range is already sorted, and NlogN
00169        *  otherwise (where N is distance(first,last)).
00170        */
00171       template<class _InputIterator>
00172         set(_InputIterator __first, _InputIterator __last)
00173         : _M_t(_Compare(), allocator_type())
00174         { _M_t.insert_unique(__first, __last); }
00175 
00176       /**
00177        *  @brief  Builds a %set from a range.
00178        *  @param  first  An input iterator.
00179        *  @param  last  An input iterator.
00180        *  @param  comp  A comparison functor.
00181        *  @param  a  An allocator object.
00182        *
00183        *  Create a %set consisting of copies of the elements from [first,last).
00184        *  This is linear in N if the range is already sorted, and NlogN
00185        *  otherwise (where N is distance(first,last)).
00186        */
00187       template<class _InputIterator>
00188         set(_InputIterator __first, _InputIterator __last,
00189         const _Compare& __comp,
00190         const allocator_type& __a = allocator_type())
00191     : _M_t(__comp, __a)
00192         { _M_t.insert_unique(__first, __last); }
00193 
00194       /**
00195        *  @brief  Set copy constructor.
00196        *  @param  x  A %set of identical element and allocator types.
00197        *
00198        *  The newly-created %set uses a copy of the allocation object used
00199        *  by @a x.
00200        */
00201       set(const set<_Key,_Compare,_Alloc>& __x)
00202       : _M_t(__x._M_t) { }
00203 
00204       /**
00205        *  @brief  Set assignment operator.
00206        *  @param  x  A %set of identical element and allocator types.
00207        *
00208        *  All the elements of @a x are copied, but unlike the copy constructor,
00209        *  the allocator object is not copied.
00210        */
00211       set<_Key,_Compare,_Alloc>&
00212       operator=(const set<_Key, _Compare, _Alloc>& __x)
00213       {
00214     _M_t = __x._M_t;
00215     return *this;
00216       }
00217 
00218       // accessors:
00219 
00220       ///  Returns the comparison object with which the %set was constructed.
00221       key_compare
00222       key_comp() const
00223       { return _M_t.key_comp(); }
00224       ///  Returns the comparison object with which the %set was constructed.
00225       value_compare
00226       value_comp() const
00227       { return _M_t.key_comp(); }
00228       ///  Returns the allocator object with which the %set was constructed.
00229       allocator_type
00230       get_allocator() const
00231       { return _M_t.get_allocator(); }
00232 
00233       /**
00234        *  Returns a read/write iterator that points to the first element in the
00235        *  %set.  Iteration is done in ascending order according to the keys.
00236        */
00237       iterator
00238       begin() const
00239       { return _M_t.begin(); }
00240 
00241       /**
00242        *  Returns a read/write iterator that points one past the last element in
00243        *  the %set.  Iteration is done in ascending order according to the keys.
00244        */
00245       iterator
00246       end() const
00247       { return _M_t.end(); }
00248 
00249       /**
00250        *  Returns a read/write reverse iterator that points to the last element
00251        *  in the %set.  Iteration is done in descending order according to the
00252        *  keys.
00253        */
00254       reverse_iterator
00255       rbegin() const
00256       { return _M_t.rbegin(); }
00257 
00258       /**
00259        *  Returns a read-only (constant) reverse iterator that points to the
00260        *  last pair in the %map.  Iteration is done in descending order
00261        *  according to the keys.
00262        */
00263       reverse_iterator
00264       rend() const
00265       { return _M_t.rend(); }
00266 
00267       ///  Returns true if the %set is empty.
00268       bool
00269       empty() const
00270       { return _M_t.empty(); }
00271 
00272       ///  Returns the size of the %set.
00273       size_type
00274       size() const
00275       { return _M_t.size(); }
00276 
00277       ///  Returns the maximum size of the %set.
00278       size_type
00279       max_size() const
00280       { return _M_t.max_size(); }
00281 
00282       /**
00283        *  @brief  Swaps data with another %set.
00284        *  @param  x  A %set of the same element and allocator types.
00285        *
00286        *  This exchanges the elements between two sets in constant time.
00287        *  (It is only swapping a pointer, an integer, and an instance of
00288        *  the @c Compare type (which itself is often stateless and empty), so it
00289        *  should be quite fast.)
00290        *  Note that the global std::swap() function is specialized such that
00291        *  std::swap(s1,s2) will feed to this function.
00292        */
00293       void
00294       swap(set<_Key,_Compare,_Alloc>& __x)
00295       { _M_t.swap(__x._M_t); }
00296 
00297       // insert/erase
00298       /**
00299        *  @brief Attempts to insert an element into the %set.
00300        *  @param  x  Element to be inserted.
00301        *  @return  A pair, of which the first element is an iterator that points
00302        *           to the possibly inserted element, and the second is a bool
00303        *           that is true if the element was actually inserted.
00304        *
00305        *  This function attempts to insert an element into the %set.  A %set
00306        *  relies on unique keys and thus an element is only inserted if it is
00307        *  not already present in the %set.
00308        *
00309        *  Insertion requires logarithmic time.
00310        */
00311       std::pair<iterator,bool>
00312       insert(const value_type& __x)
00313       {
00314     std::pair<typename _Rep_type::iterator, bool> __p =
00315       _M_t.insert_unique(__x);
00316     return std::pair<iterator, bool>(__p.first, __p.second);
00317       }
00318 
00319       /**
00320        *  @brief Attempts to insert an element into the %set.
00321        *  @param  position  An iterator that serves as a hint as to where the
00322        *                    element should be inserted.
00323        *  @param  x  Element to be inserted.
00324        *  @return  An iterator that points to the element with key of @a x (may
00325        *           or may not be the element passed in).
00326        *
00327        *  This function is not concerned about whether the insertion took place,
00328        *  and thus does not return a boolean like the single-argument insert()
00329        *  does.  Note that the first parameter is only a hint and can
00330        *  potentially improve the performance of the insertion process.  A bad
00331        *  hint would cause no gains in efficiency.
00332        *
00333        *  See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4
00334        *  for more on "hinting".
00335        *
00336        *  Insertion requires logarithmic time (if the hint is not taken).
00337        */
00338       iterator
00339       insert(iterator __position, const value_type& __x)
00340       {
00341     typedef typename _Rep_type::iterator _Rep_iterator;
00342     return _M_t.insert_unique((_Rep_iterator&)__position, __x);
00343       }
00344 
00345       /**
00346        *  @brief A template function that attemps to insert a range of elements.
00347        *  @param  first  Iterator pointing to the start of the range to be
00348        *                 inserted.
00349        *  @param  last  Iterator pointing to the end of the range.
00350        *
00351        *  Complexity similar to that of the range constructor.
00352        */
00353       template<class _InputIterator>
00354       void
00355       insert(_InputIterator __first, _InputIterator __last)
00356       { _M_t.insert_unique(__first, __last); }
00357 
00358       /**
00359        *  @brief Erases an element from a %set.
00360        *  @param  position  An iterator pointing to the element to be erased.
00361        *
00362        *  This function erases an element, pointed to by the given iterator,
00363        *  from a %set.  Note that this function only erases the element, and
00364        *  that if the element is itself a pointer, the pointed-to memory is not
00365        *  touched in any way.  Managing the pointer is the user's responsibilty.
00366        */
00367       void
00368       erase(iterator __position)
00369       {
00370     typedef typename _Rep_type::iterator _Rep_iterator;
00371     _M_t.erase((_Rep_iterator&)__position);
00372       }
00373 
00374       /**
00375        *  @brief Erases elements according to the provided key.
00376        *  @param  x  Key of element to be erased.
00377        *  @return  The number of elements erased.
00378        *
00379        *  This function erases all the elements located by the given key from
00380        *  a %set.
00381        *  Note that this function only erases the element, and that if
00382        *  the element is itself a pointer, the pointed-to memory is not touched
00383        *  in any way.  Managing the pointer is the user's responsibilty.
00384        */
00385       size_type
00386       erase(const key_type& __x) { return _M_t.erase(__x); }
00387 
00388       /**
00389        *  @brief Erases a [first,last) range of elements from a %set.
00390        *  @param  first  Iterator pointing to the start of the range to be
00391        *                 erased.
00392        *  @param  last  Iterator pointing to the end of the range to be erased.
00393        *
00394        *  This function erases a sequence of elements from a %set.
00395        *  Note that this function only erases the element, and that if
00396        *  the element is itself a pointer, the pointed-to memory is not touched
00397        *  in any way.  Managing the pointer is the user's responsibilty.
00398        */
00399       void
00400       erase(iterator __first, iterator __last)
00401       {
00402     typedef typename _Rep_type::iterator _Rep_iterator;
00403     _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last);
00404       }
00405 
00406       /**
00407        *  Erases all elements in a %set.  Note that this function only erases
00408        *  the elements, and that if the elements themselves are pointers, the
00409        *  pointed-to memory is not touched in any way.  Managing the pointer is
00410        *  the user's responsibilty.
00411        */
00412       void
00413       clear()
00414       { _M_t.clear(); }
00415 
00416       // set operations:
00417 
00418       /**
00419        *  @brief  Finds the number of elements.
00420        *  @param  x  Element to located.
00421        *  @return  Number of elements with specified key.
00422        *
00423        *  This function only makes sense for multisets; for set the result will
00424        *  either be 0 (not present) or 1 (present).
00425        */
00426       size_type
00427       count(const key_type& __x) const
00428       { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
00429 
00430       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00431       // 214.  set::find() missing const overload
00432       //@{
00433       /**
00434        *  @brief Tries to locate an element in a %set.
00435        *  @param  x  Element to be located.
00436        *  @return  Iterator pointing to sought-after element, or end() if not
00437        *           found.
00438        *
00439        *  This function takes a key and tries to locate the element with which
00440        *  the key matches.  If successful the function returns an iterator
00441        *  pointing to the sought after element.  If unsuccessful it returns the
00442        *  past-the-end ( @c end() ) iterator.
00443        */
00444       iterator
00445       find(const key_type& __x)
00446       { return _M_t.find(__x); }
00447 
00448       const_iterator
00449       find(const key_type& __x) const
00450       { return _M_t.find(__x); }
00451       //@}
00452 
00453       //@{
00454       /**
00455        *  @brief Finds the beginning of a subsequence matching given key.
00456        *  @param  x  Key to be located.
00457        *  @return  Iterator pointing to first element equal to or greater
00458        *           than key, or end().
00459        *
00460        *  This function returns the first element of a subsequence of elements
00461        *  that matches the given key.  If unsuccessful it returns an iterator
00462        *  pointing to the first element that has a greater value than given key
00463        *  or end() if no such element exists.
00464        */
00465       iterator
00466       lower_bound(const key_type& __x)
00467       { return _M_t.lower_bound(__x); }
00468 
00469       const_iterator
00470       lower_bound(const key_type& __x) const
00471       { return _M_t.lower_bound(__x); }
00472       //@}
00473 
00474       //@{
00475       /**
00476        *  @brief Finds the end of a subsequence matching given key.
00477        *  @param  x  Key to be located.
00478        *  @return Iterator pointing to the first element
00479        *          greater than key, or end().
00480        */
00481       iterator
00482       upper_bound(const key_type& __x)
00483       { return _M_t.upper_bound(__x); }
00484 
00485       const_iterator
00486       upper_bound(const key_type& __x) const
00487       { return _M_t.upper_bound(__x); }
00488       //@}
00489 
00490       //@{
00491       /**
00492        *  @brief Finds a subsequence matching given key.
00493        *  @param  x  Key to be located.
00494        *  @return  Pair of iterators that possibly points to the subsequence
00495        *           matching given key.
00496        *
00497        *  This function is equivalent to
00498        *  @code
00499        *    std::make_pair(c.lower_bound(val),
00500        *                   c.upper_bound(val))
00501        *  @endcode
00502        *  (but is faster than making the calls separately).
00503        *
00504        *  This function probably only makes sense for multisets.
00505        */
00506       std::pair<iterator,iterator>
00507       equal_range(const key_type& __x)
00508       { return _M_t.equal_range(__x); }
00509 
00510       std::pair<const_iterator,const_iterator>
00511       equal_range(const key_type& __x) const
00512       { return _M_t.equal_range(__x); }
00513       //@}
00514 
00515       template<class _K1, class _C1, class _A1>
00516         friend bool
00517         operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
00518 
00519       template<class _K1, class _C1, class _A1>
00520         friend bool
00521         operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
00522     };
00523 
00524 
00525   /**
00526    *  @brief  Set equality comparison.
00527    *  @param  x  A %set.
00528    *  @param  y  A %set of the same type as @a x.
00529    *  @return  True iff the size and elements of the sets are equal.
00530    *
00531    *  This is an equivalence relation.  It is linear in the size of the sets.
00532    *  Sets are considered equivalent if their sizes are equal, and if
00533    *  corresponding elements compare equal.
00534   */
00535   template<class _Key, class _Compare, class _Alloc>
00536     inline bool
00537     operator==(const set<_Key,_Compare,_Alloc>& __x,
00538            const set<_Key,_Compare,_Alloc>& __y)
00539     { return __x._M_t == __y._M_t; }
00540 
00541   /**
00542    *  @brief  Set ordering relation.
00543    *  @param  x  A %set.
00544    *  @param  y  A %set of the same type as @a x.
00545    *  @return  True iff @a x is lexicographically less than @a y.
00546    *
00547    *  This is a total ordering relation.  It is linear in the size of the
00548    *  maps.  The elements must be comparable with @c <.
00549    *
00550    *  See std::lexicographical_compare() for how the determination is made.
00551   */
00552   template<class _Key, class _Compare, class _Alloc>
00553     inline bool
00554     operator<(const set<_Key,_Compare,_Alloc>& __x,
00555           const set<_Key,_Compare,_Alloc>& __y)
00556     { return __x._M_t < __y._M_t; }
00557 
00558   ///  Returns !(x == y).
00559   template<class _Key, class _Compare, class _Alloc>
00560     inline bool
00561     operator!=(const set<_Key,_Compare,_Alloc>& __x,
00562            const set<_Key,_Compare,_Alloc>& __y)
00563     { return !(__x == __y); }
00564 
00565   ///  Returns y < x.
00566   template<class _Key, class _Compare, class _Alloc>
00567     inline bool
00568     operator>(const set<_Key,_Compare,_Alloc>& __x,
00569           const set<_Key,_Compare,_Alloc>& __y)
00570     { return __y < __x; }
00571 
00572   ///  Returns !(y < x)
00573   template<class _Key, class _Compare, class _Alloc>
00574     inline bool
00575     operator<=(const set<_Key,_Compare,_Alloc>& __x,
00576            const set<_Key,_Compare,_Alloc>& __y)
00577     { return !(__y < __x); }
00578 
00579   ///  Returns !(x < y)
00580   template<class _Key, class _Compare, class _Alloc>
00581     inline bool
00582     operator>=(const set<_Key,_Compare,_Alloc>& __x,
00583            const set<_Key,_Compare,_Alloc>& __y)
00584     { return !(__x < __y); }
00585 
00586   /// See std::set::swap().
00587   template<class _Key, class _Compare, class _Alloc>
00588     inline void
00589     swap(set<_Key,_Compare,_Alloc>& __x, set<_Key,_Compare,_Alloc>& __y)
00590     { __x.swap(__y); }
00591 
00592 } // namespace std
00593 
00594 #endif /* _SET_H */

Generated on Thu Jul 6 12:19:54 2006 for libstdc++ source by  doxygen 1.4.7