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