libstdc++-v3/include/ext/hash_set

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