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