5 * This material is provided "as is", with absolutely no warranty expressed
6 * or implied. Any use is at your own risk.
8 * Permission to use or copy this software for any purpose is hereby granted
9 * without fee, provided the above notices are retained on all copies.
10 * Permission to modify the code and to distribute modified code is granted,
11 * provided the above notices are retained, and a notice that the code was
12 * modified is included with the above copyright notice.
16 /* NOTE: This is an internal header file, included by other STL headers.
17 * You should not attempt to use it directly.
20 #ifndef _STLP_INTERNAL_UNORDERED_MAP_H
21 #define _STLP_INTERNAL_UNORDERED_MAP_H
23 #ifndef _STLP_INTERNAL_HASHTABLE_H
24 # include <stl/_hashtable.h>
29 //Specific iterator traits creation
30 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMapTraitsT
, traits
)
32 _STLP_BEGIN_TR1_NAMESPACE
34 template <class _Key
, class _Tp
, _STLP_DFL_TMPL_PARAM(_HashFcn
,hash
<_Key
>),
35 _STLP_DFL_TMPL_PARAM(_EqualKey
, equal_to
<_Key
>),
36 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key
, _Tp
) >
38 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
39 : public __stlport_class
<unordered_map
<_Key
, _Tp
, _HashFcn
, _EqualKey
, _Alloc
> >
43 typedef unordered_map
<_Key
, _Tp
, _HashFcn
, _EqualKey
, _Alloc
> _Self
;
45 typedef _Key key_type
;
46 typedef _Tp data_type
;
47 typedef _Tp mapped_type
;
48 typedef pair
<_STLP_CONST key_type
, data_type
> value_type
;
50 //Specific iterator traits creation
51 typedef _STLP_PRIV _UnorderedMapTraitsT
<value_type
> _UnorderedMapTraits
;
54 typedef hashtable
<value_type
, key_type
, _HashFcn
, _UnorderedMapTraits
,
55 _STLP_SELECT1ST(value_type
, _Key
), _EqualKey
, _Alloc
> _Ht
;
57 typedef typename
_Ht::hasher hasher
;
58 typedef typename
_Ht::key_equal key_equal
;
60 typedef typename
_Ht::size_type size_type
;
61 typedef typename
_Ht::difference_type difference_type
;
62 typedef typename
_Ht::pointer pointer
;
63 typedef typename
_Ht::const_pointer const_pointer
;
64 typedef typename
_Ht::reference reference
;
65 typedef typename
_Ht::const_reference const_reference
;
67 typedef typename
_Ht::iterator iterator
;
68 typedef typename
_Ht::const_iterator const_iterator
;
69 typedef typename
_Ht::local_iterator local_iterator
;
70 typedef typename
_Ht::const_local_iterator const_local_iterator
;
72 typedef typename
_Ht::allocator_type allocator_type
;
74 hasher
hash_function() const { return _M_ht
.hash_funct(); }
75 key_equal
key_eq() const { return _M_ht
.key_eq(); }
76 allocator_type
get_allocator() const { return _M_ht
.get_allocator(); }
80 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type
)
83 explicit unordered_map(size_type __n
= 0, const hasher
& __hf
= hasher(),
84 const key_equal
& __eql
= key_equal(),
85 const allocator_type
& __a
= allocator_type())
86 : _M_ht(__n
, __hf
, __eql
, __a
) {}
88 #if !defined (_STLP_NO_MOVE_SEMANTIC)
89 unordered_map(__move_source
<_Self
> src
)
90 : _M_ht(__move_source
<_Ht
>(src
.get()._M_ht
)) {}
93 #if defined (_STLP_MEMBER_TEMPLATES)
94 template <class _InputIterator
>
95 unordered_map(_InputIterator __f
, _InputIterator __l
,
96 size_type __n
= 0, const hasher
& __hf
= hasher(),
97 const key_equal
& __eql
= key_equal(),
98 const allocator_type
& __a
= allocator_type())
99 : _M_ht(__n
, __hf
, __eql
, __a
)
100 { _M_ht
.insert_unique(__f
, __l
); }
102 unordered_map(const value_type
* __f
, const value_type
* __l
,
103 size_type __n
= 0, const hasher
& __hf
= hasher(),
104 const key_equal
& __eql
= key_equal(),
105 const allocator_type
& __a
= allocator_type())
106 : _M_ht(__n
, __hf
, __eql
, __a
)
107 { _M_ht
.insert_unique(__f
, __l
); }
109 unordered_map(const_iterator __f
, const_iterator __l
,
110 size_type __n
= 0, const hasher
& __hf
= hasher(),
111 const key_equal
& __eql
= key_equal(),
112 const allocator_type
& __a
= allocator_type())
113 : _M_ht(__n
, __hf
, __eql
, __a
)
114 { _M_ht
.insert_unique(__f
, __l
); }
115 #endif /*_STLP_MEMBER_TEMPLATES */
117 _Self
& operator = (const _Self
& __other
)
118 { _M_ht
= __other
._M_ht
; return *this; }
120 size_type
size() const { return _M_ht
.size(); }
121 size_type
max_size() const { return _M_ht
.max_size(); }
122 bool empty() const { return _M_ht
.empty(); }
123 void swap(_Self
& __hs
) { _M_ht
.swap(__hs
._M_ht
); }
124 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
125 void _M_swap_workaround(_Self
& __x
) { swap(__x
); }
128 iterator
begin() { return _M_ht
.begin(); }
129 iterator
end() { return _M_ht
.end(); }
130 const_iterator
begin() const { return _M_ht
.begin(); }
131 const_iterator
end() const { return _M_ht
.end(); }
133 pair
<iterator
,bool> insert(const value_type
& __obj
)
134 { return _M_ht
.insert_unique(__obj
); }
135 iterator
insert(const_iterator
/*__hint*/, const value_type
& __obj
)
136 { return _M_ht
.insert_unique(__obj
); }
137 #if defined (_STLP_MEMBER_TEMPLATES)
138 template <class _InputIterator
>
139 void insert(_InputIterator __f
, _InputIterator __l
)
141 void insert(const value_type
* __f
, const value_type
* __l
)
142 { _M_ht
.insert_unique(__f
,__l
); }
143 void insert(const_iterator __f
, const_iterator __l
)
144 #endif /*_STLP_MEMBER_TEMPLATES */
145 { _M_ht
.insert_unique(__f
, __l
); }
147 _STLP_TEMPLATE_FOR_CONT_EXT
148 iterator
find(const _KT
& __key
) { return _M_ht
.find(__key
); }
149 _STLP_TEMPLATE_FOR_CONT_EXT
150 const_iterator
find(const _KT
& __key
) const { return _M_ht
.find(__key
); }
152 _STLP_TEMPLATE_FOR_CONT_EXT
153 _Tp
& operator[](const _KT
& __key
) {
154 iterator __it
= _M_ht
.find(__key
);
155 return (__it
== _M_ht
.end() ?
156 _M_ht
._M_insert(value_type(__key
, _STLP_DEFAULT_CONSTRUCTED(_Tp
))).second
:
160 _STLP_TEMPLATE_FOR_CONT_EXT
161 size_type
count(const _KT
& __key
) const { return _M_ht
.count(__key
); }
163 _STLP_TEMPLATE_FOR_CONT_EXT
164 pair
<iterator
, iterator
> equal_range(const _KT
& __key
)
165 { return _M_ht
.equal_range(__key
); }
166 _STLP_TEMPLATE_FOR_CONT_EXT
167 pair
<const_iterator
, const_iterator
> equal_range(const _KT
& __key
) const
168 { return _M_ht
.equal_range(__key
); }
170 size_type
erase(const key_type
& __key
) {return _M_ht
.erase(__key
); }
171 void erase(const_iterator __it
) { _M_ht
.erase(__it
); }
172 void erase(const_iterator __f
, const_iterator __l
) { _M_ht
.erase(__f
, __l
); }
173 void clear() { _M_ht
.clear(); }
175 size_type
bucket_count() const { return _M_ht
.bucket_count(); }
176 size_type
max_bucket_count() const { return _M_ht
.max_bucket_count(); }
177 size_type
bucket_size(size_type __n
) const { return _M_ht
.elems_in_bucket(__n
); }
178 _STLP_TEMPLATE_FOR_CONT_EXT
179 size_type
bucket(const _KT
& __k
) const { return _M_ht
.bucket(__k
); }
180 local_iterator
begin(size_type __n
) { return _M_ht
.begin(__n
); }
181 local_iterator
end(size_type __n
) { return _M_ht
.end(__n
); }
182 const_local_iterator
begin(size_type __n
) const { return _M_ht
.begin(__n
); }
183 const_local_iterator
end(size_type __n
) const { return _M_ht
.end(__n
); }
185 float load_factor() const { return _M_ht
.load_factor(); }
186 float max_load_factor() const { return _M_ht
.max_load_factor(); }
187 void max_load_factor(float __val
) { _M_ht
.max_load_factor(__val
); }
188 void rehash(size_type __hint
) { _M_ht
.rehash(__hint
); }
190 #if defined (__DMC__) // disable operator==(pair<x,unordered_map>, pair<x,unordered_map>)
191 bool operator==(const _Self
&) const;
197 //Specific iterator traits creation
198 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMultimapTraitsT
, traits
)
200 _STLP_BEGIN_TR1_NAMESPACE
202 template <class _Key
, class _Tp
, _STLP_DFL_TMPL_PARAM(_HashFcn
,hash
<_Key
>),
203 _STLP_DFL_TMPL_PARAM(_EqualKey
, equal_to
<_Key
>),
204 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key
, _Tp
) >
205 class unordered_multimap
206 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
207 : public __stlport_class
<unordered_multimap
<_Key
, _Tp
, _HashFcn
, _EqualKey
, _Alloc
> >
211 typedef unordered_multimap
<_Key
, _Tp
, _HashFcn
, _EqualKey
, _Alloc
> _Self
;
213 typedef _Key key_type
;
214 typedef _Tp data_type
;
215 typedef _Tp mapped_type
;
216 typedef pair
<_STLP_CONST key_type
, data_type
> value_type
;
218 //Specific iterator traits creation
219 typedef _STLP_PRIV _UnorderedMultimapTraitsT
<value_type
> _UnorderedMultimapTraits
;
222 typedef hashtable
<value_type
, key_type
, _HashFcn
, _UnorderedMultimapTraits
,
223 _STLP_SELECT1ST(value_type
, _Key
), _EqualKey
, _Alloc
> _Ht
;
225 typedef typename
_Ht::hasher hasher
;
226 typedef typename
_Ht::key_equal key_equal
;
228 typedef typename
_Ht::size_type size_type
;
229 typedef typename
_Ht::difference_type difference_type
;
230 typedef typename
_Ht::pointer pointer
;
231 typedef typename
_Ht::const_pointer const_pointer
;
232 typedef typename
_Ht::reference reference
;
233 typedef typename
_Ht::const_reference const_reference
;
235 typedef typename
_Ht::iterator iterator
;
236 typedef typename
_Ht::const_iterator const_iterator
;
237 typedef typename
_Ht::local_iterator local_iterator
;
238 typedef typename
_Ht::const_local_iterator const_local_iterator
;
240 typedef typename
_Ht::allocator_type allocator_type
;
242 hasher
hash_function() const { return _M_ht
.hash_funct(); }
243 key_equal
key_eq() const { return _M_ht
.key_eq(); }
244 allocator_type
get_allocator() const { return _M_ht
.get_allocator(); }
248 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type
)
251 explicit unordered_multimap(size_type __n
= 0, const hasher
& __hf
= hasher(),
252 const key_equal
& __eql
= key_equal(),
253 const allocator_type
& __a
= allocator_type())
254 : _M_ht(__n
, __hf
, __eql
, __a
) {}
256 #if !defined (_STLP_NO_MOVE_SEMANTIC)
257 unordered_multimap(__move_source
<_Self
> src
)
258 : _M_ht(__move_source
<_Ht
>(src
.get()._M_ht
)) {}
261 #if defined (_STLP_MEMBER_TEMPLATES)
262 template <class _InputIterator
>
263 unordered_multimap(_InputIterator __f
, _InputIterator __l
,
264 size_type __n
= 0, const hasher
& __hf
= hasher(),
265 const key_equal
& __eql
= key_equal(),
266 const allocator_type
& __a
= allocator_type())
267 : _M_ht(__n
, __hf
, __eql
, __a
)
268 { _M_ht
.insert_equal(__f
, __l
); }
270 unordered_multimap(const value_type
* __f
, const value_type
* __l
,
271 size_type __n
= 0, const hasher
& __hf
= hasher(),
272 const key_equal
& __eql
= key_equal(),
273 const allocator_type
& __a
= allocator_type())
274 : _M_ht(__n
, __hf
, __eql
, __a
)
275 { _M_ht
.insert_equal(__f
, __l
); }
277 unordered_multimap(const_iterator __f
, const_iterator __l
,
278 size_type __n
= 0, const hasher
& __hf
= hasher(),
279 const key_equal
& __eql
= key_equal(),
280 const allocator_type
& __a
= allocator_type())
281 : _M_ht(__n
, __hf
, __eql
, __a
)
282 { _M_ht
.insert_equal(__f
, __l
); }
283 #endif /*_STLP_MEMBER_TEMPLATES */
285 _Self
& operator = (const _Self
& __other
)
286 { _M_ht
= __other
._M_ht
; return *this; }
288 size_type
size() const { return _M_ht
.size(); }
289 size_type
max_size() const { return _M_ht
.max_size(); }
290 bool empty() const { return _M_ht
.empty(); }
291 void swap(_Self
& __hs
) { _M_ht
.swap(__hs
._M_ht
); }
292 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
293 void _M_swap_workaround(_Self
& __x
) { swap(__x
); }
296 iterator
begin() { return _M_ht
.begin(); }
297 iterator
end() { return _M_ht
.end(); }
298 const_iterator
begin() const { return _M_ht
.begin(); }
299 const_iterator
end() const { return _M_ht
.end(); }
301 iterator
insert(const value_type
& __obj
)
302 { return _M_ht
.insert_equal(__obj
); }
303 iterator
insert(const_iterator
/*__hint*/, const value_type
& __obj
)
304 { return _M_ht
.insert_equal(__obj
); }
305 #if defined (_STLP_MEMBER_TEMPLATES)
306 template <class _InputIterator
>
307 void insert(_InputIterator __f
, _InputIterator __l
)
309 void insert(const value_type
* __f
, const value_type
* __l
)
310 { _M_ht
.insert_equal(__f
,__l
); }
311 void insert(const_iterator __f
, const_iterator __l
)
312 #endif /*_STLP_MEMBER_TEMPLATES */
313 { _M_ht
.insert_equal(__f
, __l
); }
315 _STLP_TEMPLATE_FOR_CONT_EXT
316 iterator
find(const _KT
& __key
) { return _M_ht
.find(__key
); }
317 _STLP_TEMPLATE_FOR_CONT_EXT
318 const_iterator
find(const _KT
& __key
) const { return _M_ht
.find(__key
); }
320 _STLP_TEMPLATE_FOR_CONT_EXT
321 size_type
count(const _KT
& __key
) const { return _M_ht
.count(__key
); }
323 _STLP_TEMPLATE_FOR_CONT_EXT
324 pair
<iterator
, iterator
> equal_range(const _KT
& __key
)
325 { return _M_ht
.equal_range(__key
); }
326 _STLP_TEMPLATE_FOR_CONT_EXT
327 pair
<const_iterator
, const_iterator
> equal_range(const _KT
& __key
) const
328 { return _M_ht
.equal_range(__key
); }
330 size_type
erase(const key_type
& __key
) {return _M_ht
.erase(__key
); }
331 void erase(const_iterator __it
) { _M_ht
.erase(__it
); }
332 void erase(const_iterator __f
, const_iterator __l
) { _M_ht
.erase(__f
, __l
); }
333 void clear() { _M_ht
.clear(); }
335 size_type
bucket_count() const { return _M_ht
.bucket_count(); }
336 size_type
max_bucket_count() const { return _M_ht
.max_bucket_count(); }
337 size_type
bucket_size(size_type __n
) const { return _M_ht
.elems_in_bucket(__n
); }
338 _STLP_TEMPLATE_FOR_CONT_EXT
339 size_type
bucket(const _KT
& __k
) const { return _M_ht
.bucket(__k
); }
340 local_iterator
begin(size_type __n
) { return _M_ht
.begin(__n
); }
341 local_iterator
end(size_type __n
) { return _M_ht
.end(__n
); }
342 const_local_iterator
begin(size_type __n
) const { return _M_ht
.begin(__n
); }
343 const_local_iterator
end(size_type __n
) const { return _M_ht
.end(__n
); }
345 float load_factor() const { return _M_ht
.load_factor(); }
346 float max_load_factor() const { return _M_ht
.max_load_factor(); }
347 void max_load_factor(float __val
) { _M_ht
.max_load_factor(__val
); }
348 void rehash(size_type __hint
) { _M_ht
.rehash(__hint
); }
351 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
352 #define _STLP_TEMPLATE_CONTAINER unordered_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>
354 #include <stl/_relops_hash_cont.h>
356 #undef _STLP_TEMPLATE_CONTAINER
357 #define _STLP_TEMPLATE_CONTAINER unordered_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>
359 #include <stl/_relops_hash_cont.h>
361 #undef _STLP_TEMPLATE_CONTAINER
362 #undef _STLP_TEMPLATE_HEADER
366 // Specialization of insert_iterator so that it will work for unordered_map
367 // and unordered_multimap.
369 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
370 # if !defined (_STLP_NO_MOVE_SEMANTIC)
371 template <class _Key
, class _Tp
, class _HashFn
, class _EqKey
, class _Alloc
>
372 struct __move_traits
<_STLP_TR1 unordered_map
<_Key
, _Tp
, _HashFn
, _EqKey
, _Alloc
> > :
373 _STLP_PRIV __move_traits_help
<typename _STLP_TR1 unordered_map
<_Key
, _Tp
, _HashFn
, _EqKey
, _Alloc
>::_Ht
>
376 template <class _Key
, class _Tp
, class _HashFn
, class _EqKey
, class _Alloc
>
377 struct __move_traits
<_STLP_TR1 unordered_multimap
<_Key
, _Tp
, _HashFn
, _EqKey
, _Alloc
> > :
378 _STLP_PRIV __move_traits_help
<typename _STLP_TR1 unordered_map
<_Key
, _Tp
, _HashFn
, _EqKey
, _Alloc
>::_Ht
>
382 template <class _Key
, class _Tp
, class _HashFn
, class _EqKey
, class _Alloc
>
383 class insert_iterator
<_STLP_TR1 unordered_map
<_Key
, _Tp
, _HashFn
, _EqKey
, _Alloc
> > {
385 typedef _STLP_TR1 unordered_map
<_Key
, _Tp
, _HashFn
, _EqKey
, _Alloc
> _Container
;
386 _Container
* container
;
388 typedef _Container container_type
;
389 typedef output_iterator_tag iterator_category
;
390 typedef void value_type
;
391 typedef void difference_type
;
392 typedef void pointer
;
393 typedef void reference
;
395 insert_iterator(_Container
& __x
) : container(&__x
) {}
396 insert_iterator(_Container
& __x
, typename
_Container::iterator
)
398 insert_iterator
<_Container
>&
399 operator=(const typename
_Container::value_type
& __val
) {
400 container
->insert(__val
);
403 insert_iterator
<_Container
>& operator*() { return *this; }
404 insert_iterator
<_Container
>& operator++() { return *this; }
405 insert_iterator
<_Container
>& operator++(int) { return *this; }
408 template <class _Key
, class _Tp
, class _HashFn
, class _EqKey
, class _Alloc
>
409 class insert_iterator
<_STLP_TR1 unordered_multimap
<_Key
, _Tp
, _HashFn
, _EqKey
, _Alloc
> > {
411 typedef _STLP_TR1 unordered_multimap
<_Key
, _Tp
, _HashFn
, _EqKey
, _Alloc
> _Container
;
412 _Container
* container
;
413 typename
_Container::iterator iter
;
415 typedef _Container container_type
;
416 typedef output_iterator_tag iterator_category
;
417 typedef void value_type
;
418 typedef void difference_type
;
419 typedef void pointer
;
420 typedef void reference
;
422 insert_iterator(_Container
& __x
) : container(&__x
) {}
423 insert_iterator(_Container
& __x
, typename
_Container::iterator
)
425 insert_iterator
<_Container
>&
426 operator=(const typename
_Container::value_type
& __val
) {
427 container
->insert(__val
);
430 insert_iterator
<_Container
>& operator*() { return *this; }
431 insert_iterator
<_Container
>& operator++() { return *this; }
432 insert_iterator
<_Container
>& operator++(int) { return *this; }
435 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
439 #endif /* _STLP_INTERNAL_UNORDERED_MAP_H */