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