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