1 // Hashing set implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /* 26 * Copyright (c) 1996 27 * Silicon Graphics Computer Systems, Inc. 28 * 29 * Permission to use, copy, modify, distribute and sell this software 30 * and its documentation for any purpose is hereby granted without fee, 31 * provided that the above copyright notice appear in all copies and 32 * that both that copyright notice and this permission notice appear 33 * in supporting documentation. Silicon Graphics makes no 34 * representations about the suitability of this software for any 35 * purpose. It is provided "as is" without express or implied warranty. 36 * 37 * 38 * Copyright (c) 1994 39 * Hewlett-Packard Company 40 * 41 * Permission to use, copy, modify, distribute and sell this software 42 * and its documentation for any purpose is hereby granted without fee, 43 * provided that the above copyright notice appear in all copies and 44 * that both that copyright notice and this permission notice appear 45 * in supporting documentation. Hewlett-Packard Company makes no 46 * representations about the suitability of this software for any 47 * purpose. It is provided "as is" without express or implied warranty. 48 * 49 */ 50 51 /** @file backward/hash_set 52 * This file is a GNU extension to the Standard C++ Library (possibly 53 * containing extensions from the HP/SGI STL subset). 54 */ 55 56 #ifndef _HASH_SET 57 #define _HASH_SET 1 58 59 #ifndef _GLIBCXX_PERMIT_BACKWARD_HASH 60 #include "backward_warning.h" 61 #endif 62 63 #include <bits/c++config.h> 64 #include <backward/hashtable.h> 65 #include <bits/concept_check.h> 66 67 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 68 69 using std::equal_to; 70 using std::allocator; 71 using std::pair; 72 using std::_Identity; 73 74 /** 75 * This is an SGI extension. 76 * @ingroup SGIextensions 77 * @doctodo 78 */ 79 template<class _Value, class _HashFcn = hash<_Value>, 80 class _EqualKey = equal_to<_Value>, 81 class _Alloc = allocator<_Value> > 82 class hash_set 83 { 84 // concept requirements 85 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 86 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 87 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 88 89 private: 90 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 91 _EqualKey, _Alloc> _Ht; 92 _Ht _M_ht; 93 94 public: 95 typedef typename _Ht::key_type key_type; 96 typedef typename _Ht::value_type value_type; 97 typedef typename _Ht::hasher hasher; 98 typedef typename _Ht::key_equal key_equal; 99 100 typedef typename _Ht::size_type size_type; 101 typedef typename _Ht::difference_type difference_type; 102 typedef typename _Alloc::pointer pointer; 103 typedef typename _Alloc::const_pointer const_pointer; 104 typedef typename _Alloc::reference reference; 105 typedef typename _Alloc::const_reference const_reference; 106 107 typedef typename _Ht::const_iterator iterator; 108 typedef typename _Ht::const_iterator const_iterator; 109 110 typedef typename _Ht::allocator_type allocator_type; 111 112 hasher 113 hash_funct() const 114 { return _M_ht.hash_funct(); } 115 116 key_equal 117 key_eq() const 118 { return _M_ht.key_eq(); } 119 120 allocator_type 121 get_allocator() const 122 { return _M_ht.get_allocator(); } 123 124 hash_set() 125 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 126 127 explicit 128 hash_set(size_type __n) 129 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 130 131 hash_set(size_type __n, const hasher& __hf) 132 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 133 134 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 135 const allocator_type& __a = allocator_type()) 136 : _M_ht(__n, __hf, __eql, __a) {} 137 138 template<class _InputIterator> 139 hash_set(_InputIterator __f, _InputIterator __l) 140 : _M_ht(100, hasher(), key_equal(), allocator_type()) 141 { _M_ht.insert_unique(__f, __l); } 142 143 template<class _InputIterator> 144 hash_set(_InputIterator __f, _InputIterator __l, size_type __n) 145 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 146 { _M_ht.insert_unique(__f, __l); } 147 148 template<class _InputIterator> 149 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 150 const hasher& __hf) 151 : _M_ht(__n, __hf, key_equal(), allocator_type()) 152 { _M_ht.insert_unique(__f, __l); } 153 154 template<class _InputIterator> 155 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 156 const hasher& __hf, const key_equal& __eql, 157 const allocator_type& __a = allocator_type()) 158 : _M_ht(__n, __hf, __eql, __a) 159 { _M_ht.insert_unique(__f, __l); } 160 161 size_type 162 size() const 163 { return _M_ht.size(); } 164 165 size_type 166 max_size() const 167 { return _M_ht.max_size(); } 168 169 bool 170 empty() const 171 { return _M_ht.empty(); } 172 173 void 174 swap(hash_set& __hs) 175 { _M_ht.swap(__hs._M_ht); } 176 177 template<class _Val, class _HF, class _EqK, class _Al> 178 friend bool 179 operator==(const hash_set<_Val, _HF, _EqK, _Al>&, 180 const hash_set<_Val, _HF, _EqK, _Al>&); 181 182 iterator 183 begin() const 184 { return _M_ht.begin(); } 185 186 iterator 187 end() const 188 { return _M_ht.end(); } 189 190 pair<iterator, bool> 191 insert(const value_type& __obj) 192 { 193 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); 194 return pair<iterator,bool>(__p.first, __p.second); 195 } 196 197 template<class _InputIterator> 198 void 199 insert(_InputIterator __f, _InputIterator __l) 200 { _M_ht.insert_unique(__f, __l); } 201 202 pair<iterator, bool> 203 insert_noresize(const value_type& __obj) 204 { 205 pair<typename _Ht::iterator, bool> __p 206 = _M_ht.insert_unique_noresize(__obj); 207 return pair<iterator, bool>(__p.first, __p.second); 208 } 209 210 iterator 211 find(const key_type& __key) const 212 { return _M_ht.find(__key); } 213 214 size_type 215 count(const key_type& __key) const 216 { return _M_ht.count(__key); } 217 218 pair<iterator, iterator> 219 equal_range(const key_type& __key) const 220 { return _M_ht.equal_range(__key); } 221 222 size_type 223 erase(const key_type& __key) 224 {return _M_ht.erase(__key); } 225 226 void 227 erase(iterator __it) 228 { _M_ht.erase(__it); } 229 230 void 231 erase(iterator __f, iterator __l) 232 { _M_ht.erase(__f, __l); } 233 234 void 235 clear() 236 { _M_ht.clear(); } 237 238 void 239 resize(size_type __hint) 240 { _M_ht.resize(__hint); } 241 242 size_type 243 bucket_count() const 244 { return _M_ht.bucket_count(); } 245 246 size_type 247 max_bucket_count() const 248 { return _M_ht.max_bucket_count(); } 249 250 size_type 251 elems_in_bucket(size_type __n) const 252 { return _M_ht.elems_in_bucket(__n); } 253 }; 254 255 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 256 inline bool 257 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 258 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 259 { return __hs1._M_ht == __hs2._M_ht; } 260 261 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 262 inline bool 263 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 264 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 265 { return !(__hs1 == __hs2); } 266 267 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 268 inline void 269 swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 270 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 271 { __hs1.swap(__hs2); } 272 273 274 /** 275 * This is an SGI extension. 276 * @ingroup SGIextensions 277 * @doctodo 278 */ 279 template<class _Value, 280 class _HashFcn = hash<_Value>, 281 class _EqualKey = equal_to<_Value>, 282 class _Alloc = allocator<_Value> > 283 class hash_multiset 284 { 285 // concept requirements 286 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 287 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 288 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 289 290 private: 291 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 292 _EqualKey, _Alloc> _Ht; 293 _Ht _M_ht; 294 295 public: 296 typedef typename _Ht::key_type key_type; 297 typedef typename _Ht::value_type value_type; 298 typedef typename _Ht::hasher hasher; 299 typedef typename _Ht::key_equal key_equal; 300 301 typedef typename _Ht::size_type size_type; 302 typedef typename _Ht::difference_type difference_type; 303 typedef typename _Alloc::pointer pointer; 304 typedef typename _Alloc::const_pointer const_pointer; 305 typedef typename _Alloc::reference reference; 306 typedef typename _Alloc::const_reference const_reference; 307 308 typedef typename _Ht::const_iterator iterator; 309 typedef typename _Ht::const_iterator const_iterator; 310 311 typedef typename _Ht::allocator_type allocator_type; 312 313 hasher 314 hash_funct() const 315 { return _M_ht.hash_funct(); } 316 317 key_equal 318 key_eq() const 319 { return _M_ht.key_eq(); } 320 321 allocator_type 322 get_allocator() const 323 { return _M_ht.get_allocator(); } 324 325 hash_multiset() 326 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 327 328 explicit 329 hash_multiset(size_type __n) 330 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 331 332 hash_multiset(size_type __n, const hasher& __hf) 333 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 334 335 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, 336 const allocator_type& __a = allocator_type()) 337 : _M_ht(__n, __hf, __eql, __a) {} 338 339 template<class _InputIterator> 340 hash_multiset(_InputIterator __f, _InputIterator __l) 341 : _M_ht(100, hasher(), key_equal(), allocator_type()) 342 { _M_ht.insert_equal(__f, __l); } 343 344 template<class _InputIterator> 345 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) 346 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 347 { _M_ht.insert_equal(__f, __l); } 348 349 template<class _InputIterator> 350 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 351 const hasher& __hf) 352 : _M_ht(__n, __hf, key_equal(), allocator_type()) 353 { _M_ht.insert_equal(__f, __l); } 354 355 template<class _InputIterator> 356 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 357 const hasher& __hf, const key_equal& __eql, 358 const allocator_type& __a = allocator_type()) 359 : _M_ht(__n, __hf, __eql, __a) 360 { _M_ht.insert_equal(__f, __l); } 361 362 size_type 363 size() const 364 { return _M_ht.size(); } 365 366 size_type 367 max_size() const 368 { return _M_ht.max_size(); } 369 370 bool 371 empty() const 372 { return _M_ht.empty(); } 373 374 void 375 swap(hash_multiset& hs) 376 { _M_ht.swap(hs._M_ht); } 377 378 template<class _Val, class _HF, class _EqK, class _Al> 379 friend bool 380 operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&, 381 const hash_multiset<_Val, _HF, _EqK, _Al>&); 382 383 iterator 384 begin() const 385 { return _M_ht.begin(); } 386 387 iterator 388 end() const 389 { return _M_ht.end(); } 390 391 iterator 392 insert(const value_type& __obj) 393 { return _M_ht.insert_equal(__obj); } 394 395 template<class _InputIterator> 396 void 397 insert(_InputIterator __f, _InputIterator __l) 398 { _M_ht.insert_equal(__f,__l); } 399 400 iterator 401 insert_noresize(const value_type& __obj) 402 { return _M_ht.insert_equal_noresize(__obj); } 403 404 iterator 405 find(const key_type& __key) const 406 { return _M_ht.find(__key); } 407 408 size_type 409 count(const key_type& __key) const 410 { return _M_ht.count(__key); } 411 412 pair<iterator, iterator> 413 equal_range(const key_type& __key) const 414 { return _M_ht.equal_range(__key); } 415 416 size_type 417 erase(const key_type& __key) 418 { return _M_ht.erase(__key); } 419 420 void 421 erase(iterator __it) 422 { _M_ht.erase(__it); } 423 424 void 425 erase(iterator __f, iterator __l) 426 { _M_ht.erase(__f, __l); } 427 428 void 429 clear() 430 { _M_ht.clear(); } 431 432 void 433 resize(size_type __hint) 434 { _M_ht.resize(__hint); } 435 436 size_type 437 bucket_count() const 438 { return _M_ht.bucket_count(); } 439 440 size_type 441 max_bucket_count() const 442 { return _M_ht.max_bucket_count(); } 443 444 size_type 445 elems_in_bucket(size_type __n) const 446 { return _M_ht.elems_in_bucket(__n); } 447 }; 448 449 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 450 inline bool 451 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 452 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 453 { return __hs1._M_ht == __hs2._M_ht; } 454 455 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 456 inline bool 457 operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 458 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 459 { return !(__hs1 == __hs2); } 460 461 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 462 inline void 463 swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 464 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 465 { __hs1.swap(__hs2); } 466 467 _GLIBCXX_END_NAMESPACE 468 469 _GLIBCXX_BEGIN_NAMESPACE(std) 470 471 // Specialization of insert_iterator so that it will work for hash_set 472 // and hash_multiset. 473 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 474 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, 475 _EqualKey, _Alloc> > 476 { 477 protected: 478 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> 479 _Container; 480 _Container* container; 481 482 public: 483 typedef _Container container_type; 484 typedef output_iterator_tag iterator_category; 485 typedef void value_type; 486 typedef void difference_type; 487 typedef void pointer; 488 typedef void reference; 489 490 insert_iterator(_Container& __x) 491 : container(&__x) {} 492 493 insert_iterator(_Container& __x, typename _Container::iterator) 494 : container(&__x) {} 495 496 insert_iterator<_Container>& 497 operator=(const typename _Container::value_type& __value) 498 { 499 container->insert(__value); 500 return *this; 501 } 502 503 insert_iterator<_Container>& 504 operator*() 505 { return *this; } 506 507 insert_iterator<_Container>& 508 operator++() 509 { return *this; } 510 511 insert_iterator<_Container>& 512 operator++(int) 513 { return *this; } 514 }; 515 516 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 517 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, 518 _EqualKey, _Alloc> > 519 { 520 protected: 521 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> 522 _Container; 523 _Container* container; 524 typename _Container::iterator iter; 525 526 public: 527 typedef _Container container_type; 528 typedef output_iterator_tag iterator_category; 529 typedef void value_type; 530 typedef void difference_type; 531 typedef void pointer; 532 typedef void reference; 533 534 insert_iterator(_Container& __x) 535 : container(&__x) {} 536 537 insert_iterator(_Container& __x, typename _Container::iterator) 538 : container(&__x) {} 539 540 insert_iterator<_Container>& 541 operator=(const typename _Container::value_type& __value) 542 { 543 container->insert(__value); 544 return *this; 545 } 546 547 insert_iterator<_Container>& 548 operator*() 549 { return *this; } 550 551 insert_iterator<_Container>& 552 operator++() 553 { return *this; } 554 555 insert_iterator<_Container>& 556 operator++(int) { return *this; } 557 }; 558 559 _GLIBCXX_END_NAMESPACE 560 561 #endif 562
