libstdc++-v3/include/backward/hash_map

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