libstdc++-v3/include/ext/hash_map

   1 // Hashing map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002 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).  You should only
  59  *  include this header if you are using GCC 3 or later.
  60  */
  61
  62 #ifndef __SGI_STL_INTERNAL_HASH_MAP_H
  63 #define __SGI_STL_INTERNAL_HASH_MAP_H
  64
  65 #include <ext/stl_hashtable.h>
  66 #include <bits/concept_check.h>
  67
  68 namespace __gnu_cxx
  69 {
  70 using std::equal_to;
  71 using std::allocator;
  72 using std::pair;
  73 using std::_Select1st;
  74
  75 // Forward declaration of equality operator; needed for friend declaration.
  76
  77 template <class _Key, class _Tp,
  78           class _HashFcn  = hash<_Key>,
  79           class _EqualKey = equal_to<_Key>,
  80           class _Alloc =  allocator<_Tp> >
  81 class hash_map;
  82
  83 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
  84 inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,
  85                        const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);
  86 /**
  87  *  This is an SGI extension.
  88  *  @ingroup SGIextensions
  89  *  @doctodo
  90 */
  91 template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
  92           class _Alloc>
  93 class hash_map
  94 {
  95 private:
  96   typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn,
  97                     _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht;
  98   _Ht _M_ht;
  99
 100 public:
 101   typedef typename _Ht::key_type key_type;
 102   typedef _Tp data_type;
 103   typedef _Tp mapped_type;
 104   typedef typename _Ht::value_type value_type;
 105   typedef typename _Ht::hasher hasher;
 106   typedef typename _Ht::key_equal key_equal;
 107
 108   typedef typename _Ht::size_type size_type;
 109   typedef typename _Ht::difference_type difference_type;
 110   typedef typename _Ht::pointer pointer;
 111   typedef typename _Ht::const_pointer const_pointer;
 112   typedef typename _Ht::reference reference;
 113   typedef typename _Ht::const_reference const_reference;
 114
 115   typedef typename _Ht::iterator iterator;
 116   typedef typename _Ht::const_iterator const_iterator;
 117
 118   typedef typename _Ht::allocator_type allocator_type;
 119
 120   hasher hash_funct() const { return _M_ht.hash_funct(); }
 121   key_equal key_eq() const { return _M_ht.key_eq(); }
 122   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
 123
 124 public:
 125   hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 126   explicit hash_map(size_type __n)
 127     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 128   hash_map(size_type __n, const hasher& __hf)
 129     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 130   hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
 131            const allocator_type& __a = allocator_type())
 132     : _M_ht(__n, __hf, __eql, __a) {}
 133
 134   template <class _InputIterator>
 135   hash_map(_InputIterator __f, _InputIterator __l)
 136     : _M_ht(100, hasher(), key_equal(), allocator_type())
 137     { _M_ht.insert_unique(__f, __l); }
 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   template <class _InputIterator>
 143   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 144            const hasher& __hf)
 145     : _M_ht(__n, __hf, key_equal(), allocator_type())
 146     { _M_ht.insert_unique(__f, __l); }
 147   template <class _InputIterator>
 148   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 149            const hasher& __hf, const key_equal& __eql,
 150            const allocator_type& __a = allocator_type())
 151     : _M_ht(__n, __hf, __eql, __a)
 152     { _M_ht.insert_unique(__f, __l); }
 153
 154 public:
 155   size_type size() const { return _M_ht.size(); }
 156   size_type max_size() const { return _M_ht.max_size(); }
 157   bool empty() const { return _M_ht.empty(); }
 158   void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); }
 159
 160   template <class _K1, class _T1, class _HF, class _EqK, class _Al>
 161   friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
 162                           const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
 163
 164   iterator begin() { return _M_ht.begin(); }
 165   iterator end() { return _M_ht.end(); }
 166   const_iterator begin() const { return _M_ht.begin(); }
 167   const_iterator end() const { return _M_ht.end(); }
 168
 169 public:
 170   pair<iterator,bool> insert(const value_type& __obj)
 171     { return _M_ht.insert_unique(__obj); }
 172   template <class _InputIterator>
 173   void insert(_InputIterator __f, _InputIterator __l)
 174     { _M_ht.insert_unique(__f,__l); }
 175   pair<iterator,bool> insert_noresize(const value_type& __obj)
 176     { return _M_ht.insert_unique_noresize(__obj); }
 177
 178   iterator find(const key_type& __key) { return _M_ht.find(__key); }
 179   const_iterator find(const key_type& __key) const
 180     { return _M_ht.find(__key); }
 181
 182   _Tp& operator[](const key_type& __key) {
 183     return _M_ht.find_or_insert(value_type(__key, _Tp())).second;
 184   }
 185
 186   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
 187
 188   pair<iterator, iterator> equal_range(const key_type& __key)
 189     { return _M_ht.equal_range(__key); }
 190   pair<const_iterator, const_iterator>
 191   equal_range(const key_type& __key) const
 192     { return _M_ht.equal_range(__key); }
 193
 194   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
 195   void erase(iterator __it) { _M_ht.erase(__it); }
 196   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 197   void clear() { _M_ht.clear(); }
 198
 199   void resize(size_type __hint) { _M_ht.resize(__hint); }
 200   size_type bucket_count() const { return _M_ht.bucket_count(); }
 201   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 202   size_type elems_in_bucket(size_type __n) const
 203     { return _M_ht.elems_in_bucket(__n); }
 204 };
 205
 206 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
 207 inline bool
 208 operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
 209            const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
 210 {
 211   return __hm1._M_ht == __hm2._M_ht;
 212 }
 213
 214 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
 215 inline bool
 216 operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
 217            const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) {
 218   return !(__hm1 == __hm2);
 219 }
 220
 221 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
 222 inline void
 223 swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
 224      hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
 225 {
 226   __hm1.swap(__hm2);
 227 }
 228
 229 // Forward declaration of equality operator; needed for friend declaration.
 230
 231 template <class _Key, class _Tp,
 232           class _HashFcn  = hash<_Key>,
 233           class _EqualKey = equal_to<_Key>,
 234           class _Alloc =  allocator<_Tp> >
 235 class hash_multimap;
 236
 237 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 238 inline bool
 239 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
 240            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2);
 241
 242 /**
 243  *  This is an SGI extension.
 244  *  @ingroup SGIextensions
 245  *  @doctodo
 246 */
 247 template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc>
 248 class hash_multimap
 249 {
 250   // concept requirements
 251   __glibcpp_class_requires(_Key, _SGIAssignableConcept)
 252   __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
 253   __glibcpp_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept);
 254   __glibcpp_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept);
 255
 256 private:
 257   typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn,
 258                     _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
 259           _Ht;
 260   _Ht _M_ht;
 261
 262 public:
 263   typedef typename _Ht::key_type key_type;
 264   typedef _Tp data_type;
 265   typedef _Tp mapped_type;
 266   typedef typename _Ht::value_type value_type;
 267   typedef typename _Ht::hasher hasher;
 268   typedef typename _Ht::key_equal key_equal;
 269
 270   typedef typename _Ht::size_type size_type;
 271   typedef typename _Ht::difference_type difference_type;
 272   typedef typename _Ht::pointer pointer;
 273   typedef typename _Ht::const_pointer const_pointer;
 274   typedef typename _Ht::reference reference;
 275   typedef typename _Ht::const_reference const_reference;
 276
 277   typedef typename _Ht::iterator iterator;
 278   typedef typename _Ht::const_iterator const_iterator;
 279
 280   typedef typename _Ht::allocator_type allocator_type;
 281
 282   hasher hash_funct() const { return _M_ht.hash_funct(); }
 283   key_equal key_eq() const { return _M_ht.key_eq(); }
 284   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
 285
 286 public:
 287   hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 288   explicit hash_multimap(size_type __n)
 289     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 290   hash_multimap(size_type __n, const hasher& __hf)
 291     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 292   hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
 293                 const allocator_type& __a = allocator_type())
 294     : _M_ht(__n, __hf, __eql, __a) {}
 295
 296   template <class _InputIterator>
 297   hash_multimap(_InputIterator __f, _InputIterator __l)
 298     : _M_ht(100, hasher(), key_equal(), allocator_type())
 299     { _M_ht.insert_equal(__f, __l); }
 300   template <class _InputIterator>
 301   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
 302     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 303     { _M_ht.insert_equal(__f, __l); }
 304   template <class _InputIterator>
 305   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 306                 const hasher& __hf)
 307     : _M_ht(__n, __hf, key_equal(), allocator_type())
 308     { _M_ht.insert_equal(__f, __l); }
 309   template <class _InputIterator>
 310   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 311                 const hasher& __hf, const key_equal& __eql,
 312                 const allocator_type& __a = allocator_type())
 313     : _M_ht(__n, __hf, __eql, __a)
 314     { _M_ht.insert_equal(__f, __l); }
 315
 316 public:
 317   size_type size() const { return _M_ht.size(); }
 318   size_type max_size() const { return _M_ht.max_size(); }
 319   bool empty() const { return _M_ht.empty(); }
 320   void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); }
 321
 322   template <class _K1, class _T1, class _HF, class _EqK, class _Al>
 323   friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
 324                           const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
 325
 326   iterator begin() { return _M_ht.begin(); }
 327   iterator end() { return _M_ht.end(); }
 328   const_iterator begin() const { return _M_ht.begin(); }
 329   const_iterator end() const { return _M_ht.end(); }
 330
 331 public:
 332   iterator insert(const value_type& __obj)
 333     { return _M_ht.insert_equal(__obj); }
 334   template <class _InputIterator>
 335   void insert(_InputIterator __f, _InputIterator __l)
 336     { _M_ht.insert_equal(__f,__l); }
 337   iterator insert_noresize(const value_type& __obj)
 338     { return _M_ht.insert_equal_noresize(__obj); }
 339
 340   iterator find(const key_type& __key) { return _M_ht.find(__key); }
 341   const_iterator find(const key_type& __key) const
 342     { return _M_ht.find(__key); }
 343
 344   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
 345
 346   pair<iterator, iterator> equal_range(const key_type& __key)
 347     { return _M_ht.equal_range(__key); }
 348   pair<const_iterator, const_iterator>
 349   equal_range(const key_type& __key) const
 350     { return _M_ht.equal_range(__key); }
 351
 352   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
 353   void erase(iterator __it) { _M_ht.erase(__it); }
 354   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 355   void clear() { _M_ht.clear(); }
 356
 357 public:
 358   void resize(size_type __hint) { _M_ht.resize(__hint); }
 359   size_type bucket_count() const { return _M_ht.bucket_count(); }
 360   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 361   size_type elems_in_bucket(size_type __n) const
 362     { return _M_ht.elems_in_bucket(__n); }
 363 };
 364
 365 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 366 inline bool
 367 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
 368            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2)
 369 {
 370   return __hm1._M_ht == __hm2._M_ht;
 371 }
 372
 373 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 374 inline bool
 375 operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
 376            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) {
 377   return !(__hm1 == __hm2);
 378 }
 379
 380 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
 381 inline void
 382 swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
 383      hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
 384 {
 385   __hm1.swap(__hm2);
 386 }
 387
 388 } // namespace __gnu_cxx
 389
 390 namespace std
 391 {
 392 // Specialization of insert_iterator so that it will work for hash_map
 393 // and hash_multimap.
 394
 395 template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 396 class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
 397 protected:
 398   typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
 399   _Container* container;
 400 public:
 401   typedef _Container          container_type;
 402   typedef output_iterator_tag iterator_category;
 403   typedef void                value_type;
 404   typedef void                difference_type;
 405   typedef void                pointer;
 406   typedef void                reference;
 407
 408   insert_iterator(_Container& __x) : container(&__x) {}
 409   insert_iterator(_Container& __x, typename _Container::iterator)
 410     : container(&__x) {}
 411   insert_iterator<_Container>&
 412   operator=(const typename _Container::value_type& __value) {
 413     container->insert(__value);
 414     return *this;
 415   }
 416   insert_iterator<_Container>& operator*() { return *this; }
 417   insert_iterator<_Container>& operator++() { return *this; }
 418   insert_iterator<_Container>& operator++(int) { return *this; }
 419 };
 420
 421 template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 422 class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
 423 protected:
 424   typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
 425   _Container* container;
 426   typename _Container::iterator iter;
 427 public:
 428   typedef _Container          container_type;
 429   typedef output_iterator_tag iterator_category;
 430   typedef void                value_type;
 431   typedef void                difference_type;
 432   typedef void                pointer;
 433   typedef void                reference;
 434
 435   insert_iterator(_Container& __x) : container(&__x) {}
 436   insert_iterator(_Container& __x, typename _Container::iterator)
 437     : container(&__x) {}
 438   insert_iterator<_Container>&
 439   operator=(const typename _Container::value_type& __value) {
 440     container->insert(__value);
 441     return *this;
 442   }
 443   insert_iterator<_Container>& operator*() { return *this; }
 444   insert_iterator<_Container>& operator++() { return *this; }
 445   insert_iterator<_Container>& operator++(int) { return *this; }
 446 };
 447
 448 } // namespace std
 449
 450 #endif /* __SGI_STL_INTERNAL_HASH_MAP_H */
 451
 452 // Local Variables:
 453 // mode:C++
 454 // End: