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

// Debugging unordered_map/unordered_multimap implementation -*- C++ -*-

// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
// 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 3, 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.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

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

#ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
#define _GLIBCXX_DEBUG_UNORDERED_MAP 1

#ifndef __GXX_EXPERIMENTAL_CXX0X__
# include <bits/c++0x_warning.h>
#else
# include <unordered_map>

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

namespace std
{
namespace __debug
{
  /// Class std::unordered_map with safety/checking/debug instrumentation.
  template<typename _Key, typename _Tp,
	   typename _Hash = std::hash<_Key>,
	   typename _Pred = std::equal_to<_Key>,
	   typename _Alloc = std::allocator<_Key> >
    class unordered_map
    : public _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
      public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,
						       _Pred, _Alloc> >
    {
      typedef _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash,
					    _Pred, _Alloc> _Base;
      typedef __gnu_debug::_Safe_sequence<unordered_map> _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_map> iterator;
      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
					  unordered_map> const_iterator;

      explicit
      unordered_map(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_map(_InputIterator __f, _InputIterator __l, 
		      size_type __n = 0,
		      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_map(const unordered_map& __x) 
      : _Base(__x), _Safe_base() { }

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

      unordered_map(unordered_map&& __x)
      : _Base(std::move(__x)), _Safe_base() { }

      unordered_map(initializer_list<value_type> __l,
		    size_type __n = 0,
		    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_map&
      operator=(const unordered_map& __x)
      {
	*static_cast<_Base*>(this) = __x;
	this->_M_invalidate_all();
	return *this;
      }

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

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

      void
      swap(unordered_map& __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(const_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);
      }

      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(const_iterator __it)
      {
	__glibcxx_check_erase(__it);
	__it._M_invalidate();
	return iterator(_Base::erase(__it.base()), this);
      }

      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 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 _Key, typename _Tp, typename _Hash,
	   typename _Pred, typename _Alloc>
    inline void
    swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__y); }

  template<typename _Key, typename _Tp, typename _Hash,
	   typename _Pred, typename _Alloc>
    inline bool
    operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	       const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    { return __x._M_equal(__y); }

  template<typename _Key, typename _Tp, typename _Hash,
	   typename _Pred, typename _Alloc>
    inline bool
    operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	       const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    { return !(__x == __y); }


  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
  template<typename _Key, typename _Tp,
	   typename _Hash = std::hash<_Key>,
	   typename _Pred = std::equal_to<_Key>,
	   typename _Alloc = std::allocator<_Key> >
    class unordered_multimap
    : public _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
						_Pred, _Alloc>,
      public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
							    _Pred, _Alloc> >
    {
      typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
						 _Pred, _Alloc> _Base;
      typedef __gnu_debug::_Safe_sequence<unordered_multimap> _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_multimap> iterator;
      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
					  unordered_multimap> const_iterator;

      explicit
      unordered_multimap(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_multimap(_InputIterator __f, _InputIterator __l, 
			   size_type __n = 0,
			   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_multimap(const unordered_multimap& __x) 
      : _Base(__x), _Safe_base() { }

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

      unordered_multimap(unordered_multimap&& __x) 
      : _Base(std::move(__x)), _Safe_base() { }

      unordered_multimap(initializer_list<value_type> __l,
			 size_type __n = 0,
			 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_multimap&
      operator=(const unordered_multimap& __x)
      {
	*static_cast<_Base*>(this) = __x;
	this->_M_invalidate_all();
	return *this;
      }

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

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

      void
      swap(unordered_multimap& __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(const_iterator, const value_type& __obj)
      { return 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(const_iterator __it)
      {
	__glibcxx_check_erase(__it);
	__it._M_invalidate();
	return iterator(_Base::erase(__it.base()), this);
      }

      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 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 _Key, typename _Tp, typename _Hash,
	   typename _Pred, typename _Alloc>
    inline void
    swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__y); }

  template<typename _Key, typename _Tp, typename _Hash,
	   typename _Pred, typename _Alloc>
    inline bool
    operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	       const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    { return __x._M_equal(__y); }

  template<typename _Key, typename _Tp, typename _Hash,
	   typename _Pred, typename _Alloc>
    inline bool
    operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	       const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    { return !(__x == __y); }

} // namespace __debug
} // namespace std

#endif // __GXX_EXPERIMENTAL_CXX0X__

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