libstdc++-v3/include/backward/hash_map

   1 // Hashing map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2014 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_map
  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 _BACKWARD_HASH_MAP
  57 #define _BACKWARD_HASH_MAP 1
  58
  59 #ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
  60 #include "backward_warning.h"
  61 #endif
  62
  63 #include <bits/c++config.h>
  64 #include <backward/hashtable.h>
  65 #include <bits/concept_check.h>
  66
  67 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
  68 {
  69 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  70
  71   using std::equal_to;
  72   using std::allocator;
  73   using std::pair;
  74   using std::_Select1st;
  75
  76   /**
  77    *  This is an SGI extension.
  78    *  @ingroup SGIextensions
  79    *  @doctodo
  80    */
  81   template<class _Key, class _Tp, class _HashFn = hash<_Key>,
  82            class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
  83     class hash_map
  84     {
  85     private:
  86       typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
  87                         _Select1st<pair<const _Key, _Tp> >,
  88                         _EqualKey, _Alloc> _Ht;
  89
  90       _Ht _M_ht;
  91
  92     public:
  93       typedef typename _Ht::key_type key_type;
  94       typedef _Tp data_type;
  95       typedef _Tp mapped_type;
  96       typedef typename _Ht::value_type value_type;
  97       typedef typename _Ht::hasher hasher;
  98       typedef typename _Ht::key_equal key_equal;
  99
 100       typedef typename _Ht::size_type size_type;
 101       typedef typename _Ht::difference_type difference_type;
 102       typedef typename _Ht::pointer pointer;
 103       typedef typename _Ht::const_pointer const_pointer;
 104       typedef typename _Ht::reference reference;
 105       typedef typename _Ht::const_reference const_reference;
 106
 107       typedef typename _Ht::iterator iterator;
 108       typedef typename _Ht::const_iterator const_iterator;
 109
 110       typedef typename _Ht::allocator_type allocator_type;
 111
 112       hasher
 113       hash_funct() const
 114       { return _M_ht.hash_funct(); }
 115
 116       key_equal
 117       key_eq() const
 118       { return _M_ht.key_eq(); }
 119
 120       allocator_type
 121       get_allocator() const
 122       { return _M_ht.get_allocator(); }
 123
 124       hash_map()
 125       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 126
 127       explicit
 128       hash_map(size_type __n)
 129       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 130
 131       hash_map(size_type __n, const hasher& __hf)
 132       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 133
 134       hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
 135                const allocator_type& __a = allocator_type())
 136       : _M_ht(__n, __hf, __eql, __a) {}
 137
 138       template<class _InputIterator>
 139         hash_map(_InputIterator __f, _InputIterator __l)
 140         : _M_ht(100, hasher(), key_equal(), allocator_type())
 141         { _M_ht.insert_unique(__f, __l); }
 142
 143       template<class _InputIterator>
 144         hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
 145         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 146         { _M_ht.insert_unique(__f, __l); }
 147
 148       template<class _InputIterator>
 149         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 150                  const hasher& __hf)
 151         : _M_ht(__n, __hf, key_equal(), allocator_type())
 152         { _M_ht.insert_unique(__f, __l); }
 153
 154       template<class _InputIterator>
 155         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 156                  const hasher& __hf, const key_equal& __eql,
 157                  const allocator_type& __a = allocator_type())
 158         : _M_ht(__n, __hf, __eql, __a)
 159         { _M_ht.insert_unique(__f, __l); }
 160
 161       size_type
 162       size() const
 163       { return _M_ht.size(); }
 164
 165       size_type
 166       max_size() const
 167       { return _M_ht.max_size(); }
 168
 169       bool
 170       empty() const
 171       { return _M_ht.empty(); }
 172
 173       void
 174       swap(hash_map& __hs)
 175       { _M_ht.swap(__hs._M_ht); }
 176
 177       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
 178         friend bool
 179         operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
 180                     const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
 181
 182       iterator
 183       begin()
 184       { return _M_ht.begin(); }
 185
 186       iterator
 187       end()
 188       { return _M_ht.end(); }
 189
 190       const_iterator
 191       begin() const
 192       { return _M_ht.begin(); }
 193
 194       const_iterator
 195       end() const
 196       { return _M_ht.end(); }
 197
 198       pair<iterator, bool>
 199       insert(const value_type& __obj)
 200       { return _M_ht.insert_unique(__obj); }
 201
 202       template<class _InputIterator>
 203         void
 204         insert(_InputIterator __f, _InputIterator __l)
 205         { _M_ht.insert_unique(__f, __l); }
 206
 207       pair<iterator, bool>
 208       insert_noresize(const value_type& __obj)
 209       { return _M_ht.insert_unique_noresize(__obj); }
 210
 211       iterator
 212       find(const key_type& __key)
 213       { return _M_ht.find(__key); }
 214
 215       const_iterator
 216       find(const key_type& __key) const
 217       { return _M_ht.find(__key); }
 218
 219       _Tp&
 220       operator[](const key_type& __key)
 221       { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
 222
 223       size_type
 224       count(const key_type& __key) const
 225       { return _M_ht.count(__key); }
 226
 227       pair<iterator, iterator>
 228       equal_range(const key_type& __key)
 229       { return _M_ht.equal_range(__key); }
 230
 231       pair<const_iterator, const_iterator>
 232       equal_range(const key_type& __key) const
 233       { return _M_ht.equal_range(__key); }
 234
 235       size_type
 236       erase(const key_type& __key)
 237       {return _M_ht.erase(__key); }
 238
 239       void
 240       erase(iterator __it)
 241       { _M_ht.erase(__it); }
 242
 243       void
 244       erase(iterator __f, iterator __l)
 245       { _M_ht.erase(__f, __l); }
 246
 247       void
 248       clear()
 249       { _M_ht.clear(); }
 250
 251       void
 252       resize(size_type __hint)
 253       { _M_ht.resize(__hint); }
 254
 255       size_type
 256       bucket_count() const
 257       { return _M_ht.bucket_count(); }
 258
 259       size_type
 260       max_bucket_count() const
 261       { return _M_ht.max_bucket_count(); }
 262
 263       size_type
 264       elems_in_bucket(size_type __n) const
 265       { return _M_ht.elems_in_bucket(__n); }
 266     };
 267
 268   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 269     inline bool
 270     operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 271                const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 272     { return __hm1._M_ht == __hm2._M_ht; }
 273
 274   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 275     inline bool
 276     operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 277                const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 278     { return !(__hm1 == __hm2); }
 279
 280   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 281     inline void
 282     swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 283          hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 284     { __hm1.swap(__hm2); }
 285
 286
 287   /**
 288    *  This is an SGI extension.
 289    *  @ingroup SGIextensions
 290    *  @doctodo
 291    */
 292   template<class _Key, class _Tp,
 293            class _HashFn = hash<_Key>,
 294            class _EqualKey = equal_to<_Key>,
 295            class _Alloc = allocator<_Tp> >
 296     class hash_multimap
 297     {
 298       // concept requirements
 299       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
 300       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 301       __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
 302       __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
 303
 304     private:
 305       typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
 306                         _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
 307           _Ht;
 308
 309       _Ht _M_ht;
 310
 311     public:
 312       typedef typename _Ht::key_type key_type;
 313       typedef _Tp data_type;
 314       typedef _Tp mapped_type;
 315       typedef typename _Ht::value_type value_type;
 316       typedef typename _Ht::hasher hasher;
 317       typedef typename _Ht::key_equal key_equal;
 318
 319       typedef typename _Ht::size_type size_type;
 320       typedef typename _Ht::difference_type difference_type;
 321       typedef typename _Ht::pointer pointer;
 322       typedef typename _Ht::const_pointer const_pointer;
 323       typedef typename _Ht::reference reference;
 324       typedef typename _Ht::const_reference const_reference;
 325
 326       typedef typename _Ht::iterator iterator;
 327       typedef typename _Ht::const_iterator const_iterator;
 328
 329       typedef typename _Ht::allocator_type allocator_type;
 330
 331       hasher
 332       hash_funct() const
 333       { return _M_ht.hash_funct(); }
 334
 335       key_equal
 336       key_eq() const
 337       { return _M_ht.key_eq(); }
 338
 339       allocator_type
 340       get_allocator() const
 341       { return _M_ht.get_allocator(); }
 342
 343       hash_multimap()
 344       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 345
 346       explicit
 347       hash_multimap(size_type __n)
 348       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 349
 350       hash_multimap(size_type __n, const hasher& __hf)
 351       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 352
 353       hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
 354                     const allocator_type& __a = allocator_type())
 355       : _M_ht(__n, __hf, __eql, __a) {}
 356
 357       template<class _InputIterator>
 358         hash_multimap(_InputIterator __f, _InputIterator __l)
 359         : _M_ht(100, hasher(), key_equal(), allocator_type())
 360         { _M_ht.insert_equal(__f, __l); }
 361
 362       template<class _InputIterator>
 363         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
 364         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 365         { _M_ht.insert_equal(__f, __l); }
 366
 367       template<class _InputIterator>
 368         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 369                       const hasher& __hf)
 370         : _M_ht(__n, __hf, key_equal(), allocator_type())
 371         { _M_ht.insert_equal(__f, __l); }
 372
 373       template<class _InputIterator>
 374         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 375                       const hasher& __hf, const key_equal& __eql,
 376                       const allocator_type& __a = allocator_type())
 377         : _M_ht(__n, __hf, __eql, __a)
 378         { _M_ht.insert_equal(__f, __l); }
 379
 380       size_type
 381       size() const
 382       { return _M_ht.size(); }
 383
 384       size_type
 385       max_size() const
 386       { return _M_ht.max_size(); }
 387
 388       bool
 389       empty() const
 390       { return _M_ht.empty(); }
 391
 392       void
 393       swap(hash_multimap& __hs)
 394       { _M_ht.swap(__hs._M_ht); }
 395
 396       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
 397         friend bool
 398         operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
 399                    const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
 400
 401       iterator
 402       begin()
 403       { return _M_ht.begin(); }
 404
 405       iterator
 406       end()
 407       { return _M_ht.end(); }
 408
 409       const_iterator
 410       begin() const
 411       { return _M_ht.begin(); }
 412
 413       const_iterator
 414       end() const
 415       { return _M_ht.end(); }
 416
 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)
 432       { return _M_ht.find(__key); }
 433
 434       const_iterator
 435       find(const key_type& __key) const
 436       { return _M_ht.find(__key); }
 437
 438       size_type
 439       count(const key_type& __key) const
 440       { return _M_ht.count(__key); }
 441
 442       pair<iterator, iterator>
 443       equal_range(const key_type& __key)
 444       { return _M_ht.equal_range(__key); }
 445
 446       pair<const_iterator, const_iterator>
 447       equal_range(const key_type& __key) const
 448       { return _M_ht.equal_range(__key); }
 449
 450       size_type
 451       erase(const key_type& __key)
 452       { return _M_ht.erase(__key); }
 453
 454       void
 455       erase(iterator __it)
 456       { _M_ht.erase(__it); }
 457
 458       void
 459       erase(iterator __f, iterator __l)
 460       { _M_ht.erase(__f, __l); }
 461
 462       void
 463       clear()
 464       { _M_ht.clear(); }
 465
 466       void
 467       resize(size_type __hint)
 468       { _M_ht.resize(__hint); }
 469
 470       size_type
 471       bucket_count() const
 472       { return _M_ht.bucket_count(); }
 473
 474       size_type
 475       max_bucket_count() const
 476       { return _M_ht.max_bucket_count(); }
 477
 478       size_type
 479       elems_in_bucket(size_type __n) const
 480       { return _M_ht.elems_in_bucket(__n); }
 481     };
 482
 483   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 484     inline bool
 485     operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
 486                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
 487     { return __hm1._M_ht == __hm2._M_ht; }
 488
 489   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 490     inline bool
 491     operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
 492                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
 493     { return !(__hm1 == __hm2); }
 494
 495   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 496     inline void
 497     swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 498          hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 499     { __hm1.swap(__hm2); }
 500
 501 _GLIBCXX_END_NAMESPACE_VERSION
 502 } // namespace
 503
 504 namespace std _GLIBCXX_VISIBILITY(default)
 505 {
 506 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 507
 508   // Specialization of insert_iterator so that it will work for hash_map
 509   // and hash_multimap.
 510   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 511     class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
 512                                               _EqKey, _Alloc> >
 513     {
 514     protected:
 515       typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
 516         _Container;
 517       _Container* container;
 518
 519     public:
 520       typedef _Container          container_type;
 521       typedef output_iterator_tag iterator_category;
 522       typedef void                value_type;
 523       typedef void                difference_type;
 524       typedef void                pointer;
 525       typedef void                reference;
 526
 527       insert_iterator(_Container& __x)
 528       : container(&__x) {}
 529
 530       insert_iterator(_Container& __x, typename _Container::iterator)
 531       : container(&__x) {}
 532
 533       insert_iterator<_Container>&
 534       operator=(const typename _Container::value_type& __value)
 535       {
 536         container->insert(__value);
 537         return *this;
 538       }
 539
 540       insert_iterator<_Container>&
 541       operator*()
 542       { return *this; }
 543
 544       insert_iterator<_Container>&
 545       operator++() { return *this; }
 546
 547       insert_iterator<_Container>&
 548       operator++(int)
 549       { return *this; }
 550     };
 551
 552   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 553     class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
 554                                                    _EqKey, _Alloc> >
 555     {
 556     protected:
 557       typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
 558         _Container;
 559       _Container* container;
 560       typename _Container::iterator iter;
 561
 562     public:
 563       typedef _Container          container_type;
 564       typedef output_iterator_tag iterator_category;
 565       typedef void                value_type;
 566       typedef void                difference_type;
 567       typedef void                pointer;
 568       typedef void                reference;
 569
 570       insert_iterator(_Container& __x)
 571       : container(&__x) {}
 572
 573       insert_iterator(_Container& __x, typename _Container::iterator)
 574       : container(&__x) {}
 575
 576       insert_iterator<_Container>&
 577       operator=(const typename _Container::value_type& __value)
 578       {
 579         container->insert(__value);
 580         return *this;
 581       }
 582
 583       insert_iterator<_Container>&
 584       operator*()
 585       { return *this; }
 586
 587       insert_iterator<_Container>&
 588       operator++()
 589       { return *this; }
 590
 591       insert_iterator<_Container>&
 592       operator++(int)
 593       { return *this; }
 594     };
 595
 596 _GLIBCXX_END_NAMESPACE_VERSION
 597 } // namespace
 598
 599 #endif