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

   1 // unordered_map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2010, 2011 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 bits/unordered_map.h
  26  *  This is an internal header file, included by other library headers.
  27  *  Do not attempt to use it directly. @headername{unordered_map}
  28  */
  29
  30 #ifndef _UNORDERED_MAP_H
  31 #define _UNORDERED_MAP_H
  32
  33 namespace std _GLIBCXX_VISIBILITY(default)
  34 {
  35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  36
  37   // NB: When we get typedef templates these class definitions
  38   // will be unnecessary.
  39   template<class _Key, class _Tp,
  40            class _Hash = hash<_Key>,
  41            class _Pred = std::equal_to<_Key>,
  42            class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
  43            bool __cache_hash_code = false>
  44     class __unordered_map
  45     : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
  46                         std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
  47                         _Hash, __detail::_Mod_range_hashing,
  48                         __detail::_Default_ranged_hash,
  49                         __detail::_Prime_rehash_policy,
  50                         __cache_hash_code, false, true>
  51     {
  52       typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
  53                          std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
  54                          _Hash, __detail::_Mod_range_hashing,
  55                          __detail::_Default_ranged_hash,
  56                          __detail::_Prime_rehash_policy,
  57                          __cache_hash_code, false, true>
  58         _Base;
  59
  60     public:
  61       typedef typename _Base::value_type      value_type;
  62       typedef typename _Base::size_type       size_type;
  63       typedef typename _Base::hasher          hasher;
  64       typedef typename _Base::key_equal       key_equal;
  65       typedef typename _Base::allocator_type  allocator_type;
  66
  67       explicit
  68       __unordered_map(size_type __n = 10,
  69                       const hasher& __hf = hasher(),
  70                       const key_equal& __eql = key_equal(),
  71                       const allocator_type& __a = allocator_type())
  72       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
  73               __detail::_Default_ranged_hash(),
  74               __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
  75       { }
  76
  77       template<typename _InputIterator>
  78         __unordered_map(_InputIterator __f, _InputIterator __l,
  79                         size_type __n = 0,
  80                         const hasher& __hf = hasher(),
  81                         const key_equal& __eql = key_equal(),
  82                         const allocator_type& __a = allocator_type())
  83         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
  84                 __detail::_Default_ranged_hash(),
  85                 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
  86         { }
  87
  88       __unordered_map(initializer_list<value_type> __l,
  89                       size_type __n = 0,
  90                       const hasher& __hf = hasher(),
  91                       const key_equal& __eql = key_equal(),
  92                       const allocator_type& __a = allocator_type())
  93       : _Base(__l.begin(), __l.end(), __n, __hf,
  94               __detail::_Mod_range_hashing(),
  95               __detail::_Default_ranged_hash(),
  96               __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
  97       { }
  98
  99       __unordered_map&
 100       operator=(initializer_list<value_type> __l)
 101       {
 102         this->clear();
 103         this->insert(__l.begin(), __l.end());
 104         return *this;
 105       }
 106     };
 107
 108   template<class _Key, class _Tp,
 109            class _Hash = hash<_Key>,
 110            class _Pred = std::equal_to<_Key>,
 111            class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
 112            bool __cache_hash_code = false>
 113     class __unordered_multimap
 114     : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
 115                         _Alloc,
 116                         std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
 117                         _Hash, __detail::_Mod_range_hashing,
 118                         __detail::_Default_ranged_hash,
 119                         __detail::_Prime_rehash_policy,
 120                         __cache_hash_code, false, false>
 121     {
 122       typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
 123                          _Alloc,
 124                          std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
 125                          _Hash, __detail::_Mod_range_hashing,
 126                          __detail::_Default_ranged_hash,
 127                          __detail::_Prime_rehash_policy,
 128                          __cache_hash_code, false, false>
 129         _Base;
 130
 131     public:
 132       typedef typename _Base::value_type      value_type;
 133       typedef typename _Base::size_type       size_type;
 134       typedef typename _Base::hasher          hasher;
 135       typedef typename _Base::key_equal       key_equal;
 136       typedef typename _Base::allocator_type  allocator_type;
 137
 138       explicit
 139       __unordered_multimap(size_type __n = 10,
 140                            const hasher& __hf = hasher(),
 141                            const key_equal& __eql = key_equal(),
 142                            const allocator_type& __a = allocator_type())
 143       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
 144               __detail::_Default_ranged_hash(),
 145               __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
 146       { }
 147
 148
 149       template<typename _InputIterator>
 150         __unordered_multimap(_InputIterator __f, _InputIterator __l,
 151                              size_type __n = 0,
 152                              const hasher& __hf = hasher(),
 153                              const key_equal& __eql = key_equal(),
 154                              const allocator_type& __a = allocator_type())
 155         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
 156                 __detail::_Default_ranged_hash(),
 157                 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
 158         { }
 159
 160       __unordered_multimap(initializer_list<value_type> __l,
 161                            size_type __n = 0,
 162                            const hasher& __hf = hasher(),
 163                            const key_equal& __eql = key_equal(),
 164                            const allocator_type& __a = allocator_type())
 165       : _Base(__l.begin(), __l.end(), __n, __hf,
 166               __detail::_Mod_range_hashing(),
 167               __detail::_Default_ranged_hash(),
 168               __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
 169       { }
 170
 171       __unordered_multimap&
 172       operator=(initializer_list<value_type> __l)
 173       {
 174         this->clear();
 175         this->insert(__l.begin(), __l.end());
 176         return *this;
 177       }
 178     };
 179
 180   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
 181            bool __cache_hash_code>
 182     inline void
 183     swap(__unordered_map<_Key, _Tp, _Hash, _Pred,
 184          _Alloc, __cache_hash_code>& __x,
 185          __unordered_map<_Key, _Tp, _Hash, _Pred,
 186          _Alloc, __cache_hash_code>& __y)
 187     { __x.swap(__y); }
 188
 189   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
 190            bool __cache_hash_code>
 191     inline void
 192     swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred,
 193          _Alloc, __cache_hash_code>& __x,
 194          __unordered_multimap<_Key, _Tp, _Hash, _Pred,
 195          _Alloc, __cache_hash_code>& __y)
 196     { __x.swap(__y); }
 197
 198   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
 199            bool __cache_hash_code>
 200     inline bool
 201     operator==(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
 202                __cache_hash_code>& __x,
 203                const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
 204                __cache_hash_code>& __y)
 205     { return __x._M_equal(__y); }
 206
 207   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
 208            bool __cache_hash_code>
 209     inline bool
 210     operator!=(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
 211                __cache_hash_code>& __x,
 212                const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
 213                __cache_hash_code>& __y)
 214     { return !(__x == __y); }
 215
 216   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
 217            bool __cache_hash_code>
 218     inline bool
 219     operator==(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
 220                __cache_hash_code>& __x,
 221                const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
 222                __cache_hash_code>& __y)
 223     { return __x._M_equal(__y); }
 224
 225   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
 226            bool __cache_hash_code>
 227     inline bool
 228     operator!=(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
 229                __cache_hash_code>& __x,
 230                const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
 231                __cache_hash_code>& __y)
 232     { return !(__x == __y); }
 233
 234   /**
 235    *  @brief A standard container composed of unique keys (containing
 236    *  at most one of each key value) that associates values of another type
 237    *  with the keys.
 238    *
 239    *  @ingroup unordered_associative_containers
 240    *
 241    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
 242    *  <a href="tables.html#xx">unordered associative container</a>
 243    *
 244    *  @param  Key  Type of key objects.
 245    *  @param  Tp  Type of mapped objects.
 246    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
 247    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
 248    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
 249    *
 250    * The resulting value type of the container is std::pair<const Key, Tp>.
 251    */
 252   template<class _Key, class _Tp,
 253            class _Hash = hash<_Key>,
 254            class _Pred = std::equal_to<_Key>,
 255            class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
 256     class unordered_map
 257     : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
 258     {
 259       typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>  _Base;
 260
 261     public:
 262       typedef typename _Base::value_type      value_type;
 263       typedef typename _Base::size_type       size_type;
 264       typedef typename _Base::hasher          hasher;
 265       typedef typename _Base::key_equal       key_equal;
 266       typedef typename _Base::allocator_type  allocator_type;
 267
 268       explicit
 269       unordered_map(size_type __n = 10,
 270                     const hasher& __hf = hasher(),
 271                     const key_equal& __eql = key_equal(),
 272                     const allocator_type& __a = allocator_type())
 273       : _Base(__n, __hf, __eql, __a)
 274       { }
 275
 276       template<typename _InputIterator>
 277         unordered_map(_InputIterator __f, _InputIterator __l,
 278                       size_type __n = 0,
 279                       const hasher& __hf = hasher(),
 280                       const key_equal& __eql = key_equal(),
 281                       const allocator_type& __a = allocator_type())
 282         : _Base(__f, __l, __n, __hf, __eql, __a)
 283         { }
 284
 285       unordered_map(initializer_list<value_type> __l,
 286                     size_type __n = 0,
 287                     const hasher& __hf = hasher(),
 288                     const key_equal& __eql = key_equal(),
 289                     const allocator_type& __a = allocator_type())
 290       : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
 291       { }
 292
 293       unordered_map&
 294       operator=(initializer_list<value_type> __l)
 295       {
 296         this->clear();
 297         this->insert(__l.begin(), __l.end());
 298         return *this;
 299       }
 300     };
 301
 302   /**
 303    *  @brief A standard container composed of equivalent keys
 304    *  (possibly containing multiple of each key value) that associates
 305    *  values of another type with the keys.
 306    *
 307    *  @ingroup unordered_associative_containers
 308    *
 309    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
 310    *  <a href="tables.html#xx">unordered associative container</a>
 311    *
 312    *  @param  Key  Type of key objects.
 313    *  @param  Tp  Type of mapped objects.
 314    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
 315    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
 316    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
 317    *
 318    * The resulting value type of the container is std::pair<const Key, Tp>.
 319    */
 320   template<class _Key, class _Tp,
 321            class _Hash = hash<_Key>,
 322            class _Pred = std::equal_to<_Key>,
 323            class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
 324     class unordered_multimap
 325     : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
 326     {
 327       typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>  _Base;
 328
 329     public:
 330       typedef typename _Base::value_type      value_type;
 331       typedef typename _Base::size_type       size_type;
 332       typedef typename _Base::hasher          hasher;
 333       typedef typename _Base::key_equal       key_equal;
 334       typedef typename _Base::allocator_type  allocator_type;
 335
 336       explicit
 337       unordered_multimap(size_type __n = 10,
 338                          const hasher& __hf = hasher(),
 339                          const key_equal& __eql = key_equal(),
 340                          const allocator_type& __a = allocator_type())
 341       : _Base(__n, __hf, __eql, __a)
 342       { }
 343
 344       template<typename _InputIterator>
 345         unordered_multimap(_InputIterator __f, _InputIterator __l,
 346                            size_type __n = 0,
 347                            const hasher& __hf = hasher(),
 348                            const key_equal& __eql = key_equal(),
 349                            const allocator_type& __a = allocator_type())
 350         : _Base(__f, __l, __n, __hf, __eql, __a)
 351         { }
 352
 353       unordered_multimap(initializer_list<value_type> __l,
 354                          size_type __n = 0,
 355                          const hasher& __hf = hasher(),
 356                          const key_equal& __eql = key_equal(),
 357                          const allocator_type& __a = allocator_type())
 358       : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
 359       { }
 360
 361       unordered_multimap&
 362       operator=(initializer_list<value_type> __l)
 363       {
 364         this->clear();
 365         this->insert(__l.begin(), __l.end());
 366         return *this;
 367       }
 368     };
 369
 370   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 371     inline void
 372     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 373          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 374     { __x.swap(__y); }
 375
 376   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 377     inline void
 378     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 379          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 380     { __x.swap(__y); }
 381
 382   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 383     inline bool
 384     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 385                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 386     { return __x._M_equal(__y); }
 387
 388   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 389     inline bool
 390     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 391                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 392     { return !(__x == __y); }
 393
 394   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 395     inline bool
 396     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 397                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 398     { return __x._M_equal(__y); }
 399
 400   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 401     inline bool
 402     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 403                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 404     { return !(__x == __y); }
 405
 406 _GLIBCXX_END_NAMESPACE_CONTAINER
 407 } // namespace std
 408
 409 #endif /* _UNORDERED_MAP_H */