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