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#include <__algorithm/is_permutation.h> 587#include <__assert> 588#include <__config> 589#include <__functional/hash.h> 590#include <__functional/is_transparent.h> 591#include <__functional/operations.h> 592#include <__hash_table> 593#include <__iterator/distance.h> 594#include <__iterator/erase_if_container.h> 595#include <__iterator/iterator_traits.h> 596#include <__iterator/ranges_iterator_traits.h> 597#include <__memory/addressof.h> 598#include <__memory/allocator.h> 599#include <__memory/allocator_traits.h> 600#include <__memory/pointer_traits.h> 601#include <__memory/unique_ptr.h> 602#include <__memory_resource/polymorphic_allocator.h> 603#include <__node_handle> 604#include <__ranges/concepts.h> 605#include <__ranges/container_compatible_range.h> 606#include <__ranges/from_range.h> 607#include <__type_traits/container_traits.h> 608#include <__type_traits/enable_if.h> 609#include <__type_traits/invoke.h> 610#include <__type_traits/is_allocator.h> 611#include <__type_traits/is_integral.h> 612#include <__type_traits/remove_const.h> 613#include <__type_traits/type_identity.h> 614#include <__utility/forward.h> 615#include <__utility/pair.h> 616#include <new> // launder 617#include <stdexcept> 618#include <tuple> 619#include <version> 620 621// standard-mandated includes 622 623// [iterator.range] 624#include <__iterator/access.h> 625#include <__iterator/data.h> 626#include <__iterator/empty.h> 627#include <__iterator/reverse_access.h> 628#include <__iterator/size.h> 629 630// [unord.map.syn] 631#include <compare> 632#include <initializer_list> 633 634#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 635# pragma GCC system_header 636#endif 637 638_LIBCPP_PUSH_MACROS 639#include <__undef_macros> 640 641_LIBCPP_BEGIN_NAMESPACE_STD 642 643template <class _Key, 644 class _Cp, 645 class _Hash, 646 class _Pred, 647 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value> 648class __unordered_map_hasher : private _Hash { 649public: 650 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) : _Hash() {} 651 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 652 : _Hash(__h) {} 653 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return *this; } 654 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { 655 return static_cast<const _Hash&>(*this)(__x.__get_value().first); 656 } 657 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return static_cast<const _Hash&>(*this)(__x); } 658#if _LIBCPP_STD_VER >= 20 659 template <typename _K2> 660 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const { 661 return static_cast<const _Hash&>(*this)(__x); 662 } 663#endif 664 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Hash>) { 665 using std::swap; 666 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y)); 667 } 668}; 669 670template <class _Key, class _Cp, class _Hash, class _Pred> 671class __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false> { 672 _Hash __hash_; 673 674public: 675 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 676 : __hash_() {} 677 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 678 : __hash_(__h) {} 679 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return __hash_; } 680 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return __hash_(__x.__get_value().first); } 681 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return __hash_(__x); } 682#if _LIBCPP_STD_VER >= 20 683 template <typename _K2> 684 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const { 685 return __hash_(__x); 686 } 687#endif 688 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Hash>) { 689 using std::swap; 690 swap(__hash_, __y.__hash_); 691 } 692}; 693 694template <class _Key, class _Cp, class _Hash, class _Pred, bool __b> 695inline _LIBCPP_HIDE_FROM_ABI void 696swap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x, 697 __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 698 __x.swap(__y); 699} 700 701template <class _Key, 702 class _Cp, 703 class _Pred, 704 class _Hash, 705 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value> 706class __unordered_map_equal : private _Pred { 707public: 708 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) : _Pred() {} 709 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 710 : _Pred(__p) {} 711 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return *this; } 712 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const { 713 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first); 714 } 715 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const { 716 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y); 717 } 718 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const { 719 return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first); 720 } 721#if _LIBCPP_STD_VER >= 20 722 template <typename _K2> 723 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const { 724 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y); 725 } 726 template <typename _K2> 727 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const { 728 return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first); 729 } 730 template <typename _K2> 731 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const { 732 return static_cast<const _Pred&>(*this)(__x, __y); 733 } 734 template <typename _K2> 735 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const { 736 return static_cast<const _Pred&>(*this)(__x, __y); 737 } 738#endif 739 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Pred>) { 740 using std::swap; 741 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y)); 742 } 743}; 744 745template <class _Key, class _Cp, class _Pred, class _Hash> 746class __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false> { 747 _Pred __pred_; 748 749public: 750 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 751 : __pred_() {} 752 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 753 : __pred_(__p) {} 754 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return __pred_; } 755 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const { 756 return __pred_(__x.__get_value().first, __y.__get_value().first); 757 } 758 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const { 759 return __pred_(__x.__get_value().first, __y); 760 } 761 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const { 762 return __pred_(__x, __y.__get_value().first); 763 } 764#if _LIBCPP_STD_VER >= 20 765 template <typename _K2> 766 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const { 767 return __pred_(__x.__get_value().first, __y); 768 } 769 template <typename _K2> 770 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const { 771 return __pred_(__x, __y.__get_value().first); 772 } 773 template <typename _K2> 774 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const { 775 return __pred_(__x, __y); 776 } 777 template <typename _K2> 778 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const { 779 return __pred_(__x, __y); 780 } 781#endif 782 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Pred>) { 783 using std::swap; 784 swap(__pred_, __y.__pred_); 785 } 786}; 787 788template <class _Key, class _Cp, class _Pred, class _Hash, bool __b> 789inline _LIBCPP_HIDE_FROM_ABI void 790swap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x, __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y) 791 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 792 __x.swap(__y); 793} 794 795template <class _Alloc> 796class __hash_map_node_destructor { 797 typedef _Alloc allocator_type; 798 typedef allocator_traits<allocator_type> __alloc_traits; 799 800public: 801 typedef typename __alloc_traits::pointer pointer; 802 803private: 804 allocator_type& __na_; 805 806public: 807 bool __first_constructed; 808 bool __second_constructed; 809 810 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete; 811 812 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 813 : __na_(__na), 814 __first_constructed(false), 815 __second_constructed(false) {} 816 817#ifndef _LIBCPP_CXX03_LANG 818 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) _NOEXCEPT 819 : __na_(__x.__na_), 820 __first_constructed(__x.__value_constructed), 821 __second_constructed(__x.__value_constructed) { 822 __x.__value_constructed = false; 823 } 824#else // _LIBCPP_CXX03_LANG 825 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 826 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) { 827 const_cast<bool&>(__x.__value_constructed) = false; 828 } 829#endif // _LIBCPP_CXX03_LANG 830 831 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { 832 if (__second_constructed) 833 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().second)); 834 if (__first_constructed) 835 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().first)); 836 if (__p) 837 __alloc_traits::deallocate(__na_, __p, 1); 838 } 839}; 840 841#ifndef _LIBCPP_CXX03_LANG 842template <class _Key, class _Tp> 843struct _LIBCPP_STANDALONE_DEBUG __hash_value_type { 844 typedef _Key key_type; 845 typedef _Tp mapped_type; 846 typedef pair<const key_type, mapped_type> value_type; 847 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type; 848 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type; 849 850private: 851 value_type __cc_; 852 853public: 854 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { 855# if _LIBCPP_STD_VER >= 17 856 return *std::launder(std::addressof(__cc_)); 857# else 858 return __cc_; 859# endif 860 } 861 862 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { 863# if _LIBCPP_STD_VER >= 17 864 return *std::launder(std::addressof(__cc_)); 865# else 866 return __cc_; 867# endif 868 } 869 870 _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() { 871 value_type& __v = __get_value(); 872 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second); 873 } 874 875 _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() { 876 value_type& __v = __get_value(); 877 return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second)); 878 } 879 880 _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(const __hash_value_type& __v) { 881 __ref() = __v.__get_value(); 882 return *this; 883 } 884 885 _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(__hash_value_type&& __v) { 886 __ref() = __v.__move(); 887 return *this; 888 } 889 890 template <class _ValueTp, __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value, int> = 0> 891 _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(_ValueTp&& __v) { 892 __ref() = std::forward<_ValueTp>(__v); 893 return *this; 894 } 895 896 __hash_value_type(const __hash_value_type& __v) = delete; 897 __hash_value_type(__hash_value_type&& __v) = delete; 898 template <class... _Args> 899 explicit __hash_value_type(_Args&&... __args) = delete; 900 901 ~__hash_value_type() = delete; 902}; 903 904#else 905 906template <class _Key, class _Tp> 907struct __hash_value_type { 908 typedef _Key key_type; 909 typedef _Tp mapped_type; 910 typedef pair<const key_type, mapped_type> value_type; 911 912private: 913 value_type __cc_; 914 915public: 916 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; } 917 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; } 918 919 ~__hash_value_type() = delete; 920}; 921 922#endif 923 924template <class _HashIterator> 925class _LIBCPP_TEMPLATE_VIS __hash_map_iterator { 926 _HashIterator __i_; 927 928 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; 929 930public: 931 typedef forward_iterator_tag iterator_category; 932 typedef typename _NodeTypes::__map_value_type value_type; 933 typedef typename _NodeTypes::difference_type difference_type; 934 typedef value_type& reference; 935 typedef typename _NodeTypes::__map_value_type_pointer pointer; 936 937 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() _NOEXCEPT {} 938 939 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 940 941 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); } 942 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); } 943 944 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() { 945 ++__i_; 946 return *this; 947 } 948 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) { 949 __hash_map_iterator __t(*this); 950 ++(*this); 951 return __t; 952 } 953 954 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { 955 return __x.__i_ == __y.__i_; 956 } 957#if _LIBCPP_STD_VER <= 17 958 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { 959 return __x.__i_ != __y.__i_; 960 } 961#endif 962 963 template <class, class, class, class, class> 964 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 965 template <class, class, class, class, class> 966 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 967 template <class> 968 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 969 template <class> 970 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 971 template <class> 972 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 973}; 974 975template <class _HashIterator> 976class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator { 977 _HashIterator __i_; 978 979 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; 980 981public: 982 typedef forward_iterator_tag iterator_category; 983 typedef typename _NodeTypes::__map_value_type value_type; 984 typedef typename _NodeTypes::difference_type difference_type; 985 typedef const value_type& reference; 986 typedef typename _NodeTypes::__const_map_value_type_pointer pointer; 987 988 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() _NOEXCEPT {} 989 990 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 991 _LIBCPP_HIDE_FROM_ABI 992 __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) _NOEXCEPT 993 : __i_(__i.__i_) {} 994 995 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); } 996 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); } 997 998 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() { 999 ++__i_; 1000 return *this; 1001 } 1002 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) { 1003 __hash_map_const_iterator __t(*this); 1004 ++(*this); 1005 return __t; 1006 } 1007 1008 friend _LIBCPP_HIDE_FROM_ABI bool 1009 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { 1010 return __x.__i_ == __y.__i_; 1011 } 1012#if _LIBCPP_STD_VER <= 17 1013 friend _LIBCPP_HIDE_FROM_ABI bool 1014 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { 1015 return __x.__i_ != __y.__i_; 1016 } 1017#endif 1018 1019 template <class, class, class, class, class> 1020 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1021 template <class, class, class, class, class> 1022 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1023 template <class> 1024 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 1025 template <class> 1026 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 1027}; 1028 1029template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1030class unordered_multimap; 1031 1032template <class _Key, 1033 class _Tp, 1034 class _Hash = hash<_Key>, 1035 class _Pred = equal_to<_Key>, 1036 class _Alloc = allocator<pair<const _Key, _Tp> > > 1037class _LIBCPP_TEMPLATE_VIS unordered_map { 1038public: 1039 // types 1040 typedef _Key key_type; 1041 typedef _Tp mapped_type; 1042 typedef __type_identity_t<_Hash> hasher; 1043 typedef __type_identity_t<_Pred> key_equal; 1044 typedef __type_identity_t<_Alloc> allocator_type; 1045 typedef pair<const key_type, mapped_type> value_type; 1046 typedef value_type& reference; 1047 typedef const value_type& const_reference; 1048 static_assert(is_same<value_type, typename allocator_type::value_type>::value, 1049 "Allocator::value_type must be same type as value_type"); 1050 1051private: 1052 typedef __hash_value_type<key_type, mapped_type> __value_type; 1053 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher; 1054 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal; 1055 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; 1056 1057 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; 1058 1059 __table __table_; 1060 1061 typedef typename __table::_NodeTypes _NodeTypes; 1062 typedef typename __table::__node_pointer __node_pointer; 1063 typedef typename __table::__node_const_pointer __node_const_pointer; 1064 typedef typename __table::__node_traits __node_traits; 1065 typedef typename __table::__node_allocator __node_allocator; 1066 typedef typename __table::__node __node; 1067 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1068 typedef unique_ptr<__node, _Dp> __node_holder; 1069 typedef allocator_traits<allocator_type> __alloc_traits; 1070 1071 static_assert(__check_valid_allocator<allocator_type>::value, ""); 1072 1073 static_assert(is_same<typename __table::__container_value_type, value_type>::value, ""); 1074 static_assert(is_same<typename __table::__node_value_type, __value_type>::value, ""); 1075 1076public: 1077 typedef typename __alloc_traits::pointer pointer; 1078 typedef typename __alloc_traits::const_pointer const_pointer; 1079 typedef typename __table::size_type size_type; 1080 typedef typename __table::difference_type difference_type; 1081 1082 typedef __hash_map_iterator<typename __table::iterator> iterator; 1083 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1084 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1085 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1086 1087#if _LIBCPP_STD_VER >= 17 1088 typedef __map_node_handle<__node, allocator_type> node_type; 1089 typedef __insert_return_type<iterator, node_type> insert_return_type; 1090#endif 1091 1092 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1093 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1094 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1095 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1096 1097 _LIBCPP_HIDE_FROM_ABI unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 1098 explicit _LIBCPP_HIDE_FROM_ABI 1099 unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 1100 _LIBCPP_HIDE_FROM_ABI 1101 unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 1102 template <class _InputIterator> 1103 _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last); 1104 template <class _InputIterator> 1105 _LIBCPP_HIDE_FROM_ABI 1106 unordered_map(_InputIterator __first, 1107 _InputIterator __last, 1108 size_type __n, 1109 const hasher& __hf = hasher(), 1110 const key_equal& __eql = key_equal()); 1111 template <class _InputIterator> 1112 _LIBCPP_HIDE_FROM_ABI unordered_map( 1113 _InputIterator __first, 1114 _InputIterator __last, 1115 size_type __n, 1116 const hasher& __hf, 1117 const key_equal& __eql, 1118 const allocator_type& __a); 1119 1120#if _LIBCPP_STD_VER >= 23 1121 template <_ContainerCompatibleRange<value_type> _Range> 1122 _LIBCPP_HIDE_FROM_ABI unordered_map( 1123 from_range_t, 1124 _Range&& __range, 1125 size_type __n = /*implementation-defined*/ 0, 1126 const hasher& __hf = hasher(), 1127 const key_equal& __eql = key_equal(), 1128 const allocator_type& __a = allocator_type()) 1129 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1130 if (__n > 0) { 1131 __table_.__rehash_unique(__n); 1132 } 1133 insert_range(std::forward<_Range>(__range)); 1134 } 1135#endif 1136 1137 _LIBCPP_HIDE_FROM_ABI explicit unordered_map(const allocator_type& __a); 1138 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u); 1139 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a); 1140#ifndef _LIBCPP_CXX03_LANG 1141 _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1142 _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u, const allocator_type& __a); 1143 _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il); 1144 _LIBCPP_HIDE_FROM_ABI 1145 unordered_map(initializer_list<value_type> __il, 1146 size_type __n, 1147 const hasher& __hf = hasher(), 1148 const key_equal& __eql = key_equal()); 1149 _LIBCPP_HIDE_FROM_ABI unordered_map( 1150 initializer_list<value_type> __il, 1151 size_type __n, 1152 const hasher& __hf, 1153 const key_equal& __eql, 1154 const allocator_type& __a); 1155#endif // _LIBCPP_CXX03_LANG 1156#if _LIBCPP_STD_VER >= 14 1157 _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const allocator_type& __a) 1158 : unordered_map(__n, hasher(), key_equal(), __a) {} 1159 _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a) 1160 : unordered_map(__n, __hf, key_equal(), __a) {} 1161 template <class _InputIterator> 1162 _LIBCPP_HIDE_FROM_ABI 1163 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1164 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} 1165 template <class _InputIterator> 1166 _LIBCPP_HIDE_FROM_ABI unordered_map( 1167 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 1168 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} 1169 1170# if _LIBCPP_STD_VER >= 23 1171 template <_ContainerCompatibleRange<value_type> _Range> 1172 _LIBCPP_HIDE_FROM_ABI unordered_map(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 1173 : unordered_map(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 1174 1175 template <_ContainerCompatibleRange<value_type> _Range> 1176 _LIBCPP_HIDE_FROM_ABI 1177 unordered_map(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 1178 : unordered_map(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 1179# endif 1180 1181 _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1182 : unordered_map(__il, __n, hasher(), key_equal(), __a) {} 1183 _LIBCPP_HIDE_FROM_ABI 1184 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 1185 : unordered_map(__il, __n, __hf, key_equal(), __a) {} 1186#endif 1187 _LIBCPP_HIDE_FROM_ABI ~unordered_map() { 1188 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), ""); 1189 } 1190 1191 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(const unordered_map& __u) { 1192#ifndef _LIBCPP_CXX03_LANG 1193 __table_ = __u.__table_; 1194#else 1195 if (this != std::addressof(__u)) { 1196 __table_.clear(); 1197 __table_.hash_function() = __u.__table_.hash_function(); 1198 __table_.key_eq() = __u.__table_.key_eq(); 1199 __table_.max_load_factor() = __u.__table_.max_load_factor(); 1200 __table_.__copy_assign_alloc(__u.__table_); 1201 insert(__u.begin(), __u.end()); 1202 } 1203#endif 1204 return *this; 1205 } 1206#ifndef _LIBCPP_CXX03_LANG 1207 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(unordered_map&& __u) 1208 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1209 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(initializer_list<value_type> __il); 1210#endif // _LIBCPP_CXX03_LANG 1211 1212 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 1213 return allocator_type(__table_.__node_alloc()); 1214 } 1215 1216 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 1217 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 1218 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 1219 1220 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 1221 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 1222 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 1223 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 1224 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 1225 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 1226 1227 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); } 1228 1229 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } 1230 1231 template <class _InputIterator> 1232 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 1233 1234#if _LIBCPP_STD_VER >= 23 1235 template <_ContainerCompatibleRange<value_type> _Range> 1236 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 1237 for (auto&& __element : __range) { 1238 __table_.__insert_unique(std::forward<decltype(__element)>(__element)); 1239 } 1240 } 1241#endif 1242 1243#ifndef _LIBCPP_CXX03_LANG 1244 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 1245 1246 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) { 1247 return __table_.__insert_unique(std::move(__x)); 1248 } 1249 1250 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { 1251 return __table_.__insert_unique(std::move(__x)).first; 1252 } 1253 1254 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0> 1255 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __x) { 1256 return __table_.__insert_unique(std::forward<_Pp>(__x)); 1257 } 1258 1259 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0> 1260 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, _Pp&& __x) { 1261 return insert(std::forward<_Pp>(__x)).first; 1262 } 1263 1264 template <class... _Args> 1265 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) { 1266 return __table_.__emplace_unique(std::forward<_Args>(__args)...); 1267 } 1268 1269 template <class... _Args> 1270 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) { 1271 return __table_.__emplace_unique(std::forward<_Args>(__args)...).first; 1272 } 1273 1274#endif // _LIBCPP_CXX03_LANG 1275 1276#if _LIBCPP_STD_VER >= 17 1277 template <class... _Args> 1278 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) { 1279 return __table_.__emplace_unique_key_args( 1280 __k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...)); 1281 } 1282 1283 template <class... _Args> 1284 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) { 1285 return __table_.__emplace_unique_key_args( 1286 __k, 1287 piecewise_construct, 1288 std::forward_as_tuple(std::move(__k)), 1289 std::forward_as_tuple(std::forward<_Args>(__args)...)); 1290 } 1291 1292 template <class... _Args> 1293 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, const key_type& __k, _Args&&... __args) { 1294 return try_emplace(__k, std::forward<_Args>(__args)...).first; 1295 } 1296 1297 template <class... _Args> 1298 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, key_type&& __k, _Args&&... __args) { 1299 return try_emplace(std::move(__k), std::forward<_Args>(__args)...).first; 1300 } 1301 1302 template <class _Vp> 1303 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) { 1304 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, __k, std::forward<_Vp>(__v)); 1305 if (!__res.second) { 1306 __res.first->second = std::forward<_Vp>(__v); 1307 } 1308 return __res; 1309 } 1310 1311 template <class _Vp> 1312 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) { 1313 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, std::move(__k), std::forward<_Vp>(__v)); 1314 if (!__res.second) { 1315 __res.first->second = std::forward<_Vp>(__v); 1316 } 1317 return __res; 1318 } 1319 1320 template <class _Vp> 1321 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v) { 1322 return insert_or_assign(__k, std::forward<_Vp>(__v)).first; 1323 } 1324 1325 template <class _Vp> 1326 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v) { 1327 return insert_or_assign(std::move(__k), std::forward<_Vp>(__v)).first; 1328 } 1329#endif // _LIBCPP_STD_VER >= 17 1330 1331 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); } 1332 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); } 1333 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } 1334 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 1335 return __table_.erase(__first.__i_, __last.__i_); 1336 } 1337 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 1338 1339#if _LIBCPP_STD_VER >= 17 1340 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) { 1341 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1342 "node_type with incompatible allocator passed to unordered_map::insert()"); 1343 return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh)); 1344 } 1345 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 1346 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1347 "node_type with incompatible allocator passed to unordered_map::insert()"); 1348 return __table_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh)); 1349 } 1350 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 1351 return __table_.template __node_handle_extract<node_type>(__key); 1352 } 1353 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 1354 return __table_.template __node_handle_extract<node_type>(__it.__i_); 1355 } 1356 1357 template <class _H2, class _P2> 1358 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { 1359 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1360 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1361 return __table_.__node_handle_merge_unique(__source.__table_); 1362 } 1363 template <class _H2, class _P2> 1364 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { 1365 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1366 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1367 return __table_.__node_handle_merge_unique(__source.__table_); 1368 } 1369 template <class _H2, class _P2> 1370 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { 1371 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1372 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1373 return __table_.__node_handle_merge_unique(__source.__table_); 1374 } 1375 template <class _H2, class _P2> 1376 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { 1377 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1378 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1379 return __table_.__node_handle_merge_unique(__source.__table_); 1380 } 1381#endif 1382 1383 _LIBCPP_HIDE_FROM_ABI void swap(unordered_map& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) { 1384 __table_.swap(__u.__table_); 1385 } 1386 1387 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); } 1388 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } 1389 1390 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 1391 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 1392#if _LIBCPP_STD_VER >= 20 1393 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1394 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 1395 return __table_.find(__k); 1396 } 1397 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1398 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 1399 return __table_.find(__k); 1400 } 1401#endif // _LIBCPP_STD_VER >= 20 1402 1403 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } 1404#if _LIBCPP_STD_VER >= 20 1405 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1406 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 1407 return __table_.__count_unique(__k); 1408 } 1409#endif // _LIBCPP_STD_VER >= 20 1410 1411#if _LIBCPP_STD_VER >= 20 1412 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 1413 1414 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1415 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 1416 return find(__k) != end(); 1417 } 1418#endif // _LIBCPP_STD_VER >= 20 1419 1420 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1421 return __table_.__equal_range_unique(__k); 1422 } 1423 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1424 return __table_.__equal_range_unique(__k); 1425 } 1426#if _LIBCPP_STD_VER >= 20 1427 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1428 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 1429 return __table_.__equal_range_unique(__k); 1430 } 1431 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1432 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 1433 return __table_.__equal_range_unique(__k); 1434 } 1435#endif // _LIBCPP_STD_VER >= 20 1436 1437 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); 1438#ifndef _LIBCPP_CXX03_LANG 1439 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k); 1440#endif 1441 1442 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k); 1443 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const; 1444 1445 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 1446 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 1447 1448 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 1449 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 1450 1451 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 1452 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 1453 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 1454 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 1455 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 1456 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 1457 1458 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 1459 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 1460 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 1461 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); } 1462 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); } 1463 1464private: 1465#ifdef _LIBCPP_CXX03_LANG 1466 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k); 1467#endif 1468}; 1469 1470#if _LIBCPP_STD_VER >= 17 1471template <class _InputIterator, 1472 class _Hash = hash<__iter_key_type<_InputIterator>>, 1473 class _Pred = equal_to<__iter_key_type<_InputIterator>>, 1474 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 1475 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1476 class = enable_if_t<!__is_allocator<_Hash>::value>, 1477 class = enable_if_t<!is_integral<_Hash>::value>, 1478 class = enable_if_t<!__is_allocator<_Pred>::value>, 1479 class = enable_if_t<__is_allocator<_Allocator>::value>> 1480unordered_map(_InputIterator, 1481 _InputIterator, 1482 typename allocator_traits<_Allocator>::size_type = 0, 1483 _Hash = _Hash(), 1484 _Pred = _Pred(), 1485 _Allocator = _Allocator()) 1486 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>; 1487 1488# if _LIBCPP_STD_VER >= 23 1489template <ranges::input_range _Range, 1490 class _Hash = hash<__range_key_type<_Range>>, 1491 class _Pred = equal_to<__range_key_type<_Range>>, 1492 class _Allocator = allocator<__range_to_alloc_type<_Range>>, 1493 class = enable_if_t<!__is_allocator<_Hash>::value>, 1494 class = enable_if_t<!is_integral<_Hash>::value>, 1495 class = enable_if_t<!__is_allocator<_Pred>::value>, 1496 class = enable_if_t<__is_allocator<_Allocator>::value>> 1497unordered_map(from_range_t, 1498 _Range&&, 1499 typename allocator_traits<_Allocator>::size_type = 0, 1500 _Hash = _Hash(), 1501 _Pred = _Pred(), 1502 _Allocator = _Allocator()) 1503 -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; // C++23 1504# endif 1505 1506template <class _Key, 1507 class _Tp, 1508 class _Hash = hash<remove_const_t<_Key>>, 1509 class _Pred = equal_to<remove_const_t<_Key>>, 1510 class _Allocator = allocator<pair<const _Key, _Tp>>, 1511 class = enable_if_t<!__is_allocator<_Hash>::value>, 1512 class = enable_if_t<!is_integral<_Hash>::value>, 1513 class = enable_if_t<!__is_allocator<_Pred>::value>, 1514 class = enable_if_t<__is_allocator<_Allocator>::value>> 1515unordered_map(initializer_list<pair<_Key, _Tp>>, 1516 typename allocator_traits<_Allocator>::size_type = 0, 1517 _Hash = _Hash(), 1518 _Pred = _Pred(), 1519 _Allocator = _Allocator()) -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>; 1520 1521template <class _InputIterator, 1522 class _Allocator, 1523 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1524 class = enable_if_t<__is_allocator<_Allocator>::value>> 1525unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 1526 -> unordered_map<__iter_key_type<_InputIterator>, 1527 __iter_mapped_type<_InputIterator>, 1528 hash<__iter_key_type<_InputIterator>>, 1529 equal_to<__iter_key_type<_InputIterator>>, 1530 _Allocator>; 1531 1532template <class _InputIterator, 1533 class _Allocator, 1534 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1535 class = enable_if_t<__is_allocator<_Allocator>::value>> 1536unordered_map(_InputIterator, _InputIterator, _Allocator) 1537 -> unordered_map<__iter_key_type<_InputIterator>, 1538 __iter_mapped_type<_InputIterator>, 1539 hash<__iter_key_type<_InputIterator>>, 1540 equal_to<__iter_key_type<_InputIterator>>, 1541 _Allocator>; 1542 1543template <class _InputIterator, 1544 class _Hash, 1545 class _Allocator, 1546 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1547 class = enable_if_t<!__is_allocator<_Hash>::value>, 1548 class = enable_if_t<!is_integral<_Hash>::value>, 1549 class = enable_if_t<__is_allocator<_Allocator>::value>> 1550unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1551 -> unordered_map<__iter_key_type<_InputIterator>, 1552 __iter_mapped_type<_InputIterator>, 1553 _Hash, 1554 equal_to<__iter_key_type<_InputIterator>>, 1555 _Allocator>; 1556 1557# if _LIBCPP_STD_VER >= 23 1558 1559template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1560unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 1561 -> unordered_map<__range_key_type<_Range>, 1562 __range_mapped_type<_Range>, 1563 hash<__range_key_type<_Range>>, 1564 equal_to<__range_key_type<_Range>>, 1565 _Allocator>; 1566 1567template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1568unordered_map(from_range_t, _Range&&, _Allocator) 1569 -> unordered_map<__range_key_type<_Range>, 1570 __range_mapped_type<_Range>, 1571 hash<__range_key_type<_Range>>, 1572 equal_to<__range_key_type<_Range>>, 1573 _Allocator>; 1574 1575template <ranges::input_range _Range, 1576 class _Hash, 1577 class _Allocator, 1578 class = enable_if_t<!__is_allocator<_Hash>::value>, 1579 class = enable_if_t<!is_integral<_Hash>::value>, 1580 class = enable_if_t<__is_allocator<_Allocator>::value>> 1581unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1582 -> unordered_map<__range_key_type<_Range>, 1583 __range_mapped_type<_Range>, 1584 _Hash, 1585 equal_to<__range_key_type<_Range>>, 1586 _Allocator>; 1587 1588# endif 1589 1590template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1591unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator) 1592 -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>; 1593 1594template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1595unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) 1596 -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>; 1597 1598template <class _Key, 1599 class _Tp, 1600 class _Hash, 1601 class _Allocator, 1602 class = enable_if_t<!__is_allocator<_Hash>::value>, 1603 class = enable_if_t<!is_integral<_Hash>::value>, 1604 class = enable_if_t<__is_allocator<_Allocator>::value>> 1605unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1606 -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>; 1607#endif 1608 1609template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1610unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql) 1611 : __table_(__hf, __eql) { 1612 __table_.__rehash_unique(__n); 1613} 1614 1615template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1616unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1617 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1618 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1619 __table_.__rehash_unique(__n); 1620} 1621 1622template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1623inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const allocator_type& __a) 1624 : __table_(typename __table::allocator_type(__a)) {} 1625 1626template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1627template <class _InputIterator> 1628unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(_InputIterator __first, _InputIterator __last) { 1629 insert(__first, __last); 1630} 1631 1632template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1633template <class _InputIterator> 1634unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1635 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1636 : __table_(__hf, __eql) { 1637 __table_.__rehash_unique(__n); 1638 insert(__first, __last); 1639} 1640 1641template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1642template <class _InputIterator> 1643unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1644 _InputIterator __first, 1645 _InputIterator __last, 1646 size_type __n, 1647 const hasher& __hf, 1648 const key_equal& __eql, 1649 const allocator_type& __a) 1650 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1651 __table_.__rehash_unique(__n); 1652 insert(__first, __last); 1653} 1654 1655template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1656unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u) : __table_(__u.__table_) { 1657 __table_.__rehash_unique(__u.bucket_count()); 1658 insert(__u.begin(), __u.end()); 1659} 1660 1661template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1662unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u, const allocator_type& __a) 1663 : __table_(__u.__table_, typename __table::allocator_type(__a)) { 1664 __table_.__rehash_unique(__u.bucket_count()); 1665 insert(__u.begin(), __u.end()); 1666} 1667 1668#ifndef _LIBCPP_CXX03_LANG 1669 1670template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1671inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u) 1672 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1673 : __table_(std::move(__u.__table_)) {} 1674 1675template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1676unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u, const allocator_type& __a) 1677 : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) { 1678 if (__a != __u.get_allocator()) { 1679 iterator __i = __u.begin(); 1680 while (__u.size() != 0) { 1681 __table_.__emplace_unique(__u.__table_.remove((__i++).__i_)->__get_value().__move()); 1682 } 1683 } 1684} 1685 1686template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1687unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(initializer_list<value_type> __il) { 1688 insert(__il.begin(), __il.end()); 1689} 1690 1691template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1692unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1693 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1694 : __table_(__hf, __eql) { 1695 __table_.__rehash_unique(__n); 1696 insert(__il.begin(), __il.end()); 1697} 1698 1699template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1700unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1701 initializer_list<value_type> __il, 1702 size_type __n, 1703 const hasher& __hf, 1704 const key_equal& __eql, 1705 const allocator_type& __a) 1706 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1707 __table_.__rehash_unique(__n); 1708 insert(__il.begin(), __il.end()); 1709} 1710 1711template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1712inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1713unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1714 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 1715 __table_ = std::move(__u.__table_); 1716 return *this; 1717} 1718 1719template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1720inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1721unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 1722 __table_.__assign_unique(__il.begin(), __il.end()); 1723 return *this; 1724} 1725 1726#endif // _LIBCPP_CXX03_LANG 1727 1728template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1729template <class _InputIterator> 1730inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 1731 for (; __first != __last; ++__first) 1732 __table_.__insert_unique(*__first); 1733} 1734 1735#ifndef _LIBCPP_CXX03_LANG 1736 1737template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1738_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) { 1739 return __table_ 1740 .__emplace_unique_key_args(__k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple()) 1741 .first->__get_value() 1742 .second; 1743} 1744 1745template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1746_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) { 1747 return __table_ 1748 .__emplace_unique_key_args( 1749 __k, piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple()) 1750 .first->__get_value() 1751 .second; 1752} 1753#else // _LIBCPP_CXX03_LANG 1754 1755template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1756typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1757unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) { 1758 __node_allocator& __na = __table_.__node_alloc(); 1759 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1760 __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().first), __k); 1761 __h.get_deleter().__first_constructed = true; 1762 __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().second)); 1763 __h.get_deleter().__second_constructed = true; 1764 return __h; 1765} 1766 1767template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1768_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) { 1769 iterator __i = find(__k); 1770 if (__i != end()) 1771 return __i->second; 1772 __node_holder __h = __construct_node_with_key(__k); 1773 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1774 __h.release(); 1775 return __r.first->second; 1776} 1777 1778#endif // _LIBCPP_CXX03_LANG 1779 1780template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1781_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) { 1782 iterator __i = find(__k); 1783 if (__i == end()) 1784 __throw_out_of_range("unordered_map::at: key not found"); 1785 return __i->second; 1786} 1787 1788template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1789const _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const { 1790 const_iterator __i = find(__k); 1791 if (__i == end()) 1792 __throw_out_of_range("unordered_map::at: key not found"); 1793 return __i->second; 1794} 1795 1796template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1797inline _LIBCPP_HIDE_FROM_ABI void 1798swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1799 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 1800 __x.swap(__y); 1801} 1802 1803#if _LIBCPP_STD_VER >= 20 1804template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate> 1805inline _LIBCPP_HIDE_FROM_ABI typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type 1806erase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 1807 return std::__libcpp_erase_if_container(__c, __pred); 1808} 1809#endif 1810 1811template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1812_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1813 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 1814 if (__x.size() != __y.size()) 1815 return false; 1816 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1817 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { 1818 const_iterator __j = __y.find(__i->first); 1819 if (__j == __ey || !(*__i == *__j)) 1820 return false; 1821 } 1822 return true; 1823} 1824 1825#if _LIBCPP_STD_VER <= 17 1826 1827template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1828inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1829 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 1830 return !(__x == __y); 1831} 1832 1833#endif 1834 1835template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1836struct __container_traits<unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> > { 1837 // http://eel.is/c++draft/unord.req.except#2 1838 // For unordered associative containers, if an exception is thrown by any operation 1839 // other than the container's hash function from within an insert or emplace function 1840 // inserting a single element, the insertion has no effect. 1841 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = 1842 __nothrow_invokable<_Hash, const _Key&>::value; 1843}; 1844 1845template <class _Key, 1846 class _Tp, 1847 class _Hash = hash<_Key>, 1848 class _Pred = equal_to<_Key>, 1849 class _Alloc = allocator<pair<const _Key, _Tp> > > 1850class _LIBCPP_TEMPLATE_VIS unordered_multimap { 1851public: 1852 // types 1853 typedef _Key key_type; 1854 typedef _Tp mapped_type; 1855 typedef __type_identity_t<_Hash> hasher; 1856 typedef __type_identity_t<_Pred> key_equal; 1857 typedef __type_identity_t<_Alloc> allocator_type; 1858 typedef pair<const key_type, mapped_type> value_type; 1859 typedef value_type& reference; 1860 typedef const value_type& const_reference; 1861 static_assert(__check_valid_allocator<allocator_type>::value, ""); 1862 static_assert(is_same<value_type, typename allocator_type::value_type>::value, 1863 "Allocator::value_type must be same type as value_type"); 1864 1865private: 1866 typedef __hash_value_type<key_type, mapped_type> __value_type; 1867 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher; 1868 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal; 1869 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; 1870 1871 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; 1872 1873 __table __table_; 1874 1875 typedef typename __table::_NodeTypes _NodeTypes; 1876 typedef typename __table::__node_traits __node_traits; 1877 typedef typename __table::__node_allocator __node_allocator; 1878 typedef typename __table::__node __node; 1879 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1880 typedef unique_ptr<__node, _Dp> __node_holder; 1881 typedef allocator_traits<allocator_type> __alloc_traits; 1882 static_assert(is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value, 1883 "Allocator uses different size_type for different types"); 1884 1885public: 1886 typedef typename __alloc_traits::pointer pointer; 1887 typedef typename __alloc_traits::const_pointer const_pointer; 1888 typedef typename __table::size_type size_type; 1889 typedef typename __table::difference_type difference_type; 1890 1891 typedef __hash_map_iterator<typename __table::iterator> iterator; 1892 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1893 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1894 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1895 1896#if _LIBCPP_STD_VER >= 17 1897 typedef __map_node_handle<__node, allocator_type> node_type; 1898#endif 1899 1900 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1901 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1902 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1903 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1904 1905 _LIBCPP_HIDE_FROM_ABI unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 1906 explicit _LIBCPP_HIDE_FROM_ABI 1907 unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 1908 _LIBCPP_HIDE_FROM_ABI 1909 unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 1910 template <class _InputIterator> 1911 _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last); 1912 template <class _InputIterator> 1913 _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1914 _InputIterator __first, 1915 _InputIterator __last, 1916 size_type __n, 1917 const hasher& __hf = hasher(), 1918 const key_equal& __eql = key_equal()); 1919 template <class _InputIterator> 1920 _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1921 _InputIterator __first, 1922 _InputIterator __last, 1923 size_type __n, 1924 const hasher& __hf, 1925 const key_equal& __eql, 1926 const allocator_type& __a); 1927 1928#if _LIBCPP_STD_VER >= 23 1929 template <_ContainerCompatibleRange<value_type> _Range> 1930 _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1931 from_range_t, 1932 _Range&& __range, 1933 size_type __n = /*implementation-defined*/ 0, 1934 const hasher& __hf = hasher(), 1935 const key_equal& __eql = key_equal(), 1936 const allocator_type& __a = allocator_type()) 1937 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1938 if (__n > 0) { 1939 __table_.__rehash_multi(__n); 1940 } 1941 insert_range(std::forward<_Range>(__range)); 1942 } 1943#endif 1944 1945 _LIBCPP_HIDE_FROM_ABI explicit unordered_multimap(const allocator_type& __a); 1946 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u); 1947 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1948#ifndef _LIBCPP_CXX03_LANG 1949 _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u) 1950 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1951 _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1952 _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il); 1953 _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1954 initializer_list<value_type> __il, 1955 size_type __n, 1956 const hasher& __hf = hasher(), 1957 const key_equal& __eql = key_equal()); 1958 _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1959 initializer_list<value_type> __il, 1960 size_type __n, 1961 const hasher& __hf, 1962 const key_equal& __eql, 1963 const allocator_type& __a); 1964#endif // _LIBCPP_CXX03_LANG 1965#if _LIBCPP_STD_VER >= 14 1966 _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const allocator_type& __a) 1967 : unordered_multimap(__n, hasher(), key_equal(), __a) {} 1968 _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 1969 : unordered_multimap(__n, __hf, key_equal(), __a) {} 1970 template <class _InputIterator> 1971 _LIBCPP_HIDE_FROM_ABI 1972 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1973 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 1974 template <class _InputIterator> 1975 _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1976 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 1977 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 1978 1979# if _LIBCPP_STD_VER >= 23 1980 template <_ContainerCompatibleRange<value_type> _Range> 1981 _LIBCPP_HIDE_FROM_ABI unordered_multimap(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 1982 : unordered_multimap(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 1983 1984 template <_ContainerCompatibleRange<value_type> _Range> 1985 _LIBCPP_HIDE_FROM_ABI 1986 unordered_multimap(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 1987 : unordered_multimap(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 1988# endif 1989 1990 _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1991 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 1992 _LIBCPP_HIDE_FROM_ABI 1993 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 1994 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 1995#endif 1996 _LIBCPP_HIDE_FROM_ABI ~unordered_multimap() { 1997 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), ""); 1998 } 1999 2000 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(const unordered_multimap& __u) { 2001#ifndef _LIBCPP_CXX03_LANG 2002 __table_ = __u.__table_; 2003#else 2004 if (this != std::addressof(__u)) { 2005 __table_.clear(); 2006 __table_.hash_function() = __u.__table_.hash_function(); 2007 __table_.key_eq() = __u.__table_.key_eq(); 2008 __table_.max_load_factor() = __u.__table_.max_load_factor(); 2009 __table_.__copy_assign_alloc(__u.__table_); 2010 insert(__u.begin(), __u.end()); 2011 } 2012#endif 2013 return *this; 2014 } 2015#ifndef _LIBCPP_CXX03_LANG 2016 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(unordered_multimap&& __u) 2017 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 2018 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(initializer_list<value_type> __il); 2019#endif // _LIBCPP_CXX03_LANG 2020 2021 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 2022 return allocator_type(__table_.__node_alloc()); 2023 } 2024 2025 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 2026 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 2027 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 2028 2029 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 2030 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 2031 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 2032 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 2033 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 2034 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 2035 2036 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); } 2037 2038 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) { 2039 return __table_.__insert_multi(__p.__i_, __x); 2040 } 2041 2042 template <class _InputIterator> 2043 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 2044 2045#if _LIBCPP_STD_VER >= 23 2046 template <_ContainerCompatibleRange<value_type> _Range> 2047 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 2048 for (auto&& __element : __range) { 2049 __table_.__insert_multi(std::forward<decltype(__element)>(__element)); 2050 } 2051 } 2052#endif 2053 2054#ifndef _LIBCPP_CXX03_LANG 2055 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 2056 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); } 2057 2058 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) { 2059 return __table_.__insert_multi(__p.__i_, std::move(__x)); 2060 } 2061 2062 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0> 2063 _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __x) { 2064 return __table_.__insert_multi(std::forward<_Pp>(__x)); 2065 } 2066 2067 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0> 2068 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _Pp&& __x) { 2069 return __table_.__insert_multi(__p.__i_, std::forward<_Pp>(__x)); 2070 } 2071 2072 template <class... _Args> 2073 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { 2074 return __table_.__emplace_multi(std::forward<_Args>(__args)...); 2075 } 2076 2077 template <class... _Args> 2078 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 2079 return __table_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...); 2080 } 2081#endif // _LIBCPP_CXX03_LANG 2082 2083 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); } 2084 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); } 2085 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } 2086 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 2087 return __table_.erase(__first.__i_, __last.__i_); 2088 } 2089 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 2090 2091#if _LIBCPP_STD_VER >= 17 2092 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) { 2093 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 2094 "node_type with incompatible allocator passed to unordered_multimap::insert()"); 2095 return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh)); 2096 } 2097 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 2098 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 2099 "node_type with incompatible allocator passed to unordered_multimap::insert()"); 2100 return __table_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh)); 2101 } 2102 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 2103 return __table_.template __node_handle_extract<node_type>(__key); 2104 } 2105 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 2106 return __table_.template __node_handle_extract<node_type>(__it.__i_); 2107 } 2108 2109 template <class _H2, class _P2> 2110 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { 2111 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 2112 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 2113 return __table_.__node_handle_merge_multi(__source.__table_); 2114 } 2115 template <class _H2, class _P2> 2116 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { 2117 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 2118 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 2119 return __table_.__node_handle_merge_multi(__source.__table_); 2120 } 2121 template <class _H2, class _P2> 2122 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { 2123 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 2124 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 2125 return __table_.__node_handle_merge_multi(__source.__table_); 2126 } 2127 template <class _H2, class _P2> 2128 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { 2129 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 2130 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 2131 return __table_.__node_handle_merge_multi(__source.__table_); 2132 } 2133#endif 2134 2135 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) { 2136 __table_.swap(__u.__table_); 2137 } 2138 2139 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); } 2140 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } 2141 2142 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 2143 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 2144#if _LIBCPP_STD_VER >= 20 2145 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 2146 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 2147 return __table_.find(__k); 2148 } 2149 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 2150 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 2151 return __table_.find(__k); 2152 } 2153#endif // _LIBCPP_STD_VER >= 20 2154 2155 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } 2156#if _LIBCPP_STD_VER >= 20 2157 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 2158 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 2159 return __table_.__count_multi(__k); 2160 } 2161#endif // _LIBCPP_STD_VER >= 20 2162 2163#if _LIBCPP_STD_VER >= 20 2164 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 2165 2166 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 2167 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 2168 return find(__k) != end(); 2169 } 2170#endif // _LIBCPP_STD_VER >= 20 2171 2172 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 2173 return __table_.__equal_range_multi(__k); 2174 } 2175 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 2176 return __table_.__equal_range_multi(__k); 2177 } 2178#if _LIBCPP_STD_VER >= 20 2179 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 2180 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 2181 return __table_.__equal_range_multi(__k); 2182 } 2183 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 2184 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 2185 return __table_.__equal_range_multi(__k); 2186 } 2187#endif // _LIBCPP_STD_VER >= 20 2188 2189 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 2190 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 2191 2192 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 2193 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 2194 2195 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 2196 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 2197 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 2198 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 2199 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 2200 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 2201 2202 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 2203 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 2204 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 2205 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); } 2206 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); } 2207}; 2208 2209#if _LIBCPP_STD_VER >= 17 2210template <class _InputIterator, 2211 class _Hash = hash<__iter_key_type<_InputIterator>>, 2212 class _Pred = equal_to<__iter_key_type<_InputIterator>>, 2213 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 2214 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 2215 class = enable_if_t<!__is_allocator<_Hash>::value>, 2216 class = enable_if_t<!is_integral<_Hash>::value>, 2217 class = enable_if_t<!__is_allocator<_Pred>::value>, 2218 class = enable_if_t<__is_allocator<_Allocator>::value>> 2219unordered_multimap(_InputIterator, 2220 _InputIterator, 2221 typename allocator_traits<_Allocator>::size_type = 0, 2222 _Hash = _Hash(), 2223 _Pred = _Pred(), 2224 _Allocator = _Allocator()) 2225 -> unordered_multimap<__iter_key_type<_InputIterator>, 2226 __iter_mapped_type<_InputIterator>, 2227 _Hash, 2228 _Pred, 2229 _Allocator>; 2230 2231# if _LIBCPP_STD_VER >= 23 2232template <ranges::input_range _Range, 2233 class _Hash = hash<__range_key_type<_Range>>, 2234 class _Pred = equal_to<__range_key_type<_Range>>, 2235 class _Allocator = allocator<__range_to_alloc_type<_Range>>, 2236 class = enable_if_t<!__is_allocator<_Hash>::value>, 2237 class = enable_if_t<!is_integral<_Hash>::value>, 2238 class = enable_if_t<!__is_allocator<_Pred>::value>, 2239 class = enable_if_t<__is_allocator<_Allocator>::value>> 2240unordered_multimap(from_range_t, 2241 _Range&&, 2242 typename allocator_traits<_Allocator>::size_type = 0, 2243 _Hash = _Hash(), 2244 _Pred = _Pred(), 2245 _Allocator = _Allocator()) 2246 -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; 2247# endif 2248 2249template <class _Key, 2250 class _Tp, 2251 class _Hash = hash<remove_const_t<_Key>>, 2252 class _Pred = equal_to<remove_const_t<_Key>>, 2253 class _Allocator = allocator<pair<const _Key, _Tp>>, 2254 class = enable_if_t<!__is_allocator<_Hash>::value>, 2255 class = enable_if_t<!is_integral<_Hash>::value>, 2256 class = enable_if_t<!__is_allocator<_Pred>::value>, 2257 class = enable_if_t<__is_allocator<_Allocator>::value>> 2258unordered_multimap( 2259 initializer_list<pair<_Key, _Tp>>, 2260 typename allocator_traits<_Allocator>::size_type = 0, 2261 _Hash = _Hash(), 2262 _Pred = _Pred(), 2263 _Allocator = _Allocator()) -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>; 2264 2265template <class _InputIterator, 2266 class _Allocator, 2267 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 2268 class = enable_if_t<__is_allocator<_Allocator>::value>> 2269unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 2270 -> unordered_multimap<__iter_key_type<_InputIterator>, 2271 __iter_mapped_type<_InputIterator>, 2272 hash<__iter_key_type<_InputIterator>>, 2273 equal_to<__iter_key_type<_InputIterator>>, 2274 _Allocator>; 2275 2276template <class _InputIterator, 2277 class _Allocator, 2278 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 2279 class = enable_if_t<__is_allocator<_Allocator>::value>> 2280unordered_multimap(_InputIterator, _InputIterator, _Allocator) 2281 -> unordered_multimap<__iter_key_type<_InputIterator>, 2282 __iter_mapped_type<_InputIterator>, 2283 hash<__iter_key_type<_InputIterator>>, 2284 equal_to<__iter_key_type<_InputIterator>>, 2285 _Allocator>; 2286 2287template <class _InputIterator, 2288 class _Hash, 2289 class _Allocator, 2290 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 2291 class = enable_if_t<!__is_allocator<_Hash>::value>, 2292 class = enable_if_t<!is_integral<_Hash>::value>, 2293 class = enable_if_t<__is_allocator<_Allocator>::value>> 2294unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 2295 -> unordered_multimap<__iter_key_type<_InputIterator>, 2296 __iter_mapped_type<_InputIterator>, 2297 _Hash, 2298 equal_to<__iter_key_type<_InputIterator>>, 2299 _Allocator>; 2300 2301# if _LIBCPP_STD_VER >= 23 2302 2303template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 2304unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 2305 -> unordered_multimap<__range_key_type<_Range>, 2306 __range_mapped_type<_Range>, 2307 hash<__range_key_type<_Range>>, 2308 equal_to<__range_key_type<_Range>>, 2309 _Allocator>; 2310 2311template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 2312unordered_multimap(from_range_t, _Range&&, _Allocator) 2313 -> unordered_multimap<__range_key_type<_Range>, 2314 __range_mapped_type<_Range>, 2315 hash<__range_key_type<_Range>>, 2316 equal_to<__range_key_type<_Range>>, 2317 _Allocator>; 2318 2319template <ranges::input_range _Range, 2320 class _Hash, 2321 class _Allocator, 2322 class = enable_if_t<!__is_allocator<_Hash>::value>, 2323 class = enable_if_t<!is_integral<_Hash>::value>, 2324 class = enable_if_t<__is_allocator<_Allocator>::value>> 2325unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 2326 -> unordered_multimap<__range_key_type<_Range>, 2327 __range_mapped_type<_Range>, 2328 _Hash, 2329 equal_to<__range_key_type<_Range>>, 2330 _Allocator>; 2331 2332# endif 2333 2334template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 2335unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator) 2336 -> unordered_multimap<remove_const_t<_Key>, 2337 _Tp, 2338 hash<remove_const_t<_Key>>, 2339 equal_to<remove_const_t<_Key>>, 2340 _Allocator>; 2341 2342template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 2343unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 2344 -> unordered_multimap<remove_const_t<_Key>, 2345 _Tp, 2346 hash<remove_const_t<_Key>>, 2347 equal_to<remove_const_t<_Key>>, 2348 _Allocator>; 2349 2350template <class _Key, 2351 class _Tp, 2352 class _Hash, 2353 class _Allocator, 2354 class = enable_if_t<!__is_allocator<_Hash>::value>, 2355 class = enable_if_t<!is_integral<_Hash>::value>, 2356 class = enable_if_t<__is_allocator<_Allocator>::value>> 2357unordered_multimap( 2358 initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 2359 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>; 2360#endif 2361 2362template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2363unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2364 size_type __n, const hasher& __hf, const key_equal& __eql) 2365 : __table_(__hf, __eql) { 2366 __table_.__rehash_multi(__n); 2367} 2368 2369template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2370unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2371 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 2372 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 2373 __table_.__rehash_multi(__n); 2374} 2375 2376template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2377template <class _InputIterator> 2378unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(_InputIterator __first, _InputIterator __last) { 2379 insert(__first, __last); 2380} 2381 2382template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2383template <class _InputIterator> 2384unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2385 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 2386 : __table_(__hf, __eql) { 2387 __table_.__rehash_multi(__n); 2388 insert(__first, __last); 2389} 2390 2391template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2392template <class _InputIterator> 2393unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2394 _InputIterator __first, 2395 _InputIterator __last, 2396 size_type __n, 2397 const hasher& __hf, 2398 const key_equal& __eql, 2399 const allocator_type& __a) 2400 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 2401 __table_.__rehash_multi(__n); 2402 insert(__first, __last); 2403} 2404 2405template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2406inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const allocator_type& __a) 2407 : __table_(typename __table::allocator_type(__a)) {} 2408 2409template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2410unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const unordered_multimap& __u) 2411 : __table_(__u.__table_) { 2412 __table_.__rehash_multi(__u.bucket_count()); 2413 insert(__u.begin(), __u.end()); 2414} 2415 2416template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2417unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2418 const unordered_multimap& __u, const allocator_type& __a) 2419 : __table_(__u.__table_, typename __table::allocator_type(__a)) { 2420 __table_.__rehash_multi(__u.bucket_count()); 2421 insert(__u.begin(), __u.end()); 2422} 2423 2424#ifndef _LIBCPP_CXX03_LANG 2425 2426template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2427inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(unordered_multimap&& __u) 2428 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 2429 : __table_(std::move(__u.__table_)) {} 2430 2431template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2432unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2433 unordered_multimap&& __u, const allocator_type& __a) 2434 : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) { 2435 if (__a != __u.get_allocator()) { 2436 iterator __i = __u.begin(); 2437 while (__u.size() != 0) { 2438 __table_.__insert_multi(__u.__table_.remove((__i++).__i_)->__get_value().__move()); 2439 } 2440 } 2441} 2442 2443template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2444unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(initializer_list<value_type> __il) { 2445 insert(__il.begin(), __il.end()); 2446} 2447 2448template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2449unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2450 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 2451 : __table_(__hf, __eql) { 2452 __table_.__rehash_multi(__n); 2453 insert(__il.begin(), __il.end()); 2454} 2455 2456template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2457unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2458 initializer_list<value_type> __il, 2459 size_type __n, 2460 const hasher& __hf, 2461 const key_equal& __eql, 2462 const allocator_type& __a) 2463 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 2464 __table_.__rehash_multi(__n); 2465 insert(__il.begin(), __il.end()); 2466} 2467 2468template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2469inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2470unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 2471 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 2472 __table_ = std::move(__u.__table_); 2473 return *this; 2474} 2475 2476template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2477inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2478unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 2479 __table_.__assign_multi(__il.begin(), __il.end()); 2480 return *this; 2481} 2482 2483#endif // _LIBCPP_CXX03_LANG 2484 2485template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2486template <class _InputIterator> 2487inline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 2488 for (; __first != __last; ++__first) 2489 __table_.__insert_multi(*__first); 2490} 2491 2492template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2493inline _LIBCPP_HIDE_FROM_ABI void 2494swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2495 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 2496 __x.swap(__y); 2497} 2498 2499#if _LIBCPP_STD_VER >= 20 2500template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate> 2501inline _LIBCPP_HIDE_FROM_ABI typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type 2502erase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 2503 return std::__libcpp_erase_if_container(__c, __pred); 2504} 2505#endif 2506 2507template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2508_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2509 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 2510 if (__x.size() != __y.size()) 2511 return false; 2512 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 2513 typedef pair<const_iterator, const_iterator> _EqRng; 2514 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { 2515 _EqRng __xeq = __x.equal_range(__i->first); 2516 _EqRng __yeq = __y.equal_range(__i->first); 2517 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || 2518 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2519 return false; 2520 __i = __xeq.second; 2521 } 2522 return true; 2523} 2524 2525#if _LIBCPP_STD_VER <= 17 2526 2527template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2528inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2529 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 2530 return !(__x == __y); 2531} 2532 2533#endif 2534 2535template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2536struct __container_traits<unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> > { 2537 // http://eel.is/c++draft/unord.req.except#2 2538 // For unordered associative containers, if an exception is thrown by any operation 2539 // other than the container's hash function from within an insert or emplace function 2540 // inserting a single element, the insertion has no effect. 2541 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = 2542 __nothrow_invokable<_Hash, const _Key&>::value; 2543}; 2544 2545_LIBCPP_END_NAMESPACE_STD 2546 2547#if _LIBCPP_STD_VER >= 17 2548_LIBCPP_BEGIN_NAMESPACE_STD 2549namespace pmr { 2550template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 2551using unordered_map _LIBCPP_AVAILABILITY_PMR = 2552 std::unordered_map<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; 2553 2554template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 2555using unordered_multimap _LIBCPP_AVAILABILITY_PMR = 2556 std::unordered_multimap<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; 2557} // namespace pmr 2558_LIBCPP_END_NAMESPACE_STD 2559#endif 2560 2561_LIBCPP_POP_MACROS 2562 2563#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 2564# include <algorithm> 2565# include <bit> 2566# include <cmath> 2567# include <concepts> 2568# include <cstdlib> 2569# include <iterator> 2570# include <type_traits> 2571#endif 2572 2573#endif // _LIBCPP_UNORDERED_MAP 2574