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