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