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