contrib/gcc-8.0/libstdc++-v3/include/backward/hash_set

   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
  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     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
 472 namespace 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