1 /*
2 * Copyright (c) 2004
3 * Francois Dumont
4 *
5 * This material is provided "as is", with absolutely no warranty expressed
6 * or implied. Any use is at your own risk.
7 *
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.
13 *
14 */
15
16 /* NOTE: This is an internal header file, included by other STL headers.
17 * You should not attempt to use it directly.
18 */
19
20 #ifndef _STLP_INTERNAL_UNORDERED_SET_H
21 #define _STLP_INTERNAL_UNORDERED_SET_H
22
23 #ifndef _STLP_INTERNAL_HASHTABLE_H
24 # include <stl/_hashtable.h>
25 #endif
26
27 _STLP_BEGIN_NAMESPACE
28
29 //Specific iterator traits creation
_STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedSetTraitsT,Const_traits)30 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedSetTraitsT, Const_traits)
31
32 _STLP_BEGIN_TR1_NAMESPACE
33
34 template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>),
35 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Value>),
36 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) >
37 class unordered_set
38 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
39 : public __stlport_class<unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> >
40 #endif
41 {
42 typedef unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
43 //Specific iterator traits creation
44 typedef _STLP_PRIV _UnorderedSetTraitsT<_Value> _UnorderedSetTraits;
45 public:
46 typedef hashtable<_Value, _Value, _HashFcn,
47 _UnorderedSetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht;
48 public:
49 typedef typename _Ht::key_type key_type;
50 typedef typename _Ht::value_type value_type;
51 typedef typename _Ht::hasher hasher;
52 typedef typename _Ht::key_equal key_equal;
53
54 typedef typename _Ht::size_type size_type;
55 typedef typename _Ht::difference_type difference_type;
56 typedef typename _Ht::pointer pointer;
57 typedef typename _Ht::const_pointer const_pointer;
58 typedef typename _Ht::reference reference;
59 typedef typename _Ht::const_reference const_reference;
60
61 typedef typename _Ht::iterator iterator;
62 typedef typename _Ht::const_iterator const_iterator;
63 typedef typename _Ht::local_iterator local_iterator;
64 typedef typename _Ht::const_local_iterator const_local_iterator;
65
66 typedef typename _Ht::allocator_type allocator_type;
67
68 hasher hash_function() const { return _M_ht.hash_funct(); }
69 key_equal key_eq() const { return _M_ht.key_eq(); }
70 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
71
72 private:
73 _Ht _M_ht;
74 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
75
76 public:
77 explicit unordered_set(size_type __n = 0, const hasher& __hf = hasher(),
78 const key_equal& __eql = key_equal(),
79 const allocator_type& __a = allocator_type())
80 : _M_ht(__n, __hf, __eql, __a) {}
81
82 #if !defined (_STLP_NO_MOVE_SEMANTIC)
83 unordered_set(__move_source<_Self> src)
84 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {}
85 #endif
86
87 #if defined (_STLP_MEMBER_TEMPLATES)
88 template <class _InputIterator>
89 unordered_set(_InputIterator __f, _InputIterator __l,
90 size_type __n = 0, const hasher& __hf = hasher(),
91 const key_equal& __eql = key_equal(),
92 const allocator_type& __a = allocator_type())
93 : _M_ht(__n, __hf, __eql, __a)
94 { _M_ht.insert_unique(__f, __l); }
95 #else
96 unordered_set(const value_type* __f, const value_type* __l,
97 size_type __n = 0, const hasher& __hf = hasher(),
98 const key_equal& __eql = key_equal(),
99 const allocator_type& __a = allocator_type())
100 : _M_ht(__n, __hf, __eql, __a)
101 { _M_ht.insert_unique(__f, __l); }
102
103 unordered_set(const_iterator __f, const_iterator __l,
104 size_type __n = 0, const hasher& __hf = hasher(),
105 const key_equal& __eql = key_equal(),
106 const allocator_type& __a = allocator_type())
107 : _M_ht(__n, __hf, __eql, __a)
108 { _M_ht.insert_unique(__f, __l); }
109 #endif /*_STLP_MEMBER_TEMPLATES */
110
111 _Self& operator = (const _Self& __other)
112 { _M_ht = __other._M_ht; return *this; }
113
114 size_type size() const { return _M_ht.size(); }
115 size_type max_size() const { return _M_ht.max_size(); }
116 bool empty() const { return _M_ht.empty(); }
117 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
118 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
119 void _M_swap_workaround(_Self& __x) { swap(__x); }
120 #endif
121
122 iterator begin() { return _M_ht.begin(); }
123 iterator end() { return _M_ht.end(); }
124 const_iterator begin() const { return _M_ht.begin(); }
125 const_iterator end() const { return _M_ht.end(); }
126
127 pair<iterator, bool> insert(const value_type& __obj)
128 { return _M_ht.insert_unique(__obj); }
129 iterator insert(const_iterator /*__hint*/, const value_type& __obj)
130 { return _M_ht.insert_unique(__obj); }
131 #if defined (_STLP_MEMBER_TEMPLATES)
132 template <class _InputIterator>
133 void insert(_InputIterator __f, _InputIterator __l)
134 #else
135 void insert(const_iterator __f, const_iterator __l)
136 {_M_ht.insert_unique(__f, __l); }
137 void insert(const value_type* __f, const value_type* __l)
138 #endif
139 { _M_ht.insert_unique(__f,__l); }
140
141 _STLP_TEMPLATE_FOR_CONT_EXT
142 iterator find(const _KT& __key) { return _M_ht.find(__key); }
143 _STLP_TEMPLATE_FOR_CONT_EXT
144 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
145
146 _STLP_TEMPLATE_FOR_CONT_EXT
147 size_type count(const _KT& __key) const { return _M_ht.count(__key); }
148
149 _STLP_TEMPLATE_FOR_CONT_EXT
150 pair<iterator, iterator> equal_range(const _KT& __key)
151 { return _M_ht.equal_range(__key); }
152 _STLP_TEMPLATE_FOR_CONT_EXT
153 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
154 { return _M_ht.equal_range(__key); }
155
156 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
157 void erase(const_iterator __it) { _M_ht.erase(__it); }
158 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); }
159 void clear() { _M_ht.clear(); }
160
161 size_type bucket_count() const { return _M_ht.bucket_count(); }
162 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
163 size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); }
164 _STLP_TEMPLATE_FOR_CONT_EXT
165 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); }
166 local_iterator begin(size_type __n) { return _M_ht.begin(__n); }
167 local_iterator end(size_type __n) { return _M_ht.end(__n); }
168 const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); }
169 const_local_iterator end(size_type __n) const { return _M_ht.end(__n); }
170
171 float load_factor() const { return _M_ht.load_factor(); }
172 float max_load_factor() const { return _M_ht.max_load_factor(); }
173 void max_load_factor(float __val) { _M_ht.max_load_factor(__val); }
174 void rehash(size_type __hint) { _M_ht.rehash(__hint); }
175 };
176
177 _STLP_END_NAMESPACE
178
179 //Specific iterator traits creation
_STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMultisetTraitsT,Const_traits)180 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMultisetTraitsT, Const_traits)
181
182 _STLP_BEGIN_TR1_NAMESPACE
183
184 template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>),
185 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Value>),
186 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) >
187 class unordered_multiset
188 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
189 : public __stlport_class<unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> >
190 #endif
191 {
192 typedef unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
193 //Specific iterator traits creation
194 typedef _STLP_PRIV _UnorderedMultisetTraitsT<_Value> _UnorderedMultisetTraits;
195 public:
196 typedef hashtable<_Value, _Value, _HashFcn,
197 _UnorderedMultisetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht;
198
199 typedef typename _Ht::key_type key_type;
200 typedef typename _Ht::value_type value_type;
201 typedef typename _Ht::hasher hasher;
202 typedef typename _Ht::key_equal key_equal;
203
204 typedef typename _Ht::size_type size_type;
205 typedef typename _Ht::difference_type difference_type;
206 typedef typename _Ht::pointer pointer;
207 typedef typename _Ht::const_pointer const_pointer;
208 typedef typename _Ht::reference reference;
209 typedef typename _Ht::const_reference const_reference;
210
211 typedef typename _Ht::iterator iterator;
212 typedef typename _Ht::const_iterator const_iterator;
213 typedef typename _Ht::local_iterator local_iterator;
214 typedef typename _Ht::const_local_iterator const_local_iterator;
215
216 typedef typename _Ht::allocator_type allocator_type;
217
218 hasher hash_function() const { return _M_ht.hash_funct(); }
219 key_equal key_eq() const { return _M_ht.key_eq(); }
220 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
221
222 private:
223 _Ht _M_ht;
224 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
225
226 public:
227 explicit unordered_multiset(size_type __n = 0, const hasher& __hf = hasher(),
228 const key_equal& __eql = key_equal(),
229 const allocator_type& __a = allocator_type())
230 : _M_ht(__n, __hf, __eql, __a) {}
231
232 #if !defined (_STLP_NO_MOVE_SEMANTIC)
233 unordered_multiset(__move_source<_Self> src)
234 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {}
235 #endif
236
237 #if defined (_STLP_MEMBER_TEMPLATES)
238 template <class _InputIterator>
239 unordered_multiset(_InputIterator __f, _InputIterator __l,
240 size_type __n = 0, const hasher& __hf = hasher(),
241 const key_equal& __eql = key_equal(),
242 const allocator_type& __a = allocator_type())
243 : _M_ht(__n, __hf, __eql, __a)
244 { _M_ht.insert_equal(__f, __l); }
245 #else
246 unordered_multiset(const value_type* __f, const value_type* __l,
247 size_type __n = 0, const hasher& __hf = hasher(),
248 const key_equal& __eql = key_equal(),
249 const allocator_type& __a = allocator_type())
250 : _M_ht(__n, __hf, __eql, __a)
251 { _M_ht.insert_equal(__f, __l); }
252
253 unordered_multiset(const_iterator __f, const_iterator __l,
254 size_type __n = 0, const hasher& __hf = hasher(),
255 const key_equal& __eql = key_equal(),
256 const allocator_type& __a = allocator_type())
257 : _M_ht(__n, __hf, __eql, __a)
258 { _M_ht.insert_equal(__f, __l); }
259 #endif /*_STLP_MEMBER_TEMPLATES */
260
261 _Self& operator = (const _Self& __other)
262 { _M_ht = __other._M_ht; return *this; }
263
264 size_type size() const { return _M_ht.size(); }
265 size_type max_size() const { return _M_ht.max_size(); }
266 bool empty() const { return _M_ht.empty(); }
267 void swap(_Self& hs) { _M_ht.swap(hs._M_ht); }
268 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
269 void _M_swap_workaround(_Self& __x) { swap(__x); }
270 #endif
271
272 iterator begin() { return _M_ht.begin(); }
273 iterator end() { return _M_ht.end(); }
274 const_iterator begin() const { return _M_ht.begin(); }
275 const_iterator end() const { return _M_ht.end(); }
276
277 iterator insert(const value_type& __obj)
278 { return _M_ht.insert_equal(__obj); }
279 iterator insert(const_iterator /*__hint*/, const value_type& __obj)
280 { return _M_ht.insert_equal(__obj); }
281 #if defined (_STLP_MEMBER_TEMPLATES)
282 template <class _InputIterator>
283 void insert(_InputIterator __f, _InputIterator __l)
284 #else
285 void insert(const value_type* __f, const value_type* __l)
286 { _M_ht.insert_equal(__f,__l); }
287 void insert(const_iterator __f, const_iterator __l)
288 #endif /*_STLP_MEMBER_TEMPLATES */
289 { _M_ht.insert_equal(__f, __l); }
290
291 _STLP_TEMPLATE_FOR_CONT_EXT
292 iterator find(const _KT& __key) { return _M_ht.find(__key); }
293 _STLP_TEMPLATE_FOR_CONT_EXT
294 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
295
296 _STLP_TEMPLATE_FOR_CONT_EXT
297 size_type count(const _KT& __key) const { return _M_ht.count(__key); }
298
299 _STLP_TEMPLATE_FOR_CONT_EXT
300 pair<iterator, iterator> equal_range(const _KT& __key)
301 { return _M_ht.equal_range(__key); }
302 _STLP_TEMPLATE_FOR_CONT_EXT
303 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
304 { return _M_ht.equal_range(__key); }
305
306 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
307 void erase(const_iterator __it) { _M_ht.erase(__it); }
308 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); }
309 void clear() { _M_ht.clear(); }
310
311 size_type bucket_count() const { return _M_ht.bucket_count(); }
312 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
313 size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); }
314 _STLP_TEMPLATE_FOR_CONT_EXT
315 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); }
316 local_iterator begin(size_type __n) { return _M_ht.begin(__n); }
317 local_iterator end(size_type __n) { return _M_ht.end(__n); }
318 const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); }
319 const_local_iterator end(size_type __n) const { return _M_ht.end(__n); }
320
321 float load_factor() const { return _M_ht.load_factor(); }
322 float max_load_factor() const { return _M_ht.max_load_factor(); }
323 void max_load_factor(float __val) { _M_ht.max_load_factor(__val); }
324 void rehash(size_type __hint) { _M_ht.rehash(__hint); }
325 };
326
327 #define _STLP_TEMPLATE_HEADER template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
328 #define _STLP_TEMPLATE_CONTAINER unordered_set<_Value,_HashFcn,_EqualKey,_Alloc>
329
330 #include <stl/_relops_hash_cont.h>
331
332 #undef _STLP_TEMPLATE_CONTAINER
333 #define _STLP_TEMPLATE_CONTAINER unordered_multiset<_Value,_HashFcn,_EqualKey,_Alloc>
334 #include <stl/_relops_hash_cont.h>
335
336 #undef _STLP_TEMPLATE_CONTAINER
337 #undef _STLP_TEMPLATE_HEADER
338
339 _STLP_END_NAMESPACE
340
341 // Specialization of insert_iterator so that it will work for unordered_set
342 // and unordered_multiset.
343
344 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
345 # if !defined (_STLP_NO_MOVE_SEMANTIC)
346 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
347 struct __move_traits<_STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > :
348 _STLP_PRIV __move_traits_aux<typename _STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht>
349 {};
350
351 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
352 struct __move_traits<_STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > :
353 _STLP_PRIV __move_traits_aux<typename _STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht>
354 {};
355 # endif
356
357 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
358 class insert_iterator<_STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
359 protected:
360 typedef _STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
361 _Container* container;
362 public:
363 typedef _Container container_type;
364 typedef output_iterator_tag iterator_category;
365 typedef void value_type;
366 typedef void difference_type;
367 typedef void pointer;
368 typedef void reference;
369
370 insert_iterator(_Container& __x) : container(&__x) {}
371 insert_iterator(_Container& __x, typename _Container::iterator)
372 : container(&__x) {}
373 insert_iterator<_Container>&
374 operator=(const typename _Container::value_type& __val) {
375 container->insert(__val);
376 return *this;
377 }
378 insert_iterator<_Container>& operator*() { return *this; }
379 insert_iterator<_Container>& operator++() { return *this; }
380 insert_iterator<_Container>& operator++(int) { return *this; }
381 };
382
383 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
384 class insert_iterator<_STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
385 protected:
386 typedef _STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
387 _Container* container;
388 typename _Container::iterator iter;
389 public:
390 typedef _Container container_type;
391 typedef output_iterator_tag iterator_category;
392 typedef void value_type;
393 typedef void difference_type;
394 typedef void pointer;
395 typedef void reference;
396
397 insert_iterator(_Container& __x) : container(&__x) {}
398 insert_iterator(_Container& __x, typename _Container::iterator)
399 : container(&__x) {}
400 insert_iterator<_Container>&
401 operator=(const typename _Container::value_type& __val) {
402 container->insert(__val);
403 return *this;
404 }
405 insert_iterator<_Container>& operator*() { return *this; }
406 insert_iterator<_Container>& operator++() { return *this; }
407 insert_iterator<_Container>& operator++(int) { return *this; }
408 };
409 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
410
411 _STLP_END_NAMESPACE
412
413 #endif /* _STLP_INTERNAL_UNORDERED_SET_H */
414
415 // Local Variables:
416 // mode:C++
417 // End:
418
419