libstdc++-v3/include/tr1/unordered_map.h

   1 // TR1 unordered_map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2010-2018 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 /** @file tr1/unordered_map.h
  26  *  This is an internal header file, included by other library headers.
  27  *  Do not attempt to use it directly. @headername{tr1/unordered_map}
  28  */
  29
  30 namespace std _GLIBCXX_VISIBILITY(default)
  31 {
  32 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  33
  34 namespace tr1
  35 {
  36   // NB: When we get typedef templates these class definitions
  37   // will be unnecessary.
  38   template<class _Key, class _Tp,
  39            class _Hash = hash<_Key>,
  40            class _Pred = std::equal_to<_Key>,
  41            class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
  42            bool __cache_hash_code = false>
  43     class __unordered_map
  44     : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
  45                         std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
  46                         _Hash, __detail::_Mod_range_hashing,
  47                         __detail::_Default_ranged_hash,
  48                         __detail::_Prime_rehash_policy,
  49                         __cache_hash_code, false, true>
  50     {
  51       typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
  52                          std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
  53                          _Hash, __detail::_Mod_range_hashing,
  54                          __detail::_Default_ranged_hash,
  55                          __detail::_Prime_rehash_policy,
  56                          __cache_hash_code, false, true>
  57         _Base;
  58
  59     public:
  60       typedef typename _Base::size_type       size_type;
  61       typedef typename _Base::hasher          hasher;
  62       typedef typename _Base::key_equal       key_equal;
  63       typedef typename _Base::allocator_type  allocator_type;
  64
  65       explicit
  66       __unordered_map(size_type __n = 10,
  67                       const hasher& __hf = hasher(),
  68                       const key_equal& __eql = key_equal(),
  69                       const allocator_type& __a = allocator_type())
  70       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
  71               __detail::_Default_ranged_hash(),
  72               __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
  73       { }
  74
  75       template<typename _InputIterator>
  76         __unordered_map(_InputIterator __f, _InputIterator __l,
  77                         size_type __n = 10,
  78                         const hasher& __hf = hasher(),
  79                         const key_equal& __eql = key_equal(),
  80                         const allocator_type& __a = allocator_type())
  81         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
  82                 __detail::_Default_ranged_hash(),
  83                 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
  84         { }
  85     };
  86
  87   template<class _Key, class _Tp,
  88            class _Hash = hash<_Key>,
  89            class _Pred = std::equal_to<_Key>,
  90            class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
  91            bool __cache_hash_code = false>
  92     class __unordered_multimap
  93     : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
  94                         _Alloc,
  95                         std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
  96                         _Hash, __detail::_Mod_range_hashing,
  97                         __detail::_Default_ranged_hash,
  98                         __detail::_Prime_rehash_policy,
  99                         __cache_hash_code, false, false>
 100     {
 101       typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
 102                          _Alloc,
 103                          std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
 104                          _Hash, __detail::_Mod_range_hashing,
 105                          __detail::_Default_ranged_hash,
 106                          __detail::_Prime_rehash_policy,
 107                          __cache_hash_code, false, false>
 108         _Base;
 109
 110     public:
 111       typedef typename _Base::size_type       size_type;
 112       typedef typename _Base::hasher          hasher;
 113       typedef typename _Base::key_equal       key_equal;
 114       typedef typename _Base::allocator_type  allocator_type;
 115
 116       explicit
 117       __unordered_multimap(size_type __n = 10,
 118                            const hasher& __hf = hasher(),
 119                            const key_equal& __eql = key_equal(),
 120                            const allocator_type& __a = allocator_type())
 121       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
 122               __detail::_Default_ranged_hash(),
 123               __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
 124       { }
 125
 126
 127       template<typename _InputIterator>
 128         __unordered_multimap(_InputIterator __f, _InputIterator __l,
 129                              typename _Base::size_type __n = 0,
 130                              const hasher& __hf = hasher(),
 131                              const key_equal& __eql = key_equal(),
 132                              const allocator_type& __a = allocator_type())
 133         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
 134                 __detail::_Default_ranged_hash(),
 135                 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
 136         { }
 137     };
 138
 139   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
 140            bool __cache_hash_code>
 141     inline void
 142     swap(__unordered_map<_Key, _Tp, _Hash, _Pred,
 143          _Alloc, __cache_hash_code>& __x,
 144          __unordered_map<_Key, _Tp, _Hash, _Pred,
 145          _Alloc, __cache_hash_code>& __y)
 146     { __x.swap(__y); }
 147
 148   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
 149            bool __cache_hash_code>
 150     inline void
 151     swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred,
 152          _Alloc, __cache_hash_code>& __x,
 153          __unordered_multimap<_Key, _Tp, _Hash, _Pred,
 154          _Alloc, __cache_hash_code>& __y)
 155     { __x.swap(__y); }
 156
 157
 158   /**
 159    *  @brief A standard container composed of unique keys (containing
 160    *  at most one of each key value) that associates values of another type
 161    *  with the keys.
 162    *
 163    *  @ingroup unordered_associative_containers
 164    *
 165    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
 166    *  <a href="tables.html#xx">unordered associative container</a>
 167    *
 168    *  @param  Key  Type of key objects.
 169    *  @param  Tp  Type of mapped objects.
 170    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
 171    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
 172    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
 173    *
 174    * The resulting value type of the container is std::pair<const Key, Tp>.
 175    */
 176   template<class _Key, class _Tp,
 177            class _Hash = hash<_Key>,
 178            class _Pred = std::equal_to<_Key>,
 179            class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
 180     class unordered_map
 181     : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
 182     {
 183       typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>  _Base;
 184
 185     public:
 186       typedef typename _Base::value_type      value_type;
 187       typedef typename _Base::size_type       size_type;
 188       typedef typename _Base::hasher          hasher;
 189       typedef typename _Base::key_equal       key_equal;
 190       typedef typename _Base::allocator_type  allocator_type;
 191
 192       explicit
 193       unordered_map(size_type __n = 10,
 194                     const hasher& __hf = hasher(),
 195                     const key_equal& __eql = key_equal(),
 196                     const allocator_type& __a = allocator_type())
 197       : _Base(__n, __hf, __eql, __a)
 198       { }
 199
 200       template<typename _InputIterator>
 201         unordered_map(_InputIterator __f, _InputIterator __l,
 202                       size_type __n = 10,
 203                       const hasher& __hf = hasher(),
 204                       const key_equal& __eql = key_equal(),
 205                       const allocator_type& __a = allocator_type())
 206         : _Base(__f, __l, __n, __hf, __eql, __a)
 207         { }
 208     };
 209
 210   /**
 211    *  @brief A standard container composed of equivalent keys
 212    *  (possibly containing multiple of each key value) that associates
 213    *  values of another type with the keys.
 214    *
 215    *  @ingroup unordered_associative_containers
 216    *
 217    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
 218    *  <a href="tables.html#xx">unordered associative container</a>
 219    *
 220    *  @param  Key  Type of key objects.
 221    *  @param  Tp  Type of mapped objects.
 222    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
 223    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
 224    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
 225    *
 226    * The resulting value type of the container is std::pair<const Key, Tp>.
 227    */
 228   template<class _Key, class _Tp,
 229            class _Hash = hash<_Key>,
 230            class _Pred = std::equal_to<_Key>,
 231            class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
 232     class unordered_multimap
 233     : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
 234     {
 235       typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>  _Base;
 236
 237     public:
 238       typedef typename _Base::value_type      value_type;
 239       typedef typename _Base::size_type       size_type;
 240       typedef typename _Base::hasher          hasher;
 241       typedef typename _Base::key_equal       key_equal;
 242       typedef typename _Base::allocator_type  allocator_type;
 243
 244       explicit
 245       unordered_multimap(size_type __n = 10,
 246                          const hasher& __hf = hasher(),
 247                          const key_equal& __eql = key_equal(),
 248                          const allocator_type& __a = allocator_type())
 249       : _Base(__n, __hf, __eql, __a)
 250       { }
 251
 252
 253       template<typename _InputIterator>
 254         unordered_multimap(_InputIterator __f, _InputIterator __l,
 255                            typename _Base::size_type __n = 0,
 256                            const hasher& __hf = hasher(),
 257                            const key_equal& __eql = key_equal(),
 258                            const allocator_type& __a = allocator_type())
 259         : _Base(__f, __l, __n, __hf, __eql, __a)
 260         { }
 261
 262     };
 263
 264   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 265     inline void
 266     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 267          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 268     { __x.swap(__y); }
 269
 270   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 271     inline void
 272     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 273          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 274     { __x.swap(__y); }
 275 }
 276
 277 _GLIBCXX_END_NAMESPACE_VERSION
 278 }