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