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