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