mingw/lib/gcc/mingw32/4.3.3/include/c++/backward/hash_map

   1 // Hashing map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2004, 2005, 2006 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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 backward/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 "backward_warning.h"
  65 #include <bits/c++config.h>
  66 #include <backward/hashtable.h>
  67 #include <bits/concept_check.h>
  68
  69 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
  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
 502
 503 _GLIBCXX_BEGIN_NAMESPACE(std)
 504
 505   // Specialization of insert_iterator so that it will work for hash_map
 506   // and hash_multimap.
 507   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 508     class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
 509                                               _EqKey, _Alloc> >
 510     {
 511     protected:
 512       typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
 513         _Container;
 514       _Container* container;
 515
 516     public:
 517       typedef _Container          container_type;
 518       typedef output_iterator_tag iterator_category;
 519       typedef void                value_type;
 520       typedef void                difference_type;
 521       typedef void                pointer;
 522       typedef void                reference;
 523
 524       insert_iterator(_Container& __x)
 525       : container(&__x) {}
 526
 527       insert_iterator(_Container& __x, typename _Container::iterator)
 528       : container(&__x) {}
 529
 530       insert_iterator<_Container>&
 531       operator=(const typename _Container::value_type& __value)
 532       {
 533         container->insert(__value);
 534         return *this;
 535       }
 536
 537       insert_iterator<_Container>&
 538       operator*()
 539       { return *this; }
 540
 541       insert_iterator<_Container>&
 542       operator++() { return *this; }
 543
 544       insert_iterator<_Container>&
 545       operator++(int)
 546       { return *this; }
 547     };
 548
 549   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 550     class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
 551                                                    _EqKey, _Alloc> >
 552     {
 553     protected:
 554       typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
 555         _Container;
 556       _Container* container;
 557       typename _Container::iterator iter;
 558
 559     public:
 560       typedef _Container          container_type;
 561       typedef output_iterator_tag iterator_category;
 562       typedef void                value_type;
 563       typedef void                difference_type;
 564       typedef void                pointer;
 565       typedef void                reference;
 566
 567       insert_iterator(_Container& __x)
 568       : container(&__x) {}
 569
 570       insert_iterator(_Container& __x, typename _Container::iterator)
 571       : container(&__x) {}
 572
 573       insert_iterator<_Container>&
 574       operator=(const typename _Container::value_type& __value)
 575       {
 576         container->insert(__value);
 577         return *this;
 578       }
 579
 580       insert_iterator<_Container>&
 581       operator*()
 582       { return *this; }
 583
 584       insert_iterator<_Container>&
 585       operator++()
 586       { return *this; }
 587
 588       insert_iterator<_Container>&
 589       operator++(int)
 590       { return *this; }
 591     };
 592
 593 _GLIBCXX_END_NAMESPACE
 594
 595 #endif