1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_UNORDERED_MAP 11#define _LIBCPP_UNORDERED_MAP 12 13/* 14 15 unordered_map synopsis 16 17#include <initializer_list> 18 19namespace std 20{ 21 22template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 23 class Alloc = allocator<pair<const Key, T>>> 24class unordered_map 25{ 26public: 27 // types 28 typedef Key key_type; 29 typedef T mapped_type; 30 typedef Hash hasher; 31 typedef Pred key_equal; 32 typedef Alloc allocator_type; 33 typedef pair<const key_type, mapped_type> value_type; 34 typedef value_type& reference; 35 typedef const value_type& const_reference; 36 typedef typename allocator_traits<allocator_type>::pointer pointer; 37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 38 typedef typename allocator_traits<allocator_type>::size_type size_type; 39 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 40 41 typedef /unspecified/ iterator; 42 typedef /unspecified/ const_iterator; 43 typedef /unspecified/ local_iterator; 44 typedef /unspecified/ const_local_iterator; 45 46 typedef unspecified node_type; // C++17 47 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 48 49 unordered_map() 50 noexcept( 51 is_nothrow_default_constructible<hasher>::value && 52 is_nothrow_default_constructible<key_equal>::value && 53 is_nothrow_default_constructible<allocator_type>::value); 54 explicit unordered_map(size_type n, const hasher& hf = hasher(), 55 const key_equal& eql = key_equal(), 56 const allocator_type& a = allocator_type()); 57 template <class InputIterator> 58 unordered_map(InputIterator f, InputIterator l, 59 size_type n = 0, const hasher& hf = hasher(), 60 const key_equal& eql = key_equal(), 61 const allocator_type& a = allocator_type()); 62 explicit unordered_map(const allocator_type&); 63 unordered_map(const unordered_map&); 64 unordered_map(const unordered_map&, const Allocator&); 65 unordered_map(unordered_map&&) 66 noexcept( 67 is_nothrow_move_constructible<hasher>::value && 68 is_nothrow_move_constructible<key_equal>::value && 69 is_nothrow_move_constructible<allocator_type>::value); 70 unordered_map(unordered_map&&, const Allocator&); 71 unordered_map(initializer_list<value_type>, size_type n = 0, 72 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 73 const allocator_type& a = allocator_type()); 74 unordered_map(size_type n, const allocator_type& a) 75 : unordered_map(n, hasher(), key_equal(), a) {} // C++14 76 unordered_map(size_type n, const hasher& hf, const allocator_type& a) 77 : unordered_map(n, hf, key_equal(), a) {} // C++14 78 template <class InputIterator> 79 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 80 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14 81 template <class InputIterator> 82 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, 83 const allocator_type& a) 84 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14 85 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a) 86 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 87 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf, 88 const allocator_type& a) 89 : unordered_map(il, n, hf, key_equal(), a) {} // C++14 90 ~unordered_map(); 91 unordered_map& operator=(const unordered_map&); 92 unordered_map& operator=(unordered_map&&) 93 noexcept( 94 allocator_type::propagate_on_container_move_assignment::value && 95 is_nothrow_move_assignable<allocator_type>::value && 96 is_nothrow_move_assignable<hasher>::value && 97 is_nothrow_move_assignable<key_equal>::value); 98 unordered_map& operator=(initializer_list<value_type>); 99 100 allocator_type get_allocator() const noexcept; 101 102 bool empty() const noexcept; 103 size_type size() const noexcept; 104 size_type max_size() const noexcept; 105 106 iterator begin() noexcept; 107 iterator end() noexcept; 108 const_iterator begin() const noexcept; 109 const_iterator end() const noexcept; 110 const_iterator cbegin() const noexcept; 111 const_iterator cend() const noexcept; 112 113 template <class... Args> 114 pair<iterator, bool> emplace(Args&&... args); 115 template <class... Args> 116 iterator emplace_hint(const_iterator position, Args&&... args); 117 pair<iterator, bool> insert(const value_type& obj); 118 template <class P> 119 pair<iterator, bool> insert(P&& obj); 120 iterator insert(const_iterator hint, const value_type& obj); 121 template <class P> 122 iterator insert(const_iterator hint, P&& obj); 123 template <class InputIterator> 124 void insert(InputIterator first, InputIterator last); 125 void insert(initializer_list<value_type>); 126 127 node_type extract(const_iterator position); // C++17 128 node_type extract(const key_type& x); // C++17 129 insert_return_type insert(node_type&& nh); // C++17 130 iterator insert(const_iterator hint, node_type&& nh); // C++17 131 132 template <class... Args> 133 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17 134 template <class... Args> 135 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17 136 template <class... Args> 137 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17 138 template <class... Args> 139 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17 140 template <class M> 141 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17 142 template <class M> 143 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17 144 template <class M> 145 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17 146 template <class M> 147 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17 148 149 iterator erase(const_iterator position); 150 iterator erase(iterator position); // C++14 151 size_type erase(const key_type& k); 152 iterator erase(const_iterator first, const_iterator last); 153 void clear() noexcept; 154 155 template<class H2, class P2> 156 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 157 template<class H2, class P2> 158 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 159 template<class H2, class P2> 160 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 161 template<class H2, class P2> 162 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 163 164 void swap(unordered_map&) 165 noexcept( 166 (!allocator_type::propagate_on_container_swap::value || 167 __is_nothrow_swappable<allocator_type>::value) && 168 __is_nothrow_swappable<hasher>::value && 169 __is_nothrow_swappable<key_equal>::value); 170 171 hasher hash_function() const; 172 key_equal key_eq() const; 173 174 iterator find(const key_type& k); 175 const_iterator find(const key_type& k) const; 176 template<typename K> 177 iterator find(const K& x); // C++20 178 template<typename K> 179 const_iterator find(const K& x) const; // C++20 180 size_type count(const key_type& k) const; 181 template<typename K> 182 size_type count(const K& k) const; // C++20 183 bool contains(const key_type& k) const; // C++20 184 template<typename K> 185 bool contains(const K& k) const; // C++20 186 pair<iterator, iterator> equal_range(const key_type& k); 187 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 188 template<typename K> 189 pair<iterator, iterator> equal_range(const K& k); // C++20 190 template<typename K> 191 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 192 193 mapped_type& operator[](const key_type& k); 194 mapped_type& operator[](key_type&& k); 195 196 mapped_type& at(const key_type& k); 197 const mapped_type& at(const key_type& k) const; 198 199 size_type bucket_count() const noexcept; 200 size_type max_bucket_count() const noexcept; 201 202 size_type bucket_size(size_type n) const; 203 size_type bucket(const key_type& k) const; 204 205 local_iterator begin(size_type n); 206 local_iterator end(size_type n); 207 const_local_iterator begin(size_type n) const; 208 const_local_iterator end(size_type n) const; 209 const_local_iterator cbegin(size_type n) const; 210 const_local_iterator cend(size_type n) const; 211 212 float load_factor() const noexcept; 213 float max_load_factor() const noexcept; 214 void max_load_factor(float z); 215 void rehash(size_type n); 216 void reserve(size_type n); 217}; 218 219template<class InputIterator, 220 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>, 221 class Allocator = allocator<iter_to_alloc_t<InputIterator>>> 222unordered_map(InputIterator, InputIterator, typename see below::size_type = see below, 223 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 224 -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred, 225 Allocator>; // C++17 226 227template<class Key, class T, class Hash = hash<Key>, 228 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>> 229unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type = see below, 230 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 231 -> unordered_map<Key, T, Hash, Pred, Allocator>; // C++17 232 233template<class InputIterator, class Allocator> 234unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator) 235 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 236 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 237 238template<class InputIterator, class Allocator> 239unordered_map(InputIterator, InputIterator, Allocator) 240 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 241 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 242 243template<class InputIterator, class Hash, class Allocator> 244unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator) 245 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash, 246 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 247 248template<class Key, class T, typename Allocator> 249unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator) 250 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 251 252template<class Key, class T, typename Allocator> 253unordered_map(initializer_list<pair<const Key, T>>, Allocator) 254 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 255 256template<class Key, class T, class Hash, class Allocator> 257unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, Allocator) 258 -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>; // C++17 259 260template <class Key, class T, class Hash, class Pred, class Alloc> 261 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x, 262 unordered_map<Key, T, Hash, Pred, Alloc>& y) 263 noexcept(noexcept(x.swap(y))); 264 265template <class Key, class T, class Hash, class Pred, class Alloc> 266 bool 267 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 268 const unordered_map<Key, T, Hash, Pred, Alloc>& y); 269 270template <class Key, class T, class Hash, class Pred, class Alloc> 271 bool 272 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 273 const unordered_map<Key, T, Hash, Pred, Alloc>& y); 274 275template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 276 class Alloc = allocator<pair<const Key, T>>> 277class unordered_multimap 278{ 279public: 280 // types 281 typedef Key key_type; 282 typedef T mapped_type; 283 typedef Hash hasher; 284 typedef Pred key_equal; 285 typedef Alloc allocator_type; 286 typedef pair<const key_type, mapped_type> value_type; 287 typedef value_type& reference; 288 typedef const value_type& const_reference; 289 typedef typename allocator_traits<allocator_type>::pointer pointer; 290 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 291 typedef typename allocator_traits<allocator_type>::size_type size_type; 292 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 293 294 typedef /unspecified/ iterator; 295 typedef /unspecified/ const_iterator; 296 typedef /unspecified/ local_iterator; 297 typedef /unspecified/ const_local_iterator; 298 299 typedef unspecified node_type; // C++17 300 301 unordered_multimap() 302 noexcept( 303 is_nothrow_default_constructible<hasher>::value && 304 is_nothrow_default_constructible<key_equal>::value && 305 is_nothrow_default_constructible<allocator_type>::value); 306 explicit unordered_multimap(size_type n, const hasher& hf = hasher(), 307 const key_equal& eql = key_equal(), 308 const allocator_type& a = allocator_type()); 309 template <class InputIterator> 310 unordered_multimap(InputIterator f, InputIterator l, 311 size_type n = 0, const hasher& hf = hasher(), 312 const key_equal& eql = key_equal(), 313 const allocator_type& a = allocator_type()); 314 explicit unordered_multimap(const allocator_type&); 315 unordered_multimap(const unordered_multimap&); 316 unordered_multimap(const unordered_multimap&, const Allocator&); 317 unordered_multimap(unordered_multimap&&) 318 noexcept( 319 is_nothrow_move_constructible<hasher>::value && 320 is_nothrow_move_constructible<key_equal>::value && 321 is_nothrow_move_constructible<allocator_type>::value); 322 unordered_multimap(unordered_multimap&&, const Allocator&); 323 unordered_multimap(initializer_list<value_type>, size_type n = 0, 324 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 325 const allocator_type& a = allocator_type()); 326 unordered_multimap(size_type n, const allocator_type& a) 327 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14 328 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a) 329 : unordered_multimap(n, hf, key_equal(), a) {} // C++14 330 template <class InputIterator> 331 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 332 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14 333 template <class InputIterator> 334 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, 335 const allocator_type& a) 336 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14 337 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a) 338 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 339 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf, 340 const allocator_type& a) 341 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14 342 ~unordered_multimap(); 343 unordered_multimap& operator=(const unordered_multimap&); 344 unordered_multimap& operator=(unordered_multimap&&) 345 noexcept( 346 allocator_type::propagate_on_container_move_assignment::value && 347 is_nothrow_move_assignable<allocator_type>::value && 348 is_nothrow_move_assignable<hasher>::value && 349 is_nothrow_move_assignable<key_equal>::value); 350 unordered_multimap& operator=(initializer_list<value_type>); 351 352 allocator_type get_allocator() const noexcept; 353 354 bool empty() const noexcept; 355 size_type size() const noexcept; 356 size_type max_size() const noexcept; 357 358 iterator begin() noexcept; 359 iterator end() noexcept; 360 const_iterator begin() const noexcept; 361 const_iterator end() const noexcept; 362 const_iterator cbegin() const noexcept; 363 const_iterator cend() const noexcept; 364 365 template <class... Args> 366 iterator emplace(Args&&... args); 367 template <class... Args> 368 iterator emplace_hint(const_iterator position, Args&&... args); 369 iterator insert(const value_type& obj); 370 template <class P> 371 iterator insert(P&& obj); 372 iterator insert(const_iterator hint, const value_type& obj); 373 template <class P> 374 iterator insert(const_iterator hint, P&& obj); 375 template <class InputIterator> 376 void insert(InputIterator first, InputIterator last); 377 void insert(initializer_list<value_type>); 378 379 node_type extract(const_iterator position); // C++17 380 node_type extract(const key_type& x); // C++17 381 iterator insert(node_type&& nh); // C++17 382 iterator insert(const_iterator hint, node_type&& nh); // C++17 383 384 iterator erase(const_iterator position); 385 iterator erase(iterator position); // C++14 386 size_type erase(const key_type& k); 387 iterator erase(const_iterator first, const_iterator last); 388 void clear() noexcept; 389 390 template<class H2, class P2> 391 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 392 template<class H2, class P2> 393 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 394 template<class H2, class P2> 395 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 396 template<class H2, class P2> 397 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 398 399 void swap(unordered_multimap&) 400 noexcept( 401 (!allocator_type::propagate_on_container_swap::value || 402 __is_nothrow_swappable<allocator_type>::value) && 403 __is_nothrow_swappable<hasher>::value && 404 __is_nothrow_swappable<key_equal>::value); 405 406 hasher hash_function() const; 407 key_equal key_eq() const; 408 409 iterator find(const key_type& k); 410 const_iterator find(const key_type& k) const; 411 template<typename K> 412 iterator find(const K& x); // C++20 413 template<typename K> 414 const_iterator find(const K& x) const; // C++20 415 size_type count(const key_type& k) const; 416 template<typename K> 417 size_type count(const K& k) const; // C++20 418 bool contains(const key_type& k) const; // C++20 419 template<typename K> 420 bool contains(const K& k) const; // C++20 421 pair<iterator, iterator> equal_range(const key_type& k); 422 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 423 template<typename K> 424 pair<iterator, iterator> equal_range(const K& k); // C++20 425 template<typename K> 426 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 427 428 size_type bucket_count() const noexcept; 429 size_type max_bucket_count() const noexcept; 430 431 size_type bucket_size(size_type n) const; 432 size_type bucket(const key_type& k) const; 433 434 local_iterator begin(size_type n); 435 local_iterator end(size_type n); 436 const_local_iterator begin(size_type n) const; 437 const_local_iterator end(size_type n) const; 438 const_local_iterator cbegin(size_type n) const; 439 const_local_iterator cend(size_type n) const; 440 441 float load_factor() const noexcept; 442 float max_load_factor() const noexcept; 443 void max_load_factor(float z); 444 void rehash(size_type n); 445 void reserve(size_type n); 446}; 447 448template<class InputIterator, 449 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>, 450 class Allocator = allocator<iter_to_alloc_t<InputIterator>>> 451unordered_multimap(InputIterator, InputIterator, typename see below::size_type = see below, 452 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 453 -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred, 454 Allocator>; // C++17 455 456template<class Key, class T, class Hash = hash<Key>, 457 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>> 458unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type = see below, 459 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 460 -> unordered_multimap<Key, T, Hash, Pred, Allocator>; // C++17 461 462template<class InputIterator, class Allocator> 463unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator) 464 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 465 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 466 467template<class InputIterator, class Allocator> 468unordered_multimap(InputIterator, InputIterator, Allocator) 469 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 470 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 471 472template<class InputIterator, class Hash, class Allocator> 473unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator) 474 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash, 475 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 476 477template<class Key, class T, typename Allocator> 478unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator) 479 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 480 481template<class Key, class T, typename Allocator> 482unordered_multimap(initializer_list<pair<const Key, T>>, Allocator) 483 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 484 485template<class Key, class T, class Hash, class Allocator> 486unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, 487 Allocator) 488 -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>; // C++17 489 490template <class Key, class T, class Hash, class Pred, class Alloc> 491 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 492 unordered_multimap<Key, T, Hash, Pred, Alloc>& y) 493 noexcept(noexcept(x.swap(y))); 494 495template <class K, class T, class H, class P, class A, class Predicate> 496 typename unordered_map<K, T, H, P, A>::size_type 497 erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred); // C++20 498 499template <class K, class T, class H, class P, class A, class Predicate> 500 typename unordered_multimap<K, T, H, P, A>::size_type 501 erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred); // C++20 502 503template <class Key, class T, class Hash, class Pred, class Alloc> 504 bool 505 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 506 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 507 508template <class Key, class T, class Hash, class Pred, class Alloc> 509 bool 510 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 511 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 512 513} // std 514 515*/ 516 517#include <__algorithm/is_permutation.h> 518#include <__assert> // all public C++ headers provide the assertion handler 519#include <__config> 520#include <__debug> 521#include <__functional/is_transparent.h> 522#include <__functional/operations.h> 523#include <__hash_table> 524#include <__iterator/distance.h> 525#include <__iterator/erase_if_container.h> 526#include <__iterator/iterator_traits.h> 527#include <__memory/addressof.h> 528#include <__node_handle> 529#include <__utility/forward.h> 530#include <stdexcept> 531#include <tuple> 532#include <version> 533 534// standard-mandated includes 535 536// [iterator.range] 537#include <__iterator/access.h> 538#include <__iterator/data.h> 539#include <__iterator/empty.h> 540#include <__iterator/reverse_access.h> 541#include <__iterator/size.h> 542 543// [unord.map.syn] 544#include <compare> 545#include <initializer_list> 546 547#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 548# pragma GCC system_header 549#endif 550 551_LIBCPP_BEGIN_NAMESPACE_STD 552 553template <class _Key, class _Cp, class _Hash, class _Pred, 554 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value> 555class __unordered_map_hasher 556 : private _Hash 557{ 558public: 559 _LIBCPP_INLINE_VISIBILITY 560 __unordered_map_hasher() 561 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 562 : _Hash() {} 563 _LIBCPP_INLINE_VISIBILITY 564 __unordered_map_hasher(const _Hash& __h) 565 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 566 : _Hash(__h) {} 567 _LIBCPP_INLINE_VISIBILITY 568 const _Hash& hash_function() const _NOEXCEPT {return *this;} 569 _LIBCPP_INLINE_VISIBILITY 570 size_t operator()(const _Cp& __x) const 571 {return static_cast<const _Hash&>(*this)(__x.__get_value().first);} 572 _LIBCPP_INLINE_VISIBILITY 573 size_t operator()(const _Key& __x) const 574 {return static_cast<const _Hash&>(*this)(__x);} 575#if _LIBCPP_STD_VER > 17 576 template <typename _K2> 577 _LIBCPP_INLINE_VISIBILITY 578 size_t operator()(const _K2& __x) const 579 {return static_cast<const _Hash&>(*this)(__x);} 580#endif 581 _LIBCPP_INLINE_VISIBILITY 582 void swap(__unordered_map_hasher& __y) 583 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) 584 { 585 using _VSTD::swap; 586 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y)); 587 } 588}; 589 590template <class _Key, class _Cp, class _Hash, class _Pred> 591class __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false> 592{ 593 _Hash __hash_; 594public: 595 _LIBCPP_INLINE_VISIBILITY 596 __unordered_map_hasher() 597 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 598 : __hash_() {} 599 _LIBCPP_INLINE_VISIBILITY 600 __unordered_map_hasher(const _Hash& __h) 601 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 602 : __hash_(__h) {} 603 _LIBCPP_INLINE_VISIBILITY 604 const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 605 _LIBCPP_INLINE_VISIBILITY 606 size_t operator()(const _Cp& __x) const 607 {return __hash_(__x.__get_value().first);} 608 _LIBCPP_INLINE_VISIBILITY 609 size_t operator()(const _Key& __x) const 610 {return __hash_(__x);} 611#if _LIBCPP_STD_VER > 17 612 template <typename _K2> 613 _LIBCPP_INLINE_VISIBILITY 614 size_t operator()(const _K2& __x) const 615 {return __hash_(__x);} 616#endif 617 _LIBCPP_INLINE_VISIBILITY 618 void swap(__unordered_map_hasher& __y) 619 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) 620 { 621 using _VSTD::swap; 622 swap(__hash_, __y.__hash_); 623 } 624}; 625 626template <class _Key, class _Cp, class _Hash, class _Pred, bool __b> 627inline _LIBCPP_INLINE_VISIBILITY 628void 629swap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x, 630 __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y) 631 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 632{ 633 __x.swap(__y); 634} 635 636template <class _Key, class _Cp, class _Pred, class _Hash, 637 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value> 638class __unordered_map_equal 639 : private _Pred 640{ 641public: 642 _LIBCPP_INLINE_VISIBILITY 643 __unordered_map_equal() 644 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 645 : _Pred() {} 646 _LIBCPP_INLINE_VISIBILITY 647 __unordered_map_equal(const _Pred& __p) 648 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 649 : _Pred(__p) {} 650 _LIBCPP_INLINE_VISIBILITY 651 const _Pred& key_eq() const _NOEXCEPT {return *this;} 652 _LIBCPP_INLINE_VISIBILITY 653 bool operator()(const _Cp& __x, const _Cp& __y) const 654 {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);} 655 _LIBCPP_INLINE_VISIBILITY 656 bool operator()(const _Cp& __x, const _Key& __y) const 657 {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);} 658 _LIBCPP_INLINE_VISIBILITY 659 bool operator()(const _Key& __x, const _Cp& __y) const 660 {return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);} 661#if _LIBCPP_STD_VER > 17 662 template <typename _K2> 663 _LIBCPP_INLINE_VISIBILITY 664 bool operator()(const _Cp& __x, const _K2& __y) const 665 {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);} 666 template <typename _K2> 667 _LIBCPP_INLINE_VISIBILITY 668 bool operator()(const _K2& __x, const _Cp& __y) const 669 {return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);} 670 template <typename _K2> 671 _LIBCPP_INLINE_VISIBILITY 672 bool operator()(const _Key& __x, const _K2& __y) const 673 {return static_cast<const _Pred&>(*this)(__x, __y);} 674 template <typename _K2> 675 _LIBCPP_INLINE_VISIBILITY 676 bool operator()(const _K2& __x, const _Key& __y) const 677 {return static_cast<const _Pred&>(*this)(__x, __y);} 678#endif 679 _LIBCPP_INLINE_VISIBILITY 680 void swap(__unordered_map_equal& __y) 681 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) 682 { 683 using _VSTD::swap; 684 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y)); 685 } 686}; 687 688template <class _Key, class _Cp, class _Pred, class _Hash> 689class __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false> 690{ 691 _Pred __pred_; 692public: 693 _LIBCPP_INLINE_VISIBILITY 694 __unordered_map_equal() 695 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 696 : __pred_() {} 697 _LIBCPP_INLINE_VISIBILITY 698 __unordered_map_equal(const _Pred& __p) 699 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 700 : __pred_(__p) {} 701 _LIBCPP_INLINE_VISIBILITY 702 const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 703 _LIBCPP_INLINE_VISIBILITY 704 bool operator()(const _Cp& __x, const _Cp& __y) const 705 {return __pred_(__x.__get_value().first, __y.__get_value().first);} 706 _LIBCPP_INLINE_VISIBILITY 707 bool operator()(const _Cp& __x, const _Key& __y) const 708 {return __pred_(__x.__get_value().first, __y);} 709 _LIBCPP_INLINE_VISIBILITY 710 bool operator()(const _Key& __x, const _Cp& __y) const 711 {return __pred_(__x, __y.__get_value().first);} 712#if _LIBCPP_STD_VER > 17 713 template <typename _K2> 714 _LIBCPP_INLINE_VISIBILITY 715 bool operator()(const _Cp& __x, const _K2& __y) const 716 {return __pred_(__x.__get_value().first, __y);} 717 template <typename _K2> 718 _LIBCPP_INLINE_VISIBILITY 719 bool operator()(const _K2& __x, const _Cp& __y) const 720 {return __pred_(__x, __y.__get_value().first);} 721 template <typename _K2> 722 _LIBCPP_INLINE_VISIBILITY 723 bool operator()(const _Key& __x, const _K2& __y) const 724 {return __pred_(__x, __y);} 725 template <typename _K2> 726 _LIBCPP_INLINE_VISIBILITY 727 bool operator()(const _K2& __x, const _Key& __y) const 728 {return __pred_(__x, __y);} 729#endif 730 _LIBCPP_INLINE_VISIBILITY 731 void swap(__unordered_map_equal& __y) 732 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) 733 { 734 using _VSTD::swap; 735 swap(__pred_, __y.__pred_); 736 } 737}; 738 739template <class _Key, class _Cp, class _Pred, class _Hash, bool __b> 740inline _LIBCPP_INLINE_VISIBILITY 741void 742swap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x, 743 __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y) 744 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 745{ 746 __x.swap(__y); 747} 748 749template <class _Alloc> 750class __hash_map_node_destructor 751{ 752 typedef _Alloc allocator_type; 753 typedef allocator_traits<allocator_type> __alloc_traits; 754 755public: 756 757 typedef typename __alloc_traits::pointer pointer; 758private: 759 760 allocator_type& __na_; 761 762 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 763 764public: 765 bool __first_constructed; 766 bool __second_constructed; 767 768 _LIBCPP_INLINE_VISIBILITY 769 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 770 : __na_(__na), 771 __first_constructed(false), 772 __second_constructed(false) 773 {} 774 775#ifndef _LIBCPP_CXX03_LANG 776 _LIBCPP_INLINE_VISIBILITY 777 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 778 _NOEXCEPT 779 : __na_(__x.__na_), 780 __first_constructed(__x.__value_constructed), 781 __second_constructed(__x.__value_constructed) 782 { 783 __x.__value_constructed = false; 784 } 785#else // _LIBCPP_CXX03_LANG 786 _LIBCPP_INLINE_VISIBILITY 787 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 788 : __na_(__x.__na_), 789 __first_constructed(__x.__value_constructed), 790 __second_constructed(__x.__value_constructed) 791 { 792 const_cast<bool&>(__x.__value_constructed) = false; 793 } 794#endif // _LIBCPP_CXX03_LANG 795 796 _LIBCPP_INLINE_VISIBILITY 797 void operator()(pointer __p) _NOEXCEPT 798 { 799 if (__second_constructed) 800 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second)); 801 if (__first_constructed) 802 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first)); 803 if (__p) 804 __alloc_traits::deallocate(__na_, __p, 1); 805 } 806}; 807 808#ifndef _LIBCPP_CXX03_LANG 809template <class _Key, class _Tp> 810struct _LIBCPP_STANDALONE_DEBUG __hash_value_type 811{ 812 typedef _Key key_type; 813 typedef _Tp mapped_type; 814 typedef pair<const key_type, mapped_type> value_type; 815 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type; 816 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type; 817 818private: 819 value_type __cc; 820 821public: 822 _LIBCPP_INLINE_VISIBILITY 823 value_type& __get_value() 824 { 825#if _LIBCPP_STD_VER > 14 826 return *_VSTD::launder(_VSTD::addressof(__cc)); 827#else 828 return __cc; 829#endif 830 } 831 832 _LIBCPP_INLINE_VISIBILITY 833 const value_type& __get_value() const 834 { 835#if _LIBCPP_STD_VER > 14 836 return *_VSTD::launder(_VSTD::addressof(__cc)); 837#else 838 return __cc; 839#endif 840 } 841 842 _LIBCPP_INLINE_VISIBILITY 843 __nc_ref_pair_type __ref() 844 { 845 value_type& __v = __get_value(); 846 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second); 847 } 848 849 _LIBCPP_INLINE_VISIBILITY 850 __nc_rref_pair_type __move() 851 { 852 value_type& __v = __get_value(); 853 return __nc_rref_pair_type( 854 _VSTD::move(const_cast<key_type&>(__v.first)), 855 _VSTD::move(__v.second)); 856 } 857 858 _LIBCPP_INLINE_VISIBILITY 859 __hash_value_type& operator=(const __hash_value_type& __v) 860 { 861 __ref() = __v.__get_value(); 862 return *this; 863 } 864 865 _LIBCPP_INLINE_VISIBILITY 866 __hash_value_type& operator=(__hash_value_type&& __v) 867 { 868 __ref() = __v.__move(); 869 return *this; 870 } 871 872 template <class _ValueTp, 873 class = typename enable_if< 874 __is_same_uncvref<_ValueTp, value_type>::value 875 >::type 876 > 877 _LIBCPP_INLINE_VISIBILITY 878 __hash_value_type& operator=(_ValueTp&& __v) 879 { 880 __ref() = _VSTD::forward<_ValueTp>(__v); 881 return *this; 882 } 883 884private: 885 __hash_value_type(const __hash_value_type& __v) = delete; 886 __hash_value_type(__hash_value_type&& __v) = delete; 887 template <class ..._Args> 888 explicit __hash_value_type(_Args&& ...__args) = delete; 889 890 ~__hash_value_type() = delete; 891}; 892 893#else 894 895template <class _Key, class _Tp> 896struct __hash_value_type 897{ 898 typedef _Key key_type; 899 typedef _Tp mapped_type; 900 typedef pair<const key_type, mapped_type> value_type; 901 902private: 903 value_type __cc; 904 905public: 906 _LIBCPP_INLINE_VISIBILITY 907 value_type& __get_value() { return __cc; } 908 _LIBCPP_INLINE_VISIBILITY 909 const value_type& __get_value() const { return __cc; } 910 911private: 912 ~__hash_value_type(); 913}; 914 915#endif 916 917template <class _HashIterator> 918class _LIBCPP_TEMPLATE_VIS __hash_map_iterator 919{ 920 _HashIterator __i_; 921 922 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; 923 924public: 925 typedef forward_iterator_tag iterator_category; 926 typedef typename _NodeTypes::__map_value_type value_type; 927 typedef typename _NodeTypes::difference_type difference_type; 928 typedef value_type& reference; 929 typedef typename _NodeTypes::__map_value_type_pointer pointer; 930 931 _LIBCPP_INLINE_VISIBILITY 932 __hash_map_iterator() _NOEXCEPT {} 933 934 _LIBCPP_INLINE_VISIBILITY 935 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 936 937 _LIBCPP_INLINE_VISIBILITY 938 reference operator*() const {return __i_->__get_value();} 939 _LIBCPP_INLINE_VISIBILITY 940 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} 941 942 _LIBCPP_INLINE_VISIBILITY 943 __hash_map_iterator& operator++() {++__i_; return *this;} 944 _LIBCPP_INLINE_VISIBILITY 945 __hash_map_iterator operator++(int) 946 { 947 __hash_map_iterator __t(*this); 948 ++(*this); 949 return __t; 950 } 951 952 friend _LIBCPP_INLINE_VISIBILITY 953 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 954 {return __x.__i_ == __y.__i_;} 955 friend _LIBCPP_INLINE_VISIBILITY 956 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 957 {return __x.__i_ != __y.__i_;} 958 959 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map; 960 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 961 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 962 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 963 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 964}; 965 966template <class _HashIterator> 967class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator 968{ 969 _HashIterator __i_; 970 971 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; 972 973public: 974 typedef forward_iterator_tag iterator_category; 975 typedef typename _NodeTypes::__map_value_type value_type; 976 typedef typename _NodeTypes::difference_type difference_type; 977 typedef const value_type& reference; 978 typedef typename _NodeTypes::__const_map_value_type_pointer pointer; 979 980 _LIBCPP_INLINE_VISIBILITY 981 __hash_map_const_iterator() _NOEXCEPT {} 982 983 _LIBCPP_INLINE_VISIBILITY 984 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 985 _LIBCPP_INLINE_VISIBILITY 986 __hash_map_const_iterator( 987 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 988 _NOEXCEPT 989 : __i_(__i.__i_) {} 990 991 _LIBCPP_INLINE_VISIBILITY 992 reference operator*() const {return __i_->__get_value();} 993 _LIBCPP_INLINE_VISIBILITY 994 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} 995 996 _LIBCPP_INLINE_VISIBILITY 997 __hash_map_const_iterator& operator++() {++__i_; return *this;} 998 _LIBCPP_INLINE_VISIBILITY 999 __hash_map_const_iterator operator++(int) 1000 { 1001 __hash_map_const_iterator __t(*this); 1002 ++(*this); 1003 return __t; 1004 } 1005 1006 friend _LIBCPP_INLINE_VISIBILITY 1007 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 1008 {return __x.__i_ == __y.__i_;} 1009 friend _LIBCPP_INLINE_VISIBILITY 1010 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 1011 {return __x.__i_ != __y.__i_;} 1012 1013 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1014 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1015 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 1016 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 1017}; 1018 1019template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1020class unordered_multimap; 1021 1022template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1023 class _Alloc = allocator<pair<const _Key, _Tp> > > 1024class _LIBCPP_TEMPLATE_VIS unordered_map 1025{ 1026public: 1027 // types 1028 typedef _Key key_type; 1029 typedef _Tp mapped_type; 1030 typedef __type_identity_t<_Hash> hasher; 1031 typedef __type_identity_t<_Pred> key_equal; 1032 typedef __type_identity_t<_Alloc> allocator_type; 1033 typedef pair<const key_type, mapped_type> value_type; 1034 typedef value_type& reference; 1035 typedef const value_type& const_reference; 1036 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1037 "Invalid allocator::value_type"); 1038 1039private: 1040 typedef __hash_value_type<key_type, mapped_type> __value_type; 1041 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher; 1042 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal; 1043 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1044 __value_type>::type __allocator_type; 1045 1046 typedef __hash_table<__value_type, __hasher, 1047 __key_equal, __allocator_type> __table; 1048 1049 __table __table_; 1050 1051 typedef typename __table::_NodeTypes _NodeTypes; 1052 typedef typename __table::__node_pointer __node_pointer; 1053 typedef typename __table::__node_const_pointer __node_const_pointer; 1054 typedef typename __table::__node_traits __node_traits; 1055 typedef typename __table::__node_allocator __node_allocator; 1056 typedef typename __table::__node __node; 1057 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1058 typedef unique_ptr<__node, _Dp> __node_holder; 1059 typedef allocator_traits<allocator_type> __alloc_traits; 1060 1061 static_assert((is_same<typename __table::__container_value_type, value_type>::value), ""); 1062 static_assert((is_same<typename __table::__node_value_type, __value_type>::value), ""); 1063public: 1064 typedef typename __alloc_traits::pointer pointer; 1065 typedef typename __alloc_traits::const_pointer const_pointer; 1066 typedef typename __table::size_type size_type; 1067 typedef typename __table::difference_type difference_type; 1068 1069 typedef __hash_map_iterator<typename __table::iterator> iterator; 1070 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1071 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1072 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1073 1074#if _LIBCPP_STD_VER > 14 1075 typedef __map_node_handle<__node, allocator_type> node_type; 1076 typedef __insert_return_type<iterator, node_type> insert_return_type; 1077#endif 1078 1079 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1080 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1081 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1082 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1083 1084 _LIBCPP_INLINE_VISIBILITY 1085 unordered_map() 1086 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1087 { 1088 _VSTD::__debug_db_insert_c(this); 1089 } 1090 explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 1091 const key_equal& __eql = key_equal()); 1092 unordered_map(size_type __n, const hasher& __hf, 1093 const key_equal& __eql, 1094 const allocator_type& __a); 1095 template <class _InputIterator> 1096 unordered_map(_InputIterator __first, _InputIterator __last); 1097 template <class _InputIterator> 1098 unordered_map(_InputIterator __first, _InputIterator __last, 1099 size_type __n, const hasher& __hf = hasher(), 1100 const key_equal& __eql = key_equal()); 1101 template <class _InputIterator> 1102 unordered_map(_InputIterator __first, _InputIterator __last, 1103 size_type __n, const hasher& __hf, 1104 const key_equal& __eql, 1105 const allocator_type& __a); 1106 _LIBCPP_INLINE_VISIBILITY 1107 explicit unordered_map(const allocator_type& __a); 1108 unordered_map(const unordered_map& __u); 1109 unordered_map(const unordered_map& __u, const allocator_type& __a); 1110#ifndef _LIBCPP_CXX03_LANG 1111 _LIBCPP_INLINE_VISIBILITY 1112 unordered_map(unordered_map&& __u) 1113 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1114 unordered_map(unordered_map&& __u, const allocator_type& __a); 1115 unordered_map(initializer_list<value_type> __il); 1116 unordered_map(initializer_list<value_type> __il, size_type __n, 1117 const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 1118 unordered_map(initializer_list<value_type> __il, size_type __n, 1119 const hasher& __hf, const key_equal& __eql, 1120 const allocator_type& __a); 1121#endif // _LIBCPP_CXX03_LANG 1122#if _LIBCPP_STD_VER > 11 1123 _LIBCPP_INLINE_VISIBILITY 1124 unordered_map(size_type __n, const allocator_type& __a) 1125 : unordered_map(__n, hasher(), key_equal(), __a) {} 1126 _LIBCPP_INLINE_VISIBILITY 1127 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a) 1128 : unordered_map(__n, __hf, key_equal(), __a) {} 1129 template <class _InputIterator> 1130 _LIBCPP_INLINE_VISIBILITY 1131 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1132 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} 1133 template <class _InputIterator> 1134 _LIBCPP_INLINE_VISIBILITY 1135 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 1136 const allocator_type& __a) 1137 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} 1138 _LIBCPP_INLINE_VISIBILITY 1139 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1140 : unordered_map(__il, __n, hasher(), key_equal(), __a) {} 1141 _LIBCPP_INLINE_VISIBILITY 1142 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1143 const allocator_type& __a) 1144 : unordered_map(__il, __n, __hf, key_equal(), __a) {} 1145#endif 1146 _LIBCPP_INLINE_VISIBILITY 1147 ~unordered_map() { 1148 static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), ""); 1149 } 1150 1151 _LIBCPP_INLINE_VISIBILITY 1152 unordered_map& operator=(const unordered_map& __u) 1153 { 1154#ifndef _LIBCPP_CXX03_LANG 1155 __table_ = __u.__table_; 1156#else 1157 if (this != _VSTD::addressof(__u)) { 1158 __table_.clear(); 1159 __table_.hash_function() = __u.__table_.hash_function(); 1160 __table_.key_eq() = __u.__table_.key_eq(); 1161 __table_.max_load_factor() = __u.__table_.max_load_factor(); 1162 __table_.__copy_assign_alloc(__u.__table_); 1163 insert(__u.begin(), __u.end()); 1164 } 1165#endif 1166 return *this; 1167 } 1168#ifndef _LIBCPP_CXX03_LANG 1169 _LIBCPP_INLINE_VISIBILITY 1170 unordered_map& operator=(unordered_map&& __u) 1171 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1172 _LIBCPP_INLINE_VISIBILITY 1173 unordered_map& operator=(initializer_list<value_type> __il); 1174#endif // _LIBCPP_CXX03_LANG 1175 1176 _LIBCPP_INLINE_VISIBILITY 1177 allocator_type get_allocator() const _NOEXCEPT 1178 {return allocator_type(__table_.__node_alloc());} 1179 1180 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1181 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1182 _LIBCPP_INLINE_VISIBILITY 1183 size_type size() const _NOEXCEPT {return __table_.size();} 1184 _LIBCPP_INLINE_VISIBILITY 1185 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1186 1187 _LIBCPP_INLINE_VISIBILITY 1188 iterator begin() _NOEXCEPT {return __table_.begin();} 1189 _LIBCPP_INLINE_VISIBILITY 1190 iterator end() _NOEXCEPT {return __table_.end();} 1191 _LIBCPP_INLINE_VISIBILITY 1192 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1193 _LIBCPP_INLINE_VISIBILITY 1194 const_iterator end() const _NOEXCEPT {return __table_.end();} 1195 _LIBCPP_INLINE_VISIBILITY 1196 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1197 _LIBCPP_INLINE_VISIBILITY 1198 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1199 1200 _LIBCPP_INLINE_VISIBILITY 1201 pair<iterator, bool> insert(const value_type& __x) 1202 {return __table_.__insert_unique(__x);} 1203 1204 iterator insert(const_iterator __p, const value_type& __x) { 1205 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1206 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not " 1207 "referring to this unordered_map"); 1208 ((void)__p); 1209 return insert(__x).first; 1210 } 1211 1212 template <class _InputIterator> 1213 _LIBCPP_INLINE_VISIBILITY 1214 void insert(_InputIterator __first, _InputIterator __last); 1215 1216#ifndef _LIBCPP_CXX03_LANG 1217 _LIBCPP_INLINE_VISIBILITY 1218 void insert(initializer_list<value_type> __il) 1219 {insert(__il.begin(), __il.end());} 1220 1221 _LIBCPP_INLINE_VISIBILITY 1222 pair<iterator, bool> insert(value_type&& __x) 1223 {return __table_.__insert_unique(_VSTD::move(__x));} 1224 1225 iterator insert(const_iterator __p, value_type&& __x) { 1226 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1227 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" 1228 " referring to this unordered_map"); 1229 ((void)__p); 1230 return __table_.__insert_unique(_VSTD::move(__x)).first; 1231 } 1232 1233 template <class _Pp, 1234 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1235 _LIBCPP_INLINE_VISIBILITY 1236 pair<iterator, bool> insert(_Pp&& __x) 1237 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 1238 1239 template <class _Pp, 1240 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1241 _LIBCPP_INLINE_VISIBILITY 1242 iterator insert(const_iterator __p, _Pp&& __x) 1243 { 1244 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1245 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" 1246 " referring to this unordered_map"); 1247 ((void)__p); 1248 return insert(_VSTD::forward<_Pp>(__x)).first; 1249 } 1250 1251 template <class... _Args> 1252 _LIBCPP_INLINE_VISIBILITY 1253 pair<iterator, bool> emplace(_Args&&... __args) { 1254 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...); 1255 } 1256 1257 template <class... _Args> 1258 _LIBCPP_INLINE_VISIBILITY 1259 iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1260 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, 1261 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" 1262 " referring to this unordered_map"); 1263 ((void)__p); 1264 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 1265 } 1266 1267#endif // _LIBCPP_CXX03_LANG 1268 1269#if _LIBCPP_STD_VER > 14 1270 template <class... _Args> 1271 _LIBCPP_INLINE_VISIBILITY 1272 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) 1273 { 1274 return __table_.__emplace_unique_key_args(__k, piecewise_construct, 1275 _VSTD::forward_as_tuple(__k), 1276 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1277 } 1278 1279 template <class... _Args> 1280 _LIBCPP_INLINE_VISIBILITY 1281 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) 1282 { 1283 return __table_.__emplace_unique_key_args(__k, piecewise_construct, 1284 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1285 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1286 } 1287 1288 template <class... _Args> 1289 _LIBCPP_INLINE_VISIBILITY 1290 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) 1291 { 1292 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__h)) == this, 1293 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not" 1294 " referring to this unordered_map"); 1295 ((void)__h); 1296 return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first; 1297 } 1298 1299 template <class... _Args> 1300 _LIBCPP_INLINE_VISIBILITY 1301 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) 1302 { 1303 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__h)) == this, 1304 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not" 1305 " referring to this unordered_map"); 1306 ((void)__h); 1307 return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first; 1308 } 1309 1310 template <class _Vp> 1311 _LIBCPP_INLINE_VISIBILITY 1312 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) 1313 { 1314 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, 1315 __k, _VSTD::forward<_Vp>(__v)); 1316 if (!__res.second) { 1317 __res.first->second = _VSTD::forward<_Vp>(__v); 1318 } 1319 return __res; 1320 } 1321 1322 template <class _Vp> 1323 _LIBCPP_INLINE_VISIBILITY 1324 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) 1325 { 1326 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, 1327 _VSTD::move(__k), _VSTD::forward<_Vp>(__v)); 1328 if (!__res.second) { 1329 __res.first->second = _VSTD::forward<_Vp>(__v); 1330 } 1331 return __res; 1332 } 1333 1334 template <class _Vp> 1335 _LIBCPP_INLINE_VISIBILITY 1336 iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v) 1337 { 1338 // FIXME: Add debug mode checking for the iterator input 1339 return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first; 1340 } 1341 1342 template <class _Vp> 1343 _LIBCPP_INLINE_VISIBILITY 1344 iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v) 1345 { 1346 // FIXME: Add debug mode checking for the iterator input 1347 return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first; 1348 } 1349#endif // _LIBCPP_STD_VER > 14 1350 1351 _LIBCPP_INLINE_VISIBILITY 1352 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1353 _LIBCPP_INLINE_VISIBILITY 1354 iterator erase(iterator __p) {return __table_.erase(__p.__i_);} 1355 _LIBCPP_INLINE_VISIBILITY 1356 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 1357 _LIBCPP_INLINE_VISIBILITY 1358 iterator erase(const_iterator __first, const_iterator __last) 1359 {return __table_.erase(__first.__i_, __last.__i_);} 1360 _LIBCPP_INLINE_VISIBILITY 1361 void clear() _NOEXCEPT {__table_.clear();} 1362 1363#if _LIBCPP_STD_VER > 14 1364 _LIBCPP_INLINE_VISIBILITY 1365 insert_return_type insert(node_type&& __nh) 1366 { 1367 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1368 "node_type with incompatible allocator passed to unordered_map::insert()"); 1369 return __table_.template __node_handle_insert_unique< 1370 node_type, insert_return_type>(_VSTD::move(__nh)); 1371 } 1372 _LIBCPP_INLINE_VISIBILITY 1373 iterator insert(const_iterator __hint, node_type&& __nh) 1374 { 1375 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1376 "node_type with incompatible allocator passed to unordered_map::insert()"); 1377 return __table_.template __node_handle_insert_unique<node_type>( 1378 __hint.__i_, _VSTD::move(__nh)); 1379 } 1380 _LIBCPP_INLINE_VISIBILITY 1381 node_type extract(key_type const& __key) 1382 { 1383 return __table_.template __node_handle_extract<node_type>(__key); 1384 } 1385 _LIBCPP_INLINE_VISIBILITY 1386 node_type extract(const_iterator __it) 1387 { 1388 return __table_.template __node_handle_extract<node_type>( 1389 __it.__i_); 1390 } 1391 1392 template <class _H2, class _P2> 1393 _LIBCPP_INLINE_VISIBILITY 1394 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) 1395 { 1396 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1397 "merging container with incompatible allocator"); 1398 return __table_.__node_handle_merge_unique(__source.__table_); 1399 } 1400 template <class _H2, class _P2> 1401 _LIBCPP_INLINE_VISIBILITY 1402 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) 1403 { 1404 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1405 "merging container with incompatible allocator"); 1406 return __table_.__node_handle_merge_unique(__source.__table_); 1407 } 1408 template <class _H2, class _P2> 1409 _LIBCPP_INLINE_VISIBILITY 1410 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) 1411 { 1412 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1413 "merging container with incompatible allocator"); 1414 return __table_.__node_handle_merge_unique(__source.__table_); 1415 } 1416 template <class _H2, class _P2> 1417 _LIBCPP_INLINE_VISIBILITY 1418 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) 1419 { 1420 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1421 "merging container with incompatible allocator"); 1422 return __table_.__node_handle_merge_unique(__source.__table_); 1423 } 1424#endif 1425 1426 _LIBCPP_INLINE_VISIBILITY 1427 void swap(unordered_map& __u) 1428 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1429 { __table_.swap(__u.__table_);} 1430 1431 _LIBCPP_INLINE_VISIBILITY 1432 hasher hash_function() const 1433 {return __table_.hash_function().hash_function();} 1434 _LIBCPP_INLINE_VISIBILITY 1435 key_equal key_eq() const 1436 {return __table_.key_eq().key_eq();} 1437 1438 _LIBCPP_INLINE_VISIBILITY 1439 iterator find(const key_type& __k) {return __table_.find(__k);} 1440 _LIBCPP_INLINE_VISIBILITY 1441 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1442#if _LIBCPP_STD_VER > 17 1443 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1444 _LIBCPP_INLINE_VISIBILITY 1445 iterator find(const _K2& __k) {return __table_.find(__k);} 1446 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1447 _LIBCPP_INLINE_VISIBILITY 1448 const_iterator find(const _K2& __k) const {return __table_.find(__k);} 1449#endif // _LIBCPP_STD_VER > 17 1450 1451 _LIBCPP_INLINE_VISIBILITY 1452 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 1453#if _LIBCPP_STD_VER > 17 1454 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1455 _LIBCPP_INLINE_VISIBILITY 1456 size_type count(const _K2& __k) const {return __table_.__count_unique(__k);} 1457#endif // _LIBCPP_STD_VER > 17 1458 1459#if _LIBCPP_STD_VER > 17 1460 _LIBCPP_INLINE_VISIBILITY 1461 bool contains(const key_type& __k) const {return find(__k) != end();} 1462 1463 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1464 _LIBCPP_INLINE_VISIBILITY 1465 bool contains(const _K2& __k) const {return find(__k) != end();} 1466#endif // _LIBCPP_STD_VER > 17 1467 1468 _LIBCPP_INLINE_VISIBILITY 1469 pair<iterator, iterator> equal_range(const key_type& __k) 1470 {return __table_.__equal_range_unique(__k);} 1471 _LIBCPP_INLINE_VISIBILITY 1472 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1473 {return __table_.__equal_range_unique(__k);} 1474#if _LIBCPP_STD_VER > 17 1475 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1476 _LIBCPP_INLINE_VISIBILITY 1477 pair<iterator, iterator> equal_range(const _K2& __k) 1478 {return __table_.__equal_range_unique(__k);} 1479 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1480 _LIBCPP_INLINE_VISIBILITY 1481 pair<const_iterator, const_iterator> equal_range(const _K2& __k) const 1482 {return __table_.__equal_range_unique(__k);} 1483#endif // _LIBCPP_STD_VER > 17 1484 1485 mapped_type& operator[](const key_type& __k); 1486#ifndef _LIBCPP_CXX03_LANG 1487 mapped_type& operator[](key_type&& __k); 1488#endif 1489 1490 mapped_type& at(const key_type& __k); 1491 const mapped_type& at(const key_type& __k) const; 1492 1493 _LIBCPP_INLINE_VISIBILITY 1494 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1495 _LIBCPP_INLINE_VISIBILITY 1496 size_type max_bucket_count() const _NOEXCEPT {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#ifdef _LIBCPP_ENABLE_DEBUG_MODE 1529 1530 bool __dereferenceable(const const_iterator* __i) const 1531 {return __table_.__dereferenceable(_VSTD::addressof(__i->__i_));} 1532 bool __decrementable(const const_iterator* __i) const 1533 {return __table_.__decrementable(_VSTD::addressof(__i->__i_));} 1534 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1535 {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);} 1536 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1537 {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);} 1538 1539#endif // _LIBCPP_ENABLE_DEBUG_MODE 1540 1541private: 1542 1543#ifdef _LIBCPP_CXX03_LANG 1544 __node_holder __construct_node_with_key(const key_type& __k); 1545#endif 1546}; 1547 1548#if _LIBCPP_STD_VER >= 17 1549template<class _InputIterator, 1550 class _Hash = hash<__iter_key_type<_InputIterator>>, 1551 class _Pred = equal_to<__iter_key_type<_InputIterator>>, 1552 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 1553 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 1554 class = enable_if_t<!__is_allocator<_Hash>::value>, 1555 class = enable_if_t<!is_integral<_Hash>::value>, 1556 class = enable_if_t<!__is_allocator<_Pred>::value>, 1557 class = enable_if_t<__is_allocator<_Allocator>::value>> 1558unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0, 1559 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 1560 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>; 1561 1562template<class _Key, class _Tp, class _Hash = hash<remove_const_t<_Key>>, 1563 class _Pred = equal_to<remove_const_t<_Key>>, 1564 class _Allocator = allocator<pair<const _Key, _Tp>>, 1565 class = enable_if_t<!__is_allocator<_Hash>::value>, 1566 class = enable_if_t<!is_integral<_Hash>::value>, 1567 class = enable_if_t<!__is_allocator<_Pred>::value>, 1568 class = enable_if_t<__is_allocator<_Allocator>::value>> 1569unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type = 0, 1570 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 1571 -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>; 1572 1573template<class _InputIterator, class _Allocator, 1574 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 1575 class = enable_if_t<__is_allocator<_Allocator>::value>> 1576unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 1577 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 1578 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; 1579 1580template<class _InputIterator, class _Allocator, 1581 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 1582 class = enable_if_t<__is_allocator<_Allocator>::value>> 1583unordered_map(_InputIterator, _InputIterator, _Allocator) 1584 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 1585 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; 1586 1587template<class _InputIterator, class _Hash, class _Allocator, 1588 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 1589 class = enable_if_t<!__is_allocator<_Hash>::value>, 1590 class = enable_if_t<!is_integral<_Hash>::value>, 1591 class = enable_if_t<__is_allocator<_Allocator>::value>> 1592unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1593 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 1594 _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; 1595 1596template<class _Key, class _Tp, class _Allocator, 1597 class = enable_if_t<__is_allocator<_Allocator>::value>> 1598unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator) 1599 -> unordered_map<remove_const_t<_Key>, _Tp, 1600 hash<remove_const_t<_Key>>, 1601 equal_to<remove_const_t<_Key>>, _Allocator>; 1602 1603template<class _Key, class _Tp, class _Allocator, 1604 class = enable_if_t<__is_allocator<_Allocator>::value>> 1605unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) 1606 -> unordered_map<remove_const_t<_Key>, _Tp, 1607 hash<remove_const_t<_Key>>, 1608 equal_to<remove_const_t<_Key>>, _Allocator>; 1609 1610template<class _Key, class _Tp, class _Hash, class _Allocator, 1611 class = enable_if_t<!__is_allocator<_Hash>::value>, 1612 class = enable_if_t<!is_integral<_Hash>::value>, 1613 class = enable_if_t<__is_allocator<_Allocator>::value>> 1614unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1615 -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, 1616 equal_to<remove_const_t<_Key>>, _Allocator>; 1617#endif 1618 1619template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1620unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1621 size_type __n, const hasher& __hf, const key_equal& __eql) 1622 : __table_(__hf, __eql) 1623{ 1624 _VSTD::__debug_db_insert_c(this); 1625 __table_.rehash(__n); 1626} 1627 1628template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1629unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1630 size_type __n, const hasher& __hf, const key_equal& __eql, 1631 const allocator_type& __a) 1632 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1633{ 1634 _VSTD::__debug_db_insert_c(this); 1635 __table_.rehash(__n); 1636} 1637 1638template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1639inline 1640unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1641 const allocator_type& __a) 1642 : __table_(typename __table::allocator_type(__a)) 1643{ 1644 _VSTD::__debug_db_insert_c(this); 1645} 1646 1647template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1648template <class _InputIterator> 1649unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1650 _InputIterator __first, _InputIterator __last) 1651{ 1652 _VSTD::__debug_db_insert_c(this); 1653 insert(__first, __last); 1654} 1655 1656template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1657template <class _InputIterator> 1658unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1659 _InputIterator __first, _InputIterator __last, size_type __n, 1660 const hasher& __hf, const key_equal& __eql) 1661 : __table_(__hf, __eql) 1662{ 1663 _VSTD::__debug_db_insert_c(this); 1664 __table_.rehash(__n); 1665 insert(__first, __last); 1666} 1667 1668template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1669template <class _InputIterator> 1670unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1671 _InputIterator __first, _InputIterator __last, size_type __n, 1672 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1673 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1674{ 1675 _VSTD::__debug_db_insert_c(this); 1676 __table_.rehash(__n); 1677 insert(__first, __last); 1678} 1679 1680template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1681unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1682 const unordered_map& __u) 1683 : __table_(__u.__table_) 1684{ 1685 _VSTD::__debug_db_insert_c(this); 1686 __table_.rehash(__u.bucket_count()); 1687 insert(__u.begin(), __u.end()); 1688} 1689 1690template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1691unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1692 const unordered_map& __u, const allocator_type& __a) 1693 : __table_(__u.__table_, typename __table::allocator_type(__a)) 1694{ 1695 _VSTD::__debug_db_insert_c(this); 1696 __table_.rehash(__u.bucket_count()); 1697 insert(__u.begin(), __u.end()); 1698} 1699 1700#ifndef _LIBCPP_CXX03_LANG 1701 1702template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1703inline 1704unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1705 unordered_map&& __u) 1706 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1707 : __table_(_VSTD::move(__u.__table_)) 1708{ 1709 _VSTD::__debug_db_insert_c(this); 1710 std::__debug_db_swap(this, std::addressof(__u)); 1711} 1712 1713template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1714unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1715 unordered_map&& __u, const allocator_type& __a) 1716 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a)) 1717{ 1718 _VSTD::__debug_db_insert_c(this); 1719 if (__a != __u.get_allocator()) 1720 { 1721 iterator __i = __u.begin(); 1722 while (__u.size() != 0) { 1723 __table_.__emplace_unique( 1724 __u.__table_.remove((__i++).__i_)->__value_.__move()); 1725 } 1726 } 1727 else 1728 std::__debug_db_swap(this, std::addressof(__u)); 1729} 1730 1731template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1732unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1733 initializer_list<value_type> __il) 1734{ 1735 _VSTD::__debug_db_insert_c(this); 1736 insert(__il.begin(), __il.end()); 1737} 1738 1739template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1740unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1741 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1742 const key_equal& __eql) 1743 : __table_(__hf, __eql) 1744{ 1745 _VSTD::__debug_db_insert_c(this); 1746 __table_.rehash(__n); 1747 insert(__il.begin(), __il.end()); 1748} 1749 1750template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1751unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1752 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1753 const key_equal& __eql, const allocator_type& __a) 1754 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1755{ 1756 _VSTD::__debug_db_insert_c(this); 1757 __table_.rehash(__n); 1758 insert(__il.begin(), __il.end()); 1759} 1760 1761template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1762inline 1763unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1764unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1765 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1766{ 1767 __table_ = _VSTD::move(__u.__table_); 1768 return *this; 1769} 1770 1771template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1772inline 1773unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1774unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1775 initializer_list<value_type> __il) 1776{ 1777 __table_.__assign_unique(__il.begin(), __il.end()); 1778 return *this; 1779} 1780 1781#endif // _LIBCPP_CXX03_LANG 1782 1783template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1784template <class _InputIterator> 1785inline 1786void 1787unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1788 _InputIterator __last) 1789{ 1790 for (; __first != __last; ++__first) 1791 __table_.__insert_unique(*__first); 1792} 1793 1794#ifndef _LIBCPP_CXX03_LANG 1795 1796template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1797_Tp& 1798unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1799{ 1800 return __table_.__emplace_unique_key_args(__k, 1801 piecewise_construct, _VSTD::forward_as_tuple(__k), 1802 _VSTD::forward_as_tuple()).first->__get_value().second; 1803} 1804 1805template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1806_Tp& 1807unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1808{ 1809 return __table_.__emplace_unique_key_args(__k, 1810 piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 1811 _VSTD::forward_as_tuple()).first->__get_value().second; 1812} 1813#else // _LIBCPP_CXX03_LANG 1814 1815template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1816typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1817unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1818{ 1819 __node_allocator& __na = __table_.__node_alloc(); 1820 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1821 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k); 1822 __h.get_deleter().__first_constructed = true; 1823 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second)); 1824 __h.get_deleter().__second_constructed = true; 1825 return __h; 1826} 1827 1828template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1829_Tp& 1830unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1831{ 1832 iterator __i = find(__k); 1833 if (__i != end()) 1834 return __i->second; 1835 __node_holder __h = __construct_node_with_key(__k); 1836 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1837 __h.release(); 1838 return __r.first->second; 1839} 1840 1841#endif // _LIBCPP_CXX03_LANG 1842 1843template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1844_Tp& 1845unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1846{ 1847 iterator __i = find(__k); 1848 if (__i == end()) 1849 __throw_out_of_range("unordered_map::at: key not found"); 1850 return __i->second; 1851} 1852 1853template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1854const _Tp& 1855unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1856{ 1857 const_iterator __i = find(__k); 1858 if (__i == end()) 1859 __throw_out_of_range("unordered_map::at: key not found"); 1860 return __i->second; 1861} 1862 1863template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1864inline _LIBCPP_INLINE_VISIBILITY 1865void 1866swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1867 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1868 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1869{ 1870 __x.swap(__y); 1871} 1872 1873#if _LIBCPP_STD_VER > 17 1874template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 1875 class _Predicate> 1876inline _LIBCPP_INLINE_VISIBILITY 1877 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type 1878 erase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, 1879 _Predicate __pred) { 1880 return _VSTD::__libcpp_erase_if_container(__c, __pred); 1881} 1882#endif 1883 1884template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1885bool 1886operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1887 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1888{ 1889 if (__x.size() != __y.size()) 1890 return false; 1891 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1892 const_iterator; 1893 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1894 __i != __ex; ++__i) 1895 { 1896 const_iterator __j = __y.find(__i->first); 1897 if (__j == __ey || !(*__i == *__j)) 1898 return false; 1899 } 1900 return true; 1901} 1902 1903template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1904inline _LIBCPP_INLINE_VISIBILITY 1905bool 1906operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1907 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1908{ 1909 return !(__x == __y); 1910} 1911 1912template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1913 class _Alloc = allocator<pair<const _Key, _Tp> > > 1914class _LIBCPP_TEMPLATE_VIS unordered_multimap 1915{ 1916public: 1917 // types 1918 typedef _Key key_type; 1919 typedef _Tp mapped_type; 1920 typedef __type_identity_t<_Hash> hasher; 1921 typedef __type_identity_t<_Pred> key_equal; 1922 typedef __type_identity_t<_Alloc> allocator_type; 1923 typedef pair<const key_type, mapped_type> value_type; 1924 typedef value_type& reference; 1925 typedef const value_type& const_reference; 1926 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1927 "Invalid allocator::value_type"); 1928 1929private: 1930 typedef __hash_value_type<key_type, mapped_type> __value_type; 1931 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher; 1932 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal; 1933 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1934 __value_type>::type __allocator_type; 1935 1936 typedef __hash_table<__value_type, __hasher, 1937 __key_equal, __allocator_type> __table; 1938 1939 __table __table_; 1940 1941 typedef typename __table::_NodeTypes _NodeTypes; 1942 typedef typename __table::__node_traits __node_traits; 1943 typedef typename __table::__node_allocator __node_allocator; 1944 typedef typename __table::__node __node; 1945 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1946 typedef unique_ptr<__node, _Dp> __node_holder; 1947 typedef allocator_traits<allocator_type> __alloc_traits; 1948 static_assert((is_same<typename __node_traits::size_type, 1949 typename __alloc_traits::size_type>::value), 1950 "Allocator uses different size_type for different types"); 1951public: 1952 typedef typename __alloc_traits::pointer pointer; 1953 typedef typename __alloc_traits::const_pointer const_pointer; 1954 typedef typename __table::size_type size_type; 1955 typedef typename __table::difference_type difference_type; 1956 1957 typedef __hash_map_iterator<typename __table::iterator> iterator; 1958 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1959 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1960 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1961 1962#if _LIBCPP_STD_VER > 14 1963 typedef __map_node_handle<__node, allocator_type> node_type; 1964#endif 1965 1966 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1967 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1968 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1969 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1970 1971 _LIBCPP_INLINE_VISIBILITY 1972 unordered_multimap() 1973 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1974 { 1975 _VSTD::__debug_db_insert_c(this); 1976 } 1977 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1978 const key_equal& __eql = key_equal()); 1979 unordered_multimap(size_type __n, const hasher& __hf, 1980 const key_equal& __eql, 1981 const allocator_type& __a); 1982 template <class _InputIterator> 1983 unordered_multimap(_InputIterator __first, _InputIterator __last); 1984 template <class _InputIterator> 1985 unordered_multimap(_InputIterator __first, _InputIterator __last, 1986 size_type __n, const hasher& __hf = hasher(), 1987 const key_equal& __eql = key_equal()); 1988 template <class _InputIterator> 1989 unordered_multimap(_InputIterator __first, _InputIterator __last, 1990 size_type __n, const hasher& __hf, 1991 const key_equal& __eql, 1992 const allocator_type& __a); 1993 _LIBCPP_INLINE_VISIBILITY 1994 explicit unordered_multimap(const allocator_type& __a); 1995 unordered_multimap(const unordered_multimap& __u); 1996 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1997#ifndef _LIBCPP_CXX03_LANG 1998 _LIBCPP_INLINE_VISIBILITY 1999 unordered_multimap(unordered_multimap&& __u) 2000 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 2001 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 2002 unordered_multimap(initializer_list<value_type> __il); 2003 unordered_multimap(initializer_list<value_type> __il, size_type __n, 2004 const hasher& __hf = hasher(), 2005 const key_equal& __eql = key_equal()); 2006 unordered_multimap(initializer_list<value_type> __il, size_type __n, 2007 const hasher& __hf, const key_equal& __eql, 2008 const allocator_type& __a); 2009#endif // _LIBCPP_CXX03_LANG 2010#if _LIBCPP_STD_VER > 11 2011 _LIBCPP_INLINE_VISIBILITY 2012 unordered_multimap(size_type __n, const allocator_type& __a) 2013 : unordered_multimap(__n, hasher(), key_equal(), __a) {} 2014 _LIBCPP_INLINE_VISIBILITY 2015 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 2016 : unordered_multimap(__n, __hf, key_equal(), __a) {} 2017 template <class _InputIterator> 2018 _LIBCPP_INLINE_VISIBILITY 2019 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 2020 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 2021 template <class _InputIterator> 2022 _LIBCPP_INLINE_VISIBILITY 2023 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 2024 const allocator_type& __a) 2025 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 2026 _LIBCPP_INLINE_VISIBILITY 2027 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 2028 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 2029 _LIBCPP_INLINE_VISIBILITY 2030 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 2031 const allocator_type& __a) 2032 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 2033#endif 2034 _LIBCPP_INLINE_VISIBILITY 2035 ~unordered_multimap() { 2036 static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), ""); 2037 } 2038 2039 _LIBCPP_INLINE_VISIBILITY 2040 unordered_multimap& operator=(const unordered_multimap& __u) 2041 { 2042#ifndef _LIBCPP_CXX03_LANG 2043 __table_ = __u.__table_; 2044#else 2045 if (this != _VSTD::addressof(__u)) { 2046 __table_.clear(); 2047 __table_.hash_function() = __u.__table_.hash_function(); 2048 __table_.key_eq() = __u.__table_.key_eq(); 2049 __table_.max_load_factor() = __u.__table_.max_load_factor(); 2050 __table_.__copy_assign_alloc(__u.__table_); 2051 insert(__u.begin(), __u.end()); 2052 } 2053#endif 2054 return *this; 2055 } 2056#ifndef _LIBCPP_CXX03_LANG 2057 _LIBCPP_INLINE_VISIBILITY 2058 unordered_multimap& operator=(unordered_multimap&& __u) 2059 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 2060 _LIBCPP_INLINE_VISIBILITY 2061 unordered_multimap& operator=(initializer_list<value_type> __il); 2062#endif // _LIBCPP_CXX03_LANG 2063 2064 _LIBCPP_INLINE_VISIBILITY 2065 allocator_type get_allocator() const _NOEXCEPT 2066 {return allocator_type(__table_.__node_alloc());} 2067 2068 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 2069 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 2070 _LIBCPP_INLINE_VISIBILITY 2071 size_type size() const _NOEXCEPT {return __table_.size();} 2072 _LIBCPP_INLINE_VISIBILITY 2073 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 2074 2075 _LIBCPP_INLINE_VISIBILITY 2076 iterator begin() _NOEXCEPT {return __table_.begin();} 2077 _LIBCPP_INLINE_VISIBILITY 2078 iterator end() _NOEXCEPT {return __table_.end();} 2079 _LIBCPP_INLINE_VISIBILITY 2080 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 2081 _LIBCPP_INLINE_VISIBILITY 2082 const_iterator end() const _NOEXCEPT {return __table_.end();} 2083 _LIBCPP_INLINE_VISIBILITY 2084 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 2085 _LIBCPP_INLINE_VISIBILITY 2086 const_iterator cend() const _NOEXCEPT {return __table_.end();} 2087 2088 _LIBCPP_INLINE_VISIBILITY 2089 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 2090 2091 _LIBCPP_INLINE_VISIBILITY 2092 iterator insert(const_iterator __p, const value_type& __x) 2093 {return __table_.__insert_multi(__p.__i_, __x);} 2094 2095 template <class _InputIterator> 2096 _LIBCPP_INLINE_VISIBILITY 2097 void insert(_InputIterator __first, _InputIterator __last); 2098 2099#ifndef _LIBCPP_CXX03_LANG 2100 _LIBCPP_INLINE_VISIBILITY 2101 void insert(initializer_list<value_type> __il) 2102 {insert(__il.begin(), __il.end());} 2103 _LIBCPP_INLINE_VISIBILITY 2104 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 2105 2106 _LIBCPP_INLINE_VISIBILITY 2107 iterator insert(const_iterator __p, value_type&& __x) 2108 {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));} 2109 2110 template <class _Pp, 2111 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 2112 _LIBCPP_INLINE_VISIBILITY 2113 iterator insert(_Pp&& __x) 2114 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 2115 2116 template <class _Pp, 2117 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 2118 _LIBCPP_INLINE_VISIBILITY 2119 iterator insert(const_iterator __p, _Pp&& __x) 2120 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 2121 2122 template <class... _Args> 2123 iterator emplace(_Args&&... __args) { 2124 return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...); 2125 } 2126 2127 template <class... _Args> 2128 iterator emplace_hint(const_iterator __p, _Args&&... __args) { 2129 return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); 2130 } 2131#endif // _LIBCPP_CXX03_LANG 2132 2133 2134 _LIBCPP_INLINE_VISIBILITY 2135 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 2136 _LIBCPP_INLINE_VISIBILITY 2137 iterator erase(iterator __p) {return __table_.erase(__p.__i_);} 2138 _LIBCPP_INLINE_VISIBILITY 2139 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 2140 _LIBCPP_INLINE_VISIBILITY 2141 iterator erase(const_iterator __first, const_iterator __last) 2142 {return __table_.erase(__first.__i_, __last.__i_);} 2143 _LIBCPP_INLINE_VISIBILITY 2144 void clear() _NOEXCEPT {__table_.clear();} 2145 2146#if _LIBCPP_STD_VER > 14 2147 _LIBCPP_INLINE_VISIBILITY 2148 iterator insert(node_type&& __nh) 2149 { 2150 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 2151 "node_type with incompatible allocator passed to unordered_multimap::insert()"); 2152 return __table_.template __node_handle_insert_multi<node_type>( 2153 _VSTD::move(__nh)); 2154 } 2155 _LIBCPP_INLINE_VISIBILITY 2156 iterator insert(const_iterator __hint, node_type&& __nh) 2157 { 2158 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 2159 "node_type with incompatible allocator passed to unordered_multimap::insert()"); 2160 return __table_.template __node_handle_insert_multi<node_type>( 2161 __hint.__i_, _VSTD::move(__nh)); 2162 } 2163 _LIBCPP_INLINE_VISIBILITY 2164 node_type extract(key_type const& __key) 2165 { 2166 return __table_.template __node_handle_extract<node_type>(__key); 2167 } 2168 _LIBCPP_INLINE_VISIBILITY 2169 node_type extract(const_iterator __it) 2170 { 2171 return __table_.template __node_handle_extract<node_type>( 2172 __it.__i_); 2173 } 2174 2175 template <class _H2, class _P2> 2176 _LIBCPP_INLINE_VISIBILITY 2177 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) 2178 { 2179 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2180 "merging container with incompatible allocator"); 2181 return __table_.__node_handle_merge_multi(__source.__table_); 2182 } 2183 template <class _H2, class _P2> 2184 _LIBCPP_INLINE_VISIBILITY 2185 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) 2186 { 2187 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2188 "merging container with incompatible allocator"); 2189 return __table_.__node_handle_merge_multi(__source.__table_); 2190 } 2191 template <class _H2, class _P2> 2192 _LIBCPP_INLINE_VISIBILITY 2193 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) 2194 { 2195 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2196 "merging container with incompatible allocator"); 2197 return __table_.__node_handle_merge_multi(__source.__table_); 2198 } 2199 template <class _H2, class _P2> 2200 _LIBCPP_INLINE_VISIBILITY 2201 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) 2202 { 2203 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2204 "merging container with incompatible allocator"); 2205 return __table_.__node_handle_merge_multi(__source.__table_); 2206 } 2207#endif 2208 2209 _LIBCPP_INLINE_VISIBILITY 2210 void swap(unordered_multimap& __u) 2211 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 2212 {__table_.swap(__u.__table_);} 2213 2214 _LIBCPP_INLINE_VISIBILITY 2215 hasher hash_function() const 2216 {return __table_.hash_function().hash_function();} 2217 _LIBCPP_INLINE_VISIBILITY 2218 key_equal key_eq() const 2219 {return __table_.key_eq().key_eq();} 2220 2221 _LIBCPP_INLINE_VISIBILITY 2222 iterator find(const key_type& __k) {return __table_.find(__k);} 2223 _LIBCPP_INLINE_VISIBILITY 2224 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 2225#if _LIBCPP_STD_VER > 17 2226 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2227 _LIBCPP_INLINE_VISIBILITY 2228 iterator find(const _K2& __k) {return __table_.find(__k);} 2229 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2230 _LIBCPP_INLINE_VISIBILITY 2231 const_iterator find(const _K2& __k) const {return __table_.find(__k);} 2232#endif // _LIBCPP_STD_VER > 17 2233 2234 _LIBCPP_INLINE_VISIBILITY 2235 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 2236#if _LIBCPP_STD_VER > 17 2237 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2238 _LIBCPP_INLINE_VISIBILITY 2239 size_type count(const _K2& __k) const {return __table_.__count_multi(__k);} 2240#endif // _LIBCPP_STD_VER > 17 2241 2242#if _LIBCPP_STD_VER > 17 2243 _LIBCPP_INLINE_VISIBILITY 2244 bool contains(const key_type& __k) const {return find(__k) != end();} 2245 2246 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2247 _LIBCPP_INLINE_VISIBILITY 2248 bool contains(const _K2& __k) const {return find(__k) != end();} 2249#endif // _LIBCPP_STD_VER > 17 2250 2251 _LIBCPP_INLINE_VISIBILITY 2252 pair<iterator, iterator> equal_range(const key_type& __k) 2253 {return __table_.__equal_range_multi(__k);} 2254 _LIBCPP_INLINE_VISIBILITY 2255 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 2256 {return __table_.__equal_range_multi(__k);} 2257#if _LIBCPP_STD_VER > 17 2258 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2259 _LIBCPP_INLINE_VISIBILITY 2260 pair<iterator, iterator> equal_range(const _K2& __k) 2261 {return __table_.__equal_range_multi(__k);} 2262 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2263 _LIBCPP_INLINE_VISIBILITY 2264 pair<const_iterator, const_iterator> equal_range(const _K2& __k) const 2265 {return __table_.__equal_range_multi(__k);} 2266#endif // _LIBCPP_STD_VER > 17 2267 2268 _LIBCPP_INLINE_VISIBILITY 2269 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 2270 _LIBCPP_INLINE_VISIBILITY 2271 size_type max_bucket_count() const _NOEXCEPT 2272 {return __table_.max_bucket_count();} 2273 2274 _LIBCPP_INLINE_VISIBILITY 2275 size_type bucket_size(size_type __n) const 2276 {return __table_.bucket_size(__n);} 2277 _LIBCPP_INLINE_VISIBILITY 2278 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 2279 2280 _LIBCPP_INLINE_VISIBILITY 2281 local_iterator begin(size_type __n) {return __table_.begin(__n);} 2282 _LIBCPP_INLINE_VISIBILITY 2283 local_iterator end(size_type __n) {return __table_.end(__n);} 2284 _LIBCPP_INLINE_VISIBILITY 2285 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 2286 _LIBCPP_INLINE_VISIBILITY 2287 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 2288 _LIBCPP_INLINE_VISIBILITY 2289 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 2290 _LIBCPP_INLINE_VISIBILITY 2291 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 2292 2293 _LIBCPP_INLINE_VISIBILITY 2294 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 2295 _LIBCPP_INLINE_VISIBILITY 2296 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 2297 _LIBCPP_INLINE_VISIBILITY 2298 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 2299 _LIBCPP_INLINE_VISIBILITY 2300 void rehash(size_type __n) {__table_.rehash(__n);} 2301 _LIBCPP_INLINE_VISIBILITY 2302 void reserve(size_type __n) {__table_.reserve(__n);} 2303 2304#ifdef _LIBCPP_ENABLE_DEBUG_MODE 2305 2306 bool __dereferenceable(const const_iterator* __i) const 2307 {return __table_.__dereferenceable(_VSTD::addressof(__i->__i_));} 2308 bool __decrementable(const const_iterator* __i) const 2309 {return __table_.__decrementable(_VSTD::addressof(__i->__i_));} 2310 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 2311 {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);} 2312 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 2313 {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);} 2314 2315#endif // _LIBCPP_ENABLE_DEBUG_MODE 2316 2317 2318}; 2319 2320#if _LIBCPP_STD_VER >= 17 2321template<class _InputIterator, 2322 class _Hash = hash<__iter_key_type<_InputIterator>>, 2323 class _Pred = equal_to<__iter_key_type<_InputIterator>>, 2324 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 2325 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 2326 class = enable_if_t<!__is_allocator<_Hash>::value>, 2327 class = enable_if_t<!is_integral<_Hash>::value>, 2328 class = enable_if_t<!__is_allocator<_Pred>::value>, 2329 class = enable_if_t<__is_allocator<_Allocator>::value>> 2330unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0, 2331 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 2332 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>; 2333 2334template<class _Key, class _Tp, class _Hash = hash<remove_const_t<_Key>>, 2335 class _Pred = equal_to<remove_const_t<_Key>>, 2336 class _Allocator = allocator<pair<const _Key, _Tp>>, 2337 class = enable_if_t<!__is_allocator<_Hash>::value>, 2338 class = enable_if_t<!is_integral<_Hash>::value>, 2339 class = enable_if_t<!__is_allocator<_Pred>::value>, 2340 class = enable_if_t<__is_allocator<_Allocator>::value>> 2341unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type = 0, 2342 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 2343 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>; 2344 2345template<class _InputIterator, class _Allocator, 2346 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 2347 class = enable_if_t<__is_allocator<_Allocator>::value>> 2348unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 2349 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 2350 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; 2351 2352template<class _InputIterator, class _Allocator, 2353 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 2354 class = enable_if_t<__is_allocator<_Allocator>::value>> 2355unordered_multimap(_InputIterator, _InputIterator, _Allocator) 2356 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 2357 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; 2358 2359template<class _InputIterator, class _Hash, class _Allocator, 2360 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 2361 class = enable_if_t<!__is_allocator<_Hash>::value>, 2362 class = enable_if_t<!is_integral<_Hash>::value>, 2363 class = enable_if_t<__is_allocator<_Allocator>::value>> 2364unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 2365 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 2366 _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; 2367 2368template<class _Key, class _Tp, class _Allocator, 2369 class = enable_if_t<__is_allocator<_Allocator>::value>> 2370unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator) 2371 -> unordered_multimap<remove_const_t<_Key>, _Tp, 2372 hash<remove_const_t<_Key>>, 2373 equal_to<remove_const_t<_Key>>, _Allocator>; 2374 2375template<class _Key, class _Tp, class _Allocator, 2376 class = enable_if_t<__is_allocator<_Allocator>::value>> 2377unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 2378 -> unordered_multimap<remove_const_t<_Key>, _Tp, 2379 hash<remove_const_t<_Key>>, 2380 equal_to<remove_const_t<_Key>>, _Allocator>; 2381 2382template<class _Key, class _Tp, class _Hash, class _Allocator, 2383 class = enable_if_t<!__is_allocator<_Hash>::value>, 2384 class = enable_if_t<!is_integral<_Hash>::value>, 2385 class = enable_if_t<__is_allocator<_Allocator>::value>> 2386unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 2387 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, 2388 equal_to<remove_const_t<_Key>>, _Allocator>; 2389#endif 2390 2391template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2392unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2393 size_type __n, const hasher& __hf, const key_equal& __eql) 2394 : __table_(__hf, __eql) 2395{ 2396 _VSTD::__debug_db_insert_c(this); 2397 __table_.rehash(__n); 2398} 2399 2400template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2401unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2402 size_type __n, const hasher& __hf, const key_equal& __eql, 2403 const allocator_type& __a) 2404 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 2405{ 2406 _VSTD::__debug_db_insert_c(this); 2407 __table_.rehash(__n); 2408} 2409 2410template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2411template <class _InputIterator> 2412unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2413 _InputIterator __first, _InputIterator __last) 2414{ 2415 _VSTD::__debug_db_insert_c(this); 2416 insert(__first, __last); 2417} 2418 2419template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2420template <class _InputIterator> 2421unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2422 _InputIterator __first, _InputIterator __last, size_type __n, 2423 const hasher& __hf, const key_equal& __eql) 2424 : __table_(__hf, __eql) 2425{ 2426 _VSTD::__debug_db_insert_c(this); 2427 __table_.rehash(__n); 2428 insert(__first, __last); 2429} 2430 2431template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2432template <class _InputIterator> 2433unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2434 _InputIterator __first, _InputIterator __last, size_type __n, 2435 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 2436 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 2437{ 2438 _VSTD::__debug_db_insert_c(this); 2439 __table_.rehash(__n); 2440 insert(__first, __last); 2441} 2442 2443template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2444inline 2445unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2446 const allocator_type& __a) 2447 : __table_(typename __table::allocator_type(__a)) 2448{ 2449 _VSTD::__debug_db_insert_c(this); 2450} 2451 2452template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2453unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2454 const unordered_multimap& __u) 2455 : __table_(__u.__table_) 2456{ 2457 _VSTD::__debug_db_insert_c(this); 2458 __table_.rehash(__u.bucket_count()); 2459 insert(__u.begin(), __u.end()); 2460} 2461 2462template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2463unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2464 const unordered_multimap& __u, const allocator_type& __a) 2465 : __table_(__u.__table_, typename __table::allocator_type(__a)) 2466{ 2467 _VSTD::__debug_db_insert_c(this); 2468 __table_.rehash(__u.bucket_count()); 2469 insert(__u.begin(), __u.end()); 2470} 2471 2472#ifndef _LIBCPP_CXX03_LANG 2473 2474template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2475inline 2476unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2477 unordered_multimap&& __u) 2478 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 2479 : __table_(_VSTD::move(__u.__table_)) 2480{ 2481 _VSTD::__debug_db_insert_c(this); 2482 std::__debug_db_swap(this, std::addressof(__u)); 2483} 2484 2485template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2486unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2487 unordered_multimap&& __u, const allocator_type& __a) 2488 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a)) 2489{ 2490 _VSTD::__debug_db_insert_c(this); 2491 if (__a != __u.get_allocator()) 2492 { 2493 iterator __i = __u.begin(); 2494 while (__u.size() != 0) 2495 { 2496 __table_.__insert_multi( 2497 __u.__table_.remove((__i++).__i_)->__value_.__move()); 2498 } 2499 } 2500 else 2501 std::__debug_db_swap(this, std::addressof(__u)); 2502} 2503 2504template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2505unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2506 initializer_list<value_type> __il) 2507{ 2508 _VSTD::__debug_db_insert_c(this); 2509 insert(__il.begin(), __il.end()); 2510} 2511 2512template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2513unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2514 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 2515 const key_equal& __eql) 2516 : __table_(__hf, __eql) 2517{ 2518 _VSTD::__debug_db_insert_c(this); 2519 __table_.rehash(__n); 2520 insert(__il.begin(), __il.end()); 2521} 2522 2523template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2524unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2525 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 2526 const key_equal& __eql, const allocator_type& __a) 2527 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 2528{ 2529 _VSTD::__debug_db_insert_c(this); 2530 __table_.rehash(__n); 2531 insert(__il.begin(), __il.end()); 2532} 2533 2534template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2535inline 2536unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2537unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 2538 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 2539{ 2540 __table_ = _VSTD::move(__u.__table_); 2541 return *this; 2542} 2543 2544template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2545inline 2546unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2547unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 2548 initializer_list<value_type> __il) 2549{ 2550 __table_.__assign_multi(__il.begin(), __il.end()); 2551 return *this; 2552} 2553 2554#endif // _LIBCPP_CXX03_LANG 2555 2556 2557 2558template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2559template <class _InputIterator> 2560inline 2561void 2562unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 2563 _InputIterator __last) 2564{ 2565 for (; __first != __last; ++__first) 2566 __table_.__insert_multi(*__first); 2567} 2568 2569template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2570inline _LIBCPP_INLINE_VISIBILITY 2571void 2572swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2573 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2574 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2575{ 2576 __x.swap(__y); 2577} 2578 2579#if _LIBCPP_STD_VER > 17 2580template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 2581 class _Predicate> 2582inline _LIBCPP_INLINE_VISIBILITY 2583 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type 2584 erase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, 2585 _Predicate __pred) { 2586 return _VSTD::__libcpp_erase_if_container(__c, __pred); 2587} 2588#endif 2589 2590template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2591bool 2592operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2593 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2594{ 2595 if (__x.size() != __y.size()) 2596 return false; 2597 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 2598 const_iterator; 2599 typedef pair<const_iterator, const_iterator> _EqRng; 2600 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 2601 { 2602 _EqRng __xeq = __x.equal_range(__i->first); 2603 _EqRng __yeq = __y.equal_range(__i->first); 2604 if (_VSTD::distance(__xeq.first, __xeq.second) != 2605 _VSTD::distance(__yeq.first, __yeq.second) || 2606 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2607 return false; 2608 __i = __xeq.second; 2609 } 2610 return true; 2611} 2612 2613template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2614inline _LIBCPP_INLINE_VISIBILITY 2615bool 2616operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2617 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2618{ 2619 return !(__x == __y); 2620} 2621 2622_LIBCPP_END_NAMESPACE_STD 2623 2624#endif // _LIBCPP_UNORDERED_MAP 2625