1 // TR1 unordered_map implementation -*- C++ -*-
3 // Copyright (C) 2010 Free Software Foundation, Inc.
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
8 // Free Software Foundation; either version 3, or (at your option)
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.
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.
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/>.
25 /** @file tr1/unordered_map.h
26 * This is an internal header file, included by other library headers.
27 * You should not attempt to use it directly.
34 // XXX When we get typedef templates these class definitions
35 // will be unnecessary.
36 template<class _Key
, class _Tp
,
37 class _Hash
= hash
<_Key
>,
38 class _Pred
= std::equal_to
<_Key
>,
39 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> >,
40 bool __cache_hash_code
= false>
42 : public _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>, _Alloc
,
43 std::_Select1st
<std::pair
<const _Key
, _Tp
> >, _Pred
,
44 _Hash
, __detail::_Mod_range_hashing
,
45 __detail::_Default_ranged_hash
,
46 __detail::_Prime_rehash_policy
,
47 __cache_hash_code
, false, true>
49 typedef _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>, _Alloc
,
50 std::_Select1st
<std::pair
<const _Key
, _Tp
> >, _Pred
,
51 _Hash
, __detail::_Mod_range_hashing
,
52 __detail::_Default_ranged_hash
,
53 __detail::_Prime_rehash_policy
,
54 __cache_hash_code
, false, true>
58 typedef typename
_Base::size_type size_type
;
59 typedef typename
_Base::hasher hasher
;
60 typedef typename
_Base::key_equal key_equal
;
61 typedef typename
_Base::allocator_type allocator_type
;
64 __unordered_map(size_type __n
= 10,
65 const hasher
& __hf
= hasher(),
66 const key_equal
& __eql
= key_equal(),
67 const allocator_type
& __a
= allocator_type())
68 : _Base(__n
, __hf
, __detail::_Mod_range_hashing(),
69 __detail::_Default_ranged_hash(),
70 __eql
, std::_Select1st
<std::pair
<const _Key
, _Tp
> >(), __a
)
73 template<typename _InputIterator
>
74 __unordered_map(_InputIterator __f
, _InputIterator __l
,
76 const hasher
& __hf
= hasher(),
77 const key_equal
& __eql
= key_equal(),
78 const allocator_type
& __a
= allocator_type())
79 : _Base(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
80 __detail::_Default_ranged_hash(),
81 __eql
, std::_Select1st
<std::pair
<const _Key
, _Tp
> >(), __a
)
85 template<class _Key
, class _Tp
,
86 class _Hash
= hash
<_Key
>,
87 class _Pred
= std::equal_to
<_Key
>,
88 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> >,
89 bool __cache_hash_code
= false>
90 class __unordered_multimap
91 : public _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>,
93 std::_Select1st
<std::pair
<const _Key
, _Tp
> >, _Pred
,
94 _Hash
, __detail::_Mod_range_hashing
,
95 __detail::_Default_ranged_hash
,
96 __detail::_Prime_rehash_policy
,
97 __cache_hash_code
, false, false>
99 typedef _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>,
101 std::_Select1st
<std::pair
<const _Key
, _Tp
> >, _Pred
,
102 _Hash
, __detail::_Mod_range_hashing
,
103 __detail::_Default_ranged_hash
,
104 __detail::_Prime_rehash_policy
,
105 __cache_hash_code
, false, false>
109 typedef typename
_Base::size_type size_type
;
110 typedef typename
_Base::hasher hasher
;
111 typedef typename
_Base::key_equal key_equal
;
112 typedef typename
_Base::allocator_type allocator_type
;
115 __unordered_multimap(size_type __n
= 10,
116 const hasher
& __hf
= hasher(),
117 const key_equal
& __eql
= key_equal(),
118 const allocator_type
& __a
= allocator_type())
119 : _Base(__n
, __hf
, __detail::_Mod_range_hashing(),
120 __detail::_Default_ranged_hash(),
121 __eql
, std::_Select1st
<std::pair
<const _Key
, _Tp
> >(), __a
)
125 template<typename _InputIterator
>
126 __unordered_multimap(_InputIterator __f
, _InputIterator __l
,
127 typename
_Base::size_type __n
= 0,
128 const hasher
& __hf
= hasher(),
129 const key_equal
& __eql
= key_equal(),
130 const allocator_type
& __a
= allocator_type())
131 : _Base(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
132 __detail::_Default_ranged_hash(),
133 __eql
, std::_Select1st
<std::pair
<const _Key
, _Tp
> >(), __a
)
137 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
,
138 bool __cache_hash_code
>
140 swap(__unordered_map
<_Key
, _Tp
, _Hash
, _Pred
,
141 _Alloc
, __cache_hash_code
>& __x
,
142 __unordered_map
<_Key
, _Tp
, _Hash
, _Pred
,
143 _Alloc
, __cache_hash_code
>& __y
)
146 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
,
147 bool __cache_hash_code
>
149 swap(__unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
,
150 _Alloc
, __cache_hash_code
>& __x
,
151 __unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
,
152 _Alloc
, __cache_hash_code
>& __y
)
157 * @brief A standard container composed of unique keys (containing
158 * at most one of each key value) that associates values of another type
161 * @ingroup unordered_associative_containers
163 * Meets the requirements of a <a href="tables.html#65">container</a>, and
164 * <a href="tables.html#xx">unordered associative container</a>
166 * @param Key Type of key objects.
167 * @param Tp Type of mapped objects.
168 * @param Hash Hashing function object type, defaults to hash<Value>.
169 * @param Pred Predicate function object type, defaults to equal_to<Value>.
170 * @param Alloc Allocator type, defaults to allocator<Key>.
172 * The resulting value type of the container is std::pair<const Key, Tp>.
174 template<class _Key
, class _Tp
,
175 class _Hash
= hash
<_Key
>,
176 class _Pred
= std::equal_to
<_Key
>,
177 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
179 : public __unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>
181 typedef __unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Base
;
184 typedef typename
_Base::value_type value_type
;
185 typedef typename
_Base::size_type size_type
;
186 typedef typename
_Base::hasher hasher
;
187 typedef typename
_Base::key_equal key_equal
;
188 typedef typename
_Base::allocator_type allocator_type
;
191 unordered_map(size_type __n
= 10,
192 const hasher
& __hf
= hasher(),
193 const key_equal
& __eql
= key_equal(),
194 const allocator_type
& __a
= allocator_type())
195 : _Base(__n
, __hf
, __eql
, __a
)
198 template<typename _InputIterator
>
199 unordered_map(_InputIterator __f
, _InputIterator __l
,
201 const hasher
& __hf
= hasher(),
202 const key_equal
& __eql
= key_equal(),
203 const allocator_type
& __a
= allocator_type())
204 : _Base(__f
, __l
, __n
, __hf
, __eql
, __a
)
209 * @brief A standard container composed of equivalent keys
210 * (possibly containing multiple of each key value) that associates
211 * values of another type with the keys.
213 * @ingroup unordered_associative_containers
215 * Meets the requirements of a <a href="tables.html#65">container</a>, and
216 * <a href="tables.html#xx">unordered associative container</a>
218 * @param Key Type of key objects.
219 * @param Tp Type of mapped objects.
220 * @param Hash Hashing function object type, defaults to hash<Value>.
221 * @param Pred Predicate function object type, defaults to equal_to<Value>.
222 * @param Alloc Allocator type, defaults to allocator<Key>.
224 * The resulting value type of the container is std::pair<const Key, Tp>.
226 template<class _Key
, class _Tp
,
227 class _Hash
= hash
<_Key
>,
228 class _Pred
= std::equal_to
<_Key
>,
229 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
230 class unordered_multimap
231 : public __unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>
233 typedef __unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Base
;
236 typedef typename
_Base::value_type value_type
;
237 typedef typename
_Base::size_type size_type
;
238 typedef typename
_Base::hasher hasher
;
239 typedef typename
_Base::key_equal key_equal
;
240 typedef typename
_Base::allocator_type allocator_type
;
243 unordered_multimap(size_type __n
= 10,
244 const hasher
& __hf
= hasher(),
245 const key_equal
& __eql
= key_equal(),
246 const allocator_type
& __a
= allocator_type())
247 : _Base(__n
, __hf
, __eql
, __a
)
251 template<typename _InputIterator
>
252 unordered_multimap(_InputIterator __f
, _InputIterator __l
,
253 typename
_Base::size_type __n
= 0,
254 const hasher
& __hf
= hasher(),
255 const key_equal
& __eql
= key_equal(),
256 const allocator_type
& __a
= allocator_type())
257 : _Base(__f
, __l
, __n
, __hf
, __eql
, __a
)
262 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
264 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
265 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
268 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
270 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
271 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)