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#if _LIBCPP_DEBUG_LEVEL == 2 1697 __get_db()->swap(this, _VSTD::addressof(__u)); 1698#endif 1699} 1700 1701template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1702unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1703 unordered_map&& __u, const allocator_type& __a) 1704 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a)) 1705{ 1706 _VSTD::__debug_db_insert_c(this); 1707 if (__a != __u.get_allocator()) 1708 { 1709 iterator __i = __u.begin(); 1710 while (__u.size() != 0) { 1711 __table_.__emplace_unique( 1712 __u.__table_.remove((__i++).__i_)->__value_.__move()); 1713 } 1714 } 1715#if _LIBCPP_DEBUG_LEVEL == 2 1716 else 1717 __get_db()->swap(this, _VSTD::addressof(__u)); 1718#endif 1719} 1720 1721template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1722unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1723 initializer_list<value_type> __il) 1724{ 1725 _VSTD::__debug_db_insert_c(this); 1726 insert(__il.begin(), __il.end()); 1727} 1728 1729template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1730unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1731 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1732 const key_equal& __eql) 1733 : __table_(__hf, __eql) 1734{ 1735 _VSTD::__debug_db_insert_c(this); 1736 __table_.rehash(__n); 1737 insert(__il.begin(), __il.end()); 1738} 1739 1740template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1741unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1742 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1743 const key_equal& __eql, const allocator_type& __a) 1744 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1745{ 1746 _VSTD::__debug_db_insert_c(this); 1747 __table_.rehash(__n); 1748 insert(__il.begin(), __il.end()); 1749} 1750 1751template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1752inline 1753unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1754unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1755 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1756{ 1757 __table_ = _VSTD::move(__u.__table_); 1758 return *this; 1759} 1760 1761template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1762inline 1763unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1764unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1765 initializer_list<value_type> __il) 1766{ 1767 __table_.__assign_unique(__il.begin(), __il.end()); 1768 return *this; 1769} 1770 1771#endif // _LIBCPP_CXX03_LANG 1772 1773template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1774template <class _InputIterator> 1775inline 1776void 1777unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1778 _InputIterator __last) 1779{ 1780 for (; __first != __last; ++__first) 1781 __table_.__insert_unique(*__first); 1782} 1783 1784#ifndef _LIBCPP_CXX03_LANG 1785 1786template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1787_Tp& 1788unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1789{ 1790 return __table_.__emplace_unique_key_args(__k, 1791 piecewise_construct, _VSTD::forward_as_tuple(__k), 1792 _VSTD::forward_as_tuple()).first->__get_value().second; 1793} 1794 1795template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1796_Tp& 1797unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1798{ 1799 return __table_.__emplace_unique_key_args(__k, 1800 piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 1801 _VSTD::forward_as_tuple()).first->__get_value().second; 1802} 1803#else // _LIBCPP_CXX03_LANG 1804 1805template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1806typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1807unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1808{ 1809 __node_allocator& __na = __table_.__node_alloc(); 1810 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1811 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k); 1812 __h.get_deleter().__first_constructed = true; 1813 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second)); 1814 __h.get_deleter().__second_constructed = true; 1815 return __h; 1816} 1817 1818template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1819_Tp& 1820unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1821{ 1822 iterator __i = find(__k); 1823 if (__i != end()) 1824 return __i->second; 1825 __node_holder __h = __construct_node_with_key(__k); 1826 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1827 __h.release(); 1828 return __r.first->second; 1829} 1830 1831#endif // _LIBCPP_CXX03_LANG 1832 1833template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1834_Tp& 1835unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1836{ 1837 iterator __i = find(__k); 1838 if (__i == end()) 1839 __throw_out_of_range("unordered_map::at: key not found"); 1840 return __i->second; 1841} 1842 1843template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1844const _Tp& 1845unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1846{ 1847 const_iterator __i = find(__k); 1848 if (__i == end()) 1849 __throw_out_of_range("unordered_map::at: key not found"); 1850 return __i->second; 1851} 1852 1853template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1854inline _LIBCPP_INLINE_VISIBILITY 1855void 1856swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1857 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1858 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1859{ 1860 __x.swap(__y); 1861} 1862 1863#if _LIBCPP_STD_VER > 17 1864template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 1865 class _Predicate> 1866inline _LIBCPP_INLINE_VISIBILITY 1867 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type 1868 erase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, 1869 _Predicate __pred) { 1870 return _VSTD::__libcpp_erase_if_container(__c, __pred); 1871} 1872#endif 1873 1874template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1875bool 1876operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1877 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1878{ 1879 if (__x.size() != __y.size()) 1880 return false; 1881 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1882 const_iterator; 1883 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1884 __i != __ex; ++__i) 1885 { 1886 const_iterator __j = __y.find(__i->first); 1887 if (__j == __ey || !(*__i == *__j)) 1888 return false; 1889 } 1890 return true; 1891} 1892 1893template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1894inline _LIBCPP_INLINE_VISIBILITY 1895bool 1896operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1897 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1898{ 1899 return !(__x == __y); 1900} 1901 1902template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1903 class _Alloc = allocator<pair<const _Key, _Tp> > > 1904class _LIBCPP_TEMPLATE_VIS unordered_multimap 1905{ 1906public: 1907 // types 1908 typedef _Key key_type; 1909 typedef _Tp mapped_type; 1910 typedef __type_identity_t<_Hash> hasher; 1911 typedef __type_identity_t<_Pred> key_equal; 1912 typedef __type_identity_t<_Alloc> allocator_type; 1913 typedef pair<const key_type, mapped_type> value_type; 1914 typedef value_type& reference; 1915 typedef const value_type& const_reference; 1916 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1917 "Invalid allocator::value_type"); 1918 1919private: 1920 typedef __hash_value_type<key_type, mapped_type> __value_type; 1921 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher; 1922 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal; 1923 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1924 __value_type>::type __allocator_type; 1925 1926 typedef __hash_table<__value_type, __hasher, 1927 __key_equal, __allocator_type> __table; 1928 1929 __table __table_; 1930 1931 typedef typename __table::_NodeTypes _NodeTypes; 1932 typedef typename __table::__node_traits __node_traits; 1933 typedef typename __table::__node_allocator __node_allocator; 1934 typedef typename __table::__node __node; 1935 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1936 typedef unique_ptr<__node, _Dp> __node_holder; 1937 typedef allocator_traits<allocator_type> __alloc_traits; 1938 static_assert((is_same<typename __node_traits::size_type, 1939 typename __alloc_traits::size_type>::value), 1940 "Allocator uses different size_type for different types"); 1941public: 1942 typedef typename __alloc_traits::pointer pointer; 1943 typedef typename __alloc_traits::const_pointer const_pointer; 1944 typedef typename __table::size_type size_type; 1945 typedef typename __table::difference_type difference_type; 1946 1947 typedef __hash_map_iterator<typename __table::iterator> iterator; 1948 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1949 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1950 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1951 1952#if _LIBCPP_STD_VER > 14 1953 typedef __map_node_handle<__node, allocator_type> node_type; 1954#endif 1955 1956 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1957 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1958 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1959 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1960 1961 _LIBCPP_INLINE_VISIBILITY 1962 unordered_multimap() 1963 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1964 { 1965 _VSTD::__debug_db_insert_c(this); 1966 } 1967 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1968 const key_equal& __eql = key_equal()); 1969 unordered_multimap(size_type __n, const hasher& __hf, 1970 const key_equal& __eql, 1971 const allocator_type& __a); 1972 template <class _InputIterator> 1973 unordered_multimap(_InputIterator __first, _InputIterator __last); 1974 template <class _InputIterator> 1975 unordered_multimap(_InputIterator __first, _InputIterator __last, 1976 size_type __n, const hasher& __hf = hasher(), 1977 const key_equal& __eql = key_equal()); 1978 template <class _InputIterator> 1979 unordered_multimap(_InputIterator __first, _InputIterator __last, 1980 size_type __n, const hasher& __hf, 1981 const key_equal& __eql, 1982 const allocator_type& __a); 1983 _LIBCPP_INLINE_VISIBILITY 1984 explicit unordered_multimap(const allocator_type& __a); 1985 unordered_multimap(const unordered_multimap& __u); 1986 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1987#ifndef _LIBCPP_CXX03_LANG 1988 _LIBCPP_INLINE_VISIBILITY 1989 unordered_multimap(unordered_multimap&& __u) 1990 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1991 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1992 unordered_multimap(initializer_list<value_type> __il); 1993 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1994 const hasher& __hf = hasher(), 1995 const key_equal& __eql = key_equal()); 1996 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1997 const hasher& __hf, const key_equal& __eql, 1998 const allocator_type& __a); 1999#endif // _LIBCPP_CXX03_LANG 2000#if _LIBCPP_STD_VER > 11 2001 _LIBCPP_INLINE_VISIBILITY 2002 unordered_multimap(size_type __n, const allocator_type& __a) 2003 : unordered_multimap(__n, hasher(), key_equal(), __a) {} 2004 _LIBCPP_INLINE_VISIBILITY 2005 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 2006 : unordered_multimap(__n, __hf, key_equal(), __a) {} 2007 template <class _InputIterator> 2008 _LIBCPP_INLINE_VISIBILITY 2009 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 2010 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 2011 template <class _InputIterator> 2012 _LIBCPP_INLINE_VISIBILITY 2013 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 2014 const allocator_type& __a) 2015 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 2016 _LIBCPP_INLINE_VISIBILITY 2017 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 2018 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 2019 _LIBCPP_INLINE_VISIBILITY 2020 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 2021 const allocator_type& __a) 2022 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 2023#endif 2024 _LIBCPP_INLINE_VISIBILITY 2025 ~unordered_multimap() { 2026 static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), ""); 2027 } 2028 2029 _LIBCPP_INLINE_VISIBILITY 2030 unordered_multimap& operator=(const unordered_multimap& __u) 2031 { 2032#ifndef _LIBCPP_CXX03_LANG 2033 __table_ = __u.__table_; 2034#else 2035 if (this != _VSTD::addressof(__u)) { 2036 __table_.clear(); 2037 __table_.hash_function() = __u.__table_.hash_function(); 2038 __table_.key_eq() = __u.__table_.key_eq(); 2039 __table_.max_load_factor() = __u.__table_.max_load_factor(); 2040 __table_.__copy_assign_alloc(__u.__table_); 2041 insert(__u.begin(), __u.end()); 2042 } 2043#endif 2044 return *this; 2045 } 2046#ifndef _LIBCPP_CXX03_LANG 2047 _LIBCPP_INLINE_VISIBILITY 2048 unordered_multimap& operator=(unordered_multimap&& __u) 2049 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 2050 _LIBCPP_INLINE_VISIBILITY 2051 unordered_multimap& operator=(initializer_list<value_type> __il); 2052#endif // _LIBCPP_CXX03_LANG 2053 2054 _LIBCPP_INLINE_VISIBILITY 2055 allocator_type get_allocator() const _NOEXCEPT 2056 {return allocator_type(__table_.__node_alloc());} 2057 2058 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 2059 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 2060 _LIBCPP_INLINE_VISIBILITY 2061 size_type size() const _NOEXCEPT {return __table_.size();} 2062 _LIBCPP_INLINE_VISIBILITY 2063 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 2064 2065 _LIBCPP_INLINE_VISIBILITY 2066 iterator begin() _NOEXCEPT {return __table_.begin();} 2067 _LIBCPP_INLINE_VISIBILITY 2068 iterator end() _NOEXCEPT {return __table_.end();} 2069 _LIBCPP_INLINE_VISIBILITY 2070 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 2071 _LIBCPP_INLINE_VISIBILITY 2072 const_iterator end() const _NOEXCEPT {return __table_.end();} 2073 _LIBCPP_INLINE_VISIBILITY 2074 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 2075 _LIBCPP_INLINE_VISIBILITY 2076 const_iterator cend() const _NOEXCEPT {return __table_.end();} 2077 2078 _LIBCPP_INLINE_VISIBILITY 2079 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 2080 2081 _LIBCPP_INLINE_VISIBILITY 2082 iterator insert(const_iterator __p, const value_type& __x) 2083 {return __table_.__insert_multi(__p.__i_, __x);} 2084 2085 template <class _InputIterator> 2086 _LIBCPP_INLINE_VISIBILITY 2087 void insert(_InputIterator __first, _InputIterator __last); 2088 2089#ifndef _LIBCPP_CXX03_LANG 2090 _LIBCPP_INLINE_VISIBILITY 2091 void insert(initializer_list<value_type> __il) 2092 {insert(__il.begin(), __il.end());} 2093 _LIBCPP_INLINE_VISIBILITY 2094 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 2095 2096 _LIBCPP_INLINE_VISIBILITY 2097 iterator insert(const_iterator __p, value_type&& __x) 2098 {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));} 2099 2100 template <class _Pp, 2101 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 2102 _LIBCPP_INLINE_VISIBILITY 2103 iterator insert(_Pp&& __x) 2104 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 2105 2106 template <class _Pp, 2107 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 2108 _LIBCPP_INLINE_VISIBILITY 2109 iterator insert(const_iterator __p, _Pp&& __x) 2110 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 2111 2112 template <class... _Args> 2113 iterator emplace(_Args&&... __args) { 2114 return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...); 2115 } 2116 2117 template <class... _Args> 2118 iterator emplace_hint(const_iterator __p, _Args&&... __args) { 2119 return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); 2120 } 2121#endif // _LIBCPP_CXX03_LANG 2122 2123 2124 _LIBCPP_INLINE_VISIBILITY 2125 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 2126 _LIBCPP_INLINE_VISIBILITY 2127 iterator erase(iterator __p) {return __table_.erase(__p.__i_);} 2128 _LIBCPP_INLINE_VISIBILITY 2129 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 2130 _LIBCPP_INLINE_VISIBILITY 2131 iterator erase(const_iterator __first, const_iterator __last) 2132 {return __table_.erase(__first.__i_, __last.__i_);} 2133 _LIBCPP_INLINE_VISIBILITY 2134 void clear() _NOEXCEPT {__table_.clear();} 2135 2136#if _LIBCPP_STD_VER > 14 2137 _LIBCPP_INLINE_VISIBILITY 2138 iterator insert(node_type&& __nh) 2139 { 2140 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 2141 "node_type with incompatible allocator passed to unordered_multimap::insert()"); 2142 return __table_.template __node_handle_insert_multi<node_type>( 2143 _VSTD::move(__nh)); 2144 } 2145 _LIBCPP_INLINE_VISIBILITY 2146 iterator insert(const_iterator __hint, node_type&& __nh) 2147 { 2148 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 2149 "node_type with incompatible allocator passed to unordered_multimap::insert()"); 2150 return __table_.template __node_handle_insert_multi<node_type>( 2151 __hint.__i_, _VSTD::move(__nh)); 2152 } 2153 _LIBCPP_INLINE_VISIBILITY 2154 node_type extract(key_type const& __key) 2155 { 2156 return __table_.template __node_handle_extract<node_type>(__key); 2157 } 2158 _LIBCPP_INLINE_VISIBILITY 2159 node_type extract(const_iterator __it) 2160 { 2161 return __table_.template __node_handle_extract<node_type>( 2162 __it.__i_); 2163 } 2164 2165 template <class _H2, class _P2> 2166 _LIBCPP_INLINE_VISIBILITY 2167 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) 2168 { 2169 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2170 "merging container with incompatible allocator"); 2171 return __table_.__node_handle_merge_multi(__source.__table_); 2172 } 2173 template <class _H2, class _P2> 2174 _LIBCPP_INLINE_VISIBILITY 2175 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) 2176 { 2177 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2178 "merging container with incompatible allocator"); 2179 return __table_.__node_handle_merge_multi(__source.__table_); 2180 } 2181 template <class _H2, class _P2> 2182 _LIBCPP_INLINE_VISIBILITY 2183 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) 2184 { 2185 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2186 "merging container with incompatible allocator"); 2187 return __table_.__node_handle_merge_multi(__source.__table_); 2188 } 2189 template <class _H2, class _P2> 2190 _LIBCPP_INLINE_VISIBILITY 2191 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) 2192 { 2193 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 2194 "merging container with incompatible allocator"); 2195 return __table_.__node_handle_merge_multi(__source.__table_); 2196 } 2197#endif 2198 2199 _LIBCPP_INLINE_VISIBILITY 2200 void swap(unordered_multimap& __u) 2201 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 2202 {__table_.swap(__u.__table_);} 2203 2204 _LIBCPP_INLINE_VISIBILITY 2205 hasher hash_function() const 2206 {return __table_.hash_function().hash_function();} 2207 _LIBCPP_INLINE_VISIBILITY 2208 key_equal key_eq() const 2209 {return __table_.key_eq().key_eq();} 2210 2211 _LIBCPP_INLINE_VISIBILITY 2212 iterator find(const key_type& __k) {return __table_.find(__k);} 2213 _LIBCPP_INLINE_VISIBILITY 2214 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 2215#if _LIBCPP_STD_VER > 17 2216 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2217 _LIBCPP_INLINE_VISIBILITY 2218 iterator find(const _K2& __k) {return __table_.find(__k);} 2219 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2220 _LIBCPP_INLINE_VISIBILITY 2221 const_iterator find(const _K2& __k) const {return __table_.find(__k);} 2222#endif // _LIBCPP_STD_VER > 17 2223 2224 _LIBCPP_INLINE_VISIBILITY 2225 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 2226#if _LIBCPP_STD_VER > 17 2227 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2228 _LIBCPP_INLINE_VISIBILITY 2229 size_type count(const _K2& __k) const {return __table_.__count_multi(__k);} 2230#endif // _LIBCPP_STD_VER > 17 2231 2232#if _LIBCPP_STD_VER > 17 2233 _LIBCPP_INLINE_VISIBILITY 2234 bool contains(const key_type& __k) const {return find(__k) != end();} 2235 2236 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2237 _LIBCPP_INLINE_VISIBILITY 2238 bool contains(const _K2& __k) const {return find(__k) != end();} 2239#endif // _LIBCPP_STD_VER > 17 2240 2241 _LIBCPP_INLINE_VISIBILITY 2242 pair<iterator, iterator> equal_range(const key_type& __k) 2243 {return __table_.__equal_range_multi(__k);} 2244 _LIBCPP_INLINE_VISIBILITY 2245 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 2246 {return __table_.__equal_range_multi(__k);} 2247#if _LIBCPP_STD_VER > 17 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<iterator, iterator> equal_range(const _K2& __k) 2251 {return __table_.__equal_range_multi(__k);} 2252 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2253 _LIBCPP_INLINE_VISIBILITY 2254 pair<const_iterator, const_iterator> equal_range(const _K2& __k) const 2255 {return __table_.__equal_range_multi(__k);} 2256#endif // _LIBCPP_STD_VER > 17 2257 2258 _LIBCPP_INLINE_VISIBILITY 2259 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 2260 _LIBCPP_INLINE_VISIBILITY 2261 size_type max_bucket_count() const _NOEXCEPT 2262 {return __table_.max_bucket_count();} 2263 2264 _LIBCPP_INLINE_VISIBILITY 2265 size_type bucket_size(size_type __n) const 2266 {return __table_.bucket_size(__n);} 2267 _LIBCPP_INLINE_VISIBILITY 2268 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 2269 2270 _LIBCPP_INLINE_VISIBILITY 2271 local_iterator begin(size_type __n) {return __table_.begin(__n);} 2272 _LIBCPP_INLINE_VISIBILITY 2273 local_iterator end(size_type __n) {return __table_.end(__n);} 2274 _LIBCPP_INLINE_VISIBILITY 2275 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 2276 _LIBCPP_INLINE_VISIBILITY 2277 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 2278 _LIBCPP_INLINE_VISIBILITY 2279 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 2280 _LIBCPP_INLINE_VISIBILITY 2281 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 2282 2283 _LIBCPP_INLINE_VISIBILITY 2284 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 2285 _LIBCPP_INLINE_VISIBILITY 2286 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 2287 _LIBCPP_INLINE_VISIBILITY 2288 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 2289 _LIBCPP_INLINE_VISIBILITY 2290 void rehash(size_type __n) {__table_.rehash(__n);} 2291 _LIBCPP_INLINE_VISIBILITY 2292 void reserve(size_type __n) {__table_.reserve(__n);} 2293 2294#if _LIBCPP_DEBUG_LEVEL == 2 2295 2296 bool __dereferenceable(const const_iterator* __i) const 2297 {return __table_.__dereferenceable(_VSTD::addressof(__i->__i_));} 2298 bool __decrementable(const const_iterator* __i) const 2299 {return __table_.__decrementable(_VSTD::addressof(__i->__i_));} 2300 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 2301 {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);} 2302 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 2303 {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);} 2304 2305#endif // _LIBCPP_DEBUG_LEVEL == 2 2306 2307 2308}; 2309 2310#if _LIBCPP_STD_VER >= 17 2311template<class _InputIterator, 2312 class _Hash = hash<__iter_key_type<_InputIterator>>, 2313 class _Pred = equal_to<__iter_key_type<_InputIterator>>, 2314 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 2315 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 2316 class = enable_if_t<!__is_allocator<_Hash>::value>, 2317 class = enable_if_t<!is_integral<_Hash>::value>, 2318 class = enable_if_t<!__is_allocator<_Pred>::value>, 2319 class = enable_if_t<__is_allocator<_Allocator>::value>> 2320unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0, 2321 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 2322 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>; 2323 2324template<class _Key, class _Tp, class _Hash = hash<remove_const_t<_Key>>, 2325 class _Pred = equal_to<remove_const_t<_Key>>, 2326 class _Allocator = allocator<pair<const _Key, _Tp>>, 2327 class = enable_if_t<!__is_allocator<_Hash>::value>, 2328 class = enable_if_t<!is_integral<_Hash>::value>, 2329 class = enable_if_t<!__is_allocator<_Pred>::value>, 2330 class = enable_if_t<__is_allocator<_Allocator>::value>> 2331unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type = 0, 2332 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 2333 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>; 2334 2335template<class _InputIterator, class _Allocator, 2336 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 2337 class = enable_if_t<__is_allocator<_Allocator>::value>> 2338unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 2339 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 2340 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; 2341 2342template<class _InputIterator, class _Allocator, 2343 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 2344 class = enable_if_t<__is_allocator<_Allocator>::value>> 2345unordered_multimap(_InputIterator, _InputIterator, _Allocator) 2346 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 2347 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; 2348 2349template<class _InputIterator, class _Hash, class _Allocator, 2350 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 2351 class = enable_if_t<!__is_allocator<_Hash>::value>, 2352 class = enable_if_t<!is_integral<_Hash>::value>, 2353 class = enable_if_t<__is_allocator<_Allocator>::value>> 2354unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 2355 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, 2356 _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; 2357 2358template<class _Key, class _Tp, class _Allocator, 2359 class = enable_if_t<__is_allocator<_Allocator>::value>> 2360unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator) 2361 -> unordered_multimap<remove_const_t<_Key>, _Tp, 2362 hash<remove_const_t<_Key>>, 2363 equal_to<remove_const_t<_Key>>, _Allocator>; 2364 2365template<class _Key, class _Tp, class _Allocator, 2366 class = enable_if_t<__is_allocator<_Allocator>::value>> 2367unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 2368 -> unordered_multimap<remove_const_t<_Key>, _Tp, 2369 hash<remove_const_t<_Key>>, 2370 equal_to<remove_const_t<_Key>>, _Allocator>; 2371 2372template<class _Key, class _Tp, class _Hash, class _Allocator, 2373 class = enable_if_t<!__is_allocator<_Hash>::value>, 2374 class = enable_if_t<!is_integral<_Hash>::value>, 2375 class = enable_if_t<__is_allocator<_Allocator>::value>> 2376unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 2377 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, 2378 equal_to<remove_const_t<_Key>>, _Allocator>; 2379#endif 2380 2381template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2382unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2383 size_type __n, const hasher& __hf, const key_equal& __eql) 2384 : __table_(__hf, __eql) 2385{ 2386 _VSTD::__debug_db_insert_c(this); 2387 __table_.rehash(__n); 2388} 2389 2390template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2391unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2392 size_type __n, const hasher& __hf, const key_equal& __eql, 2393 const allocator_type& __a) 2394 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 2395{ 2396 _VSTD::__debug_db_insert_c(this); 2397 __table_.rehash(__n); 2398} 2399 2400template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2401template <class _InputIterator> 2402unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2403 _InputIterator __first, _InputIterator __last) 2404{ 2405 _VSTD::__debug_db_insert_c(this); 2406 insert(__first, __last); 2407} 2408 2409template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2410template <class _InputIterator> 2411unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2412 _InputIterator __first, _InputIterator __last, size_type __n, 2413 const hasher& __hf, const key_equal& __eql) 2414 : __table_(__hf, __eql) 2415{ 2416 _VSTD::__debug_db_insert_c(this); 2417 __table_.rehash(__n); 2418 insert(__first, __last); 2419} 2420 2421template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2422template <class _InputIterator> 2423unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2424 _InputIterator __first, _InputIterator __last, size_type __n, 2425 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 2426 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 2427{ 2428 _VSTD::__debug_db_insert_c(this); 2429 __table_.rehash(__n); 2430 insert(__first, __last); 2431} 2432 2433template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2434inline 2435unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2436 const allocator_type& __a) 2437 : __table_(typename __table::allocator_type(__a)) 2438{ 2439 _VSTD::__debug_db_insert_c(this); 2440} 2441 2442template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2443unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2444 const unordered_multimap& __u) 2445 : __table_(__u.__table_) 2446{ 2447 _VSTD::__debug_db_insert_c(this); 2448 __table_.rehash(__u.bucket_count()); 2449 insert(__u.begin(), __u.end()); 2450} 2451 2452template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2453unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2454 const unordered_multimap& __u, const allocator_type& __a) 2455 : __table_(__u.__table_, typename __table::allocator_type(__a)) 2456{ 2457 _VSTD::__debug_db_insert_c(this); 2458 __table_.rehash(__u.bucket_count()); 2459 insert(__u.begin(), __u.end()); 2460} 2461 2462#ifndef _LIBCPP_CXX03_LANG 2463 2464template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2465inline 2466unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2467 unordered_multimap&& __u) 2468 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 2469 : __table_(_VSTD::move(__u.__table_)) 2470{ 2471 _VSTD::__debug_db_insert_c(this); 2472#if _LIBCPP_DEBUG_LEVEL == 2 2473 __get_db()->swap(this, _VSTD::addressof(__u)); 2474#endif 2475} 2476 2477template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2478unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2479 unordered_multimap&& __u, const allocator_type& __a) 2480 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a)) 2481{ 2482 _VSTD::__debug_db_insert_c(this); 2483 if (__a != __u.get_allocator()) 2484 { 2485 iterator __i = __u.begin(); 2486 while (__u.size() != 0) 2487 { 2488 __table_.__insert_multi( 2489 __u.__table_.remove((__i++).__i_)->__value_.__move()); 2490 } 2491 } 2492#if _LIBCPP_DEBUG_LEVEL == 2 2493 else 2494 __get_db()->swap(this, _VSTD::addressof(__u)); 2495#endif 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) 2501{ 2502 _VSTD::__debug_db_insert_c(this); 2503 insert(__il.begin(), __il.end()); 2504} 2505 2506template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2507unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2508 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 2509 const key_equal& __eql) 2510 : __table_(__hf, __eql) 2511{ 2512 _VSTD::__debug_db_insert_c(this); 2513 __table_.rehash(__n); 2514 insert(__il.begin(), __il.end()); 2515} 2516 2517template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2518unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2519 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 2520 const key_equal& __eql, const allocator_type& __a) 2521 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 2522{ 2523 _VSTD::__debug_db_insert_c(this); 2524 __table_.rehash(__n); 2525 insert(__il.begin(), __il.end()); 2526} 2527 2528template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2529inline 2530unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2531unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 2532 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 2533{ 2534 __table_ = _VSTD::move(__u.__table_); 2535 return *this; 2536} 2537 2538template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2539inline 2540unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2541unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 2542 initializer_list<value_type> __il) 2543{ 2544 __table_.__assign_multi(__il.begin(), __il.end()); 2545 return *this; 2546} 2547 2548#endif // _LIBCPP_CXX03_LANG 2549 2550 2551 2552template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2553template <class _InputIterator> 2554inline 2555void 2556unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 2557 _InputIterator __last) 2558{ 2559 for (; __first != __last; ++__first) 2560 __table_.__insert_multi(*__first); 2561} 2562 2563template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2564inline _LIBCPP_INLINE_VISIBILITY 2565void 2566swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2567 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2568 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2569{ 2570 __x.swap(__y); 2571} 2572 2573#if _LIBCPP_STD_VER > 17 2574template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 2575 class _Predicate> 2576inline _LIBCPP_INLINE_VISIBILITY 2577 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type 2578 erase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, 2579 _Predicate __pred) { 2580 return _VSTD::__libcpp_erase_if_container(__c, __pred); 2581} 2582#endif 2583 2584template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2585bool 2586operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2587 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2588{ 2589 if (__x.size() != __y.size()) 2590 return false; 2591 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 2592 const_iterator; 2593 typedef pair<const_iterator, const_iterator> _EqRng; 2594 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 2595 { 2596 _EqRng __xeq = __x.equal_range(__i->first); 2597 _EqRng __yeq = __y.equal_range(__i->first); 2598 if (_VSTD::distance(__xeq.first, __xeq.second) != 2599 _VSTD::distance(__yeq.first, __yeq.second) || 2600 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2601 return false; 2602 __i = __xeq.second; 2603 } 2604 return true; 2605} 2606 2607template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2608inline _LIBCPP_INLINE_VISIBILITY 2609bool 2610operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2611 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2612{ 2613 return !(__x == __y); 2614} 2615 2616_LIBCPP_END_NAMESPACE_STD 2617 2618#endif // _LIBCPP_UNORDERED_MAP 2619