libstdc++-v3/include/ext/hash_map

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