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