[thirdparty/gcc.git] / libstdc++-v3 / include / debug / unordered_set

// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-

// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file debug/unordered_set
 *  This file is a GNU debug extension to the Standard C++ Library.
 */

#ifndef _GLIBCXX_DEBUG_UNORDERED_SET
#define _GLIBCXX_DEBUG_UNORDERED_SET 1

#ifdef __GXX_EXPERIMENTAL_CXX0X__
# include <unordered_set>
#else
# include <c++0x_warning.h>
#endif

#include <debug/safe_sequence.h>
#include <debug/safe_iterator.h>
#include <initializer_list>

namespace std
{
namespace __debug
{
  template<typename _Value,
	   typename _Hash = std::hash<_Value>,
	   typename _Pred = std::equal_to<_Value>,
	   typename _Alloc = std::allocator<_Value> >
    class unordered_set
    : public _GLIBCXX_STD_D::unordered_set<_Value, _Hash, _Pred, _Alloc>,
      public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
						       _Pred, _Alloc> >
    {
      typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash,
					    _Pred, _Alloc> _Base;
      typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;

    public:
      typedef typename _Base::size_type       size_type;
      typedef typename _Base::hasher          hasher;
      typedef typename _Base::key_equal       key_equal;
      typedef typename _Base::allocator_type  allocator_type;

      typedef typename _Base::key_type        key_type;
      typedef typename _Base::value_type      value_type;

      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
					  unordered_set> iterator;
      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
					  unordered_set> const_iterator;

      explicit
      unordered_set(size_type __n = 10,
		    const hasher& __hf = hasher(),
		    const key_equal& __eql = key_equal(),
		    const allocator_type& __a = allocator_type())
      : _Base(__n, __hf, __eql, __a) { }

      template<typename _InputIterator>
        unordered_set(_InputIterator __f, _InputIterator __l, 
		      size_type __n = 10,
		      const hasher& __hf = hasher(), 
		      const key_equal& __eql = key_equal(), 
		      const allocator_type& __a = allocator_type())
	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
		__hf, __eql, __a), _Safe_base() { }

      unordered_set(const unordered_set& __x) 
      : _Base(__x), _Safe_base() { }

      unordered_set(const _Base& __x) 
      : _Base(__x), _Safe_base() { }

      unordered_set(unordered_set&& __x) 
      : _Base(std::forward<unordered_set>(__x)), _Safe_base() { }

      unordered_set(initializer_list<value_type> __l,
		    size_type __n = 10,
		    const hasher& __hf = hasher(),
		    const key_equal& __eql = key_equal(),
		    const allocator_type& __a = allocator_type())
      : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }

      unordered_set&
      operator=(const unordered_set& __x)
      {
	*static_cast<_Base*>(this) = __x;
	this->_M_invalidate_all();
	return *this;
      }

      unordered_set&
      operator=(unordered_set&& __x)
      {
        // NB: DR 675.
	clear();
	swap(__x);
	return *this;
      }

      unordered_set&
      operator=(initializer_list<value_type> __l)
      {
	this->clear();
	this->insert(__l);
	return *this;
      }

      void
      swap(unordered_set&& __x)
      {
	_Base::swap(__x);
	_Safe_base::_M_swap(__x);
      }

      void
      clear()
      {
	_Base::clear();
	this->_M_invalidate_all();
      }

      iterator 
      begin()
      { return iterator(_Base::begin(), this); }

      const_iterator
      begin() const
      { return const_iterator(_Base::begin(), this); }

      iterator
      end()
      { return iterator(_Base::end(), this); }

      const_iterator
      end() const
      { return const_iterator(_Base::end(), this); }

      const_iterator
      cbegin() const
      { return const_iterator(_Base::begin(), this); }

      const_iterator
      cend() const
      { return const_iterator(_Base::end(), this); }

      // local versions
      using _Base::begin;
      using _Base::end;
      using _Base::cbegin;
      using _Base::cend;

      std::pair<iterator, bool>
      insert(const value_type& __obj)
      {
	typedef std::pair<typename _Base::iterator, bool> __pair_type;
	__pair_type __res = _Base::insert(__obj);
	return std::make_pair(iterator(__res.first, this), __res.second);
      }

      iterator
      insert(iterator, const value_type& __obj)
      {
	typedef std::pair<typename _Base::iterator, bool> __pair_type;
	__pair_type __res = _Base::insert(__obj);
	return iterator(__res.first, this);
      }

      const_iterator
      insert(const_iterator, const value_type& __obj)
      {
	typedef std::pair<typename _Base::iterator, bool> __pair_type;
	__pair_type __res = _Base::insert(__obj);
	return const_iterator(__res.first, this);
      }

      void
      insert(std::initializer_list<value_type> __l)
      { _Base::insert(__l); }

      template<typename _InputIterator>
        void
        insert(_InputIterator __first, _InputIterator __last)
        {
	  __glibcxx_check_valid_range(__first, __last);
	  _Base::insert(__first, __last);
	}

      iterator
      find(const key_type& __key)
      { return iterator(_Base::find(__key), this); }

      const_iterator
      find(const key_type& __key) const
      { return const_iterator(_Base::find(__key), this); }

      std::pair<iterator, iterator>
      equal_range(const key_type& __key)
      {
	typedef typename _Base::iterator _Base_iterator;
	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
	__pair_type __res = _Base::equal_range(__key);
	return std::make_pair(iterator(__res.first, this),
			      iterator(__res.second, this));
      }

      std::pair<const_iterator, const_iterator>
      equal_range(const key_type& __key) const
      {
	typedef typename _Base::const_iterator _Base_iterator;
	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
	__pair_type __res = _Base::equal_range(__key);
	return std::make_pair(const_iterator(__res.first, this),
			      const_iterator(__res.second, this));
      }

      size_type
      erase(const key_type& __key)
      {
	size_type __ret(0);
	iterator __victim(_Base::find(__key), this);
	if (__victim != end())
	  {
	    this->erase(__victim);
	    __ret = 1;
	  }
	return __ret;
      }

      iterator
      erase(iterator __it)
      {
	__glibcxx_check_erase(__it);
	__it._M_invalidate();
	return iterator(_Base::erase(__it.base()), this);
      }

      const_iterator
      erase(const_iterator __it)
      {
	__glibcxx_check_erase(__it);
	__it._M_invalidate();
	return const_iterator(_Base::erase(__it.base()), this);
      }

      iterator
      erase(iterator __first, iterator __last)
      {
	__glibcxx_check_erase_range(__first, __last);
	for (iterator __tmp = __first; __tmp != __last;)
	{
	  iterator __victim = __tmp++;
	  __victim._M_invalidate();
	}
	return iterator(_Base::erase(__first.base(),
				     __last.base()), this);
      }

      const_iterator
      erase(const_iterator __first, const_iterator __last)
      {
	__glibcxx_check_erase_range(__first, __last);
	for (const_iterator __tmp = __first; __tmp != __last;)
	{
	  const_iterator __victim = __tmp++;
	  __victim._M_invalidate();
	}
	return const_iterator(_Base::erase(__first.base(),
					   __last.base()), this);
      }

      _Base&
      _M_base() { return *this; }

      const _Base&
      _M_base() const { return *this; }

    private:
      void
      _M_invalidate_all()
      {
	typedef typename _Base::const_iterator _Base_const_iterator;
	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
	this->_M_invalidate_if(_Not_equal(_M_base().end()));
      }
    };

  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
    inline void
    swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
	 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__y); }

  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
    inline void
    swap(unordered_set<_Value, _Hash, _Pred, _Alloc>&& __x,
	 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__y); }

  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
    inline void
    swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
	 unordered_set<_Value, _Hash, _Pred, _Alloc>&& __y)
    { __x.swap(__y); }


  template<typename _Value,
	   typename _Hash = std::hash<_Value>,
	   typename _Pred = std::equal_to<_Value>,
	   typename _Alloc = std::allocator<_Value> >
    class unordered_multiset
    : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
      public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
							    _Pred, _Alloc> >
    {
      typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash,
						 _Pred, _Alloc> _Base;
      typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;

    public:
      typedef typename _Base::size_type       size_type;
      typedef typename _Base::hasher          hasher;
      typedef typename _Base::key_equal       key_equal;
      typedef typename _Base::allocator_type  allocator_type;

      typedef typename _Base::key_type        key_type;
      typedef typename _Base::value_type      value_type;

      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
					  unordered_multiset> iterator;
      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
					  unordered_multiset> const_iterator;

      explicit
      unordered_multiset(size_type __n = 10,
			 const hasher& __hf = hasher(),
			 const key_equal& __eql = key_equal(),
			 const allocator_type& __a = allocator_type())
      : _Base(__n, __hf, __eql, __a) { }

      template<typename _InputIterator>
        unordered_multiset(_InputIterator __f, _InputIterator __l, 
			   size_type __n = 10,
			   const hasher& __hf = hasher(), 
			   const key_equal& __eql = key_equal(), 
			   const allocator_type& __a = allocator_type())
	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
		__hf, __eql, __a), _Safe_base() { }

      unordered_multiset(const unordered_multiset& __x) 
      : _Base(__x), _Safe_base() { }

      unordered_multiset(const _Base& __x) 
      : _Base(__x), _Safe_base() { }

      unordered_multiset(unordered_multiset&& __x) 
      : _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { }

      unordered_multiset(initializer_list<value_type> __l,
			 size_type __n = 10,
			 const hasher& __hf = hasher(),
			 const key_equal& __eql = key_equal(),
			 const allocator_type& __a = allocator_type())
      : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }

      unordered_multiset&
      operator=(const unordered_multiset& __x)
      {
	*static_cast<_Base*>(this) = __x;
	this->_M_invalidate_all();
	return *this;
      }

      unordered_multiset&
      operator=(unordered_multiset&& __x)
      {
        // NB: DR 675.
	clear();
	swap(__x);
	return *this;
      }

      unordered_multiset&
      operator=(initializer_list<value_type> __l)
      {
	this->clear();
	this->insert(__l);
	return *this;
      }

      void
      swap(unordered_multiset&& __x)
      {
	_Base::swap(__x);
	_Safe_base::_M_swap(__x);
      }

      void
      clear()
      {
	_Base::clear();
	this->_M_invalidate_all();
      }

      iterator
      begin()
      { return iterator(_Base::begin(), this); }

      const_iterator
      begin() const
      { return const_iterator(_Base::begin(), this); }

      iterator
      end()
      { return iterator(_Base::end(), this); }

      const_iterator
      end() const
      { return const_iterator(_Base::end(), this); }

      const_iterator
      cbegin() const
      { return const_iterator(_Base::begin(), this); }

      const_iterator
      cend() const
      { return const_iterator(_Base::end(), this); }

      // local versions
      using _Base::begin;
      using _Base::end;
      using _Base::cbegin;
      using _Base::cend;

      iterator
      insert(const value_type& __obj)
      { return iterator(_Base::insert(__obj), this); }

      iterator
      insert(iterator, const value_type& __obj)
      { return iterator(_Base::insert(__obj), this); }

      const_iterator
      insert(const_iterator, const value_type& __obj)
      { return const_iterator(_Base::insert(__obj), this); }

      void
      insert(std::initializer_list<value_type> __l)
      { _Base::insert(__l); }

      template<typename _InputIterator>
        void
        insert(_InputIterator __first, _InputIterator __last)
        {
	  __glibcxx_check_valid_range(__first, __last);
	  _Base::insert(__first, __last);
	}

      iterator
      find(const key_type& __key)
      { return iterator(_Base::find(__key), this); }

      const_iterator
      find(const key_type& __key) const
      { return const_iterator(_Base::find(__key), this); }

      std::pair<iterator, iterator>
      equal_range(const key_type& __key)
      {
	typedef typename _Base::iterator _Base_iterator;
	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
	__pair_type __res = _Base::equal_range(__key);
	return std::make_pair(iterator(__res.first, this),
			      iterator(__res.second, this));
      }

      std::pair<const_iterator, const_iterator>
      equal_range(const key_type& __key) const
      {
	typedef typename _Base::const_iterator _Base_iterator;
	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
	__pair_type __res = _Base::equal_range(__key);
	return std::make_pair(const_iterator(__res.first, this),
			      const_iterator(__res.second, this));
      }

      size_type
      erase(const key_type& __key)
      {
	size_type __ret(0);
	iterator __victim(_Base::find(__key), this);
	if (__victim != end())
	  {
	    this->erase(__victim);
	    __ret = 1;
	  }
	return __ret;
      }

      iterator
      erase(iterator __it)
      {
	__glibcxx_check_erase(__it);
	__it._M_invalidate();
	return iterator(_Base::erase(__it.base()), this);
      }

      const_iterator
      erase(const_iterator __it)
      {
	__glibcxx_check_erase(__it);
	__it._M_invalidate();
	return const_iterator(_Base::erase(__it.base()), this);
      }

      iterator
      erase(iterator __first, iterator __last)
      {
	__glibcxx_check_erase_range(__first, __last);
	for (iterator __tmp = __first; __tmp != __last;)
	{
	  iterator __victim = __tmp++;
	  __victim._M_invalidate();
	}
	return iterator(_Base::erase(__first.base(),
				     __last.base()), this);
      }

      const_iterator
      erase(const_iterator __first, const_iterator __last)
      {
	__glibcxx_check_erase_range(__first, __last);
	for (const_iterator __tmp = __first; __tmp != __last;)
	{
	  const_iterator __victim = __tmp++;
	  __victim._M_invalidate();
	}
	return const_iterator(_Base::erase(__first.base(),
					   __last.base()), this);
      }

      _Base&
      _M_base() { return *this; }

      const _Base&
      _M_base() const { return *this; }

    private:
      void
      _M_invalidate_all()
      {
	typedef typename _Base::const_iterator _Base_const_iterator;
	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
	this->_M_invalidate_if(_Not_equal(_M_base().end()));
      }
    };

  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
    inline void
    swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
	 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__y); }

  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
    inline void
    swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>&& __x,
	 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__y); }

  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
    inline void
    swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
	 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&& __y)
    { __x.swap(__y); }

} // namespace __debug
} // namespace std

#endif
Commit	Line	Data
e63637ea BK	1	// Debugging unordered_set/unordered_multiset implementation -- C++ --
e63637ea BK	2
ced3cb9f	3	// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
e63637ea BK	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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
	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	/** @file debug/unordered_set
	32	* This file is a GNU debug extension to the Standard C++ Library.
	33	*/
	34
	35	#ifndef _GLIBCXX_DEBUG_UNORDERED_SET
	36	#define _GLIBCXX_DEBUG_UNORDERED_SET 1
	37
	38	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	39	# include <unordered_set>
	40	#else
	41	# include <c++0x_warning.h>
	42	#endif
	43
ced3cb9f	44	#include <debug/safe_sequence.h>
e63637ea	45	#include <debug/safe_iterator.h>
ced3cb9f	46	#include <initializer_list>
e63637ea BK	47
	48	namespace std
	49	{
	50	namespace __debug
	51	{
	52	template<typename _Value,
ced3cb9f	53	typename _Hash = std::hash<_Value>,
e63637ea	54	typename _Pred = std::equal_to<_Value>,
ced3cb9f	55	typename _Alloc = std::allocator<_Value> >
e63637ea	56	class unordered_set
ced3cb9f PC	57	: public _GLIBCXX_STD_D::unordered_set<_Value, _Hash, _Pred, _Alloc>,
	58	public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
	59	_Pred, _Alloc> >
e63637ea	60	{
ced3cb9f PC	61	typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash,
ced3cb9f PC	62	_Pred, _Alloc> _Base;
e63637ea BK	63	typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;
	64
	65	public:
ced3cb9f PC	66	typedef typename _Base::size_type size_type;
	67	typedef typename _Base::hasher hasher;
	68	typedef typename _Base::key_equal key_equal;
	69	typedef typename _Base::allocator_type allocator_type;
	70
	71	typedef typename _Base::key_type key_type;
	72	typedef typename _Base::value_type value_type;
	73
	74	typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
	75	unordered_set> iterator;
	76	typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
	77	unordered_set> const_iterator;
e63637ea BK	78
	79	explicit
	80	unordered_set(size_type __n = 10,
	81	const hasher& __hf = hasher(),
	82	const key_equal& __eql = key_equal(),
	83	const allocator_type& __a = allocator_type())
ced3cb9f	84	: _Base(__n, __hf, __eql, __a) { }
e63637ea BK	85
	86	template<typename _InputIterator>
	87	unordered_set(_InputIterator __f, _InputIterator __l,
	88	size_type __n = 10,
	89	const hasher& __hf = hasher(),
	90	const key_equal& __eql = key_equal(),
	91	const allocator_type& __a = allocator_type())
ced3cb9f PC	92	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
	93	__hf, __eql, __a), _Safe_base() { }
	94
	95	unordered_set(const unordered_set& __x)
	96	: _Base(__x), _Safe_base() { }
	97
	98	unordered_set(const _Base& __x)
	99	: _Base(__x), _Safe_base() { }
	100
	101	unordered_set(unordered_set&& __x)
	102	: _Base(std::forward<unordered_set>(__x)), _Safe_base() { }
e63637ea	103
988499f4 JM	104	unordered_set(initializer_list<value_type> __l,
	105	size_type __n = 10,
	106	const hasher& __hf = hasher(),
	107	const key_equal& __eql = key_equal(),
	108	const allocator_type& __a = allocator_type())
ced3cb9f	109	: _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
e63637ea	110
ced3cb9f PC	111	unordered_set&
	112	operator=(const unordered_set& __x)
	113	{
	114	static_cast<_Base>(this) = __x;
	115	this->_M_invalidate_all();
	116	return *this;
	117	}
69b3331e PC	118
	119	unordered_set&
	120	operator=(unordered_set&& __x)
	121	{
	122	// NB: DR 675.
	123	clear();
	124	swap(__x);
	125	return *this;
	126	}
	127
988499f4 JM	128	unordered_set&
	129	operator=(initializer_list<value_type> __l)
	130	{
	131	this->clear();
	132	this->insert(__l);
	133	return *this;
	134	}
	135
e63637ea	136	void
69b3331e	137	swap(unordered_set&& __x)
e63637ea	138	{
ced3cb9f	139	_Base::swap(__x);
e63637ea BK	140	_Safe_base::_M_swap(__x);
e63637ea BK	141	}
69b3331e PC	142
	143	void
	144	clear()
	145	{
	146	_Base::clear();
	147	this->_M_invalidate_all();
	148	}
	149
ced3cb9f PC	150	iterator
	151	begin()
	152	{ return iterator(_Base::begin(), this); }
	153
	154	const_iterator
	155	begin() const
	156	{ return const_iterator(_Base::begin(), this); }
	157
	158	iterator
	159	end()
	160	{ return iterator(_Base::end(), this); }
	161
	162	const_iterator
	163	end() const
	164	{ return const_iterator(_Base::end(), this); }
	165
	166	const_iterator
	167	cbegin() const
	168	{ return const_iterator(_Base::begin(), this); }
	169
	170	const_iterator
	171	cend() const
	172	{ return const_iterator(_Base::end(), this); }
	173
	174	// local versions
	175	using _Base::begin;
	176	using _Base::end;
	177	using _Base::cbegin;
	178	using _Base::cend;
	179
	180	std::pair<iterator, bool>
	181	insert(const value_type& __obj)
	182	{
	183	typedef std::pair<typename _Base::iterator, bool> __pair_type;
	184	__pair_type __res = _Base::insert(__obj);
	185	return std::make_pair(iterator(__res.first, this), __res.second);
	186	}
	187
	188	iterator
	189	insert(iterator, const value_type& __obj)
	190	{
	191	typedef std::pair<typename _Base::iterator, bool> __pair_type;
	192	__pair_type __res = _Base::insert(__obj);
	193	return iterator(__res.first, this);
	194	}
	195
	196	const_iterator
	197	insert(const_iterator, const value_type& __obj)
	198	{
	199	typedef std::pair<typename _Base::iterator, bool> __pair_type;
	200	__pair_type __res = _Base::insert(__obj);
	201	return const_iterator(__res.first, this);
	202	}
	203
	204	void
	205	insert(std::initializer_list<value_type> __l)
	206	{ _Base::insert(__l); }
	207
	208	template<typename _InputIterator>
	209	void
	210	insert(_InputIterator __first, _InputIterator __last)
	211	{
	212	__glibcxx_check_valid_range(__first, __last);
	213	_Base::insert(__first, __last);
214	}
215
216	iterator
217	find(const key_type& __key)
218	{ return iterator(_Base::find(__key), this); }
219
220	const_iterator
221	find(const key_type& __key) const
222	{ return const_iterator(_Base::find(__key), this); }
223
224	std::pair<iterator, iterator>
225	equal_range(const key_type& __key)
226	{
227	typedef typename _Base::iterator _Base_iterator;
228	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
229	__pair_type __res = _Base::equal_range(__key);
230	return std::make_pair(iterator(__res.first, this),
231	iterator(__res.second, this));
232	}
233
234	std::pair<const_iterator, const_iterator>
235	equal_range(const key_type& __key) const
236	{
237	typedef typename _Base::const_iterator _Base_iterator;
238	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
239	__pair_type __res = _Base::equal_range(__key);
240	return std::make_pair(const_iterator(__res.first, this),
241	const_iterator(__res.second, this));
242	}
243
244	size_type
245	erase(const key_type& __key)
246	{
247	size_type __ret(0);
248	iterator __victim(_Base::find(__key), this);
249	if (__victim != end())
250	{
251	this->erase(__victim);
252	__ret = 1;
253	}
254	return __ret;
255	}
256
257	iterator
258	erase(iterator __it)
259	{
260	__glibcxx_check_erase(__it);
261	__it._M_invalidate();
262	return iterator(_Base::erase(__it.base()), this);
263	}
264
265	const_iterator
266	erase(const_iterator __it)
267	{
268	__glibcxx_check_erase(__it);
269	__it._M_invalidate();
270	return const_iterator(_Base::erase(__it.base()), this);
271	}
272
273	iterator
274	erase(iterator __first, iterator __last)
275	{
276	__glibcxx_check_erase_range(__first, __last);
277	for (iterator __tmp = __first; __tmp != __last;)
278	{
279	iterator __victim = __tmp++;
280	__victim._M_invalidate();
281	}
282	return iterator(_Base::erase(__first.base(),
283	__last.base()), this);
284	}
285
286	const_iterator
287	erase(const_iterator __first, const_iterator __last)
288	{
289	__glibcxx_check_erase_range(__first, __last);
290	for (const_iterator __tmp = __first; __tmp != __last;)
291	{
292	const_iterator __victim = __tmp++;
293	__victim._M_invalidate();
294	}
295	return const_iterator(_Base::erase(__first.base(),
296	__last.base()), this);
297	}
298
299	_Base&
300	_M_base() { return *this; }
301
302	const _Base&
303	_M_base() const { return *this; }
304
69b3331e PC	305	private:
	306	void
	307	_M_invalidate_all()
	308	{
	309	typedef typename _Base::const_iterator _Base_const_iterator;
	310	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
ced3cb9f	311	this->_M_invalidate_if(_Not_equal(_M_base().end()));
69b3331e	312	}
e63637ea BK	313	};
	314
	315	template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
69b3331e PC	316	inline void
	317	swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
	318	unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
	319	{ __x.swap(__y); }
e63637ea BK	320
e63637ea BK	321	template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
69b3331e PC	322	inline void
	323	swap(unordered_set<_Value, _Hash, _Pred, _Alloc>&& __x,
	324	unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
	325	{ __x.swap(__y); }
e63637ea BK	326
	327	template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
	328	inline void
	329	swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
69b3331e	330	unordered_set<_Value, _Hash, _Pred, _Alloc>&& __y)
e63637ea BK	331	{ __x.swap(__y); }
e63637ea BK	332
e63637ea BK	333
e63637ea BK	334	template<typename _Value,
ced3cb9f	335	typename _Hash = std::hash<_Value>,
e63637ea	336	typename _Pred = std::equal_to<_Value>,
ced3cb9f	337	typename _Alloc = std::allocator<_Value> >
e63637ea	338	class unordered_multiset
ced3cb9f PC	339	: public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
	340	public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
	341	_Pred, _Alloc> >
e63637ea	342	{
ced3cb9f PC	343	typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash,
ced3cb9f PC	344	_Pred, _Alloc> _Base;
e63637ea BK	345	typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
	346
	347	public:
ced3cb9f PC	348	typedef typename _Base::size_type size_type;
	349	typedef typename _Base::hasher hasher;
	350	typedef typename _Base::key_equal key_equal;
	351	typedef typename _Base::allocator_type allocator_type;
	352
	353	typedef typename _Base::key_type key_type;
	354	typedef typename _Base::value_type value_type;
	355
	356	typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
	357	unordered_multiset> iterator;
	358	typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
	359	unordered_multiset> const_iterator;
e63637ea BK	360
	361	explicit
	362	unordered_multiset(size_type __n = 10,
ced3cb9f PC	363	const hasher& __hf = hasher(),
	364	const key_equal& __eql = key_equal(),
	365	const allocator_type& __a = allocator_type())
	366	: _Base(__n, __hf, __eql, __a) { }
e63637ea BK	367
	368	template<typename _InputIterator>
	369	unordered_multiset(_InputIterator __f, _InputIterator __l,
ced3cb9f PC	370	size_type __n = 10,
	371	const hasher& __hf = hasher(),
	372	const key_equal& __eql = key_equal(),
	373	const allocator_type& __a = allocator_type())
	374	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,
	375	__hf, __eql, __a), _Safe_base() { }
	376
	377	unordered_multiset(const unordered_multiset& __x)
	378	: _Base(__x), _Safe_base() { }
	379
	380	unordered_multiset(const _Base& __x)
	381	: _Base(__x), _Safe_base() { }
	382
	383	unordered_multiset(unordered_multiset&& __x)
	384	: _Base(std::forward<unordered_multiset>(__x)), _Safe_base() { }
e63637ea	385
988499f4 JM	386	unordered_multiset(initializer_list<value_type> __l,
	387	size_type __n = 10,
	388	const hasher& __hf = hasher(),
	389	const key_equal& __eql = key_equal(),
	390	const allocator_type& __a = allocator_type())
ced3cb9f	391	: _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
e63637ea	392
ced3cb9f PC	393	unordered_multiset&
	394	operator=(const unordered_multiset& __x)
	395	{
	396	static_cast<_Base>(this) = __x;
	397	this->_M_invalidate_all();
	398	return *this;
	399	}
69b3331e PC	400
	401	unordered_multiset&
	402	operator=(unordered_multiset&& __x)
	403	{
	404	// NB: DR 675.
	405	clear();
	406	swap(__x);
	407	return *this;
	408	}
	409
988499f4 JM	410	unordered_multiset&
	411	operator=(initializer_list<value_type> __l)
	412	{
	413	this->clear();
	414	this->insert(__l);
	415	return *this;
	416	}
	417
e63637ea	418	void
69b3331e	419	swap(unordered_multiset&& __x)
e63637ea	420	{
ced3cb9f	421	_Base::swap(__x);
e63637ea BK	422	_Safe_base::_M_swap(__x);
e63637ea BK	423	}
69b3331e	424
ced3cb9f	425	void
69b3331e PC	426	clear()
	427	{
	428	_Base::clear();
	429	this->_M_invalidate_all();
	430	}
	431
ced3cb9f PC	432	iterator
	433	begin()
	434	{ return iterator(_Base::begin(), this); }
	435
	436	const_iterator
	437	begin() const
	438	{ return const_iterator(_Base::begin(), this); }
	439
	440	iterator
	441	end()
	442	{ return iterator(_Base::end(), this); }
	443
	444	const_iterator
	445	end() const
	446	{ return const_iterator(_Base::end(), this); }
	447
	448	const_iterator
	449	cbegin() const
	450	{ return const_iterator(_Base::begin(), this); }
	451
	452	const_iterator
	453	cend() const
	454	{ return const_iterator(_Base::end(), this); }
	455
	456	// local versions
	457	using _Base::begin;
	458	using _Base::end;
	459	using _Base::cbegin;
	460	using _Base::cend;
	461
	462	iterator
	463	insert(const value_type& __obj)
	464	{ return iterator(_Base::insert(__obj), this); }
	465
	466	iterator
	467	insert(iterator, const value_type& __obj)
	468	{ return iterator(_Base::insert(__obj), this); }
	469
	470	const_iterator
	471	insert(const_iterator, const value_type& __obj)
	472	{ return const_iterator(_Base::insert(__obj), this); }
	473
	474	void
	475	insert(std::initializer_list<value_type> __l)
	476	{ _Base::insert(__l); }
	477
	478	template<typename _InputIterator>
	479	void
	480	insert(_InputIterator __first, _InputIterator __last)
	481	{
	482	__glibcxx_check_valid_range(__first, __last);
	483	_Base::insert(__first, __last);
	484	}
	485
	486	iterator
	487	find(const key_type& __key)
	488	{ return iterator(_Base::find(__key), this); }
	489
	490	const_iterator
	491	find(const key_type& __key) const
	492	{ return const_iterator(_Base::find(__key), this); }
	493
	494	std::pair<iterator, iterator>
	495	equal_range(const key_type& __key)
496	{
497	typedef typename _Base::iterator _Base_iterator;
498	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
499	__pair_type __res = _Base::equal_range(__key);
500	return std::make_pair(iterator(__res.first, this),
501	iterator(__res.second, this));
502	}
503
504	std::pair<const_iterator, const_iterator>
505	equal_range(const key_type& __key) const
506	{
507	typedef typename _Base::const_iterator _Base_iterator;
508	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
509	__pair_type __res = _Base::equal_range(__key);
510	return std::make_pair(const_iterator(__res.first, this),
511	const_iterator(__res.second, this));
512	}
513
514	size_type
515	erase(const key_type& __key)
516	{
517	size_type __ret(0);
518	iterator __victim(_Base::find(__key), this);
519	if (__victim != end())
520	{
521	this->erase(__victim);
522	__ret = 1;
523	}
524	return __ret;
525	}
526
527	iterator
528	erase(iterator __it)
529	{
530	__glibcxx_check_erase(__it);
531	__it._M_invalidate();
532	return iterator(_Base::erase(__it.base()), this);
533	}
534
535	const_iterator
536	erase(const_iterator __it)
537	{
538	__glibcxx_check_erase(__it);
539	__it._M_invalidate();
540	return const_iterator(_Base::erase(__it.base()), this);
541	}
542
543	iterator
544	erase(iterator __first, iterator __last)
545	{
546	__glibcxx_check_erase_range(__first, __last);
547	for (iterator __tmp = __first; __tmp != __last;)
548	{
549	iterator __victim = __tmp++;
550	__victim._M_invalidate();
551	}
552	return iterator(_Base::erase(__first.base(),
553	__last.base()), this);
554	}
555
556	const_iterator
557	erase(const_iterator __first, const_iterator __last)
558	{
559	__glibcxx_check_erase_range(__first, __last);
560	for (const_iterator __tmp = __first; __tmp != __last;)
561	{
562	const_iterator __victim = __tmp++;
563	__victim._M_invalidate();
564	}
565	return const_iterator(_Base::erase(__first.base(),
566	__last.base()), this);
567	}
568
569	_Base&
570	_M_base() { return *this; }
571
572	const _Base&
573	_M_base() const { return *this; }
574
69b3331e PC	575	private:
	576	void
	577	_M_invalidate_all()
	578	{
	579	typedef typename _Base::const_iterator _Base_const_iterator;
	580	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
ced3cb9f	581	this->_M_invalidate_if(_Not_equal(_M_base().end()));
69b3331e	582	}
e63637ea BK	583	};
	584
	585	template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
69b3331e PC	586	inline void
	587	swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
	588	unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
	589	{ __x.swap(__y); }
e63637ea BK	590
e63637ea BK	591	template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
69b3331e PC	592	inline void
	593	swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>&& __x,
	594	unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
	595	{ __x.swap(__y); }
e63637ea BK	596
	597	template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
	598	inline void
	599	swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
69b3331e	600	unordered_multiset<_Value, _Hash, _Pred, _Alloc>&& __y)
e63637ea	601	{ __x.swap(__y); }
69b3331e	602
e63637ea BK	603	} // namespace __debug
	604	} // namespace std
	605
e63637ea	606	#endif