libstdc++-v3/include/backward/hash_set

   1 // Hashing set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009 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 _HASH_SET
  57 #define _HASH_SET 1
  58
  59 #include "backward_warning.h"
  60 #include <bits/c++config.h>
  61 #ifdef _GLIBCXX_PROFILE
  62 #include <profile/hashtable.h>
  63 #else
  64 #include <backward/hashtable.h>
  65 #endif
  66 #include <bits/concept_check.h>
  67
  68 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
  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_NAMESPACE
 469
 470 _GLIBCXX_BEGIN_NAMESPACE(std)
 471
 472   // Specialization of insert_iterator so that it will work for hash_set
 473   // and hash_multiset.
 474   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 475     class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
 476                                               _EqualKey, _Alloc> >
 477     {
 478     protected:
 479       typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
 480         _Container;
 481       _Container* container;
 482
 483     public:
 484       typedef _Container          container_type;
 485       typedef output_iterator_tag iterator_category;
 486       typedef void                value_type;
 487       typedef void                difference_type;
 488       typedef void                pointer;
 489       typedef void                reference;
 490
 491       insert_iterator(_Container& __x)
 492       : container(&__x) {}
 493
 494       insert_iterator(_Container& __x, typename _Container::iterator)
 495       : container(&__x) {}
 496
 497       insert_iterator<_Container>&
 498       operator=(const typename _Container::value_type& __value)
 499       {
 500         container->insert(__value);
 501         return *this;
 502       }
 503
 504       insert_iterator<_Container>&
 505       operator*()
 506       { return *this; }
 507
 508       insert_iterator<_Container>&
 509       operator++()
 510       { return *this; }
 511
 512       insert_iterator<_Container>&
 513       operator++(int)
 514       { return *this; }
 515     };
 516
 517   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 518     class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
 519                                                    _EqualKey, _Alloc> >
 520     {
 521     protected:
 522       typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
 523         _Container;
 524       _Container* container;
 525       typename _Container::iterator iter;
 526
 527     public:
 528       typedef _Container          container_type;
 529       typedef output_iterator_tag iterator_category;
 530       typedef void                value_type;
 531       typedef void                difference_type;
 532       typedef void                pointer;
 533       typedef void                reference;
 534
 535       insert_iterator(_Container& __x)
 536       : container(&__x) {}
 537
 538       insert_iterator(_Container& __x, typename _Container::iterator)
 539       : container(&__x) {}
 540
 541       insert_iterator<_Container>&
 542       operator=(const typename _Container::value_type& __value)
 543       {
 544         container->insert(__value);
 545         return *this;
 546       }
 547
 548       insert_iterator<_Container>&
 549       operator*()
 550       { return *this; }
 551
 552       insert_iterator<_Container>&
 553       operator++()
 554       { return *this; }
 555
 556       insert_iterator<_Container>&
 557       operator++(int) { return *this; }
 558     };
 559
 560 _GLIBCXX_END_NAMESPACE
 561
 562 #endif