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