libstdc++-v3/include/ext/hash_map

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