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