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