libstdc++-v3/include/backward/hash_set

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