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