1 /*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
8 *
9 * Copyright (c) 1997
10 * Moscow Center for SPARC Technology
11 *
12 * Copyright (c) 1999
13 * Boris Fomitchev
14 *
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
17 *
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.
23 *
24 */
25
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
28 */
29
30 #ifndef _STLP_INTERNAL_HASH_SET_H
31 #define _STLP_INTERNAL_HASH_SET_H
32
33 #ifndef _STLP_INTERNAL_HASHTABLE_H
34 # include <stl/_hashtable.h>
35 #endif
36
37 _STLP_BEGIN_NAMESPACE
38
39 //Specific iterator traits creation
_STLP_CREATE_HASH_ITERATOR_TRAITS(HashSetTraitsT,Const_traits)40 _STLP_CREATE_HASH_ITERATOR_TRAITS(HashSetTraitsT, Const_traits)
41
42 template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>),
43 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Value>),
44 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) >
45 class hash_set
46 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
47 : public __stlport_class<hash_set<_Value, _HashFcn, _EqualKey, _Alloc> >
48 #endif
49 {
50 typedef hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
51 //Specific iterator traits creation
52 typedef _STLP_PRIV _HashSetTraitsT<_Value> _HashSetTraits;
53 public:
54 typedef hashtable<_Value, _Value, _HashFcn,
55 _HashSetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht;
56 public:
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;
61
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;
68
69 typedef typename _Ht::iterator iterator;
70 typedef typename _Ht::const_iterator const_iterator;
71
72 typedef typename _Ht::allocator_type allocator_type;
73
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(); }
77
78 private:
79 _Ht _M_ht;
80 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
81
82 public:
83 hash_set()
84 : _M_ht(0, 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())
92 #else
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)
97 #endif
98 : _M_ht(__n, __hf, __eql, __a) {}
99
100 #if !defined (_STLP_NO_MOVE_SEMANTIC)
101 hash_set(__move_source<_Self> src)
102 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {}
103 #endif
104
105 #if defined (_STLP_MEMBER_TEMPLATES)
106 template <class _InputIterator>
107 hash_set(_InputIterator __f, _InputIterator __l)
108 : _M_ht(0, hasher(), key_equal(), allocator_type())
109 { _M_ht.insert_unique(__f, __l); }
110 template <class _InputIterator>
111 hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
112 : _M_ht(__n, hasher(), key_equal(), allocator_type())
113 { _M_ht.insert_unique(__f, __l); }
114 template <class _InputIterator>
115 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
116 const hasher& __hf)
117 : _M_ht(__n, __hf, key_equal(), allocator_type())
118 { _M_ht.insert_unique(__f, __l); }
119 template <class _InputIterator>
120 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
121 const hasher& __hf, const key_equal& __eql,
122 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
123 : _M_ht(__n, __hf, __eql, __a)
124 { _M_ht.insert_unique(__f, __l); }
125 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
126 template <class _InputIterator>
127 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
128 const hasher& __hf, const key_equal& __eql)
129 : _M_ht(__n, __hf, __eql, allocator_type())
130 { _M_ht.insert_unique(__f, __l); }
131 # endif
132 #else
133 hash_set(const value_type* __f, const value_type* __l)
134 : _M_ht(0, hasher(), key_equal(), allocator_type())
135 { _M_ht.insert_unique(__f, __l); }
136 hash_set(const value_type* __f, const value_type* __l, size_type __n)
137 : _M_ht(__n, hasher(), key_equal(), allocator_type())
138 { _M_ht.insert_unique(__f, __l); }
139 hash_set(const value_type* __f, const value_type* __l, size_type __n,
140 const hasher& __hf)
141 : _M_ht(__n, __hf, key_equal(), allocator_type())
142 { _M_ht.insert_unique(__f, __l); }
143 hash_set(const value_type* __f, const value_type* __l, size_type __n,
144 const hasher& __hf, const key_equal& __eql,
145 const allocator_type& __a = allocator_type())
146 : _M_ht(__n, __hf, __eql, __a)
147 { _M_ht.insert_unique(__f, __l); }
148
149 hash_set(const_iterator __f, const_iterator __l)
150 : _M_ht(0, hasher(), key_equal(), allocator_type())
151 { _M_ht.insert_unique(__f, __l); }
152 hash_set(const_iterator __f, const_iterator __l, size_type __n)
153 : _M_ht(__n, hasher(), key_equal(), allocator_type())
154 { _M_ht.insert_unique(__f, __l); }
155 hash_set(const_iterator __f, const_iterator __l, size_type __n,
156 const hasher& __hf)
157 : _M_ht(__n, __hf, key_equal(), allocator_type())
158 { _M_ht.insert_unique(__f, __l); }
159 hash_set(const_iterator __f, const_iterator __l, size_type __n,
160 const hasher& __hf, const key_equal& __eql,
161 const allocator_type& __a = allocator_type())
162 : _M_ht(__n, __hf, __eql, __a)
163 { _M_ht.insert_unique(__f, __l); }
164 #endif /*_STLP_MEMBER_TEMPLATES */
165
166 public:
167 size_type size() const { return _M_ht.size(); }
168 size_type max_size() const { return _M_ht.max_size(); }
169 bool empty() const { return _M_ht.empty(); }
170 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
171 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
172 void _M_swap_workaround(_Self& __x) { swap(__x); }
173 #endif
174
175 iterator begin() { return _M_ht.begin(); }
176 iterator end() { return _M_ht.end(); }
177 const_iterator begin() const { return _M_ht.begin(); }
178 const_iterator end() const { return _M_ht.end(); }
179
180 public:
181 pair<iterator, bool> insert(const value_type& __obj)
182 { return _M_ht.insert_unique(__obj); }
183 #if defined (_STLP_MEMBER_TEMPLATES)
184 template <class _InputIterator>
185 void insert(_InputIterator __f, _InputIterator __l)
186 #else
187 void insert(const_iterator __f, const_iterator __l)
188 {_M_ht.insert_unique(__f, __l); }
189 void insert(const value_type* __f, const value_type* __l)
190 #endif
191 { _M_ht.insert_unique(__f,__l); }
192
193 pair<iterator, bool> insert_noresize(const value_type& __obj)
194 { return _M_ht.insert_unique_noresize(__obj); }
195
196 _STLP_TEMPLATE_FOR_CONT_EXT
197 iterator find(const _KT& __key) { return _M_ht.find(__key); }
198 _STLP_TEMPLATE_FOR_CONT_EXT
199 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
200
201 _STLP_TEMPLATE_FOR_CONT_EXT
202 size_type count(const _KT& __key) const { return _M_ht.count(__key); }
203
204 _STLP_TEMPLATE_FOR_CONT_EXT
205 pair<iterator, iterator> equal_range(const _KT& __key)
206 { return _M_ht.equal_range(__key); }
207 _STLP_TEMPLATE_FOR_CONT_EXT
208 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
209 { return _M_ht.equal_range(__key); }
210
211 _STLP_TEMPLATE_FOR_CONT_EXT
212 size_type erase(const _KT& __key) {return _M_ht.erase(__key); }
213 void erase(iterator __it) { _M_ht.erase(__it); }
214 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
215 void clear() { _M_ht.clear(); }
216
217 public:
218 void resize(size_type __hint) { _M_ht.resize(__hint); }
219 size_type bucket_count() const { return _M_ht.bucket_count(); }
220 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
221 size_type elems_in_bucket(size_type __n) const
222 { return _M_ht.elems_in_bucket(__n); }
223 };
224
225 //Specific iterator traits creation
_STLP_CREATE_HASH_ITERATOR_TRAITS(HashMultisetTraitsT,Const_traits)226 _STLP_CREATE_HASH_ITERATOR_TRAITS(HashMultisetTraitsT, Const_traits)
227
228 template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>),
229 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Value>),
230 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) >
231 class hash_multiset
232 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
233 : public __stlport_class<hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> >
234 #endif
235 {
236 typedef hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
237 //Specific iterator traits creation
238 typedef _STLP_PRIV _HashMultisetTraitsT<_Value> _HashMultisetTraits;
239 public:
240 typedef hashtable<_Value, _Value, _HashFcn,
241 _HashMultisetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht;
242
243 typedef typename _Ht::key_type key_type;
244 typedef typename _Ht::value_type value_type;
245 typedef typename _Ht::hasher hasher;
246 typedef typename _Ht::key_equal key_equal;
247
248 typedef typename _Ht::size_type size_type;
249 typedef typename _Ht::difference_type difference_type;
250 typedef typename _Ht::pointer pointer;
251 typedef typename _Ht::const_pointer const_pointer;
252 typedef typename _Ht::reference reference;
253 typedef typename _Ht::const_reference const_reference;
254
255 typedef typename _Ht::iterator iterator;
256 typedef typename _Ht::const_iterator const_iterator;
257
258 typedef typename _Ht::allocator_type allocator_type;
259
260 hasher hash_funct() const { return _M_ht.hash_funct(); }
261 key_equal key_eq() const { return _M_ht.key_eq(); }
262 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
263
264 private:
265 _Ht _M_ht;
266 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
267
268 public:
269 hash_multiset()
270 : _M_ht(0, hasher(), key_equal(), allocator_type()) {}
271 explicit hash_multiset(size_type __n)
272 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
273 hash_multiset(size_type __n, const hasher& __hf)
274 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
275 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql)
276 : _M_ht(__n, __hf, __eql, allocator_type()) {}
277 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
278 const allocator_type& __a)
279 : _M_ht(__n, __hf, __eql, __a) {}
280
281 #if !defined (_STLP_NO_MOVE_SEMANTIC)
282 hash_multiset(__move_source<_Self> src)
283 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {}
284 #endif
285
286 #if defined (_STLP_MEMBER_TEMPLATES)
287 template <class _InputIterator>
288 hash_multiset(_InputIterator __f, _InputIterator __l)
289 : _M_ht(0, hasher(), key_equal(), allocator_type())
290 { _M_ht.insert_equal(__f, __l); }
291 template <class _InputIterator>
292 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
293 : _M_ht(__n, hasher(), key_equal(), allocator_type())
294 { _M_ht.insert_equal(__f, __l); }
295 template <class _InputIterator>
296 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
297 const hasher& __hf)
298 : _M_ht(__n, __hf, key_equal(), allocator_type())
299 { _M_ht.insert_equal(__f, __l); }
300
301 template <class _InputIterator>
302 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
303 const hasher& __hf, const key_equal& __eql,
304 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
305 : _M_ht(__n, __hf, __eql, __a)
306 { _M_ht.insert_equal(__f, __l); }
307 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
308 template <class _InputIterator>
309 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
310 const hasher& __hf, const key_equal& __eql)
311 : _M_ht(__n, __hf, __eql, allocator_type())
312 { _M_ht.insert_equal(__f, __l); }
313 # endif
314 #else
315 hash_multiset(const value_type* __f, const value_type* __l)
316 : _M_ht(0, hasher(), 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 : _M_ht(__n, hasher(), key_equal(), allocator_type())
320 { _M_ht.insert_equal(__f, __l); }
321 hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
322 const hasher& __hf)
323 : _M_ht(__n, __hf, key_equal(), allocator_type())
324 { _M_ht.insert_equal(__f, __l); }
325 hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
326 const hasher& __hf, const key_equal& __eql,
327 const allocator_type& __a = allocator_type())
328 : _M_ht(__n, __hf, __eql, __a)
329 { _M_ht.insert_equal(__f, __l); }
330
331 hash_multiset(const_iterator __f, const_iterator __l)
332 : _M_ht(0, hasher(), key_equal(), allocator_type())
333 { _M_ht.insert_equal(__f, __l); }
334 hash_multiset(const_iterator __f, const_iterator __l, size_type __n)
335 : _M_ht(__n, hasher(), key_equal(), allocator_type())
336 { _M_ht.insert_equal(__f, __l); }
337 hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
338 const hasher& __hf)
339 : _M_ht(__n, __hf, key_equal(), allocator_type())
340 { _M_ht.insert_equal(__f, __l); }
341 hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
342 const hasher& __hf, const key_equal& __eql,
343 const allocator_type& __a = allocator_type())
344 : _M_ht(__n, __hf, __eql, __a)
345 { _M_ht.insert_equal(__f, __l); }
346 #endif /*_STLP_MEMBER_TEMPLATES */
347
348 public:
349 size_type size() const { return _M_ht.size(); }
350 size_type max_size() const { return _M_ht.max_size(); }
351 bool empty() const { return _M_ht.empty(); }
352 void swap(_Self& hs) { _M_ht.swap(hs._M_ht); }
353 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
354 void _M_swap_workaround(_Self& __x) { swap(__x); }
355 #endif
356
357 iterator begin() { return _M_ht.begin(); }
358 iterator end() { return _M_ht.end(); }
359 const_iterator begin() const { return _M_ht.begin(); }
360 const_iterator end() const { return _M_ht.end(); }
361
362 public:
363 iterator insert(const value_type& __obj) { return _M_ht.insert_equal(__obj); }
364 #if defined (_STLP_MEMBER_TEMPLATES)
365 template <class _InputIterator>
366 void insert(_InputIterator __f, _InputIterator __l)
367 { _M_ht.insert_equal(__f,__l); }
368 #else
369 void insert(const value_type* __f, const value_type* __l)
370 { _M_ht.insert_equal(__f,__l); }
371 void insert(const_iterator __f, const_iterator __l)
372 { _M_ht.insert_equal(__f, __l); }
373 #endif /*_STLP_MEMBER_TEMPLATES */
374 iterator insert_noresize(const value_type& __obj)
375 { return _M_ht.insert_equal_noresize(__obj); }
376
377 _STLP_TEMPLATE_FOR_CONT_EXT
378 iterator find(const _KT& __key) { return _M_ht.find(__key); }
379
380 _STLP_TEMPLATE_FOR_CONT_EXT
381 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
382
383 _STLP_TEMPLATE_FOR_CONT_EXT
384 size_type count(const _KT& __key) const { return _M_ht.count(__key); }
385
386 _STLP_TEMPLATE_FOR_CONT_EXT
387 pair<iterator, iterator> equal_range(const _KT& __key)
388 { return _M_ht.equal_range(__key); }
389 _STLP_TEMPLATE_FOR_CONT_EXT
390 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
391 { return _M_ht.equal_range(__key); }
392
393 _STLP_TEMPLATE_FOR_CONT_EXT
394 size_type erase(const _KT& __key) {return _M_ht.erase(__key); }
395 void erase(iterator __it) { _M_ht.erase(__it); }
396 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
397 void clear() { _M_ht.clear(); }
398
399 public:
400 void resize(size_type __hint) { _M_ht.resize(__hint); }
401 size_type bucket_count() const { return _M_ht.bucket_count(); }
402 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
403 size_type elems_in_bucket(size_type __n) const
404 { return _M_ht.elems_in_bucket(__n); }
405 };
406
407 #define _STLP_TEMPLATE_HEADER template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
408 #define _STLP_TEMPLATE_CONTAINER hash_set<_Value,_HashFcn,_EqualKey,_Alloc>
409
410 #include <stl/_relops_hash_cont.h>
411
412 #undef _STLP_TEMPLATE_CONTAINER
413 #define _STLP_TEMPLATE_CONTAINER hash_multiset<_Value,_HashFcn,_EqualKey,_Alloc>
414 #include <stl/_relops_hash_cont.h>
415
416 #undef _STLP_TEMPLATE_CONTAINER
417 #undef _STLP_TEMPLATE_HEADER
418
419 // Specialization of insert_iterator so that it will work for hash_set
420 // and hash_multiset.
421
422 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
423 # if !defined (_STLP_NO_MOVE_SEMANTIC)
424 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
425 struct __move_traits<hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > :
426 _STLP_PRIV __move_traits_aux<typename hash_set<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht>
427 {};
428
429 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
430 struct __move_traits<hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > :
431 _STLP_PRIV __move_traits_aux<typename hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht>
432 {};
433 # endif
434
435 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
436 class insert_iterator<hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
437 protected:
438 typedef hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
439 _Container* container;
440 public:
441 typedef _Container container_type;
442 typedef output_iterator_tag iterator_category;
443 typedef void value_type;
444 typedef void difference_type;
445 typedef void pointer;
446 typedef void reference;
447
448 insert_iterator(_Container& __x) : container(&__x) {}
449 insert_iterator(_Container& __x, typename _Container::iterator)
450 : container(&__x) {}
451 insert_iterator<_Container>&
452 operator=(const typename _Container::value_type& __val) {
453 container->insert(__val);
454 return *this;
455 }
456 insert_iterator<_Container>& operator*() { return *this; }
457 insert_iterator<_Container>& operator++() { return *this; }
458 insert_iterator<_Container>& operator++(int) { return *this; }
459 };
460
461 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
462 class insert_iterator<hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
463 protected:
464 typedef hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
465 _Container* container;
466 typename _Container::iterator iter;
467 public:
468 typedef _Container container_type;
469 typedef output_iterator_tag iterator_category;
470 typedef void value_type;
471 typedef void difference_type;
472 typedef void pointer;
473 typedef void reference;
474
475 insert_iterator(_Container& __x) : container(&__x) {}
476 insert_iterator(_Container& __x, typename _Container::iterator)
477 : container(&__x) {}
478 insert_iterator<_Container>&
479 operator=(const typename _Container::value_type& __val) {
480 container->insert(__val);
481 return *this;
482 }
483 insert_iterator<_Container>& operator*() { return *this; }
484 insert_iterator<_Container>& operator++() { return *this; }
485 insert_iterator<_Container>& operator++(int) { return *this; }
486 };
487 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
488
489 _STLP_END_NAMESPACE
490
491 #endif /* _STLP_INTERNAL_HASH_SET_H */
492
493 // Local Variables:
494 // mode:C++
495 // End:
496