1// Hashing set implementation -*- C++ -*- 2 3// Copyright (C) 2001-2021 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 _BACKWARD_HASH_SET 57#define _BACKWARD_HASH_SET 1 58 59#ifndef _GLIBCXX_PERMIT_BACKWARD_HASH 60#include <backward/backward_warning.h> 61#endif 62 63#include <bits/c++config.h> 64#include <backward/hashtable.h> 65#include <bits/concept_check.h> 66 67namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 68{ 69_GLIBCXX_BEGIN_NAMESPACE_VERSION 70 71 using std::equal_to; 72 using std::allocator; 73 using std::pair; 74 using std::_Identity; 75 76 /** 77 * This is an SGI extension. 78 * @ingroup SGIextensions 79 * @doctodo 80 */ 81 template<class _Value, class _HashFcn = hash<_Value>, 82 class _EqualKey = equal_to<_Value>, 83 class _Alloc = allocator<_Value> > 84 class hash_set 85 { 86 // concept requirements 87 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 88 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 89 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 90 91 typedef __alloc_traits<_Alloc> _Alloc_traits; 92 93 private: 94 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 95 _EqualKey, _Alloc> _Ht; 96 _Ht _M_ht; 97 98 public: 99 typedef typename _Ht::key_type key_type; 100 typedef typename _Ht::value_type value_type; 101 typedef typename _Ht::hasher hasher; 102 typedef typename _Ht::key_equal key_equal; 103 104 typedef typename _Ht::size_type size_type; 105 typedef typename _Ht::difference_type difference_type; 106 typedef typename _Alloc_traits::pointer pointer; 107 typedef typename _Alloc_traits::const_pointer const_pointer; 108 typedef typename _Alloc_traits::reference reference; 109 typedef typename _Alloc_traits::const_reference const_reference; 110 111 typedef typename _Ht::const_iterator iterator; 112 typedef typename _Ht::const_iterator const_iterator; 113 114 typedef typename _Ht::allocator_type allocator_type; 115 116 hasher 117 hash_funct() const 118 { return _M_ht.hash_funct(); } 119 120 key_equal 121 key_eq() const 122 { return _M_ht.key_eq(); } 123 124 allocator_type 125 get_allocator() const 126 { return _M_ht.get_allocator(); } 127 128 hash_set() 129 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 130 131 explicit 132 hash_set(size_type __n) 133 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 134 135 hash_set(size_type __n, const hasher& __hf) 136 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 137 138 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 139 const allocator_type& __a = allocator_type()) 140 : _M_ht(__n, __hf, __eql, __a) {} 141 142 template<class _InputIterator> 143 hash_set(_InputIterator __f, _InputIterator __l) 144 : _M_ht(100, hasher(), key_equal(), allocator_type()) 145 { _M_ht.insert_unique(__f, __l); } 146 147 template<class _InputIterator> 148 hash_set(_InputIterator __f, _InputIterator __l, size_type __n) 149 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 150 { _M_ht.insert_unique(__f, __l); } 151 152 template<class _InputIterator> 153 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 154 const hasher& __hf) 155 : _M_ht(__n, __hf, key_equal(), allocator_type()) 156 { _M_ht.insert_unique(__f, __l); } 157 158 template<class _InputIterator> 159 hash_set(_InputIterator __f, _InputIterator __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 165 size_type 166 size() const 167 { return _M_ht.size(); } 168 169 size_type 170 max_size() const 171 { return _M_ht.max_size(); } 172 173 _GLIBCXX_NODISCARD bool 174 empty() const 175 { return _M_ht.empty(); } 176 177 void 178 swap(hash_set& __hs) 179 { _M_ht.swap(__hs._M_ht); } 180 181 template<class _Val, class _HF, class _EqK, class _Al> 182 friend bool 183 operator==(const hash_set<_Val, _HF, _EqK, _Al>&, 184 const hash_set<_Val, _HF, _EqK, _Al>&); 185 186 iterator 187 begin() const 188 { return _M_ht.begin(); } 189 190 iterator 191 end() const 192 { return _M_ht.end(); } 193 194 pair<iterator, bool> 195 insert(const value_type& __obj) 196 { 197 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); 198 return pair<iterator,bool>(__p.first, __p.second); 199 } 200 201 template<class _InputIterator> 202 void 203 insert(_InputIterator __f, _InputIterator __l) 204 { _M_ht.insert_unique(__f, __l); } 205 206 pair<iterator, bool> 207 insert_noresize(const value_type& __obj) 208 { 209 pair<typename _Ht::iterator, bool> __p 210 = _M_ht.insert_unique_noresize(__obj); 211 return pair<iterator, bool>(__p.first, __p.second); 212 } 213 214 iterator 215 find(const key_type& __key) const 216 { return _M_ht.find(__key); } 217 218 size_type 219 count(const key_type& __key) const 220 { return _M_ht.count(__key); } 221 222 pair<iterator, iterator> 223 equal_range(const key_type& __key) const 224 { return _M_ht.equal_range(__key); } 225 226 size_type 227 erase(const key_type& __key) 228 {return _M_ht.erase(__key); } 229 230 void 231 erase(iterator __it) 232 { _M_ht.erase(__it); } 233 234 void 235 erase(iterator __f, iterator __l) 236 { _M_ht.erase(__f, __l); } 237 238 void 239 clear() 240 { _M_ht.clear(); } 241 242 void 243 resize(size_type __hint) 244 { _M_ht.resize(__hint); } 245 246 size_type 247 bucket_count() const 248 { return _M_ht.bucket_count(); } 249 250 size_type 251 max_bucket_count() const 252 { return _M_ht.max_bucket_count(); } 253 254 size_type 255 elems_in_bucket(size_type __n) const 256 { return _M_ht.elems_in_bucket(__n); } 257 }; 258 259 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 260 inline bool 261 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 262 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 263 { return __hs1._M_ht == __hs2._M_ht; } 264 265 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 266 inline bool 267 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 268 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 269 { return !(__hs1 == __hs2); } 270 271 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 272 inline void 273 swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 274 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 275 { __hs1.swap(__hs2); } 276 277 278 /** 279 * This is an SGI extension. 280 * @ingroup SGIextensions 281 * @doctodo 282 */ 283 template<class _Value, 284 class _HashFcn = hash<_Value>, 285 class _EqualKey = equal_to<_Value>, 286 class _Alloc = allocator<_Value> > 287 class hash_multiset 288 { 289 // concept requirements 290 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 291 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 292 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 293 294 private: 295 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 296 _EqualKey, _Alloc> _Ht; 297 _Ht _M_ht; 298 299 public: 300 typedef typename _Ht::key_type key_type; 301 typedef typename _Ht::value_type value_type; 302 typedef typename _Ht::hasher hasher; 303 typedef typename _Ht::key_equal key_equal; 304 305 typedef typename _Ht::size_type size_type; 306 typedef typename _Ht::difference_type difference_type; 307 typedef typename _Alloc::pointer pointer; 308 typedef typename _Alloc::const_pointer const_pointer; 309 typedef typename _Alloc::reference reference; 310 typedef typename _Alloc::const_reference const_reference; 311 312 typedef typename _Ht::const_iterator iterator; 313 typedef typename _Ht::const_iterator const_iterator; 314 315 typedef typename _Ht::allocator_type allocator_type; 316 317 hasher 318 hash_funct() const 319 { return _M_ht.hash_funct(); } 320 321 key_equal 322 key_eq() const 323 { return _M_ht.key_eq(); } 324 325 allocator_type 326 get_allocator() const 327 { return _M_ht.get_allocator(); } 328 329 hash_multiset() 330 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 331 332 explicit 333 hash_multiset(size_type __n) 334 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 335 336 hash_multiset(size_type __n, const hasher& __hf) 337 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 338 339 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, 340 const allocator_type& __a = allocator_type()) 341 : _M_ht(__n, __hf, __eql, __a) {} 342 343 template<class _InputIterator> 344 hash_multiset(_InputIterator __f, _InputIterator __l) 345 : _M_ht(100, hasher(), key_equal(), allocator_type()) 346 { _M_ht.insert_equal(__f, __l); } 347 348 template<class _InputIterator> 349 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) 350 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 351 { _M_ht.insert_equal(__f, __l); } 352 353 template<class _InputIterator> 354 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 355 const hasher& __hf) 356 : _M_ht(__n, __hf, key_equal(), allocator_type()) 357 { _M_ht.insert_equal(__f, __l); } 358 359 template<class _InputIterator> 360 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 361 const hasher& __hf, const key_equal& __eql, 362 const allocator_type& __a = allocator_type()) 363 : _M_ht(__n, __hf, __eql, __a) 364 { _M_ht.insert_equal(__f, __l); } 365 366 size_type 367 size() const 368 { return _M_ht.size(); } 369 370 size_type 371 max_size() const 372 { return _M_ht.max_size(); } 373 374 _GLIBCXX_NODISCARD bool 375 empty() const 376 { return _M_ht.empty(); } 377 378 void 379 swap(hash_multiset& hs) 380 { _M_ht.swap(hs._M_ht); } 381 382 template<class _Val, class _HF, class _EqK, class _Al> 383 friend bool 384 operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&, 385 const hash_multiset<_Val, _HF, _EqK, _Al>&); 386 387 iterator 388 begin() const 389 { return _M_ht.begin(); } 390 391 iterator 392 end() const 393 { return _M_ht.end(); } 394 395 iterator 396 insert(const value_type& __obj) 397 { return _M_ht.insert_equal(__obj); } 398 399 template<class _InputIterator> 400 void 401 insert(_InputIterator __f, _InputIterator __l) 402 { _M_ht.insert_equal(__f,__l); } 403 404 iterator 405 insert_noresize(const value_type& __obj) 406 { return _M_ht.insert_equal_noresize(__obj); } 407 408 iterator 409 find(const key_type& __key) const 410 { return _M_ht.find(__key); } 411 412 size_type 413 count(const key_type& __key) const 414 { return _M_ht.count(__key); } 415 416 pair<iterator, iterator> 417 equal_range(const key_type& __key) const 418 { return _M_ht.equal_range(__key); } 419 420 size_type 421 erase(const key_type& __key) 422 { return _M_ht.erase(__key); } 423 424 void 425 erase(iterator __it) 426 { _M_ht.erase(__it); } 427 428 void 429 erase(iterator __f, iterator __l) 430 { _M_ht.erase(__f, __l); } 431 432 void 433 clear() 434 { _M_ht.clear(); } 435 436 void 437 resize(size_type __hint) 438 { _M_ht.resize(__hint); } 439 440 size_type 441 bucket_count() const 442 { return _M_ht.bucket_count(); } 443 444 size_type 445 max_bucket_count() const 446 { return _M_ht.max_bucket_count(); } 447 448 size_type 449 elems_in_bucket(size_type __n) const 450 { return _M_ht.elems_in_bucket(__n); } 451 }; 452 453 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 454 inline bool 455 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 456 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 457 { return __hs1._M_ht == __hs2._M_ht; } 458 459 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 460 inline bool 461 operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 462 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 463 { return !(__hs1 == __hs2); } 464 465 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 466 inline void 467 swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 468 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 469 { __hs1.swap(__hs2); } 470 471_GLIBCXX_END_NAMESPACE_VERSION 472} // namespace 473 474namespace std _GLIBCXX_VISIBILITY(default) 475{ 476_GLIBCXX_BEGIN_NAMESPACE_VERSION 477 478 // Specialization of insert_iterator so that it will work for hash_set 479 // and hash_multiset. 480 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 481 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, 482 _EqualKey, _Alloc> > 483 { 484 protected: 485 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> 486 _Container; 487 _Container* container; 488 489 public: 490 typedef _Container container_type; 491 typedef output_iterator_tag iterator_category; 492 typedef void value_type; 493 typedef void difference_type; 494 typedef void pointer; 495 typedef void reference; 496 497 insert_iterator(_Container& __x) 498 : container(&__x) {} 499 500 insert_iterator(_Container& __x, typename _Container::iterator) 501 : container(&__x) {} 502 503 insert_iterator<_Container>& 504 operator=(const typename _Container::value_type& __value) 505 { 506 container->insert(__value); 507 return *this; 508 } 509 510 insert_iterator<_Container>& 511 operator*() 512 { return *this; } 513 514 insert_iterator<_Container>& 515 operator++() 516 { return *this; } 517 518 insert_iterator<_Container>& 519 operator++(int) 520 { return *this; } 521 }; 522 523 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 524 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, 525 _EqualKey, _Alloc> > 526 { 527 protected: 528 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> 529 _Container; 530 _Container* container; 531 typename _Container::iterator iter; 532 533 public: 534 typedef _Container container_type; 535 typedef output_iterator_tag iterator_category; 536 typedef void value_type; 537 typedef void difference_type; 538 typedef void pointer; 539 typedef void reference; 540 541 insert_iterator(_Container& __x) 542 : container(&__x) {} 543 544 insert_iterator(_Container& __x, typename _Container::iterator) 545 : container(&__x) {} 546 547 insert_iterator<_Container>& 548 operator=(const typename _Container::value_type& __value) 549 { 550 container->insert(__value); 551 return *this; 552 } 553 554 insert_iterator<_Container>& 555 operator*() 556 { return *this; } 557 558 insert_iterator<_Container>& 559 operator++() 560 { return *this; } 561 562 insert_iterator<_Container>& 563 operator++(int) { return *this; } 564 }; 565 566_GLIBCXX_END_NAMESPACE_VERSION 567} // namespace 568 569#endif 570