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