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