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 373 #include <__debug> 374 375 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 376 #pragma GCC system_header 377 #endif 378 379 _LIBCPP_BEGIN_NAMESPACE_STD 380 381 template <class _Key, class _Cp, class _Hash, 382 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value 383 > 384 class __unordered_map_hasher 385 : private _Hash 386 { 387 public: 388 _LIBCPP_INLINE_VISIBILITY 389 __unordered_map_hasher() 390 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 391 : _Hash() {} 392 _LIBCPP_INLINE_VISIBILITY 393 __unordered_map_hasher(const _Hash& __h) 394 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 395 : _Hash(__h) {} 396 _LIBCPP_INLINE_VISIBILITY 397 const _Hash& hash_function() const _NOEXCEPT {return *this;} 398 _LIBCPP_INLINE_VISIBILITY 399 size_t operator()(const _Cp& __x) const 400 {return static_cast<const _Hash&>(*this)(__x.__cc.first);} 401 _LIBCPP_INLINE_VISIBILITY 402 size_t operator()(const _Key& __x) const 403 {return static_cast<const _Hash&>(*this)(__x);} 404 void swap(__unordered_map_hasher&__y) 405 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) 406 { 407 using _VSTD::swap; 408 swap(static_cast<const _Hash&>(*this), static_cast<const _Hash&>(__y)); 409 } 410 }; 411 412 template <class _Key, class _Cp, class _Hash> 413 class __unordered_map_hasher<_Key, _Cp, _Hash, false> 414 { 415 _Hash __hash_; 416 417 public: 418 _LIBCPP_INLINE_VISIBILITY 419 __unordered_map_hasher() 420 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 421 : __hash_() {} 422 _LIBCPP_INLINE_VISIBILITY 423 __unordered_map_hasher(const _Hash& __h) 424 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 425 : __hash_(__h) {} 426 _LIBCPP_INLINE_VISIBILITY 427 const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 428 _LIBCPP_INLINE_VISIBILITY 429 size_t operator()(const _Cp& __x) const 430 {return __hash_(__x.__cc.first);} 431 _LIBCPP_INLINE_VISIBILITY 432 size_t operator()(const _Key& __x) const 433 {return __hash_(__x);} 434 void swap(__unordered_map_hasher&__y) 435 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) 436 { 437 using _VSTD::swap; 438 swap(__hash_, __y.__hash_); 439 } 440 }; 441 442 template <class _Key, class _Cp, class _Hash, bool __b> 443 inline _LIBCPP_INLINE_VISIBILITY 444 void 445 swap(__unordered_map_hasher<_Key, _Cp, _Hash, __b>& __x, 446 __unordered_map_hasher<_Key, _Cp, _Hash, __b>& __y) 447 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 448 { 449 __x.swap(__y); 450 } 451 452 template <class _Key, class _Cp, class _Pred, 453 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value 454 > 455 class __unordered_map_equal 456 : private _Pred 457 { 458 public: 459 _LIBCPP_INLINE_VISIBILITY 460 __unordered_map_equal() 461 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 462 : _Pred() {} 463 _LIBCPP_INLINE_VISIBILITY 464 __unordered_map_equal(const _Pred& __p) 465 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 466 : _Pred(__p) {} 467 _LIBCPP_INLINE_VISIBILITY 468 const _Pred& key_eq() const _NOEXCEPT {return *this;} 469 _LIBCPP_INLINE_VISIBILITY 470 bool operator()(const _Cp& __x, const _Cp& __y) const 471 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);} 472 _LIBCPP_INLINE_VISIBILITY 473 bool operator()(const _Cp& __x, const _Key& __y) const 474 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);} 475 _LIBCPP_INLINE_VISIBILITY 476 bool operator()(const _Key& __x, const _Cp& __y) const 477 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);} 478 void swap(__unordered_map_equal&__y) 479 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) 480 { 481 using _VSTD::swap; 482 swap(static_cast<const _Pred&>(*this), static_cast<const _Pred&>(__y)); 483 } 484 }; 485 486 template <class _Key, class _Cp, class _Pred> 487 class __unordered_map_equal<_Key, _Cp, _Pred, false> 488 { 489 _Pred __pred_; 490 491 public: 492 _LIBCPP_INLINE_VISIBILITY 493 __unordered_map_equal() 494 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 495 : __pred_() {} 496 _LIBCPP_INLINE_VISIBILITY 497 __unordered_map_equal(const _Pred& __p) 498 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 499 : __pred_(__p) {} 500 _LIBCPP_INLINE_VISIBILITY 501 const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 502 _LIBCPP_INLINE_VISIBILITY 503 bool operator()(const _Cp& __x, const _Cp& __y) const 504 {return __pred_(__x.__cc.first, __y.__cc.first);} 505 _LIBCPP_INLINE_VISIBILITY 506 bool operator()(const _Cp& __x, const _Key& __y) const 507 {return __pred_(__x.__cc.first, __y);} 508 _LIBCPP_INLINE_VISIBILITY 509 bool operator()(const _Key& __x, const _Cp& __y) const 510 {return __pred_(__x, __y.__cc.first);} 511 void swap(__unordered_map_equal&__y) 512 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) 513 { 514 using _VSTD::swap; 515 swap(__pred_, __y.__pred_); 516 } 517 }; 518 519 template <class _Key, class _Cp, class _Pred, bool __b> 520 inline _LIBCPP_INLINE_VISIBILITY 521 void 522 swap(__unordered_map_equal<_Key, _Cp, _Pred, __b>& __x, 523 __unordered_map_equal<_Key, _Cp, _Pred, __b>& __y) 524 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 525 { 526 __x.swap(__y); 527 } 528 529 template <class _Alloc> 530 class __hash_map_node_destructor 531 { 532 typedef _Alloc allocator_type; 533 typedef allocator_traits<allocator_type> __alloc_traits; 534 typedef typename __alloc_traits::value_type::value_type value_type; 535 public: 536 typedef typename __alloc_traits::pointer pointer; 537 private: 538 typedef typename value_type::value_type::first_type first_type; 539 typedef typename value_type::value_type::second_type second_type; 540 541 allocator_type& __na_; 542 543 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 544 545 public: 546 bool __first_constructed; 547 bool __second_constructed; 548 549 _LIBCPP_INLINE_VISIBILITY 550 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 551 : __na_(__na), 552 __first_constructed(false), 553 __second_constructed(false) 554 {} 555 556 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 557 _LIBCPP_INLINE_VISIBILITY 558 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 559 _NOEXCEPT 560 : __na_(__x.__na_), 561 __first_constructed(__x.__value_constructed), 562 __second_constructed(__x.__value_constructed) 563 { 564 __x.__value_constructed = false; 565 } 566 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 567 _LIBCPP_INLINE_VISIBILITY 568 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 569 : __na_(__x.__na_), 570 __first_constructed(__x.__value_constructed), 571 __second_constructed(__x.__value_constructed) 572 { 573 const_cast<bool&>(__x.__value_constructed) = false; 574 } 575 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 576 577 _LIBCPP_INLINE_VISIBILITY 578 void operator()(pointer __p) _NOEXCEPT 579 { 580 if (__second_constructed) 581 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second)); 582 if (__first_constructed) 583 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first)); 584 if (__p) 585 __alloc_traits::deallocate(__na_, __p, 1); 586 } 587 }; 588 589 #if __cplusplus >= 201103L 590 591 template <class _Key, class _Tp> 592 union __hash_value_type 593 { 594 typedef _Key key_type; 595 typedef _Tp mapped_type; 596 typedef pair<const key_type, mapped_type> value_type; 597 typedef pair<key_type, mapped_type> __nc_value_type; 598 599 value_type __cc; 600 __nc_value_type __nc; 601 602 template <class ..._Args> 603 _LIBCPP_INLINE_VISIBILITY 604 __hash_value_type(_Args&& ...__args) 605 : __cc(std::forward<_Args>(__args)...) {} 606 607 _LIBCPP_INLINE_VISIBILITY 608 __hash_value_type(const __hash_value_type& __v) 609 : __cc(__v.__cc) {} 610 611 _LIBCPP_INLINE_VISIBILITY 612 __hash_value_type(__hash_value_type&& __v) 613 : __nc(_VSTD::move(__v.__nc)) {} 614 615 _LIBCPP_INLINE_VISIBILITY 616 __hash_value_type& operator=(const __hash_value_type& __v) 617 {__nc = __v.__cc; return *this;} 618 619 _LIBCPP_INLINE_VISIBILITY 620 __hash_value_type& operator=(__hash_value_type&& __v) 621 {__nc = _VSTD::move(__v.__nc); return *this;} 622 623 _LIBCPP_INLINE_VISIBILITY 624 ~__hash_value_type() {__cc.~value_type();} 625 }; 626 627 #else 628 629 template <class _Key, class _Tp> 630 struct __hash_value_type 631 { 632 typedef _Key key_type; 633 typedef _Tp mapped_type; 634 typedef pair<const key_type, mapped_type> value_type; 635 636 value_type __cc; 637 638 _LIBCPP_INLINE_VISIBILITY 639 __hash_value_type() {} 640 641 template <class _A0> 642 _LIBCPP_INLINE_VISIBILITY 643 __hash_value_type(const _A0& __a0) 644 : __cc(__a0) {} 645 646 template <class _A0, class _A1> 647 _LIBCPP_INLINE_VISIBILITY 648 __hash_value_type(const _A0& __a0, const _A1& __a1) 649 : __cc(__a0, __a1) {} 650 }; 651 652 #endif 653 654 template <class _HashIterator> 655 class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator 656 { 657 _HashIterator __i_; 658 659 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 660 typedef const typename _HashIterator::value_type::value_type::first_type key_type; 661 typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 662 public: 663 typedef forward_iterator_tag iterator_category; 664 typedef pair<key_type, mapped_type> value_type; 665 typedef typename _HashIterator::difference_type difference_type; 666 typedef value_type& reference; 667 typedef typename __pointer_traits::template 668 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 669 rebind<value_type> 670 #else 671 rebind<value_type>::other 672 #endif 673 pointer; 674 675 _LIBCPP_INLINE_VISIBILITY 676 __hash_map_iterator() _NOEXCEPT {} 677 678 _LIBCPP_INLINE_VISIBILITY 679 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 680 681 _LIBCPP_INLINE_VISIBILITY 682 reference operator*() const {return __i_->__cc;} 683 _LIBCPP_INLINE_VISIBILITY 684 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 685 686 _LIBCPP_INLINE_VISIBILITY 687 __hash_map_iterator& operator++() {++__i_; return *this;} 688 _LIBCPP_INLINE_VISIBILITY 689 __hash_map_iterator operator++(int) 690 { 691 __hash_map_iterator __t(*this); 692 ++(*this); 693 return __t; 694 } 695 696 friend _LIBCPP_INLINE_VISIBILITY 697 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 698 {return __x.__i_ == __y.__i_;} 699 friend _LIBCPP_INLINE_VISIBILITY 700 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 701 {return __x.__i_ != __y.__i_;} 702 703 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 704 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 705 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 706 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 707 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 708 }; 709 710 template <class _HashIterator> 711 class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator 712 { 713 _HashIterator __i_; 714 715 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 716 typedef const typename _HashIterator::value_type::value_type::first_type key_type; 717 typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 718 public: 719 typedef forward_iterator_tag iterator_category; 720 typedef pair<key_type, mapped_type> value_type; 721 typedef typename _HashIterator::difference_type difference_type; 722 typedef const value_type& reference; 723 typedef typename __pointer_traits::template 724 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 725 rebind<const value_type> 726 #else 727 rebind<const value_type>::other 728 #endif 729 pointer; 730 731 _LIBCPP_INLINE_VISIBILITY 732 __hash_map_const_iterator() _NOEXCEPT {} 733 734 _LIBCPP_INLINE_VISIBILITY 735 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 736 _LIBCPP_INLINE_VISIBILITY 737 __hash_map_const_iterator( 738 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 739 _NOEXCEPT 740 : __i_(__i.__i_) {} 741 742 _LIBCPP_INLINE_VISIBILITY 743 reference operator*() const {return __i_->__cc;} 744 _LIBCPP_INLINE_VISIBILITY 745 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 746 747 _LIBCPP_INLINE_VISIBILITY 748 __hash_map_const_iterator& operator++() {++__i_; return *this;} 749 _LIBCPP_INLINE_VISIBILITY 750 __hash_map_const_iterator operator++(int) 751 { 752 __hash_map_const_iterator __t(*this); 753 ++(*this); 754 return __t; 755 } 756 757 friend _LIBCPP_INLINE_VISIBILITY 758 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 759 {return __x.__i_ == __y.__i_;} 760 friend _LIBCPP_INLINE_VISIBILITY 761 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 762 {return __x.__i_ != __y.__i_;} 763 764 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 765 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 766 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 767 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 768 }; 769 770 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 771 class _Alloc = allocator<pair<const _Key, _Tp> > > 772 class _LIBCPP_TYPE_VIS_ONLY unordered_map 773 { 774 public: 775 // types 776 typedef _Key key_type; 777 typedef _Tp mapped_type; 778 typedef _Hash hasher; 779 typedef _Pred key_equal; 780 typedef _Alloc allocator_type; 781 typedef pair<const key_type, mapped_type> value_type; 782 typedef pair<key_type, mapped_type> __nc_value_type; 783 typedef value_type& reference; 784 typedef const value_type& const_reference; 785 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 786 "Invalid allocator::value_type"); 787 788 private: 789 typedef __hash_value_type<key_type, mapped_type> __value_type; 790 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 791 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 792 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 793 __value_type>::type __allocator_type; 794 795 typedef __hash_table<__value_type, __hasher, 796 __key_equal, __allocator_type> __table; 797 798 __table __table_; 799 800 typedef typename __table::__node_pointer __node_pointer; 801 typedef typename __table::__node_const_pointer __node_const_pointer; 802 typedef typename __table::__node_traits __node_traits; 803 typedef typename __table::__node_allocator __node_allocator; 804 typedef typename __table::__node __node; 805 typedef __hash_map_node_destructor<__node_allocator> _Dp; 806 typedef unique_ptr<__node, _Dp> __node_holder; 807 typedef allocator_traits<allocator_type> __alloc_traits; 808 public: 809 typedef typename __alloc_traits::pointer pointer; 810 typedef typename __alloc_traits::const_pointer const_pointer; 811 typedef typename __alloc_traits::size_type size_type; 812 typedef typename __alloc_traits::difference_type difference_type; 813 814 typedef __hash_map_iterator<typename __table::iterator> iterator; 815 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 816 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 817 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 818 819 _LIBCPP_INLINE_VISIBILITY 820 unordered_map() 821 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 822 { 823 #if _LIBCPP_DEBUG_LEVEL >= 2 824 __get_db()->__insert_c(this); 825 #endif 826 } 827 explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 828 const key_equal& __eql = key_equal()); 829 unordered_map(size_type __n, const hasher& __hf, 830 const key_equal& __eql, 831 const allocator_type& __a); 832 template <class _InputIterator> 833 unordered_map(_InputIterator __first, _InputIterator __last); 834 template <class _InputIterator> 835 unordered_map(_InputIterator __first, _InputIterator __last, 836 size_type __n, const hasher& __hf = hasher(), 837 const key_equal& __eql = key_equal()); 838 template <class _InputIterator> 839 unordered_map(_InputIterator __first, _InputIterator __last, 840 size_type __n, const hasher& __hf, 841 const key_equal& __eql, 842 const allocator_type& __a); 843 explicit unordered_map(const allocator_type& __a); 844 unordered_map(const unordered_map& __u); 845 unordered_map(const unordered_map& __u, const allocator_type& __a); 846 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 847 unordered_map(unordered_map&& __u) 848 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 849 unordered_map(unordered_map&& __u, const allocator_type& __a); 850 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 851 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 852 unordered_map(initializer_list<value_type> __il); 853 unordered_map(initializer_list<value_type> __il, size_type __n, 854 const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 855 unordered_map(initializer_list<value_type> __il, size_type __n, 856 const hasher& __hf, const key_equal& __eql, 857 const allocator_type& __a); 858 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 859 #if _LIBCPP_STD_VER > 11 860 _LIBCPP_INLINE_VISIBILITY 861 unordered_map(size_type __n, const allocator_type& __a) 862 : unordered_map(__n, hasher(), key_equal(), __a) {} 863 _LIBCPP_INLINE_VISIBILITY 864 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a) 865 : unordered_map(__n, __hf, key_equal(), __a) {} 866 template <class _InputIterator> 867 _LIBCPP_INLINE_VISIBILITY 868 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 869 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} 870 template <class _InputIterator> 871 _LIBCPP_INLINE_VISIBILITY 872 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 873 const allocator_type& __a) 874 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} 875 _LIBCPP_INLINE_VISIBILITY 876 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 877 : unordered_map(__il, __n, hasher(), key_equal(), __a) {} 878 _LIBCPP_INLINE_VISIBILITY 879 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 880 const allocator_type& __a) 881 : unordered_map(__il, __n, __hf, key_equal(), __a) {} 882 #endif 883 // ~unordered_map() = default; 884 _LIBCPP_INLINE_VISIBILITY 885 unordered_map& operator=(const unordered_map& __u) 886 { 887 #if __cplusplus >= 201103L 888 __table_ = __u.__table_; 889 #else 890 if (this != &__u) { 891 __table_.clear(); 892 __table_.hash_function() = __u.__table_.hash_function(); 893 __table_.key_eq() = __u.__table_.key_eq(); 894 __table_.max_load_factor() = __u.__table_.max_load_factor(); 895 __table_.__copy_assign_alloc(__u.__table_); 896 insert(__u.begin(), __u.end()); 897 } 898 #endif 899 return *this; 900 } 901 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 902 unordered_map& operator=(unordered_map&& __u) 903 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 904 #endif 905 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 906 unordered_map& operator=(initializer_list<value_type> __il); 907 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 908 909 _LIBCPP_INLINE_VISIBILITY 910 allocator_type get_allocator() const _NOEXCEPT 911 {return allocator_type(__table_.__node_alloc());} 912 913 _LIBCPP_INLINE_VISIBILITY 914 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 915 _LIBCPP_INLINE_VISIBILITY 916 size_type size() const _NOEXCEPT {return __table_.size();} 917 _LIBCPP_INLINE_VISIBILITY 918 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 919 920 _LIBCPP_INLINE_VISIBILITY 921 iterator begin() _NOEXCEPT {return __table_.begin();} 922 _LIBCPP_INLINE_VISIBILITY 923 iterator end() _NOEXCEPT {return __table_.end();} 924 _LIBCPP_INLINE_VISIBILITY 925 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 926 _LIBCPP_INLINE_VISIBILITY 927 const_iterator end() const _NOEXCEPT {return __table_.end();} 928 _LIBCPP_INLINE_VISIBILITY 929 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 930 _LIBCPP_INLINE_VISIBILITY 931 const_iterator cend() const _NOEXCEPT {return __table_.end();} 932 933 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 934 #ifndef _LIBCPP_HAS_NO_VARIADICS 935 936 template <class... _Args> 937 pair<iterator, bool> emplace(_Args&&... __args); 938 939 template <class... _Args> 940 _LIBCPP_INLINE_VISIBILITY 941 #if _LIBCPP_DEBUG_LEVEL >= 2 942 iterator emplace_hint(const_iterator __p, _Args&&... __args) 943 { 944 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 945 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" 946 " referring to this unordered_map"); 947 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 948 } 949 #else 950 iterator emplace_hint(const_iterator, _Args&&... __args) 951 {return emplace(_VSTD::forward<_Args>(__args)...).first;} 952 #endif 953 #endif // _LIBCPP_HAS_NO_VARIADICS 954 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 955 _LIBCPP_INLINE_VISIBILITY 956 pair<iterator, bool> insert(const value_type& __x) 957 {return __table_.__insert_unique(__x);} 958 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 959 template <class _Pp, 960 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 961 _LIBCPP_INLINE_VISIBILITY 962 pair<iterator, bool> insert(_Pp&& __x) 963 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 964 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 965 _LIBCPP_INLINE_VISIBILITY 966 #if _LIBCPP_DEBUG_LEVEL >= 2 967 iterator insert(const_iterator __p, const value_type& __x) 968 { 969 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 970 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" 971 " referring to this unordered_map"); 972 return insert(__x).first; 973 } 974 #else 975 iterator insert(const_iterator, const value_type& __x) 976 {return insert(__x).first;} 977 #endif 978 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 979 template <class _Pp, 980 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 981 _LIBCPP_INLINE_VISIBILITY 982 #if _LIBCPP_DEBUG_LEVEL >= 2 983 iterator insert(const_iterator __p, _Pp&& __x) 984 { 985 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 986 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" 987 " referring to this unordered_map"); 988 return insert(_VSTD::forward<_Pp>(__x)).first; 989 } 990 #else 991 iterator insert(const_iterator, _Pp&& __x) 992 {return insert(_VSTD::forward<_Pp>(__x)).first;} 993 #endif 994 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 995 template <class _InputIterator> 996 void insert(_InputIterator __first, _InputIterator __last); 997 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 998 _LIBCPP_INLINE_VISIBILITY 999 void insert(initializer_list<value_type> __il) 1000 {insert(__il.begin(), __il.end());} 1001 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1002 1003 #if _LIBCPP_STD_VER > 14 1004 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1005 #ifndef _LIBCPP_HAS_NO_VARIADICS 1006 template <class... _Args> 1007 _LIBCPP_INLINE_VISIBILITY 1008 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) 1009 { 1010 iterator __p = __table_.find(__k); 1011 if ( __p != end()) 1012 return _VSTD::make_pair(__p, false); 1013 else 1014 return _VSTD::make_pair( 1015 emplace_hint(__p, 1016 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), 1017 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)), 1018 true); 1019 } 1020 1021 template <class... _Args> 1022 _LIBCPP_INLINE_VISIBILITY 1023 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) 1024 { 1025 iterator __p = __table_.find(__k); 1026 if ( __p != end()) 1027 return _VSTD::make_pair(__p, false); 1028 else 1029 return _VSTD::make_pair( 1030 emplace_hint(__p, 1031 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 1032 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)), 1033 true); 1034 } 1035 1036 template <class... _Args> 1037 _LIBCPP_INLINE_VISIBILITY 1038 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) 1039 { 1040 iterator __p = __table_.find(__k); 1041 if ( __p != end()) 1042 return __p; 1043 else 1044 return emplace_hint(__h, 1045 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), 1046 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1047 } 1048 1049 template <class... _Args> 1050 _LIBCPP_INLINE_VISIBILITY 1051 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) 1052 { 1053 iterator __p = __table_.find(__k); 1054 if ( __p != end()) 1055 return __p; 1056 else 1057 return emplace_hint(__h, 1058 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 1059 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1060 } 1061 1062 template <class _Vp> 1063 _LIBCPP_INLINE_VISIBILITY 1064 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) 1065 { 1066 iterator __p = __table_.find(__k); 1067 if ( __p != end()) 1068 { 1069 __p->second = _VSTD::move(__v); 1070 return _VSTD::make_pair(__p, false); 1071 } 1072 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true); 1073 } 1074 1075 template <class _Vp> 1076 _LIBCPP_INLINE_VISIBILITY 1077 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) 1078 { 1079 iterator __p = __table_.find(__k); 1080 if ( __p != end()) 1081 { 1082 __p->second = _VSTD::move(__v); 1083 return _VSTD::make_pair(__p, false); 1084 } 1085 return _VSTD::make_pair(emplace_hint(__p, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v)), true); 1086 } 1087 1088 template <class _Vp> 1089 _LIBCPP_INLINE_VISIBILITY 1090 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) 1091 { 1092 iterator __p = __table_.find(__k); 1093 if ( __p != end()) 1094 { 1095 __p->second = _VSTD::move(__v); 1096 return __p; 1097 } 1098 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v)); 1099 } 1100 1101 template <class _Vp> 1102 _LIBCPP_INLINE_VISIBILITY 1103 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) 1104 { 1105 iterator __p = __table_.find(__k); 1106 if ( __p != end()) 1107 { 1108 __p->second = _VSTD::move(__v); 1109 return __p; 1110 } 1111 return emplace_hint(__h, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v)); 1112 } 1113 #endif 1114 #endif 1115 #endif 1116 1117 _LIBCPP_INLINE_VISIBILITY 1118 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1119 _LIBCPP_INLINE_VISIBILITY 1120 iterator erase(iterator __p) {return __table_.erase(__p.__i_);} 1121 _LIBCPP_INLINE_VISIBILITY 1122 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 1123 _LIBCPP_INLINE_VISIBILITY 1124 iterator erase(const_iterator __first, const_iterator __last) 1125 {return __table_.erase(__first.__i_, __last.__i_);} 1126 _LIBCPP_INLINE_VISIBILITY 1127 void clear() _NOEXCEPT {__table_.clear();} 1128 1129 _LIBCPP_INLINE_VISIBILITY 1130 void swap(unordered_map& __u) 1131 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1132 {__table_.swap(__u.__table_);} 1133 1134 _LIBCPP_INLINE_VISIBILITY 1135 hasher hash_function() const 1136 {return __table_.hash_function().hash_function();} 1137 _LIBCPP_INLINE_VISIBILITY 1138 key_equal key_eq() const 1139 {return __table_.key_eq().key_eq();} 1140 1141 _LIBCPP_INLINE_VISIBILITY 1142 iterator find(const key_type& __k) {return __table_.find(__k);} 1143 _LIBCPP_INLINE_VISIBILITY 1144 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1145 _LIBCPP_INLINE_VISIBILITY 1146 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 1147 _LIBCPP_INLINE_VISIBILITY 1148 pair<iterator, iterator> equal_range(const key_type& __k) 1149 {return __table_.__equal_range_unique(__k);} 1150 _LIBCPP_INLINE_VISIBILITY 1151 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1152 {return __table_.__equal_range_unique(__k);} 1153 1154 mapped_type& operator[](const key_type& __k); 1155 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1156 mapped_type& operator[](key_type&& __k); 1157 #endif 1158 1159 mapped_type& at(const key_type& __k); 1160 const mapped_type& at(const key_type& __k) const; 1161 1162 _LIBCPP_INLINE_VISIBILITY 1163 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1164 _LIBCPP_INLINE_VISIBILITY 1165 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 1166 1167 _LIBCPP_INLINE_VISIBILITY 1168 size_type bucket_size(size_type __n) const 1169 {return __table_.bucket_size(__n);} 1170 _LIBCPP_INLINE_VISIBILITY 1171 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1172 1173 _LIBCPP_INLINE_VISIBILITY 1174 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1175 _LIBCPP_INLINE_VISIBILITY 1176 local_iterator end(size_type __n) {return __table_.end(__n);} 1177 _LIBCPP_INLINE_VISIBILITY 1178 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1179 _LIBCPP_INLINE_VISIBILITY 1180 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1181 _LIBCPP_INLINE_VISIBILITY 1182 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1183 _LIBCPP_INLINE_VISIBILITY 1184 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1185 1186 _LIBCPP_INLINE_VISIBILITY 1187 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1188 _LIBCPP_INLINE_VISIBILITY 1189 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1190 _LIBCPP_INLINE_VISIBILITY 1191 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1192 _LIBCPP_INLINE_VISIBILITY 1193 void rehash(size_type __n) {__table_.rehash(__n);} 1194 _LIBCPP_INLINE_VISIBILITY 1195 void reserve(size_type __n) {__table_.reserve(__n);} 1196 1197 #if _LIBCPP_DEBUG_LEVEL >= 2 1198 1199 bool __dereferenceable(const const_iterator* __i) const 1200 {return __table_.__dereferenceable(&__i->__i_);} 1201 bool __decrementable(const const_iterator* __i) const 1202 {return __table_.__decrementable(&__i->__i_);} 1203 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1204 {return __table_.__addable(&__i->__i_, __n);} 1205 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1206 {return __table_.__addable(&__i->__i_, __n);} 1207 1208 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1209 1210 private: 1211 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1212 __node_holder __construct_node(); 1213 template <class _A0> 1214 __node_holder 1215 __construct_node(_A0&& __a0); 1216 __node_holder __construct_node_with_key(key_type&& __k); 1217 #ifndef _LIBCPP_HAS_NO_VARIADICS 1218 template <class _A0, class _A1, class ..._Args> 1219 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1220 #endif // _LIBCPP_HAS_NO_VARIADICS 1221 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1222 __node_holder __construct_node_with_key(const key_type& __k); 1223 }; 1224 1225 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1226 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1227 size_type __n, const hasher& __hf, const key_equal& __eql) 1228 : __table_(__hf, __eql) 1229 { 1230 #if _LIBCPP_DEBUG_LEVEL >= 2 1231 __get_db()->__insert_c(this); 1232 #endif 1233 __table_.rehash(__n); 1234 } 1235 1236 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1237 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1238 size_type __n, const hasher& __hf, const key_equal& __eql, 1239 const allocator_type& __a) 1240 : __table_(__hf, __eql, __a) 1241 { 1242 #if _LIBCPP_DEBUG_LEVEL >= 2 1243 __get_db()->__insert_c(this); 1244 #endif 1245 __table_.rehash(__n); 1246 } 1247 1248 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1249 inline _LIBCPP_INLINE_VISIBILITY 1250 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1251 const allocator_type& __a) 1252 : __table_(__a) 1253 { 1254 #if _LIBCPP_DEBUG_LEVEL >= 2 1255 __get_db()->__insert_c(this); 1256 #endif 1257 } 1258 1259 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1260 template <class _InputIterator> 1261 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1262 _InputIterator __first, _InputIterator __last) 1263 { 1264 #if _LIBCPP_DEBUG_LEVEL >= 2 1265 __get_db()->__insert_c(this); 1266 #endif 1267 insert(__first, __last); 1268 } 1269 1270 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1271 template <class _InputIterator> 1272 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1273 _InputIterator __first, _InputIterator __last, size_type __n, 1274 const hasher& __hf, const key_equal& __eql) 1275 : __table_(__hf, __eql) 1276 { 1277 #if _LIBCPP_DEBUG_LEVEL >= 2 1278 __get_db()->__insert_c(this); 1279 #endif 1280 __table_.rehash(__n); 1281 insert(__first, __last); 1282 } 1283 1284 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1285 template <class _InputIterator> 1286 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1287 _InputIterator __first, _InputIterator __last, size_type __n, 1288 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1289 : __table_(__hf, __eql, __a) 1290 { 1291 #if _LIBCPP_DEBUG_LEVEL >= 2 1292 __get_db()->__insert_c(this); 1293 #endif 1294 __table_.rehash(__n); 1295 insert(__first, __last); 1296 } 1297 1298 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1299 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1300 const unordered_map& __u) 1301 : __table_(__u.__table_) 1302 { 1303 #if _LIBCPP_DEBUG_LEVEL >= 2 1304 __get_db()->__insert_c(this); 1305 #endif 1306 __table_.rehash(__u.bucket_count()); 1307 insert(__u.begin(), __u.end()); 1308 } 1309 1310 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1311 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1312 const unordered_map& __u, const allocator_type& __a) 1313 : __table_(__u.__table_, __a) 1314 { 1315 #if _LIBCPP_DEBUG_LEVEL >= 2 1316 __get_db()->__insert_c(this); 1317 #endif 1318 __table_.rehash(__u.bucket_count()); 1319 insert(__u.begin(), __u.end()); 1320 } 1321 1322 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1323 1324 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1325 inline _LIBCPP_INLINE_VISIBILITY 1326 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1327 unordered_map&& __u) 1328 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1329 : __table_(_VSTD::move(__u.__table_)) 1330 { 1331 #if _LIBCPP_DEBUG_LEVEL >= 2 1332 __get_db()->__insert_c(this); 1333 __get_db()->swap(this, &__u); 1334 #endif 1335 } 1336 1337 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1338 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1339 unordered_map&& __u, const allocator_type& __a) 1340 : __table_(_VSTD::move(__u.__table_), __a) 1341 { 1342 #if _LIBCPP_DEBUG_LEVEL >= 2 1343 __get_db()->__insert_c(this); 1344 #endif 1345 if (__a != __u.get_allocator()) 1346 { 1347 iterator __i = __u.begin(); 1348 while (__u.size() != 0) 1349 __table_.__insert_unique( 1350 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1351 ); 1352 } 1353 #if _LIBCPP_DEBUG_LEVEL >= 2 1354 else 1355 __get_db()->swap(this, &__u); 1356 #endif 1357 } 1358 1359 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1360 1361 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1362 1363 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1364 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1365 initializer_list<value_type> __il) 1366 { 1367 #if _LIBCPP_DEBUG_LEVEL >= 2 1368 __get_db()->__insert_c(this); 1369 #endif 1370 insert(__il.begin(), __il.end()); 1371 } 1372 1373 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1374 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1375 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1376 const key_equal& __eql) 1377 : __table_(__hf, __eql) 1378 { 1379 #if _LIBCPP_DEBUG_LEVEL >= 2 1380 __get_db()->__insert_c(this); 1381 #endif 1382 __table_.rehash(__n); 1383 insert(__il.begin(), __il.end()); 1384 } 1385 1386 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1387 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1388 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1389 const key_equal& __eql, const allocator_type& __a) 1390 : __table_(__hf, __eql, __a) 1391 { 1392 #if _LIBCPP_DEBUG_LEVEL >= 2 1393 __get_db()->__insert_c(this); 1394 #endif 1395 __table_.rehash(__n); 1396 insert(__il.begin(), __il.end()); 1397 } 1398 1399 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1400 1401 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1402 1403 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1404 inline _LIBCPP_INLINE_VISIBILITY 1405 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1406 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1407 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1408 { 1409 __table_ = _VSTD::move(__u.__table_); 1410 return *this; 1411 } 1412 1413 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1414 1415 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1416 1417 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1418 inline _LIBCPP_INLINE_VISIBILITY 1419 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1420 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1421 initializer_list<value_type> __il) 1422 { 1423 __table_.__assign_unique(__il.begin(), __il.end()); 1424 return *this; 1425 } 1426 1427 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1428 1429 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1430 1431 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1432 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1433 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1434 { 1435 __node_allocator& __na = __table_.__node_alloc(); 1436 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1437 __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1438 __h.get_deleter().__first_constructed = true; 1439 __h.get_deleter().__second_constructed = true; 1440 return __h; 1441 } 1442 1443 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1444 template <class _A0> 1445 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1446 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1447 { 1448 __node_allocator& __na = __table_.__node_alloc(); 1449 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1450 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1451 _VSTD::forward<_A0>(__a0)); 1452 __h.get_deleter().__first_constructed = true; 1453 __h.get_deleter().__second_constructed = true; 1454 return __h; 1455 } 1456 1457 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1458 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1459 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k) 1460 { 1461 __node_allocator& __na = __table_.__node_alloc(); 1462 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1463 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k)); 1464 __h.get_deleter().__first_constructed = true; 1465 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1466 __h.get_deleter().__second_constructed = true; 1467 return __h; 1468 } 1469 1470 #ifndef _LIBCPP_HAS_NO_VARIADICS 1471 1472 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1473 template <class _A0, class _A1, class ..._Args> 1474 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1475 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1476 _A1&& __a1, 1477 _Args&&... __args) 1478 { 1479 __node_allocator& __na = __table_.__node_alloc(); 1480 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1481 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1482 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1483 _VSTD::forward<_Args>(__args)...); 1484 __h.get_deleter().__first_constructed = true; 1485 __h.get_deleter().__second_constructed = true; 1486 return __h; 1487 } 1488 1489 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1490 template <class... _Args> 1491 pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1492 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1493 { 1494 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1495 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1496 if (__r.second) 1497 __h.release(); 1498 return __r; 1499 } 1500 1501 #endif // _LIBCPP_HAS_NO_VARIADICS 1502 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1503 1504 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1505 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1506 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1507 { 1508 __node_allocator& __na = __table_.__node_alloc(); 1509 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1510 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1511 __h.get_deleter().__first_constructed = true; 1512 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1513 __h.get_deleter().__second_constructed = true; 1514 return _VSTD::move(__h); // explicitly moved for C++03 1515 } 1516 1517 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1518 template <class _InputIterator> 1519 inline _LIBCPP_INLINE_VISIBILITY 1520 void 1521 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1522 _InputIterator __last) 1523 { 1524 for (; __first != __last; ++__first) 1525 __table_.__insert_unique(*__first); 1526 } 1527 1528 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1529 _Tp& 1530 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1531 { 1532 iterator __i = find(__k); 1533 if (__i != end()) 1534 return __i->second; 1535 __node_holder __h = __construct_node_with_key(__k); 1536 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1537 __h.release(); 1538 return __r.first->second; 1539 } 1540 1541 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1542 1543 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1544 _Tp& 1545 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1546 { 1547 iterator __i = find(__k); 1548 if (__i != end()) 1549 return __i->second; 1550 __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); 1551 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1552 __h.release(); 1553 return __r.first->second; 1554 } 1555 1556 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1557 1558 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1559 _Tp& 1560 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1561 { 1562 iterator __i = find(__k); 1563 #ifndef _LIBCPP_NO_EXCEPTIONS 1564 if (__i == end()) 1565 throw out_of_range("unordered_map::at: key not found"); 1566 #endif // _LIBCPP_NO_EXCEPTIONS 1567 return __i->second; 1568 } 1569 1570 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1571 const _Tp& 1572 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1573 { 1574 const_iterator __i = find(__k); 1575 #ifndef _LIBCPP_NO_EXCEPTIONS 1576 if (__i == end()) 1577 throw out_of_range("unordered_map::at: key not found"); 1578 #endif // _LIBCPP_NO_EXCEPTIONS 1579 return __i->second; 1580 } 1581 1582 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1583 inline _LIBCPP_INLINE_VISIBILITY 1584 void 1585 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1586 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1587 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1588 { 1589 __x.swap(__y); 1590 } 1591 1592 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1593 bool 1594 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1595 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1596 { 1597 if (__x.size() != __y.size()) 1598 return false; 1599 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1600 const_iterator; 1601 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1602 __i != __ex; ++__i) 1603 { 1604 const_iterator __j = __y.find(__i->first); 1605 if (__j == __ey || !(*__i == *__j)) 1606 return false; 1607 } 1608 return true; 1609 } 1610 1611 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1612 inline _LIBCPP_INLINE_VISIBILITY 1613 bool 1614 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1615 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1616 { 1617 return !(__x == __y); 1618 } 1619 1620 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1621 class _Alloc = allocator<pair<const _Key, _Tp> > > 1622 class _LIBCPP_TYPE_VIS_ONLY unordered_multimap 1623 { 1624 public: 1625 // types 1626 typedef _Key key_type; 1627 typedef _Tp mapped_type; 1628 typedef _Hash hasher; 1629 typedef _Pred key_equal; 1630 typedef _Alloc allocator_type; 1631 typedef pair<const key_type, mapped_type> value_type; 1632 typedef pair<key_type, mapped_type> __nc_value_type; 1633 typedef value_type& reference; 1634 typedef const value_type& const_reference; 1635 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1636 "Invalid allocator::value_type"); 1637 1638 private: 1639 typedef __hash_value_type<key_type, mapped_type> __value_type; 1640 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 1641 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 1642 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1643 __value_type>::type __allocator_type; 1644 1645 typedef __hash_table<__value_type, __hasher, 1646 __key_equal, __allocator_type> __table; 1647 1648 __table __table_; 1649 1650 typedef typename __table::__node_traits __node_traits; 1651 typedef typename __table::__node_allocator __node_allocator; 1652 typedef typename __table::__node __node; 1653 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1654 typedef unique_ptr<__node, _Dp> __node_holder; 1655 typedef allocator_traits<allocator_type> __alloc_traits; 1656 public: 1657 typedef typename __alloc_traits::pointer pointer; 1658 typedef typename __alloc_traits::const_pointer const_pointer; 1659 typedef typename __alloc_traits::size_type size_type; 1660 typedef typename __alloc_traits::difference_type difference_type; 1661 1662 typedef __hash_map_iterator<typename __table::iterator> iterator; 1663 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1664 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1665 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1666 1667 _LIBCPP_INLINE_VISIBILITY 1668 unordered_multimap() 1669 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1670 { 1671 #if _LIBCPP_DEBUG_LEVEL >= 2 1672 __get_db()->__insert_c(this); 1673 #endif 1674 } 1675 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1676 const key_equal& __eql = key_equal()); 1677 unordered_multimap(size_type __n, const hasher& __hf, 1678 const key_equal& __eql, 1679 const allocator_type& __a); 1680 template <class _InputIterator> 1681 unordered_multimap(_InputIterator __first, _InputIterator __last); 1682 template <class _InputIterator> 1683 unordered_multimap(_InputIterator __first, _InputIterator __last, 1684 size_type __n, const hasher& __hf = hasher(), 1685 const key_equal& __eql = key_equal()); 1686 template <class _InputIterator> 1687 unordered_multimap(_InputIterator __first, _InputIterator __last, 1688 size_type __n, const hasher& __hf, 1689 const key_equal& __eql, 1690 const allocator_type& __a); 1691 explicit unordered_multimap(const allocator_type& __a); 1692 unordered_multimap(const unordered_multimap& __u); 1693 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1694 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1695 unordered_multimap(unordered_multimap&& __u) 1696 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1697 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1698 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1699 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1700 unordered_multimap(initializer_list<value_type> __il); 1701 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1702 const hasher& __hf = hasher(), 1703 const key_equal& __eql = key_equal()); 1704 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1705 const hasher& __hf, const key_equal& __eql, 1706 const allocator_type& __a); 1707 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1708 #if _LIBCPP_STD_VER > 11 1709 _LIBCPP_INLINE_VISIBILITY 1710 unordered_multimap(size_type __n, const allocator_type& __a) 1711 : unordered_multimap(__n, hasher(), key_equal(), __a) {} 1712 _LIBCPP_INLINE_VISIBILITY 1713 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 1714 : unordered_multimap(__n, __hf, key_equal(), __a) {} 1715 template <class _InputIterator> 1716 _LIBCPP_INLINE_VISIBILITY 1717 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1718 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 1719 template <class _InputIterator> 1720 _LIBCPP_INLINE_VISIBILITY 1721 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 1722 const allocator_type& __a) 1723 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 1724 _LIBCPP_INLINE_VISIBILITY 1725 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1726 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 1727 _LIBCPP_INLINE_VISIBILITY 1728 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1729 const allocator_type& __a) 1730 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 1731 #endif 1732 // ~unordered_multimap() = default; 1733 _LIBCPP_INLINE_VISIBILITY 1734 unordered_multimap& operator=(const unordered_multimap& __u) 1735 { 1736 #if __cplusplus >= 201103L 1737 __table_ = __u.__table_; 1738 #else 1739 if (this != &__u) { 1740 __table_.clear(); 1741 __table_.hash_function() = __u.__table_.hash_function(); 1742 __table_.key_eq() = __u.__table_.key_eq(); 1743 __table_.max_load_factor() = __u.__table_.max_load_factor(); 1744 __table_.__copy_assign_alloc(__u.__table_); 1745 insert(__u.begin(), __u.end()); 1746 } 1747 #endif 1748 return *this; 1749 } 1750 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1751 unordered_multimap& operator=(unordered_multimap&& __u) 1752 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1753 #endif 1754 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1755 unordered_multimap& operator=(initializer_list<value_type> __il); 1756 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1757 1758 _LIBCPP_INLINE_VISIBILITY 1759 allocator_type get_allocator() const _NOEXCEPT 1760 {return allocator_type(__table_.__node_alloc());} 1761 1762 _LIBCPP_INLINE_VISIBILITY 1763 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1764 _LIBCPP_INLINE_VISIBILITY 1765 size_type size() const _NOEXCEPT {return __table_.size();} 1766 _LIBCPP_INLINE_VISIBILITY 1767 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1768 1769 _LIBCPP_INLINE_VISIBILITY 1770 iterator begin() _NOEXCEPT {return __table_.begin();} 1771 _LIBCPP_INLINE_VISIBILITY 1772 iterator end() _NOEXCEPT {return __table_.end();} 1773 _LIBCPP_INLINE_VISIBILITY 1774 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1775 _LIBCPP_INLINE_VISIBILITY 1776 const_iterator end() const _NOEXCEPT {return __table_.end();} 1777 _LIBCPP_INLINE_VISIBILITY 1778 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1779 _LIBCPP_INLINE_VISIBILITY 1780 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1781 1782 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1783 #ifndef _LIBCPP_HAS_NO_VARIADICS 1784 1785 template <class... _Args> 1786 iterator emplace(_Args&&... __args); 1787 1788 template <class... _Args> 1789 iterator emplace_hint(const_iterator __p, _Args&&... __args); 1790 #endif // _LIBCPP_HAS_NO_VARIADICS 1791 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1792 _LIBCPP_INLINE_VISIBILITY 1793 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1794 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1795 template <class _Pp, 1796 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1797 _LIBCPP_INLINE_VISIBILITY 1798 iterator insert(_Pp&& __x) 1799 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1800 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1801 _LIBCPP_INLINE_VISIBILITY 1802 iterator insert(const_iterator __p, const value_type& __x) 1803 {return __table_.__insert_multi(__p.__i_, __x);} 1804 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1805 template <class _Pp, 1806 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1807 _LIBCPP_INLINE_VISIBILITY 1808 iterator insert(const_iterator __p, _Pp&& __x) 1809 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1810 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1811 template <class _InputIterator> 1812 void insert(_InputIterator __first, _InputIterator __last); 1813 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1814 _LIBCPP_INLINE_VISIBILITY 1815 void insert(initializer_list<value_type> __il) 1816 {insert(__il.begin(), __il.end());} 1817 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1818 1819 _LIBCPP_INLINE_VISIBILITY 1820 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1821 _LIBCPP_INLINE_VISIBILITY 1822 iterator erase(iterator __p) {return __table_.erase(__p.__i_);} 1823 _LIBCPP_INLINE_VISIBILITY 1824 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1825 _LIBCPP_INLINE_VISIBILITY 1826 iterator erase(const_iterator __first, const_iterator __last) 1827 {return __table_.erase(__first.__i_, __last.__i_);} 1828 _LIBCPP_INLINE_VISIBILITY 1829 void clear() _NOEXCEPT {__table_.clear();} 1830 1831 _LIBCPP_INLINE_VISIBILITY 1832 void swap(unordered_multimap& __u) 1833 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1834 {__table_.swap(__u.__table_);} 1835 1836 _LIBCPP_INLINE_VISIBILITY 1837 hasher hash_function() const 1838 {return __table_.hash_function().hash_function();} 1839 _LIBCPP_INLINE_VISIBILITY 1840 key_equal key_eq() const 1841 {return __table_.key_eq().key_eq();} 1842 1843 _LIBCPP_INLINE_VISIBILITY 1844 iterator find(const key_type& __k) {return __table_.find(__k);} 1845 _LIBCPP_INLINE_VISIBILITY 1846 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1847 _LIBCPP_INLINE_VISIBILITY 1848 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1849 _LIBCPP_INLINE_VISIBILITY 1850 pair<iterator, iterator> equal_range(const key_type& __k) 1851 {return __table_.__equal_range_multi(__k);} 1852 _LIBCPP_INLINE_VISIBILITY 1853 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1854 {return __table_.__equal_range_multi(__k);} 1855 1856 _LIBCPP_INLINE_VISIBILITY 1857 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1858 _LIBCPP_INLINE_VISIBILITY 1859 size_type max_bucket_count() const _NOEXCEPT 1860 {return __table_.max_bucket_count();} 1861 1862 _LIBCPP_INLINE_VISIBILITY 1863 size_type bucket_size(size_type __n) const 1864 {return __table_.bucket_size(__n);} 1865 _LIBCPP_INLINE_VISIBILITY 1866 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1867 1868 _LIBCPP_INLINE_VISIBILITY 1869 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1870 _LIBCPP_INLINE_VISIBILITY 1871 local_iterator end(size_type __n) {return __table_.end(__n);} 1872 _LIBCPP_INLINE_VISIBILITY 1873 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1874 _LIBCPP_INLINE_VISIBILITY 1875 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1876 _LIBCPP_INLINE_VISIBILITY 1877 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1878 _LIBCPP_INLINE_VISIBILITY 1879 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1880 1881 _LIBCPP_INLINE_VISIBILITY 1882 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1883 _LIBCPP_INLINE_VISIBILITY 1884 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1885 _LIBCPP_INLINE_VISIBILITY 1886 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1887 _LIBCPP_INLINE_VISIBILITY 1888 void rehash(size_type __n) {__table_.rehash(__n);} 1889 _LIBCPP_INLINE_VISIBILITY 1890 void reserve(size_type __n) {__table_.reserve(__n);} 1891 1892 #if _LIBCPP_DEBUG_LEVEL >= 2 1893 1894 bool __dereferenceable(const const_iterator* __i) const 1895 {return __table_.__dereferenceable(&__i->__i_);} 1896 bool __decrementable(const const_iterator* __i) const 1897 {return __table_.__decrementable(&__i->__i_);} 1898 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1899 {return __table_.__addable(&__i->__i_, __n);} 1900 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1901 {return __table_.__addable(&__i->__i_, __n);} 1902 1903 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1904 1905 private: 1906 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1907 __node_holder __construct_node(); 1908 template <class _A0> 1909 __node_holder 1910 __construct_node(_A0&& __a0); 1911 #ifndef _LIBCPP_HAS_NO_VARIADICS 1912 template <class _A0, class _A1, class ..._Args> 1913 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1914 #endif // _LIBCPP_HAS_NO_VARIADICS 1915 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1916 }; 1917 1918 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1919 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1920 size_type __n, const hasher& __hf, const key_equal& __eql) 1921 : __table_(__hf, __eql) 1922 { 1923 #if _LIBCPP_DEBUG_LEVEL >= 2 1924 __get_db()->__insert_c(this); 1925 #endif 1926 __table_.rehash(__n); 1927 } 1928 1929 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1930 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1931 size_type __n, const hasher& __hf, const key_equal& __eql, 1932 const allocator_type& __a) 1933 : __table_(__hf, __eql, __a) 1934 { 1935 #if _LIBCPP_DEBUG_LEVEL >= 2 1936 __get_db()->__insert_c(this); 1937 #endif 1938 __table_.rehash(__n); 1939 } 1940 1941 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1942 template <class _InputIterator> 1943 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1944 _InputIterator __first, _InputIterator __last) 1945 { 1946 #if _LIBCPP_DEBUG_LEVEL >= 2 1947 __get_db()->__insert_c(this); 1948 #endif 1949 insert(__first, __last); 1950 } 1951 1952 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1953 template <class _InputIterator> 1954 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1955 _InputIterator __first, _InputIterator __last, size_type __n, 1956 const hasher& __hf, const key_equal& __eql) 1957 : __table_(__hf, __eql) 1958 { 1959 #if _LIBCPP_DEBUG_LEVEL >= 2 1960 __get_db()->__insert_c(this); 1961 #endif 1962 __table_.rehash(__n); 1963 insert(__first, __last); 1964 } 1965 1966 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1967 template <class _InputIterator> 1968 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1969 _InputIterator __first, _InputIterator __last, size_type __n, 1970 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1971 : __table_(__hf, __eql, __a) 1972 { 1973 #if _LIBCPP_DEBUG_LEVEL >= 2 1974 __get_db()->__insert_c(this); 1975 #endif 1976 __table_.rehash(__n); 1977 insert(__first, __last); 1978 } 1979 1980 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1981 inline _LIBCPP_INLINE_VISIBILITY 1982 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1983 const allocator_type& __a) 1984 : __table_(__a) 1985 { 1986 #if _LIBCPP_DEBUG_LEVEL >= 2 1987 __get_db()->__insert_c(this); 1988 #endif 1989 } 1990 1991 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1992 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1993 const unordered_multimap& __u) 1994 : __table_(__u.__table_) 1995 { 1996 #if _LIBCPP_DEBUG_LEVEL >= 2 1997 __get_db()->__insert_c(this); 1998 #endif 1999 __table_.rehash(__u.bucket_count()); 2000 insert(__u.begin(), __u.end()); 2001 } 2002 2003 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2004 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2005 const unordered_multimap& __u, const allocator_type& __a) 2006 : __table_(__u.__table_, __a) 2007 { 2008 #if _LIBCPP_DEBUG_LEVEL >= 2 2009 __get_db()->__insert_c(this); 2010 #endif 2011 __table_.rehash(__u.bucket_count()); 2012 insert(__u.begin(), __u.end()); 2013 } 2014 2015 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2016 2017 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2018 inline _LIBCPP_INLINE_VISIBILITY 2019 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2020 unordered_multimap&& __u) 2021 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 2022 : __table_(_VSTD::move(__u.__table_)) 2023 { 2024 #if _LIBCPP_DEBUG_LEVEL >= 2 2025 __get_db()->__insert_c(this); 2026 __get_db()->swap(this, &__u); 2027 #endif 2028 } 2029 2030 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2031 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2032 unordered_multimap&& __u, const allocator_type& __a) 2033 : __table_(_VSTD::move(__u.__table_), __a) 2034 { 2035 #if _LIBCPP_DEBUG_LEVEL >= 2 2036 __get_db()->__insert_c(this); 2037 #endif 2038 if (__a != __u.get_allocator()) 2039 { 2040 iterator __i = __u.begin(); 2041 while (__u.size() != 0) 2042 { 2043 __table_.__insert_multi( 2044 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 2045 ); 2046 } 2047 } 2048 #if _LIBCPP_DEBUG_LEVEL >= 2 2049 else 2050 __get_db()->swap(this, &__u); 2051 #endif 2052 } 2053 2054 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2055 2056 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2057 2058 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2059 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2060 initializer_list<value_type> __il) 2061 { 2062 #if _LIBCPP_DEBUG_LEVEL >= 2 2063 __get_db()->__insert_c(this); 2064 #endif 2065 insert(__il.begin(), __il.end()); 2066 } 2067 2068 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2069 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2070 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 2071 const key_equal& __eql) 2072 : __table_(__hf, __eql) 2073 { 2074 #if _LIBCPP_DEBUG_LEVEL >= 2 2075 __get_db()->__insert_c(this); 2076 #endif 2077 __table_.rehash(__n); 2078 insert(__il.begin(), __il.end()); 2079 } 2080 2081 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2082 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2083 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 2084 const key_equal& __eql, const allocator_type& __a) 2085 : __table_(__hf, __eql, __a) 2086 { 2087 #if _LIBCPP_DEBUG_LEVEL >= 2 2088 __get_db()->__insert_c(this); 2089 #endif 2090 __table_.rehash(__n); 2091 insert(__il.begin(), __il.end()); 2092 } 2093 2094 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2095 2096 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2097 2098 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2099 inline _LIBCPP_INLINE_VISIBILITY 2100 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2101 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 2102 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 2103 { 2104 __table_ = _VSTD::move(__u.__table_); 2105 return *this; 2106 } 2107 2108 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2109 2110 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2111 2112 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2113 inline _LIBCPP_INLINE_VISIBILITY 2114 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2115 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 2116 initializer_list<value_type> __il) 2117 { 2118 __table_.__assign_multi(__il.begin(), __il.end()); 2119 return *this; 2120 } 2121 2122 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2123 2124 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2125 2126 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2127 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 2128 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 2129 { 2130 __node_allocator& __na = __table_.__node_alloc(); 2131 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2132 __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 2133 __h.get_deleter().__first_constructed = true; 2134 __h.get_deleter().__second_constructed = true; 2135 return __h; 2136 } 2137 2138 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2139 template <class _A0> 2140 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 2141 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 2142 { 2143 __node_allocator& __na = __table_.__node_alloc(); 2144 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2145 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 2146 _VSTD::forward<_A0>(__a0)); 2147 __h.get_deleter().__first_constructed = true; 2148 __h.get_deleter().__second_constructed = true; 2149 return __h; 2150 } 2151 2152 #ifndef _LIBCPP_HAS_NO_VARIADICS 2153 2154 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2155 template <class _A0, class _A1, class ..._Args> 2156 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 2157 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 2158 _A0&& __a0, _A1&& __a1, _Args&&... __args) 2159 { 2160 __node_allocator& __na = __table_.__node_alloc(); 2161 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2162 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 2163 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 2164 _VSTD::forward<_Args>(__args)...); 2165 __h.get_deleter().__first_constructed = true; 2166 __h.get_deleter().__second_constructed = true; 2167 return __h; 2168 } 2169 2170 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2171 template <class... _Args> 2172 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2173 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 2174 { 2175 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2176 iterator __r = __table_.__node_insert_multi(__h.get()); 2177 __h.release(); 2178 return __r; 2179 } 2180 2181 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2182 template <class... _Args> 2183 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2184 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 2185 const_iterator __p, _Args&&... __args) 2186 { 2187 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2188 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 2189 __h.release(); 2190 return __r; 2191 } 2192 2193 #endif // _LIBCPP_HAS_NO_VARIADICS 2194 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2195 2196 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2197 template <class _InputIterator> 2198 inline _LIBCPP_INLINE_VISIBILITY 2199 void 2200 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 2201 _InputIterator __last) 2202 { 2203 for (; __first != __last; ++__first) 2204 __table_.__insert_multi(*__first); 2205 } 2206 2207 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2208 inline _LIBCPP_INLINE_VISIBILITY 2209 void 2210 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2211 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2212 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2213 { 2214 __x.swap(__y); 2215 } 2216 2217 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2218 bool 2219 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2220 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2221 { 2222 if (__x.size() != __y.size()) 2223 return false; 2224 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 2225 const_iterator; 2226 typedef pair<const_iterator, const_iterator> _EqRng; 2227 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 2228 { 2229 _EqRng __xeq = __x.equal_range(__i->first); 2230 _EqRng __yeq = __y.equal_range(__i->first); 2231 if (_VSTD::distance(__xeq.first, __xeq.second) != 2232 _VSTD::distance(__yeq.first, __yeq.second) || 2233 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2234 return false; 2235 __i = __xeq.second; 2236 } 2237 return true; 2238 } 2239 2240 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2241 inline _LIBCPP_INLINE_VISIBILITY 2242 bool 2243 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2244 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2245 { 2246 return !(__x == __y); 2247 } 2248 2249 _LIBCPP_END_NAMESPACE_STD 2250 2251 #endif // _LIBCPP_UNORDERED_MAP 2252
