home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / multiset.h < prev    next >
C/C++ Source or Header  |  2005-01-29  |  10KB  |  321 lines
  1. // Debugging multiset implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2003, 2004
  4. // 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 2, 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. // You should have received a copy of the GNU General Public License along
  18. // with this library; see the file COPYING.  If not, write to the Free
  19. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  20. // USA.
  21.  
  22. // As a special exception, you may use this file as part of a free software
  23. // library without restriction.  Specifically, if other files instantiate
  24. // templates or use macros or inline functions from this file, or you compile
  25. // this file and link it with other files to produce an executable, this
  26. // file does not by itself cause the resulting executable to be covered by
  27. // the GNU General Public License.  This exception does not however
  28. // invalidate any other reasons why the executable file might be covered by
  29. // the GNU General Public License.
  30.  
  31. #ifndef _GLIBCXX_DEBUG_MULTISET_H
  32. #define _GLIBCXX_DEBUG_MULTISET_H 1
  33.  
  34. #include <debug/safe_sequence.h>
  35. #include <debug/safe_iterator.h>
  36. #include <utility>
  37.  
  38. namespace __gnu_debug_def
  39. {
  40.   template<typename _Key, typename _Compare = std::less<_Key>,
  41.        typename _Allocator = std::allocator<_Key> >
  42.     class multiset
  43.     : public _GLIBCXX_STD::multiset<_Key, _Compare, _Allocator>,
  44.       public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
  45.     {
  46.       typedef _GLIBCXX_STD::multiset<_Key, _Compare, _Allocator> _Base;
  47.       typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;
  48.  
  49.     public:
  50.       // types:
  51.       typedef _Key                     key_type;
  52.       typedef _Key                     value_type;
  53.       typedef _Compare                     key_compare;
  54.       typedef _Compare                     value_compare;
  55.       typedef _Allocator                 allocator_type;
  56.       typedef typename _Allocator::reference         reference;
  57.       typedef typename _Allocator::const_reference   const_reference;
  58.  
  59.       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multiset>
  60.       iterator;
  61.       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
  62.                       multiset> const_iterator;
  63.  
  64.       typedef typename _Base::size_type              size_type;
  65.       typedef typename _Base::difference_type        difference_type;
  66.       typedef typename _Allocator::pointer           pointer;
  67.       typedef typename _Allocator::const_pointer     const_pointer;
  68.       typedef std::reverse_iterator<iterator>        reverse_iterator;
  69.       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
  70.  
  71.       // 23.3.3.1 construct/copy/destroy:
  72.       explicit multiset(const _Compare& __comp = _Compare(),
  73.             const _Allocator& __a = _Allocator())
  74.       : _Base(__comp, __a) { }
  75.  
  76.       template<typename _InputIterator>
  77.         multiset(_InputIterator __first, _InputIterator __last,
  78.          const _Compare& __comp = _Compare(),
  79.          const _Allocator& __a = _Allocator())
  80.     : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
  81.         __comp, __a) { }
  82.  
  83.       multiset(const multiset<_Key,_Compare,_Allocator>& __x)
  84.       : _Base(__x), _Safe_base() { }
  85.  
  86.       multiset(const _Base& __x) : _Base(__x), _Safe_base() { }
  87.  
  88.       ~multiset() { }
  89.  
  90.       multiset<_Key,_Compare,_Allocator>&
  91.       operator=(const multiset<_Key,_Compare,_Allocator>& __x)
  92.       {
  93.     *static_cast<_Base*>(this) = __x;
  94.     this->_M_invalidate_all();
  95.     return *this;
  96.       }
  97.  
  98.       using _Base::get_allocator;
  99.  
  100.       // iterators:
  101.       iterator
  102.       begin()
  103.       { return iterator(_Base::begin(), this); }
  104.  
  105.       const_iterator
  106.       begin() const
  107.       { return const_iterator(_Base::begin(), this); }
  108.  
  109.       iterator
  110.       end()
  111.       { return iterator(_Base::end(), this); }
  112.  
  113.       const_iterator
  114.       end() const
  115.       { return const_iterator(_Base::end(), this); }
  116.  
  117.       reverse_iterator
  118.       rbegin()
  119.       { return reverse_iterator(end()); }
  120.  
  121.       const_reverse_iterator
  122.       rbegin() const
  123.       { return const_reverse_iterator(end()); }
  124.  
  125.       reverse_iterator
  126.       rend()
  127.       { return reverse_iterator(begin()); }
  128.  
  129.       const_reverse_iterator
  130.       rend() const
  131.       { return const_reverse_iterator(begin()); }
  132.  
  133.       // capacity:
  134.       using _Base::empty;
  135.       using _Base::size;
  136.       using _Base::max_size;
  137.  
  138.       // modifiers:
  139.       iterator
  140.       insert(const value_type& __x)
  141.       { return iterator(_Base::insert(__x), this); }
  142.  
  143.       iterator
  144.       insert(iterator __position, const value_type& __x)
  145.       {
  146.     __glibcxx_check_insert(__position);
  147.     return iterator(_Base::insert(__position.base(), __x), this);
  148.       }
  149.  
  150.       template<typename _InputIterator>
  151.       void
  152.       insert(_InputIterator __first, _InputIterator __last)
  153.       {
  154.     __glibcxx_check_valid_range(__first, __last);
  155.     _Base::insert(__first, __last);
  156.       }
  157.  
  158.       void
  159.       erase(iterator __position)
  160.       {
  161.     __glibcxx_check_erase(__position);
  162.     __position._M_invalidate();
  163.     _Base::erase(__position.base());
  164.       }
  165.  
  166.       size_type
  167.       erase(const key_type& __x)
  168.       {
  169.     std::pair<iterator, iterator> __victims = this->equal_range(__x);
  170.     size_type __count = 0;
  171.     while (__victims.first != __victims.second)
  172.     {
  173.       iterator __victim = __victims.first++;
  174.       __victim._M_invalidate();
  175.       _Base::erase(__victim.base());
  176.       ++__count;
  177.     }
  178.     return __count;
  179.       }
  180.  
  181.       void
  182.       erase(iterator __first, iterator __last)
  183.       {
  184.     // _GLIBCXX_RESOLVE_LIB_DEFECTS
  185.     // 151. can't currently clear() empty container
  186.     __glibcxx_check_erase_range(__first, __last);
  187.     while (__first != __last)
  188.     this->erase(__first++);
  189.       }
  190.  
  191.       void
  192.       swap(multiset<_Key,_Compare,_Allocator>& __x)
  193.       {
  194.     _Base::swap(__x);
  195.     this->_M_swap(__x);
  196.       }
  197.  
  198.       void
  199.       clear()
  200.       { this->erase(begin(), end()); }
  201.  
  202.       // observers:
  203.       using _Base::key_comp;
  204.       using _Base::value_comp;
  205.  
  206.       // multiset operations:
  207.       iterator
  208.       find(const key_type& __x)
  209.       { return iterator(_Base::find(__x), this); }
  210.  
  211.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  212.       // 214. set::find() missing const overload
  213.       const_iterator
  214.       find(const key_type& __x) const
  215.       { return const_iterator(_Base::find(__x), this); }
  216.  
  217.       using _Base::count;
  218.  
  219.       iterator
  220.       lower_bound(const key_type& __x)
  221.       { return iterator(_Base::lower_bound(__x), this); }
  222.  
  223.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  224.       // 214. set::find() missing const overload
  225.       const_iterator
  226.       lower_bound(const key_type& __x) const
  227.       { return const_iterator(_Base::lower_bound(__x), this); }
  228.  
  229.       iterator
  230.       upper_bound(const key_type& __x)
  231.       { return iterator(_Base::upper_bound(__x), this); }
  232.  
  233.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  234.       // 214. set::find() missing const overload
  235.       const_iterator
  236.       upper_bound(const key_type& __x) const
  237.       { return const_iterator(_Base::upper_bound(__x), this); }
  238.  
  239.       std::pair<iterator,iterator>
  240.       equal_range(const key_type& __x)
  241.       {
  242.     typedef typename _Base::iterator _Base_iterator;
  243.     std::pair<_Base_iterator, _Base_iterator> __res =
  244.         _Base::equal_range(__x);
  245.     return std::make_pair(iterator(__res.first, this),
  246.                   iterator(__res.second, this));
  247.       }
  248.  
  249.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  250.       // 214. set::find() missing const overload
  251.       std::pair<const_iterator,const_iterator>
  252.       equal_range(const key_type& __x) const
  253.       {
  254.     typedef typename _Base::const_iterator _Base_iterator;
  255.     std::pair<_Base_iterator, _Base_iterator> __res =
  256.         _Base::equal_range(__x);
  257.     return std::make_pair(const_iterator(__res.first, this),
  258.                   const_iterator(__res.second, this));
  259.       }
  260.  
  261.       _Base&
  262.       _M_base() { return *this; }
  263.  
  264.       const _Base&
  265.       _M_base() const { return *this; }
  266.  
  267.     private:
  268.       void
  269.       _M_invalidate_all()
  270.       {
  271.     typedef typename _Base::const_iterator _Base_const_iterator;
  272.     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
  273.     this->_M_invalidate_if(_Not_equal(_M_base().end()));
  274.       }
  275.     };
  276.  
  277.   template<typename _Key, typename _Compare, typename _Allocator>
  278.     inline bool
  279.     operator==(const multiset<_Key,_Compare,_Allocator>& __lhs,
  280.            const multiset<_Key,_Compare,_Allocator>& __rhs)
  281.     { return __lhs._M_base() == __rhs._M_base(); }
  282.  
  283.   template<typename _Key, typename _Compare, typename _Allocator>
  284.     inline bool
  285.     operator!=(const multiset<_Key,_Compare,_Allocator>& __lhs,
  286.            const multiset<_Key,_Compare,_Allocator>& __rhs)
  287.     { return __lhs._M_base() != __rhs._M_base(); }
  288.  
  289.   template<typename _Key, typename _Compare, typename _Allocator>
  290.     inline bool
  291.     operator<(const multiset<_Key,_Compare,_Allocator>& __lhs,
  292.           const multiset<_Key,_Compare,_Allocator>& __rhs)
  293.     { return __lhs._M_base() < __rhs._M_base(); }
  294.  
  295.   template<typename _Key, typename _Compare, typename _Allocator>
  296.     inline bool
  297.     operator<=(const multiset<_Key,_Compare,_Allocator>& __lhs,
  298.            const multiset<_Key,_Compare,_Allocator>& __rhs)
  299.     { return __lhs._M_base() <= __rhs._M_base(); }
  300.  
  301.   template<typename _Key, typename _Compare, typename _Allocator>
  302.     inline bool
  303.     operator>=(const multiset<_Key,_Compare,_Allocator>& __lhs,
  304.            const multiset<_Key,_Compare,_Allocator>& __rhs)
  305.     { return __lhs._M_base() >= __rhs._M_base(); }
  306.  
  307.   template<typename _Key, typename _Compare, typename _Allocator>
  308.     inline bool
  309.     operator>(const multiset<_Key,_Compare,_Allocator>& __lhs,
  310.           const multiset<_Key,_Compare,_Allocator>& __rhs)
  311.     { return __lhs._M_base() > __rhs._M_base(); }
  312.  
  313.   template<typename _Key, typename _Compare, typename _Allocator>
  314.     void
  315.     swap(multiset<_Key,_Compare,_Allocator>& __x,
  316.      multiset<_Key,_Compare,_Allocator>& __y)
  317.     { return __x.swap(__y); }
  318. } // namespace __gnu_debug_def
  319.  
  320. #endif
  321.