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>
39 //Specific iterator traits creation
40 _STLP_CREATE_HASH_ITERATOR_TRAITS(HashSetTraitsT, Const_traits)
42 template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>),
43 _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Value>),
44 _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
46 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
47 : public __stlport_class<hash_set<_Value, _HashFcn, _EqualKey, _Alloc> >
50 typedef hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
51 //Specific iterator traits creation
52 typedef _STLP_PRIV _HashSetTraitsT<_Value> _HashSetTraits;
54 typedef hashtable<_Value, _Value, _HashFcn,
55 _HashSetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht;
57 typedef typename _Ht::key_type key_type;
58 typedef typename _Ht::value_type value_type;
59 typedef typename _Ht::hasher hasher;
60 typedef typename _Ht::key_equal key_equal;
62 typedef typename _Ht::size_type size_type;
63 typedef typename _Ht::difference_type difference_type;
64 typedef typename _Ht::pointer pointer;
65 typedef typename _Ht::const_pointer const_pointer;
66 typedef typename _Ht::reference reference;
67 typedef typename _Ht::const_reference const_reference;
69 typedef typename _Ht::iterator iterator;
70 typedef typename _Ht::const_iterator const_iterator;
72 typedef typename _Ht::allocator_type allocator_type;
74 hasher hash_funct() 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)
84 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
85 explicit hash_set(size_type __n)
86 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
87 hash_set(size_type __n, const hasher& __hf)
88 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
89 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
90 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
91 const allocator_type& __a = allocator_type())
93 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql)
94 : _M_ht(__n, __hf, __eql, allocator_type()) {}
95 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
96 const allocator_type& __a)
98 : _M_ht(__n, __hf, __eql, __a) {}
100 hash_set(__move_source<_Self> src)
101 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {}
103 #if defined (_STLP_MEMBER_TEMPLATES)
104 template <class _InputIterator>
105 hash_set(_InputIterator __f, _InputIterator __l)
106 : _M_ht(100, hasher(), key_equal(), allocator_type())
107 { _M_ht.insert_unique(__f, __l); }
108 template <class _InputIterator>
109 hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
110 : _M_ht(__n, hasher(), key_equal(), allocator_type())
111 { _M_ht.insert_unique(__f, __l); }
112 template <class _InputIterator>
113 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
115 : _M_ht(__n, __hf, key_equal(), allocator_type())
116 { _M_ht.insert_unique(__f, __l); }
117 template <class _InputIterator>
118 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
119 const hasher& __hf, const key_equal& __eql,
120 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
121 : _M_ht(__n, __hf, __eql, __a)
122 { _M_ht.insert_unique(__f, __l); }
123 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
124 template <class _InputIterator>
125 hash_set(_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); }
131 hash_set(const value_type* __f, const value_type* __l)
132 : _M_ht(100, hasher(), key_equal(), allocator_type())
133 { _M_ht.insert_unique(__f, __l); }
134 hash_set(const value_type* __f, const value_type* __l, size_type __n)
135 : _M_ht(__n, hasher(), key_equal(), allocator_type())
136 { _M_ht.insert_unique(__f, __l); }
137 hash_set(const value_type* __f, const value_type* __l, size_type __n,
139 : _M_ht(__n, __hf, key_equal(), allocator_type())
140 { _M_ht.insert_unique(__f, __l); }
141 hash_set(const value_type* __f, const value_type* __l, size_type __n,
142 const hasher& __hf, const key_equal& __eql,
143 const allocator_type& __a = allocator_type())
144 : _M_ht(__n, __hf, __eql, __a)
145 { _M_ht.insert_unique(__f, __l); }
147 hash_set(const_iterator __f, const_iterator __l)
148 : _M_ht(100, hasher(), key_equal(), allocator_type())
149 { _M_ht.insert_unique(__f, __l); }
150 hash_set(const_iterator __f, const_iterator __l, size_type __n)
151 : _M_ht(__n, hasher(), key_equal(), allocator_type())
152 { _M_ht.insert_unique(__f, __l); }
153 hash_set(const_iterator __f, const_iterator __l, size_type __n,
155 : _M_ht(__n, __hf, key_equal(), allocator_type())
156 { _M_ht.insert_unique(__f, __l); }
157 hash_set(const_iterator __f, const_iterator __l, size_type __n,
158 const hasher& __hf, const key_equal& __eql,
159 const allocator_type& __a = allocator_type())
160 : _M_ht(__n, __hf, __eql, __a)
161 { _M_ht.insert_unique(__f, __l); }
162 #endif /*_STLP_MEMBER_TEMPLATES */
165 size_type size() const { return _M_ht.size(); }
166 size_type max_size() const { return _M_ht.max_size(); }
167 bool empty() const { return _M_ht.empty(); }
168 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
170 iterator begin() { return _M_ht.begin(); }
171 iterator end() { return _M_ht.end(); }
172 const_iterator begin() const { return _M_ht.begin(); }
173 const_iterator end() const { return _M_ht.end(); }
176 pair<iterator, bool> insert(const value_type& __obj)
177 { return _M_ht.insert_unique(__obj); }
178 #if defined (_STLP_MEMBER_TEMPLATES)
179 template <class _InputIterator>
180 void insert(_InputIterator __f, _InputIterator __l)
182 void insert(const_iterator __f, const_iterator __l)
183 {_M_ht.insert_unique(__f, __l); }
184 void insert(const value_type* __f, const value_type* __l)
186 { _M_ht.insert_unique(__f,__l); }
188 pair<iterator, bool> insert_noresize(const value_type& __obj)
189 { return _M_ht.insert_unique_noresize(__obj); }
191 _STLP_TEMPLATE_FOR_CONT_EXT
192 iterator find(const _KT& __key) { return _M_ht.find(__key); }
193 _STLP_TEMPLATE_FOR_CONT_EXT
194 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
196 _STLP_TEMPLATE_FOR_CONT_EXT
197 size_type count(const _KT& __key) const { return _M_ht.count(__key); }
199 _STLP_TEMPLATE_FOR_CONT_EXT
200 pair<iterator, iterator> equal_range(const _KT& __key)
201 { return _M_ht.equal_range(__key); }
202 _STLP_TEMPLATE_FOR_CONT_EXT
203 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
204 { return _M_ht.equal_range(__key); }
206 _STLP_TEMPLATE_FOR_CONT_EXT
207 size_type erase(const _KT& __key) {return _M_ht.erase(__key); }
208 void erase(iterator __it) { _M_ht.erase(__it); }
209 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
210 void clear() { _M_ht.clear(); }
213 void resize(size_type __hint) { _M_ht.resize(__hint); }
214 size_type bucket_count() const { return _M_ht.bucket_count(); }
215 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
216 size_type elems_in_bucket(size_type __n) const
217 { return _M_ht.elems_in_bucket(__n); }
220 //Specific iterator traits creation
221 _STLP_CREATE_HASH_ITERATOR_TRAITS(HashMultisetTraitsT, Const_traits)
223 template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>),
224 _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Value>),
225 _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
227 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
228 : public __stlport_class<hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> >
231 typedef hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
232 //Specific iterator traits creation
233 typedef _STLP_PRIV _HashMultisetTraitsT<_Value> _HashMultisetTraits;
235 typedef hashtable<_Value, _Value, _HashFcn,
236 _HashMultisetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht;
238 typedef typename _Ht::key_type key_type;
239 typedef typename _Ht::value_type value_type;
240 typedef typename _Ht::hasher hasher;
241 typedef typename _Ht::key_equal key_equal;
243 typedef typename _Ht::size_type size_type;
244 typedef typename _Ht::difference_type difference_type;
245 typedef typename _Ht::pointer pointer;
246 typedef typename _Ht::const_pointer const_pointer;
247 typedef typename _Ht::reference reference;
248 typedef typename _Ht::const_reference const_reference;
250 typedef typename _Ht::iterator iterator;
251 typedef typename _Ht::const_iterator const_iterator;
253 typedef typename _Ht::allocator_type allocator_type;
255 hasher hash_funct() const { return _M_ht.hash_funct(); }
256 key_equal key_eq() const { return _M_ht.key_eq(); }
257 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
261 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
265 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
266 explicit hash_multiset(size_type __n)
267 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
268 hash_multiset(size_type __n, const hasher& __hf)
269 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
270 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql)
271 : _M_ht(__n, __hf, __eql, allocator_type()) {}
272 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
273 const allocator_type& __a)
274 : _M_ht(__n, __hf, __eql, __a) {}
276 hash_multiset(__move_source<_Self> src)
277 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {}
279 #if defined (_STLP_MEMBER_TEMPLATES)
280 template <class _InputIterator>
281 hash_multiset(_InputIterator __f, _InputIterator __l)
282 : _M_ht(100, hasher(), key_equal(), allocator_type())
283 { _M_ht.insert_equal(__f, __l); }
284 template <class _InputIterator>
285 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
286 : _M_ht(__n, hasher(), key_equal(), allocator_type())
287 { _M_ht.insert_equal(__f, __l); }
288 template <class _InputIterator>
289 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
291 : _M_ht(__n, __hf, key_equal(), allocator_type())
292 { _M_ht.insert_equal(__f, __l); }
294 template <class _InputIterator>
295 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
296 const hasher& __hf, const key_equal& __eql,
297 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
298 : _M_ht(__n, __hf, __eql, __a)
299 { _M_ht.insert_equal(__f, __l); }
300 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
301 template <class _InputIterator>
302 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
303 const hasher& __hf, const key_equal& __eql)
304 : _M_ht(__n, __hf, __eql, allocator_type())
305 { _M_ht.insert_equal(__f, __l); }
308 hash_multiset(const value_type* __f, const value_type* __l)
309 : _M_ht(100, hasher(), key_equal(), allocator_type())
310 { _M_ht.insert_equal(__f, __l); }
311 hash_multiset(const value_type* __f, const value_type* __l, size_type __n)
312 : _M_ht(__n, hasher(), key_equal(), allocator_type())
313 { _M_ht.insert_equal(__f, __l); }
314 hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
316 : _M_ht(__n, __hf, key_equal(), allocator_type())
317 { _M_ht.insert_equal(__f, __l); }
318 hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
319 const hasher& __hf, const key_equal& __eql,
320 const allocator_type& __a = allocator_type())
321 : _M_ht(__n, __hf, __eql, __a)
322 { _M_ht.insert_equal(__f, __l); }
324 hash_multiset(const_iterator __f, const_iterator __l)
325 : _M_ht(100, hasher(), key_equal(), allocator_type())
326 { _M_ht.insert_equal(__f, __l); }
327 hash_multiset(const_iterator __f, const_iterator __l, size_type __n)
328 : _M_ht(__n, hasher(), key_equal(), allocator_type())
329 { _M_ht.insert_equal(__f, __l); }
330 hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
332 : _M_ht(__n, __hf, key_equal(), allocator_type())
333 { _M_ht.insert_equal(__f, __l); }
334 hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
335 const hasher& __hf, const key_equal& __eql,
336 const allocator_type& __a = allocator_type())
337 : _M_ht(__n, __hf, __eql, __a)
338 { _M_ht.insert_equal(__f, __l); }
339 #endif /*_STLP_MEMBER_TEMPLATES */
342 size_type size() const { return _M_ht.size(); }
343 size_type max_size() const { return _M_ht.max_size(); }
344 bool empty() const { return _M_ht.empty(); }
345 void swap(_Self& hs) { _M_ht.swap(hs._M_ht); }
347 iterator begin() { return _M_ht.begin(); }
348 iterator end() { return _M_ht.end(); }
349 const_iterator begin() const { return _M_ht.begin(); }
350 const_iterator end() const { return _M_ht.end(); }
353 iterator insert(const value_type& __obj) { return _M_ht.insert_equal(__obj); }
354 #if defined (_STLP_MEMBER_TEMPLATES)
355 template <class _InputIterator>
356 void insert(_InputIterator __f, _InputIterator __l)
357 { _M_ht.insert_equal(__f,__l); }
359 void insert(const value_type* __f, const value_type* __l)
360 { _M_ht.insert_equal(__f,__l); }
361 void insert(const_iterator __f, const_iterator __l)
362 { _M_ht.insert_equal(__f, __l); }
363 #endif /*_STLP_MEMBER_TEMPLATES */
364 iterator insert_noresize(const value_type& __obj)
365 { return _M_ht.insert_equal_noresize(__obj); }
367 _STLP_TEMPLATE_FOR_CONT_EXT
368 iterator find(const _KT& __key) { return _M_ht.find(__key); }
370 _STLP_TEMPLATE_FOR_CONT_EXT
371 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
373 _STLP_TEMPLATE_FOR_CONT_EXT
374 size_type count(const _KT& __key) const { return _M_ht.count(__key); }
376 _STLP_TEMPLATE_FOR_CONT_EXT
377 pair<iterator, iterator> equal_range(const _KT& __key)
378 { return _M_ht.equal_range(__key); }
379 _STLP_TEMPLATE_FOR_CONT_EXT
380 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
381 { return _M_ht.equal_range(__key); }
383 _STLP_TEMPLATE_FOR_CONT_EXT
384 size_type erase(const _KT& __key) {return _M_ht.erase(__key); }
385 void erase(iterator __it) { _M_ht.erase(__it); }
386 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
387 void clear() { _M_ht.clear(); }
390 void resize(size_type __hint) { _M_ht.resize(__hint); }
391 size_type bucket_count() const { return _M_ht.bucket_count(); }
392 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
393 size_type elems_in_bucket(size_type __n) const
394 { return _M_ht.elems_in_bucket(__n); }
397 #define _STLP_TEMPLATE_HEADER template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
398 #define _STLP_TEMPLATE_CONTAINER hash_set<_Value,_HashFcn,_EqualKey,_Alloc>
400 #include <stl/_relops_hash_cont.h>
402 #undef _STLP_TEMPLATE_CONTAINER
403 #define _STLP_TEMPLATE_CONTAINER hash_multiset<_Value,_HashFcn,_EqualKey,_Alloc>
404 #include <stl/_relops_hash_cont.h>
406 #undef _STLP_TEMPLATE_CONTAINER
407 #undef _STLP_TEMPLATE_HEADER
409 // Specialization of insert_iterator so that it will work for hash_set
410 // and hash_multiset.
412 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
413 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
414 struct __move_traits<hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > :
415 _STLP_PRIV __move_traits_aux<typename hash_set<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht>
418 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
419 struct __move_traits<hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > :
420 _STLP_PRIV __move_traits_aux<typename hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht>
423 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
424 class insert_iterator<hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
426 typedef hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
427 _Container* container;
429 typedef _Container container_type;
430 typedef output_iterator_tag iterator_category;
431 typedef void value_type;
432 typedef void difference_type;
433 typedef void pointer;
434 typedef void reference;
436 insert_iterator(_Container& __x) : container(&__x) {}
437 insert_iterator(_Container& __x, typename _Container::iterator)
439 insert_iterator<_Container>&
440 operator=(const typename _Container::value_type& __val) {
441 container->insert(__val);
444 insert_iterator<_Container>& operator*() { return *this; }
445 insert_iterator<_Container>& operator++() { return *this; }
446 insert_iterator<_Container>& operator++(int) { return *this; }
449 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
450 class insert_iterator<hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
452 typedef hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
453 _Container* container;
454 typename _Container::iterator iter;
456 typedef _Container container_type;
457 typedef output_iterator_tag iterator_category;
458 typedef void value_type;
459 typedef void difference_type;
460 typedef void pointer;
461 typedef void reference;
463 insert_iterator(_Container& __x) : container(&__x) {}
464 insert_iterator(_Container& __x, typename _Container::iterator)
466 insert_iterator<_Container>&
467 operator=(const typename _Container::value_type& __val) {
468 container->insert(__val);
471 insert_iterator<_Container>& operator*() { return *this; }
472 insert_iterator<_Container>& operator++() { return *this; }
473 insert_iterator<_Container>& operator++(int) { return *this; }
475 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
479 #endif /* _STLP_INTERNAL_HASH_SET_H */