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

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