[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 __first, _InputIterator __last, 
		      size_type __n = 0,
		      const hasher& __hf = hasher(), 
		      const key_equal& __eql = key_equal(), 
		      const allocator_type& __a = allocator_type())
	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
								     __last)),
		__gnu_debug::__base(__last), __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);
      }

      template<typename _Pair, typename = typename
	       std::enable_if<std::is_convertible<_Pair,
						  value_type>::value>::type>
        std::pair<iterator, bool>
        insert(_Pair&& __obj)
        {
	  typedef std::pair<typename _Base::iterator, bool> __pair_type;
	  __pair_type __res = _Base::insert(std::forward<_Pair>(__obj));
	  return std::make_pair(iterator(__res.first, this), __res.second);
	}

      template<typename _Pair, typename = typename
	       std::enable_if<std::is_convertible<_Pair,
						  value_type>::value>::type>
        iterator
        insert(const_iterator, _Pair&& __obj)
        {
	  typedef std::pair<typename _Base::iterator, bool> __pair_type;
	  __pair_type __res = _Base::insert(std::forward<_Pair>(__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(__gnu_debug::__base(__first),
			__gnu_debug::__base(__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 __first, _InputIterator __last, 
			   size_type __n = 0,
			   const hasher& __hf = hasher(), 
			   const key_equal& __eql = key_equal(), 
			   const allocator_type& __a = allocator_type())
	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
								     __last)),
		__gnu_debug::__base(__last), __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); }

      template<typename _Pair, typename = typename
	       std::enable_if<std::is_convertible<_Pair,
						  value_type>::value>::type>
        iterator
        insert(_Pair&& __obj)
        { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }

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