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_SET_H
31 #define _STLP_INTERNAL_HASH_SET_H
33 #ifndef _STLP_INTERNAL_HASHTABLE_H
34 # include <stl/_hashtable.h>
37 # define hash_set __WORKAROUND_RENAME(hash_set)
38 # define hash_multiset __WORKAROUND_RENAME(hash_multiset)
42 template <class _Value, __DFL_TMPL_PARAM(_HashFcn,hash<_Value>),
43 __DFL_TMPL_PARAM(_EqualKey,equal_to<_Value>),
44 _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
48 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
49 _EqualKey, _Alloc> _Ht;
50 typedef hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
51 typedef typename _Ht::iterator _ht_iterator;
53 typedef typename _Ht::key_type key_type;
54 typedef typename _Ht::value_type value_type;
55 typedef typename _Ht::hasher hasher;
56 typedef typename _Ht::key_equal key_equal;
58 typedef typename _Ht::size_type size_type;
59 typedef typename _Ht::difference_type difference_type;
60 typedef typename _Ht::pointer pointer;
61 typedef typename _Ht::const_pointer const_pointer;
62 typedef typename _Ht::reference reference;
63 typedef typename _Ht::const_reference const_reference;
66 typedef typename _Ht::const_iterator const_iterator;
67 typedef const_iterator iterator;
69 typedef typename _Ht::allocator_type allocator_type;
71 hasher hash_funct() const { return _M_ht.hash_funct(); }
72 key_equal key_eq() const { return _M_ht.key_eq(); }
73 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
80 : _M_ht(100, hasher(), key_equal(), allocator_type()) {
84 # ifdef _STLP_USE_TRAP_LEAVE
85 hash_set(const _Self& __o) :
88 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
90 _STLP_POP_CLEANUP_ITEM
93 hash_set(const _Self& __o)
97 explicit hash_set(size_type __n)
98 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {
101 hash_set(size_type __n, const hasher& __hf)
102 : _M_ht(__n, __hf, key_equal(), allocator_type()) {
105 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
106 const allocator_type& __a = allocator_type())
107 : _M_ht(__n, __hf, __eql, __a) {
111 #ifdef _STLP_MEMBER_TEMPLATES
112 template <class _InputIterator>
113 hash_set(_InputIterator __f, _InputIterator __l)
114 : _M_ht(100, hasher(), key_equal(), allocator_type())
116 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
117 _M_ht.insert_unique(__f, __l);
118 _STLP_POP_CLEANUP_ITEM
120 template <class _InputIterator>
121 hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
122 : _M_ht(__n, hasher(), key_equal(), allocator_type())
124 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
125 _M_ht.insert_unique(__f, __l);
126 _STLP_POP_CLEANUP_ITEM
128 template <class _InputIterator>
129 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
131 : _M_ht(__n, __hf, key_equal(), allocator_type())
133 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
134 _M_ht.insert_unique(__f, __l);
135 _STLP_POP_CLEANUP_ITEM
137 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
138 template <class _InputIterator>
139 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
140 const hasher& __hf, const key_equal& __eql)
141 : _M_ht(__n, __hf, __eql, allocator_type())
143 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
144 _M_ht.insert_unique(__f, __l);
145 _STLP_POP_CLEANUP_ITEM
148 template <class _InputIterator>
149 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
150 const hasher& __hf, const key_equal& __eql,
151 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
152 : _M_ht(__n, __hf, __eql, __a)
154 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
155 _M_ht.insert_unique(__f, __l);
156 _STLP_POP_CLEANUP_ITEM
160 hash_set(const value_type* __f, const value_type* __l)
161 : _M_ht(100, hasher(), key_equal(), allocator_type())
163 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
164 _M_ht.insert_unique(__f, __l);
165 _STLP_POP_CLEANUP_ITEM
167 hash_set(const value_type* __f, const value_type* __l, size_type __n)
168 : _M_ht(__n, hasher(), key_equal(), allocator_type())
170 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
171 _M_ht.insert_unique(__f, __l);
172 _STLP_POP_CLEANUP_ITEM
174 hash_set(const value_type* __f, const value_type* __l, size_type __n,
176 : _M_ht(__n, __hf, key_equal(), allocator_type())
178 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
179 _M_ht.insert_unique(__f, __l);
180 _STLP_POP_CLEANUP_ITEM
182 hash_set(const value_type* __f, const value_type* __l, size_type __n,
183 const hasher& __hf, const key_equal& __eql,
184 const allocator_type& __a = allocator_type())
185 : _M_ht(__n, __hf, __eql, __a)
187 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
188 _M_ht.insert_unique(__f, __l);
189 _STLP_POP_CLEANUP_ITEM
192 hash_set(const_iterator __f, const_iterator __l)
193 : _M_ht(100, hasher(), key_equal(), allocator_type())
195 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
196 _M_ht.insert_unique(__f, __l);
197 _STLP_POP_CLEANUP_ITEM
199 hash_set(const_iterator __f, const_iterator __l, size_type __n)
200 : _M_ht(__n, hasher(), key_equal(), allocator_type())
202 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
203 _M_ht.insert_unique(__f, __l);
204 _STLP_POP_CLEANUP_ITEM
206 hash_set(const_iterator __f, const_iterator __l, size_type __n,
208 : _M_ht(__n, __hf, key_equal(), allocator_type())
210 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
211 _M_ht.insert_unique(__f, __l);
212 _STLP_POP_CLEANUP_ITEM
214 hash_set(const_iterator __f, const_iterator __l, size_type __n,
215 const hasher& __hf, const key_equal& __eql,
216 const allocator_type& __a = allocator_type())
217 : _M_ht(__n, __hf, __eql, __a)
219 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
220 _M_ht.insert_unique(__f, __l);
221 _STLP_POP_CLEANUP_ITEM
223 #endif /*_STLP_MEMBER_TEMPLATES */
225 #ifdef _STLP_USE_TRAP_LEAVE
227 static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper<bool>::_NewLC(__n); }
228 static void* operator new (size_t __n) { return _STLP_StackHelper<bool>::_NewLC(__n); }
232 size_type size() const { return _M_ht.size(); }
233 size_type max_size() const { return _M_ht.max_size(); }
234 bool empty() const { return _M_ht.empty(); }
235 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
237 iterator begin() const { return _M_ht.begin(); }
238 iterator end() const { return _M_ht.end(); }
241 pair<iterator, bool> insert(const value_type& __obj)
243 pair<_ht_iterator, bool> __p = _M_ht.insert_unique(__obj);
244 return pair<iterator,bool>(__REINTERPRET_CAST(const iterator&, __p.first), __p.second);
246 #ifdef _STLP_MEMBER_TEMPLATES
247 template <class _InputIterator>
248 void insert(_InputIterator __f, _InputIterator __l)
249 { _M_ht.insert_unique(__f,__l); }
251 void insert(const value_type* __f, const value_type* __l) {
252 _M_ht.insert_unique(__f,__l);
254 void insert(const_iterator __f, const_iterator __l)
255 {_M_ht.insert_unique(__f, __l); }
257 #endif /*_STLP_MEMBER_TEMPLATES */
258 pair<iterator, bool> insert_noresize(const value_type& __obj)
260 pair<_ht_iterator, bool> __p =
261 _M_ht.insert_unique_noresize(__obj);
262 return pair<iterator, bool>(__p.first, __p.second);
265 # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS )
267 iterator find(const _KT& __key) const { return _M_ht.find(__key); }
269 iterator find(const key_type& __key) const { return _M_ht.find(__key); }
271 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
273 pair<iterator, iterator> equal_range(const key_type& __key) const
274 { return _M_ht.equal_range(__key); }
276 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
277 void erase(iterator __it) { _M_ht.erase(__it); }
278 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
279 void clear() { _M_ht.clear(); }
282 void resize(size_type __hint) { _M_ht.resize(__hint); }
283 size_type bucket_count() const { return _M_ht.bucket_count(); }
284 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
285 size_type elems_in_bucket(size_type __n) const
286 { return _M_ht.elems_in_bucket(__n); }
288 static bool _STLP_CALL _M_equal (const _Self& __x, const _Self& __y) {
289 return _Ht::_M_equal(__x._M_ht,__y._M_ht);
294 template <class _Value, __DFL_TMPL_PARAM(_HashFcn,hash<_Value>),
295 __DFL_TMPL_PARAM(_EqualKey,equal_to<_Value>),
296 _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
300 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
301 _EqualKey, _Alloc> _Ht;
302 typedef hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
305 typedef typename _Ht::key_type key_type;
306 typedef typename _Ht::value_type value_type;
307 typedef typename _Ht::hasher hasher;
308 typedef typename _Ht::key_equal key_equal;
310 typedef typename _Ht::size_type size_type;
311 typedef typename _Ht::difference_type difference_type;
312 typedef typename _Ht::pointer pointer;
313 typedef typename _Ht::const_pointer const_pointer;
314 typedef typename _Ht::reference reference;
315 typedef typename _Ht::const_reference const_reference;
317 typedef typename _Ht::const_iterator const_iterator;
319 typedef const_iterator iterator;
321 typedef typename _Ht::allocator_type allocator_type;
323 hasher hash_funct() const { return _M_ht.hash_funct(); }
324 key_equal key_eq() const { return _M_ht.key_eq(); }
325 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
332 : _M_ht(100, hasher(), key_equal(), allocator_type()) {
336 # ifdef _STLP_USE_TRAP_LEAVE
337 hash_multiset(const _Self& __o) :
340 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
342 _STLP_POP_CLEANUP_ITEM
345 hash_multiset(const _Self& __o)
350 explicit hash_multiset(size_type __n)
351 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {
354 hash_multiset(size_type __n, const hasher& __hf)
355 : _M_ht(__n, __hf, key_equal(), allocator_type()) {
358 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql)
359 : _M_ht(__n, __hf, __eql, allocator_type()) {
362 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
363 const allocator_type& __a)
364 : _M_ht(__n, __hf, __eql, __a) {
368 #ifdef _STLP_MEMBER_TEMPLATES
369 template <class _InputIterator>
370 hash_multiset(_InputIterator __f, _InputIterator __l)
371 : _M_ht(100, hasher(), key_equal(), allocator_type())
373 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
374 _M_ht.insert_equal(__f, __l);
375 _STLP_POP_CLEANUP_ITEM
377 template <class _InputIterator>
378 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
379 : _M_ht(__n, hasher(), key_equal(), allocator_type())
381 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
382 _M_ht.insert_equal(__f, __l);
383 _STLP_POP_CLEANUP_ITEM
385 template <class _InputIterator>
386 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
388 : _M_ht(__n, __hf, key_equal(), allocator_type())
390 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
391 _M_ht.insert_equal(__f, __l);
392 _STLP_POP_CLEANUP_ITEM
395 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
396 template <class _InputIterator>
397 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
398 const hasher& __hf, const key_equal& __eql)
399 : _M_ht(__n, __hf, __eql, allocator_type())
401 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
402 _M_ht.insert_equal(__f, __l);
403 _STLP_POP_CLEANUP_ITEM
406 template <class _InputIterator>
407 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
408 const hasher& __hf, const key_equal& __eql,
409 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
410 : _M_ht(__n, __hf, __eql, __a)
412 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
413 _M_ht.insert_equal(__f, __l);
414 _STLP_POP_CLEANUP_ITEM
418 hash_multiset(const value_type* __f, const value_type* __l)
419 : _M_ht(100, hasher(), key_equal(), allocator_type())
421 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
422 _M_ht.insert_equal(__f, __l);
423 _STLP_POP_CLEANUP_ITEM
425 hash_multiset(const value_type* __f, const value_type* __l, size_type __n)
426 : _M_ht(__n, hasher(), key_equal(), allocator_type())
428 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
429 _M_ht.insert_equal(__f, __l);
430 _STLP_POP_CLEANUP_ITEM
432 hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
434 : _M_ht(__n, __hf, key_equal(), allocator_type())
436 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
437 _M_ht.insert_equal(__f, __l);
438 _STLP_POP_CLEANUP_ITEM
440 hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
441 const hasher& __hf, const key_equal& __eql,
442 const allocator_type& __a = allocator_type())
443 : _M_ht(__n, __hf, __eql, __a)
445 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
446 _M_ht.insert_equal(__f, __l);
447 _STLP_POP_CLEANUP_ITEM
450 hash_multiset(const_iterator __f, const_iterator __l)
451 : _M_ht(100, hasher(), key_equal(), allocator_type())
453 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
454 _M_ht.insert_equal(__f, __l);
455 _STLP_POP_CLEANUP_ITEM
457 hash_multiset(const_iterator __f, const_iterator __l, size_type __n)
458 : _M_ht(__n, hasher(), key_equal(), allocator_type())
460 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
461 _M_ht.insert_equal(__f, __l);
462 _STLP_POP_CLEANUP_ITEM
464 hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
466 : _M_ht(__n, __hf, key_equal(), allocator_type())
468 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
469 _M_ht.insert_equal(__f, __l);
470 _STLP_POP_CLEANUP_ITEM
472 hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
473 const hasher& __hf, const key_equal& __eql,
474 const allocator_type& __a = allocator_type())
475 : _M_ht(__n, __hf, __eql, __a)
477 _STLP_PUSH_CLEANUP_ITEM(_Self, this)
478 _M_ht.insert_equal(__f, __l);
479 _STLP_POP_CLEANUP_ITEM
481 #endif /*_STLP_MEMBER_TEMPLATES */
483 #ifdef _STLP_USE_TRAP_LEAVE
485 static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper<bool>::_NewLC(__n); }
486 static void* operator new (size_t __n) { return _STLP_StackHelper<bool>::_NewLC(__n); }
490 size_type size() const { return _M_ht.size(); }
491 size_type max_size() const { return _M_ht.max_size(); }
492 bool empty() const { return _M_ht.empty(); }
493 void swap(_Self& hs) { _M_ht.swap(hs._M_ht); }
495 iterator begin() const { return _M_ht.begin(); }
496 iterator end() const { return _M_ht.end(); }
499 iterator insert(const value_type& __obj)
500 { return _M_ht.insert_equal(__obj); }
501 #ifdef _STLP_MEMBER_TEMPLATES
502 template <class _InputIterator>
503 void insert(_InputIterator __f, _InputIterator __l)
504 { _M_ht.insert_equal(__f,__l); }
506 void insert(const value_type* __f, const value_type* __l) {
507 _M_ht.insert_equal(__f,__l);
509 void insert(const_iterator __f, const_iterator __l)
510 { _M_ht.insert_equal(__f, __l); }
511 #endif /*_STLP_MEMBER_TEMPLATES */
512 iterator insert_noresize(const value_type& __obj)
513 { return _M_ht.insert_equal_noresize(__obj); }
515 # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS )
517 iterator find(const _KT& __key) const { return _M_ht.find(__key); }
519 iterator find(const key_type& __key) const { return _M_ht.find(__key); }
522 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
524 pair<iterator, iterator> equal_range(const key_type& __key) const
525 { return _M_ht.equal_range(__key); }
527 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
528 void erase(iterator __it) { _M_ht.erase(__it); }
529 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
530 void clear() { _M_ht.clear(); }
533 void resize(size_type __hint) { _M_ht.resize(__hint); }
534 size_type bucket_count() const { return _M_ht.bucket_count(); }
535 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
536 size_type elems_in_bucket(size_type __n) const
537 { return _M_ht.elems_in_bucket(__n); }
538 static bool _STLP_CALL _M_equal (const _Self& __x, const _Self& __y) {
539 return _Ht::_M_equal(__x._M_ht,__y._M_ht);
543 #define _STLP_TEMPLATE_HEADER template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
544 #define _STLP_TEMPLATE_CONTAINER hash_set<_Value,_HashFcn,_EqualKey,_Alloc>
546 #include <stl/_relops_hash_cont.h>
548 #undef _STLP_TEMPLATE_CONTAINER
549 #define _STLP_TEMPLATE_CONTAINER hash_multiset<_Value,_HashFcn,_EqualKey,_Alloc>
550 #include <stl/_relops_hash_cont.h>
552 #undef _STLP_TEMPLATE_CONTAINER
553 #undef _STLP_TEMPLATE_HEADER
555 // Specialization of insert_iterator so that it will work for hash_set
556 // and hash_multiset.
558 #ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
560 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
561 class insert_iterator<hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
563 typedef hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
564 _Container* container;
566 typedef _Container container_type;
567 typedef output_iterator_tag iterator_category;
568 typedef void value_type;
569 typedef void difference_type;
570 typedef void pointer;
571 typedef void reference;
573 insert_iterator(_Container& __x) : container(&__x) {}
574 insert_iterator(_Container& __x, typename _Container::iterator)
576 insert_iterator<_Container>&
577 operator=(const typename _Container::value_type& __val) {
578 container->insert(__val);
581 insert_iterator<_Container>& operator*() { return *this; }
582 insert_iterator<_Container>& operator++() { return *this; }
583 insert_iterator<_Container>& operator++(int) { return *this; }
586 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
587 class insert_iterator<hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
589 typedef hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
590 _Container* container;
591 typename _Container::iterator iter;
593 typedef _Container container_type;
594 typedef output_iterator_tag iterator_category;
595 typedef void value_type;
596 typedef void difference_type;
597 typedef void pointer;
598 typedef void reference;
600 insert_iterator(_Container& __x) : container(&__x) {}
601 insert_iterator(_Container& __x, typename _Container::iterator)
603 insert_iterator<_Container>&
604 operator=(const typename _Container::value_type& __val) {
605 container->insert(__val);
608 insert_iterator<_Container>& operator*() { return *this; }
609 insert_iterator<_Container>& operator++() { return *this; }
610 insert_iterator<_Container>& operator++(int) { return *this; }
613 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
618 # undef hash_multiset
620 // provide a uniform way to access full funclionality
621 # define __hash_set__ __FULL_NAME(hash_set)
622 # define __hash_multiset__ __FULL_NAME(hash_multiset)
624 # if defined ( _STLP_USE_WRAPPER_FOR_ALLOC_PARAM )
625 # include <stl/wrappers/_hash_set.h>
626 # endif /* WRAPPER */
628 #endif /* _STLP_INTERNAL_HASH_SET_H */