libstdc++-v3/include/backward/hash_set

   1 // Hashing set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2024 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
  67 namespace __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
 474 namespace 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