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___CXX03_UNORDERED_MAP 11#define _LIBCPP___CXX03_UNORDERED_MAP 12 13/* 14 15 unordered_map synopsis 16 17#include <__cxx03/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 template<container-compatible-range<value_type> R> 63 unordered_map(from_range_t, R&& rg, size_type n = see below, 64 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 65 const allocator_type& a = allocator_type()); // C++23 66 67 explicit unordered_map(const allocator_type&); 68 unordered_map(const unordered_map&); 69 unordered_map(const unordered_map&, const Allocator&); 70 unordered_map(unordered_map&&) 71 noexcept( 72 is_nothrow_move_constructible<hasher>::value && 73 is_nothrow_move_constructible<key_equal>::value && 74 is_nothrow_move_constructible<allocator_type>::value); 75 unordered_map(unordered_map&&, const Allocator&); 76 unordered_map(initializer_list<value_type>, size_type n = 0, 77 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 78 const allocator_type& a = allocator_type()); 79 unordered_map(size_type n, const allocator_type& a) 80 : unordered_map(n, hasher(), key_equal(), a) {} // C++14 81 unordered_map(size_type n, const hasher& hf, const allocator_type& a) 82 : unordered_map(n, hf, key_equal(), a) {} // C++14 83 template <class InputIterator> 84 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 85 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14 86 template <class InputIterator> 87 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, 88 const allocator_type& a) 89 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14 90 template<container-compatible-range<value_type> R> 91 unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a) 92 : unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 93 template<container-compatible-range<value_type> R> 94 unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) 95 : unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 96 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a) 97 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 98 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf, 99 const allocator_type& a) 100 : unordered_map(il, n, hf, key_equal(), a) {} // C++14 101 ~unordered_map(); 102 unordered_map& operator=(const unordered_map&); 103 unordered_map& operator=(unordered_map&&) 104 noexcept( 105 allocator_type::propagate_on_container_move_assignment::value && 106 is_nothrow_move_assignable<allocator_type>::value && 107 is_nothrow_move_assignable<hasher>::value && 108 is_nothrow_move_assignable<key_equal>::value); 109 unordered_map& operator=(initializer_list<value_type>); 110 111 allocator_type get_allocator() const noexcept; 112 113 bool empty() const noexcept; 114 size_type size() const noexcept; 115 size_type max_size() const noexcept; 116 117 iterator begin() noexcept; 118 iterator end() noexcept; 119 const_iterator begin() const noexcept; 120 const_iterator end() const noexcept; 121 const_iterator cbegin() const noexcept; 122 const_iterator cend() const noexcept; 123 124 template <class... Args> 125 pair<iterator, bool> emplace(Args&&... args); 126 template <class... Args> 127 iterator emplace_hint(const_iterator position, Args&&... args); 128 pair<iterator, bool> insert(const value_type& obj); 129 template <class P> 130 pair<iterator, bool> insert(P&& obj); 131 iterator insert(const_iterator hint, const value_type& obj); 132 template <class P> 133 iterator insert(const_iterator hint, P&& obj); 134 template <class InputIterator> 135 void insert(InputIterator first, InputIterator last); 136 template<container-compatible-range<value_type> R> 137 void insert_range(R&& rg); // C++23 138 void insert(initializer_list<value_type>); 139 140 node_type extract(const_iterator position); // C++17 141 node_type extract(const key_type& x); // C++17 142 insert_return_type insert(node_type&& nh); // C++17 143 iterator insert(const_iterator hint, node_type&& nh); // C++17 144 145 template <class... Args> 146 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17 147 template <class... Args> 148 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17 149 template <class... Args> 150 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17 151 template <class... Args> 152 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17 153 template <class M> 154 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17 155 template <class M> 156 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17 157 template <class M> 158 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17 159 template <class M> 160 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17 161 162 iterator erase(const_iterator position); 163 iterator erase(iterator position); // C++14 164 size_type erase(const key_type& k); 165 iterator erase(const_iterator first, const_iterator last); 166 void clear() noexcept; 167 168 template<class H2, class P2> 169 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 170 template<class H2, class P2> 171 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 172 template<class H2, class P2> 173 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 174 template<class H2, class P2> 175 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 176 177 void swap(unordered_map&) 178 noexcept( 179 (!allocator_type::propagate_on_container_swap::value || 180 __is_nothrow_swappable<allocator_type>::value) && 181 __is_nothrow_swappable<hasher>::value && 182 __is_nothrow_swappable<key_equal>::value); 183 184 hasher hash_function() const; 185 key_equal key_eq() const; 186 187 iterator find(const key_type& k); 188 const_iterator find(const key_type& k) const; 189 template<typename K> 190 iterator find(const K& x); // C++20 191 template<typename K> 192 const_iterator find(const K& x) const; // C++20 193 size_type count(const key_type& k) const; 194 template<typename K> 195 size_type count(const K& k) const; // C++20 196 bool contains(const key_type& k) const; // C++20 197 template<typename K> 198 bool contains(const K& k) const; // C++20 199 pair<iterator, iterator> equal_range(const key_type& k); 200 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 201 template<typename K> 202 pair<iterator, iterator> equal_range(const K& k); // C++20 203 template<typename K> 204 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 205 206 mapped_type& operator[](const key_type& k); 207 mapped_type& operator[](key_type&& k); 208 209 mapped_type& at(const key_type& k); 210 const mapped_type& at(const key_type& k) const; 211 212 size_type bucket_count() const noexcept; 213 size_type max_bucket_count() const noexcept; 214 215 size_type bucket_size(size_type n) const; 216 size_type bucket(const key_type& k) const; 217 218 local_iterator begin(size_type n); 219 local_iterator end(size_type n); 220 const_local_iterator begin(size_type n) const; 221 const_local_iterator end(size_type n) const; 222 const_local_iterator cbegin(size_type n) const; 223 const_local_iterator cend(size_type n) const; 224 225 float load_factor() const noexcept; 226 float max_load_factor() const noexcept; 227 void max_load_factor(float z); 228 void rehash(size_type n); 229 void reserve(size_type n); 230}; 231 232template<class InputIterator, 233 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>, 234 class Allocator = allocator<iter_to_alloc_t<InputIterator>>> 235unordered_map(InputIterator, InputIterator, typename see below::size_type = see below, 236 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 237 -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred, 238 Allocator>; // C++17 239 240template<ranges::input_range R, class Hash = hash<range-key-type<R>>, 241 class Pred = equal_to<range-key-type<R>>, 242 class Allocator = allocator<range-to-alloc-type<R>>> 243 unordered_map(from_range_t, R&&, typename see below::size_type = see below, 244 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 245 -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23 246 247template<class Key, class T, class Hash = hash<Key>, 248 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>> 249unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type = see below, 250 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 251 -> unordered_map<Key, T, Hash, Pred, Allocator>; // C++17 252 253template<class InputIterator, class Allocator> 254unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator) 255 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 256 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 257 258template<class InputIterator, class Allocator> 259unordered_map(InputIterator, InputIterator, Allocator) 260 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 261 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 262 263template<class InputIterator, class Hash, class Allocator> 264unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator) 265 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash, 266 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 267 268template<ranges::input_range R, class Allocator> 269 unordered_map(from_range_t, R&&, typename see below::size_type, Allocator) 270 -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, 271 equal_to<range-key-type<R>>, Allocator>; // C++23 272 273template<ranges::input_range R, class Allocator> 274 unordered_map(from_range_t, R&&, Allocator) 275 -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, 276 equal_to<range-key-type<R>>, Allocator>; // C++23 277 278template<ranges::input_range R, class Hash, class Allocator> 279 unordered_map(from_range_t, R&&, typename see below::size_type, Hash, Allocator) 280 -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, 281 equal_to<range-key-type<R>>, Allocator>; // C++23 282 283template<class Key, class T, typename Allocator> 284unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator) 285 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 286 287template<class Key, class T, typename Allocator> 288unordered_map(initializer_list<pair<const Key, T>>, Allocator) 289 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 290 291template<class Key, class T, class Hash, class Allocator> 292unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, Allocator) 293 -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>; // C++17 294 295template <class Key, class T, class Hash, class Pred, class Alloc> 296 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x, 297 unordered_map<Key, T, Hash, Pred, Alloc>& y) 298 noexcept(noexcept(x.swap(y))); 299 300template <class Key, class T, class Hash, class Pred, class Alloc> 301 bool 302 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 303 const unordered_map<Key, T, Hash, Pred, Alloc>& y); 304 305template <class Key, class T, class Hash, class Pred, class Alloc> 306 bool 307 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 308 const unordered_map<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20 309 310template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 311 class Alloc = allocator<pair<const Key, T>>> 312class unordered_multimap 313{ 314public: 315 // types 316 typedef Key key_type; 317 typedef T mapped_type; 318 typedef Hash hasher; 319 typedef Pred key_equal; 320 typedef Alloc allocator_type; 321 typedef pair<const key_type, mapped_type> value_type; 322 typedef value_type& reference; 323 typedef const value_type& const_reference; 324 typedef typename allocator_traits<allocator_type>::pointer pointer; 325 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 326 typedef typename allocator_traits<allocator_type>::size_type size_type; 327 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 328 329 typedef /unspecified/ iterator; 330 typedef /unspecified/ const_iterator; 331 typedef /unspecified/ local_iterator; 332 typedef /unspecified/ const_local_iterator; 333 334 typedef unspecified node_type; // C++17 335 336 unordered_multimap() 337 noexcept( 338 is_nothrow_default_constructible<hasher>::value && 339 is_nothrow_default_constructible<key_equal>::value && 340 is_nothrow_default_constructible<allocator_type>::value); 341 explicit unordered_multimap(size_type n, const hasher& hf = hasher(), 342 const key_equal& eql = key_equal(), 343 const allocator_type& a = allocator_type()); 344 template <class InputIterator> 345 unordered_multimap(InputIterator f, InputIterator l, 346 size_type n = 0, const hasher& hf = hasher(), 347 const key_equal& eql = key_equal(), 348 const allocator_type& a = allocator_type()); 349 template<container-compatible-range<value_type> R> 350 unordered_multimap(from_range_t, R&& rg, size_type n = see below, 351 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 352 const allocator_type& a = allocator_type()); // C++23 353 explicit unordered_multimap(const allocator_type&); 354 unordered_multimap(const unordered_multimap&); 355 unordered_multimap(const unordered_multimap&, const Allocator&); 356 unordered_multimap(unordered_multimap&&) 357 noexcept( 358 is_nothrow_move_constructible<hasher>::value && 359 is_nothrow_move_constructible<key_equal>::value && 360 is_nothrow_move_constructible<allocator_type>::value); 361 unordered_multimap(unordered_multimap&&, const Allocator&); 362 unordered_multimap(initializer_list<value_type>, size_type n = 0, 363 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 364 const allocator_type& a = allocator_type()); 365 unordered_multimap(size_type n, const allocator_type& a) 366 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14 367 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a) 368 : unordered_multimap(n, hf, key_equal(), a) {} // C++14 369 template <class InputIterator> 370 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 371 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14 372 template <class InputIterator> 373 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, 374 const allocator_type& a) 375 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14 376 template<container-compatible-range<value_type> R> 377 unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a) 378 : unordered_multimap(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 379 template<container-compatible-range<value_type> R> 380 unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) 381 : unordered_multimap(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 382 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a) 383 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 384 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf, 385 const allocator_type& a) 386 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14 387 ~unordered_multimap(); 388 unordered_multimap& operator=(const unordered_multimap&); 389 unordered_multimap& operator=(unordered_multimap&&) 390 noexcept( 391 allocator_type::propagate_on_container_move_assignment::value && 392 is_nothrow_move_assignable<allocator_type>::value && 393 is_nothrow_move_assignable<hasher>::value && 394 is_nothrow_move_assignable<key_equal>::value); 395 unordered_multimap& operator=(initializer_list<value_type>); 396 397 allocator_type get_allocator() const noexcept; 398 399 bool empty() const noexcept; 400 size_type size() const noexcept; 401 size_type max_size() const noexcept; 402 403 iterator begin() noexcept; 404 iterator end() noexcept; 405 const_iterator begin() const noexcept; 406 const_iterator end() const noexcept; 407 const_iterator cbegin() const noexcept; 408 const_iterator cend() const noexcept; 409 410 template <class... Args> 411 iterator emplace(Args&&... args); 412 template <class... Args> 413 iterator emplace_hint(const_iterator position, Args&&... args); 414 iterator insert(const value_type& obj); 415 template <class P> 416 iterator insert(P&& obj); 417 iterator insert(const_iterator hint, const value_type& obj); 418 template <class P> 419 iterator insert(const_iterator hint, P&& obj); 420 template <class InputIterator> 421 void insert(InputIterator first, InputIterator last); 422 template<container-compatible-range<value_type> R> 423 void insert_range(R&& rg); // C++23 424 void insert(initializer_list<value_type>); 425 426 node_type extract(const_iterator position); // C++17 427 node_type extract(const key_type& x); // C++17 428 iterator insert(node_type&& nh); // C++17 429 iterator insert(const_iterator hint, node_type&& nh); // C++17 430 431 iterator erase(const_iterator position); 432 iterator erase(iterator position); // C++14 433 size_type erase(const key_type& k); 434 iterator erase(const_iterator first, const_iterator last); 435 void clear() noexcept; 436 437 template<class H2, class P2> 438 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 439 template<class H2, class P2> 440 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 441 template<class H2, class P2> 442 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 443 template<class H2, class P2> 444 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 445 446 void swap(unordered_multimap&) 447 noexcept( 448 (!allocator_type::propagate_on_container_swap::value || 449 __is_nothrow_swappable<allocator_type>::value) && 450 __is_nothrow_swappable<hasher>::value && 451 __is_nothrow_swappable<key_equal>::value); 452 453 hasher hash_function() const; 454 key_equal key_eq() const; 455 456 iterator find(const key_type& k); 457 const_iterator find(const key_type& k) const; 458 template<typename K> 459 iterator find(const K& x); // C++20 460 template<typename K> 461 const_iterator find(const K& x) const; // C++20 462 size_type count(const key_type& k) const; 463 template<typename K> 464 size_type count(const K& k) const; // C++20 465 bool contains(const key_type& k) const; // C++20 466 template<typename K> 467 bool contains(const K& k) const; // C++20 468 pair<iterator, iterator> equal_range(const key_type& k); 469 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 470 template<typename K> 471 pair<iterator, iterator> equal_range(const K& k); // C++20 472 template<typename K> 473 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 474 475 size_type bucket_count() const noexcept; 476 size_type max_bucket_count() const noexcept; 477 478 size_type bucket_size(size_type n) const; 479 size_type bucket(const key_type& k) const; 480 481 local_iterator begin(size_type n); 482 local_iterator end(size_type n); 483 const_local_iterator begin(size_type n) const; 484 const_local_iterator end(size_type n) const; 485 const_local_iterator cbegin(size_type n) const; 486 const_local_iterator cend(size_type n) const; 487 488 float load_factor() const noexcept; 489 float max_load_factor() const noexcept; 490 void max_load_factor(float z); 491 void rehash(size_type n); 492 void reserve(size_type n); 493}; 494 495template<class InputIterator, 496 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>, 497 class Allocator = allocator<iter_to_alloc_t<InputIterator>>> 498unordered_multimap(InputIterator, InputIterator, typename see below::size_type = see below, 499 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 500 -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred, 501 Allocator>; // C++17 502 503template<ranges::input_range R, class Hash = hash<range-key-type<R>>, 504 class Pred = equal_to<range-key-type<R>>, 505 class Allocator = allocator<range-to-alloc-type<R>>> 506 unordered_multimap(from_range_t, R&&, typename see below::size_type = see below, 507 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 508 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23 509 510template<class Key, class T, class Hash = hash<Key>, 511 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>> 512unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type = see below, 513 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 514 -> unordered_multimap<Key, T, Hash, Pred, Allocator>; // C++17 515 516template<class InputIterator, class Allocator> 517unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator) 518 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 519 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 520 521template<class InputIterator, class Allocator> 522unordered_multimap(InputIterator, InputIterator, Allocator) 523 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 524 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 525 526template<class InputIterator, class Hash, class Allocator> 527unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator) 528 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash, 529 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 530 531template<ranges::input_range R, class Allocator> 532 unordered_multimap(from_range_t, R&&, typename see below::size_type, Allocator) 533 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, 534 equal_to<range-key-type<R>>, Allocator>; // C++23 535 536template<ranges::input_range R, class Allocator> 537 unordered_multimap(from_range_t, R&&, Allocator) 538 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, 539 equal_to<range-key-type<R>>, Allocator>; // C++23 540 541template<ranges::input_range R, class Hash, class Allocator> 542 unordered_multimap(from_range_t, R&&, typename see below::size_type, Hash, Allocator) 543 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, 544 equal_to<range-key-type<R>>, Allocator>; // C++23 545 546template<class Key, class T, typename Allocator> 547unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator) 548 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 549 550template<class Key, class T, typename Allocator> 551unordered_multimap(initializer_list<pair<const Key, T>>, Allocator) 552 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 553 554template<class Key, class T, class Hash, class Allocator> 555unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, 556 Allocator) 557 -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>; // C++17 558 559template <class Key, class T, class Hash, class Pred, class Alloc> 560 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 561 unordered_multimap<Key, T, Hash, Pred, Alloc>& y) 562 noexcept(noexcept(x.swap(y))); 563 564template <class K, class T, class H, class P, class A, class Predicate> 565 typename unordered_map<K, T, H, P, A>::size_type 566 erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred); // C++20 567 568template <class K, class T, class H, class P, class A, class Predicate> 569 typename unordered_multimap<K, T, H, P, A>::size_type 570 erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred); // C++20 571 572template <class Key, class T, class Hash, class Pred, class Alloc> 573 bool 574 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 575 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 576 577template <class Key, class T, class Hash, class Pred, class Alloc> 578 bool 579 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 580 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20 581 582} // std 583 584*/ 585 586#include <__cxx03/__algorithm/is_permutation.h> 587#include <__cxx03/__assert> 588#include <__cxx03/__config> 589#include <__cxx03/__functional/operations.h> 590#include <__cxx03/__hash_table> 591#include <__cxx03/__iterator/distance.h> 592#include <__cxx03/__iterator/erase_if_container.h> 593#include <__cxx03/__iterator/iterator_traits.h> 594#include <__cxx03/__memory/addressof.h> 595#include <__cxx03/__memory/allocator.h> 596#include <__cxx03/__type_traits/is_allocator.h> 597#include <__cxx03/__type_traits/type_identity.h> 598#include <__cxx03/__utility/forward.h> 599#include <__cxx03/stdexcept> 600#include <__cxx03/version> 601 602// standard-mandated includes 603 604// [iterator.range] 605#include <__cxx03/__iterator/access.h> 606 607#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 608# pragma GCC system_header 609#endif 610 611_LIBCPP_PUSH_MACROS 612#include <__cxx03/__undef_macros> 613 614_LIBCPP_BEGIN_NAMESPACE_STD 615 616template <class _Key, 617 class _Cp, 618 class _Hash, 619 class _Pred, 620 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value> 621class __unordered_map_hasher : private _Hash { 622public: 623 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() : _Hash() {} 624 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) : _Hash(__h) {} 625 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return *this; } 626 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { 627 return static_cast<const _Hash&>(*this)(__x.__get_value().first); 628 } 629 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return static_cast<const _Hash&>(*this)(__x); } 630 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) { 631 using std::swap; 632 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y)); 633 } 634}; 635 636template <class _Key, class _Cp, class _Hash, class _Pred> 637class __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false> { 638 _Hash __hash_; 639 640public: 641 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() : __hash_() {} 642 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) : __hash_(__h) {} 643 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return __hash_; } 644 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return __hash_(__x.__get_value().first); } 645 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return __hash_(__x); } 646 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) { 647 using std::swap; 648 swap(__hash_, __y.__hash_); 649 } 650}; 651 652template <class _Key, class _Cp, class _Hash, class _Pred, bool __b> 653inline _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x, 654 __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y) { 655 __x.swap(__y); 656} 657 658template <class _Key, 659 class _Cp, 660 class _Pred, 661 class _Hash, 662 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value> 663class __unordered_map_equal : private _Pred { 664public: 665 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() : _Pred() {} 666 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) : _Pred(__p) {} 667 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return *this; } 668 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const { 669 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first); 670 } 671 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const { 672 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y); 673 } 674 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const { 675 return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first); 676 } 677 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) { 678 using std::swap; 679 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y)); 680 } 681}; 682 683template <class _Key, class _Cp, class _Pred, class _Hash> 684class __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false> { 685 _Pred __pred_; 686 687public: 688 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() : __pred_() {} 689 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) : __pred_(__p) {} 690 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return __pred_; } 691 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const { 692 return __pred_(__x.__get_value().first, __y.__get_value().first); 693 } 694 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const { 695 return __pred_(__x.__get_value().first, __y); 696 } 697 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const { 698 return __pred_(__x, __y.__get_value().first); 699 } 700 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) { 701 using std::swap; 702 swap(__pred_, __y.__pred_); 703 } 704}; 705 706template <class _Key, class _Cp, class _Pred, class _Hash, bool __b> 707inline _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x, 708 __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y) { 709 __x.swap(__y); 710} 711 712template <class _Alloc> 713class __hash_map_node_destructor { 714 typedef _Alloc allocator_type; 715 typedef allocator_traits<allocator_type> __alloc_traits; 716 717public: 718 typedef typename __alloc_traits::pointer pointer; 719 720private: 721 allocator_type& __na_; 722 723public: 724 bool __first_constructed; 725 bool __second_constructed; 726 727 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete; 728 729 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 730 : __na_(__na), 731 __first_constructed(false), 732 __second_constructed(false) {} 733 734 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 735 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) { 736 const_cast<bool&>(__x.__value_constructed) = false; 737 } 738 739 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { 740 if (__second_constructed) 741 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().second)); 742 if (__first_constructed) 743 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().first)); 744 if (__p) 745 __alloc_traits::deallocate(__na_, __p, 1); 746 } 747}; 748 749template <class _Key, class _Tp> 750struct __hash_value_type { 751 typedef _Key key_type; 752 typedef _Tp mapped_type; 753 typedef pair<const key_type, mapped_type> value_type; 754 755private: 756 value_type __cc_; 757 758public: 759 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; } 760 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; } 761 762 ~__hash_value_type() = delete; 763}; 764 765template <class _HashIterator> 766class _LIBCPP_TEMPLATE_VIS __hash_map_iterator { 767 _HashIterator __i_; 768 769 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; 770 771public: 772 typedef forward_iterator_tag iterator_category; 773 typedef typename _NodeTypes::__map_value_type value_type; 774 typedef typename _NodeTypes::difference_type difference_type; 775 typedef value_type& reference; 776 typedef typename _NodeTypes::__map_value_type_pointer pointer; 777 778 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() _NOEXCEPT {} 779 780 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 781 782 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); } 783 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); } 784 785 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() { 786 ++__i_; 787 return *this; 788 } 789 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) { 790 __hash_map_iterator __t(*this); 791 ++(*this); 792 return __t; 793 } 794 795 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { 796 return __x.__i_ == __y.__i_; 797 } 798 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { 799 return __x.__i_ != __y.__i_; 800 } 801 802 template <class, class, class, class, class> 803 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 804 template <class, class, class, class, class> 805 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 806 template <class> 807 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 808 template <class> 809 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 810 template <class> 811 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 812}; 813 814template <class _HashIterator> 815class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator { 816 _HashIterator __i_; 817 818 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; 819 820public: 821 typedef forward_iterator_tag iterator_category; 822 typedef typename _NodeTypes::__map_value_type value_type; 823 typedef typename _NodeTypes::difference_type difference_type; 824 typedef const value_type& reference; 825 typedef typename _NodeTypes::__const_map_value_type_pointer pointer; 826 827 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() _NOEXCEPT {} 828 829 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 830 _LIBCPP_HIDE_FROM_ABI 831 __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) _NOEXCEPT 832 : __i_(__i.__i_) {} 833 834 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); } 835 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); } 836 837 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() { 838 ++__i_; 839 return *this; 840 } 841 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) { 842 __hash_map_const_iterator __t(*this); 843 ++(*this); 844 return __t; 845 } 846 847 friend _LIBCPP_HIDE_FROM_ABI bool 848 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { 849 return __x.__i_ == __y.__i_; 850 } 851 friend _LIBCPP_HIDE_FROM_ABI bool 852 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { 853 return __x.__i_ != __y.__i_; 854 } 855 856 template <class, class, class, class, class> 857 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 858 template <class, class, class, class, class> 859 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 860 template <class> 861 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 862 template <class> 863 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 864}; 865 866template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 867class unordered_multimap; 868 869template <class _Key, 870 class _Tp, 871 class _Hash = hash<_Key>, 872 class _Pred = equal_to<_Key>, 873 class _Alloc = allocator<pair<const _Key, _Tp> > > 874class _LIBCPP_TEMPLATE_VIS unordered_map { 875public: 876 // types 877 typedef _Key key_type; 878 typedef _Tp mapped_type; 879 typedef __type_identity_t<_Hash> hasher; 880 typedef __type_identity_t<_Pred> key_equal; 881 typedef __type_identity_t<_Alloc> allocator_type; 882 typedef pair<const key_type, mapped_type> value_type; 883 typedef value_type& reference; 884 typedef const value_type& const_reference; 885 static_assert(is_same<value_type, typename allocator_type::value_type>::value, 886 "Allocator::value_type must be same type as value_type"); 887 888private: 889 typedef __hash_value_type<key_type, mapped_type> __value_type; 890 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher; 891 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal; 892 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; 893 894 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; 895 896 __table __table_; 897 898 typedef typename __table::_NodeTypes _NodeTypes; 899 typedef typename __table::__node_pointer __node_pointer; 900 typedef typename __table::__node_const_pointer __node_const_pointer; 901 typedef typename __table::__node_traits __node_traits; 902 typedef typename __table::__node_allocator __node_allocator; 903 typedef typename __table::__node __node; 904 typedef __hash_map_node_destructor<__node_allocator> _Dp; 905 typedef unique_ptr<__node, _Dp> __node_holder; 906 typedef allocator_traits<allocator_type> __alloc_traits; 907 908 static_assert(__check_valid_allocator<allocator_type>::value, ""); 909 910 static_assert(is_same<typename __table::__container_value_type, value_type>::value, ""); 911 static_assert(is_same<typename __table::__node_value_type, __value_type>::value, ""); 912 913public: 914 typedef typename __alloc_traits::pointer pointer; 915 typedef typename __alloc_traits::const_pointer const_pointer; 916 typedef typename __table::size_type size_type; 917 typedef typename __table::difference_type difference_type; 918 919 typedef __hash_map_iterator<typename __table::iterator> iterator; 920 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 921 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 922 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 923 924 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 925 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 926 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 927 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 928 929 _LIBCPP_HIDE_FROM_ABI unordered_map() {} 930 explicit _LIBCPP_HIDE_FROM_ABI 931 unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 932 _LIBCPP_HIDE_FROM_ABI 933 unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 934 template <class _InputIterator> 935 _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last); 936 template <class _InputIterator> 937 _LIBCPP_HIDE_FROM_ABI 938 unordered_map(_InputIterator __first, 939 _InputIterator __last, 940 size_type __n, 941 const hasher& __hf = hasher(), 942 const key_equal& __eql = key_equal()); 943 template <class _InputIterator> 944 _LIBCPP_HIDE_FROM_ABI unordered_map( 945 _InputIterator __first, 946 _InputIterator __last, 947 size_type __n, 948 const hasher& __hf, 949 const key_equal& __eql, 950 const allocator_type& __a); 951 952 _LIBCPP_HIDE_FROM_ABI explicit unordered_map(const allocator_type& __a); 953 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u); 954 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a); 955 956 _LIBCPP_HIDE_FROM_ABI ~unordered_map() { 957 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), ""); 958 } 959 960 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(const unordered_map& __u) { 961 if (this != std::addressof(__u)) { 962 __table_.clear(); 963 __table_.hash_function() = __u.__table_.hash_function(); 964 __table_.key_eq() = __u.__table_.key_eq(); 965 __table_.max_load_factor() = __u.__table_.max_load_factor(); 966 __table_.__copy_assign_alloc(__u.__table_); 967 insert(__u.begin(), __u.end()); 968 } 969 return *this; 970 } 971 972 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 973 return allocator_type(__table_.__node_alloc()); 974 } 975 976 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 977 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 978 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 979 980 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 981 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 982 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 983 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 984 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 985 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 986 987 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); } 988 989 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } 990 991 template <class _InputIterator> 992 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 993 994 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); } 995 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); } 996 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } 997 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 998 return __table_.erase(__first.__i_, __last.__i_); 999 } 1000 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 1001 1002 _LIBCPP_HIDE_FROM_ABI void swap(unordered_map& __u) { __table_.swap(__u.__table_); } 1003 1004 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); } 1005 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } 1006 1007 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 1008 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 1009 1010 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } 1011 1012 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1013 return __table_.__equal_range_unique(__k); 1014 } 1015 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1016 return __table_.__equal_range_unique(__k); 1017 } 1018 1019 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); 1020 1021 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k); 1022 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const; 1023 1024 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 1025 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 1026 1027 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 1028 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 1029 1030 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 1031 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 1032 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 1033 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 1034 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 1035 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 1036 1037 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 1038 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 1039 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 1040 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); } 1041 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); } 1042 1043private: 1044 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k); 1045}; 1046 1047template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1048unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql) 1049 : __table_(__hf, __eql) { 1050 __table_.__rehash_unique(__n); 1051} 1052 1053template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1054unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1055 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1056 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1057 __table_.__rehash_unique(__n); 1058} 1059 1060template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1061inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const allocator_type& __a) 1062 : __table_(typename __table::allocator_type(__a)) {} 1063 1064template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1065template <class _InputIterator> 1066unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(_InputIterator __first, _InputIterator __last) { 1067 insert(__first, __last); 1068} 1069 1070template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1071template <class _InputIterator> 1072unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1073 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1074 : __table_(__hf, __eql) { 1075 __table_.__rehash_unique(__n); 1076 insert(__first, __last); 1077} 1078 1079template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1080template <class _InputIterator> 1081unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1082 _InputIterator __first, 1083 _InputIterator __last, 1084 size_type __n, 1085 const hasher& __hf, 1086 const key_equal& __eql, 1087 const allocator_type& __a) 1088 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1089 __table_.__rehash_unique(__n); 1090 insert(__first, __last); 1091} 1092 1093template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1094unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u) : __table_(__u.__table_) { 1095 __table_.__rehash_unique(__u.bucket_count()); 1096 insert(__u.begin(), __u.end()); 1097} 1098 1099template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1100unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u, const allocator_type& __a) 1101 : __table_(__u.__table_, typename __table::allocator_type(__a)) { 1102 __table_.__rehash_unique(__u.bucket_count()); 1103 insert(__u.begin(), __u.end()); 1104} 1105 1106template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1107template <class _InputIterator> 1108inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 1109 for (; __first != __last; ++__first) 1110 __table_.__insert_unique(*__first); 1111} 1112 1113template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1114typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1115unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) { 1116 __node_allocator& __na = __table_.__node_alloc(); 1117 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1118 __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().first), __k); 1119 __h.get_deleter().__first_constructed = true; 1120 __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().second)); 1121 __h.get_deleter().__second_constructed = true; 1122 return __h; 1123} 1124 1125template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1126_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) { 1127 iterator __i = find(__k); 1128 if (__i != end()) 1129 return __i->second; 1130 __node_holder __h = __construct_node_with_key(__k); 1131 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1132 __h.release(); 1133 return __r.first->second; 1134} 1135 1136template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1137_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) { 1138 iterator __i = find(__k); 1139 if (__i == end()) 1140 __throw_out_of_range("unordered_map::at: key not found"); 1141 return __i->second; 1142} 1143 1144template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1145const _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const { 1146 const_iterator __i = find(__k); 1147 if (__i == end()) 1148 __throw_out_of_range("unordered_map::at: key not found"); 1149 return __i->second; 1150} 1151 1152template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1153inline _LIBCPP_HIDE_FROM_ABI void 1154swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 1155 __x.swap(__y); 1156} 1157 1158template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1159_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1160 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 1161 if (__x.size() != __y.size()) 1162 return false; 1163 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1164 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { 1165 const_iterator __j = __y.find(__i->first); 1166 if (__j == __ey || !(*__i == *__j)) 1167 return false; 1168 } 1169 return true; 1170} 1171 1172template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1173inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1174 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 1175 return !(__x == __y); 1176} 1177 1178template <class _Key, 1179 class _Tp, 1180 class _Hash = hash<_Key>, 1181 class _Pred = equal_to<_Key>, 1182 class _Alloc = allocator<pair<const _Key, _Tp> > > 1183class _LIBCPP_TEMPLATE_VIS unordered_multimap { 1184public: 1185 // types 1186 typedef _Key key_type; 1187 typedef _Tp mapped_type; 1188 typedef __type_identity_t<_Hash> hasher; 1189 typedef __type_identity_t<_Pred> key_equal; 1190 typedef __type_identity_t<_Alloc> allocator_type; 1191 typedef pair<const key_type, mapped_type> value_type; 1192 typedef value_type& reference; 1193 typedef const value_type& const_reference; 1194 static_assert(__check_valid_allocator<allocator_type>::value, ""); 1195 static_assert(is_same<value_type, typename allocator_type::value_type>::value, 1196 "Allocator::value_type must be same type as value_type"); 1197 1198private: 1199 typedef __hash_value_type<key_type, mapped_type> __value_type; 1200 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher; 1201 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal; 1202 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; 1203 1204 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; 1205 1206 __table __table_; 1207 1208 typedef typename __table::_NodeTypes _NodeTypes; 1209 typedef typename __table::__node_traits __node_traits; 1210 typedef typename __table::__node_allocator __node_allocator; 1211 typedef typename __table::__node __node; 1212 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1213 typedef unique_ptr<__node, _Dp> __node_holder; 1214 typedef allocator_traits<allocator_type> __alloc_traits; 1215 static_assert(is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value, 1216 "Allocator uses different size_type for different types"); 1217 1218public: 1219 typedef typename __alloc_traits::pointer pointer; 1220 typedef typename __alloc_traits::const_pointer const_pointer; 1221 typedef typename __table::size_type size_type; 1222 typedef typename __table::difference_type difference_type; 1223 1224 typedef __hash_map_iterator<typename __table::iterator> iterator; 1225 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1226 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1227 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1228 1229 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1230 friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1231 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 1232 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1233 1234 _LIBCPP_HIDE_FROM_ABI unordered_multimap() {} 1235 explicit _LIBCPP_HIDE_FROM_ABI 1236 unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 1237 _LIBCPP_HIDE_FROM_ABI 1238 unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 1239 template <class _InputIterator> 1240 _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last); 1241 template <class _InputIterator> 1242 _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1243 _InputIterator __first, 1244 _InputIterator __last, 1245 size_type __n, 1246 const hasher& __hf = hasher(), 1247 const key_equal& __eql = key_equal()); 1248 template <class _InputIterator> 1249 _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1250 _InputIterator __first, 1251 _InputIterator __last, 1252 size_type __n, 1253 const hasher& __hf, 1254 const key_equal& __eql, 1255 const allocator_type& __a); 1256 1257 _LIBCPP_HIDE_FROM_ABI explicit unordered_multimap(const allocator_type& __a); 1258 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u); 1259 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1260 1261 _LIBCPP_HIDE_FROM_ABI ~unordered_multimap() { 1262 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), ""); 1263 } 1264 1265 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(const unordered_multimap& __u) { 1266 if (this != std::addressof(__u)) { 1267 __table_.clear(); 1268 __table_.hash_function() = __u.__table_.hash_function(); 1269 __table_.key_eq() = __u.__table_.key_eq(); 1270 __table_.max_load_factor() = __u.__table_.max_load_factor(); 1271 __table_.__copy_assign_alloc(__u.__table_); 1272 insert(__u.begin(), __u.end()); 1273 } 1274 return *this; 1275 } 1276 1277 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 1278 return allocator_type(__table_.__node_alloc()); 1279 } 1280 1281 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 1282 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 1283 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 1284 1285 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 1286 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 1287 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 1288 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 1289 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 1290 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 1291 1292 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); } 1293 1294 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) { 1295 return __table_.__insert_multi(__p.__i_, __x); 1296 } 1297 1298 template <class _InputIterator> 1299 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 1300 1301 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); } 1302 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); } 1303 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } 1304 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 1305 return __table_.erase(__first.__i_, __last.__i_); 1306 } 1307 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 1308 1309 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap& __u) { __table_.swap(__u.__table_); } 1310 1311 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); } 1312 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } 1313 1314 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 1315 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 1316 1317 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } 1318 1319 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1320 return __table_.__equal_range_multi(__k); 1321 } 1322 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1323 return __table_.__equal_range_multi(__k); 1324 } 1325 1326 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 1327 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 1328 1329 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 1330 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 1331 1332 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 1333 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 1334 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 1335 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 1336 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 1337 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 1338 1339 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 1340 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 1341 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 1342 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); } 1343 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); } 1344}; 1345 1346template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1347unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1348 size_type __n, const hasher& __hf, const key_equal& __eql) 1349 : __table_(__hf, __eql) { 1350 __table_.__rehash_multi(__n); 1351} 1352 1353template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1354unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1355 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1356 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1357 __table_.__rehash_multi(__n); 1358} 1359 1360template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1361template <class _InputIterator> 1362unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(_InputIterator __first, _InputIterator __last) { 1363 insert(__first, __last); 1364} 1365 1366template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1367template <class _InputIterator> 1368unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1369 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1370 : __table_(__hf, __eql) { 1371 __table_.__rehash_multi(__n); 1372 insert(__first, __last); 1373} 1374 1375template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1376template <class _InputIterator> 1377unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1378 _InputIterator __first, 1379 _InputIterator __last, 1380 size_type __n, 1381 const hasher& __hf, 1382 const key_equal& __eql, 1383 const allocator_type& __a) 1384 : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1385 __table_.__rehash_multi(__n); 1386 insert(__first, __last); 1387} 1388 1389template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1390inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const allocator_type& __a) 1391 : __table_(typename __table::allocator_type(__a)) {} 1392 1393template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1394unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const unordered_multimap& __u) 1395 : __table_(__u.__table_) { 1396 __table_.__rehash_multi(__u.bucket_count()); 1397 insert(__u.begin(), __u.end()); 1398} 1399 1400template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1401unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1402 const unordered_multimap& __u, const allocator_type& __a) 1403 : __table_(__u.__table_, typename __table::allocator_type(__a)) { 1404 __table_.__rehash_multi(__u.bucket_count()); 1405 insert(__u.begin(), __u.end()); 1406} 1407 1408template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1409template <class _InputIterator> 1410inline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 1411 for (; __first != __last; ++__first) 1412 __table_.__insert_multi(*__first); 1413} 1414 1415template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1416inline _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1417 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 1418 __x.swap(__y); 1419} 1420 1421template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1422_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1423 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 1424 if (__x.size() != __y.size()) 1425 return false; 1426 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1427 typedef pair<const_iterator, const_iterator> _EqRng; 1428 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { 1429 _EqRng __xeq = __x.equal_range(__i->first); 1430 _EqRng __yeq = __y.equal_range(__i->first); 1431 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || 1432 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1433 return false; 1434 __i = __xeq.second; 1435 } 1436 return true; 1437} 1438 1439template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1440inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1441 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 1442 return !(__x == __y); 1443} 1444 1445_LIBCPP_END_NAMESPACE_STD 1446 1447_LIBCPP_POP_MACROS 1448 1449#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) 1450# include <__cxx03/algorithm> 1451# include <__cxx03/cstdlib> 1452# include <__cxx03/iterator> 1453# include <__cxx03/type_traits> 1454#endif 1455 1456#endif // _LIBCPP___CXX03_UNORDERED_MAP 1457