4 * Hewlett-Packard Company
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
10 * Moscow Center for SPARC Technology
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef _STLP_INTERNAL_HASH_MAP_H
31 #define _STLP_INTERNAL_HASH_MAP_H
33 #ifndef _STLP_INTERNAL_HASHTABLE_H
34 # include <stl/_hashtable.h>
39 //Specific iterator traits creation
40 _STLP_CREATE_HASH_ITERATOR_TRAITS(HashMapTraitsT, traits)
42 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>),
43 _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Key>),
44 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) >
46 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
47 : public __stlport_class<hash_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> >
51 typedef hash_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self;
53 typedef _Key key_type;
54 typedef _Tp data_type;
55 typedef _Tp mapped_type;
56 #if !defined (__DMC__)
57 typedef pair<const key_type, data_type> value_type;
59 /* DMC goes too far in template instanciation and tries to fully instanciate
60 * slist<pair<const int, string> > for instance. The generation of assignment
61 * operator fails of course so we are force to use mutable key for this compiler.
63 typedef pair<key_type, data_type> value_type;
66 //Specific iterator traits creation
67 typedef _STLP_PRIV _HashMapTraitsT<value_type> _HashMapTraits;
70 typedef hashtable<value_type, key_type, _HashFcn, _HashMapTraits,
71 _STLP_SELECT1ST(value_type, _Key), _EqualKey, _Alloc > _Ht;
73 typedef typename _Ht::hasher hasher;
74 typedef typename _Ht::key_equal key_equal;
76 typedef typename _Ht::size_type size_type;
77 typedef typename _Ht::difference_type difference_type;
78 typedef typename _Ht::pointer pointer;
79 typedef typename _Ht::const_pointer const_pointer;
80 typedef typename _Ht::reference reference;
81 typedef typename _Ht::const_reference const_reference;
83 typedef typename _Ht::iterator iterator;
84 typedef typename _Ht::const_iterator const_iterator;
86 typedef typename _Ht::allocator_type allocator_type;
88 hasher hash_funct() const { return _M_ht.hash_funct(); }
89 key_equal key_eq() const { return _M_ht.key_eq(); }
90 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
94 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
96 hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
97 explicit hash_map(size_type __n)
98 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
99 hash_map(size_type __n, const hasher& __hf)
100 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
101 hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
102 const allocator_type& __a = allocator_type())
103 : _M_ht(__n, __hf, __eql, __a) {}
105 hash_map(__move_source<_Self> src)
106 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {
109 #ifdef _STLP_MEMBER_TEMPLATES
110 template <class _InputIterator>
111 hash_map(_InputIterator __f, _InputIterator __l)
112 : _M_ht(100, hasher(), key_equal(), allocator_type())
113 { _M_ht.insert_unique(__f, __l); }
114 template <class _InputIterator>
115 hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
116 : _M_ht(__n, hasher(), key_equal(), allocator_type())
117 { _M_ht.insert_unique(__f, __l); }
118 template <class _InputIterator>
119 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
121 : _M_ht(__n, __hf, key_equal(), allocator_type())
122 { _M_ht.insert_unique(__f, __l); }
123 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
124 template <class _InputIterator>
125 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
126 const hasher& __hf, const key_equal& __eql)
127 : _M_ht(__n, __hf, __eql, allocator_type())
128 { _M_ht.insert_unique(__f, __l); }
130 template <class _InputIterator>
131 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
132 const hasher& __hf, const key_equal& __eql,
133 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
134 : _M_ht(__n, __hf, __eql, __a)
135 { _M_ht.insert_unique(__f, __l); }
138 hash_map(const value_type* __f, const value_type* __l)
139 : _M_ht(100, hasher(), key_equal(), allocator_type())
140 { _M_ht.insert_unique(__f, __l); }
141 hash_map(const value_type* __f, const value_type* __l, size_type __n)
142 : _M_ht(__n, hasher(), key_equal(), allocator_type())
143 { _M_ht.insert_unique(__f, __l); }
144 hash_map(const value_type* __f, const value_type* __l, size_type __n,
146 : _M_ht(__n, __hf, key_equal(), allocator_type())
147 { _M_ht.insert_unique(__f, __l); }
148 hash_map(const value_type* __f, const value_type* __l, size_type __n,
149 const hasher& __hf, const key_equal& __eql,
150 const allocator_type& __a = allocator_type())
151 : _M_ht(__n, __hf, __eql, __a)
152 { _M_ht.insert_unique(__f, __l); }
154 hash_map(const_iterator __f, const_iterator __l)
155 : _M_ht(100, hasher(), key_equal(), allocator_type())
156 { _M_ht.insert_unique(__f, __l); }
157 hash_map(const_iterator __f, const_iterator __l, size_type __n)
158 : _M_ht(__n, hasher(), key_equal(), allocator_type())
159 { _M_ht.insert_unique(__f, __l); }
160 hash_map(const_iterator __f, const_iterator __l, size_type __n,
162 : _M_ht(__n, __hf, key_equal(), allocator_type())
163 { _M_ht.insert_unique(__f, __l); }
164 hash_map(const_iterator __f, const_iterator __l, size_type __n,
165 const hasher& __hf, const key_equal& __eql,
166 const allocator_type& __a = allocator_type())
167 : _M_ht(__n, __hf, __eql, __a)
168 { _M_ht.insert_unique(__f, __l); }
169 #endif /*_STLP_MEMBER_TEMPLATES */
172 size_type size() const { return _M_ht.size(); }
173 size_type max_size() const { return _M_ht.max_size(); }
174 bool empty() const { return _M_ht.empty(); }
175 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
176 iterator begin() { return _M_ht.begin(); }
177 iterator end() { return _M_ht.end(); }
178 const_iterator begin() const { return _M_ht.begin(); }
179 const_iterator end() const { return _M_ht.end(); }
182 pair<iterator,bool> insert(const value_type& __obj)
183 { return _M_ht.insert_unique(__obj); }
184 #ifdef _STLP_MEMBER_TEMPLATES
185 template <class _InputIterator>
186 void insert(_InputIterator __f, _InputIterator __l)
187 { _M_ht.insert_unique(__f,__l); }
189 void insert(const value_type* __f, const value_type* __l)
190 { _M_ht.insert_unique(__f,__l); }
191 void insert(const_iterator __f, const_iterator __l)
192 { _M_ht.insert_unique(__f, __l); }
193 #endif /*_STLP_MEMBER_TEMPLATES */
194 pair<iterator,bool> insert_noresize(const value_type& __obj)
195 { return _M_ht.insert_unique_noresize(__obj); }
197 _STLP_TEMPLATE_FOR_CONT_EXT
198 iterator find(const _KT& __key) { return _M_ht.find(__key); }
199 _STLP_TEMPLATE_FOR_CONT_EXT
200 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
202 _STLP_TEMPLATE_FOR_CONT_EXT
203 _Tp& operator[](const _KT& __key) {
204 iterator __it = _M_ht.find(__key);
205 return (__it == _M_ht.end() ?
206 _M_ht._M_insert(value_type(__key, _STLP_DEFAULT_CONSTRUCTED(_Tp))).second :
210 _STLP_TEMPLATE_FOR_CONT_EXT
211 size_type count(const _KT& __key) const { return _M_ht.count(__key); }
213 _STLP_TEMPLATE_FOR_CONT_EXT
214 pair<iterator, iterator> equal_range(const _KT& __key)
215 { return _M_ht.equal_range(__key); }
216 _STLP_TEMPLATE_FOR_CONT_EXT
217 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
218 { return _M_ht.equal_range(__key); }
220 _STLP_TEMPLATE_FOR_CONT_EXT
221 size_type erase(const _KT& __key) {return _M_ht.erase(__key); }
222 void erase(iterator __it) { _M_ht.erase(__it); }
223 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
224 void clear() { _M_ht.clear(); }
226 void resize(size_type __hint) { _M_ht.resize(__hint); }
227 size_type bucket_count() const { return _M_ht.bucket_count(); }
228 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
229 size_type elems_in_bucket(size_type __n) const
230 { return _M_ht.elems_in_bucket(__n); }
233 //Specific iterator traits creation
234 _STLP_CREATE_HASH_ITERATOR_TRAITS(HashMultimapTraitsT, traits)
236 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>),
237 _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Key>),
238 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) >
240 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
241 : public __stlport_class<hash_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> >
245 typedef hash_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self;
247 typedef _Key key_type;
248 typedef _Tp data_type;
249 typedef _Tp mapped_type;
250 #if !defined (__DMC__)
251 typedef pair<const key_type, data_type> value_type;
253 typedef pair<key_type, data_type> value_type;
256 //Specific iterator traits creation
257 typedef _STLP_PRIV _HashMultimapTraitsT<value_type> _HashMultimapTraits;
260 typedef hashtable<value_type, key_type, _HashFcn, _HashMultimapTraits,
261 _STLP_SELECT1ST(value_type, _Key), _EqualKey, _Alloc > _Ht;
263 typedef typename _Ht::hasher hasher;
264 typedef typename _Ht::key_equal key_equal;
266 typedef typename _Ht::size_type size_type;
267 typedef typename _Ht::difference_type difference_type;
268 typedef typename _Ht::pointer pointer;
269 typedef typename _Ht::const_pointer const_pointer;
270 typedef typename _Ht::reference reference;
271 typedef typename _Ht::const_reference const_reference;
273 typedef typename _Ht::iterator iterator;
274 typedef typename _Ht::const_iterator const_iterator;
276 typedef typename _Ht::allocator_type allocator_type;
278 hasher hash_funct() const { return _M_ht.hash_funct(); }
279 key_equal key_eq() const { return _M_ht.key_eq(); }
280 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
284 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
286 hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
287 explicit hash_multimap(size_type __n)
288 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
289 hash_multimap(size_type __n, const hasher& __hf)
290 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
291 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
292 const allocator_type& __a = allocator_type())
293 : _M_ht(__n, __hf, __eql, __a) {}
295 hash_multimap(__move_source<_Self> src)
296 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {
299 #ifdef _STLP_MEMBER_TEMPLATES
300 template <class _InputIterator>
301 hash_multimap(_InputIterator __f, _InputIterator __l)
302 : _M_ht(100, hasher(), key_equal(), allocator_type())
303 { _M_ht.insert_equal(__f, __l); }
304 template <class _InputIterator>
305 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
306 : _M_ht(__n, hasher(), key_equal(), allocator_type())
307 { _M_ht.insert_equal(__f, __l); }
308 template <class _InputIterator>
309 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
311 : _M_ht(__n, __hf, key_equal(), allocator_type())
312 { _M_ht.insert_equal(__f, __l); }
313 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
314 template <class _InputIterator>
315 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
316 const hasher& __hf, const key_equal& __eql)
317 : _M_ht(__n, __hf, __eql, allocator_type())
318 { _M_ht.insert_equal(__f, __l); }
320 template <class _InputIterator>
321 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
322 const hasher& __hf, const key_equal& __eql,
323 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
324 : _M_ht(__n, __hf, __eql, __a)
325 { _M_ht.insert_equal(__f, __l); }
328 hash_multimap(const value_type* __f, const value_type* __l)
329 : _M_ht(100, hasher(), key_equal(), allocator_type())
330 { _M_ht.insert_equal(__f, __l); }
331 hash_multimap(const value_type* __f, const value_type* __l, size_type __n)
332 : _M_ht(__n, hasher(), key_equal(), allocator_type())
333 { _M_ht.insert_equal(__f, __l); }
334 hash_multimap(const value_type* __f, const value_type* __l, size_type __n,
336 : _M_ht(__n, __hf, key_equal(), allocator_type())
337 { _M_ht.insert_equal(__f, __l); }
338 hash_multimap(const value_type* __f, const value_type* __l, size_type __n,
339 const hasher& __hf, const key_equal& __eql,
340 const allocator_type& __a = allocator_type())
341 : _M_ht(__n, __hf, __eql, __a)
342 { _M_ht.insert_equal(__f, __l); }
344 hash_multimap(const_iterator __f, const_iterator __l)
345 : _M_ht(100, hasher(), key_equal(), allocator_type())
346 { _M_ht.insert_equal(__f, __l); }
347 hash_multimap(const_iterator __f, const_iterator __l, size_type __n)
348 : _M_ht(__n, hasher(), key_equal(), allocator_type())
349 { _M_ht.insert_equal(__f, __l); }
350 hash_multimap(const_iterator __f, const_iterator __l, size_type __n,
352 : _M_ht(__n, __hf, key_equal(), allocator_type())
353 { _M_ht.insert_equal(__f, __l); }
354 hash_multimap(const_iterator __f, const_iterator __l, size_type __n,
355 const hasher& __hf, const key_equal& __eql,
356 const allocator_type& __a = allocator_type())
357 : _M_ht(__n, __hf, __eql, __a)
358 { _M_ht.insert_equal(__f, __l); }
359 #endif /*_STLP_MEMBER_TEMPLATES */
362 size_type size() const { return _M_ht.size(); }
363 size_type max_size() const { return _M_ht.max_size(); }
364 bool empty() const { return _M_ht.empty(); }
365 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
367 iterator begin() { return _M_ht.begin(); }
368 iterator end() { return _M_ht.end(); }
369 const_iterator begin() const { return _M_ht.begin(); }
370 const_iterator end() const { return _M_ht.end(); }
373 iterator insert(const value_type& __obj)
374 { return _M_ht.insert_equal(__obj); }
375 #ifdef _STLP_MEMBER_TEMPLATES
376 template <class _InputIterator>
377 void insert(_InputIterator __f, _InputIterator __l)
378 { _M_ht.insert_equal(__f,__l); }
380 void insert(const value_type* __f, const value_type* __l) {
381 _M_ht.insert_equal(__f,__l);
383 void insert(const_iterator __f, const_iterator __l)
384 { _M_ht.insert_equal(__f, __l); }
385 #endif /*_STLP_MEMBER_TEMPLATES */
386 iterator insert_noresize(const value_type& __obj)
387 { return _M_ht.insert_equal_noresize(__obj); }
389 _STLP_TEMPLATE_FOR_CONT_EXT
390 iterator find(const _KT& __key) { return _M_ht.find(__key); }
391 _STLP_TEMPLATE_FOR_CONT_EXT
392 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
394 _STLP_TEMPLATE_FOR_CONT_EXT
395 size_type count(const _KT& __key) const { return _M_ht.count(__key); }
397 _STLP_TEMPLATE_FOR_CONT_EXT
398 pair<iterator, iterator>
399 equal_range(const _KT& __key) { return _M_ht.equal_range(__key); }
400 _STLP_TEMPLATE_FOR_CONT_EXT
401 pair<const_iterator, const_iterator>
402 equal_range(const _KT& __key) const { return _M_ht.equal_range(__key); }
404 _STLP_TEMPLATE_FOR_CONT_EXT
405 size_type erase(const _KT& __key) {return _M_ht.erase(__key); }
406 void erase(iterator __it) { _M_ht.erase(__it); }
407 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
408 void clear() { _M_ht.clear(); }
411 void resize(size_type __hint) { _M_ht.resize(__hint); }
412 size_type bucket_count() const { return _M_ht.bucket_count(); }
413 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
414 size_type elems_in_bucket(size_type __n) const
415 { return _M_ht.elems_in_bucket(__n); }
418 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
419 #define _STLP_TEMPLATE_CONTAINER hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>
420 #include <stl/_relops_hash_cont.h>
421 #undef _STLP_TEMPLATE_CONTAINER
422 #define _STLP_TEMPLATE_CONTAINER hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>
423 #include <stl/_relops_hash_cont.h>
424 #undef _STLP_TEMPLATE_CONTAINER
425 #undef _STLP_TEMPLATE_HEADER
427 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
428 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
429 struct __move_traits<hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > :
430 _STLP_PRIV __move_traits_help<typename hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht>
433 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
434 struct __move_traits<hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > :
435 _STLP_PRIV __move_traits_help<typename hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht>
438 // Specialization of insert_iterator so that it will work for hash_map
439 // and hash_multimap.
440 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
441 class insert_iterator<hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
443 typedef hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
444 _Container* container;
446 typedef _Container container_type;
447 typedef output_iterator_tag iterator_category;
448 typedef void value_type;
449 typedef void difference_type;
450 typedef void pointer;
451 typedef void reference;
453 insert_iterator(_Container& __x) : container(&__x) {}
454 insert_iterator(_Container& __x, typename _Container::iterator)
456 insert_iterator<_Container>&
457 operator=(const typename _Container::value_type& __val) {
458 container->insert(__val);
461 insert_iterator<_Container>& operator*() { return *this; }
462 insert_iterator<_Container>& operator++() { return *this; }
463 insert_iterator<_Container>& operator++(int) { return *this; }
466 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
467 class insert_iterator<hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
469 typedef hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
470 _Container* container;
471 typename _Container::iterator iter;
473 typedef _Container container_type;
474 typedef output_iterator_tag iterator_category;
475 typedef void value_type;
476 typedef void difference_type;
477 typedef void pointer;
478 typedef void reference;
480 insert_iterator(_Container& __x) : container(&__x) {}
481 insert_iterator(_Container& __x, typename _Container::iterator)
483 insert_iterator<_Container>&
484 operator=(const typename _Container::value_type& __val) {
485 container->insert(__val);
488 insert_iterator<_Container>& operator*() { return *this; }
489 insert_iterator<_Container>& operator++() { return *this; }
490 insert_iterator<_Container>& operator++(int) { return *this; }
492 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
496 #endif /* _STLP_INTERNAL_HASH_MAP_H */