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