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

// TR1 unordered_map implementation -*- C++ -*-

// Copyright (C) 2010-2016 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 tr1/unordered_map.h
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{tr1/unordered_map}
 */

namespace std _GLIBCXX_VISIBILITY(default)
{
namespace tr1
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  // NB: When we get typedef templates these class definitions
  // will be unnecessary.
  template<class _Key, class _Tp,
	   class _Hash = hash<_Key>,
	   class _Pred = std::equal_to<_Key>,
	   class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
	   bool __cache_hash_code = false>
    class __unordered_map
    : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
			std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
			_Hash, __detail::_Mod_range_hashing,
			__detail::_Default_ranged_hash,
			__detail::_Prime_rehash_policy,
			__cache_hash_code, false, true>
    {
      typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
			 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
			 _Hash, __detail::_Mod_range_hashing,
			 __detail::_Default_ranged_hash,
			 __detail::_Prime_rehash_policy,
			 __cache_hash_code, false, true>
	_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;

      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, __detail::_Mod_range_hashing(),
	      __detail::_Default_ranged_hash(),
	      __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
      { }

      template<typename _InputIterator>
	__unordered_map(_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(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
		__detail::_Default_ranged_hash(),
		__eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
	{ }
    };

  template<class _Key, class _Tp,
	   class _Hash = hash<_Key>,
	   class _Pred = std::equal_to<_Key>,
	   class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
	   bool __cache_hash_code = false>
    class __unordered_multimap
    : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
			_Alloc,
			std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
			_Hash, __detail::_Mod_range_hashing,
			__detail::_Default_ranged_hash,
			__detail::_Prime_rehash_policy,
			__cache_hash_code, false, false>
    {
      typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
			 _Alloc,
			 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
			 _Hash, __detail::_Mod_range_hashing,
			 __detail::_Default_ranged_hash,
			 __detail::_Prime_rehash_policy,
			 __cache_hash_code, false, false>
	_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;

      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, __detail::_Mod_range_hashing(),
	      __detail::_Default_ranged_hash(),
	      __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
      { }


      template<typename _InputIterator>
	__unordered_multimap(_InputIterator __f, _InputIterator __l,
			     typename _Base::size_type __n = 0,
			     const hasher& __hf = hasher(),
			     const key_equal& __eql = key_equal(),
			     const allocator_type& __a = allocator_type())
	: _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
		__detail::_Default_ranged_hash(),
		__eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
	{ }
    };

  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
	   bool __cache_hash_code>
    inline void
    swap(__unordered_map<_Key, _Tp, _Hash, _Pred,
	 _Alloc, __cache_hash_code>& __x,
	 __unordered_map<_Key, _Tp, _Hash, _Pred,
	 _Alloc, __cache_hash_code>& __y)
    { __x.swap(__y); }

  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
	   bool __cache_hash_code>
    inline void
    swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred,
	 _Alloc, __cache_hash_code>& __x,
	 __unordered_multimap<_Key, _Tp, _Hash, _Pred,
	 _Alloc, __cache_hash_code>& __y)
    { __x.swap(__y); }


  /**
   *  @brief A standard container composed of unique keys (containing
   *  at most one of each key value) that associates values of another type
   *  with the keys.
   *
   *  @ingroup unordered_associative_containers
   *
   *  Meets the requirements of a <a href="tables.html#65">container</a>, and
   *  <a href="tables.html#xx">unordered associative container</a>
   *
   *  @param  Key  Type of key objects.
   *  @param  Tp  Type of mapped objects.
   *  @param  Hash  Hashing function object type, defaults to hash<Value>.
   *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
   *  @param  Alloc  Allocator type, defaults to allocator<Key>.
   *
   * The resulting value type of the container is std::pair<const Key, Tp>.
   */
  template<class _Key, class _Tp,
	   class _Hash = hash<_Key>,
	   class _Pred = std::equal_to<_Key>,
	   class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
    class unordered_map
    : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
    {
      typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>  _Base;

    public:
      typedef typename _Base::value_type      value_type;
      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;

      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 = 10,
		      const hasher& __hf = hasher(),
		      const key_equal& __eql = key_equal(),
		      const allocator_type& __a = allocator_type())
	: _Base(__f, __l, __n, __hf, __eql, __a)
	{ }
    };

  /**
   *  @brief A standard container composed of equivalent keys
   *  (possibly containing multiple of each key value) that associates
   *  values of another type with the keys.
   *
   *  @ingroup unordered_associative_containers
   *
   *  Meets the requirements of a <a href="tables.html#65">container</a>, and
   *  <a href="tables.html#xx">unordered associative container</a>
   *
   *  @param  Key  Type of key objects.
   *  @param  Tp  Type of mapped objects.
   *  @param  Hash  Hashing function object type, defaults to hash<Value>.
   *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
   *  @param  Alloc  Allocator type, defaults to allocator<Key>.
   *
   * The resulting value type of the container is std::pair<const Key, Tp>.
   */
  template<class _Key, class _Tp,
	   class _Hash = hash<_Key>,
	   class _Pred = std::equal_to<_Key>,
	   class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
    class unordered_multimap
    : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
    {
      typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>  _Base;

    public:
      typedef typename _Base::value_type      value_type;
      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;

      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,
			   typename _Base::size_type __n = 0,
			   const hasher& __hf = hasher(),
			   const key_equal& __eql = key_equal(),
			   const allocator_type& __a = allocator_type())
	: _Base(__f, __l, __n, __hf, __eql, __a)
	{ }

    };

  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
    inline void
    swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__y); }

  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
    inline void
    swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    { __x.swap(__y); }

_GLIBCXX_END_NAMESPACE_VERSION
}
}
Commit	Line	Data
d5ad42a1	1	// TR1 unordered_map implementation -- C++ --
c17b0a1c	2
f1717362	3	// Copyright (C) 2010-2016 Free Software Foundation, Inc.
c17b0a1c	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the
	7	// terms of the GNU General Public License as published by the
6bc9506f	8	// Free Software Foundation; either version 3, or (at your option)
c17b0a1c	9	// any later version.
	10
	11	// This library is distributed in the hope that it will be useful,
	12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	// GNU General Public License for more details.
	15
6bc9506f	16	// Under Section 7 of GPL version 3, you are granted additional
	17	// permissions described in the GCC Runtime Library Exception, version
	18	// 3.1, as published by the Free Software Foundation.
c17b0a1c	19
6bc9506f	20	// You should have received a copy of the GNU General Public License and
	21	// a copy of the GCC Runtime Library Exception along with this program;
	22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	23	// <http://www.gnu.org/licenses/>.
c17b0a1c	24
d5ad42a1	25	/** @file tr1/unordered_map.h
c17b0a1c	26	* This is an internal header file, included by other library headers.
5846aeac	27	* Do not attempt to use it directly. @headername{tr1/unordered_map}
c17b0a1c	28	*/
c17b0a1c	29
2948dd21	30	namespace std _GLIBCXX_VISIBILITY(default)
c17b0a1c	31	{
73e1eac5	32	namespace tr1
73e1eac5	33	{
2948dd21	34	_GLIBCXX_BEGIN_NAMESPACE_VERSION
	35
	36	// NB: When we get typedef templates these class definitions
c17b0a1c	37	// will be unnecessary.
	38	template<class _Key, class _Tp,
	39	class _Hash = hash<_Key>,
	40	class _Pred = std::equal_to<_Key>,
	41	class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
	42	bool __cache_hash_code = false>
	43	class __unordered_map
	44	: public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
5846aeac	45	std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
c17b0a1c	46	_Hash, __detail::_Mod_range_hashing,
	47	__detail::_Default_ranged_hash,
	48	__detail::_Prime_rehash_policy,
	49	__cache_hash_code, false, true>
	50	{
	51	typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
	52	std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
	53	_Hash, __detail::_Mod_range_hashing,
	54	__detail::_Default_ranged_hash,
	55	__detail::_Prime_rehash_policy,
	56	__cache_hash_code, false, true>
5846aeac	57	_Base;
c17b0a1c	58
	59	public:
	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	explicit
	66	__unordered_map(size_type __n = 10,
	67	const hasher& __hf = hasher(),
	68	const key_equal& __eql = key_equal(),
	69	const allocator_type& __a = allocator_type())
	70	: _Base(__n, __hf, __detail::_Mod_range_hashing(),
	71	__detail::_Default_ranged_hash(),
	72	__eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
	73	{ }
	74
	75	template<typename _InputIterator>
5846aeac	76	__unordered_map(_InputIterator __f, _InputIterator __l,
c17b0a1c	77	size_type __n = 10,
5846aeac	78	const hasher& __hf = hasher(),
5846aeac	79	const key_equal& __eql = key_equal(),
c17b0a1c	80	const allocator_type& __a = allocator_type())
	81	: _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
	82	__detail::_Default_ranged_hash(),
	83	__eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
	84	{ }
	85	};
5846aeac	86
c17b0a1c	87	template<class _Key, class _Tp,
	88	class _Hash = hash<_Key>,
	89	class _Pred = std::equal_to<_Key>,
	90	class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
	91	bool __cache_hash_code = false>
	92	class __unordered_multimap
	93	: public _Hashtable<_Key, std::pair<const _Key, _Tp>,
	94	_Alloc,
	95	std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
	96	_Hash, __detail::_Mod_range_hashing,
	97	__detail::_Default_ranged_hash,
	98	__detail::_Prime_rehash_policy,
	99	__cache_hash_code, false, false>
	100	{
	101	typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
	102	_Alloc,
	103	std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
	104	_Hash, __detail::_Mod_range_hashing,
	105	__detail::_Default_ranged_hash,
	106	__detail::_Prime_rehash_policy,
	107	__cache_hash_code, false, false>
5846aeac	108	_Base;
c17b0a1c	109
	110	public:
	111	typedef typename _Base::size_type size_type;
	112	typedef typename _Base::hasher hasher;
	113	typedef typename _Base::key_equal key_equal;
	114	typedef typename _Base::allocator_type allocator_type;
5846aeac	115
c17b0a1c	116	explicit
	117	__unordered_multimap(size_type __n = 10,
	118	const hasher& __hf = hasher(),
	119	const key_equal& __eql = key_equal(),
	120	const allocator_type& __a = allocator_type())
	121	: _Base(__n, __hf, __detail::_Mod_range_hashing(),
	122	__detail::_Default_ranged_hash(),
	123	__eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
	124	{ }
	125
	126
	127	template<typename _InputIterator>
5846aeac	128	__unordered_multimap(_InputIterator __f, _InputIterator __l,
c17b0a1c	129	typename _Base::size_type __n = 0,
5846aeac	130	const hasher& __hf = hasher(),
5846aeac	131	const key_equal& __eql = key_equal(),
c17b0a1c	132	const allocator_type& __a = allocator_type())
	133	: _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
	134	__detail::_Default_ranged_hash(),
	135	__eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
5846aeac	136	{ }
c17b0a1c	137	};
	138
	139	template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
	140	bool __cache_hash_code>
	141	inline void
	142	swap(__unordered_map<_Key, _Tp, _Hash, _Pred,
	143	_Alloc, __cache_hash_code>& __x,
	144	__unordered_map<_Key, _Tp, _Hash, _Pred,
	145	_Alloc, __cache_hash_code>& __y)
	146	{ __x.swap(__y); }
	147
	148	template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
	149	bool __cache_hash_code>
	150	inline void
	151	swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred,
	152	_Alloc, __cache_hash_code>& __x,
	153	__unordered_multimap<_Key, _Tp, _Hash, _Pred,
	154	_Alloc, __cache_hash_code>& __y)
	155	{ __x.swap(__y); }
	156
	157
48e3f567	158	/**
	159	* @brief A standard container composed of unique keys (containing
	160	* at most one of each key value) that associates values of another type
	161	* with the keys.
	162	*
48e3f567	163	* @ingroup unordered_associative_containers
	164	*
	165	* Meets the requirements of a <a href="tables.html#65">container</a>, and
	166	* <a href="tables.html#xx">unordered associative container</a>
	167	*
	168	* @param Key Type of key objects.
	169	* @param Tp Type of mapped objects.
	170	* @param Hash Hashing function object type, defaults to hash<Value>.
	171	* @param Pred Predicate function object type, defaults to equal_to<Value>.
	172	* @param Alloc Allocator type, defaults to allocator<Key>.
	173	*
	174	* The resulting value type of the container is std::pair<const Key, Tp>.
	175	*/
c17b0a1c	176	template<class _Key, class _Tp,
	177	class _Hash = hash<_Key>,
	178	class _Pred = std::equal_to<_Key>,
	179	class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
	180	class unordered_map
	181	: public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
	182	{
	183	typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
	184
	185	public:
b23fdac1	186	typedef typename _Base::value_type value_type;
c17b0a1c	187	typedef typename _Base::size_type size_type;
	188	typedef typename _Base::hasher hasher;
	189	typedef typename _Base::key_equal key_equal;
	190	typedef typename _Base::allocator_type allocator_type;
	191
	192	explicit
	193	unordered_map(size_type __n = 10,
	194	const hasher& __hf = hasher(),
	195	const key_equal& __eql = key_equal(),
	196	const allocator_type& __a = allocator_type())
	197	: _Base(__n, __hf, __eql, __a)
	198	{ }
	199
	200	template<typename _InputIterator>
5846aeac	201	unordered_map(_InputIterator __f, _InputIterator __l,
c17b0a1c	202	size_type __n = 10,
5846aeac	203	const hasher& __hf = hasher(),
5846aeac	204	const key_equal& __eql = key_equal(),
c17b0a1c	205	const allocator_type& __a = allocator_type())
c17b0a1c	206	: _Base(__f, __l, __n, __hf, __eql, __a)
5846aeac	207	{ }
c17b0a1c	208	};
5846aeac	209
48e3f567	210	/**
	211	* @brief A standard container composed of equivalent keys
	212	* (possibly containing multiple of each key value) that associates
	213	* values of another type with the keys.
	214	*
48e3f567	215	* @ingroup unordered_associative_containers
	216	*
	217	* Meets the requirements of a <a href="tables.html#65">container</a>, and
	218	* <a href="tables.html#xx">unordered associative container</a>
	219	*
	220	* @param Key Type of key objects.
	221	* @param Tp Type of mapped objects.
	222	* @param Hash Hashing function object type, defaults to hash<Value>.
	223	* @param Pred Predicate function object type, defaults to equal_to<Value>.
	224	* @param Alloc Allocator type, defaults to allocator<Key>.
	225	*
	226	* The resulting value type of the container is std::pair<const Key, Tp>.
	227	*/
c17b0a1c	228	template<class _Key, class _Tp,
	229	class _Hash = hash<_Key>,
	230	class _Pred = std::equal_to<_Key>,
	231	class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
	232	class unordered_multimap
	233	: public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
	234	{
	235	typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
	236
	237	public:
b23fdac1	238	typedef typename _Base::value_type value_type;
c17b0a1c	239	typedef typename _Base::size_type size_type;
	240	typedef typename _Base::hasher hasher;
	241	typedef typename _Base::key_equal key_equal;
	242	typedef typename _Base::allocator_type allocator_type;
5846aeac	243
c17b0a1c	244	explicit
	245	unordered_multimap(size_type __n = 10,
	246	const hasher& __hf = hasher(),
	247	const key_equal& __eql = key_equal(),
	248	const allocator_type& __a = allocator_type())
	249	: _Base(__n, __hf, __eql, __a)
	250	{ }
	251
	252
	253	template<typename _InputIterator>
5846aeac	254	unordered_multimap(_InputIterator __f, _InputIterator __l,
c17b0a1c	255	typename _Base::size_type __n = 0,
5846aeac	256	const hasher& __hf = hasher(),
5846aeac	257	const key_equal& __eql = key_equal(),
c17b0a1c	258	const allocator_type& __a = allocator_type())
c17b0a1c	259	: _Base(__f, __l, __n, __hf, __eql, __a)
5846aeac	260	{ }
0307ea24	261
c17b0a1c	262	};
c17b0a1c	263
0307ea24	264	template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
	265	inline void
	266	swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	267	unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
	268	{ __x.swap(__y); }
	269
	270	template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
	271	inline void
	272	swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
	273	unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
	274	{ __x.swap(__y); }
2948dd21	275
2948dd21	276	_GLIBCXX_END_NAMESPACE_VERSION
73e1eac5	277	}
c17b0a1c	278	}