ReactOS Development > Doxygen
_unordered_set.h
Go to the documentation of this file.
00001 /* 00002 * Copyright (c) 2004 00003 * Francois Dumont 00004 * 00005 * This material is provided "as is", with absolutely no warranty expressed 00006 * or implied. Any use is at your own risk. 00007 * 00008 * Permission to use or copy this software for any purpose is hereby granted 00009 * without fee, provided the above notices are retained on all copies. 00010 * Permission to modify the code and to distribute modified code is granted, 00011 * provided the above notices are retained, and a notice that the code was 00012 * modified is included with the above copyright notice. 00013 * 00014 */ 00015 00016 /* NOTE: This is an internal header file, included by other STL headers. 00017 * You should not attempt to use it directly. 00018 */ 00019 00020 #ifndef _STLP_INTERNAL_UNORDERED_SET_H 00021 #define _STLP_INTERNAL_UNORDERED_SET_H 00022 00023 #ifndef _STLP_INTERNAL_HASHTABLE_H 00024 # include <stl/_hashtable.h> 00025 #endif 00026 00027 _STLP_BEGIN_NAMESPACE 00028 00029 //Specific iterator traits creation 00030 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedSetTraitsT, Const_traits) 00031 00032 _STLP_BEGIN_TR1_NAMESPACE 00033 00034 template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>), 00035 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Value>), 00036 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) > 00037 class unordered_set 00038 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 00039 : public __stlport_class<unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > 00040 #endif 00041 { 00042 typedef unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> _Self; 00043 //Specific iterator traits creation 00044 typedef _STLP_PRIV _UnorderedSetTraitsT<_Value> _UnorderedSetTraits; 00045 public: 00046 typedef hashtable<_Value, _Value, _HashFcn, 00047 _UnorderedSetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht; 00048 public: 00049 typedef typename _Ht::key_type key_type; 00050 typedef typename _Ht::value_type value_type; 00051 typedef typename _Ht::hasher hasher; 00052 typedef typename _Ht::key_equal key_equal; 00053 00054 typedef typename _Ht::size_type size_type; 00055 typedef typename _Ht::difference_type difference_type; 00056 typedef typename _Ht::pointer pointer; 00057 typedef typename _Ht::const_pointer const_pointer; 00058 typedef typename _Ht::reference reference; 00059 typedef typename _Ht::const_reference const_reference; 00060 00061 typedef typename _Ht::iterator iterator; 00062 typedef typename _Ht::const_iterator const_iterator; 00063 typedef typename _Ht::local_iterator local_iterator; 00064 typedef typename _Ht::const_local_iterator const_local_iterator; 00065 00066 typedef typename _Ht::allocator_type allocator_type; 00067 00068 hasher hash_function() const { return _M_ht.hash_funct(); } 00069 key_equal key_eq() const { return _M_ht.key_eq(); } 00070 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00071 00072 private: 00073 _Ht _M_ht; 00074 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 00075 00076 public: 00077 explicit unordered_set(size_type __n = 0, const hasher& __hf = hasher(), 00078 const key_equal& __eql = key_equal(), 00079 const allocator_type& __a = allocator_type()) 00080 : _M_ht(__n, __hf, __eql, __a) {} 00081 00082 #if !defined (_STLP_NO_MOVE_SEMANTIC) 00083 unordered_set(__move_source<_Self> src) 00084 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {} 00085 #endif 00086 00087 #if defined (_STLP_MEMBER_TEMPLATES) 00088 template <class _InputIterator> 00089 unordered_set(_InputIterator __f, _InputIterator __l, 00090 size_type __n = 0, const hasher& __hf = hasher(), 00091 const key_equal& __eql = key_equal(), 00092 const allocator_type& __a = allocator_type()) 00093 : _M_ht(__n, __hf, __eql, __a) 00094 { _M_ht.insert_unique(__f, __l); } 00095 #else 00096 unordered_set(const value_type* __f, const value_type* __l, 00097 size_type __n = 0, const hasher& __hf = hasher(), 00098 const key_equal& __eql = key_equal(), 00099 const allocator_type& __a = allocator_type()) 00100 : _M_ht(__n, __hf, __eql, __a) 00101 { _M_ht.insert_unique(__f, __l); } 00102 00103 unordered_set(const_iterator __f, const_iterator __l, 00104 size_type __n = 0, const hasher& __hf = hasher(), 00105 const key_equal& __eql = key_equal(), 00106 const allocator_type& __a = allocator_type()) 00107 : _M_ht(__n, __hf, __eql, __a) 00108 { _M_ht.insert_unique(__f, __l); } 00109 #endif /*_STLP_MEMBER_TEMPLATES */ 00110 00111 _Self& operator = (const _Self& __other) 00112 { _M_ht = __other._M_ht; return *this; } 00113 00114 size_type size() const { return _M_ht.size(); } 00115 size_type max_size() const { return _M_ht.max_size(); } 00116 bool empty() const { return _M_ht.empty(); } 00117 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); } 00118 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 00119 void _M_swap_workaround(_Self& __x) { swap(__x); } 00120 #endif 00121 00122 iterator begin() { return _M_ht.begin(); } 00123 iterator end() { return _M_ht.end(); } 00124 const_iterator begin() const { return _M_ht.begin(); } 00125 const_iterator end() const { return _M_ht.end(); } 00126 00127 pair<iterator, bool> insert(const value_type& __obj) 00128 { return _M_ht.insert_unique(__obj); } 00129 iterator insert(const_iterator /*__hint*/, const value_type& __obj) 00130 { return _M_ht.insert_unique(__obj); } 00131 #if defined (_STLP_MEMBER_TEMPLATES) 00132 template <class _InputIterator> 00133 void insert(_InputIterator __f, _InputIterator __l) 00134 #else 00135 void insert(const_iterator __f, const_iterator __l) 00136 {_M_ht.insert_unique(__f, __l); } 00137 void insert(const value_type* __f, const value_type* __l) 00138 #endif 00139 { _M_ht.insert_unique(__f,__l); } 00140 00141 _STLP_TEMPLATE_FOR_CONT_EXT 00142 iterator find(const _KT& __key) { return _M_ht.find(__key); } 00143 _STLP_TEMPLATE_FOR_CONT_EXT 00144 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); } 00145 00146 _STLP_TEMPLATE_FOR_CONT_EXT 00147 size_type count(const _KT& __key) const { return _M_ht.count(__key); } 00148 00149 _STLP_TEMPLATE_FOR_CONT_EXT 00150 pair<iterator, iterator> equal_range(const _KT& __key) 00151 { return _M_ht.equal_range(__key); } 00152 _STLP_TEMPLATE_FOR_CONT_EXT 00153 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const 00154 { return _M_ht.equal_range(__key); } 00155 00156 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00157 void erase(const_iterator __it) { _M_ht.erase(__it); } 00158 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); } 00159 void clear() { _M_ht.clear(); } 00160 00161 size_type bucket_count() const { return _M_ht.bucket_count(); } 00162 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00163 size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); } 00164 _STLP_TEMPLATE_FOR_CONT_EXT 00165 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); } 00166 local_iterator begin(size_type __n) { return _M_ht.begin(__n); } 00167 local_iterator end(size_type __n) { return _M_ht.end(__n); } 00168 const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); } 00169 const_local_iterator end(size_type __n) const { return _M_ht.end(__n); } 00170 00171 float load_factor() const { return _M_ht.load_factor(); } 00172 float max_load_factor() const { return _M_ht.max_load_factor(); } 00173 void max_load_factor(float __val) { _M_ht.max_load_factor(__val); } 00174 void rehash(size_type __hint) { _M_ht.rehash(__hint); } 00175 }; 00176 00177 _STLP_END_NAMESPACE 00178 00179 //Specific iterator traits creation 00180 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMultisetTraitsT, Const_traits) 00181 00182 _STLP_BEGIN_TR1_NAMESPACE 00183 00184 template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>), 00185 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Value>), 00186 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) > 00187 class unordered_multiset 00188 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 00189 : public __stlport_class<unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > 00190 #endif 00191 { 00192 typedef unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Self; 00193 //Specific iterator traits creation 00194 typedef _STLP_PRIV _UnorderedMultisetTraitsT<_Value> _UnorderedMultisetTraits; 00195 public: 00196 typedef hashtable<_Value, _Value, _HashFcn, 00197 _UnorderedMultisetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht; 00198 00199 typedef typename _Ht::key_type key_type; 00200 typedef typename _Ht::value_type value_type; 00201 typedef typename _Ht::hasher hasher; 00202 typedef typename _Ht::key_equal key_equal; 00203 00204 typedef typename _Ht::size_type size_type; 00205 typedef typename _Ht::difference_type difference_type; 00206 typedef typename _Ht::pointer pointer; 00207 typedef typename _Ht::const_pointer const_pointer; 00208 typedef typename _Ht::reference reference; 00209 typedef typename _Ht::const_reference const_reference; 00210 00211 typedef typename _Ht::iterator iterator; 00212 typedef typename _Ht::const_iterator const_iterator; 00213 typedef typename _Ht::local_iterator local_iterator; 00214 typedef typename _Ht::const_local_iterator const_local_iterator; 00215 00216 typedef typename _Ht::allocator_type allocator_type; 00217 00218 hasher hash_function() const { return _M_ht.hash_funct(); } 00219 key_equal key_eq() const { return _M_ht.key_eq(); } 00220 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00221 00222 private: 00223 _Ht _M_ht; 00224 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 00225 00226 public: 00227 explicit unordered_multiset(size_type __n = 0, const hasher& __hf = hasher(), 00228 const key_equal& __eql = key_equal(), 00229 const allocator_type& __a = allocator_type()) 00230 : _M_ht(__n, __hf, __eql, __a) {} 00231 00232 #if !defined (_STLP_NO_MOVE_SEMANTIC) 00233 unordered_multiset(__move_source<_Self> src) 00234 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {} 00235 #endif 00236 00237 #if defined (_STLP_MEMBER_TEMPLATES) 00238 template <class _InputIterator> 00239 unordered_multiset(_InputIterator __f, _InputIterator __l, 00240 size_type __n = 0, const hasher& __hf = hasher(), 00241 const key_equal& __eql = key_equal(), 00242 const allocator_type& __a = allocator_type()) 00243 : _M_ht(__n, __hf, __eql, __a) 00244 { _M_ht.insert_equal(__f, __l); } 00245 #else 00246 unordered_multiset(const value_type* __f, const value_type* __l, 00247 size_type __n = 0, const hasher& __hf = hasher(), 00248 const key_equal& __eql = key_equal(), 00249 const allocator_type& __a = allocator_type()) 00250 : _M_ht(__n, __hf, __eql, __a) 00251 { _M_ht.insert_equal(__f, __l); } 00252 00253 unordered_multiset(const_iterator __f, const_iterator __l, 00254 size_type __n = 0, const hasher& __hf = hasher(), 00255 const key_equal& __eql = key_equal(), 00256 const allocator_type& __a = allocator_type()) 00257 : _M_ht(__n, __hf, __eql, __a) 00258 { _M_ht.insert_equal(__f, __l); } 00259 #endif /*_STLP_MEMBER_TEMPLATES */ 00260 00261 _Self& operator = (const _Self& __other) 00262 { _M_ht = __other._M_ht; return *this; } 00263 00264 size_type size() const { return _M_ht.size(); } 00265 size_type max_size() const { return _M_ht.max_size(); } 00266 bool empty() const { return _M_ht.empty(); } 00267 void swap(_Self& hs) { _M_ht.swap(hs._M_ht); } 00268 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 00269 void _M_swap_workaround(_Self& __x) { swap(__x); } 00270 #endif 00271 00272 iterator begin() { return _M_ht.begin(); } 00273 iterator end() { return _M_ht.end(); } 00274 const_iterator begin() const { return _M_ht.begin(); } 00275 const_iterator end() const { return _M_ht.end(); } 00276 00277 iterator insert(const value_type& __obj) 00278 { return _M_ht.insert_equal(__obj); } 00279 iterator insert(const_iterator /*__hint*/, const value_type& __obj) 00280 { return _M_ht.insert_equal(__obj); } 00281 #if defined (_STLP_MEMBER_TEMPLATES) 00282 template <class _InputIterator> 00283 void insert(_InputIterator __f, _InputIterator __l) 00284 #else 00285 void insert(const value_type* __f, const value_type* __l) 00286 { _M_ht.insert_equal(__f,__l); } 00287 void insert(const_iterator __f, const_iterator __l) 00288 #endif /*_STLP_MEMBER_TEMPLATES */ 00289 { _M_ht.insert_equal(__f, __l); } 00290 00291 _STLP_TEMPLATE_FOR_CONT_EXT 00292 iterator find(const _KT& __key) { return _M_ht.find(__key); } 00293 _STLP_TEMPLATE_FOR_CONT_EXT 00294 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); } 00295 00296 _STLP_TEMPLATE_FOR_CONT_EXT 00297 size_type count(const _KT& __key) const { return _M_ht.count(__key); } 00298 00299 _STLP_TEMPLATE_FOR_CONT_EXT 00300 pair<iterator, iterator> equal_range(const _KT& __key) 00301 { return _M_ht.equal_range(__key); } 00302 _STLP_TEMPLATE_FOR_CONT_EXT 00303 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const 00304 { return _M_ht.equal_range(__key); } 00305 00306 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00307 void erase(const_iterator __it) { _M_ht.erase(__it); } 00308 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); } 00309 void clear() { _M_ht.clear(); } 00310 00311 size_type bucket_count() const { return _M_ht.bucket_count(); } 00312 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00313 size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); } 00314 _STLP_TEMPLATE_FOR_CONT_EXT 00315 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); } 00316 local_iterator begin(size_type __n) { return _M_ht.begin(__n); } 00317 local_iterator end(size_type __n) { return _M_ht.end(__n); } 00318 const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); } 00319 const_local_iterator end(size_type __n) const { return _M_ht.end(__n); } 00320 00321 float load_factor() const { return _M_ht.load_factor(); } 00322 float max_load_factor() const { return _M_ht.max_load_factor(); } 00323 void max_load_factor(float __val) { _M_ht.max_load_factor(__val); } 00324 void rehash(size_type __hint) { _M_ht.rehash(__hint); } 00325 }; 00326 00327 #define _STLP_TEMPLATE_HEADER template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00328 #define _STLP_TEMPLATE_CONTAINER unordered_set<_Value,_HashFcn,_EqualKey,_Alloc> 00329 00330 #include <stl/_relops_hash_cont.h> 00331 00332 #undef _STLP_TEMPLATE_CONTAINER 00333 #define _STLP_TEMPLATE_CONTAINER unordered_multiset<_Value,_HashFcn,_EqualKey,_Alloc> 00334 #include <stl/_relops_hash_cont.h> 00335 00336 #undef _STLP_TEMPLATE_CONTAINER 00337 #undef _STLP_TEMPLATE_HEADER 00338 00339 _STLP_END_NAMESPACE 00340 00341 // Specialization of insert_iterator so that it will work for unordered_set 00342 // and unordered_multiset. 00343 00344 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 00345 # if !defined (_STLP_NO_MOVE_SEMANTIC) 00346 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00347 struct __move_traits<_STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > : 00348 _STLP_PRIV __move_traits_aux<typename _STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht> 00349 {}; 00350 00351 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00352 struct __move_traits<_STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > : 00353 _STLP_PRIV __move_traits_aux<typename _STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht> 00354 {}; 00355 # endif 00356 00357 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00358 class insert_iterator<_STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > { 00359 protected: 00360 typedef _STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 00361 _Container* container; 00362 public: 00363 typedef _Container container_type; 00364 typedef output_iterator_tag iterator_category; 00365 typedef void value_type; 00366 typedef void difference_type; 00367 typedef void pointer; 00368 typedef void reference; 00369 00370 insert_iterator(_Container& __x) : container(&__x) {} 00371 insert_iterator(_Container& __x, typename _Container::iterator) 00372 : container(&__x) {} 00373 insert_iterator<_Container>& 00374 operator=(const typename _Container::value_type& __val) { 00375 container->insert(__val); 00376 return *this; 00377 } 00378 insert_iterator<_Container>& operator*() { return *this; } 00379 insert_iterator<_Container>& operator++() { return *this; } 00380 insert_iterator<_Container>& operator++(int) { return *this; } 00381 }; 00382 00383 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00384 class insert_iterator<_STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > { 00385 protected: 00386 typedef _STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 00387 _Container* container; 00388 typename _Container::iterator iter; 00389 public: 00390 typedef _Container container_type; 00391 typedef output_iterator_tag iterator_category; 00392 typedef void value_type; 00393 typedef void difference_type; 00394 typedef void pointer; 00395 typedef void reference; 00396 00397 insert_iterator(_Container& __x) : container(&__x) {} 00398 insert_iterator(_Container& __x, typename _Container::iterator) 00399 : container(&__x) {} 00400 insert_iterator<_Container>& 00401 operator=(const typename _Container::value_type& __val) { 00402 container->insert(__val); 00403 return *this; 00404 } 00405 insert_iterator<_Container>& operator*() { return *this; } 00406 insert_iterator<_Container>& operator++() { return *this; } 00407 insert_iterator<_Container>& operator++(int) { return *this; } 00408 }; 00409 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 00410 00411 _STLP_END_NAMESPACE 00412 00413 #endif /* _STLP_INTERNAL_UNORDERED_SET_H */ 00414 00415 // Local Variables: 00416 // mode:C++ 00417 // End: 00418
Generated on Sat May 26 2012 04:28:20 for ReactOS by
1.7.6.1
