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