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