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