unordered_map revision 227825
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 _Tp, class _Hash, bool = is_empty<_Hash>::value> 329class __unordered_map_hasher 330 : private _Hash 331{ 332public: 333 _LIBCPP_INLINE_VISIBILITY 334 __unordered_map_hasher() 335 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 336 : _Hash() {} 337 _LIBCPP_INLINE_VISIBILITY 338 __unordered_map_hasher(const _Hash& __h) 339 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 340 : _Hash(__h) {} 341 _LIBCPP_INLINE_VISIBILITY 342 const _Hash& hash_function() const _NOEXCEPT {return *this;} 343 _LIBCPP_INLINE_VISIBILITY 344 size_t operator()(const _Tp& __x) const 345 {return static_cast<const _Hash&>(*this)(__x.first);} 346 _LIBCPP_INLINE_VISIBILITY 347 size_t operator()(const typename _Tp::first_type& __x) const 348 {return static_cast<const _Hash&>(*this)(__x);} 349}; 350 351template <class _Tp, class _Hash> 352class __unordered_map_hasher<_Tp, _Hash, false> 353{ 354 _Hash __hash_; 355public: 356 _LIBCPP_INLINE_VISIBILITY 357 __unordered_map_hasher() 358 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 359 : __hash_() {} 360 _LIBCPP_INLINE_VISIBILITY 361 __unordered_map_hasher(const _Hash& __h) 362 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 363 : __hash_(__h) {} 364 _LIBCPP_INLINE_VISIBILITY 365 const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 366 _LIBCPP_INLINE_VISIBILITY 367 size_t operator()(const _Tp& __x) const 368 {return __hash_(__x.first);} 369 _LIBCPP_INLINE_VISIBILITY 370 size_t operator()(const typename _Tp::first_type& __x) const 371 {return __hash_(__x);} 372}; 373 374template <class _Tp, class _Pred, bool = is_empty<_Pred>::value> 375class __unordered_map_equal 376 : private _Pred 377{ 378public: 379 _LIBCPP_INLINE_VISIBILITY 380 __unordered_map_equal() 381 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 382 : _Pred() {} 383 _LIBCPP_INLINE_VISIBILITY 384 __unordered_map_equal(const _Pred& __p) 385 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 386 : _Pred(__p) {} 387 _LIBCPP_INLINE_VISIBILITY 388 const _Pred& key_eq() const _NOEXCEPT {return *this;} 389 _LIBCPP_INLINE_VISIBILITY 390 bool operator()(const _Tp& __x, const _Tp& __y) const 391 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 392 _LIBCPP_INLINE_VISIBILITY 393 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 394 {return static_cast<const _Pred&>(*this)(__x, __y.first);} 395 _LIBCPP_INLINE_VISIBILITY 396 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 397 {return static_cast<const _Pred&>(*this)(__x.first, __y);} 398 _LIBCPP_INLINE_VISIBILITY 399 bool operator()(const typename _Tp::first_type& __x, 400 const typename _Tp::first_type& __y) const 401 {return static_cast<const _Pred&>(*this)(__x, __y);} 402}; 403 404template <class _Tp, class _Pred> 405class __unordered_map_equal<_Tp, _Pred, false> 406{ 407 _Pred __pred_; 408public: 409 _LIBCPP_INLINE_VISIBILITY 410 __unordered_map_equal() 411 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 412 : __pred_() {} 413 _LIBCPP_INLINE_VISIBILITY 414 __unordered_map_equal(const _Pred& __p) 415 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 416 : __pred_(__p) {} 417 _LIBCPP_INLINE_VISIBILITY 418 const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 419 _LIBCPP_INLINE_VISIBILITY 420 bool operator()(const _Tp& __x, const _Tp& __y) const 421 {return __pred_(__x.first, __y.first);} 422 _LIBCPP_INLINE_VISIBILITY 423 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 424 {return __pred_(__x, __y.first);} 425 _LIBCPP_INLINE_VISIBILITY 426 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 427 {return __pred_(__x.first, __y);} 428 _LIBCPP_INLINE_VISIBILITY 429 bool operator()(const typename _Tp::first_type& __x, 430 const typename _Tp::first_type& __y) const 431 {return __pred_(__x, __y);} 432}; 433 434template <class _Alloc> 435class __hash_map_node_destructor 436{ 437 typedef _Alloc allocator_type; 438 typedef allocator_traits<allocator_type> __alloc_traits; 439 typedef typename __alloc_traits::value_type::value_type value_type; 440public: 441 typedef typename __alloc_traits::pointer pointer; 442private: 443 typedef typename value_type::first_type first_type; 444 typedef typename value_type::second_type second_type; 445 446 allocator_type& __na_; 447 448 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 449 450public: 451 bool __first_constructed; 452 bool __second_constructed; 453 454 _LIBCPP_INLINE_VISIBILITY 455 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 456 : __na_(__na), 457 __first_constructed(false), 458 __second_constructed(false) 459 {} 460 461#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 462 _LIBCPP_INLINE_VISIBILITY 463 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 464 _NOEXCEPT 465 : __na_(__x.__na_), 466 __first_constructed(__x.__value_constructed), 467 __second_constructed(__x.__value_constructed) 468 { 469 __x.__value_constructed = false; 470 } 471#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 472 _LIBCPP_INLINE_VISIBILITY 473 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 474 : __na_(__x.__na_), 475 __first_constructed(__x.__value_constructed), 476 __second_constructed(__x.__value_constructed) 477 { 478 const_cast<bool&>(__x.__value_constructed) = false; 479 } 480#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 481 482 _LIBCPP_INLINE_VISIBILITY 483 void operator()(pointer __p) _NOEXCEPT 484 { 485 if (__second_constructed) 486 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second)); 487 if (__first_constructed) 488 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); 489 if (__p) 490 __alloc_traits::deallocate(__na_, __p, 1); 491 } 492}; 493 494template <class _HashIterator> 495class _LIBCPP_VISIBLE __hash_map_iterator 496{ 497 _HashIterator __i_; 498 499 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 500 typedef const typename _HashIterator::value_type::first_type key_type; 501 typedef typename _HashIterator::value_type::second_type mapped_type; 502public: 503 typedef forward_iterator_tag iterator_category; 504 typedef pair<key_type, mapped_type> value_type; 505 typedef typename _HashIterator::difference_type difference_type; 506 typedef value_type& reference; 507 typedef typename __pointer_traits::template 508#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 509 rebind<value_type> 510#else 511 rebind<value_type>::other 512#endif 513 pointer; 514 515 _LIBCPP_INLINE_VISIBILITY 516 __hash_map_iterator() _NOEXCEPT {} 517 518 _LIBCPP_INLINE_VISIBILITY 519 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 520 521 _LIBCPP_INLINE_VISIBILITY 522 reference operator*() const {return *operator->();} 523 _LIBCPP_INLINE_VISIBILITY 524 pointer operator->() const {return (pointer)__i_.operator->();} 525 526 _LIBCPP_INLINE_VISIBILITY 527 __hash_map_iterator& operator++() {++__i_; return *this;} 528 _LIBCPP_INLINE_VISIBILITY 529 __hash_map_iterator operator++(int) 530 { 531 __hash_map_iterator __t(*this); 532 ++(*this); 533 return __t; 534 } 535 536 friend _LIBCPP_INLINE_VISIBILITY 537 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 538 {return __x.__i_ == __y.__i_;} 539 friend _LIBCPP_INLINE_VISIBILITY 540 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 541 {return __x.__i_ != __y.__i_;} 542 543 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; 544 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; 545 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator; 546 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator; 547 template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator; 548}; 549 550template <class _HashIterator> 551class _LIBCPP_VISIBLE __hash_map_const_iterator 552{ 553 _HashIterator __i_; 554 555 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 556 typedef const typename _HashIterator::value_type::first_type key_type; 557 typedef typename _HashIterator::value_type::second_type mapped_type; 558public: 559 typedef forward_iterator_tag iterator_category; 560 typedef pair<key_type, mapped_type> value_type; 561 typedef typename _HashIterator::difference_type difference_type; 562 typedef const value_type& reference; 563 typedef typename __pointer_traits::template 564#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 565 rebind<const value_type> 566#else 567 rebind<const value_type>::other 568#endif 569 pointer; 570 571 _LIBCPP_INLINE_VISIBILITY 572 __hash_map_const_iterator() _NOEXCEPT {} 573 574 _LIBCPP_INLINE_VISIBILITY 575 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 576 _LIBCPP_INLINE_VISIBILITY 577 __hash_map_const_iterator( 578 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 579 _NOEXCEPT 580 : __i_(__i.__i_) {} 581 582 _LIBCPP_INLINE_VISIBILITY 583 reference operator*() const {return *operator->();} 584 _LIBCPP_INLINE_VISIBILITY 585 pointer operator->() const {return (pointer)__i_.operator->();} 586 587 _LIBCPP_INLINE_VISIBILITY 588 __hash_map_const_iterator& operator++() {++__i_; return *this;} 589 _LIBCPP_INLINE_VISIBILITY 590 __hash_map_const_iterator operator++(int) 591 { 592 __hash_map_const_iterator __t(*this); 593 ++(*this); 594 return __t; 595 } 596 597 friend _LIBCPP_INLINE_VISIBILITY 598 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 599 {return __x.__i_ == __y.__i_;} 600 friend _LIBCPP_INLINE_VISIBILITY 601 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 602 {return __x.__i_ != __y.__i_;} 603 604 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; 605 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; 606 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator; 607 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator; 608}; 609 610template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 611 class _Alloc = allocator<pair<const _Key, _Tp> > > 612class _LIBCPP_VISIBLE unordered_map 613{ 614public: 615 // types 616 typedef _Key key_type; 617 typedef _Tp mapped_type; 618 typedef _Hash hasher; 619 typedef _Pred key_equal; 620 typedef _Alloc allocator_type; 621 typedef pair<const key_type, mapped_type> value_type; 622 typedef value_type& reference; 623 typedef const value_type& const_reference; 624 625private: 626 typedef pair<key_type, mapped_type> __value_type; 627 typedef __unordered_map_hasher<__value_type, hasher> __hasher; 628 typedef __unordered_map_equal<__value_type, key_equal> __key_equal; 629 typedef typename allocator_traits<allocator_type>::template 630#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 631 rebind_alloc<__value_type> 632#else 633 rebind_alloc<__value_type>::other 634#endif 635 __allocator_type; 636 637 typedef __hash_table<__value_type, __hasher, 638 __key_equal, __allocator_type> __table; 639 640 __table __table_; 641 642 typedef typename __table::__node_pointer __node_pointer; 643 typedef typename __table::__node_const_pointer __node_const_pointer; 644 typedef typename __table::__node_traits __node_traits; 645 typedef typename __table::__node_allocator __node_allocator; 646 typedef typename __table::__node __node; 647 typedef __hash_map_node_destructor<__node_allocator> _D; 648 typedef unique_ptr<__node, _D> __node_holder; 649 typedef allocator_traits<allocator_type> __alloc_traits; 650public: 651 typedef typename __alloc_traits::pointer pointer; 652 typedef typename __alloc_traits::const_pointer const_pointer; 653 typedef typename __alloc_traits::size_type size_type; 654 typedef typename __alloc_traits::difference_type difference_type; 655 656 typedef __hash_map_iterator<typename __table::iterator> iterator; 657 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 658 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 659 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 660 661 _LIBCPP_INLINE_VISIBILITY 662 unordered_map() 663 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 664 {} // = default; 665 explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 666 const key_equal& __eql = key_equal()); 667 unordered_map(size_type __n, const hasher& __hf, 668 const key_equal& __eql, 669 const allocator_type& __a); 670 template <class _InputIterator> 671 unordered_map(_InputIterator __first, _InputIterator __last); 672 template <class _InputIterator> 673 unordered_map(_InputIterator __first, _InputIterator __last, 674 size_type __n, const hasher& __hf = hasher(), 675 const key_equal& __eql = key_equal()); 676 template <class _InputIterator> 677 unordered_map(_InputIterator __first, _InputIterator __last, 678 size_type __n, const hasher& __hf, 679 const key_equal& __eql, 680 const allocator_type& __a); 681 explicit unordered_map(const allocator_type& __a); 682 unordered_map(const unordered_map& __u); 683 unordered_map(const unordered_map& __u, const allocator_type& __a); 684#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 685 unordered_map(unordered_map&& __u) 686 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 687 unordered_map(unordered_map&& __u, const allocator_type& __a); 688#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 689#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 690 unordered_map(initializer_list<value_type> __il); 691 unordered_map(initializer_list<value_type> __il, size_type __n, 692 const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 693 unordered_map(initializer_list<value_type> __il, size_type __n, 694 const hasher& __hf, const key_equal& __eql, 695 const allocator_type& __a); 696#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 697 // ~unordered_map() = default; 698 _LIBCPP_INLINE_VISIBILITY 699 unordered_map& operator=(const unordered_map& __u) 700 { 701 __table_ = __u.__table_; 702 return *this; 703 } 704#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 705 unordered_map& operator=(unordered_map&& __u) 706 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 707#endif 708#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 709 unordered_map& operator=(initializer_list<value_type> __il); 710#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 711 712 _LIBCPP_INLINE_VISIBILITY 713 allocator_type get_allocator() const _NOEXCEPT 714 {return allocator_type(__table_.__node_alloc());} 715 716 _LIBCPP_INLINE_VISIBILITY 717 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 718 _LIBCPP_INLINE_VISIBILITY 719 size_type size() const _NOEXCEPT {return __table_.size();} 720 _LIBCPP_INLINE_VISIBILITY 721 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 722 723 _LIBCPP_INLINE_VISIBILITY 724 iterator begin() _NOEXCEPT {return __table_.begin();} 725 _LIBCPP_INLINE_VISIBILITY 726 iterator end() _NOEXCEPT {return __table_.end();} 727 _LIBCPP_INLINE_VISIBILITY 728 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 729 _LIBCPP_INLINE_VISIBILITY 730 const_iterator end() const _NOEXCEPT {return __table_.end();} 731 _LIBCPP_INLINE_VISIBILITY 732 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 733 _LIBCPP_INLINE_VISIBILITY 734 const_iterator cend() const _NOEXCEPT {return __table_.end();} 735 736#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 737 _LIBCPP_INLINE_VISIBILITY 738 pair<iterator, bool> emplace() 739 {return __table_.__emplace_unique();} 740 741 template <class _A0, 742 class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 743 _LIBCPP_INLINE_VISIBILITY 744 pair<iterator, bool> emplace(_A0&& __a0) 745 {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0));} 746 747#ifndef _LIBCPP_HAS_NO_VARIADICS 748 749 template <class _A0, class... _Args, 750 class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 751 pair<iterator, bool> emplace(_A0&& __a0, _Args&&... __args); 752 753#endif // _LIBCPP_HAS_NO_VARIADICS 754 755 _LIBCPP_INLINE_VISIBILITY 756 iterator emplace_hint(const_iterator) 757 {return __table_.__emplace_unique().first;} 758 759 template <class _A0, 760 class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 761 _LIBCPP_INLINE_VISIBILITY 762 iterator emplace_hint(const_iterator, _A0&& __a0) 763 {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0)).first;} 764 765#ifndef _LIBCPP_HAS_NO_VARIADICS 766 767 template <class _A0, class... _Args, 768 class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 769 _LIBCPP_INLINE_VISIBILITY 770 iterator emplace_hint(const_iterator, _A0&& __a0, _Args&&... __args) 771 {return emplace(_VSTD::forward<_A0>(__a0), 772 _VSTD::forward<_Args>(__args)...).first;} 773#endif // _LIBCPP_HAS_NO_VARIADICS 774#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 775 _LIBCPP_INLINE_VISIBILITY 776 pair<iterator, bool> insert(const value_type& __x) 777 {return __table_.__insert_unique(__x);} 778#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 779 template <class _P, 780 class = typename enable_if<is_constructible<value_type, _P>::value>::type> 781 _LIBCPP_INLINE_VISIBILITY 782 pair<iterator, bool> insert(_P&& __x) 783 {return __table_.__insert_unique(_VSTD::forward<_P>(__x));} 784#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 785 _LIBCPP_INLINE_VISIBILITY 786 iterator insert(const_iterator, const value_type& __x) 787 {return insert(__x).first;} 788#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 789 template <class _P, 790 class = typename enable_if<is_constructible<value_type, _P>::value>::type> 791 _LIBCPP_INLINE_VISIBILITY 792 iterator insert(const_iterator, _P&& __x) 793 {return insert(_VSTD::forward<_P>(__x)).first;} 794#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 795 template <class _InputIterator> 796 void insert(_InputIterator __first, _InputIterator __last); 797#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 798 _LIBCPP_INLINE_VISIBILITY 799 void insert(initializer_list<value_type> __il) 800 {insert(__il.begin(), __il.end());} 801#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 802 803 _LIBCPP_INLINE_VISIBILITY 804 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 805 _LIBCPP_INLINE_VISIBILITY 806 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 807 _LIBCPP_INLINE_VISIBILITY 808 iterator erase(const_iterator __first, const_iterator __last) 809 {return __table_.erase(__first.__i_, __last.__i_);} 810 _LIBCPP_INLINE_VISIBILITY 811 void clear() _NOEXCEPT {__table_.clear();} 812 813 _LIBCPP_INLINE_VISIBILITY 814 void swap(unordered_map& __u) 815 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 816 {__table_.swap(__u.__table_);} 817 818 _LIBCPP_INLINE_VISIBILITY 819 hasher hash_function() const 820 {return __table_.hash_function().hash_function();} 821 _LIBCPP_INLINE_VISIBILITY 822 key_equal key_eq() const 823 {return __table_.key_eq().key_eq();} 824 825 _LIBCPP_INLINE_VISIBILITY 826 iterator find(const key_type& __k) {return __table_.find(__k);} 827 _LIBCPP_INLINE_VISIBILITY 828 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 829 _LIBCPP_INLINE_VISIBILITY 830 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 831 _LIBCPP_INLINE_VISIBILITY 832 pair<iterator, iterator> equal_range(const key_type& __k) 833 {return __table_.__equal_range_unique(__k);} 834 _LIBCPP_INLINE_VISIBILITY 835 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 836 {return __table_.__equal_range_unique(__k);} 837 838 mapped_type& operator[](const key_type& __k); 839#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 840 mapped_type& operator[](key_type&& __k); 841#endif 842 843 mapped_type& at(const key_type& __k); 844 const mapped_type& at(const key_type& __k) const; 845 846 _LIBCPP_INLINE_VISIBILITY 847 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 848 _LIBCPP_INLINE_VISIBILITY 849 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 850 851 _LIBCPP_INLINE_VISIBILITY 852 size_type bucket_size(size_type __n) const 853 {return __table_.bucket_size(__n);} 854 _LIBCPP_INLINE_VISIBILITY 855 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 856 857 _LIBCPP_INLINE_VISIBILITY 858 local_iterator begin(size_type __n) {return __table_.begin(__n);} 859 _LIBCPP_INLINE_VISIBILITY 860 local_iterator end(size_type __n) {return __table_.end(__n);} 861 _LIBCPP_INLINE_VISIBILITY 862 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 863 _LIBCPP_INLINE_VISIBILITY 864 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 865 _LIBCPP_INLINE_VISIBILITY 866 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 867 _LIBCPP_INLINE_VISIBILITY 868 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 869 870 _LIBCPP_INLINE_VISIBILITY 871 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 872 _LIBCPP_INLINE_VISIBILITY 873 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 874 _LIBCPP_INLINE_VISIBILITY 875 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 876 _LIBCPP_INLINE_VISIBILITY 877 void rehash(size_type __n) {__table_.rehash(__n);} 878 _LIBCPP_INLINE_VISIBILITY 879 void reserve(size_type __n) {__table_.reserve(__n);} 880 881private: 882#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 883#ifndef _LIBCPP_HAS_NO_VARIADICS 884 template <class _A0, class... _Args, 885 class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 886 __node_holder __construct_node(_A0&& __a0, _Args&&... __args); 887#endif // _LIBCPP_HAS_NO_VARIADICS 888 template <class _A0, 889 class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 890 __node_holder __construct_node(_A0&& __a0); 891#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 892 __node_holder __construct_node(const key_type& __k); 893#endif 894}; 895 896template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 897unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 898 size_type __n, const hasher& __hf, const key_equal& __eql) 899 : __table_(__hf, __eql) 900{ 901 __table_.rehash(__n); 902} 903 904template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 905unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 906 size_type __n, const hasher& __hf, const key_equal& __eql, 907 const allocator_type& __a) 908 : __table_(__hf, __eql, __a) 909{ 910 __table_.rehash(__n); 911} 912 913template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 914inline _LIBCPP_INLINE_VISIBILITY 915unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 916 const allocator_type& __a) 917 : __table_(__a) 918{ 919} 920 921template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 922template <class _InputIterator> 923unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 924 _InputIterator __first, _InputIterator __last) 925{ 926 insert(__first, __last); 927} 928 929template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 930template <class _InputIterator> 931unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 932 _InputIterator __first, _InputIterator __last, size_type __n, 933 const hasher& __hf, const key_equal& __eql) 934 : __table_(__hf, __eql) 935{ 936 __table_.rehash(__n); 937 insert(__first, __last); 938} 939 940template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 941template <class _InputIterator> 942unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 943 _InputIterator __first, _InputIterator __last, size_type __n, 944 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 945 : __table_(__hf, __eql, __a) 946{ 947 __table_.rehash(__n); 948 insert(__first, __last); 949} 950 951template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 952unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 953 const unordered_map& __u) 954 : __table_(__u.__table_) 955{ 956 __table_.rehash(__u.bucket_count()); 957 insert(__u.begin(), __u.end()); 958} 959 960template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 961unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 962 const unordered_map& __u, const allocator_type& __a) 963 : __table_(__u.__table_, __a) 964{ 965 __table_.rehash(__u.bucket_count()); 966 insert(__u.begin(), __u.end()); 967} 968 969#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 970 971template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 972inline _LIBCPP_INLINE_VISIBILITY 973unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 974 unordered_map&& __u) 975 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 976 : __table_(_VSTD::move(__u.__table_)) 977{ 978} 979 980template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 981unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 982 unordered_map&& __u, const allocator_type& __a) 983 : __table_(_VSTD::move(__u.__table_), __a) 984{ 985 if (__a != __u.get_allocator()) 986 { 987 iterator __i = __u.begin(); 988 while (__u.size() != 0) 989 __table_.__insert_unique( 990 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 991 ); 992 } 993} 994 995#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 996 997#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 998 999template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1000unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1001 initializer_list<value_type> __il) 1002{ 1003 insert(__il.begin(), __il.end()); 1004} 1005 1006template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1007unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1008 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1009 const key_equal& __eql) 1010 : __table_(__hf, __eql) 1011{ 1012 __table_.rehash(__n); 1013 insert(__il.begin(), __il.end()); 1014} 1015 1016template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1017unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1018 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1019 const key_equal& __eql, const allocator_type& __a) 1020 : __table_(__hf, __eql, __a) 1021{ 1022 __table_.rehash(__n); 1023 insert(__il.begin(), __il.end()); 1024} 1025 1026#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1027 1028#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1029 1030template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1031inline _LIBCPP_INLINE_VISIBILITY 1032unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1033unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1034 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1035{ 1036 __table_ = _VSTD::move(__u.__table_); 1037 return *this; 1038} 1039 1040#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1041 1042#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1043 1044template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1045inline _LIBCPP_INLINE_VISIBILITY 1046unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1047unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1048 initializer_list<value_type> __il) 1049{ 1050 __table_.__assign_unique(__il.begin(), __il.end()); 1051 return *this; 1052} 1053 1054#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1055 1056#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1057#ifndef _LIBCPP_HAS_NO_VARIADICS 1058 1059template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1060template <class _A0, class... _Args, 1061 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1062 > 1063typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1064unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1065 _Args&&... __args) 1066{ 1067 __node_allocator& __na = __table_.__node_alloc(); 1068 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na)); 1069 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), 1070 _VSTD::forward<_A0>(__a0)); 1071 __h.get_deleter().__first_constructed = true; 1072 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second), 1073 _VSTD::forward<_Args>(__args)...); 1074 __h.get_deleter().__second_constructed = true; 1075 return __h; 1076} 1077 1078#endif // _LIBCPP_HAS_NO_VARIADICS 1079 1080template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1081template <class _A0, 1082 class // = typename enable_if<is_constructible<value_type, _A0>::value>::type 1083 > 1084typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1085unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1086{ 1087 __node_allocator& __na = __table_.__node_alloc(); 1088 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na)); 1089 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1090 _VSTD::forward<_A0>(__a0)); 1091 __h.get_deleter().__first_constructed = true; 1092 __h.get_deleter().__second_constructed = true; 1093 return __h; 1094} 1095 1096#ifndef _LIBCPP_HAS_NO_VARIADICS 1097 1098template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1099template <class _A0, class... _Args, 1100 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1101 > 1102pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1103unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args) 1104{ 1105 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0), 1106 _VSTD::forward<_Args>(__args)...); 1107 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1108 if (__r.second) 1109 __h.release(); 1110 return __r; 1111} 1112 1113#endif // _LIBCPP_HAS_NO_VARIADICS 1114#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1115 1116template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1117typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1118unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) 1119{ 1120 __node_allocator& __na = __table_.__node_alloc(); 1121 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na)); 1122 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); 1123 __h.get_deleter().__first_constructed = true; 1124 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1125 __h.get_deleter().__second_constructed = true; 1126 return _VSTD::move(__h); 1127} 1128 1129#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1130 1131template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1132template <class _InputIterator> 1133inline _LIBCPP_INLINE_VISIBILITY 1134void 1135unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1136 _InputIterator __last) 1137{ 1138 for (; __first != __last; ++__first) 1139 __table_.__insert_unique(*__first); 1140} 1141 1142template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1143_Tp& 1144unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1145{ 1146 iterator __i = find(__k); 1147 if (__i != end()) 1148 return __i->second; 1149 __node_holder __h = __construct_node(__k); 1150 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1151 __h.release(); 1152 return __r.first->second; 1153} 1154 1155#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1156 1157template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1158_Tp& 1159unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1160{ 1161 iterator __i = find(__k); 1162 if (__i != end()) 1163 return __i->second; 1164 __node_holder __h = __construct_node(_VSTD::move(__k)); 1165 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1166 __h.release(); 1167 return __r.first->second; 1168} 1169 1170#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1171 1172template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1173_Tp& 1174unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1175{ 1176 iterator __i = find(__k); 1177#ifndef _LIBCPP_NO_EXCEPTIONS 1178 if (__i == end()) 1179 throw out_of_range("unordered_map::at: key not found"); 1180#endif // _LIBCPP_NO_EXCEPTIONS 1181 return __i->second; 1182} 1183 1184template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1185const _Tp& 1186unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1187{ 1188 const_iterator __i = find(__k); 1189#ifndef _LIBCPP_NO_EXCEPTIONS 1190 if (__i == end()) 1191 throw out_of_range("unordered_map::at: key not found"); 1192#endif // _LIBCPP_NO_EXCEPTIONS 1193 return __i->second; 1194} 1195 1196template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1197inline _LIBCPP_INLINE_VISIBILITY 1198void 1199swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1200 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1201 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1202{ 1203 __x.swap(__y); 1204} 1205 1206template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1207bool 1208operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1209 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1210{ 1211 if (__x.size() != __y.size()) 1212 return false; 1213 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1214 const_iterator; 1215 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1216 __i != __ex; ++__i) 1217 { 1218 const_iterator __j = __y.find(__i->first); 1219 if (__j == __ey || !(*__i == *__j)) 1220 return false; 1221 } 1222 return true; 1223} 1224 1225template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1226inline _LIBCPP_INLINE_VISIBILITY 1227bool 1228operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1229 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1230{ 1231 return !(__x == __y); 1232} 1233 1234template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1235 class _Alloc = allocator<pair<const _Key, _Tp> > > 1236class _LIBCPP_VISIBLE unordered_multimap 1237{ 1238public: 1239 // types 1240 typedef _Key key_type; 1241 typedef _Tp mapped_type; 1242 typedef _Hash hasher; 1243 typedef _Pred key_equal; 1244 typedef _Alloc allocator_type; 1245 typedef pair<const key_type, mapped_type> value_type; 1246 typedef value_type& reference; 1247 typedef const value_type& const_reference; 1248 1249private: 1250 typedef pair<key_type, mapped_type> __value_type; 1251 typedef __unordered_map_hasher<__value_type, hasher> __hasher; 1252 typedef __unordered_map_equal<__value_type, key_equal> __key_equal; 1253 typedef typename allocator_traits<allocator_type>::template 1254#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1255 rebind_alloc<__value_type> 1256#else 1257 rebind_alloc<__value_type>::other 1258#endif 1259 __allocator_type; 1260 1261 typedef __hash_table<__value_type, __hasher, 1262 __key_equal, __allocator_type> __table; 1263 1264 __table __table_; 1265 1266 typedef typename __table::__node_traits __node_traits; 1267 typedef typename __table::__node_allocator __node_allocator; 1268 typedef typename __table::__node __node; 1269 typedef __hash_map_node_destructor<__node_allocator> _D; 1270 typedef unique_ptr<__node, _D> __node_holder; 1271 typedef allocator_traits<allocator_type> __alloc_traits; 1272public: 1273 typedef typename __alloc_traits::pointer pointer; 1274 typedef typename __alloc_traits::const_pointer const_pointer; 1275 typedef typename __alloc_traits::size_type size_type; 1276 typedef typename __alloc_traits::difference_type difference_type; 1277 1278 typedef __hash_map_iterator<typename __table::iterator> iterator; 1279 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1280 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1281 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1282 1283 _LIBCPP_INLINE_VISIBILITY 1284 unordered_multimap() 1285 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1286 {} // = default; 1287 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1288 const key_equal& __eql = key_equal()); 1289 unordered_multimap(size_type __n, const hasher& __hf, 1290 const key_equal& __eql, 1291 const allocator_type& __a); 1292 template <class _InputIterator> 1293 unordered_multimap(_InputIterator __first, _InputIterator __last); 1294 template <class _InputIterator> 1295 unordered_multimap(_InputIterator __first, _InputIterator __last, 1296 size_type __n, const hasher& __hf = hasher(), 1297 const key_equal& __eql = key_equal()); 1298 template <class _InputIterator> 1299 unordered_multimap(_InputIterator __first, _InputIterator __last, 1300 size_type __n, const hasher& __hf, 1301 const key_equal& __eql, 1302 const allocator_type& __a); 1303 explicit unordered_multimap(const allocator_type& __a); 1304 unordered_multimap(const unordered_multimap& __u); 1305 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1306#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1307 unordered_multimap(unordered_multimap&& __u) 1308 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1309 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1310#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1311#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1312 unordered_multimap(initializer_list<value_type> __il); 1313 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1314 const hasher& __hf = hasher(), 1315 const key_equal& __eql = key_equal()); 1316 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1317 const hasher& __hf, const key_equal& __eql, 1318 const allocator_type& __a); 1319#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1320 // ~unordered_multimap() = default; 1321 _LIBCPP_INLINE_VISIBILITY 1322 unordered_multimap& operator=(const unordered_multimap& __u) 1323 { 1324 __table_ = __u.__table_; 1325 return *this; 1326 } 1327#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1328 unordered_multimap& operator=(unordered_multimap&& __u) 1329 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1330#endif 1331#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1332 unordered_multimap& operator=(initializer_list<value_type> __il); 1333#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1334 1335 _LIBCPP_INLINE_VISIBILITY 1336 allocator_type get_allocator() const _NOEXCEPT 1337 {return allocator_type(__table_.__node_alloc());} 1338 1339 _LIBCPP_INLINE_VISIBILITY 1340 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1341 _LIBCPP_INLINE_VISIBILITY 1342 size_type size() const _NOEXCEPT {return __table_.size();} 1343 _LIBCPP_INLINE_VISIBILITY 1344 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1345 1346 _LIBCPP_INLINE_VISIBILITY 1347 iterator begin() _NOEXCEPT {return __table_.begin();} 1348 _LIBCPP_INLINE_VISIBILITY 1349 iterator end() _NOEXCEPT {return __table_.end();} 1350 _LIBCPP_INLINE_VISIBILITY 1351 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1352 _LIBCPP_INLINE_VISIBILITY 1353 const_iterator end() const _NOEXCEPT {return __table_.end();} 1354 _LIBCPP_INLINE_VISIBILITY 1355 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1356 _LIBCPP_INLINE_VISIBILITY 1357 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1358 1359#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1360 _LIBCPP_INLINE_VISIBILITY 1361 iterator emplace() 1362 {return __table_.__emplace_multi();} 1363 1364 template <class _A0, 1365 class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 1366 _LIBCPP_INLINE_VISIBILITY 1367 iterator emplace(_A0&& __a0) 1368 {return __table_.__emplace_multi(_VSTD::forward<_A0>(__a0));} 1369 1370#ifndef _LIBCPP_HAS_NO_VARIADICS 1371 1372 template <class _A0, class... _Args, 1373 class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 1374 iterator emplace(_A0&& __a0, _Args&&... __args); 1375 1376#endif // _LIBCPP_HAS_NO_VARIADICS 1377 1378 _LIBCPP_INLINE_VISIBILITY 1379 iterator emplace_hint(const_iterator __p) 1380 {return __table_.__emplace_hint_multi(__p.__i_);} 1381 1382 template <class _A0, 1383 class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 1384 _LIBCPP_INLINE_VISIBILITY 1385 iterator emplace_hint(const_iterator __p, _A0&& __a0) 1386 {return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_A0>(__a0));} 1387 1388#ifndef _LIBCPP_HAS_NO_VARIADICS 1389 1390 template <class _A0, class... _Args, 1391 class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 1392 iterator emplace_hint(const_iterator __p, _A0&& __a0, _Args&&... __args); 1393#endif // _LIBCPP_HAS_NO_VARIADICS 1394#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1395 _LIBCPP_INLINE_VISIBILITY 1396 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1397#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1398 template <class _P, 1399 class = typename enable_if<is_constructible<value_type, _P>::value>::type> 1400 _LIBCPP_INLINE_VISIBILITY 1401 iterator insert(_P&& __x) 1402 {return __table_.__insert_multi(_VSTD::forward<_P>(__x));} 1403#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1404 _LIBCPP_INLINE_VISIBILITY 1405 iterator insert(const_iterator __p, const value_type& __x) 1406 {return __table_.__insert_multi(__p.__i_, __x);} 1407#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1408 template <class _P, 1409 class = typename enable_if<is_constructible<value_type, _P>::value>::type> 1410 _LIBCPP_INLINE_VISIBILITY 1411 iterator insert(const_iterator __p, _P&& __x) 1412 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_P>(__x));} 1413#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1414 template <class _InputIterator> 1415 void insert(_InputIterator __first, _InputIterator __last); 1416#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1417 _LIBCPP_INLINE_VISIBILITY 1418 void insert(initializer_list<value_type> __il) 1419 {insert(__il.begin(), __il.end());} 1420#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1421 1422 _LIBCPP_INLINE_VISIBILITY 1423 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1424 _LIBCPP_INLINE_VISIBILITY 1425 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1426 _LIBCPP_INLINE_VISIBILITY 1427 iterator erase(const_iterator __first, const_iterator __last) 1428 {return __table_.erase(__first.__i_, __last.__i_);} 1429 _LIBCPP_INLINE_VISIBILITY 1430 void clear() _NOEXCEPT {__table_.clear();} 1431 1432 _LIBCPP_INLINE_VISIBILITY 1433 void swap(unordered_multimap& __u) 1434 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1435 {__table_.swap(__u.__table_);} 1436 1437 _LIBCPP_INLINE_VISIBILITY 1438 hasher hash_function() const 1439 {return __table_.hash_function().hash_function();} 1440 _LIBCPP_INLINE_VISIBILITY 1441 key_equal key_eq() const 1442 {return __table_.key_eq().key_eq();} 1443 1444 _LIBCPP_INLINE_VISIBILITY 1445 iterator find(const key_type& __k) {return __table_.find(__k);} 1446 _LIBCPP_INLINE_VISIBILITY 1447 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1448 _LIBCPP_INLINE_VISIBILITY 1449 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1450 _LIBCPP_INLINE_VISIBILITY 1451 pair<iterator, iterator> equal_range(const key_type& __k) 1452 {return __table_.__equal_range_multi(__k);} 1453 _LIBCPP_INLINE_VISIBILITY 1454 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1455 {return __table_.__equal_range_multi(__k);} 1456 1457 _LIBCPP_INLINE_VISIBILITY 1458 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1459 _LIBCPP_INLINE_VISIBILITY 1460 size_type max_bucket_count() const _NOEXCEPT 1461 {return __table_.max_bucket_count();} 1462 1463 _LIBCPP_INLINE_VISIBILITY 1464 size_type bucket_size(size_type __n) const 1465 {return __table_.bucket_size(__n);} 1466 _LIBCPP_INLINE_VISIBILITY 1467 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1468 1469 _LIBCPP_INLINE_VISIBILITY 1470 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1471 _LIBCPP_INLINE_VISIBILITY 1472 local_iterator end(size_type __n) {return __table_.end(__n);} 1473 _LIBCPP_INLINE_VISIBILITY 1474 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1475 _LIBCPP_INLINE_VISIBILITY 1476 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1477 _LIBCPP_INLINE_VISIBILITY 1478 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1479 _LIBCPP_INLINE_VISIBILITY 1480 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1481 1482 _LIBCPP_INLINE_VISIBILITY 1483 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1484 _LIBCPP_INLINE_VISIBILITY 1485 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1486 _LIBCPP_INLINE_VISIBILITY 1487 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1488 _LIBCPP_INLINE_VISIBILITY 1489 void rehash(size_type __n) {__table_.rehash(__n);} 1490 _LIBCPP_INLINE_VISIBILITY 1491 void reserve(size_type __n) {__table_.reserve(__n);} 1492 1493private: 1494#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1495 template <class _A0, class... _Args, 1496 class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 1497 __node_holder __construct_node(_A0&& __a0, _Args&&... __args); 1498 template <class _A0, 1499 class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 1500 __node_holder __construct_node(_A0&& __a0); 1501#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1502}; 1503 1504template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1505unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1506 size_type __n, const hasher& __hf, const key_equal& __eql) 1507 : __table_(__hf, __eql) 1508{ 1509 __table_.rehash(__n); 1510} 1511 1512template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1513unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1514 size_type __n, const hasher& __hf, const key_equal& __eql, 1515 const allocator_type& __a) 1516 : __table_(__hf, __eql, __a) 1517{ 1518 __table_.rehash(__n); 1519} 1520 1521template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1522template <class _InputIterator> 1523unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1524 _InputIterator __first, _InputIterator __last) 1525{ 1526 insert(__first, __last); 1527} 1528 1529template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1530template <class _InputIterator> 1531unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1532 _InputIterator __first, _InputIterator __last, size_type __n, 1533 const hasher& __hf, const key_equal& __eql) 1534 : __table_(__hf, __eql) 1535{ 1536 __table_.rehash(__n); 1537 insert(__first, __last); 1538} 1539 1540template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1541template <class _InputIterator> 1542unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1543 _InputIterator __first, _InputIterator __last, size_type __n, 1544 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1545 : __table_(__hf, __eql, __a) 1546{ 1547 __table_.rehash(__n); 1548 insert(__first, __last); 1549} 1550 1551template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1552inline _LIBCPP_INLINE_VISIBILITY 1553unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1554 const allocator_type& __a) 1555 : __table_(__a) 1556{ 1557} 1558 1559template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1560unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1561 const unordered_multimap& __u) 1562 : __table_(__u.__table_) 1563{ 1564 __table_.rehash(__u.bucket_count()); 1565 insert(__u.begin(), __u.end()); 1566} 1567 1568template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1569unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1570 const unordered_multimap& __u, const allocator_type& __a) 1571 : __table_(__u.__table_, __a) 1572{ 1573 __table_.rehash(__u.bucket_count()); 1574 insert(__u.begin(), __u.end()); 1575} 1576 1577#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1578 1579template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1580inline _LIBCPP_INLINE_VISIBILITY 1581unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1582 unordered_multimap&& __u) 1583 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1584 : __table_(_VSTD::move(__u.__table_)) 1585{ 1586} 1587 1588template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1589unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1590 unordered_multimap&& __u, const allocator_type& __a) 1591 : __table_(_VSTD::move(__u.__table_), __a) 1592{ 1593 if (__a != __u.get_allocator()) 1594 { 1595 iterator __i = __u.begin(); 1596 while (__u.size() != 0) 1597{ 1598 __table_.__insert_multi( 1599 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1600 ); 1601} 1602 } 1603} 1604 1605#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1606 1607#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1608 1609template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1610unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1611 initializer_list<value_type> __il) 1612{ 1613 insert(__il.begin(), __il.end()); 1614} 1615 1616template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1617unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1618 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1619 const key_equal& __eql) 1620 : __table_(__hf, __eql) 1621{ 1622 __table_.rehash(__n); 1623 insert(__il.begin(), __il.end()); 1624} 1625 1626template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1627unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1628 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1629 const key_equal& __eql, const allocator_type& __a) 1630 : __table_(__hf, __eql, __a) 1631{ 1632 __table_.rehash(__n); 1633 insert(__il.begin(), __il.end()); 1634} 1635 1636#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1637 1638#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1639 1640template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1641inline _LIBCPP_INLINE_VISIBILITY 1642unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1643unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1644 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1645{ 1646 __table_ = _VSTD::move(__u.__table_); 1647 return *this; 1648} 1649 1650#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1651 1652#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1653 1654template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1655inline _LIBCPP_INLINE_VISIBILITY 1656unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1657unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1658 initializer_list<value_type> __il) 1659{ 1660 __table_.__assign_multi(__il.begin(), __il.end()); 1661 return *this; 1662} 1663 1664#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1665 1666#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1667#ifndef _LIBCPP_HAS_NO_VARIADICS 1668 1669template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1670template <class _A0, class... _Args, 1671 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1672 > 1673typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1674unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 1675 _A0&& __a0, _Args&&... __args) 1676{ 1677 __node_allocator& __na = __table_.__node_alloc(); 1678 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na)); 1679 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), 1680 _VSTD::forward<_A0>(__a0)); 1681 __h.get_deleter().__first_constructed = true; 1682 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second), 1683 _VSTD::forward<_Args>(__args)...); 1684 __h.get_deleter().__second_constructed = true; 1685 return __h; 1686} 1687 1688#endif // _LIBCPP_HAS_NO_VARIADICS 1689 1690template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1691template <class _A0, 1692 class // = typename enable_if<is_constructible<value_type, _A0>::value>::type 1693 > 1694typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1695unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1696{ 1697 __node_allocator& __na = __table_.__node_alloc(); 1698 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na)); 1699 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1700 _VSTD::forward<_A0>(__a0)); 1701 __h.get_deleter().__first_constructed = true; 1702 __h.get_deleter().__second_constructed = true; 1703 return __h; 1704} 1705 1706#ifndef _LIBCPP_HAS_NO_VARIADICS 1707 1708template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1709template <class _A0, class... _Args, 1710 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1711 > 1712typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1713unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args) 1714{ 1715 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0), 1716 _VSTD::forward<_Args>(__args)...); 1717 iterator __r = __table_.__node_insert_multi(__h.get()); 1718 __h.release(); 1719 return __r; 1720} 1721 1722template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1723template <class _A0, class... _Args, 1724 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1725 > 1726typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1727unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 1728 const_iterator __p, _A0&& __a0, _Args&&... __args) 1729{ 1730 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0), 1731 _VSTD::forward<_Args>(__args)...); 1732 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 1733 __h.release(); 1734 return __r; 1735} 1736 1737#endif // _LIBCPP_HAS_NO_VARIADICS 1738#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1739 1740template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1741template <class _InputIterator> 1742inline _LIBCPP_INLINE_VISIBILITY 1743void 1744unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1745 _InputIterator __last) 1746{ 1747 for (; __first != __last; ++__first) 1748 __table_.__insert_multi(*__first); 1749} 1750 1751template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1752inline _LIBCPP_INLINE_VISIBILITY 1753void 1754swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1755 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1756 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1757{ 1758 __x.swap(__y); 1759} 1760 1761template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1762bool 1763operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1764 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1765{ 1766 if (__x.size() != __y.size()) 1767 return false; 1768 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1769 const_iterator; 1770 typedef pair<const_iterator, const_iterator> _EqRng; 1771 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1772 { 1773 _EqRng __xeq = __x.equal_range(__i->first); 1774 _EqRng __yeq = __y.equal_range(__i->first); 1775 if (_VSTD::distance(__xeq.first, __xeq.second) != 1776 _VSTD::distance(__yeq.first, __yeq.second) || 1777 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1778 return false; 1779 __i = __xeq.second; 1780 } 1781 return true; 1782} 1783 1784template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1785inline _LIBCPP_INLINE_VISIBILITY 1786bool 1787operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1788 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1789{ 1790 return !(__x == __y); 1791} 1792 1793_LIBCPP_END_NAMESPACE_STD 1794 1795#endif // _LIBCPP_UNORDERED_MAP 1796