ReactOS 0.4.15-dev-8348-gc1b9bb5
_unordered_set.h
Go to the documentation of this file.
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
28
29//Specific iterator traits creation
30_STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedSetTraitsT, Const_traits)
31
33
34template <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>) >
38#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
39 : public __stlport_class<unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> >
40#endif
41{
43 //Specific iterator traits creation
44 typedef _STLP_PRIV _UnorderedSetTraitsT<_Value> _UnorderedSetTraits;
45public:
46 typedef hashtable<_Value, _Value, _HashFcn,
48public:
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;
56 typedef typename _Ht::pointer pointer;
58 typedef typename _Ht::reference reference;
60
61 typedef typename _Ht::iterator iterator;
65
67
68 hasher hash_function() const { return _M_ht.hash_funct(); }
69 key_equal key_eq() const { return _M_ht.key_eq(); }
71
72private:
75
76public:
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)
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
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
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
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
142 iterator find(const _KT& __key) { return _M_ht.find(__key); }
144 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
145
147 size_type count(const _KT& __key) const { return _M_ht.count(__key); }
148
151 { return _M_ht.equal_range(__key); }
154 { return _M_ht.equal_range(__key); }
155
156 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
158 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); }
159 void clear() { _M_ht.clear(); }
160
165 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); }
170
171 float load_factor() const { return _M_ht.load_factor(); }
172 float max_load_factor() const { return _M_ht.max_load_factor(); }
174 void rehash(size_type __hint) { _M_ht.rehash(__hint); }
175};
176
178
179//Specific iterator traits creation
180_STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMultisetTraitsT, Const_traits)
181
183
184template <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>) >
188#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
189 : public __stlport_class<unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> >
190#endif
191{
193 //Specific iterator traits creation
194 typedef _STLP_PRIV _UnorderedMultisetTraitsT<_Value> _UnorderedMultisetTraits;
195public:
196 typedef hashtable<_Value, _Value, _HashFcn,
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;
206 typedef typename _Ht::pointer pointer;
208 typedef typename _Ht::reference reference;
210
211 typedef typename _Ht::iterator iterator;
215
217
218 hasher hash_function() const { return _M_ht.hash_funct(); }
219 key_equal key_eq() const { return _M_ht.key_eq(); }
221
222private:
225
226public:
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)
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
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
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
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); }
288#endif /*_STLP_MEMBER_TEMPLATES */
289 { _M_ht.insert_equal(__f, __l); }
290
292 iterator find(const _KT& __key) { return _M_ht.find(__key); }
294 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
295
297 size_type count(const _KT& __key) const { return _M_ht.count(__key); }
298
301 { return _M_ht.equal_range(__key); }
304 { return _M_ht.equal_range(__key); }
305
306 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
308 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); }
309 void clear() { _M_ht.clear(); }
310
315 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); }
320
321 float load_factor() const { return _M_ht.load_factor(); }
322 float max_load_factor() const { return _M_ht.max_load_factor(); }
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
331
332#undef _STLP_TEMPLATE_CONTAINER
333#define _STLP_TEMPLATE_CONTAINER unordered_multiset<_Value,_HashFcn,_EqualKey,_Alloc>
335
336#undef _STLP_TEMPLATE_CONTAINER
337#undef _STLP_TEMPLATE_HEADER
338
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)
346template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
347struct __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
351template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
352struct __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
357template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
358class insert_iterator<_STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
359protected:
361 _Container* container;
362public:
363 typedef _Container container_type;
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) {}
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
383template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
384class insert_iterator<_STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
385protected:
387 _Container* container;
388 typename _Container::iterator iter;
389public:
390 typedef _Container container_type;
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) {}
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
412
413#endif /* _STLP_INTERNAL_UNORDERED_SET_H */
414
415// Local Variables:
416// mode:C++
417// End:
418
return __n
Definition: _algo.h:75
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
#define _Alloc
Definition: _bvector.h:330
#define _STLP_PRIV
Definition: _dm.h:70
#define _STLP_CREATE_HASH_ITERATOR_TRAITS(Motif, Traits)
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
void get(int argc, const char *argv[])
Definition: cmds.c:480
size_type erase(const key_type &__key)
Definition: _hashtable.c:263
allocator_type get_allocator() const
Definition: _hashtable.h:300
key_equal key_eq() const
Definition: _hashtable.h:247
iterator insert_equal(const value_type &__obj)
Definition: _hashtable.h:412
pair< iterator, bool > insert_unique(const value_type &__obj)
Definition: _hashtable.h:407
iterator end()
Definition: _hashtable.h:377
bool empty() const
Definition: _hashtable.h:365
size_type bucket_count() const
Definition: _hashtable.h:391
float max_load_factor() const
Definition: _hashtable.h:401
size_type max_bucket_count() const
Definition: _hashtable.h:392
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__key)
Definition: _hashtable.h:534
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__key)
Definition: _hashtable.h:511
size_type max_size() const
Definition: _hashtable.h:364
void swap(_Self &__ht)
Definition: _hashtable.h:367
size_type elems_in_bucket(size_type __bucket) const
Definition: _hashtable.h:393
size_type size() const
Definition: _hashtable.h:363
void rehash(size_type __num_buckets_hint)
Definition: _hashtable.c:365
void clear()
Definition: _hashtable.c:501
iterator begin()
Definition: _hashtable.h:376
float load_factor() const
Definition: _hashtable.h:400
hasher hash_funct() const
Definition: _hashtable.h:246
_STLP_TEMPLATE_FOR_CONT_EXT size_type bucket(const _KT &__k) const
Definition: _hashtable.h:397
_STLP_TEMPLATE_FOR_CONT_EXT size_type count(const _KT &__key) const
Definition: _hashtable.h:516
output_iterator_tag iterator_category
Definition: _iterator.h:229
_Self & operator=(_Self const &__other)
Definition: _iterator.h:233
_Self & operator++()
Definition: _iterator.h:244
_Container * container
Definition: _iterator.h:225
_Container container_type
Definition: _iterator.h:228
_Self & operator*()
Definition: _iterator.h:243
void rehash(size_type __hint)
_STLP_TEMPLATE_FOR_CONT_EXT size_type bucket(const _KT &__k) const
unordered_multiset(size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
const_local_iterator end(size_type __n) const
unordered_multiset(const value_type *__f, const value_type *__l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
const_iterator begin() const
_Ht::const_local_iterator const_local_iterator
allocator_type get_allocator() const
_Ht::value_type value_type
hashtable< _Value, _Value, _HashFcn, _UnorderedMultisetTraits, _STLP_PRIV _Identity< _Value >, _EqualKey, _Alloc > _Ht
float load_factor() const
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__key)
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__key)
void erase(const_iterator __f, const_iterator __l)
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find(const _KT &__key) const
size_type bucket_count() const
_Ht::key_equal key_equal
const_iterator end() const
bool empty() const
size_type max_size() const
_STLP_TEMPLATE_FOR_CONT_EXT size_type count(const _KT &__key) const
iterator insert(const value_type &__obj)
_Ht::local_iterator local_iterator
key_equal key_eq() const
_Ht::const_pointer const_pointer
_Self & operator=(const _Self &__other)
size_type erase(const key_type &__key)
_Ht::const_reference const_reference
void insert(const_iterator __f, const_iterator __l)
unordered_multiset(__move_source< _Self > src)
_Ht::iterator iterator
void max_load_factor(float __val)
unordered_multiset< _Value, _HashFcn, _EqualKey, _Alloc > _Self
size_type max_bucket_count() const
void swap(_Self &hs)
void erase(const_iterator __it)
_Ht::difference_type difference_type
local_iterator begin(size_type __n)
_Ht::reference reference
hasher hash_function() const
_Ht::pointer pointer
_STLP_PRIV _UnorderedMultisetTraitsT< _Value > _UnorderedMultisetTraits
size_type bucket_size(size_type __n) const
local_iterator end(size_type __n)
iterator insert(const_iterator, const value_type &__obj)
unordered_multiset(const_iterator __f, const_iterator __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
void insert(const value_type *__f, const value_type *__l)
_Ht::allocator_type allocator_type
_Ht::key_type key_type
_Ht::const_iterator const_iterator
_Ht::size_type size_type
float max_load_factor() const
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range(const _KT &__key) const
const_local_iterator begin(size_type __n) const
size_type size() const
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__key)
_Ht::key_equal key_equal
_Ht::iterator iterator
_Ht::hasher hasher
unordered_set(size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
local_iterator begin(size_type __n)
void insert(const_iterator __f, const_iterator __l)
void max_load_factor(float __val)
float max_load_factor() const
unordered_set(__move_source< _Self > src)
allocator_type get_allocator() const
void insert(const value_type *__f, const value_type *__l)
_Ht::const_reference const_reference
size_type bucket_count() const
size_type bucket_size(size_type __n) const
unordered_set(const value_type *__f, const value_type *__l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
const_iterator end() const
size_type erase(const key_type &__key)
_Ht::const_pointer const_pointer
size_type max_bucket_count() const
_Ht::value_type value_type
_STLP_TEMPLATE_FOR_CONT_EXT size_type count(const _KT &__key) const
const_local_iterator begin(size_type __n) const
bool empty() const
size_type max_size() const
_Ht::reference reference
const_local_iterator end(size_type __n) const
const_iterator begin() const
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__key)
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find(const _KT &__key) const
_Ht::local_iterator local_iterator
float load_factor() const
size_type size() const
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range(const _KT &__key) const
_Ht::key_type key_type
_Ht::pointer pointer
_STLP_PRIV _UnorderedSetTraitsT< _Value > _UnorderedSetTraits
unordered_set< _Value, _HashFcn, _EqualKey, _Alloc > _Self
iterator begin()
_Ht::allocator_type allocator_type
unordered_set(const_iterator __f, const_iterator __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
pair< iterator, bool > insert(const value_type &__obj)
key_equal key_eq() const
_Ht::const_iterator const_iterator
void swap(_Self &__hs)
void rehash(size_type __hint)
iterator end()
_Self & operator=(const _Self &__other)
void erase(const_iterator __f, const_iterator __l)
hasher hash_function() const
void erase(const_iterator __it)
_STLP_TEMPLATE_FOR_CONT_EXT size_type bucket(const _KT &__k) const
_Ht::difference_type difference_type
local_iterator end(size_type __n)
hashtable< _Value, _Value, _HashFcn, _UnorderedSetTraits, _STLP_PRIV _Identity< _Value >, _EqualKey, _Alloc > _Ht
iterator insert(const_iterator, const value_type &__obj)
_Ht::const_local_iterator const_local_iterator
_Ht::size_type size_type
int _Value
Definition: setjmp.h:214
#define _STLP_TEMPLATE_FOR_CONT_EXT
Definition: features.h:623
#define _STLP_BEGIN_TR1_NAMESPACE
Definition: features.h:502
#define _STLP_TR1
Definition: features.h:518
#define _STLP_KEY_TYPE_FOR_CONT_EXT(type)
Definition: features.h:622
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
#define _STLP_END_NAMESPACE
Definition: features.h:503
GLenum src
Definition: glext.h:6340
GLsizei const GLvoid * pointer
Definition: glext.h:5848
GLint reference
Definition: glext.h:11729
if(dx< 0)
Definition: linetemp.h:194
#define swap(a, b)
Definition: qsort.c:63
Definition: _pair.h:47
static int insert
Definition: xmllint.c:138