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