1 // -*- C++ -*- 2 //===-------------------------- unordered_map -----------------------------===// 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is dual licensed under the MIT and the University of Illinois Open 7 // Source Licenses. See LICENSE.TXT for details. 8 // 9 //===----------------------------------------------------------------------===// 10 11 #ifndef _LIBCPP_UNORDERED_MAP 12 #define _LIBCPP_UNORDERED_MAP 13 14 /* 15 16 unordered_map synopsis 17 18 #include <initializer_list> 19 20 namespace std 21 { 22 23 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 24 class Alloc = allocator<pair<const Key, T>>> 25 class unordered_map 26 { 27 public: 28 // types 29 typedef Key key_type; 30 typedef T mapped_type; 31 typedef Hash hasher; 32 typedef Pred key_equal; 33 typedef Alloc allocator_type; 34 typedef pair<const key_type, mapped_type> value_type; 35 typedef value_type& reference; 36 typedef const value_type& const_reference; 37 typedef typename allocator_traits<allocator_type>::pointer pointer; 38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 39 typedef typename allocator_traits<allocator_type>::size_type size_type; 40 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 41 42 typedef /unspecified/ iterator; 43 typedef /unspecified/ const_iterator; 44 typedef /unspecified/ local_iterator; 45 typedef /unspecified/ const_local_iterator; 46 47 unordered_map() 48 noexcept( 49 is_nothrow_default_constructible<hasher>::value && 50 is_nothrow_default_constructible<key_equal>::value && 51 is_nothrow_default_constructible<allocator_type>::value); 52 explicit unordered_map(size_type n, const hasher& hf = hasher(), 53 const key_equal& eql = key_equal(), 54 const allocator_type& a = allocator_type()); 55 template <class InputIterator> 56 unordered_map(InputIterator f, InputIterator l, 57 size_type n = 0, const hasher& hf = hasher(), 58 const key_equal& eql = key_equal(), 59 const allocator_type& a = allocator_type()); 60 explicit unordered_map(const allocator_type&); 61 unordered_map(const unordered_map&); 62 unordered_map(const unordered_map&, const Allocator&); 63 unordered_map(unordered_map&&) 64 noexcept( 65 is_nothrow_move_constructible<hasher>::value && 66 is_nothrow_move_constructible<key_equal>::value && 67 is_nothrow_move_constructible<allocator_type>::value); 68 unordered_map(unordered_map&&, const Allocator&); 69 unordered_map(initializer_list<value_type>, size_type n = 0, 70 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 71 const allocator_type& a = allocator_type()); 72 ~unordered_map(); 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 156 template <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 161 template <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 166 template <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 171 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 172 class Alloc = allocator<pair<const Key, T>>> 173 class unordered_multimap 174 { 175 public: 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 298 template <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 303 template <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 308 template <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 328 template <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value 329 #if __has_feature(is_final) 330 && !__is_final(_Hash) 331 #endif 332 > 333 class __unordered_map_hasher 334 : private _Hash 335 { 336 public: 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 355 template <class _Key, class _Cp, class _Hash> 356 class __unordered_map_hasher<_Key, _Cp, _Hash, false> 357 { 358 _Hash __hash_; 359 360 public: 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 379 template <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value 380 #if __has_feature(is_final) 381 && !__is_final(_Pred) 382 #endif 383 > 384 class __unordered_map_equal 385 : private _Pred 386 { 387 public: 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 409 template <class _Key, class _Cp, class _Pred> 410 class __unordered_map_equal<_Key, _Cp, _Pred, false> 411 { 412 _Pred __pred_; 413 414 public: 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 436 template <class _Alloc> 437 class __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; 442 public: 443 typedef typename __alloc_traits::pointer pointer; 444 private: 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 452 public: 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 496 template <class _HashIterator> 497 class _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; 504 public: 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 552 template <class _HashIterator> 553 class _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; 560 public: 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 612 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 613 class _Alloc = allocator<pair<const _Key, _Tp> > > 614 class _LIBCPP_TYPE_VIS unordered_map 615 { 616 public: 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 628 private: 629 #if __cplusplus >= 201103L 630 union __value_type 631 { 632 typedef typename unordered_map::value_type value_type; 633 typedef typename unordered_map::__nc_value_type __nc_value_type; 634 value_type __cc; 635 __nc_value_type __nc; 636 637 template <class ..._Args> 638 __value_type(_Args&& ...__args) 639 : __cc(std::forward<_Args>(__args)...) {} 640 641 __value_type(const __value_type& __v) 642 : __cc(std::move(__v.__cc)) {} 643 644 __value_type(__value_type&& __v) 645 : __nc(std::move(__v.__nc)) {} 646 647 __value_type& operator=(const __value_type& __v) 648 {__nc = __v.__cc; return *this;} 649 650 __value_type& operator=(__value_type&& __v) 651 {__nc = std::move(__v.__nc); return *this;} 652 653 ~__value_type() {__cc.~value_type();} 654 }; 655 #else 656 struct __value_type 657 { 658 typedef typename unordered_map::value_type value_type; 659 value_type __cc; 660 661 __value_type() {} 662 663 template <class _A0> 664 __value_type(const _A0& __a0) 665 : __cc(__a0) {} 666 667 template <class _A0, class _A1> 668 __value_type(const _A0& __a0, const _A1& __a1) 669 : __cc(__a0, __a1) {} 670 }; 671 #endif 672 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 673 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 674 typedef typename allocator_traits<allocator_type>::template 675 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 676 rebind_alloc<__value_type> 677 #else 678 rebind_alloc<__value_type>::other 679 #endif 680 __allocator_type; 681 682 typedef __hash_table<__value_type, __hasher, 683 __key_equal, __allocator_type> __table; 684 685 __table __table_; 686 687 typedef typename __table::__node_pointer __node_pointer; 688 typedef typename __table::__node_const_pointer __node_const_pointer; 689 typedef typename __table::__node_traits __node_traits; 690 typedef typename __table::__node_allocator __node_allocator; 691 typedef typename __table::__node __node; 692 typedef __hash_map_node_destructor<__node_allocator> _Dp; 693 typedef unique_ptr<__node, _Dp> __node_holder; 694 typedef allocator_traits<allocator_type> __alloc_traits; 695 public: 696 typedef typename __alloc_traits::pointer pointer; 697 typedef typename __alloc_traits::const_pointer const_pointer; 698 typedef typename __alloc_traits::size_type size_type; 699 typedef typename __alloc_traits::difference_type difference_type; 700 701 typedef __hash_map_iterator<typename __table::iterator> iterator; 702 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 703 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 704 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 705 706 _LIBCPP_INLINE_VISIBILITY 707 unordered_map() 708 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 709 {} // = default; 710 explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 711 const key_equal& __eql = key_equal()); 712 unordered_map(size_type __n, const hasher& __hf, 713 const key_equal& __eql, 714 const allocator_type& __a); 715 template <class _InputIterator> 716 unordered_map(_InputIterator __first, _InputIterator __last); 717 template <class _InputIterator> 718 unordered_map(_InputIterator __first, _InputIterator __last, 719 size_type __n, const hasher& __hf = hasher(), 720 const key_equal& __eql = key_equal()); 721 template <class _InputIterator> 722 unordered_map(_InputIterator __first, _InputIterator __last, 723 size_type __n, const hasher& __hf, 724 const key_equal& __eql, 725 const allocator_type& __a); 726 explicit unordered_map(const allocator_type& __a); 727 unordered_map(const unordered_map& __u); 728 unordered_map(const unordered_map& __u, const allocator_type& __a); 729 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 730 unordered_map(unordered_map&& __u) 731 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 732 unordered_map(unordered_map&& __u, const allocator_type& __a); 733 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 734 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 735 unordered_map(initializer_list<value_type> __il); 736 unordered_map(initializer_list<value_type> __il, size_type __n, 737 const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 738 unordered_map(initializer_list<value_type> __il, size_type __n, 739 const hasher& __hf, const key_equal& __eql, 740 const allocator_type& __a); 741 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 742 // ~unordered_map() = default; 743 _LIBCPP_INLINE_VISIBILITY 744 unordered_map& operator=(const unordered_map& __u) 745 { 746 #if __cplusplus >= 201103L 747 __table_ = __u.__table_; 748 #else 749 __table_.clear(); 750 __table_.hash_function() = __u.__table_.hash_function(); 751 __table_.key_eq() = __u.__table_.key_eq(); 752 __table_.max_load_factor() = __u.__table_.max_load_factor(); 753 __table_.__copy_assign_alloc(__u.__table_); 754 insert(__u.begin(), __u.end()); 755 #endif 756 return *this; 757 } 758 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 759 unordered_map& operator=(unordered_map&& __u) 760 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 761 #endif 762 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 763 unordered_map& operator=(initializer_list<value_type> __il); 764 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 765 766 _LIBCPP_INLINE_VISIBILITY 767 allocator_type get_allocator() const _NOEXCEPT 768 {return allocator_type(__table_.__node_alloc());} 769 770 _LIBCPP_INLINE_VISIBILITY 771 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 772 _LIBCPP_INLINE_VISIBILITY 773 size_type size() const _NOEXCEPT {return __table_.size();} 774 _LIBCPP_INLINE_VISIBILITY 775 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 776 777 _LIBCPP_INLINE_VISIBILITY 778 iterator begin() _NOEXCEPT {return __table_.begin();} 779 _LIBCPP_INLINE_VISIBILITY 780 iterator end() _NOEXCEPT {return __table_.end();} 781 _LIBCPP_INLINE_VISIBILITY 782 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 783 _LIBCPP_INLINE_VISIBILITY 784 const_iterator end() const _NOEXCEPT {return __table_.end();} 785 _LIBCPP_INLINE_VISIBILITY 786 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 787 _LIBCPP_INLINE_VISIBILITY 788 const_iterator cend() const _NOEXCEPT {return __table_.end();} 789 790 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 791 #ifndef _LIBCPP_HAS_NO_VARIADICS 792 793 template <class... _Args> 794 pair<iterator, bool> emplace(_Args&&... __args); 795 796 template <class... _Args> 797 _LIBCPP_INLINE_VISIBILITY 798 iterator emplace_hint(const_iterator, _Args&&... __args) 799 {return emplace(_VSTD::forward<_Args>(__args)...).first;} 800 #endif // _LIBCPP_HAS_NO_VARIADICS 801 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 802 _LIBCPP_INLINE_VISIBILITY 803 pair<iterator, bool> insert(const value_type& __x) 804 {return __table_.__insert_unique(__x);} 805 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 806 template <class _Pp, 807 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 808 _LIBCPP_INLINE_VISIBILITY 809 pair<iterator, bool> insert(_Pp&& __x) 810 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 811 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 812 _LIBCPP_INLINE_VISIBILITY 813 iterator insert(const_iterator, const value_type& __x) 814 {return insert(__x).first;} 815 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 816 template <class _Pp, 817 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 818 _LIBCPP_INLINE_VISIBILITY 819 iterator insert(const_iterator, _Pp&& __x) 820 {return insert(_VSTD::forward<_Pp>(__x)).first;} 821 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 822 template <class _InputIterator> 823 void insert(_InputIterator __first, _InputIterator __last); 824 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 825 _LIBCPP_INLINE_VISIBILITY 826 void insert(initializer_list<value_type> __il) 827 {insert(__il.begin(), __il.end());} 828 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 829 830 _LIBCPP_INLINE_VISIBILITY 831 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 832 _LIBCPP_INLINE_VISIBILITY 833 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 834 _LIBCPP_INLINE_VISIBILITY 835 iterator erase(const_iterator __first, const_iterator __last) 836 {return __table_.erase(__first.__i_, __last.__i_);} 837 _LIBCPP_INLINE_VISIBILITY 838 void clear() _NOEXCEPT {__table_.clear();} 839 840 _LIBCPP_INLINE_VISIBILITY 841 void swap(unordered_map& __u) 842 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 843 {__table_.swap(__u.__table_);} 844 845 _LIBCPP_INLINE_VISIBILITY 846 hasher hash_function() const 847 {return __table_.hash_function().hash_function();} 848 _LIBCPP_INLINE_VISIBILITY 849 key_equal key_eq() const 850 {return __table_.key_eq().key_eq();} 851 852 _LIBCPP_INLINE_VISIBILITY 853 iterator find(const key_type& __k) {return __table_.find(__k);} 854 _LIBCPP_INLINE_VISIBILITY 855 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 856 _LIBCPP_INLINE_VISIBILITY 857 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 858 _LIBCPP_INLINE_VISIBILITY 859 pair<iterator, iterator> equal_range(const key_type& __k) 860 {return __table_.__equal_range_unique(__k);} 861 _LIBCPP_INLINE_VISIBILITY 862 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 863 {return __table_.__equal_range_unique(__k);} 864 865 mapped_type& operator[](const key_type& __k); 866 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 867 mapped_type& operator[](key_type&& __k); 868 #endif 869 870 mapped_type& at(const key_type& __k); 871 const mapped_type& at(const key_type& __k) const; 872 873 _LIBCPP_INLINE_VISIBILITY 874 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 875 _LIBCPP_INLINE_VISIBILITY 876 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 877 878 _LIBCPP_INLINE_VISIBILITY 879 size_type bucket_size(size_type __n) const 880 {return __table_.bucket_size(__n);} 881 _LIBCPP_INLINE_VISIBILITY 882 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 883 884 _LIBCPP_INLINE_VISIBILITY 885 local_iterator begin(size_type __n) {return __table_.begin(__n);} 886 _LIBCPP_INLINE_VISIBILITY 887 local_iterator end(size_type __n) {return __table_.end(__n);} 888 _LIBCPP_INLINE_VISIBILITY 889 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 890 _LIBCPP_INLINE_VISIBILITY 891 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 892 _LIBCPP_INLINE_VISIBILITY 893 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 894 _LIBCPP_INLINE_VISIBILITY 895 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 896 897 _LIBCPP_INLINE_VISIBILITY 898 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 899 _LIBCPP_INLINE_VISIBILITY 900 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 901 _LIBCPP_INLINE_VISIBILITY 902 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 903 _LIBCPP_INLINE_VISIBILITY 904 void rehash(size_type __n) {__table_.rehash(__n);} 905 _LIBCPP_INLINE_VISIBILITY 906 void reserve(size_type __n) {__table_.reserve(__n);} 907 908 private: 909 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 910 __node_holder __construct_node(); 911 template <class _A0> 912 __node_holder 913 __construct_node(_A0&& __a0); 914 __node_holder __construct_node_with_key(key_type&& __k); 915 #ifndef _LIBCPP_HAS_NO_VARIADICS 916 template <class _A0, class _A1, class ..._Args> 917 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 918 #endif // _LIBCPP_HAS_NO_VARIADICS 919 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 920 __node_holder __construct_node_with_key(const key_type& __k); 921 }; 922 923 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 924 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 925 size_type __n, const hasher& __hf, const key_equal& __eql) 926 : __table_(__hf, __eql) 927 { 928 __table_.rehash(__n); 929 } 930 931 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 932 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 933 size_type __n, const hasher& __hf, const key_equal& __eql, 934 const allocator_type& __a) 935 : __table_(__hf, __eql, __a) 936 { 937 __table_.rehash(__n); 938 } 939 940 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 941 inline _LIBCPP_INLINE_VISIBILITY 942 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 943 const allocator_type& __a) 944 : __table_(__a) 945 { 946 } 947 948 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 949 template <class _InputIterator> 950 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 951 _InputIterator __first, _InputIterator __last) 952 { 953 insert(__first, __last); 954 } 955 956 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 957 template <class _InputIterator> 958 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 959 _InputIterator __first, _InputIterator __last, size_type __n, 960 const hasher& __hf, const key_equal& __eql) 961 : __table_(__hf, __eql) 962 { 963 __table_.rehash(__n); 964 insert(__first, __last); 965 } 966 967 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 968 template <class _InputIterator> 969 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 970 _InputIterator __first, _InputIterator __last, size_type __n, 971 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 972 : __table_(__hf, __eql, __a) 973 { 974 __table_.rehash(__n); 975 insert(__first, __last); 976 } 977 978 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 979 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 980 const unordered_map& __u) 981 : __table_(__u.__table_) 982 { 983 __table_.rehash(__u.bucket_count()); 984 insert(__u.begin(), __u.end()); 985 } 986 987 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 988 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 989 const unordered_map& __u, const allocator_type& __a) 990 : __table_(__u.__table_, __a) 991 { 992 __table_.rehash(__u.bucket_count()); 993 insert(__u.begin(), __u.end()); 994 } 995 996 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 997 998 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 999 inline _LIBCPP_INLINE_VISIBILITY 1000 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1001 unordered_map&& __u) 1002 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1003 : __table_(_VSTD::move(__u.__table_)) 1004 { 1005 } 1006 1007 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1008 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1009 unordered_map&& __u, const allocator_type& __a) 1010 : __table_(_VSTD::move(__u.__table_), __a) 1011 { 1012 if (__a != __u.get_allocator()) 1013 { 1014 iterator __i = __u.begin(); 1015 while (__u.size() != 0) 1016 __table_.__insert_unique( 1017 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1018 ); 1019 } 1020 } 1021 1022 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1023 1024 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1025 1026 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1027 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1028 initializer_list<value_type> __il) 1029 { 1030 insert(__il.begin(), __il.end()); 1031 } 1032 1033 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1034 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1035 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1036 const key_equal& __eql) 1037 : __table_(__hf, __eql) 1038 { 1039 __table_.rehash(__n); 1040 insert(__il.begin(), __il.end()); 1041 } 1042 1043 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1044 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1045 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1046 const key_equal& __eql, const allocator_type& __a) 1047 : __table_(__hf, __eql, __a) 1048 { 1049 __table_.rehash(__n); 1050 insert(__il.begin(), __il.end()); 1051 } 1052 1053 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1054 1055 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1056 1057 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1058 inline _LIBCPP_INLINE_VISIBILITY 1059 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1060 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1061 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1062 { 1063 __table_ = _VSTD::move(__u.__table_); 1064 return *this; 1065 } 1066 1067 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1068 1069 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1070 1071 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1072 inline _LIBCPP_INLINE_VISIBILITY 1073 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1074 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1075 initializer_list<value_type> __il) 1076 { 1077 __table_.__assign_unique(__il.begin(), __il.end()); 1078 return *this; 1079 } 1080 1081 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1082 1083 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1084 1085 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1086 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1087 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1088 { 1089 __node_allocator& __na = __table_.__node_alloc(); 1090 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1091 __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1092 __h.get_deleter().__first_constructed = true; 1093 __h.get_deleter().__second_constructed = true; 1094 return __h; 1095 } 1096 1097 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1098 template <class _A0> 1099 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1100 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1101 { 1102 __node_allocator& __na = __table_.__node_alloc(); 1103 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1104 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1105 _VSTD::forward<_A0>(__a0)); 1106 __h.get_deleter().__first_constructed = true; 1107 __h.get_deleter().__second_constructed = true; 1108 return __h; 1109 } 1110 1111 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1112 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1113 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k) 1114 { 1115 __node_allocator& __na = __table_.__node_alloc(); 1116 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1117 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k)); 1118 __h.get_deleter().__first_constructed = true; 1119 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1120 __h.get_deleter().__second_constructed = true; 1121 return _VSTD::move(__h); 1122 } 1123 1124 #ifndef _LIBCPP_HAS_NO_VARIADICS 1125 1126 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1127 template <class _A0, class _A1, class ..._Args> 1128 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1129 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1130 _A1&& __a1, 1131 _Args&&... __args) 1132 { 1133 __node_allocator& __na = __table_.__node_alloc(); 1134 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1135 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1136 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1137 _VSTD::forward<_Args>(__args)...); 1138 __h.get_deleter().__first_constructed = true; 1139 __h.get_deleter().__second_constructed = true; 1140 return __h; 1141 } 1142 1143 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1144 template <class... _Args> 1145 pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1146 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1147 { 1148 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1149 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1150 if (__r.second) 1151 __h.release(); 1152 return __r; 1153 } 1154 1155 #endif // _LIBCPP_HAS_NO_VARIADICS 1156 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1157 1158 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1159 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1160 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1161 { 1162 __node_allocator& __na = __table_.__node_alloc(); 1163 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1164 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1165 __h.get_deleter().__first_constructed = true; 1166 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1167 __h.get_deleter().__second_constructed = true; 1168 return _VSTD::move(__h); 1169 } 1170 1171 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1172 template <class _InputIterator> 1173 inline _LIBCPP_INLINE_VISIBILITY 1174 void 1175 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1176 _InputIterator __last) 1177 { 1178 for (; __first != __last; ++__first) 1179 __table_.__insert_unique(*__first); 1180 } 1181 1182 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1183 _Tp& 1184 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1185 { 1186 iterator __i = find(__k); 1187 if (__i != end()) 1188 return __i->second; 1189 __node_holder __h = __construct_node_with_key(__k); 1190 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1191 __h.release(); 1192 return __r.first->second; 1193 } 1194 1195 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1196 1197 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1198 _Tp& 1199 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1200 { 1201 iterator __i = find(__k); 1202 if (__i != end()) 1203 return __i->second; 1204 __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); 1205 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1206 __h.release(); 1207 return __r.first->second; 1208 } 1209 1210 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1211 1212 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1213 _Tp& 1214 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1215 { 1216 iterator __i = find(__k); 1217 #ifndef _LIBCPP_NO_EXCEPTIONS 1218 if (__i == end()) 1219 throw out_of_range("unordered_map::at: key not found"); 1220 #endif // _LIBCPP_NO_EXCEPTIONS 1221 return __i->second; 1222 } 1223 1224 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1225 const _Tp& 1226 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1227 { 1228 const_iterator __i = find(__k); 1229 #ifndef _LIBCPP_NO_EXCEPTIONS 1230 if (__i == end()) 1231 throw out_of_range("unordered_map::at: key not found"); 1232 #endif // _LIBCPP_NO_EXCEPTIONS 1233 return __i->second; 1234 } 1235 1236 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1237 inline _LIBCPP_INLINE_VISIBILITY 1238 void 1239 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1240 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1241 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1242 { 1243 __x.swap(__y); 1244 } 1245 1246 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1247 bool 1248 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1249 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1250 { 1251 if (__x.size() != __y.size()) 1252 return false; 1253 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1254 const_iterator; 1255 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1256 __i != __ex; ++__i) 1257 { 1258 const_iterator __j = __y.find(__i->first); 1259 if (__j == __ey || !(*__i == *__j)) 1260 return false; 1261 } 1262 return true; 1263 } 1264 1265 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1266 inline _LIBCPP_INLINE_VISIBILITY 1267 bool 1268 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1269 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1270 { 1271 return !(__x == __y); 1272 } 1273 1274 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1275 class _Alloc = allocator<pair<const _Key, _Tp> > > 1276 class _LIBCPP_TYPE_VIS unordered_multimap 1277 { 1278 public: 1279 // types 1280 typedef _Key key_type; 1281 typedef _Tp mapped_type; 1282 typedef _Hash hasher; 1283 typedef _Pred key_equal; 1284 typedef _Alloc allocator_type; 1285 typedef pair<const key_type, mapped_type> value_type; 1286 typedef pair<key_type, mapped_type> __nc_value_type; 1287 typedef value_type& reference; 1288 typedef const value_type& const_reference; 1289 1290 private: 1291 #if __cplusplus >= 201103L 1292 union __value_type 1293 { 1294 typedef typename unordered_multimap::value_type value_type; 1295 typedef typename unordered_multimap::__nc_value_type __nc_value_type; 1296 value_type __cc; 1297 __nc_value_type __nc; 1298 1299 template <class ..._Args> 1300 __value_type(_Args&& ...__args) 1301 : __cc(std::forward<_Args>(__args)...) {} 1302 1303 __value_type(const __value_type& __v) 1304 : __cc(std::move(__v.__cc)) {} 1305 1306 __value_type(__value_type&& __v) 1307 : __nc(std::move(__v.__nc)) {} 1308 1309 __value_type& operator=(const __value_type& __v) 1310 {__nc = __v.__cc; return *this;} 1311 1312 __value_type& operator=(__value_type&& __v) 1313 {__nc = std::move(__v.__nc); return *this;} 1314 1315 ~__value_type() {__cc.~value_type();} 1316 }; 1317 #else 1318 struct __value_type 1319 { 1320 typedef typename unordered_multimap::value_type value_type; 1321 value_type __cc; 1322 1323 __value_type() {} 1324 1325 template <class _A0> 1326 __value_type(const _A0& __a0) 1327 : __cc(__a0) {} 1328 1329 template <class _A0, class _A1> 1330 __value_type(const _A0& __a0, const _A1& __a1) 1331 : __cc(__a0, __a1) {} 1332 }; 1333 #endif 1334 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 1335 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 1336 typedef typename allocator_traits<allocator_type>::template 1337 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1338 rebind_alloc<__value_type> 1339 #else 1340 rebind_alloc<__value_type>::other 1341 #endif 1342 __allocator_type; 1343 1344 typedef __hash_table<__value_type, __hasher, 1345 __key_equal, __allocator_type> __table; 1346 1347 __table __table_; 1348 1349 typedef typename __table::__node_traits __node_traits; 1350 typedef typename __table::__node_allocator __node_allocator; 1351 typedef typename __table::__node __node; 1352 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1353 typedef unique_ptr<__node, _Dp> __node_holder; 1354 typedef allocator_traits<allocator_type> __alloc_traits; 1355 public: 1356 typedef typename __alloc_traits::pointer pointer; 1357 typedef typename __alloc_traits::const_pointer const_pointer; 1358 typedef typename __alloc_traits::size_type size_type; 1359 typedef typename __alloc_traits::difference_type difference_type; 1360 1361 typedef __hash_map_iterator<typename __table::iterator> iterator; 1362 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1363 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1364 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1365 1366 _LIBCPP_INLINE_VISIBILITY 1367 unordered_multimap() 1368 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1369 {} // = default; 1370 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1371 const key_equal& __eql = key_equal()); 1372 unordered_multimap(size_type __n, const hasher& __hf, 1373 const key_equal& __eql, 1374 const allocator_type& __a); 1375 template <class _InputIterator> 1376 unordered_multimap(_InputIterator __first, _InputIterator __last); 1377 template <class _InputIterator> 1378 unordered_multimap(_InputIterator __first, _InputIterator __last, 1379 size_type __n, const hasher& __hf = hasher(), 1380 const key_equal& __eql = key_equal()); 1381 template <class _InputIterator> 1382 unordered_multimap(_InputIterator __first, _InputIterator __last, 1383 size_type __n, const hasher& __hf, 1384 const key_equal& __eql, 1385 const allocator_type& __a); 1386 explicit unordered_multimap(const allocator_type& __a); 1387 unordered_multimap(const unordered_multimap& __u); 1388 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1389 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1390 unordered_multimap(unordered_multimap&& __u) 1391 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1392 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1393 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1394 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1395 unordered_multimap(initializer_list<value_type> __il); 1396 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1397 const hasher& __hf = hasher(), 1398 const key_equal& __eql = key_equal()); 1399 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1400 const hasher& __hf, const key_equal& __eql, 1401 const allocator_type& __a); 1402 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1403 // ~unordered_multimap() = default; 1404 _LIBCPP_INLINE_VISIBILITY 1405 unordered_multimap& operator=(const unordered_multimap& __u) 1406 { 1407 #if __cplusplus >= 201103L 1408 __table_ = __u.__table_; 1409 #else 1410 __table_.clear(); 1411 __table_.hash_function() = __u.__table_.hash_function(); 1412 __table_.key_eq() = __u.__table_.key_eq(); 1413 __table_.max_load_factor() = __u.__table_.max_load_factor(); 1414 __table_.__copy_assign_alloc(__u.__table_); 1415 insert(__u.begin(), __u.end()); 1416 #endif 1417 return *this; 1418 } 1419 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1420 unordered_multimap& operator=(unordered_multimap&& __u) 1421 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1422 #endif 1423 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1424 unordered_multimap& operator=(initializer_list<value_type> __il); 1425 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1426 1427 _LIBCPP_INLINE_VISIBILITY 1428 allocator_type get_allocator() const _NOEXCEPT 1429 {return allocator_type(__table_.__node_alloc());} 1430 1431 _LIBCPP_INLINE_VISIBILITY 1432 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1433 _LIBCPP_INLINE_VISIBILITY 1434 size_type size() const _NOEXCEPT {return __table_.size();} 1435 _LIBCPP_INLINE_VISIBILITY 1436 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1437 1438 _LIBCPP_INLINE_VISIBILITY 1439 iterator begin() _NOEXCEPT {return __table_.begin();} 1440 _LIBCPP_INLINE_VISIBILITY 1441 iterator end() _NOEXCEPT {return __table_.end();} 1442 _LIBCPP_INLINE_VISIBILITY 1443 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1444 _LIBCPP_INLINE_VISIBILITY 1445 const_iterator end() const _NOEXCEPT {return __table_.end();} 1446 _LIBCPP_INLINE_VISIBILITY 1447 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1448 _LIBCPP_INLINE_VISIBILITY 1449 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1450 1451 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1452 #ifndef _LIBCPP_HAS_NO_VARIADICS 1453 1454 template <class... _Args> 1455 iterator emplace(_Args&&... __args); 1456 1457 template <class... _Args> 1458 iterator emplace_hint(const_iterator __p, _Args&&... __args); 1459 #endif // _LIBCPP_HAS_NO_VARIADICS 1460 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1461 _LIBCPP_INLINE_VISIBILITY 1462 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1463 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1464 template <class _Pp, 1465 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1466 _LIBCPP_INLINE_VISIBILITY 1467 iterator insert(_Pp&& __x) 1468 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1469 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1470 _LIBCPP_INLINE_VISIBILITY 1471 iterator insert(const_iterator __p, const value_type& __x) 1472 {return __table_.__insert_multi(__p.__i_, __x);} 1473 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1474 template <class _Pp, 1475 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1476 _LIBCPP_INLINE_VISIBILITY 1477 iterator insert(const_iterator __p, _Pp&& __x) 1478 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1479 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1480 template <class _InputIterator> 1481 void insert(_InputIterator __first, _InputIterator __last); 1482 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1483 _LIBCPP_INLINE_VISIBILITY 1484 void insert(initializer_list<value_type> __il) 1485 {insert(__il.begin(), __il.end());} 1486 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1487 1488 _LIBCPP_INLINE_VISIBILITY 1489 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1490 _LIBCPP_INLINE_VISIBILITY 1491 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1492 _LIBCPP_INLINE_VISIBILITY 1493 iterator erase(const_iterator __first, const_iterator __last) 1494 {return __table_.erase(__first.__i_, __last.__i_);} 1495 _LIBCPP_INLINE_VISIBILITY 1496 void clear() _NOEXCEPT {__table_.clear();} 1497 1498 _LIBCPP_INLINE_VISIBILITY 1499 void swap(unordered_multimap& __u) 1500 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1501 {__table_.swap(__u.__table_);} 1502 1503 _LIBCPP_INLINE_VISIBILITY 1504 hasher hash_function() const 1505 {return __table_.hash_function().hash_function();} 1506 _LIBCPP_INLINE_VISIBILITY 1507 key_equal key_eq() const 1508 {return __table_.key_eq().key_eq();} 1509 1510 _LIBCPP_INLINE_VISIBILITY 1511 iterator find(const key_type& __k) {return __table_.find(__k);} 1512 _LIBCPP_INLINE_VISIBILITY 1513 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1514 _LIBCPP_INLINE_VISIBILITY 1515 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1516 _LIBCPP_INLINE_VISIBILITY 1517 pair<iterator, iterator> equal_range(const key_type& __k) 1518 {return __table_.__equal_range_multi(__k);} 1519 _LIBCPP_INLINE_VISIBILITY 1520 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1521 {return __table_.__equal_range_multi(__k);} 1522 1523 _LIBCPP_INLINE_VISIBILITY 1524 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1525 _LIBCPP_INLINE_VISIBILITY 1526 size_type max_bucket_count() const _NOEXCEPT 1527 {return __table_.max_bucket_count();} 1528 1529 _LIBCPP_INLINE_VISIBILITY 1530 size_type bucket_size(size_type __n) const 1531 {return __table_.bucket_size(__n);} 1532 _LIBCPP_INLINE_VISIBILITY 1533 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1534 1535 _LIBCPP_INLINE_VISIBILITY 1536 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1537 _LIBCPP_INLINE_VISIBILITY 1538 local_iterator end(size_type __n) {return __table_.end(__n);} 1539 _LIBCPP_INLINE_VISIBILITY 1540 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1541 _LIBCPP_INLINE_VISIBILITY 1542 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1543 _LIBCPP_INLINE_VISIBILITY 1544 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1545 _LIBCPP_INLINE_VISIBILITY 1546 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1547 1548 _LIBCPP_INLINE_VISIBILITY 1549 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1550 _LIBCPP_INLINE_VISIBILITY 1551 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1552 _LIBCPP_INLINE_VISIBILITY 1553 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1554 _LIBCPP_INLINE_VISIBILITY 1555 void rehash(size_type __n) {__table_.rehash(__n);} 1556 _LIBCPP_INLINE_VISIBILITY 1557 void reserve(size_type __n) {__table_.reserve(__n);} 1558 1559 private: 1560 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1561 __node_holder __construct_node(); 1562 template <class _A0> 1563 __node_holder 1564 __construct_node(_A0&& __a0); 1565 #ifndef _LIBCPP_HAS_NO_VARIADICS 1566 template <class _A0, class _A1, class ..._Args> 1567 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1568 #endif // _LIBCPP_HAS_NO_VARIADICS 1569 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1570 }; 1571 1572 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1573 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1574 size_type __n, const hasher& __hf, const key_equal& __eql) 1575 : __table_(__hf, __eql) 1576 { 1577 __table_.rehash(__n); 1578 } 1579 1580 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1581 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1582 size_type __n, const hasher& __hf, const key_equal& __eql, 1583 const allocator_type& __a) 1584 : __table_(__hf, __eql, __a) 1585 { 1586 __table_.rehash(__n); 1587 } 1588 1589 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1590 template <class _InputIterator> 1591 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1592 _InputIterator __first, _InputIterator __last) 1593 { 1594 insert(__first, __last); 1595 } 1596 1597 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1598 template <class _InputIterator> 1599 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1600 _InputIterator __first, _InputIterator __last, size_type __n, 1601 const hasher& __hf, const key_equal& __eql) 1602 : __table_(__hf, __eql) 1603 { 1604 __table_.rehash(__n); 1605 insert(__first, __last); 1606 } 1607 1608 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1609 template <class _InputIterator> 1610 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1611 _InputIterator __first, _InputIterator __last, size_type __n, 1612 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1613 : __table_(__hf, __eql, __a) 1614 { 1615 __table_.rehash(__n); 1616 insert(__first, __last); 1617 } 1618 1619 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1620 inline _LIBCPP_INLINE_VISIBILITY 1621 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1622 const allocator_type& __a) 1623 : __table_(__a) 1624 { 1625 } 1626 1627 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1628 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1629 const unordered_multimap& __u) 1630 : __table_(__u.__table_) 1631 { 1632 __table_.rehash(__u.bucket_count()); 1633 insert(__u.begin(), __u.end()); 1634 } 1635 1636 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1637 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1638 const unordered_multimap& __u, const allocator_type& __a) 1639 : __table_(__u.__table_, __a) 1640 { 1641 __table_.rehash(__u.bucket_count()); 1642 insert(__u.begin(), __u.end()); 1643 } 1644 1645 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1646 1647 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1648 inline _LIBCPP_INLINE_VISIBILITY 1649 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1650 unordered_multimap&& __u) 1651 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1652 : __table_(_VSTD::move(__u.__table_)) 1653 { 1654 } 1655 1656 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1657 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1658 unordered_multimap&& __u, const allocator_type& __a) 1659 : __table_(_VSTD::move(__u.__table_), __a) 1660 { 1661 if (__a != __u.get_allocator()) 1662 { 1663 iterator __i = __u.begin(); 1664 while (__u.size() != 0) 1665 { 1666 __table_.__insert_multi( 1667 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1668 ); 1669 } 1670 } 1671 } 1672 1673 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1674 1675 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1676 1677 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1678 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1679 initializer_list<value_type> __il) 1680 { 1681 insert(__il.begin(), __il.end()); 1682 } 1683 1684 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1685 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1686 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1687 const key_equal& __eql) 1688 : __table_(__hf, __eql) 1689 { 1690 __table_.rehash(__n); 1691 insert(__il.begin(), __il.end()); 1692 } 1693 1694 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1695 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1696 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1697 const key_equal& __eql, const allocator_type& __a) 1698 : __table_(__hf, __eql, __a) 1699 { 1700 __table_.rehash(__n); 1701 insert(__il.begin(), __il.end()); 1702 } 1703 1704 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1705 1706 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1707 1708 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1709 inline _LIBCPP_INLINE_VISIBILITY 1710 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1711 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1712 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1713 { 1714 __table_ = _VSTD::move(__u.__table_); 1715 return *this; 1716 } 1717 1718 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1719 1720 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1721 1722 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1723 inline _LIBCPP_INLINE_VISIBILITY 1724 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1725 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1726 initializer_list<value_type> __il) 1727 { 1728 __table_.__assign_multi(__il.begin(), __il.end()); 1729 return *this; 1730 } 1731 1732 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1733 1734 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1735 1736 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1737 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1738 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1739 { 1740 __node_allocator& __na = __table_.__node_alloc(); 1741 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1742 __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1743 __h.get_deleter().__first_constructed = true; 1744 __h.get_deleter().__second_constructed = true; 1745 return __h; 1746 } 1747 1748 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1749 template <class _A0> 1750 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1751 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1752 { 1753 __node_allocator& __na = __table_.__node_alloc(); 1754 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1755 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1756 _VSTD::forward<_A0>(__a0)); 1757 __h.get_deleter().__first_constructed = true; 1758 __h.get_deleter().__second_constructed = true; 1759 return __h; 1760 } 1761 1762 #ifndef _LIBCPP_HAS_NO_VARIADICS 1763 1764 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1765 template <class _A0, class _A1, class ..._Args> 1766 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1767 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 1768 _A0&& __a0, _A1&& __a1, _Args&&... __args) 1769 { 1770 __node_allocator& __na = __table_.__node_alloc(); 1771 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1772 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1773 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1774 _VSTD::forward<_Args>(__args)...); 1775 __h.get_deleter().__first_constructed = true; 1776 __h.get_deleter().__second_constructed = true; 1777 return __h; 1778 } 1779 1780 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1781 template <class... _Args> 1782 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1783 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1784 { 1785 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1786 iterator __r = __table_.__node_insert_multi(__h.get()); 1787 __h.release(); 1788 return __r; 1789 } 1790 1791 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1792 template <class... _Args> 1793 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1794 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 1795 const_iterator __p, _Args&&... __args) 1796 { 1797 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1798 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 1799 __h.release(); 1800 return __r; 1801 } 1802 1803 #endif // _LIBCPP_HAS_NO_VARIADICS 1804 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1805 1806 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1807 template <class _InputIterator> 1808 inline _LIBCPP_INLINE_VISIBILITY 1809 void 1810 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1811 _InputIterator __last) 1812 { 1813 for (; __first != __last; ++__first) 1814 __table_.__insert_multi(*__first); 1815 } 1816 1817 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1818 inline _LIBCPP_INLINE_VISIBILITY 1819 void 1820 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1821 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1822 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1823 { 1824 __x.swap(__y); 1825 } 1826 1827 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1828 bool 1829 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1830 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1831 { 1832 if (__x.size() != __y.size()) 1833 return false; 1834 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1835 const_iterator; 1836 typedef pair<const_iterator, const_iterator> _EqRng; 1837 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1838 { 1839 _EqRng __xeq = __x.equal_range(__i->first); 1840 _EqRng __yeq = __y.equal_range(__i->first); 1841 if (_VSTD::distance(__xeq.first, __xeq.second) != 1842 _VSTD::distance(__yeq.first, __yeq.second) || 1843 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1844 return false; 1845 __i = __xeq.second; 1846 } 1847 return true; 1848 } 1849 1850 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1851 inline _LIBCPP_INLINE_VISIBILITY 1852 bool 1853 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1854 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1855 { 1856 return !(__x == __y); 1857 } 1858 1859 _LIBCPP_END_NAMESPACE_STD 1860 1861 #endif // _LIBCPP_UNORDERED_MAP 1862
