contrib/libstdc++/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)
  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     public:
 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     public:
 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     public:
 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     public:
 243       void
 244       resize(size_type __hint)
 245       { _M_ht.resize(__hint); }
 246
 247       size_type
 248       bucket_count() const
 249       { return _M_ht.bucket_count(); }
 250
 251       size_type
 252       max_bucket_count() const
 253       { return _M_ht.max_bucket_count(); }
 254
 255       size_type
 256       elems_in_bucket(size_type __n) const
 257       { return _M_ht.elems_in_bucket(__n); }
 258     };
 259
 260   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 261     inline bool
 262     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
 263                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
 264     { return __hs1._M_ht == __hs2._M_ht; }
 265
 266   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 267     inline bool
 268     operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
 269                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
 270     { return !(__hs1 == __hs2); }
 271
 272   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 273     inline void
 274     swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 275          hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 276     { __hs1.swap(__hs2); }
 277
 278
 279   /**
 280    *  This is an SGI extension.
 281    *  @ingroup SGIextensions
 282    *  @doctodo
 283    */
 284   template<class _Value,
 285            class _HashFcn = hash<_Value>,
 286            class _EqualKey = equal_to<_Value>,
 287            class _Alloc = allocator<_Value> >
 288     class hash_multiset
 289     {
 290       // concept requirements
 291       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
 292       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
 293       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
 294
 295     private:
 296       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
 297                         _EqualKey, _Alloc> _Ht;
 298       _Ht _M_ht;
 299
 300     public:
 301       typedef typename _Ht::key_type key_type;
 302       typedef typename _Ht::value_type value_type;
 303       typedef typename _Ht::hasher hasher;
 304       typedef typename _Ht::key_equal key_equal;
 305
 306       typedef typename _Ht::size_type size_type;
 307       typedef typename _Ht::difference_type difference_type;
 308       typedef typename _Alloc::pointer pointer;
 309       typedef typename _Alloc::const_pointer const_pointer;
 310       typedef typename _Alloc::reference reference;
 311       typedef typename _Alloc::const_reference const_reference;
 312
 313       typedef typename _Ht::const_iterator iterator;
 314       typedef typename _Ht::const_iterator const_iterator;
 315
 316       typedef typename _Ht::allocator_type allocator_type;
 317
 318       hasher
 319       hash_funct() const
 320       { return _M_ht.hash_funct(); }
 321
 322       key_equal
 323       key_eq() const
 324       { return _M_ht.key_eq(); }
 325
 326       allocator_type
 327       get_allocator() const
 328       { return _M_ht.get_allocator(); }
 329
 330     public:
 331       hash_multiset()
 332       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 333
 334       explicit
 335       hash_multiset(size_type __n)
 336       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 337
 338       hash_multiset(size_type __n, const hasher& __hf)
 339       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 340
 341       hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
 342                     const allocator_type& __a = allocator_type())
 343       : _M_ht(__n, __hf, __eql, __a) {}
 344
 345       template<class _InputIterator>
 346         hash_multiset(_InputIterator __f, _InputIterator __l)
 347         : _M_ht(100, 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         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 353         { _M_ht.insert_equal(__f, __l); }
 354
 355       template<class _InputIterator>
 356         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 357                       const hasher& __hf)
 358         : _M_ht(__n, __hf, key_equal(), allocator_type())
 359         { _M_ht.insert_equal(__f, __l); }
 360
 361       template<class _InputIterator>
 362         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 363                       const hasher& __hf, const key_equal& __eql,
 364                       const allocator_type& __a = allocator_type())
 365         : _M_ht(__n, __hf, __eql, __a)
 366         { _M_ht.insert_equal(__f, __l); }
 367
 368     public:
 369       size_type
 370       size() const
 371       { return _M_ht.size(); }
 372
 373       size_type
 374       max_size() const
 375       { return _M_ht.max_size(); }
 376
 377       bool
 378       empty() const
 379       { return _M_ht.empty(); }
 380
 381       void
 382       swap(hash_multiset& hs)
 383       { _M_ht.swap(hs._M_ht); }
 384
 385       template<class _Val, class _HF, class _EqK, class _Al>
 386         friend bool
 387         operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
 388                    const hash_multiset<_Val, _HF, _EqK, _Al>&);
 389
 390       iterator
 391       begin() const
 392       { return _M_ht.begin(); }
 393
 394       iterator
 395       end() const
 396       { return _M_ht.end(); }
 397
 398     public:
 399       iterator
 400       insert(const value_type& __obj)
 401       { return _M_ht.insert_equal(__obj); }
 402
 403       template<class _InputIterator>
 404         void
 405         insert(_InputIterator __f, _InputIterator __l)
 406         { _M_ht.insert_equal(__f,__l); }
 407
 408       iterator
 409       insert_noresize(const value_type& __obj)
 410       { return _M_ht.insert_equal_noresize(__obj); }
 411
 412       iterator
 413       find(const key_type& __key) const
 414       { return _M_ht.find(__key); }
 415
 416       size_type
 417       count(const key_type& __key) const
 418       { return _M_ht.count(__key); }
 419
 420       pair<iterator, iterator>
 421       equal_range(const key_type& __key) const
 422       { return _M_ht.equal_range(__key); }
 423
 424       size_type
 425       erase(const key_type& __key)
 426       { return _M_ht.erase(__key); }
 427
 428       void
 429       erase(iterator __it)
 430       { _M_ht.erase(__it); }
 431
 432       void
 433       erase(iterator __f, iterator __l)
 434       { _M_ht.erase(__f, __l); }
 435
 436       void
 437       clear()
 438       { _M_ht.clear(); }
 439
 440     public:
 441       void
 442       resize(size_type __hint)
 443       { _M_ht.resize(__hint); }
 444
 445       size_type
 446       bucket_count() const
 447       { return _M_ht.bucket_count(); }
 448
 449       size_type
 450       max_bucket_count() const
 451       { return _M_ht.max_bucket_count(); }
 452
 453       size_type
 454       elems_in_bucket(size_type __n) const
 455       { return _M_ht.elems_in_bucket(__n); }
 456     };
 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._M_ht == __hs2._M_ht; }
 463
 464   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 465     inline bool
 466     operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 467                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 468     { return !(__hs1 == __hs2); }
 469
 470   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 471     inline void
 472     swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 473          hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 474     { __hs1.swap(__hs2); }
 475
 476 _GLIBCXX_END_NESTED_NAMESPACE
 477
 478 #ifdef _GLIBCXX_DEBUG
 479 # include <debug/hash_set>
 480 #endif
 481
 482 _GLIBCXX_BEGIN_NAMESPACE(std)
 483
 484   // Specialization of insert_iterator so that it will work for hash_set
 485   // and hash_multiset.
 486   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 487     class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
 488                                               _EqualKey, _Alloc> >
 489     {
 490     protected:
 491       typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
 492         _Container;
 493       _Container* container;
 494
 495     public:
 496       typedef _Container          container_type;
 497       typedef output_iterator_tag iterator_category;
 498       typedef void                value_type;
 499       typedef void                difference_type;
 500       typedef void                pointer;
 501       typedef void                reference;
 502
 503       insert_iterator(_Container& __x)
 504       : container(&__x) {}
 505
 506       insert_iterator(_Container& __x, typename _Container::iterator)
 507       : container(&__x) {}
 508
 509       insert_iterator<_Container>&
 510       operator=(const typename _Container::value_type& __value)
 511       {
 512         container->insert(__value);
 513         return *this;
 514       }
 515
 516       insert_iterator<_Container>&
 517       operator*()
 518       { return *this; }
 519
 520       insert_iterator<_Container>&
 521       operator++()
 522       { return *this; }
 523
 524       insert_iterator<_Container>&
 525       operator++(int)
 526       { return *this; }
 527     };
 528
 529   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 530     class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
 531                                                    _EqualKey, _Alloc> >
 532     {
 533     protected:
 534       typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
 535         _Container;
 536       _Container* container;
 537       typename _Container::iterator iter;
 538
 539     public:
 540       typedef _Container          container_type;
 541       typedef output_iterator_tag iterator_category;
 542       typedef void                value_type;
 543       typedef void                difference_type;
 544       typedef void                pointer;
 545       typedef void                reference;
 546
 547       insert_iterator(_Container& __x)
 548       : container(&__x) {}
 549
 550       insert_iterator(_Container& __x, typename _Container::iterator)
 551       : container(&__x) {}
 552
 553       insert_iterator<_Container>&
 554       operator=(const typename _Container::value_type& __value)
 555       {
 556         container->insert(__value);
 557         return *this;
 558       }
 559
 560       insert_iterator<_Container>&
 561       operator*()
 562       { return *this; }
 563
 564       insert_iterator<_Container>&
 565       operator++()
 566       { return *this; }
 567
 568       insert_iterator<_Container>&
 569       operator++(int) { return *this; }
 570     };
 571
 572 _GLIBCXX_END_NAMESPACE
 573
 574 #endif