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