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 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 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
