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