home *** CD-ROM | disk | FTP | other *** search
/ PC World 2008 April / PCWorld_2008-04_cd.bin / temacd / devc++ / devcpp-4.9.9.2_setup.exe / stl_set.h < prev    next >
C/C++ Source or Header  |  2005-01-29  |  21KB  |  594 lines
  1. // Set implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001, 2002, 2004 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 2, 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. // You should have received a copy of the GNU General Public License along
  17. // with this library; see the file COPYING.  If not, write to the Free
  18. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19. // USA.
  20.  
  21. // As a special exception, you may use this file as part of a free software
  22. // library without restriction.  Specifically, if other files instantiate
  23. // templates or use macros or inline functions from this file, or you compile
  24. // this file and link it with other files to produce an executable, this
  25. // file does not by itself cause the resulting executable to be covered by
  26. // the GNU General Public License.  This exception does not however
  27. // invalidate any other reasons why the executable file might be covered by
  28. // the GNU General Public License.
  29.  
  30. /*
  31.  *
  32.  * Copyright (c) 1994
  33.  * Hewlett-Packard Company
  34.  *
  35.  * Permission to use, copy, modify, distribute and sell this software
  36.  * and its documentation for any purpose is hereby granted without fee,
  37.  * provided that the above copyright notice appear in all copies and
  38.  * that both that copyright notice and this permission notice appear
  39.  * in supporting documentation.  Hewlett-Packard Company makes no
  40.  * representations about the suitability of this software for any
  41.  * purpose.  It is provided "as is" without express or implied warranty.
  42.  *
  43.  *
  44.  * Copyright (c) 1996,1997
  45.  * Silicon Graphics Computer Systems, Inc.
  46.  *
  47.  * Permission to use, copy, modify, distribute and sell this software
  48.  * and its documentation for any purpose is hereby granted without fee,
  49.  * provided that the above copyright notice appear in all copies and
  50.  * that both that copyright notice and this permission notice appear
  51.  * in supporting documentation.  Silicon Graphics makes no
  52.  * representations about the suitability of this software for any
  53.  * purpose.  It is provided "as is" without express or implied warranty.
  54.  */
  55.  
  56. /** @file stl_set.h
  57.  *  This is an internal header file, included by other library headers.
  58.  *  You should not attempt to use it directly.
  59.  */
  60.  
  61. #ifndef _SET_H
  62. #define _SET_H 1
  63.  
  64. #include <bits/concept_check.h>
  65.  
  66. namespace _GLIBCXX_STD
  67. {
  68.   // Forward declarations of operators < and ==, needed for friend declaration.
  69.   template<class _Key, class _Compare = less<_Key>,
  70.        class _Alloc = allocator<_Key> >
  71.     class set;
  72.  
  73.   template<class _Key, class _Compare, class _Alloc>
  74.     inline bool
  75.     operator==(const set<_Key,_Compare,_Alloc>& __x,
  76.            const set<_Key,_Compare,_Alloc>& __y);
  77.  
  78.   template<class _Key, class _Compare, class _Alloc>
  79.     inline bool
  80.     operator<(const set<_Key,_Compare,_Alloc>& __x,
  81.           const set<_Key,_Compare,_Alloc>& __y);
  82.  
  83.   /**
  84.    *  @brief A standard container made up of unique keys, which can be
  85.    *  retrieved in logarithmic time.
  86.    *
  87.    *  @ingroup Containers
  88.    *  @ingroup Assoc_containers
  89.    *
  90.    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
  91.    *  <a href="tables.html#66">reversible container</a>, and an
  92.    *  <a href="tables.html#69">associative container</a> (using unique keys).
  93.    *
  94.    *  Sets support bidirectional iterators.
  95.    *
  96.    *  @param  Key  Type of key objects.
  97.    *  @param  Compare  Comparison function object type, defaults to less<Key>.
  98.    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
  99.    *
  100.    *  @if maint
  101.    *  The private tree data is declared exactly the same way for set and
  102.    *  multiset; the distinction is made entirely in how the tree functions are
  103.    *  called (*_unique versus *_equal, same as the standard).
  104.    *  @endif
  105.   */
  106.   template<class _Key, class _Compare, class _Alloc>
  107.     class set
  108.     {
  109.       // concept requirements
  110.       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
  111.       __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
  112.                 _BinaryFunctionConcept)
  113.  
  114.     public:
  115.       // typedefs:
  116.       //@{
  117.       /// Public typedefs.
  118.       typedef _Key     key_type;
  119.       typedef _Key     value_type;
  120.       typedef _Compare key_compare;
  121.       typedef _Compare value_compare;
  122.       //@}
  123.  
  124.     private:
  125.       typedef _Rb_tree<key_type, value_type,
  126.                _Identity<value_type>, key_compare, _Alloc> _Rep_type;
  127.       _Rep_type _M_t;  // red-black tree representing set
  128.     public:
  129.       //@{
  130.       ///  Iterator-related typedefs.
  131.       typedef typename _Alloc::pointer pointer;
  132.       typedef typename _Alloc::const_pointer const_pointer;
  133.       typedef typename _Alloc::reference reference;
  134.       typedef typename _Alloc::const_reference const_reference;
  135.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  136.       // DR 103. set::iterator is required to be modifiable,
  137.       // but this allows modification of keys.
  138.       typedef typename _Rep_type::const_iterator iterator;
  139.       typedef typename _Rep_type::const_iterator const_iterator;
  140.       typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
  141.       typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  142.       typedef typename _Rep_type::size_type size_type;
  143.       typedef typename _Rep_type::difference_type difference_type;
  144.       typedef typename _Rep_type::allocator_type allocator_type;
  145.       //@}
  146.  
  147.       // allocation/deallocation
  148.       ///  Default constructor creates no elements.
  149.       set()
  150.       : _M_t(_Compare(), allocator_type()) {}
  151.  
  152.       /**
  153.        *  @brief  Default constructor creates no elements.
  154.        *
  155.        *  @param  comp  Comparator to use.
  156.        *  @param  a  Allocator to use.
  157.        */
  158.       explicit set(const _Compare& __comp,
  159.            const allocator_type& __a = allocator_type())
  160.       : _M_t(__comp, __a) {}
  161.  
  162.       /**
  163.        *  @brief  Builds a %set from a range.
  164.        *  @param  first  An input iterator.
  165.        *  @param  last  An input iterator.
  166.        *
  167.        *  Create a %set consisting of copies of the elements from [first,last).
  168.        *  This is linear in N if the range is already sorted, and NlogN
  169.        *  otherwise (where N is distance(first,last)).
  170.        */
  171.       template<class _InputIterator>
  172.         set(_InputIterator __first, _InputIterator __last)
  173.         : _M_t(_Compare(), allocator_type())
  174.         { _M_t.insert_unique(__first, __last); }
  175.  
  176.       /**
  177.        *  @brief  Builds a %set from a range.
  178.        *  @param  first  An input iterator.
  179.        *  @param  last  An input iterator.
  180.        *  @param  comp  A comparison functor.
  181.        *  @param  a  An allocator object.
  182.        *
  183.        *  Create a %set consisting of copies of the elements from [first,last).
  184.        *  This is linear in N if the range is already sorted, and NlogN
  185.        *  otherwise (where N is distance(first,last)).
  186.        */
  187.       template<class _InputIterator>
  188.         set(_InputIterator __first, _InputIterator __last,
  189.         const _Compare& __comp,
  190.         const allocator_type& __a = allocator_type())
  191.     : _M_t(__comp, __a)
  192.         { _M_t.insert_unique(__first, __last); }
  193.  
  194.       /**
  195.        *  @brief  Set copy constructor.
  196.        *  @param  x  A %set of identical element and allocator types.
  197.        *
  198.        *  The newly-created %set uses a copy of the allocation object used
  199.        *  by @a x.
  200.        */
  201.       set(const set<_Key,_Compare,_Alloc>& __x)
  202.       : _M_t(__x._M_t) { }
  203.  
  204.       /**
  205.        *  @brief  Set assignment operator.
  206.        *  @param  x  A %set of identical element and allocator types.
  207.        *
  208.        *  All the elements of @a x are copied, but unlike the copy constructor,
  209.        *  the allocator object is not copied.
  210.        */
  211.       set<_Key,_Compare,_Alloc>&
  212.       operator=(const set<_Key, _Compare, _Alloc>& __x)
  213.       {
  214.     _M_t = __x._M_t;
  215.     return *this;
  216.       }
  217.  
  218.       // accessors:
  219.  
  220.       ///  Returns the comparison object with which the %set was constructed.
  221.       key_compare
  222.       key_comp() const
  223.       { return _M_t.key_comp(); }
  224.       ///  Returns the comparison object with which the %set was constructed.
  225.       value_compare
  226.       value_comp() const
  227.       { return _M_t.key_comp(); }
  228.       ///  Returns the allocator object with which the %set was constructed.
  229.       allocator_type
  230.       get_allocator() const
  231.       { return _M_t.get_allocator(); }
  232.  
  233.       /**
  234.        *  Returns a read/write iterator that points to the first element in the
  235.        *  %set.  Iteration is done in ascending order according to the keys.
  236.        */
  237.       iterator
  238.       begin() const
  239.       { return _M_t.begin(); }
  240.  
  241.       /**
  242.        *  Returns a read/write iterator that points one past the last element in
  243.        *  the %set.  Iteration is done in ascending order according to the keys.
  244.        */
  245.       iterator
  246.       end() const
  247.       { return _M_t.end(); }
  248.  
  249.       /**
  250.        *  Returns a read/write reverse iterator that points to the last element
  251.        *  in the %set.  Iteration is done in descending order according to the
  252.        *  keys.
  253.        */
  254.       reverse_iterator
  255.       rbegin() const
  256.       { return _M_t.rbegin(); }
  257.  
  258.       /**
  259.        *  Returns a read-only (constant) reverse iterator that points to the
  260.        *  last pair in the %map.  Iteration is done in descending order
  261.        *  according to the keys.
  262.        */
  263.       reverse_iterator
  264.       rend() const
  265.       { return _M_t.rend(); }
  266.  
  267.       ///  Returns true if the %set is empty.
  268.       bool
  269.       empty() const
  270.       { return _M_t.empty(); }
  271.  
  272.       ///  Returns the size of the %set.
  273.       size_type
  274.       size() const
  275.       { return _M_t.size(); }
  276.  
  277.       ///  Returns the maximum size of the %set.
  278.       size_type
  279.       max_size() const
  280.       { return _M_t.max_size(); }
  281.  
  282.       /**
  283.        *  @brief  Swaps data with another %set.
  284.        *  @param  x  A %set of the same element and allocator types.
  285.        *
  286.        *  This exchanges the elements between two sets in constant time.
  287.        *  (It is only swapping a pointer, an integer, and an instance of
  288.        *  the @c Compare type (which itself is often stateless and empty), so it
  289.        *  should be quite fast.)
  290.        *  Note that the global std::swap() function is specialized such that
  291.        *  std::swap(s1,s2) will feed to this function.
  292.        */
  293.       void
  294.       swap(set<_Key,_Compare,_Alloc>& __x)
  295.       { _M_t.swap(__x._M_t); }
  296.  
  297.       // insert/erase
  298.       /**
  299.        *  @brief Attempts to insert an element into the %set.
  300.        *  @param  x  Element to be inserted.
  301.        *  @return  A pair, of which the first element is an iterator that points
  302.        *           to the possibly inserted element, and the second is a bool
  303.        *           that is true if the element was actually inserted.
  304.        *
  305.        *  This function attempts to insert an element into the %set.  A %set
  306.        *  relies on unique keys and thus an element is only inserted if it is
  307.        *  not already present in the %set.
  308.        *
  309.        *  Insertion requires logarithmic time.
  310.        */
  311.       pair<iterator,bool>
  312.       insert(const value_type& __x)
  313.       {
  314.     pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x);
  315.     return pair<iterator, bool>(__p.first, __p.second);
  316.       }
  317.  
  318.       /**
  319.        *  @brief Attempts to insert an element into the %set.
  320.        *  @param  position  An iterator that serves as a hint as to where the
  321.        *                    element should be inserted.
  322.        *  @param  x  Element to be inserted.
  323.        *  @return  An iterator that points to the element with key of @a x (may
  324.        *           or may not be the element passed in).
  325.        *
  326.        *  This function is not concerned about whether the insertion took place,
  327.        *  and thus does not return a boolean like the single-argument insert()
  328.        *  does.  Note that the first parameter is only a hint and can
  329.        *  potentially improve the performance of the insertion process.  A bad
  330.        *  hint would cause no gains in efficiency.
  331.        *
  332.        *  See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4
  333.        *  for more on "hinting".
  334.        *
  335.        *  Insertion requires logarithmic time (if the hint is not taken).
  336.        */
  337.       iterator
  338.       insert(iterator __position, const value_type& __x)
  339.       {
  340.     typedef typename _Rep_type::iterator _Rep_iterator;
  341.     return _M_t.insert_unique((_Rep_iterator&)__position, __x);
  342.       }
  343.  
  344.       /**
  345.        *  @brief A template function that attemps to insert a range of elements.
  346.        *  @param  first  Iterator pointing to the start of the range to be
  347.        *                 inserted.
  348.        *  @param  last  Iterator pointing to the end of the range.
  349.        *
  350.        *  Complexity similar to that of the range constructor.
  351.        */
  352.       template<class _InputIterator>
  353.       void
  354.       insert(_InputIterator __first, _InputIterator __last)
  355.       { _M_t.insert_unique(__first, __last); }
  356.  
  357.       /**
  358.        *  @brief Erases an element from a %set.
  359.        *  @param  position  An iterator pointing to the element to be erased.
  360.        *
  361.        *  This function erases an element, pointed to by the given iterator,
  362.        *  from a %set.  Note that this function only erases the element, and
  363.        *  that if the element is itself a pointer, the pointed-to memory is not
  364.        *  touched in any way.  Managing the pointer is the user's responsibilty.
  365.        */
  366.       void
  367.       erase(iterator __position)
  368.       {
  369.     typedef typename _Rep_type::iterator _Rep_iterator;
  370.     _M_t.erase((_Rep_iterator&)__position);
  371.       }
  372.  
  373.       /**
  374.        *  @brief Erases elements according to the provided key.
  375.        *  @param  x  Key of element to be erased.
  376.        *  @return  The number of elements erased.
  377.        *
  378.        *  This function erases all the elements located by the given key from
  379.        *  a %set.
  380.        *  Note that this function only erases the element, and that if
  381.        *  the element is itself a pointer, the pointed-to memory is not touched
  382.        *  in any way.  Managing the pointer is the user's responsibilty.
  383.        */
  384.       size_type
  385.       erase(const key_type& __x) { return _M_t.erase(__x); }
  386.  
  387.       /**
  388.        *  @brief Erases a [first,last) range of elements from a %set.
  389.        *  @param  first  Iterator pointing to the start of the range to be
  390.        *                 erased.
  391.        *  @param  last  Iterator pointing to the end of the range to be erased.
  392.        *
  393.        *  This function erases a sequence of elements from a %set.
  394.        *  Note that this function only erases the element, and that if
  395.        *  the element is itself a pointer, the pointed-to memory is not touched
  396.        *  in any way.  Managing the pointer is the user's responsibilty.
  397.        */
  398.       void
  399.       erase(iterator __first, iterator __last)
  400.       {
  401.     typedef typename _Rep_type::iterator _Rep_iterator;
  402.     _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last);
  403.       }
  404.  
  405.       /**
  406.        *  Erases all elements in a %set.  Note that this function only erases
  407.        *  the elements, and that if the elements themselves are pointers, the
  408.        *  pointed-to memory is not touched in any way.  Managing the pointer is
  409.        *  the user's responsibilty.
  410.        */
  411.       void
  412.       clear()
  413.       { _M_t.clear(); }
  414.  
  415.       // set operations:
  416.  
  417.       /**
  418.        *  @brief  Finds the number of elements.
  419.        *  @param  x  Element to located.
  420.        *  @return  Number of elements with specified key.
  421.        *
  422.        *  This function only makes sense for multisets; for set the result will
  423.        *  either be 0 (not present) or 1 (present).
  424.        */
  425.       size_type
  426.       count(const key_type& __x) const
  427.       { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
  428.  
  429.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  430.       // 214.  set::find() missing const overload
  431.       //@{
  432.       /**
  433.        *  @brief Tries to locate an element in a %set.
  434.        *  @param  x  Element to be located.
  435.        *  @return  Iterator pointing to sought-after element, or end() if not
  436.        *           found.
  437.        *
  438.        *  This function takes a key and tries to locate the element with which
  439.        *  the key matches.  If successful the function returns an iterator
  440.        *  pointing to the sought after element.  If unsuccessful it returns the
  441.        *  past-the-end ( @c end() ) iterator.
  442.        */
  443.       iterator
  444.       find(const key_type& __x)
  445.       { return _M_t.find(__x); }
  446.  
  447.       const_iterator
  448.       find(const key_type& __x) const
  449.       { return _M_t.find(__x); }
  450.       //@}
  451.  
  452.       //@{
  453.       /**
  454.        *  @brief Finds the beginning of a subsequence matching given key.
  455.        *  @param  x  Key to be located.
  456.        *  @return  Iterator pointing to first element equal to or greater
  457.        *           than key, or end().
  458.        *
  459.        *  This function returns the first element of a subsequence of elements
  460.        *  that matches the given key.  If unsuccessful it returns an iterator
  461.        *  pointing to the first element that has a greater value than given key
  462.        *  or end() if no such element exists.
  463.        */
  464.       iterator
  465.       lower_bound(const key_type& __x)
  466.       { return _M_t.lower_bound(__x); }
  467.  
  468.       const_iterator
  469.       lower_bound(const key_type& __x) const
  470.       { return _M_t.lower_bound(__x); }
  471.       //@}
  472.  
  473.       //@{
  474.       /**
  475.        *  @brief Finds the end of a subsequence matching given key.
  476.        *  @param  x  Key to be located.
  477.        *  @return Iterator pointing to the first element
  478.        *          greater than key, or end().
  479.        */
  480.       iterator
  481.       upper_bound(const key_type& __x)
  482.       { return _M_t.upper_bound(__x); }
  483.  
  484.       const_iterator
  485.       upper_bound(const key_type& __x) const
  486.       { return _M_t.upper_bound(__x); }
  487.       //@}
  488.  
  489.       //@{
  490.       /**
  491.        *  @brief Finds a subsequence matching given key.
  492.        *  @param  x  Key to be located.
  493.        *  @return  Pair of iterators that possibly points to the subsequence
  494.        *           matching given key.
  495.        *
  496.        *  This function is equivalent to
  497.        *  @code
  498.        *    std::make_pair(c.lower_bound(val),
  499.        *                   c.upper_bound(val))
  500.        *  @endcode
  501.        *  (but is faster than making the calls separately).
  502.        *
  503.        *  This function probably only makes sense for multisets.
  504.        */
  505.       pair<iterator,iterator>
  506.       equal_range(const key_type& __x)
  507.       { return _M_t.equal_range(__x); }
  508.  
  509.       pair<const_iterator,const_iterator>
  510.       equal_range(const key_type& __x) const
  511.       { return _M_t.equal_range(__x); }
  512.       //@}
  513.  
  514.       template<class _K1, class _C1, class _A1>
  515.         friend bool
  516.         operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
  517.  
  518.       template<class _K1, class _C1, class _A1>
  519.         friend bool
  520.         operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
  521.     };
  522.  
  523.  
  524.   /**
  525.    *  @brief  Set equality comparison.
  526.    *  @param  x  A %set.
  527.    *  @param  y  A %set of the same type as @a x.
  528.    *  @return  True iff the size and elements of the sets are equal.
  529.    *
  530.    *  This is an equivalence relation.  It is linear in the size of the sets.
  531.    *  Sets are considered equivalent if their sizes are equal, and if
  532.    *  corresponding elements compare equal.
  533.   */
  534.   template<class _Key, class _Compare, class _Alloc>
  535.     inline bool
  536.     operator==(const set<_Key,_Compare,_Alloc>& __x,
  537.            const set<_Key,_Compare,_Alloc>& __y)
  538.     { return __x._M_t == __y._M_t; }
  539.  
  540.   /**
  541.    *  @brief  Set ordering relation.
  542.    *  @param  x  A %set.
  543.    *  @param  y  A %set of the same type as @a x.
  544.    *  @return  True iff @a x is lexicographically less than @a y.
  545.    *
  546.    *  This is a total ordering relation.  It is linear in the size of the
  547.    *  maps.  The elements must be comparable with @c <.
  548.    *
  549.    *  See std::lexicographical_compare() for how the determination is made.
  550.   */
  551.   template<class _Key, class _Compare, class _Alloc>
  552.     inline bool
  553.     operator<(const set<_Key,_Compare,_Alloc>& __x,
  554.           const set<_Key,_Compare,_Alloc>& __y)
  555.     { return __x._M_t < __y._M_t; }
  556.  
  557.   ///  Returns !(x == y).
  558.   template<class _Key, class _Compare, class _Alloc>
  559.     inline bool
  560.     operator!=(const set<_Key,_Compare,_Alloc>& __x,
  561.            const set<_Key,_Compare,_Alloc>& __y)
  562.     { return !(__x == __y); }
  563.  
  564.   ///  Returns y < x.
  565.   template<class _Key, class _Compare, class _Alloc>
  566.     inline bool
  567.     operator>(const set<_Key,_Compare,_Alloc>& __x,
  568.           const set<_Key,_Compare,_Alloc>& __y)
  569.     { return __y < __x; }
  570.  
  571.   ///  Returns !(y < x)
  572.   template<class _Key, class _Compare, class _Alloc>
  573.     inline bool
  574.     operator<=(const set<_Key,_Compare,_Alloc>& __x,
  575.            const set<_Key,_Compare,_Alloc>& __y)
  576.     { return !(__y < __x); }
  577.  
  578.   ///  Returns !(x < y)
  579.   template<class _Key, class _Compare, class _Alloc>
  580.     inline bool
  581.     operator>=(const set<_Key,_Compare,_Alloc>& __x,
  582.            const set<_Key,_Compare,_Alloc>& __y)
  583.     { return !(__x < __y); }
  584.  
  585.   /// See std::set::swap().
  586.   template<class _Key, class _Compare, class _Alloc>
  587.     inline void
  588.     swap(set<_Key,_Compare,_Alloc>& __x, set<_Key,_Compare,_Alloc>& __y)
  589.     { __x.swap(__y); }
  590.  
  591. } // namespace std
  592.  
  593. #endif /* _SET_H */
  594.