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