// unordered_map implementation -*- C++ -*-
-// Copyright (C) 2010, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2010, 2011, 2012 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
{
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
- // 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 =
- __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
- integral_constant<bool, !__is_final(_Hash)>,
- __detail::__is_noexcept_hash<_Key, _Hash>>>::value>
- 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::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, __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 = 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)
- { }
-
- __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.begin(), __l.end(), __n, __hf,
- __detail::_Mod_range_hashing(),
- __detail::_Default_ranged_hash(),
- __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
- { }
-
- __unordered_map&
- operator=(initializer_list<value_type> __l)
- {
- this->clear();
- this->insert(__l.begin(), __l.end());
- return *this;
- }
- };
-
- 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 =
- __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
- integral_constant<bool, !__is_final(_Hash)>,
- __detail::__is_noexcept_hash<_Key, _Hash>>>::value>
- 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::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, __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,
- 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)
- { }
-
- __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.begin(), __l.end(), __n, __hf,
- __detail::_Mod_range_hashing(),
- __detail::_Default_ranged_hash(),
- __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
- { }
-
- __unordered_multimap&
- operator=(initializer_list<value_type> __l)
- {
- this->clear();
- this->insert(__l.begin(), __l.end());
- return *this;
- }
- };
-
- 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); }
-
- template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
- bool __cache_hash_code>
- inline bool
- operator==(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
- __cache_hash_code>& __x,
- const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
- __cache_hash_code>& __y)
- { return __x._M_equal(__y); }
-
- template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
- bool __cache_hash_code>
- inline bool
- operator!=(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
- __cache_hash_code>& __x,
- const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
- __cache_hash_code>& __y)
- { return !(__x == __y); }
-
- template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
- bool __cache_hash_code>
- inline bool
- operator==(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
- __cache_hash_code>& __x,
- const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
- __cache_hash_code>& __y)
- { return __x._M_equal(__y); }
-
- template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
- bool __cache_hash_code>
- inline bool
- operator!=(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
- __cache_hash_code>& __x,
- const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
- __cache_hash_code>& __y)
- { return !(__x == __y); }
+ /// Base types for unordered_map.
+ template<bool _Cache>
+ using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
+
+ template<typename _Key,
+ typename _Tp,
+ typename _Hash = hash<_Key>,
+ typename _Pred = std::equal_to<_Key>,
+ typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
+ typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
+ using __umap_hashtable = _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, _Tr>;
+
+ /// Base types for unordered_multimap.
+ template<bool _Cache>
+ using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;
+
+ template<typename _Key,
+ typename _Tp,
+ typename _Hash = hash<_Key>,
+ typename _Pred = std::equal_to<_Key>,
+ typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
+ typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>>
+ using __ummap_hashtable = _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, _Tr>;
/**
* @brief A standard container composed of unique keys (containing
* 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>.
+ * @tparam _Key Type of key objects.
+ * @tparam _Tp Type of mapped objects.
+ * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
+ * @tparam _Pred Predicate function object type, defaults
+ * to equal_to<_Value>.
+ * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
*
- * The resulting value type of the container is std::pair<const Key, Tp>.
+ * The resulting value type of the container is std::pair<const _Key, _Tp>.
+ *
+ * Base is _Hashtable, dispatched at compile time via template
+ * alias __umap_hashtable.
*/
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>
+ : public __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>
{
- typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
+ typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
public:
typedef typename _Base::value_type value_type;
{ }
template<typename _InputIterator>
- unordered_map(_InputIterator __f, _InputIterator __l,
+ unordered_map(_InputIterator __f, _InputIterator __l,
size_type __n = 0,
- const hasher& __hf = hasher(),
- const key_equal& __eql = key_equal(),
+ const hasher& __hf = hasher(),
+ const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
: _Base(__f, __l, __n, __hf, __eql, __a)
- { }
+ { }
unordered_map(initializer_list<value_type> __l,
size_type __n = 0,
const allocator_type& __a = allocator_type())
: _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
{ }
-
- unordered_map&
- operator=(initializer_list<value_type> __l)
- {
- this->clear();
- this->insert(__l.begin(), __l.end());
- return *this;
- }
};
-
+
/**
* @brief A standard container composed of equivalent keys
* (possibly containing multiple of each key value) that associates
* 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>.
+ * @tparam _Key Type of key objects.
+ * @tparam _Tp Type of mapped objects.
+ * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
+ * @tparam _Pred Predicate function object type, defaults
+ * to equal_to<_Value>.
+ * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
+ *
+ * The resulting value type of the container is std::pair<const _Key, _Tp>.
*
- * The resulting value type of the container is std::pair<const Key, Tp>.
+ * Base is _Hashtable, dispatched at compile time via template
+ * alias __ummap_hashtable.
*/
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>
+ : public __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>
{
- typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
+ typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
public:
typedef typename _Base::value_type value_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(),
{ }
template<typename _InputIterator>
- unordered_multimap(_InputIterator __f, _InputIterator __l,
+ unordered_multimap(_InputIterator __f, _InputIterator __l,
size_type __n = 0,
- const hasher& __hf = hasher(),
- const key_equal& __eql = key_equal(),
+ const hasher& __hf = hasher(),
+ const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
: _Base(__f, __l, __n, __hf, __eql, __a)
- { }
+ { }
unordered_multimap(initializer_list<value_type> __l,
size_type __n = 0,
const allocator_type& __a = allocator_type())
: _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
{ }
-
- unordered_multimap&
- operator=(initializer_list<value_type> __l)
- {
- this->clear();
- this->insert(__l.begin(), __l.end());
- return *this;
- }
};
template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>