1 // -*- C++ -*- 2 //===-------------------------- unordered_map -----------------------------===// 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is dual licensed under the MIT and the University of Illinois Open 7 // Source Licenses. See LICENSE.TXT for details. 8 // 9 //===----------------------------------------------------------------------===// 10 11 #ifndef _LIBCPP_UNORDERED_MAP 12 #define _LIBCPP_UNORDERED_MAP 13 14 /* 15 16 unordered_map synopsis 17 18 #include <initializer_list> 19 20 namespace std 21 { 22 23 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 24 class Alloc = allocator<pair<const Key, T>>> 25 class unordered_map 26 { 27 public: 28 // types 29 typedef Key key_type; 30 typedef T mapped_type; 31 typedef Hash hasher; 32 typedef Pred key_equal; 33 typedef Alloc allocator_type; 34 typedef pair<const key_type, mapped_type> value_type; 35 typedef value_type& reference; 36 typedef const value_type& const_reference; 37 typedef typename allocator_traits<allocator_type>::pointer pointer; 38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 39 typedef typename allocator_traits<allocator_type>::size_type size_type; 40 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 41 42 typedef /unspecified/ iterator; 43 typedef /unspecified/ const_iterator; 44 typedef /unspecified/ local_iterator; 45 typedef /unspecified/ const_local_iterator; 46 47 unordered_map() 48 noexcept( 49 is_nothrow_default_constructible<hasher>::value && 50 is_nothrow_default_constructible<key_equal>::value && 51 is_nothrow_default_constructible<allocator_type>::value); 52 explicit unordered_map(size_type n, const hasher& hf = hasher(), 53 const key_equal& eql = key_equal(), 54 const allocator_type& a = allocator_type()); 55 template <class InputIterator> 56 unordered_map(InputIterator f, InputIterator l, 57 size_type n = 0, const hasher& hf = hasher(), 58 const key_equal& eql = key_equal(), 59 const allocator_type& a = allocator_type()); 60 explicit unordered_map(const allocator_type&); 61 unordered_map(const unordered_map&); 62 unordered_map(const unordered_map&, const Allocator&); 63 unordered_map(unordered_map&&) 64 noexcept( 65 is_nothrow_move_constructible<hasher>::value && 66 is_nothrow_move_constructible<key_equal>::value && 67 is_nothrow_move_constructible<allocator_type>::value); 68 unordered_map(unordered_map&&, const Allocator&); 69 unordered_map(initializer_list<value_type>, size_type n = 0, 70 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 71 const allocator_type& a = allocator_type()); 72 unordered_map(size_type n, const allocator_type& a) 73 : unordered_map(n, hasher(), key_equal(), a) {} // C++14 74 unordered_map(size_type n, const hasher& hf, const allocator_type& a) 75 : unordered_map(n, hf, key_equal(), a) {} // C++14 76 template <class InputIterator> 77 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 78 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14 79 template <class InputIterator> 80 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, 81 const allocator_type& a) 82 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14 83 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a) 84 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 85 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf, 86 const allocator_type& a) 87 : unordered_map(il, n, hf, key_equal(), a) {} // C++14 88 ~unordered_map(); 89 unordered_map& operator=(const unordered_map&); 90 unordered_map& operator=(unordered_map&&) 91 noexcept( 92 allocator_type::propagate_on_container_move_assignment::value && 93 is_nothrow_move_assignable<allocator_type>::value && 94 is_nothrow_move_assignable<hasher>::value && 95 is_nothrow_move_assignable<key_equal>::value); 96 unordered_map& operator=(initializer_list<value_type>); 97 98 allocator_type get_allocator() const noexcept; 99 100 bool empty() const noexcept; 101 size_type size() const noexcept; 102 size_type max_size() const noexcept; 103 104 iterator begin() noexcept; 105 iterator end() noexcept; 106 const_iterator begin() const noexcept; 107 const_iterator end() const noexcept; 108 const_iterator cbegin() const noexcept; 109 const_iterator cend() const noexcept; 110 111 template <class... Args> 112 pair<iterator, bool> emplace(Args&&... args); 113 template <class... Args> 114 iterator emplace_hint(const_iterator position, Args&&... args); 115 pair<iterator, bool> insert(const value_type& obj); 116 template <class P> 117 pair<iterator, bool> insert(P&& obj); 118 iterator insert(const_iterator hint, const value_type& obj); 119 template <class P> 120 iterator insert(const_iterator hint, P&& obj); 121 template <class InputIterator> 122 void insert(InputIterator first, InputIterator last); 123 void insert(initializer_list<value_type>); 124 125 template <class... Args> 126 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17 127 template <class... Args> 128 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17 129 template <class... Args> 130 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17 131 template <class... Args> 132 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17 133 template <class M> 134 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17 135 template <class M> 136 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17 137 template <class M> 138 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17 139 template <class M> 140 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17 141 142 iterator erase(const_iterator position); 143 iterator erase(iterator position); // C++14 144 size_type erase(const key_type& k); 145 iterator erase(const_iterator first, const_iterator last); 146 void clear() noexcept; 147 148 void swap(unordered_map&) 149 noexcept( 150 (!allocator_type::propagate_on_container_swap::value || 151 __is_nothrow_swappable<allocator_type>::value) && 152 __is_nothrow_swappable<hasher>::value && 153 __is_nothrow_swappable<key_equal>::value); 154 155 hasher hash_function() const; 156 key_equal key_eq() const; 157 158 iterator find(const key_type& k); 159 const_iterator find(const key_type& k) const; 160 size_type count(const key_type& k) const; 161 pair<iterator, iterator> equal_range(const key_type& k); 162 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 163 164 mapped_type& operator[](const key_type& k); 165 mapped_type& operator[](key_type&& k); 166 167 mapped_type& at(const key_type& k); 168 const mapped_type& at(const key_type& k) const; 169 170 size_type bucket_count() const noexcept; 171 size_type max_bucket_count() const noexcept; 172 173 size_type bucket_size(size_type n) const; 174 size_type bucket(const key_type& k) const; 175 176 local_iterator begin(size_type n); 177 local_iterator end(size_type n); 178 const_local_iterator begin(size_type n) const; 179 const_local_iterator end(size_type n) const; 180 const_local_iterator cbegin(size_type n) const; 181 const_local_iterator cend(size_type n) const; 182 183 float load_factor() const noexcept; 184 float max_load_factor() const noexcept; 185 void max_load_factor(float z); 186 void rehash(size_type n); 187 void reserve(size_type n); 188 }; 189 190 template <class Key, class T, class Hash, class Pred, class Alloc> 191 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x, 192 unordered_map<Key, T, Hash, Pred, Alloc>& y) 193 noexcept(noexcept(x.swap(y))); 194 195 template <class Key, class T, class Hash, class Pred, class Alloc> 196 bool 197 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 198 const unordered_map<Key, T, Hash, Pred, Alloc>& y); 199 200 template <class Key, class T, class Hash, class Pred, class Alloc> 201 bool 202 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 203 const unordered_map<Key, T, Hash, Pred, Alloc>& y); 204 205 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 206 class Alloc = allocator<pair<const Key, T>>> 207 class unordered_multimap 208 { 209 public: 210 // types 211 typedef Key key_type; 212 typedef T mapped_type; 213 typedef Hash hasher; 214 typedef Pred key_equal; 215 typedef Alloc allocator_type; 216 typedef pair<const key_type, mapped_type> value_type; 217 typedef value_type& reference; 218 typedef const value_type& const_reference; 219 typedef typename allocator_traits<allocator_type>::pointer pointer; 220 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 221 typedef typename allocator_traits<allocator_type>::size_type size_type; 222 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 223 224 typedef /unspecified/ iterator; 225 typedef /unspecified/ const_iterator; 226 typedef /unspecified/ local_iterator; 227 typedef /unspecified/ const_local_iterator; 228 229 unordered_multimap() 230 noexcept( 231 is_nothrow_default_constructible<hasher>::value && 232 is_nothrow_default_constructible<key_equal>::value && 233 is_nothrow_default_constructible<allocator_type>::value); 234 explicit unordered_multimap(size_type n, const hasher& hf = hasher(), 235 const key_equal& eql = key_equal(), 236 const allocator_type& a = allocator_type()); 237 template <class InputIterator> 238 unordered_multimap(InputIterator f, InputIterator l, 239 size_type n = 0, const hasher& hf = hasher(), 240 const key_equal& eql = key_equal(), 241 const allocator_type& a = allocator_type()); 242 explicit unordered_multimap(const allocator_type&); 243 unordered_multimap(const unordered_multimap&); 244 unordered_multimap(const unordered_multimap&, const Allocator&); 245 unordered_multimap(unordered_multimap&&) 246 noexcept( 247 is_nothrow_move_constructible<hasher>::value && 248 is_nothrow_move_constructible<key_equal>::value && 249 is_nothrow_move_constructible<allocator_type>::value); 250 unordered_multimap(unordered_multimap&&, const Allocator&); 251 unordered_multimap(initializer_list<value_type>, size_type n = 0, 252 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 253 const allocator_type& a = allocator_type()); 254 unordered_multimap(size_type n, const allocator_type& a) 255 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14 256 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a) 257 : unordered_multimap(n, hf, key_equal(), a) {} // C++14 258 template <class InputIterator> 259 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 260 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14 261 template <class InputIterator> 262 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, 263 const allocator_type& a) 264 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14 265 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a) 266 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 267 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf, 268 const allocator_type& a) 269 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14 270 ~unordered_multimap(); 271 unordered_multimap& operator=(const unordered_multimap&); 272 unordered_multimap& operator=(unordered_multimap&&) 273 noexcept( 274 allocator_type::propagate_on_container_move_assignment::value && 275 is_nothrow_move_assignable<allocator_type>::value && 276 is_nothrow_move_assignable<hasher>::value && 277 is_nothrow_move_assignable<key_equal>::value); 278 unordered_multimap& operator=(initializer_list<value_type>); 279 280 allocator_type get_allocator() const noexcept; 281 282 bool empty() const noexcept; 283 size_type size() const noexcept; 284 size_type max_size() const noexcept; 285 286 iterator begin() noexcept; 287 iterator end() noexcept; 288 const_iterator begin() const noexcept; 289 const_iterator end() const noexcept; 290 const_iterator cbegin() const noexcept; 291 const_iterator cend() const noexcept; 292 293 template <class... Args> 294 iterator emplace(Args&&... args); 295 template <class... Args> 296 iterator emplace_hint(const_iterator position, Args&&... args); 297 iterator insert(const value_type& obj); 298 template <class P> 299 iterator insert(P&& obj); 300 iterator insert(const_iterator hint, const value_type& obj); 301 template <class P> 302 iterator insert(const_iterator hint, P&& obj); 303 template <class InputIterator> 304 void insert(InputIterator first, InputIterator last); 305 void insert(initializer_list<value_type>); 306 307 iterator erase(const_iterator position); 308 iterator erase(iterator position); // C++14 309 size_type erase(const key_type& k); 310 iterator erase(const_iterator first, const_iterator last); 311 void clear() noexcept; 312 313 void swap(unordered_multimap&) 314 noexcept( 315 (!allocator_type::propagate_on_container_swap::value || 316 __is_nothrow_swappable<allocator_type>::value) && 317 __is_nothrow_swappable<hasher>::value && 318 __is_nothrow_swappable<key_equal>::value); 319 320 hasher hash_function() const; 321 key_equal key_eq() const; 322 323 iterator find(const key_type& k); 324 const_iterator find(const key_type& k) const; 325 size_type count(const key_type& k) const; 326 pair<iterator, iterator> equal_range(const key_type& k); 327 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 328 329 size_type bucket_count() const noexcept; 330 size_type max_bucket_count() const noexcept; 331 332 size_type bucket_size(size_type n) const; 333 size_type bucket(const key_type& k) const; 334 335 local_iterator begin(size_type n); 336 local_iterator end(size_type n); 337 const_local_iterator begin(size_type n) const; 338 const_local_iterator end(size_type n) const; 339 const_local_iterator cbegin(size_type n) const; 340 const_local_iterator cend(size_type n) const; 341 342 float load_factor() const noexcept; 343 float max_load_factor() const noexcept; 344 void max_load_factor(float z); 345 void rehash(size_type n); 346 void reserve(size_type n); 347 }; 348 349 template <class Key, class T, class Hash, class Pred, class Alloc> 350 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 351 unordered_multimap<Key, T, Hash, Pred, Alloc>& y) 352 noexcept(noexcept(x.swap(y))); 353 354 template <class Key, class T, class Hash, class Pred, class Alloc> 355 bool 356 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 357 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 358 359 template <class Key, class T, class Hash, class Pred, class Alloc> 360 bool 361 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 362 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 363 364 } // std 365 366 */ 367 368 #include <__config> 369 #include <__hash_table> 370 #include <functional> 371 #include <stdexcept> 372 #include <tuple> 373 374 #include <__debug> 375 376 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 377 #pragma GCC system_header 378 #endif 379 380 _LIBCPP_BEGIN_NAMESPACE_STD 381 382 template <class _Key, class _Cp, class _Hash, bool _IsEmpty> 383 class __unordered_map_hasher 384 : private _Hash 385 { 386 public: 387 _LIBCPP_INLINE_VISIBILITY 388 __unordered_map_hasher() 389 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 390 : _Hash() {} 391 _LIBCPP_INLINE_VISIBILITY 392 __unordered_map_hasher(const _Hash& __h) 393 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 394 : _Hash(__h) {} 395 _LIBCPP_INLINE_VISIBILITY 396 const _Hash& hash_function() const _NOEXCEPT {return *this;} 397 _LIBCPP_INLINE_VISIBILITY 398 size_t operator()(const _Cp& __x) const 399 {return static_cast<const _Hash&>(*this)(__x.__cc.first);} 400 _LIBCPP_INLINE_VISIBILITY 401 size_t operator()(const _Key& __x) const 402 {return static_cast<const _Hash&>(*this)(__x);} 403 void swap(__unordered_map_hasher&__y) 404 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) 405 { 406 using _VSTD::swap; 407 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y)); 408 } 409 }; 410 411 template <class _Key, class _Cp, class _Hash> 412 class __unordered_map_hasher<_Key, _Cp, _Hash, false> 413 { 414 _Hash __hash_; 415 public: 416 _LIBCPP_INLINE_VISIBILITY 417 __unordered_map_hasher() 418 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 419 : __hash_() {} 420 _LIBCPP_INLINE_VISIBILITY 421 __unordered_map_hasher(const _Hash& __h) 422 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 423 : __hash_(__h) {} 424 _LIBCPP_INLINE_VISIBILITY 425 const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 426 _LIBCPP_INLINE_VISIBILITY 427 size_t operator()(const _Cp& __x) const 428 {return __hash_(__x.__cc.first);} 429 _LIBCPP_INLINE_VISIBILITY 430 size_t operator()(const _Key& __x) const 431 {return __hash_(__x);} 432 void swap(__unordered_map_hasher&__y) 433 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) 434 { 435 using _VSTD::swap; 436 swap(__hash_, __y.__hash_); 437 } 438 }; 439 440 template <class _Key, class _Cp, class _Hash, bool __b> 441 inline _LIBCPP_INLINE_VISIBILITY 442 void 443 swap(__unordered_map_hasher<_Key, _Cp, _Hash, __b>& __x, 444 __unordered_map_hasher<_Key, _Cp, _Hash, __b>& __y) 445 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 446 { 447 __x.swap(__y); 448 } 449 450 template <class _Key, class _Cp, class _Pred, bool _IsEmpty> 451 class __unordered_map_equal 452 : private _Pred 453 { 454 public: 455 _LIBCPP_INLINE_VISIBILITY 456 __unordered_map_equal() 457 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 458 : _Pred() {} 459 _LIBCPP_INLINE_VISIBILITY 460 __unordered_map_equal(const _Pred& __p) 461 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 462 : _Pred(__p) {} 463 _LIBCPP_INLINE_VISIBILITY 464 const _Pred& key_eq() const _NOEXCEPT {return *this;} 465 _LIBCPP_INLINE_VISIBILITY 466 bool operator()(const _Cp& __x, const _Cp& __y) const 467 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);} 468 _LIBCPP_INLINE_VISIBILITY 469 bool operator()(const _Cp& __x, const _Key& __y) const 470 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);} 471 _LIBCPP_INLINE_VISIBILITY 472 bool operator()(const _Key& __x, const _Cp& __y) const 473 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);} 474 void swap(__unordered_map_equal&__y) 475 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) 476 { 477 using _VSTD::swap; 478 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y)); 479 } 480 }; 481 482 template <class _Key, class _Cp, class _Pred> 483 class __unordered_map_equal<_Key, _Cp, _Pred, false> 484 { 485 _Pred __pred_; 486 public: 487 _LIBCPP_INLINE_VISIBILITY 488 __unordered_map_equal() 489 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 490 : __pred_() {} 491 _LIBCPP_INLINE_VISIBILITY 492 __unordered_map_equal(const _Pred& __p) 493 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 494 : __pred_(__p) {} 495 _LIBCPP_INLINE_VISIBILITY 496 const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 497 _LIBCPP_INLINE_VISIBILITY 498 bool operator()(const _Cp& __x, const _Cp& __y) const 499 {return __pred_(__x.__cc.first, __y.__cc.first);} 500 _LIBCPP_INLINE_VISIBILITY 501 bool operator()(const _Cp& __x, const _Key& __y) const 502 {return __pred_(__x.__cc.first, __y);} 503 _LIBCPP_INLINE_VISIBILITY 504 bool operator()(const _Key& __x, const _Cp& __y) const 505 {return __pred_(__x, __y.__cc.first);} 506 void swap(__unordered_map_equal&__y) 507 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) 508 { 509 using _VSTD::swap; 510 swap(__pred_, __y.__pred_); 511 } 512 }; 513 514 template <class _Key, class _Cp, class _Pred, bool __b> 515 inline _LIBCPP_INLINE_VISIBILITY 516 void 517 swap(__unordered_map_equal<_Key, _Cp, _Pred, __b>& __x, 518 __unordered_map_equal<_Key, _Cp, _Pred, __b>& __y) 519 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 520 { 521 __x.swap(__y); 522 } 523 524 template <class _Alloc> 525 class __hash_map_node_destructor 526 { 527 typedef _Alloc allocator_type; 528 typedef allocator_traits<allocator_type> __alloc_traits; 529 530 public: 531 532 typedef typename __alloc_traits::pointer pointer; 533 private: 534 535 allocator_type& __na_; 536 537 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 538 539 public: 540 bool __first_constructed; 541 bool __second_constructed; 542 543 _LIBCPP_INLINE_VISIBILITY 544 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 545 : __na_(__na), 546 __first_constructed(false), 547 __second_constructed(false) 548 {} 549 550 #ifndef _LIBCPP_CXX03_LANG 551 _LIBCPP_INLINE_VISIBILITY 552 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 553 _NOEXCEPT 554 : __na_(__x.__na_), 555 __first_constructed(__x.__value_constructed), 556 __second_constructed(__x.__value_constructed) 557 { 558 __x.__value_constructed = false; 559 } 560 #else // _LIBCPP_CXX03_LANG 561 _LIBCPP_INLINE_VISIBILITY 562 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 563 : __na_(__x.__na_), 564 __first_constructed(__x.__value_constructed), 565 __second_constructed(__x.__value_constructed) 566 { 567 const_cast<bool&>(__x.__value_constructed) = false; 568 } 569 #endif // _LIBCPP_CXX03_LANG 570 571 _LIBCPP_INLINE_VISIBILITY 572 void operator()(pointer __p) _NOEXCEPT 573 { 574 if (__second_constructed) 575 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second)); 576 if (__first_constructed) 577 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first)); 578 if (__p) 579 __alloc_traits::deallocate(__na_, __p, 1); 580 } 581 }; 582 583 #ifndef _LIBCPP_CXX03_LANG 584 template <class _Key, class _Tp> 585 union __hash_value_type 586 { 587 typedef _Key key_type; 588 typedef _Tp mapped_type; 589 typedef pair<const key_type, mapped_type> value_type; 590 typedef pair<key_type, mapped_type> __nc_value_type; 591 592 value_type __cc; 593 __nc_value_type __nc; 594 595 _LIBCPP_INLINE_VISIBILITY 596 __hash_value_type& operator=(const __hash_value_type& __v) 597 {__nc = __v.__cc; return *this;} 598 599 _LIBCPP_INLINE_VISIBILITY 600 __hash_value_type& operator=(__hash_value_type&& __v) 601 {__nc = _VSTD::move(__v.__nc); return *this;} 602 603 template <class _ValueTp, 604 class = typename enable_if< 605 __is_same_uncvref<_ValueTp, value_type>::value 606 >::type 607 > 608 _LIBCPP_INLINE_VISIBILITY 609 __hash_value_type& operator=(_ValueTp&& __v) { 610 __nc = _VSTD::forward<_ValueTp>(__v); return *this; 611 } 612 613 private: 614 __hash_value_type(const __hash_value_type& __v) = delete; 615 __hash_value_type(__hash_value_type&& __v) = delete; 616 template <class ..._Args> 617 explicit __hash_value_type(_Args&& ...__args) = delete; 618 619 ~__hash_value_type() = delete; 620 }; 621 622 #else 623 624 template <class _Key, class _Tp> 625 struct __hash_value_type 626 { 627 typedef _Key key_type; 628 typedef _Tp mapped_type; 629 typedef pair<const key_type, mapped_type> value_type; 630 631 value_type __cc; 632 633 private: 634 ~__hash_value_type(); 635 }; 636 637 #endif 638 639 template <class _HashIterator> 640 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator 641 { 642 _HashIterator __i_; 643 644 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; 645 646 public: 647 typedef forward_iterator_tag iterator_category; 648 typedef typename _NodeTypes::__map_value_type value_type; 649 typedef typename _NodeTypes::difference_type difference_type; 650 typedef value_type& reference; 651 typedef typename _NodeTypes::__map_value_type_pointer pointer; 652 653 _LIBCPP_INLINE_VISIBILITY 654 __hash_map_iterator() _NOEXCEPT {} 655 656 _LIBCPP_INLINE_VISIBILITY 657 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 658 659 _LIBCPP_INLINE_VISIBILITY 660 reference operator*() const {return __i_->__cc;} 661 _LIBCPP_INLINE_VISIBILITY 662 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 663 664 _LIBCPP_INLINE_VISIBILITY 665 __hash_map_iterator& operator++() {++__i_; return *this;} 666 _LIBCPP_INLINE_VISIBILITY 667 __hash_map_iterator operator++(int) 668 { 669 __hash_map_iterator __t(*this); 670 ++(*this); 671 return __t; 672 } 673 674 friend _LIBCPP_INLINE_VISIBILITY 675 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 676 {return __x.__i_ == __y.__i_;} 677 friend _LIBCPP_INLINE_VISIBILITY 678 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 679 {return __x.__i_ != __y.__i_;} 680 681 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map; 682 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 683 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 684 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 685 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 686 }; 687 688 template <class _HashIterator> 689 class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator 690 { 691 _HashIterator __i_; 692 693 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; 694 695 public: 696 typedef forward_iterator_tag iterator_category; 697 typedef typename _NodeTypes::__map_value_type value_type; 698 typedef typename _NodeTypes::difference_type difference_type; 699 typedef const value_type& reference; 700 typedef typename _NodeTypes::__const_map_value_type_pointer pointer; 701 702 _LIBCPP_INLINE_VISIBILITY 703 __hash_map_const_iterator() _NOEXCEPT {} 704 705 _LIBCPP_INLINE_VISIBILITY 706 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 707 _LIBCPP_INLINE_VISIBILITY 708 __hash_map_const_iterator( 709 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 710 _NOEXCEPT 711 : __i_(__i.__i_) {} 712 713 _LIBCPP_INLINE_VISIBILITY 714 reference operator*() const {return __i_->__cc;} 715 _LIBCPP_INLINE_VISIBILITY 716 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 717 718 _LIBCPP_INLINE_VISIBILITY 719 __hash_map_const_iterator& operator++() {++__i_; return *this;} 720 _LIBCPP_INLINE_VISIBILITY 721 __hash_map_const_iterator operator++(int) 722 { 723 __hash_map_const_iterator __t(*this); 724 ++(*this); 725 return __t; 726 } 727 728 friend _LIBCPP_INLINE_VISIBILITY 729 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 730 {return __x.__i_ == __y.__i_;} 731 friend _LIBCPP_INLINE_VISIBILITY 732 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 733 {return __x.__i_ != __y.__i_;} 734 735 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map; 736 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 737 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 738 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 739 }; 740 741 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 742 class _Alloc = allocator<pair<const _Key, _Tp> > > 743 class _LIBCPP_TEMPLATE_VIS unordered_map 744 { 745 public: 746 // types 747 typedef _Key key_type; 748 typedef _Tp mapped_type; 749 typedef _Hash hasher; 750 typedef _Pred key_equal; 751 typedef _Alloc allocator_type; 752 typedef pair<const key_type, mapped_type> value_type; 753 typedef pair<key_type, mapped_type> __nc_value_type; 754 typedef value_type& reference; 755 typedef const value_type& const_reference; 756 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 757 "Invalid allocator::value_type"); 758 759 private: 760 typedef __hash_value_type<key_type, mapped_type> __value_type; 761 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 762 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 763 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 764 __value_type>::type __allocator_type; 765 766 typedef __hash_table<__value_type, __hasher, 767 __key_equal, __allocator_type> __table; 768 769 __table __table_; 770 771 typedef typename __table::_NodeTypes _NodeTypes; 772 typedef typename __table::__node_pointer __node_pointer; 773 typedef typename __table::__node_const_pointer __node_const_pointer; 774 typedef typename __table::__node_traits __node_traits; 775 typedef typename __table::__node_allocator __node_allocator; 776 typedef typename __table::__node __node; 777 typedef __hash_map_node_destructor<__node_allocator> _Dp; 778 typedef unique_ptr<__node, _Dp> __node_holder; 779 typedef allocator_traits<allocator_type> __alloc_traits; 780 781 static_assert((is_same<typename __table::__container_value_type, value_type>::value), ""); 782 static_assert((is_same<typename __table::__node_value_type, __value_type>::value), ""); 783 public: 784 typedef typename __alloc_traits::pointer pointer; 785 typedef typename __alloc_traits::const_pointer const_pointer; 786 typedef typename __table::size_type size_type; 787 typedef typename __table::difference_type difference_type; 788 789 typedef __hash_map_iterator<typename __table::iterator> iterator; 790 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 791 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 792 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 793 794 _LIBCPP_INLINE_VISIBILITY 795 unordered_map() 796 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 797 { 798 #if _LIBCPP_DEBUG_LEVEL >= 2 799 __get_db()->__insert_c(this); 800 #endif 801 } 802 explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 803 const key_equal& __eql = key_equal()); 804 unordered_map(size_type __n, const hasher& __hf, 805 const key_equal& __eql, 806 const allocator_type& __a); 807 template <class _InputIterator> 808 unordered_map(_InputIterator __first, _InputIterator __last); 809 template <class _InputIterator> 810 unordered_map(_InputIterator __first, _InputIterator __last, 811 size_type __n, const hasher& __hf = hasher(), 812 const key_equal& __eql = key_equal()); 813 template <class _InputIterator> 814 unordered_map(_InputIterator __first, _InputIterator __last, 815 size_type __n, const hasher& __hf, 816 const key_equal& __eql, 817 const allocator_type& __a); 818 _LIBCPP_INLINE_VISIBILITY 819 explicit unordered_map(const allocator_type& __a); 820 unordered_map(const unordered_map& __u); 821 unordered_map(const unordered_map& __u, const allocator_type& __a); 822 #ifndef _LIBCPP_CXX03_LANG 823 _LIBCPP_INLINE_VISIBILITY 824 unordered_map(unordered_map&& __u) 825 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 826 unordered_map(unordered_map&& __u, const allocator_type& __a); 827 unordered_map(initializer_list<value_type> __il); 828 unordered_map(initializer_list<value_type> __il, size_type __n, 829 const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 830 unordered_map(initializer_list<value_type> __il, size_type __n, 831 const hasher& __hf, const key_equal& __eql, 832 const allocator_type& __a); 833 #endif // _LIBCPP_CXX03_LANG 834 #if _LIBCPP_STD_VER > 11 835 _LIBCPP_INLINE_VISIBILITY 836 unordered_map(size_type __n, const allocator_type& __a) 837 : unordered_map(__n, hasher(), key_equal(), __a) {} 838 _LIBCPP_INLINE_VISIBILITY 839 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a) 840 : unordered_map(__n, __hf, key_equal(), __a) {} 841 template <class _InputIterator> 842 _LIBCPP_INLINE_VISIBILITY 843 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 844 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} 845 template <class _InputIterator> 846 _LIBCPP_INLINE_VISIBILITY 847 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 848 const allocator_type& __a) 849 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} 850 _LIBCPP_INLINE_VISIBILITY 851 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 852 : unordered_map(__il, __n, hasher(), key_equal(), __a) {} 853 _LIBCPP_INLINE_VISIBILITY 854 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 855 const allocator_type& __a) 856 : unordered_map(__il, __n, __hf, key_equal(), __a) {} 857 #endif 858 // ~unordered_map() = default; 859 _LIBCPP_INLINE_VISIBILITY 860 unordered_map& operator=(const unordered_map& __u) 861 { 862 #ifndef _LIBCPP_CXX03_LANG 863 __table_ = __u.__table_; 864 #else 865 if (this != &__u) { 866 __table_.clear(); 867 __table_.hash_function() = __u.__table_.hash_function(); 868 __table_.key_eq() = __u.__table_.key_eq(); 869 __table_.max_load_factor() = __u.__table_.max_load_factor(); 870 __table_.__copy_assign_alloc(__u.__table_); 871 insert(__u.begin(), __u.end()); 872 } 873 #endif 874 return *this; 875 } 876 #ifndef _LIBCPP_CXX03_LANG 877 _LIBCPP_INLINE_VISIBILITY 878 unordered_map& operator=(unordered_map&& __u) 879 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 880 _LIBCPP_INLINE_VISIBILITY 881 unordered_map& operator=(initializer_list<value_type> __il); 882 #endif // _LIBCPP_CXX03_LANG 883 884 _LIBCPP_INLINE_VISIBILITY 885 allocator_type get_allocator() const _NOEXCEPT 886 {return allocator_type(__table_.__node_alloc());} 887 888 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 889 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 890 _LIBCPP_INLINE_VISIBILITY 891 size_type size() const _NOEXCEPT {return __table_.size();} 892 _LIBCPP_INLINE_VISIBILITY 893 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 894 895 _LIBCPP_INLINE_VISIBILITY 896 iterator begin() _NOEXCEPT {return __table_.begin();} 897 _LIBCPP_INLINE_VISIBILITY 898 iterator end() _NOEXCEPT {return __table_.end();} 899 _LIBCPP_INLINE_VISIBILITY 900 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 901 _LIBCPP_INLINE_VISIBILITY 902 const_iterator end() const _NOEXCEPT {return __table_.end();} 903 _LIBCPP_INLINE_VISIBILITY 904 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 905 _LIBCPP_INLINE_VISIBILITY 906 const_iterator cend() const _NOEXCEPT {return __table_.end();} 907 908 _LIBCPP_INLINE_VISIBILITY 909 pair<iterator, bool> insert(const value_type& __x) 910 {return __table_.__insert_unique(__x);} 911 912 iterator insert(const_iterator __p, const value_type& __x) { 913 #if _LIBCPP_DEBUG_LEVEL >= 2 914 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 915 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" 916 " referring to this unordered_map"); 917 #else 918 ((void)__p); 919 #endif 920 return insert(__x).first; 921 } 922 923 template <class _InputIterator> 924 _LIBCPP_INLINE_VISIBILITY 925 void insert(_InputIterator __first, _InputIterator __last); 926 927 #ifndef _LIBCPP_CXX03_LANG 928 _LIBCPP_INLINE_VISIBILITY 929 void insert(initializer_list<value_type> __il) 930 {insert(__il.begin(), __il.end());} 931 932 _LIBCPP_INLINE_VISIBILITY 933 pair<iterator, bool> insert(value_type&& __x) 934 {return __table_.__insert_unique(_VSTD::move(__x));} 935 936 iterator insert(const_iterator __p, value_type&& __x) { 937 #if _LIBCPP_DEBUG_LEVEL >= 2 938 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 939 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" 940 " referring to this unordered_map"); 941 #else 942 ((void)__p); 943 #endif 944 return __table_.__insert_unique(_VSTD::move(__x)).first; 945 } 946 947 template <class _Pp, 948 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 949 _LIBCPP_INLINE_VISIBILITY 950 pair<iterator, bool> insert(_Pp&& __x) 951 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 952 953 template <class _Pp, 954 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 955 _LIBCPP_INLINE_VISIBILITY 956 iterator insert(const_iterator __p, _Pp&& __x) 957 { 958 #if _LIBCPP_DEBUG_LEVEL >= 2 959 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 960 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" 961 " referring to this unordered_map"); 962 #else 963 ((void)__p); 964 #endif 965 return insert(_VSTD::forward<_Pp>(__x)).first; 966 } 967 968 template <class... _Args> 969 _LIBCPP_INLINE_VISIBILITY 970 pair<iterator, bool> emplace(_Args&&... __args) { 971 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...); 972 } 973 974 template <class... _Args> 975 _LIBCPP_INLINE_VISIBILITY 976 iterator emplace_hint(const_iterator __p, _Args&&... __args) { 977 #if _LIBCPP_DEBUG_LEVEL >= 2 978 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 979 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" 980 " referring to this unordered_map"); 981 #else 982 ((void)__p); 983 #endif 984 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 985 } 986 987 #endif // _LIBCPP_CXX03_LANG 988 989 #if _LIBCPP_STD_VER > 14 990 template <class... _Args> 991 _LIBCPP_INLINE_VISIBILITY 992 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) 993 { 994 return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct, 995 _VSTD::forward_as_tuple(__k), 996 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 997 } 998 999 template <class... _Args> 1000 _LIBCPP_INLINE_VISIBILITY 1001 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) 1002 { 1003 return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct, 1004 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1005 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1006 } 1007 1008 template <class... _Args> 1009 _LIBCPP_INLINE_VISIBILITY 1010 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) 1011 { 1012 #if _LIBCPP_DEBUG_LEVEL >= 2 1013 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this, 1014 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not" 1015 " referring to this unordered_map"); 1016 #else 1017 ((void)__h); 1018 #endif 1019 return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first; 1020 } 1021 1022 template <class... _Args> 1023 _LIBCPP_INLINE_VISIBILITY 1024 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) 1025 { 1026 #if _LIBCPP_DEBUG_LEVEL >= 2 1027 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this, 1028 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not" 1029 " referring to this unordered_map"); 1030 #else 1031 ((void)__h); 1032 #endif 1033 return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first; 1034 } 1035 1036 template <class _Vp> 1037 _LIBCPP_INLINE_VISIBILITY 1038 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) 1039 { 1040 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, 1041 __k, _VSTD::forward<_Vp>(__v)); 1042 if (!__res.second) { 1043 __res.first->second = _VSTD::forward<_Vp>(__v); 1044 } 1045 return __res; 1046 } 1047 1048 template <class _Vp> 1049 _LIBCPP_INLINE_VISIBILITY 1050 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) 1051 { 1052 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, 1053 _VSTD::move(__k), _VSTD::forward<_Vp>(__v)); 1054 if (!__res.second) { 1055 __res.first->second = _VSTD::forward<_Vp>(__v); 1056 } 1057 return __res; 1058 } 1059 1060 template <class _Vp> 1061 _LIBCPP_INLINE_VISIBILITY 1062 iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v) 1063 { 1064 // FIXME: Add debug mode checking for the iterator input 1065 return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first; 1066 } 1067 1068 template <class _Vp> 1069 _LIBCPP_INLINE_VISIBILITY 1070 iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v) 1071 { 1072 // FIXME: Add debug mode checking for the iterator input 1073 return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first; 1074 } 1075 #endif // _LIBCPP_STD_VER > 14 1076 1077 _LIBCPP_INLINE_VISIBILITY 1078 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1079 _LIBCPP_INLINE_VISIBILITY 1080 iterator erase(iterator __p) {return __table_.erase(__p.__i_);} 1081 _LIBCPP_INLINE_VISIBILITY 1082 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 1083 _LIBCPP_INLINE_VISIBILITY 1084 iterator erase(const_iterator __first, const_iterator __last) 1085 {return __table_.erase(__first.__i_, __last.__i_);} 1086 _LIBCPP_INLINE_VISIBILITY 1087 void clear() _NOEXCEPT {__table_.clear();} 1088 1089 _LIBCPP_INLINE_VISIBILITY 1090 void swap(unordered_map& __u) 1091 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1092 { __table_.swap(__u.__table_);} 1093 1094 _LIBCPP_INLINE_VISIBILITY 1095 hasher hash_function() const 1096 {return __table_.hash_function().hash_function();} 1097 _LIBCPP_INLINE_VISIBILITY 1098 key_equal key_eq() const 1099 {return __table_.key_eq().key_eq();} 1100 1101 _LIBCPP_INLINE_VISIBILITY 1102 iterator find(const key_type& __k) {return __table_.find(__k);} 1103 _LIBCPP_INLINE_VISIBILITY 1104 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1105 _LIBCPP_INLINE_VISIBILITY 1106 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 1107 _LIBCPP_INLINE_VISIBILITY 1108 pair<iterator, iterator> equal_range(const key_type& __k) 1109 {return __table_.__equal_range_unique(__k);} 1110 _LIBCPP_INLINE_VISIBILITY 1111 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1112 {return __table_.__equal_range_unique(__k);} 1113 1114 mapped_type& operator[](const key_type& __k); 1115 #ifndef _LIBCPP_CXX03_LANG 1116 mapped_type& operator[](key_type&& __k); 1117 #endif 1118 1119 mapped_type& at(const key_type& __k); 1120 const mapped_type& at(const key_type& __k) const; 1121 1122 _LIBCPP_INLINE_VISIBILITY 1123 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1124 _LIBCPP_INLINE_VISIBILITY 1125 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 1126 1127 _LIBCPP_INLINE_VISIBILITY 1128 size_type bucket_size(size_type __n) const 1129 {return __table_.bucket_size(__n);} 1130 _LIBCPP_INLINE_VISIBILITY 1131 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1132 1133 _LIBCPP_INLINE_VISIBILITY 1134 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1135 _LIBCPP_INLINE_VISIBILITY 1136 local_iterator end(size_type __n) {return __table_.end(__n);} 1137 _LIBCPP_INLINE_VISIBILITY 1138 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1139 _LIBCPP_INLINE_VISIBILITY 1140 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1141 _LIBCPP_INLINE_VISIBILITY 1142 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1143 _LIBCPP_INLINE_VISIBILITY 1144 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1145 1146 _LIBCPP_INLINE_VISIBILITY 1147 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1148 _LIBCPP_INLINE_VISIBILITY 1149 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1150 _LIBCPP_INLINE_VISIBILITY 1151 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1152 _LIBCPP_INLINE_VISIBILITY 1153 void rehash(size_type __n) {__table_.rehash(__n);} 1154 _LIBCPP_INLINE_VISIBILITY 1155 void reserve(size_type __n) {__table_.reserve(__n);} 1156 1157 #if _LIBCPP_DEBUG_LEVEL >= 2 1158 1159 bool __dereferenceable(const const_iterator* __i) const 1160 {return __table_.__dereferenceable(&__i->__i_);} 1161 bool __decrementable(const const_iterator* __i) const 1162 {return __table_.__decrementable(&__i->__i_);} 1163 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1164 {return __table_.__addable(&__i->__i_, __n);} 1165 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1166 {return __table_.__addable(&__i->__i_, __n);} 1167 1168 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1169 1170 private: 1171 1172 #ifdef _LIBCPP_CXX03_LANG 1173 __node_holder __construct_node_with_key(const key_type& __k); 1174 #endif 1175 }; 1176 1177 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1178 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1179 size_type __n, const hasher& __hf, const key_equal& __eql) 1180 : __table_(__hf, __eql) 1181 { 1182 #if _LIBCPP_DEBUG_LEVEL >= 2 1183 __get_db()->__insert_c(this); 1184 #endif 1185 __table_.rehash(__n); 1186 } 1187 1188 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1189 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1190 size_type __n, const hasher& __hf, const key_equal& __eql, 1191 const allocator_type& __a) 1192 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1193 { 1194 #if _LIBCPP_DEBUG_LEVEL >= 2 1195 __get_db()->__insert_c(this); 1196 #endif 1197 __table_.rehash(__n); 1198 } 1199 1200 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1201 inline 1202 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1203 const allocator_type& __a) 1204 : __table_(typename __table::allocator_type(__a)) 1205 { 1206 #if _LIBCPP_DEBUG_LEVEL >= 2 1207 __get_db()->__insert_c(this); 1208 #endif 1209 } 1210 1211 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1212 template <class _InputIterator> 1213 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1214 _InputIterator __first, _InputIterator __last) 1215 { 1216 #if _LIBCPP_DEBUG_LEVEL >= 2 1217 __get_db()->__insert_c(this); 1218 #endif 1219 insert(__first, __last); 1220 } 1221 1222 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1223 template <class _InputIterator> 1224 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1225 _InputIterator __first, _InputIterator __last, size_type __n, 1226 const hasher& __hf, const key_equal& __eql) 1227 : __table_(__hf, __eql) 1228 { 1229 #if _LIBCPP_DEBUG_LEVEL >= 2 1230 __get_db()->__insert_c(this); 1231 #endif 1232 __table_.rehash(__n); 1233 insert(__first, __last); 1234 } 1235 1236 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1237 template <class _InputIterator> 1238 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1239 _InputIterator __first, _InputIterator __last, size_type __n, 1240 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1241 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1242 { 1243 #if _LIBCPP_DEBUG_LEVEL >= 2 1244 __get_db()->__insert_c(this); 1245 #endif 1246 __table_.rehash(__n); 1247 insert(__first, __last); 1248 } 1249 1250 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1251 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1252 const unordered_map& __u) 1253 : __table_(__u.__table_) 1254 { 1255 #if _LIBCPP_DEBUG_LEVEL >= 2 1256 __get_db()->__insert_c(this); 1257 #endif 1258 __table_.rehash(__u.bucket_count()); 1259 insert(__u.begin(), __u.end()); 1260 } 1261 1262 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1263 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1264 const unordered_map& __u, const allocator_type& __a) 1265 : __table_(__u.__table_, typename __table::allocator_type(__a)) 1266 { 1267 #if _LIBCPP_DEBUG_LEVEL >= 2 1268 __get_db()->__insert_c(this); 1269 #endif 1270 __table_.rehash(__u.bucket_count()); 1271 insert(__u.begin(), __u.end()); 1272 } 1273 1274 #ifndef _LIBCPP_CXX03_LANG 1275 1276 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1277 inline 1278 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1279 unordered_map&& __u) 1280 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1281 : __table_(_VSTD::move(__u.__table_)) 1282 { 1283 #if _LIBCPP_DEBUG_LEVEL >= 2 1284 __get_db()->__insert_c(this); 1285 __get_db()->swap(this, &__u); 1286 #endif 1287 } 1288 1289 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1290 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1291 unordered_map&& __u, const allocator_type& __a) 1292 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a)) 1293 { 1294 #if _LIBCPP_DEBUG_LEVEL >= 2 1295 __get_db()->__insert_c(this); 1296 #endif 1297 if (__a != __u.get_allocator()) 1298 { 1299 iterator __i = __u.begin(); 1300 while (__u.size() != 0) { 1301 __table_.__emplace_unique(_VSTD::move( 1302 __u.__table_.remove((__i++).__i_)->__value_.__nc)); 1303 } 1304 } 1305 #if _LIBCPP_DEBUG_LEVEL >= 2 1306 else 1307 __get_db()->swap(this, &__u); 1308 #endif 1309 } 1310 1311 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1312 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1313 initializer_list<value_type> __il) 1314 { 1315 #if _LIBCPP_DEBUG_LEVEL >= 2 1316 __get_db()->__insert_c(this); 1317 #endif 1318 insert(__il.begin(), __il.end()); 1319 } 1320 1321 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1322 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1323 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1324 const key_equal& __eql) 1325 : __table_(__hf, __eql) 1326 { 1327 #if _LIBCPP_DEBUG_LEVEL >= 2 1328 __get_db()->__insert_c(this); 1329 #endif 1330 __table_.rehash(__n); 1331 insert(__il.begin(), __il.end()); 1332 } 1333 1334 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1335 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1336 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1337 const key_equal& __eql, const allocator_type& __a) 1338 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1339 { 1340 #if _LIBCPP_DEBUG_LEVEL >= 2 1341 __get_db()->__insert_c(this); 1342 #endif 1343 __table_.rehash(__n); 1344 insert(__il.begin(), __il.end()); 1345 } 1346 1347 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1348 inline 1349 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1350 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1351 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1352 { 1353 __table_ = _VSTD::move(__u.__table_); 1354 return *this; 1355 } 1356 1357 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1358 inline 1359 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1360 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1361 initializer_list<value_type> __il) 1362 { 1363 __table_.__assign_unique(__il.begin(), __il.end()); 1364 return *this; 1365 } 1366 1367 #endif // _LIBCPP_CXX03_LANG 1368 1369 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1370 template <class _InputIterator> 1371 inline 1372 void 1373 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1374 _InputIterator __last) 1375 { 1376 for (; __first != __last; ++__first) 1377 __table_.__insert_unique(*__first); 1378 } 1379 1380 #ifndef _LIBCPP_CXX03_LANG 1381 1382 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1383 _Tp& 1384 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1385 { 1386 return __table_.__emplace_unique_key_args(__k, 1387 std::piecewise_construct, std::forward_as_tuple(__k), 1388 std::forward_as_tuple()).first->__cc.second; 1389 } 1390 1391 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1392 _Tp& 1393 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1394 { 1395 return __table_.__emplace_unique_key_args(__k, 1396 std::piecewise_construct, std::forward_as_tuple(std::move(__k)), 1397 std::forward_as_tuple()).first->__cc.second; 1398 } 1399 #else // _LIBCPP_CXX03_LANG 1400 1401 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1402 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1403 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1404 { 1405 __node_allocator& __na = __table_.__node_alloc(); 1406 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1407 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1408 __h.get_deleter().__first_constructed = true; 1409 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1410 __h.get_deleter().__second_constructed = true; 1411 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 1412 } 1413 1414 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1415 _Tp& 1416 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1417 { 1418 iterator __i = find(__k); 1419 if (__i != end()) 1420 return __i->second; 1421 __node_holder __h = __construct_node_with_key(__k); 1422 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1423 __h.release(); 1424 return __r.first->second; 1425 } 1426 1427 #endif // _LIBCPP_CXX03_MODE 1428 1429 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1430 _Tp& 1431 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1432 { 1433 iterator __i = find(__k); 1434 #ifndef _LIBCPP_NO_EXCEPTIONS 1435 if (__i == end()) 1436 throw out_of_range("unordered_map::at: key not found"); 1437 #endif // _LIBCPP_NO_EXCEPTIONS 1438 return __i->second; 1439 } 1440 1441 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1442 const _Tp& 1443 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1444 { 1445 const_iterator __i = find(__k); 1446 #ifndef _LIBCPP_NO_EXCEPTIONS 1447 if (__i == end()) 1448 throw out_of_range("unordered_map::at: key not found"); 1449 #endif // _LIBCPP_NO_EXCEPTIONS 1450 return __i->second; 1451 } 1452 1453 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1454 inline _LIBCPP_INLINE_VISIBILITY 1455 void 1456 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1457 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1458 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1459 { 1460 __x.swap(__y); 1461 } 1462 1463 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1464 bool 1465 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1466 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1467 { 1468 if (__x.size() != __y.size()) 1469 return false; 1470 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1471 const_iterator; 1472 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1473 __i != __ex; ++__i) 1474 { 1475 const_iterator __j = __y.find(__i->first); 1476 if (__j == __ey || !(*__i == *__j)) 1477 return false; 1478 } 1479 return true; 1480 } 1481 1482 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1483 inline _LIBCPP_INLINE_VISIBILITY 1484 bool 1485 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1486 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1487 { 1488 return !(__x == __y); 1489 } 1490 1491 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1492 class _Alloc = allocator<pair<const _Key, _Tp> > > 1493 class _LIBCPP_TEMPLATE_VIS unordered_multimap 1494 { 1495 public: 1496 // types 1497 typedef _Key key_type; 1498 typedef _Tp mapped_type; 1499 typedef _Hash hasher; 1500 typedef _Pred key_equal; 1501 typedef _Alloc allocator_type; 1502 typedef pair<const key_type, mapped_type> value_type; 1503 typedef pair<key_type, mapped_type> __nc_value_type; 1504 typedef value_type& reference; 1505 typedef const value_type& const_reference; 1506 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1507 "Invalid allocator::value_type"); 1508 1509 private: 1510 typedef __hash_value_type<key_type, mapped_type> __value_type; 1511 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 1512 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 1513 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1514 __value_type>::type __allocator_type; 1515 1516 typedef __hash_table<__value_type, __hasher, 1517 __key_equal, __allocator_type> __table; 1518 1519 __table __table_; 1520 1521 typedef typename __table::_NodeTypes _NodeTypes; 1522 typedef typename __table::__node_traits __node_traits; 1523 typedef typename __table::__node_allocator __node_allocator; 1524 typedef typename __table::__node __node; 1525 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1526 typedef unique_ptr<__node, _Dp> __node_holder; 1527 typedef allocator_traits<allocator_type> __alloc_traits; 1528 static_assert((is_same<typename __node_traits::size_type, 1529 typename __alloc_traits::size_type>::value), 1530 "Allocator uses different size_type for different types"); 1531 public: 1532 typedef typename __alloc_traits::pointer pointer; 1533 typedef typename __alloc_traits::const_pointer const_pointer; 1534 typedef typename __table::size_type size_type; 1535 typedef typename __table::difference_type difference_type; 1536 1537 typedef __hash_map_iterator<typename __table::iterator> iterator; 1538 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1539 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1540 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1541 1542 _LIBCPP_INLINE_VISIBILITY 1543 unordered_multimap() 1544 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1545 { 1546 #if _LIBCPP_DEBUG_LEVEL >= 2 1547 __get_db()->__insert_c(this); 1548 #endif 1549 } 1550 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1551 const key_equal& __eql = key_equal()); 1552 unordered_multimap(size_type __n, const hasher& __hf, 1553 const key_equal& __eql, 1554 const allocator_type& __a); 1555 template <class _InputIterator> 1556 unordered_multimap(_InputIterator __first, _InputIterator __last); 1557 template <class _InputIterator> 1558 unordered_multimap(_InputIterator __first, _InputIterator __last, 1559 size_type __n, const hasher& __hf = hasher(), 1560 const key_equal& __eql = key_equal()); 1561 template <class _InputIterator> 1562 unordered_multimap(_InputIterator __first, _InputIterator __last, 1563 size_type __n, const hasher& __hf, 1564 const key_equal& __eql, 1565 const allocator_type& __a); 1566 _LIBCPP_INLINE_VISIBILITY 1567 explicit unordered_multimap(const allocator_type& __a); 1568 unordered_multimap(const unordered_multimap& __u); 1569 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1570 #ifndef _LIBCPP_CXX03_LANG 1571 _LIBCPP_INLINE_VISIBILITY 1572 unordered_multimap(unordered_multimap&& __u) 1573 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1574 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1575 unordered_multimap(initializer_list<value_type> __il); 1576 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1577 const hasher& __hf = hasher(), 1578 const key_equal& __eql = key_equal()); 1579 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1580 const hasher& __hf, const key_equal& __eql, 1581 const allocator_type& __a); 1582 #endif // _LIBCPP_CXX03_LANG 1583 #if _LIBCPP_STD_VER > 11 1584 _LIBCPP_INLINE_VISIBILITY 1585 unordered_multimap(size_type __n, const allocator_type& __a) 1586 : unordered_multimap(__n, hasher(), key_equal(), __a) {} 1587 _LIBCPP_INLINE_VISIBILITY 1588 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 1589 : unordered_multimap(__n, __hf, key_equal(), __a) {} 1590 template <class _InputIterator> 1591 _LIBCPP_INLINE_VISIBILITY 1592 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1593 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 1594 template <class _InputIterator> 1595 _LIBCPP_INLINE_VISIBILITY 1596 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 1597 const allocator_type& __a) 1598 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 1599 _LIBCPP_INLINE_VISIBILITY 1600 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1601 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 1602 _LIBCPP_INLINE_VISIBILITY 1603 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1604 const allocator_type& __a) 1605 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 1606 #endif 1607 // ~unordered_multimap() = default; 1608 _LIBCPP_INLINE_VISIBILITY 1609 unordered_multimap& operator=(const unordered_multimap& __u) 1610 { 1611 #ifndef _LIBCPP_CXX03_LANG 1612 __table_ = __u.__table_; 1613 #else 1614 if (this != &__u) { 1615 __table_.clear(); 1616 __table_.hash_function() = __u.__table_.hash_function(); 1617 __table_.key_eq() = __u.__table_.key_eq(); 1618 __table_.max_load_factor() = __u.__table_.max_load_factor(); 1619 __table_.__copy_assign_alloc(__u.__table_); 1620 insert(__u.begin(), __u.end()); 1621 } 1622 #endif 1623 return *this; 1624 } 1625 #ifndef _LIBCPP_CXX03_LANG 1626 _LIBCPP_INLINE_VISIBILITY 1627 unordered_multimap& operator=(unordered_multimap&& __u) 1628 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1629 _LIBCPP_INLINE_VISIBILITY 1630 unordered_multimap& operator=(initializer_list<value_type> __il); 1631 #endif // _LIBCPP_CXX03_LANG 1632 1633 _LIBCPP_INLINE_VISIBILITY 1634 allocator_type get_allocator() const _NOEXCEPT 1635 {return allocator_type(__table_.__node_alloc());} 1636 1637 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1638 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1639 _LIBCPP_INLINE_VISIBILITY 1640 size_type size() const _NOEXCEPT {return __table_.size();} 1641 _LIBCPP_INLINE_VISIBILITY 1642 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1643 1644 _LIBCPP_INLINE_VISIBILITY 1645 iterator begin() _NOEXCEPT {return __table_.begin();} 1646 _LIBCPP_INLINE_VISIBILITY 1647 iterator end() _NOEXCEPT {return __table_.end();} 1648 _LIBCPP_INLINE_VISIBILITY 1649 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1650 _LIBCPP_INLINE_VISIBILITY 1651 const_iterator end() const _NOEXCEPT {return __table_.end();} 1652 _LIBCPP_INLINE_VISIBILITY 1653 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1654 _LIBCPP_INLINE_VISIBILITY 1655 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1656 1657 _LIBCPP_INLINE_VISIBILITY 1658 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1659 1660 _LIBCPP_INLINE_VISIBILITY 1661 iterator insert(const_iterator __p, const value_type& __x) 1662 {return __table_.__insert_multi(__p.__i_, __x);} 1663 1664 template <class _InputIterator> 1665 _LIBCPP_INLINE_VISIBILITY 1666 void insert(_InputIterator __first, _InputIterator __last); 1667 1668 #ifndef _LIBCPP_CXX03_LANG 1669 _LIBCPP_INLINE_VISIBILITY 1670 void insert(initializer_list<value_type> __il) 1671 {insert(__il.begin(), __il.end());} 1672 _LIBCPP_INLINE_VISIBILITY 1673 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 1674 1675 _LIBCPP_INLINE_VISIBILITY 1676 iterator insert(const_iterator __p, value_type&& __x) 1677 {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));} 1678 1679 template <class _Pp, 1680 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1681 _LIBCPP_INLINE_VISIBILITY 1682 iterator insert(_Pp&& __x) 1683 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1684 1685 template <class _Pp, 1686 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1687 _LIBCPP_INLINE_VISIBILITY 1688 iterator insert(const_iterator __p, _Pp&& __x) 1689 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1690 1691 template <class... _Args> 1692 iterator emplace(_Args&&... __args) { 1693 return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...); 1694 } 1695 1696 template <class... _Args> 1697 iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1698 return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); 1699 } 1700 #endif // _LIBCPP_CXX03_LANG 1701 1702 1703 _LIBCPP_INLINE_VISIBILITY 1704 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1705 _LIBCPP_INLINE_VISIBILITY 1706 iterator erase(iterator __p) {return __table_.erase(__p.__i_);} 1707 _LIBCPP_INLINE_VISIBILITY 1708 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1709 _LIBCPP_INLINE_VISIBILITY 1710 iterator erase(const_iterator __first, const_iterator __last) 1711 {return __table_.erase(__first.__i_, __last.__i_);} 1712 _LIBCPP_INLINE_VISIBILITY 1713 void clear() _NOEXCEPT {__table_.clear();} 1714 1715 _LIBCPP_INLINE_VISIBILITY 1716 void swap(unordered_multimap& __u) 1717 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1718 {__table_.swap(__u.__table_);} 1719 1720 _LIBCPP_INLINE_VISIBILITY 1721 hasher hash_function() const 1722 {return __table_.hash_function().hash_function();} 1723 _LIBCPP_INLINE_VISIBILITY 1724 key_equal key_eq() const 1725 {return __table_.key_eq().key_eq();} 1726 1727 _LIBCPP_INLINE_VISIBILITY 1728 iterator find(const key_type& __k) {return __table_.find(__k);} 1729 _LIBCPP_INLINE_VISIBILITY 1730 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1731 _LIBCPP_INLINE_VISIBILITY 1732 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1733 _LIBCPP_INLINE_VISIBILITY 1734 pair<iterator, iterator> equal_range(const key_type& __k) 1735 {return __table_.__equal_range_multi(__k);} 1736 _LIBCPP_INLINE_VISIBILITY 1737 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1738 {return __table_.__equal_range_multi(__k);} 1739 1740 _LIBCPP_INLINE_VISIBILITY 1741 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1742 _LIBCPP_INLINE_VISIBILITY 1743 size_type max_bucket_count() const _NOEXCEPT 1744 {return __table_.max_bucket_count();} 1745 1746 _LIBCPP_INLINE_VISIBILITY 1747 size_type bucket_size(size_type __n) const 1748 {return __table_.bucket_size(__n);} 1749 _LIBCPP_INLINE_VISIBILITY 1750 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1751 1752 _LIBCPP_INLINE_VISIBILITY 1753 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1754 _LIBCPP_INLINE_VISIBILITY 1755 local_iterator end(size_type __n) {return __table_.end(__n);} 1756 _LIBCPP_INLINE_VISIBILITY 1757 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1758 _LIBCPP_INLINE_VISIBILITY 1759 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1760 _LIBCPP_INLINE_VISIBILITY 1761 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1762 _LIBCPP_INLINE_VISIBILITY 1763 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1764 1765 _LIBCPP_INLINE_VISIBILITY 1766 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1767 _LIBCPP_INLINE_VISIBILITY 1768 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1769 _LIBCPP_INLINE_VISIBILITY 1770 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1771 _LIBCPP_INLINE_VISIBILITY 1772 void rehash(size_type __n) {__table_.rehash(__n);} 1773 _LIBCPP_INLINE_VISIBILITY 1774 void reserve(size_type __n) {__table_.reserve(__n);} 1775 1776 #if _LIBCPP_DEBUG_LEVEL >= 2 1777 1778 bool __dereferenceable(const const_iterator* __i) const 1779 {return __table_.__dereferenceable(&__i->__i_);} 1780 bool __decrementable(const const_iterator* __i) const 1781 {return __table_.__decrementable(&__i->__i_);} 1782 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1783 {return __table_.__addable(&__i->__i_, __n);} 1784 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1785 {return __table_.__addable(&__i->__i_, __n);} 1786 1787 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1788 1789 1790 }; 1791 1792 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1793 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1794 size_type __n, const hasher& __hf, const key_equal& __eql) 1795 : __table_(__hf, __eql) 1796 { 1797 #if _LIBCPP_DEBUG_LEVEL >= 2 1798 __get_db()->__insert_c(this); 1799 #endif 1800 __table_.rehash(__n); 1801 } 1802 1803 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1804 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1805 size_type __n, const hasher& __hf, const key_equal& __eql, 1806 const allocator_type& __a) 1807 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1808 { 1809 #if _LIBCPP_DEBUG_LEVEL >= 2 1810 __get_db()->__insert_c(this); 1811 #endif 1812 __table_.rehash(__n); 1813 } 1814 1815 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1816 template <class _InputIterator> 1817 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1818 _InputIterator __first, _InputIterator __last) 1819 { 1820 #if _LIBCPP_DEBUG_LEVEL >= 2 1821 __get_db()->__insert_c(this); 1822 #endif 1823 insert(__first, __last); 1824 } 1825 1826 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1827 template <class _InputIterator> 1828 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1829 _InputIterator __first, _InputIterator __last, size_type __n, 1830 const hasher& __hf, const key_equal& __eql) 1831 : __table_(__hf, __eql) 1832 { 1833 #if _LIBCPP_DEBUG_LEVEL >= 2 1834 __get_db()->__insert_c(this); 1835 #endif 1836 __table_.rehash(__n); 1837 insert(__first, __last); 1838 } 1839 1840 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1841 template <class _InputIterator> 1842 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1843 _InputIterator __first, _InputIterator __last, size_type __n, 1844 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1845 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1846 { 1847 #if _LIBCPP_DEBUG_LEVEL >= 2 1848 __get_db()->__insert_c(this); 1849 #endif 1850 __table_.rehash(__n); 1851 insert(__first, __last); 1852 } 1853 1854 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1855 inline 1856 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1857 const allocator_type& __a) 1858 : __table_(typename __table::allocator_type(__a)) 1859 { 1860 #if _LIBCPP_DEBUG_LEVEL >= 2 1861 __get_db()->__insert_c(this); 1862 #endif 1863 } 1864 1865 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1866 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1867 const unordered_multimap& __u) 1868 : __table_(__u.__table_) 1869 { 1870 #if _LIBCPP_DEBUG_LEVEL >= 2 1871 __get_db()->__insert_c(this); 1872 #endif 1873 __table_.rehash(__u.bucket_count()); 1874 insert(__u.begin(), __u.end()); 1875 } 1876 1877 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1878 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1879 const unordered_multimap& __u, const allocator_type& __a) 1880 : __table_(__u.__table_, typename __table::allocator_type(__a)) 1881 { 1882 #if _LIBCPP_DEBUG_LEVEL >= 2 1883 __get_db()->__insert_c(this); 1884 #endif 1885 __table_.rehash(__u.bucket_count()); 1886 insert(__u.begin(), __u.end()); 1887 } 1888 1889 #ifndef _LIBCPP_CXX03_LANG 1890 1891 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1892 inline 1893 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1894 unordered_multimap&& __u) 1895 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1896 : __table_(_VSTD::move(__u.__table_)) 1897 { 1898 #if _LIBCPP_DEBUG_LEVEL >= 2 1899 __get_db()->__insert_c(this); 1900 __get_db()->swap(this, &__u); 1901 #endif 1902 } 1903 1904 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1905 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1906 unordered_multimap&& __u, const allocator_type& __a) 1907 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a)) 1908 { 1909 #if _LIBCPP_DEBUG_LEVEL >= 2 1910 __get_db()->__insert_c(this); 1911 #endif 1912 if (__a != __u.get_allocator()) 1913 { 1914 iterator __i = __u.begin(); 1915 while (__u.size() != 0) 1916 { 1917 __table_.__insert_multi( 1918 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_.__nc) 1919 ); 1920 } 1921 } 1922 #if _LIBCPP_DEBUG_LEVEL >= 2 1923 else 1924 __get_db()->swap(this, &__u); 1925 #endif 1926 } 1927 1928 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1929 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1930 initializer_list<value_type> __il) 1931 { 1932 #if _LIBCPP_DEBUG_LEVEL >= 2 1933 __get_db()->__insert_c(this); 1934 #endif 1935 insert(__il.begin(), __il.end()); 1936 } 1937 1938 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1939 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1940 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1941 const key_equal& __eql) 1942 : __table_(__hf, __eql) 1943 { 1944 #if _LIBCPP_DEBUG_LEVEL >= 2 1945 __get_db()->__insert_c(this); 1946 #endif 1947 __table_.rehash(__n); 1948 insert(__il.begin(), __il.end()); 1949 } 1950 1951 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1952 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1953 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1954 const key_equal& __eql, const allocator_type& __a) 1955 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1956 { 1957 #if _LIBCPP_DEBUG_LEVEL >= 2 1958 __get_db()->__insert_c(this); 1959 #endif 1960 __table_.rehash(__n); 1961 insert(__il.begin(), __il.end()); 1962 } 1963 1964 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1965 inline 1966 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1967 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1968 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1969 { 1970 __table_ = _VSTD::move(__u.__table_); 1971 return *this; 1972 } 1973 1974 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1975 inline 1976 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1977 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1978 initializer_list<value_type> __il) 1979 { 1980 __table_.__assign_multi(__il.begin(), __il.end()); 1981 return *this; 1982 } 1983 1984 #endif // _LIBCPP_CXX03_LANG 1985 1986 1987 1988 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1989 template <class _InputIterator> 1990 inline 1991 void 1992 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1993 _InputIterator __last) 1994 { 1995 for (; __first != __last; ++__first) 1996 __table_.__insert_multi(*__first); 1997 } 1998 1999 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2000 inline _LIBCPP_INLINE_VISIBILITY 2001 void 2002 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2003 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2004 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2005 { 2006 __x.swap(__y); 2007 } 2008 2009 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2010 bool 2011 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2012 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2013 { 2014 if (__x.size() != __y.size()) 2015 return false; 2016 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 2017 const_iterator; 2018 typedef pair<const_iterator, const_iterator> _EqRng; 2019 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 2020 { 2021 _EqRng __xeq = __x.equal_range(__i->first); 2022 _EqRng __yeq = __y.equal_range(__i->first); 2023 if (_VSTD::distance(__xeq.first, __xeq.second) != 2024 _VSTD::distance(__yeq.first, __yeq.second) || 2025 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2026 return false; 2027 __i = __xeq.second; 2028 } 2029 return true; 2030 } 2031 2032 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2033 inline _LIBCPP_INLINE_VISIBILITY 2034 bool 2035 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2036 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2037 { 2038 return !(__x == __y); 2039 } 2040 2041 _LIBCPP_END_NAMESPACE_STD 2042 2043 #endif // _LIBCPP_UNORDERED_MAP 2044
