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