libstdc++-v3/include/ext/hash_set

   1 // Hashing set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2004, 2005, 2006 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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).
  59  */
  60
  61 #ifndef _HASH_SET
  62 #define _HASH_SET 1
  63
  64 #include <bits/c++config.h>
  65 #include <ext/hashtable.h>
  66 #include <bits/concept_check.h>
  67
  68 _GLIBCXX_BEGIN_NESTED_NAMESPACE(__gnu_cxx, _GLIBCXX_EXT_D)
  69
  70   using std::equal_to;
  71   using std::allocator;
  72   using std::pair;
  73   using std::_Identity;
  74
  75   /**
  76    *  This is an SGI extension.
  77    *  @ingroup SGIextensions
  78    *  @doctodo
  79    */
  80   template<class _Value, class _HashFcn  = hash<_Value>,
  81            class _EqualKey = equal_to<_Value>,
  82            class _Alloc = allocator<_Value> >
  83     class hash_set
  84     {
  85       // concept requirements
  86       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
  87       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
  88       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
  89
  90     private:
  91       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
  92                         _EqualKey, _Alloc> _Ht;
  93       _Ht _M_ht;
  94
  95     public:
  96       typedef typename _Ht::key_type key_type;
  97       typedef typename _Ht::value_type value_type;
  98       typedef typename _Ht::hasher hasher;
  99       typedef typename _Ht::key_equal key_equal;
 100
 101       typedef typename _Ht::size_type size_type;
 102       typedef typename _Ht::difference_type difference_type;
 103       typedef typename _Alloc::pointer pointer;
 104       typedef typename _Alloc::const_pointer const_pointer;
 105       typedef typename _Alloc::reference reference;
 106       typedef typename _Alloc::const_reference const_reference;
 107
 108       typedef typename _Ht::const_iterator iterator;
 109       typedef typename _Ht::const_iterator const_iterator;
 110
 111       typedef typename _Ht::allocator_type allocator_type;
 112
 113       hasher
 114       hash_funct() const
 115       { return _M_ht.hash_funct(); }
 116
 117       key_equal
 118       key_eq() const
 119       { return _M_ht.key_eq(); }
 120
 121       allocator_type
 122       get_allocator() const
 123       { return _M_ht.get_allocator(); }
 124
 125       hash_set()
 126       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 127
 128       explicit
 129       hash_set(size_type __n)
 130       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 131
 132       hash_set(size_type __n, const hasher& __hf)
 133       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 134
 135       hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
 136                const allocator_type& __a = allocator_type())
 137       : _M_ht(__n, __hf, __eql, __a) {}
 138
 139       template<class _InputIterator>
 140         hash_set(_InputIterator __f, _InputIterator __l)
 141         : _M_ht(100, hasher(), key_equal(), allocator_type())
 142         { _M_ht.insert_unique(__f, __l); }
 143
 144       template<class _InputIterator>
 145         hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
 146         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 147         { _M_ht.insert_unique(__f, __l); }
 148
 149       template<class _InputIterator>
 150         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
 151                  const hasher& __hf)
 152         : _M_ht(__n, __hf, 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                  const hasher& __hf, const key_equal& __eql,
 158                  const allocator_type& __a = allocator_type())
 159         : _M_ht(__n, __hf, __eql, __a)
 160         { _M_ht.insert_unique(__f, __l); }
 161
 162       size_type
 163       size() const
 164       { return _M_ht.size(); }
 165
 166       size_type
 167       max_size() const
 168       { return _M_ht.max_size(); }
 169
 170       bool
 171       empty() const
 172       { return _M_ht.empty(); }
 173
 174       void
 175       swap(hash_set& __hs)
 176       { _M_ht.swap(__hs._M_ht); }
 177
 178       template<class _Val, class _HF, class _EqK, class _Al>
 179         friend bool
 180         operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
 181                    const hash_set<_Val, _HF, _EqK, _Al>&);
 182
 183       iterator
 184       begin() const
 185       { return _M_ht.begin(); }
 186
 187       iterator
 188       end() const
 189       { return _M_ht.end(); }
 190
 191       pair<iterator, bool>
 192       insert(const value_type& __obj)
 193       {
 194         pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
 195         return pair<iterator,bool>(__p.first, __p.second);
 196       }
 197
 198       template<class _InputIterator>
 199         void
 200         insert(_InputIterator __f, _InputIterator __l)
 201         { _M_ht.insert_unique(__f, __l); }
 202
 203       pair<iterator, bool>
 204       insert_noresize(const value_type& __obj)
 205       {
 206         pair<typename _Ht::iterator, bool> __p
 207           = _M_ht.insert_unique_noresize(__obj);
 208         return pair<iterator, bool>(__p.first, __p.second);
 209       }
 210
 211       iterator
 212       find(const key_type& __key) const
 213       { return _M_ht.find(__key); }
 214
 215       size_type
 216       count(const key_type& __key) const
 217       { return _M_ht.count(__key); }
 218
 219       pair<iterator, iterator>
 220       equal_range(const key_type& __key) const
 221       { return _M_ht.equal_range(__key); }
 222
 223       size_type
 224       erase(const key_type& __key)
 225       {return _M_ht.erase(__key); }
 226
 227       void
 228       erase(iterator __it)
 229       { _M_ht.erase(__it); }
 230
 231       void
 232       erase(iterator __f, iterator __l)
 233       { _M_ht.erase(__f, __l); }
 234
 235       void
 236       clear()
 237       { _M_ht.clear(); }
 238
 239       void
 240       resize(size_type __hint)
 241       { _M_ht.resize(__hint); }
 242
 243       size_type
 244       bucket_count() const
 245       { return _M_ht.bucket_count(); }
 246
 247       size_type
 248       max_bucket_count() const
 249       { return _M_ht.max_bucket_count(); }
 250
 251       size_type
 252       elems_in_bucket(size_type __n) const
 253       { return _M_ht.elems_in_bucket(__n); }
 254     };
 255
 256   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 257     inline bool
 258     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
 259                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
 260     { return __hs1._M_ht == __hs2._M_ht; }
 261
 262   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 263     inline bool
 264     operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
 265                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
 266     { return !(__hs1 == __hs2); }
 267
 268   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 269     inline void
 270     swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 271          hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 272     { __hs1.swap(__hs2); }
 273
 274
 275   /**
 276    *  This is an SGI extension.
 277    *  @ingroup SGIextensions
 278    *  @doctodo
 279    */
 280   template<class _Value,
 281            class _HashFcn = hash<_Value>,
 282            class _EqualKey = equal_to<_Value>,
 283            class _Alloc = allocator<_Value> >
 284     class hash_multiset
 285     {
 286       // concept requirements
 287       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
 288       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
 289       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
 290
 291     private:
 292       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
 293                         _EqualKey, _Alloc> _Ht;
 294       _Ht _M_ht;
 295
 296     public:
 297       typedef typename _Ht::key_type key_type;
 298       typedef typename _Ht::value_type value_type;
 299       typedef typename _Ht::hasher hasher;
 300       typedef typename _Ht::key_equal key_equal;
 301
 302       typedef typename _Ht::size_type size_type;
 303       typedef typename _Ht::difference_type difference_type;
 304       typedef typename _Alloc::pointer pointer;
 305       typedef typename _Alloc::const_pointer const_pointer;
 306       typedef typename _Alloc::reference reference;
 307       typedef typename _Alloc::const_reference const_reference;
 308
 309       typedef typename _Ht::const_iterator iterator;
 310       typedef typename _Ht::const_iterator const_iterator;
 311
 312       typedef typename _Ht::allocator_type allocator_type;
 313
 314       hasher
 315       hash_funct() const
 316       { return _M_ht.hash_funct(); }
 317
 318       key_equal
 319       key_eq() const
 320       { return _M_ht.key_eq(); }
 321
 322       allocator_type
 323       get_allocator() const
 324       { return _M_ht.get_allocator(); }
 325
 326       hash_multiset()
 327       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 328
 329       explicit
 330       hash_multiset(size_type __n)
 331       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 332
 333       hash_multiset(size_type __n, const hasher& __hf)
 334       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 335
 336       hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
 337                     const allocator_type& __a = allocator_type())
 338       : _M_ht(__n, __hf, __eql, __a) {}
 339
 340       template<class _InputIterator>
 341         hash_multiset(_InputIterator __f, _InputIterator __l)
 342         : _M_ht(100, hasher(), key_equal(), allocator_type())
 343         { _M_ht.insert_equal(__f, __l); }
 344
 345       template<class _InputIterator>
 346         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
 347         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 348         { _M_ht.insert_equal(__f, __l); }
 349
 350       template<class _InputIterator>
 351         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 352                       const hasher& __hf)
 353         : _M_ht(__n, __hf, key_equal(), allocator_type())
 354         { _M_ht.insert_equal(__f, __l); }
 355
 356       template<class _InputIterator>
 357         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 358                       const hasher& __hf, const key_equal& __eql,
 359                       const allocator_type& __a = allocator_type())
 360         : _M_ht(__n, __hf, __eql, __a)
 361         { _M_ht.insert_equal(__f, __l); }
 362
 363       size_type
 364       size() const
 365       { return _M_ht.size(); }
 366
 367       size_type
 368       max_size() const
 369       { return _M_ht.max_size(); }
 370
 371       bool
 372       empty() const
 373       { return _M_ht.empty(); }
 374
 375       void
 376       swap(hash_multiset& hs)
 377       { _M_ht.swap(hs._M_ht); }
 378
 379       template<class _Val, class _HF, class _EqK, class _Al>
 380         friend bool
 381         operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
 382                    const hash_multiset<_Val, _HF, _EqK, _Al>&);
 383
 384       iterator
 385       begin() const
 386       { return _M_ht.begin(); }
 387
 388       iterator
 389       end() const
 390       { return _M_ht.end(); }
 391
 392       iterator
 393       insert(const value_type& __obj)
 394       { return _M_ht.insert_equal(__obj); }
 395
 396       template<class _InputIterator>
 397         void
 398         insert(_InputIterator __f, _InputIterator __l)
 399         { _M_ht.insert_equal(__f,__l); }
 400
 401       iterator
 402       insert_noresize(const value_type& __obj)
 403       { return _M_ht.insert_equal_noresize(__obj); }
 404
 405       iterator
 406       find(const key_type& __key) const
 407       { return _M_ht.find(__key); }
 408
 409       size_type
 410       count(const key_type& __key) const
 411       { return _M_ht.count(__key); }
 412
 413       pair<iterator, iterator>
 414       equal_range(const key_type& __key) const
 415       { return _M_ht.equal_range(__key); }
 416
 417       size_type
 418       erase(const key_type& __key)
 419       { return _M_ht.erase(__key); }
 420
 421       void
 422       erase(iterator __it)
 423       { _M_ht.erase(__it); }
 424
 425       void
 426       erase(iterator __f, iterator __l)
 427       { _M_ht.erase(__f, __l); }
 428
 429       void
 430       clear()
 431       { _M_ht.clear(); }
 432
 433       void
 434       resize(size_type __hint)
 435       { _M_ht.resize(__hint); }
 436
 437       size_type
 438       bucket_count() const
 439       { return _M_ht.bucket_count(); }
 440
 441       size_type
 442       max_bucket_count() const
 443       { return _M_ht.max_bucket_count(); }
 444
 445       size_type
 446       elems_in_bucket(size_type __n) const
 447       { return _M_ht.elems_in_bucket(__n); }
 448     };
 449
 450   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 451     inline bool
 452     operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 453                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 454     { return __hs1._M_ht == __hs2._M_ht; }
 455
 456   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 457     inline bool
 458     operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 459                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 460     { return !(__hs1 == __hs2); }
 461
 462   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 463     inline void
 464     swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 465          hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 466     { __hs1.swap(__hs2); }
 467
 468 _GLIBCXX_END_NESTED_NAMESPACE
 469
 470 #ifdef _GLIBCXX_DEBUG
 471 # include <debug/hash_set>
 472 #endif
 473
 474 _GLIBCXX_BEGIN_NAMESPACE(std)
 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
 565
 566 #endif