1 // 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 bits/unordered_map.h
26 * This is an internal header file, included by other library headers.
27 * You should not attempt to use it directly.
30 #ifndef _UNORDERED_MAP_H
31 #define _UNORDERED_MAP_H
33 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std
, _GLIBCXX_STD_D
)
35 // XXX When we get typedef templates these class definitions
36 // will be unnecessary.
37 template<class _Key
, class _Tp
,
38 class _Hash
= hash
<_Key
>,
39 class _Pred
= std::equal_to
<_Key
>,
40 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> >,
41 bool __cache_hash_code
= false>
43 : public _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>, _Alloc
,
44 std::_Select1st
<std::pair
<const _Key
, _Tp
> >, _Pred
,
45 _Hash
, __detail::_Mod_range_hashing
,
46 __detail::_Default_ranged_hash
,
47 __detail::_Prime_rehash_policy
,
48 __cache_hash_code
, false, true>
50 typedef _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>, _Alloc
,
51 std::_Select1st
<std::pair
<const _Key
, _Tp
> >, _Pred
,
52 _Hash
, __detail::_Mod_range_hashing
,
53 __detail::_Default_ranged_hash
,
54 __detail::_Prime_rehash_policy
,
55 __cache_hash_code
, false, true>
59 typedef typename
_Base::size_type size_type
;
60 typedef typename
_Base::hasher hasher
;
61 typedef typename
_Base::key_equal key_equal
;
62 typedef typename
_Base::allocator_type allocator_type
;
65 __unordered_map(size_type __n
= 10,
66 const hasher
& __hf
= hasher(),
67 const key_equal
& __eql
= key_equal(),
68 const allocator_type
& __a
= allocator_type())
69 : _Base(__n
, __hf
, __detail::_Mod_range_hashing(),
70 __detail::_Default_ranged_hash(),
71 __eql
, std::_Select1st
<std::pair
<const _Key
, _Tp
> >(), __a
)
74 template<typename _InputIterator
>
75 __unordered_map(_InputIterator __f
, _InputIterator __l
,
77 const hasher
& __hf
= hasher(),
78 const key_equal
& __eql
= key_equal(),
79 const allocator_type
& __a
= allocator_type())
80 : _Base(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
81 __detail::_Default_ranged_hash(),
82 __eql
, std::_Select1st
<std::pair
<const _Key
, _Tp
> >(), __a
)
85 __unordered_map(__unordered_map
&& __x
)
86 : _Base(std::forward
<_Base
>(__x
)) { }
89 template<class _Key
, class _Tp
,
90 class _Hash
= hash
<_Key
>,
91 class _Pred
= std::equal_to
<_Key
>,
92 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> >,
93 bool __cache_hash_code
= false>
94 class __unordered_multimap
95 : public _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>,
97 std::_Select1st
<std::pair
<const _Key
, _Tp
> >, _Pred
,
98 _Hash
, __detail::_Mod_range_hashing
,
99 __detail::_Default_ranged_hash
,
100 __detail::_Prime_rehash_policy
,
101 __cache_hash_code
, false, false>
103 typedef _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>,
105 std::_Select1st
<std::pair
<const _Key
, _Tp
> >, _Pred
,
106 _Hash
, __detail::_Mod_range_hashing
,
107 __detail::_Default_ranged_hash
,
108 __detail::_Prime_rehash_policy
,
109 __cache_hash_code
, false, false>
113 typedef typename
_Base::size_type size_type
;
114 typedef typename
_Base::hasher hasher
;
115 typedef typename
_Base::key_equal key_equal
;
116 typedef typename
_Base::allocator_type allocator_type
;
119 __unordered_multimap(size_type __n
= 10,
120 const hasher
& __hf
= hasher(),
121 const key_equal
& __eql
= key_equal(),
122 const allocator_type
& __a
= allocator_type())
123 : _Base(__n
, __hf
, __detail::_Mod_range_hashing(),
124 __detail::_Default_ranged_hash(),
125 __eql
, std::_Select1st
<std::pair
<const _Key
, _Tp
> >(), __a
)
129 template<typename _InputIterator
>
130 __unordered_multimap(_InputIterator __f
, _InputIterator __l
,
131 typename
_Base::size_type __n
= 0,
132 const hasher
& __hf
= hasher(),
133 const key_equal
& __eql
= key_equal(),
134 const allocator_type
& __a
= allocator_type())
135 : _Base(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
136 __detail::_Default_ranged_hash(),
137 __eql
, std::_Select1st
<std::pair
<const _Key
, _Tp
> >(), __a
)
140 __unordered_multimap(__unordered_multimap
&& __x
)
141 : _Base(std::forward
<_Base
>(__x
)) { }
144 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
,
145 bool __cache_hash_code
>
147 swap(__unordered_map
<_Key
, _Tp
, _Hash
, _Pred
,
148 _Alloc
, __cache_hash_code
>& __x
,
149 __unordered_map
<_Key
, _Tp
, _Hash
, _Pred
,
150 _Alloc
, __cache_hash_code
>& __y
)
153 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
,
154 bool __cache_hash_code
>
156 swap(__unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
,
157 _Alloc
, __cache_hash_code
>& __x
,
158 __unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
,
159 _Alloc
, __cache_hash_code
>& __y
)
162 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
,
163 bool __cache_hash_code
>
165 operator==(const __unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
,
166 __cache_hash_code
>& __x
,
167 const __unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
,
168 __cache_hash_code
>& __y
)
169 { return __x
._M_equal(__y
); }
171 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
,
172 bool __cache_hash_code
>
174 operator!=(const __unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
,
175 __cache_hash_code
>& __x
,
176 const __unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
,
177 __cache_hash_code
>& __y
)
178 { return !(__x
== __y
); }
180 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
,
181 bool __cache_hash_code
>
183 operator==(const __unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
,
184 __cache_hash_code
>& __x
,
185 const __unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
,
186 __cache_hash_code
>& __y
)
187 { return __x
._M_equal(__y
); }
189 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
,
190 bool __cache_hash_code
>
192 operator!=(const __unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
,
193 __cache_hash_code
>& __x
,
194 const __unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
,
195 __cache_hash_code
>& __y
)
196 { return !(__x
== __y
); }
199 * @brief A standard container composed of unique keys (containing
200 * at most one of each key value) that associates values of another type
203 * @ingroup unordered_associative_containers
205 * Meets the requirements of a <a href="tables.html#65">container</a>, and
206 * <a href="tables.html#xx">unordered associative container</a>
208 * @param Key Type of key objects.
209 * @param Tp Type of mapped objects.
210 * @param Hash Hashing function object type, defaults to hash<Value>.
211 * @param Pred Predicate function object type, defaults to equal_to<Value>.
212 * @param Alloc Allocator type, defaults to allocator<Key>.
214 * The resulting value type of the container is std::pair<const Key, Tp>.
216 template<class _Key
, class _Tp
,
217 class _Hash
= hash
<_Key
>,
218 class _Pred
= std::equal_to
<_Key
>,
219 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
221 : public __unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>
223 typedef __unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Base
;
226 typedef typename
_Base::value_type value_type
;
227 typedef typename
_Base::size_type size_type
;
228 typedef typename
_Base::hasher hasher
;
229 typedef typename
_Base::key_equal key_equal
;
230 typedef typename
_Base::allocator_type allocator_type
;
233 unordered_map(size_type __n
= 10,
234 const hasher
& __hf
= hasher(),
235 const key_equal
& __eql
= key_equal(),
236 const allocator_type
& __a
= allocator_type())
237 : _Base(__n
, __hf
, __eql
, __a
)
240 template<typename _InputIterator
>
241 unordered_map(_InputIterator __f
, _InputIterator __l
,
243 const hasher
& __hf
= hasher(),
244 const key_equal
& __eql
= key_equal(),
245 const allocator_type
& __a
= allocator_type())
246 : _Base(__f
, __l
, __n
, __hf
, __eql
, __a
)
249 unordered_map(unordered_map
&& __x
)
250 : _Base(std::forward
<_Base
>(__x
)) { }
252 unordered_map(initializer_list
<value_type
> __l
,
254 const hasher
& __hf
= hasher(),
255 const key_equal
& __eql
= key_equal(),
256 const allocator_type
& __a
= allocator_type())
257 : _Base(__l
.begin(), __l
.end(), __n
, __hf
, __eql
, __a
)
261 operator=(unordered_map
&& __x
)
271 operator=(initializer_list
<value_type
> __l
)
274 this->insert(__l
.begin(), __l
.end());
280 * @brief A standard container composed of equivalent keys
281 * (possibly containing multiple of each key value) that associates
282 * values of another type with the keys.
284 * @ingroup unordered_associative_containers
286 * Meets the requirements of a <a href="tables.html#65">container</a>, and
287 * <a href="tables.html#xx">unordered associative container</a>
289 * @param Key Type of key objects.
290 * @param Tp Type of mapped objects.
291 * @param Hash Hashing function object type, defaults to hash<Value>.
292 * @param Pred Predicate function object type, defaults to equal_to<Value>.
293 * @param Alloc Allocator type, defaults to allocator<Key>.
295 * The resulting value type of the container is std::pair<const Key, Tp>.
297 template<class _Key
, class _Tp
,
298 class _Hash
= hash
<_Key
>,
299 class _Pred
= std::equal_to
<_Key
>,
300 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
301 class unordered_multimap
302 : public __unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>
304 typedef __unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Base
;
307 typedef typename
_Base::value_type value_type
;
308 typedef typename
_Base::size_type size_type
;
309 typedef typename
_Base::hasher hasher
;
310 typedef typename
_Base::key_equal key_equal
;
311 typedef typename
_Base::allocator_type allocator_type
;
314 unordered_multimap(size_type __n
= 10,
315 const hasher
& __hf
= hasher(),
316 const key_equal
& __eql
= key_equal(),
317 const allocator_type
& __a
= allocator_type())
318 : _Base(__n
, __hf
, __eql
, __a
)
322 template<typename _InputIterator
>
323 unordered_multimap(_InputIterator __f
, _InputIterator __l
,
324 typename
_Base::size_type __n
= 0,
325 const hasher
& __hf
= hasher(),
326 const key_equal
& __eql
= key_equal(),
327 const allocator_type
& __a
= allocator_type())
328 : _Base(__f
, __l
, __n
, __hf
, __eql
, __a
)
331 unordered_multimap(unordered_multimap
&& __x
)
332 : _Base(std::forward
<_Base
>(__x
)) { }
334 unordered_multimap(initializer_list
<value_type
> __l
,
336 const hasher
& __hf
= hasher(),
337 const key_equal
& __eql
= key_equal(),
338 const allocator_type
& __a
= allocator_type())
339 : _Base(__l
.begin(), __l
.end(), __n
, __hf
, __eql
, __a
)
343 operator=(unordered_multimap
&& __x
)
353 operator=(initializer_list
<value_type
> __l
)
356 this->insert(__l
.begin(), __l
.end());
361 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
363 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
364 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
367 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
369 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
370 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
373 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
375 operator==(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
376 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
377 { return __x
._M_equal(__y
); }
379 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
381 operator!=(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
382 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
383 { return !(__x
== __y
); }
385 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
387 operator==(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
388 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
389 { return __x
._M_equal(__y
); }
391 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
393 operator!=(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
394 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
395 { return !(__x
== __y
); }
397 _GLIBCXX_END_NESTED_NAMESPACE
399 #endif /* _UNORDERED_MAP_H */