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_SET 11#define _LIBCPP_UNORDERED_SET 12 13// clang-format off 14 15/* 16 17 unordered_set synopsis 18 19#include <initializer_list> 20 21namespace std 22{ 23 24template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 25 class Alloc = allocator<Value>> 26class unordered_set 27{ 28public: 29 // types 30 typedef Value key_type; 31 typedef key_type value_type; 32 typedef Hash hasher; 33 typedef Pred key_equal; 34 typedef Alloc allocator_type; 35 typedef value_type& reference; 36 typedef const value_type& const_reference; 37 typedef typename allocator_traits<allocator_type>::pointer pointer; 38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 39 typedef typename allocator_traits<allocator_type>::size_type size_type; 40 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 41 42 typedef /unspecified/ iterator; 43 typedef /unspecified/ const_iterator; 44 typedef /unspecified/ local_iterator; 45 typedef /unspecified/ const_local_iterator; 46 47 typedef unspecified node_type unspecified; // C++17 48 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 49 50 unordered_set() 51 noexcept( 52 is_nothrow_default_constructible<hasher>::value && 53 is_nothrow_default_constructible<key_equal>::value && 54 is_nothrow_default_constructible<allocator_type>::value); 55 explicit unordered_set(size_type n, const hasher& hf = hasher(), 56 const key_equal& eql = key_equal(), 57 const allocator_type& a = allocator_type()); 58 template <class InputIterator> 59 unordered_set(InputIterator f, InputIterator l, 60 size_type n = 0, const hasher& hf = hasher(), 61 const key_equal& eql = key_equal(), 62 const allocator_type& a = allocator_type()); 63 template<container-compatible-range<value_type> R> 64 unordered_set(from_range_t, R&& rg, size_type n = see below, 65 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 66 const allocator_type& a = allocator_type()); // C++23 67 explicit unordered_set(const allocator_type&); 68 unordered_set(const unordered_set&); 69 unordered_set(const unordered_set&, const Allocator&); 70 unordered_set(unordered_set&&) 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_set(unordered_set&&, const Allocator&); 76 unordered_set(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_set(size_type n, const allocator_type& a); // C++14 80 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14 81 template <class InputIterator> 82 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 83 template <class InputIterator> 84 unordered_set(InputIterator f, InputIterator l, size_type n, 85 const hasher& hf, const allocator_type& a); // C++14 86 template<container-compatible-range<value_type> R> 87 unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a) 88 : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 89 template<container-compatible-range<value_type> R> 90 unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) 91 : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 92 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 93 unordered_set(initializer_list<value_type> il, size_type n, 94 const hasher& hf, const allocator_type& a); // C++14 95 ~unordered_set(); 96 unordered_set& operator=(const unordered_set&); 97 unordered_set& operator=(unordered_set&&) 98 noexcept( 99 allocator_type::propagate_on_container_move_assignment::value && 100 is_nothrow_move_assignable<allocator_type>::value && 101 is_nothrow_move_assignable<hasher>::value && 102 is_nothrow_move_assignable<key_equal>::value); 103 unordered_set& operator=(initializer_list<value_type>); 104 105 allocator_type get_allocator() const noexcept; 106 107 bool empty() const noexcept; 108 size_type size() const noexcept; 109 size_type max_size() const noexcept; 110 111 iterator begin() noexcept; 112 iterator end() noexcept; 113 const_iterator begin() const noexcept; 114 const_iterator end() const noexcept; 115 const_iterator cbegin() const noexcept; 116 const_iterator cend() const noexcept; 117 118 template <class... Args> 119 pair<iterator, bool> emplace(Args&&... args); 120 template <class... Args> 121 iterator emplace_hint(const_iterator position, Args&&... args); 122 pair<iterator, bool> insert(const value_type& obj); 123 pair<iterator, bool> insert(value_type&& obj); 124 iterator insert(const_iterator hint, const value_type& obj); 125 iterator insert(const_iterator hint, value_type&& obj); 126 template <class InputIterator> 127 void insert(InputIterator first, InputIterator last); 128 template<container-compatible-range<value_type> R> 129 void insert_range(R&& rg); // C++23 130 void insert(initializer_list<value_type>); 131 132 node_type extract(const_iterator position); // C++17 133 node_type extract(const key_type& x); // C++17 134 insert_return_type insert(node_type&& nh); // C++17 135 iterator insert(const_iterator hint, node_type&& nh); // C++17 136 137 iterator erase(const_iterator position); 138 iterator erase(iterator position); // C++14 139 size_type erase(const key_type& k); 140 iterator erase(const_iterator first, const_iterator last); 141 void clear() noexcept; 142 143 template<class H2, class P2> 144 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 145 template<class H2, class P2> 146 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 147 template<class H2, class P2> 148 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 149 template<class H2, class P2> 150 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 151 152 void swap(unordered_set&) 153 noexcept(allocator_traits<Allocator>::is_always_equal::value && 154 noexcept(swap(declval<hasher&>(), declval<hasher&>())) && 155 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17 156 157 hasher hash_function() const; 158 key_equal key_eq() const; 159 160 iterator find(const key_type& k); 161 const_iterator find(const key_type& k) const; 162 template<typename K> 163 iterator find(const K& x); // C++20 164 template<typename K> 165 const_iterator find(const K& x) const; // C++20 166 size_type count(const key_type& k) const; 167 template<typename K> 168 size_type count(const K& k) const; // C++20 169 bool contains(const key_type& k) const; // C++20 170 template<typename K> 171 bool contains(const K& k) const; // C++20 172 pair<iterator, iterator> equal_range(const key_type& k); 173 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 174 template<typename K> 175 pair<iterator, iterator> equal_range(const K& k); // C++20 176 template<typename K> 177 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 178 179 size_type bucket_count() const noexcept; 180 size_type max_bucket_count() const noexcept; 181 182 size_type bucket_size(size_type n) const; 183 size_type bucket(const key_type& k) const; 184 185 local_iterator begin(size_type n); 186 local_iterator end(size_type n); 187 const_local_iterator begin(size_type n) const; 188 const_local_iterator end(size_type n) const; 189 const_local_iterator cbegin(size_type n) const; 190 const_local_iterator cend(size_type n) const; 191 192 float load_factor() const noexcept; 193 float max_load_factor() const noexcept; 194 void max_load_factor(float z); 195 void rehash(size_type n); 196 void reserve(size_type n); 197}; 198 199template<class InputIterator, 200 class Hash = hash<typename iterator_traits<InputIterator>::value_type>, 201 class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>, 202 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 203unordered_set(InputIterator, InputIterator, typename see below::size_type = see below, 204 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 205 -> unordered_set<typename iterator_traits<InputIterator>::value_type, 206 Hash, Pred, Allocator>; // C++17 207 208template<ranges::input_range R, 209 class Hash = hash<ranges::range_value_t<R>>, 210 class Pred = equal_to<ranges::range_value_t<R>>, 211 class Allocator = allocator<ranges::range_value_t<R>>> 212 unordered_set(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 213 -> unordered_set<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23 214 215template<class T, class Hash = hash<T>, 216 class Pred = equal_to<T>, class Allocator = allocator<T>> 217unordered_set(initializer_list<T>, typename see below::size_type = see below, 218 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 219 -> unordered_set<T, Hash, Pred, Allocator>; // C++17 220 221template<class InputIterator, class Allocator> 222unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator) 223 -> unordered_set<typename iterator_traits<InputIterator>::value_type, 224 hash<typename iterator_traits<InputIterator>::value_type>, 225 equal_to<typename iterator_traits<InputIterator>::value_type>, 226 Allocator>; // C++17 227 228template<class InputIterator, class Hash, class Allocator> 229unordered_set(InputIterator, InputIterator, typename see below::size_type, 230 Hash, Allocator) 231 -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash, 232 equal_to<typename iterator_traits<InputIterator>::value_type>, 233 Allocator>; // C++17 234 235template<ranges::input_range R, class Allocator> 236 unordered_set(from_range_t, R&&, typename see below::size_type, Allocator) 237 -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>, 238 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 239 240template<ranges::input_range R, class Allocator> 241 unordered_set(from_range_t, R&&, Allocator) 242 -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>, 243 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 244 245template<ranges::input_range R, class Hash, class Allocator> 246 unordered_set(from_range_t, R&&, typename see below::size_type, Hash, Allocator) 247 -> unordered_set<ranges::range_value_t<R>, Hash, 248 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 249 250template<class T, class Allocator> 251unordered_set(initializer_list<T>, typename see below::size_type, Allocator) 252 -> unordered_set<T, hash<T>, equal_to<T>, Allocator>; // C++17 253 254template<class T, class Hash, class Allocator> 255unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator) 256 -> unordered_set<T, Hash, equal_to<T>, Allocator>; // C++17 257 258template <class Value, class Hash, class Pred, class Alloc> 259 void swap(unordered_set<Value, Hash, Pred, Alloc>& x, 260 unordered_set<Value, Hash, Pred, Alloc>& y) 261 noexcept(noexcept(x.swap(y))); 262 263template <class Value, class Hash, class Pred, class Alloc> 264 bool 265 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x, 266 const unordered_set<Value, Hash, Pred, Alloc>& y); 267 268template <class Value, class Hash, class Pred, class Alloc> 269 bool 270 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x, 271 const unordered_set<Value, Hash, Pred, Alloc>& y); // removed in C++20 272 273template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 274 class Alloc = allocator<Value>> 275class unordered_multiset 276{ 277public: 278 // types 279 typedef Value key_type; 280 typedef key_type value_type; 281 typedef Hash hasher; 282 typedef Pred key_equal; 283 typedef Alloc allocator_type; 284 typedef value_type& reference; 285 typedef const value_type& const_reference; 286 typedef typename allocator_traits<allocator_type>::pointer pointer; 287 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 288 typedef typename allocator_traits<allocator_type>::size_type size_type; 289 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 290 291 typedef /unspecified/ iterator; 292 typedef /unspecified/ const_iterator; 293 typedef /unspecified/ local_iterator; 294 typedef /unspecified/ const_local_iterator; 295 296 typedef unspecified node_type unspecified; // C++17 297 298 unordered_multiset() 299 noexcept( 300 is_nothrow_default_constructible<hasher>::value && 301 is_nothrow_default_constructible<key_equal>::value && 302 is_nothrow_default_constructible<allocator_type>::value); 303 explicit unordered_multiset(size_type n, const hasher& hf = hasher(), 304 const key_equal& eql = key_equal(), 305 const allocator_type& a = allocator_type()); 306 template <class InputIterator> 307 unordered_multiset(InputIterator f, InputIterator l, 308 size_type n = 0, const hasher& hf = hasher(), 309 const key_equal& eql = key_equal(), 310 const allocator_type& a = allocator_type()); 311 template<container-compatible-range<value_type> R> 312 unordered_multiset(from_range_t, R&& rg, size_type n = see below, 313 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 314 const allocator_type& a = allocator_type()); // C++23 315 explicit unordered_multiset(const allocator_type&); 316 unordered_multiset(const unordered_multiset&); 317 unordered_multiset(const unordered_multiset&, const Allocator&); 318 unordered_multiset(unordered_multiset&&) 319 noexcept( 320 is_nothrow_move_constructible<hasher>::value && 321 is_nothrow_move_constructible<key_equal>::value && 322 is_nothrow_move_constructible<allocator_type>::value); 323 unordered_multiset(unordered_multiset&&, const Allocator&); 324 unordered_multiset(initializer_list<value_type>, size_type n = /see below/, 325 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 326 const allocator_type& a = allocator_type()); 327 unordered_multiset(size_type n, const allocator_type& a); // C++14 328 unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14 329 template <class InputIterator> 330 unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 331 template <class InputIterator> 332 unordered_multiset(InputIterator f, InputIterator l, size_type n, 333 const hasher& hf, const allocator_type& a); // C++14 334 template<container-compatible-range<value_type> R> 335 unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a) 336 : unordered_multiset(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 337 template<container-compatible-range<value_type> R> 338 unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) 339 : unordered_multiset(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 340 unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 341 unordered_multiset(initializer_list<value_type> il, size_type n, 342 const hasher& hf, const allocator_type& a); // C++14 343 ~unordered_multiset(); 344 unordered_multiset& operator=(const unordered_multiset&); 345 unordered_multiset& operator=(unordered_multiset&&) 346 noexcept( 347 allocator_type::propagate_on_container_move_assignment::value && 348 is_nothrow_move_assignable<allocator_type>::value && 349 is_nothrow_move_assignable<hasher>::value && 350 is_nothrow_move_assignable<key_equal>::value); 351 unordered_multiset& operator=(initializer_list<value_type>); 352 353 allocator_type get_allocator() const noexcept; 354 355 bool empty() const noexcept; 356 size_type size() const noexcept; 357 size_type max_size() const noexcept; 358 359 iterator begin() noexcept; 360 iterator end() noexcept; 361 const_iterator begin() const noexcept; 362 const_iterator end() const noexcept; 363 const_iterator cbegin() const noexcept; 364 const_iterator cend() const noexcept; 365 366 template <class... Args> 367 iterator emplace(Args&&... args); 368 template <class... Args> 369 iterator emplace_hint(const_iterator position, Args&&... args); 370 iterator insert(const value_type& obj); 371 iterator insert(value_type&& obj); 372 iterator insert(const_iterator hint, const value_type& obj); 373 iterator insert(const_iterator hint, value_type&& obj); 374 template <class InputIterator> 375 void insert(InputIterator first, InputIterator last); 376 template<container-compatible-range<value_type> R> 377 void insert_range(R&& rg); // C++23 378 void insert(initializer_list<value_type>); 379 380 node_type extract(const_iterator position); // C++17 381 node_type extract(const key_type& x); // C++17 382 iterator insert(node_type&& nh); // C++17 383 iterator insert(const_iterator hint, node_type&& nh); // C++17 384 385 iterator erase(const_iterator position); 386 iterator erase(iterator position); // C++14 387 size_type erase(const key_type& k); 388 iterator erase(const_iterator first, const_iterator last); 389 void clear() noexcept; 390 391 template<class H2, class P2> 392 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 393 template<class H2, class P2> 394 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 395 template<class H2, class P2> 396 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 397 template<class H2, class P2> 398 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 399 400 void swap(unordered_multiset&) 401 noexcept(allocator_traits<Allocator>::is_always_equal::value && 402 noexcept(swap(declval<hasher&>(), declval<hasher&>())) && 403 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17 404 405 hasher hash_function() const; 406 key_equal key_eq() const; 407 408 iterator find(const key_type& k); 409 const_iterator find(const key_type& k) const; 410 template<typename K> 411 iterator find(const K& x); // C++20 412 template<typename K> 413 const_iterator find(const K& x) const; // C++20 414 size_type count(const key_type& k) const; 415 template<typename K> 416 size_type count(const K& k) const; // C++20 417 bool contains(const key_type& k) const; // C++20 418 template<typename K> 419 bool contains(const K& k) const; // C++20 420 pair<iterator, iterator> equal_range(const key_type& k); 421 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 422 template<typename K> 423 pair<iterator, iterator> equal_range(const K& k); // C++20 424 template<typename K> 425 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 426 427 size_type bucket_count() const noexcept; 428 size_type max_bucket_count() const noexcept; 429 430 size_type bucket_size(size_type n) const; 431 size_type bucket(const key_type& k) const; 432 433 local_iterator begin(size_type n); 434 local_iterator end(size_type n); 435 const_local_iterator begin(size_type n) const; 436 const_local_iterator end(size_type n) const; 437 const_local_iterator cbegin(size_type n) const; 438 const_local_iterator cend(size_type n) const; 439 440 float load_factor() const noexcept; 441 float max_load_factor() const noexcept; 442 void max_load_factor(float z); 443 void rehash(size_type n); 444 void reserve(size_type n); 445}; 446 447template<class InputIterator, 448 class Hash = hash<typename iterator_traits<InputIterator>::value_type>, 449 class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>, 450 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 451unordered_multiset(InputIterator, InputIterator, see below::size_type = see below, 452 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 453 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, 454 Hash, Pred, Allocator>; // C++17 455 456template<ranges::input_range R, 457 class Hash = hash<ranges::range_value_t<R>>, 458 class Pred = equal_to<ranges::range_value_t<R>>, 459 class Allocator = allocator<ranges::range_value_t<R>>> 460 unordered_multiset(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 461 -> unordered_multiset<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23 462 463template<class T, class Hash = hash<T>, 464 class Pred = equal_to<T>, class Allocator = allocator<T>> 465unordered_multiset(initializer_list<T>, typename see below::size_type = see below, 466 Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 467 -> unordered_multiset<T, Hash, Pred, Allocator>; // C++17 468 469template<class InputIterator, class Allocator> 470unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator) 471 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, 472 hash<typename iterator_traits<InputIterator>::value_type>, 473 equal_to<typename iterator_traits<InputIterator>::value_type>, 474 Allocator>; // C++17 475 476template<class InputIterator, class Hash, class Allocator> 477unordered_multiset(InputIterator, InputIterator, typename see below::size_type, 478 Hash, Allocator) 479 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash, 480 equal_to<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17 481 482template<ranges::input_range R, class Allocator> 483 unordered_multiset(from_range_t, R&&, typename see below::size_type, Allocator) 484 -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>, 485 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 486 487template<ranges::input_range R, class Allocator> 488 unordered_multiset(from_range_t, R&&, Allocator) 489 -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>, 490 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 491 492template<ranges::input_range R, class Hash, class Allocator> 493 unordered_multiset(from_range_t, R&&, typename see below::size_type, Hash, Allocator) 494 -> unordered_multiset<ranges::range_value_t<R>, Hash, 495 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 496 497template<class T, class Allocator> 498unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator) 499 -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>; // C++17 500 501template<class T, class Hash, class Allocator> 502unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator) 503 -> unordered_multiset<T, Hash, equal_to<T>, Allocator>; // C++17 504 505template <class Value, class Hash, class Pred, class Alloc> 506 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x, 507 unordered_multiset<Value, Hash, Pred, Alloc>& y) 508 noexcept(noexcept(x.swap(y))); 509 510template <class K, class T, class H, class P, class A, class Predicate> 511 typename unordered_set<K, T, H, P, A>::size_type 512 erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20 513 514template <class K, class T, class H, class P, class A, class Predicate> 515 typename unordered_multiset<K, T, H, P, A>::size_type 516 erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20 517 518 519template <class Value, class Hash, class Pred, class Alloc> 520 bool 521 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 522 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 523 524template <class Value, class Hash, class Pred, class Alloc> 525 bool 526 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 527 const unordered_multiset<Value, Hash, Pred, Alloc>& y); // removed in C++20 528} // std 529 530*/ 531 532// clang-format on 533 534#include <__algorithm/is_permutation.h> 535#include <__assert> 536#include <__config> 537#include <__functional/hash.h> 538#include <__functional/is_transparent.h> 539#include <__functional/operations.h> 540#include <__hash_table> 541#include <__iterator/distance.h> 542#include <__iterator/erase_if_container.h> 543#include <__iterator/iterator_traits.h> 544#include <__iterator/ranges_iterator_traits.h> 545#include <__memory/addressof.h> 546#include <__memory/allocator.h> 547#include <__memory/allocator_traits.h> 548#include <__memory_resource/polymorphic_allocator.h> 549#include <__node_handle> 550#include <__ranges/concepts.h> 551#include <__ranges/container_compatible_range.h> 552#include <__ranges/from_range.h> 553#include <__type_traits/container_traits.h> 554#include <__type_traits/enable_if.h> 555#include <__type_traits/invoke.h> 556#include <__type_traits/is_allocator.h> 557#include <__type_traits/is_integral.h> 558#include <__type_traits/is_nothrow_assignable.h> 559#include <__type_traits/is_nothrow_constructible.h> 560#include <__type_traits/is_same.h> 561#include <__type_traits/is_swappable.h> 562#include <__type_traits/type_identity.h> 563#include <__utility/forward.h> 564#include <__utility/move.h> 565#include <__utility/pair.h> 566#include <version> 567 568// standard-mandated includes 569 570// [iterator.range] 571#include <__iterator/access.h> 572#include <__iterator/data.h> 573#include <__iterator/empty.h> 574#include <__iterator/reverse_access.h> 575#include <__iterator/size.h> 576 577// [unord.set.syn] 578#include <compare> 579#include <initializer_list> 580 581#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 582# pragma GCC system_header 583#endif 584 585_LIBCPP_PUSH_MACROS 586#include <__undef_macros> 587 588_LIBCPP_BEGIN_NAMESPACE_STD 589 590template <class _Value, class _Hash, class _Pred, class _Alloc> 591class unordered_multiset; 592 593template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > 594class _LIBCPP_TEMPLATE_VIS unordered_set { 595public: 596 // types 597 typedef _Value key_type; 598 typedef key_type value_type; 599 typedef __type_identity_t<_Hash> hasher; 600 typedef __type_identity_t<_Pred> key_equal; 601 typedef __type_identity_t<_Alloc> allocator_type; 602 typedef value_type& reference; 603 typedef const value_type& const_reference; 604 static_assert(__check_valid_allocator<allocator_type>::value, ""); 605 static_assert(is_same<value_type, typename allocator_type::value_type>::value, 606 "Allocator::value_type must be same type as value_type"); 607 608private: 609 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 610 611 __table __table_; 612 613public: 614 typedef typename __table::pointer pointer; 615 typedef typename __table::const_pointer const_pointer; 616 typedef typename __table::size_type size_type; 617 typedef typename __table::difference_type difference_type; 618 619 typedef typename __table::const_iterator iterator; 620 typedef typename __table::const_iterator const_iterator; 621 typedef typename __table::const_local_iterator local_iterator; 622 typedef typename __table::const_local_iterator const_local_iterator; 623 624#if _LIBCPP_STD_VER >= 17 625 typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 626 typedef __insert_return_type<iterator, node_type> insert_return_type; 627#endif 628 629 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 630 friend class _LIBCPP_TEMPLATE_VIS unordered_set; 631 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 632 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 633 634 _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 635 explicit _LIBCPP_HIDE_FROM_ABI 636 unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 637#if _LIBCPP_STD_VER >= 14 638 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a) 639 : unordered_set(__n, hasher(), key_equal(), __a) {} 640 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 641 : unordered_set(__n, __hf, key_equal(), __a) {} 642#endif 643 _LIBCPP_HIDE_FROM_ABI 644 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 645 template <class _InputIterator> 646 _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last); 647 template <class _InputIterator> 648 _LIBCPP_HIDE_FROM_ABI 649 unordered_set(_InputIterator __first, 650 _InputIterator __last, 651 size_type __n, 652 const hasher& __hf = hasher(), 653 const key_equal& __eql = key_equal()); 654 template <class _InputIterator> 655 _LIBCPP_HIDE_FROM_ABI unordered_set( 656 _InputIterator __first, 657 _InputIterator __last, 658 size_type __n, 659 const hasher& __hf, 660 const key_equal& __eql, 661 const allocator_type& __a); 662 663#if _LIBCPP_STD_VER >= 23 664 template <_ContainerCompatibleRange<value_type> _Range> 665 _LIBCPP_HIDE_FROM_ABI unordered_set( 666 from_range_t, 667 _Range&& __range, 668 size_type __n = /*implementation-defined*/ 0, 669 const hasher& __hf = hasher(), 670 const key_equal& __eql = key_equal(), 671 const allocator_type& __a = allocator_type()) 672 : __table_(__hf, __eql, __a) { 673 if (__n > 0) { 674 __table_.__rehash_unique(__n); 675 } 676 insert_range(std::forward<_Range>(__range)); 677 } 678#endif 679 680#if _LIBCPP_STD_VER >= 14 681 template <class _InputIterator> 682 inline _LIBCPP_HIDE_FROM_ABI 683 unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 684 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 685 template <class _InputIterator> 686 _LIBCPP_HIDE_FROM_ABI unordered_set( 687 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 688 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 689#endif 690 691#if _LIBCPP_STD_VER >= 23 692 template <_ContainerCompatibleRange<value_type> _Range> 693 _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 694 : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 695 696 template <_ContainerCompatibleRange<value_type> _Range> 697 _LIBCPP_HIDE_FROM_ABI 698 unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 699 : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 700#endif 701 702 _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a); 703 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u); 704 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a); 705#ifndef _LIBCPP_CXX03_LANG 706 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 707 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a); 708 _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il); 709 _LIBCPP_HIDE_FROM_ABI 710 unordered_set(initializer_list<value_type> __il, 711 size_type __n, 712 const hasher& __hf = hasher(), 713 const key_equal& __eql = key_equal()); 714 _LIBCPP_HIDE_FROM_ABI unordered_set( 715 initializer_list<value_type> __il, 716 size_type __n, 717 const hasher& __hf, 718 const key_equal& __eql, 719 const allocator_type& __a); 720# if _LIBCPP_STD_VER >= 14 721 inline _LIBCPP_HIDE_FROM_ABI 722 unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 723 : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 724 inline _LIBCPP_HIDE_FROM_ABI 725 unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 726 : unordered_set(__il, __n, __hf, key_equal(), __a) {} 727# endif 728#endif // _LIBCPP_CXX03_LANG 729 _LIBCPP_HIDE_FROM_ABI ~unordered_set() { 730 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 731 } 732 733 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) { 734 __table_ = __u.__table_; 735 return *this; 736 } 737#ifndef _LIBCPP_CXX03_LANG 738 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u) 739 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 740 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il); 741#endif // _LIBCPP_CXX03_LANG 742 743 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 744 return allocator_type(__table_.__node_alloc()); 745 } 746 747 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 748 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 749 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 750 751 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 752 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 753 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 754 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 755 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 756 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 757 758#ifndef _LIBCPP_CXX03_LANG 759 template <class... _Args> 760 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) { 761 return __table_.__emplace_unique(std::forward<_Args>(__args)...); 762 } 763 template <class... _Args> 764 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) { 765 return __table_.__emplace_unique(std::forward<_Args>(__args)...).first; 766 } 767 768 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) { 769 return __table_.__insert_unique(std::move(__x)); 770 } 771 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; } 772 773 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 774#endif // _LIBCPP_CXX03_LANG 775 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); } 776 777 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } 778 template <class _InputIterator> 779 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 780 781#if _LIBCPP_STD_VER >= 23 782 template <_ContainerCompatibleRange<value_type> _Range> 783 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 784 for (auto&& __element : __range) { 785 __table_.__insert_unique(std::forward<decltype(__element)>(__element)); 786 } 787 } 788#endif 789 790 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); } 791 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } 792 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 793 return __table_.erase(__first, __last); 794 } 795 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 796 797#if _LIBCPP_STD_VER >= 17 798 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) { 799 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 800 "node_type with incompatible allocator passed to unordered_set::insert()"); 801 return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh)); 802 } 803 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) { 804 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 805 "node_type with incompatible allocator passed to unordered_set::insert()"); 806 return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh)); 807 } 808 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 809 return __table_.template __node_handle_extract<node_type>(__key); 810 } 811 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 812 return __table_.template __node_handle_extract<node_type>(__it); 813 } 814 815 template <class _H2, class _P2> 816 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) { 817 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 818 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 819 __table_.__node_handle_merge_unique(__source.__table_); 820 } 821 template <class _H2, class _P2> 822 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) { 823 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 824 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 825 __table_.__node_handle_merge_unique(__source.__table_); 826 } 827 template <class _H2, class _P2> 828 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) { 829 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 830 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 831 __table_.__node_handle_merge_unique(__source.__table_); 832 } 833 template <class _H2, class _P2> 834 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) { 835 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 836 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 837 __table_.__node_handle_merge_unique(__source.__table_); 838 } 839#endif 840 841 _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) { 842 __table_.swap(__u.__table_); 843 } 844 845 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); } 846 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } 847 848 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 849 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 850#if _LIBCPP_STD_VER >= 20 851 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 852 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 853 return __table_.find(__k); 854 } 855 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 856 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 857 return __table_.find(__k); 858 } 859#endif // _LIBCPP_STD_VER >= 20 860 861 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } 862#if _LIBCPP_STD_VER >= 20 863 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 864 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 865 return __table_.__count_unique(__k); 866 } 867#endif // _LIBCPP_STD_VER >= 20 868 869#if _LIBCPP_STD_VER >= 20 870 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 871 872 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 873 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 874 return find(__k) != end(); 875 } 876#endif // _LIBCPP_STD_VER >= 20 877 878 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 879 return __table_.__equal_range_unique(__k); 880 } 881 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 882 return __table_.__equal_range_unique(__k); 883 } 884#if _LIBCPP_STD_VER >= 20 885 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 886 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 887 return __table_.__equal_range_unique(__k); 888 } 889 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 890 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 891 return __table_.__equal_range_unique(__k); 892 } 893#endif // _LIBCPP_STD_VER >= 20 894 895 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 896 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 897 898 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 899 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 900 901 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 902 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 903 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 904 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 905 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 906 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 907 908 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 909 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 910 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 911 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); } 912 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); } 913}; 914 915#if _LIBCPP_STD_VER >= 17 916template <class _InputIterator, 917 class _Hash = hash<__iter_value_type<_InputIterator>>, 918 class _Pred = equal_to<__iter_value_type<_InputIterator>>, 919 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 920 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 921 class = enable_if_t<!__is_allocator<_Hash>::value>, 922 class = enable_if_t<!is_integral<_Hash>::value>, 923 class = enable_if_t<!__is_allocator<_Pred>::value>, 924 class = enable_if_t<__is_allocator<_Allocator>::value>> 925unordered_set(_InputIterator, 926 _InputIterator, 927 typename allocator_traits<_Allocator>::size_type = 0, 928 _Hash = _Hash(), 929 _Pred = _Pred(), 930 _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 931 932# if _LIBCPP_STD_VER >= 23 933template <ranges::input_range _Range, 934 class _Hash = hash<ranges::range_value_t<_Range>>, 935 class _Pred = equal_to<ranges::range_value_t<_Range>>, 936 class _Allocator = allocator<ranges::range_value_t<_Range>>, 937 class = enable_if_t<!__is_allocator<_Hash>::value>, 938 class = enable_if_t<!is_integral<_Hash>::value>, 939 class = enable_if_t<!__is_allocator<_Pred>::value>, 940 class = enable_if_t<__is_allocator<_Allocator>::value>> 941unordered_set( 942 from_range_t, 943 _Range&&, 944 typename allocator_traits<_Allocator>::size_type = 0, 945 _Hash = _Hash(), 946 _Pred = _Pred(), 947 _Allocator = _Allocator()) -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 948# endif 949 950template <class _Tp, 951 class _Hash = hash<_Tp>, 952 class _Pred = equal_to<_Tp>, 953 class _Allocator = allocator<_Tp>, 954 class = enable_if_t<!__is_allocator<_Hash>::value>, 955 class = enable_if_t<!is_integral<_Hash>::value>, 956 class = enable_if_t<!__is_allocator<_Pred>::value>, 957 class = enable_if_t<__is_allocator<_Allocator>::value>> 958unordered_set(initializer_list<_Tp>, 959 typename allocator_traits<_Allocator>::size_type = 0, 960 _Hash = _Hash(), 961 _Pred = _Pred(), 962 _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 963 964template <class _InputIterator, 965 class _Allocator, 966 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 967 class = enable_if_t<__is_allocator<_Allocator>::value>> 968unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 969 -> unordered_set<__iter_value_type<_InputIterator>, 970 hash<__iter_value_type<_InputIterator>>, 971 equal_to<__iter_value_type<_InputIterator>>, 972 _Allocator>; 973 974template <class _InputIterator, 975 class _Hash, 976 class _Allocator, 977 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 978 class = enable_if_t<!__is_allocator<_Hash>::value>, 979 class = enable_if_t<!is_integral<_Hash>::value>, 980 class = enable_if_t<__is_allocator<_Allocator>::value>> 981unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 982 -> unordered_set<__iter_value_type<_InputIterator>, _Hash, equal_to<__iter_value_type<_InputIterator>>, _Allocator>; 983 984# if _LIBCPP_STD_VER >= 23 985 986template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 987unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 988 -> unordered_set<ranges::range_value_t<_Range>, 989 hash<ranges::range_value_t<_Range>>, 990 equal_to<ranges::range_value_t<_Range>>, 991 _Allocator>; 992 993template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 994unordered_set(from_range_t, _Range&&, _Allocator) 995 -> unordered_set<ranges::range_value_t<_Range>, 996 hash<ranges::range_value_t<_Range>>, 997 equal_to<ranges::range_value_t<_Range>>, 998 _Allocator>; 999 1000template <ranges::input_range _Range, 1001 class _Hash, 1002 class _Allocator, 1003 class = enable_if_t<!__is_allocator<_Hash>::value>, 1004 class = enable_if_t<!is_integral<_Hash>::value>, 1005 class = enable_if_t<__is_allocator<_Allocator>::value>> 1006unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1007 -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 1008 1009# endif 1010 1011template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1012unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 1013 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 1014 1015template <class _Tp, 1016 class _Hash, 1017 class _Allocator, 1018 class = enable_if_t<!__is_allocator<_Hash>::value>, 1019 class = enable_if_t<!is_integral<_Hash>::value>, 1020 class = enable_if_t<__is_allocator<_Allocator>::value>> 1021unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1022 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 1023#endif 1024 1025template <class _Value, class _Hash, class _Pred, class _Alloc> 1026unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql) 1027 : __table_(__hf, __eql) { 1028 __table_.__rehash_unique(__n); 1029} 1030 1031template <class _Value, class _Hash, class _Pred, class _Alloc> 1032unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1033 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1034 : __table_(__hf, __eql, __a) { 1035 __table_.__rehash_unique(__n); 1036} 1037 1038template <class _Value, class _Hash, class _Pred, class _Alloc> 1039template <class _InputIterator> 1040unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) { 1041 insert(__first, __last); 1042} 1043 1044template <class _Value, class _Hash, class _Pred, class _Alloc> 1045template <class _InputIterator> 1046unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1047 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1048 : __table_(__hf, __eql) { 1049 __table_.__rehash_unique(__n); 1050 insert(__first, __last); 1051} 1052 1053template <class _Value, class _Hash, class _Pred, class _Alloc> 1054template <class _InputIterator> 1055unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1056 _InputIterator __first, 1057 _InputIterator __last, 1058 size_type __n, 1059 const hasher& __hf, 1060 const key_equal& __eql, 1061 const allocator_type& __a) 1062 : __table_(__hf, __eql, __a) { 1063 __table_.__rehash_unique(__n); 1064 insert(__first, __last); 1065} 1066 1067template <class _Value, class _Hash, class _Pred, class _Alloc> 1068inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {} 1069 1070template <class _Value, class _Hash, class _Pred, class _Alloc> 1071unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) { 1072 __table_.__rehash_unique(__u.bucket_count()); 1073 insert(__u.begin(), __u.end()); 1074} 1075 1076template <class _Value, class _Hash, class _Pred, class _Alloc> 1077unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a) 1078 : __table_(__u.__table_, __a) { 1079 __table_.__rehash_unique(__u.bucket_count()); 1080 insert(__u.begin(), __u.end()); 1081} 1082 1083#ifndef _LIBCPP_CXX03_LANG 1084 1085template <class _Value, class _Hash, class _Pred, class _Alloc> 1086inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u) 1087 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1088 : __table_(std::move(__u.__table_)) {} 1089 1090template <class _Value, class _Hash, class _Pred, class _Alloc> 1091unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u, const allocator_type& __a) 1092 : __table_(std::move(__u.__table_), __a) { 1093 if (__a != __u.get_allocator()) { 1094 iterator __i = __u.begin(); 1095 while (__u.size() != 0) 1096 __table_.__insert_unique(std::move(__u.__table_.remove(__i++)->__get_value())); 1097 } 1098} 1099 1100template <class _Value, class _Hash, class _Pred, class _Alloc> 1101unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(initializer_list<value_type> __il) { 1102 insert(__il.begin(), __il.end()); 1103} 1104 1105template <class _Value, class _Hash, class _Pred, class _Alloc> 1106unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1107 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1108 : __table_(__hf, __eql) { 1109 __table_.__rehash_unique(__n); 1110 insert(__il.begin(), __il.end()); 1111} 1112 1113template <class _Value, class _Hash, class _Pred, class _Alloc> 1114unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1115 initializer_list<value_type> __il, 1116 size_type __n, 1117 const hasher& __hf, 1118 const key_equal& __eql, 1119 const allocator_type& __a) 1120 : __table_(__hf, __eql, __a) { 1121 __table_.__rehash_unique(__n); 1122 insert(__il.begin(), __il.end()); 1123} 1124 1125template <class _Value, class _Hash, class _Pred, class _Alloc> 1126inline unordered_set<_Value, _Hash, _Pred, _Alloc>& 1127unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 1128 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 1129 __table_ = std::move(__u.__table_); 1130 return *this; 1131} 1132 1133template <class _Value, class _Hash, class _Pred, class _Alloc> 1134inline unordered_set<_Value, _Hash, _Pred, _Alloc>& 1135unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 1136 __table_.__assign_unique(__il.begin(), __il.end()); 1137 return *this; 1138} 1139 1140#endif // _LIBCPP_CXX03_LANG 1141 1142template <class _Value, class _Hash, class _Pred, class _Alloc> 1143template <class _InputIterator> 1144inline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 1145 for (; __first != __last; ++__first) 1146 __table_.__insert_unique(*__first); 1147} 1148 1149template <class _Value, class _Hash, class _Pred, class _Alloc> 1150inline _LIBCPP_HIDE_FROM_ABI void 1151swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1152 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 1153 __x.swap(__y); 1154} 1155 1156#if _LIBCPP_STD_VER >= 20 1157template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> 1158inline _LIBCPP_HIDE_FROM_ABI typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type 1159erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 1160 return std::__libcpp_erase_if_container(__c, __pred); 1161} 1162#endif 1163 1164template <class _Value, class _Hash, class _Pred, class _Alloc> 1165_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1166 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) { 1167 if (__x.size() != __y.size()) 1168 return false; 1169 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1170 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { 1171 const_iterator __j = __y.find(*__i); 1172 if (__j == __ey || !(*__i == *__j)) 1173 return false; 1174 } 1175 return true; 1176} 1177 1178#if _LIBCPP_STD_VER <= 17 1179 1180template <class _Value, class _Hash, class _Pred, class _Alloc> 1181inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1182 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) { 1183 return !(__x == __y); 1184} 1185 1186#endif 1187 1188template <class _Value, class _Hash, class _Pred, class _Alloc> 1189struct __container_traits<unordered_set<_Value, _Hash, _Pred, _Alloc> > { 1190 // http://eel.is/c++draft/unord.req.except#2 1191 // For unordered associative containers, if an exception is thrown by any operation 1192 // other than the container's hash function from within an insert or emplace function 1193 // inserting a single element, the insertion has no effect. 1194 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = 1195 __nothrow_invokable<_Hash, const _Value&>::value; 1196}; 1197 1198template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > 1199class _LIBCPP_TEMPLATE_VIS unordered_multiset { 1200public: 1201 // types 1202 typedef _Value key_type; 1203 typedef key_type value_type; 1204 typedef __type_identity_t<_Hash> hasher; 1205 typedef __type_identity_t<_Pred> key_equal; 1206 typedef __type_identity_t<_Alloc> allocator_type; 1207 typedef value_type& reference; 1208 typedef const value_type& const_reference; 1209 static_assert(is_same<value_type, typename allocator_type::value_type>::value, 1210 "Allocator::value_type must be same type as value_type"); 1211 1212private: 1213 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 1214 1215 __table __table_; 1216 1217public: 1218 typedef typename __table::pointer pointer; 1219 typedef typename __table::const_pointer const_pointer; 1220 typedef typename __table::size_type size_type; 1221 typedef typename __table::difference_type difference_type; 1222 1223 typedef typename __table::const_iterator iterator; 1224 typedef typename __table::const_iterator const_iterator; 1225 typedef typename __table::const_local_iterator local_iterator; 1226 typedef typename __table::const_local_iterator const_local_iterator; 1227 1228#if _LIBCPP_STD_VER >= 17 1229 typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 1230#endif 1231 1232 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 1233 friend class _LIBCPP_TEMPLATE_VIS unordered_set; 1234 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 1235 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 1236 1237 _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 1238 explicit _LIBCPP_HIDE_FROM_ABI 1239 unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 1240 _LIBCPP_HIDE_FROM_ABI 1241 unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 1242#if _LIBCPP_STD_VER >= 14 1243 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a) 1244 : unordered_multiset(__n, hasher(), key_equal(), __a) {} 1245 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 1246 : unordered_multiset(__n, __hf, key_equal(), __a) {} 1247#endif 1248 template <class _InputIterator> 1249 _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last); 1250 template <class _InputIterator> 1251 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1252 _InputIterator __first, 1253 _InputIterator __last, 1254 size_type __n, 1255 const hasher& __hf = hasher(), 1256 const key_equal& __eql = key_equal()); 1257 template <class _InputIterator> 1258 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1259 _InputIterator __first, 1260 _InputIterator __last, 1261 size_type __n, 1262 const hasher& __hf, 1263 const key_equal& __eql, 1264 const allocator_type& __a); 1265 1266#if _LIBCPP_STD_VER >= 23 1267 template <_ContainerCompatibleRange<value_type> _Range> 1268 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1269 from_range_t, 1270 _Range&& __range, 1271 size_type __n = /*implementation-defined*/ 0, 1272 const hasher& __hf = hasher(), 1273 const key_equal& __eql = key_equal(), 1274 const allocator_type& __a = allocator_type()) 1275 : __table_(__hf, __eql, __a) { 1276 if (__n > 0) { 1277 __table_.__rehash_multi(__n); 1278 } 1279 insert_range(std::forward<_Range>(__range)); 1280 } 1281#endif 1282 1283#if _LIBCPP_STD_VER >= 14 1284 template <class _InputIterator> 1285 inline _LIBCPP_HIDE_FROM_ABI 1286 unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1287 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 1288 template <class _InputIterator> 1289 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1290 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 1291 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 1292#endif 1293 1294#if _LIBCPP_STD_VER >= 23 1295 template <_ContainerCompatibleRange<value_type> _Range> 1296 _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 1297 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 1298 1299 template <_ContainerCompatibleRange<value_type> _Range> 1300 _LIBCPP_HIDE_FROM_ABI 1301 unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 1302 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 1303#endif 1304 1305 _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a); 1306 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u); 1307 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 1308#ifndef _LIBCPP_CXX03_LANG 1309 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u) 1310 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1311 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 1312 _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il); 1313 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1314 initializer_list<value_type> __il, 1315 size_type __n, 1316 const hasher& __hf = hasher(), 1317 const key_equal& __eql = key_equal()); 1318 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1319 initializer_list<value_type> __il, 1320 size_type __n, 1321 const hasher& __hf, 1322 const key_equal& __eql, 1323 const allocator_type& __a); 1324# if _LIBCPP_STD_VER >= 14 1325 inline _LIBCPP_HIDE_FROM_ABI 1326 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1327 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 1328 inline _LIBCPP_HIDE_FROM_ABI 1329 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 1330 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 1331# endif 1332#endif // _LIBCPP_CXX03_LANG 1333 _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() { 1334 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 1335 } 1336 1337 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) { 1338 __table_ = __u.__table_; 1339 return *this; 1340 } 1341#ifndef _LIBCPP_CXX03_LANG 1342 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u) 1343 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1344 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il); 1345#endif // _LIBCPP_CXX03_LANG 1346 1347 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 1348 return allocator_type(__table_.__node_alloc()); 1349 } 1350 1351 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 1352 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 1353 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 1354 1355 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 1356 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 1357 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 1358 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 1359 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 1360 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 1361 1362#ifndef _LIBCPP_CXX03_LANG 1363 template <class... _Args> 1364 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { 1365 return __table_.__emplace_multi(std::forward<_Args>(__args)...); 1366 } 1367 template <class... _Args> 1368 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1369 return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...); 1370 } 1371 1372 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); } 1373 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) { 1374 return __table_.__insert_multi(__p, std::move(__x)); 1375 } 1376 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 1377#endif // _LIBCPP_CXX03_LANG 1378 1379 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); } 1380 1381 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) { 1382 return __table_.__insert_multi(__p, __x); 1383 } 1384 1385 template <class _InputIterator> 1386 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 1387 1388#if _LIBCPP_STD_VER >= 23 1389 template <_ContainerCompatibleRange<value_type> _Range> 1390 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 1391 for (auto&& __element : __range) { 1392 __table_.__insert_multi(std::forward<decltype(__element)>(__element)); 1393 } 1394 } 1395#endif 1396 1397#if _LIBCPP_STD_VER >= 17 1398 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) { 1399 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1400 "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1401 return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh)); 1402 } 1403 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 1404 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1405 "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1406 return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh)); 1407 } 1408 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) { 1409 return __table_.template __node_handle_extract<node_type>(__position); 1410 } 1411 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 1412 return __table_.template __node_handle_extract<node_type>(__key); 1413 } 1414 1415 template <class _H2, class _P2> 1416 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) { 1417 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1418 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1419 return __table_.__node_handle_merge_multi(__source.__table_); 1420 } 1421 template <class _H2, class _P2> 1422 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) { 1423 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1424 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1425 return __table_.__node_handle_merge_multi(__source.__table_); 1426 } 1427 template <class _H2, class _P2> 1428 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) { 1429 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1430 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1431 return __table_.__node_handle_merge_multi(__source.__table_); 1432 } 1433 template <class _H2, class _P2> 1434 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) { 1435 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1436 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1437 return __table_.__node_handle_merge_multi(__source.__table_); 1438 } 1439#endif 1440 1441 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); } 1442 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } 1443 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 1444 return __table_.erase(__first, __last); 1445 } 1446 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 1447 1448 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) { 1449 __table_.swap(__u.__table_); 1450 } 1451 1452 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); } 1453 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } 1454 1455 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 1456 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 1457#if _LIBCPP_STD_VER >= 20 1458 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1459 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 1460 return __table_.find(__k); 1461 } 1462 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1463 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 1464 return __table_.find(__k); 1465 } 1466#endif // _LIBCPP_STD_VER >= 20 1467 1468 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } 1469#if _LIBCPP_STD_VER >= 20 1470 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1471 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 1472 return __table_.__count_multi(__k); 1473 } 1474#endif // _LIBCPP_STD_VER >= 20 1475 1476#if _LIBCPP_STD_VER >= 20 1477 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 1478 1479 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1480 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 1481 return find(__k) != end(); 1482 } 1483#endif // _LIBCPP_STD_VER >= 20 1484 1485 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1486 return __table_.__equal_range_multi(__k); 1487 } 1488 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1489 return __table_.__equal_range_multi(__k); 1490 } 1491#if _LIBCPP_STD_VER >= 20 1492 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1493 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 1494 return __table_.__equal_range_multi(__k); 1495 } 1496 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1497 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 1498 return __table_.__equal_range_multi(__k); 1499 } 1500#endif // _LIBCPP_STD_VER >= 20 1501 1502 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 1503 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 1504 1505 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 1506 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 1507 1508 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 1509 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 1510 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 1511 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 1512 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 1513 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 1514 1515 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 1516 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 1517 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 1518 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); } 1519 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); } 1520}; 1521 1522#if _LIBCPP_STD_VER >= 17 1523template <class _InputIterator, 1524 class _Hash = hash<__iter_value_type<_InputIterator>>, 1525 class _Pred = equal_to<__iter_value_type<_InputIterator>>, 1526 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 1527 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1528 class = enable_if_t<!__is_allocator<_Hash>::value>, 1529 class = enable_if_t<!is_integral<_Hash>::value>, 1530 class = enable_if_t<!__is_allocator<_Pred>::value>, 1531 class = enable_if_t<__is_allocator<_Allocator>::value>> 1532unordered_multiset( 1533 _InputIterator, 1534 _InputIterator, 1535 typename allocator_traits<_Allocator>::size_type = 0, 1536 _Hash = _Hash(), 1537 _Pred = _Pred(), 1538 _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 1539 1540# if _LIBCPP_STD_VER >= 23 1541template <ranges::input_range _Range, 1542 class _Hash = hash<ranges::range_value_t<_Range>>, 1543 class _Pred = equal_to<ranges::range_value_t<_Range>>, 1544 class _Allocator = allocator<ranges::range_value_t<_Range>>, 1545 class = enable_if_t<!__is_allocator<_Hash>::value>, 1546 class = enable_if_t<!is_integral<_Hash>::value>, 1547 class = enable_if_t<!__is_allocator<_Pred>::value>, 1548 class = enable_if_t<__is_allocator<_Allocator>::value>> 1549unordered_multiset( 1550 from_range_t, 1551 _Range&&, 1552 typename allocator_traits<_Allocator>::size_type = 0, 1553 _Hash = _Hash(), 1554 _Pred = _Pred(), 1555 _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 1556# endif 1557 1558template <class _Tp, 1559 class _Hash = hash<_Tp>, 1560 class _Pred = equal_to<_Tp>, 1561 class _Allocator = allocator<_Tp>, 1562 class = enable_if_t<!__is_allocator<_Hash>::value>, 1563 class = enable_if_t<!is_integral<_Hash>::value>, 1564 class = enable_if_t<!__is_allocator<_Pred>::value>, 1565 class = enable_if_t<__is_allocator<_Allocator>::value>> 1566unordered_multiset(initializer_list<_Tp>, 1567 typename allocator_traits<_Allocator>::size_type = 0, 1568 _Hash = _Hash(), 1569 _Pred = _Pred(), 1570 _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 1571 1572template <class _InputIterator, 1573 class _Allocator, 1574 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1575 class = enable_if_t<__is_allocator<_Allocator>::value>> 1576unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 1577 -> unordered_multiset<__iter_value_type<_InputIterator>, 1578 hash<__iter_value_type<_InputIterator>>, 1579 equal_to<__iter_value_type<_InputIterator>>, 1580 _Allocator>; 1581 1582template <class _InputIterator, 1583 class _Hash, 1584 class _Allocator, 1585 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1586 class = enable_if_t<!__is_allocator<_Hash>::value>, 1587 class = enable_if_t<!is_integral<_Hash>::value>, 1588 class = enable_if_t<__is_allocator<_Allocator>::value>> 1589unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1590 -> unordered_multiset<__iter_value_type<_InputIterator>, 1591 _Hash, 1592 equal_to<__iter_value_type<_InputIterator>>, 1593 _Allocator>; 1594 1595# if _LIBCPP_STD_VER >= 23 1596 1597template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1598unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 1599 -> unordered_multiset<ranges::range_value_t<_Range>, 1600 hash<ranges::range_value_t<_Range>>, 1601 equal_to<ranges::range_value_t<_Range>>, 1602 _Allocator>; 1603 1604template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1605unordered_multiset(from_range_t, _Range&&, _Allocator) 1606 -> unordered_multiset<ranges::range_value_t<_Range>, 1607 hash<ranges::range_value_t<_Range>>, 1608 equal_to<ranges::range_value_t<_Range>>, 1609 _Allocator>; 1610 1611template <ranges::input_range _Range, 1612 class _Hash, 1613 class _Allocator, 1614 class = enable_if_t<!__is_allocator<_Hash>::value>, 1615 class = enable_if_t<!is_integral<_Hash>::value>, 1616 class = enable_if_t<__is_allocator<_Allocator>::value>> 1617unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1618 -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 1619 1620# endif 1621 1622template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1623unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 1624 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 1625 1626template <class _Tp, 1627 class _Hash, 1628 class _Allocator, 1629 class = enable_if_t<!__is_allocator<_Hash>::value>, 1630 class = enable_if_t<!is_integral<_Hash>::value>, 1631 class = enable_if_t<__is_allocator<_Allocator>::value>> 1632unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1633 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 1634#endif 1635 1636template <class _Value, class _Hash, class _Pred, class _Alloc> 1637unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1638 size_type __n, const hasher& __hf, const key_equal& __eql) 1639 : __table_(__hf, __eql) { 1640 __table_.__rehash_multi(__n); 1641} 1642 1643template <class _Value, class _Hash, class _Pred, class _Alloc> 1644unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1645 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1646 : __table_(__hf, __eql, __a) { 1647 __table_.__rehash_multi(__n); 1648} 1649 1650template <class _Value, class _Hash, class _Pred, class _Alloc> 1651template <class _InputIterator> 1652unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) { 1653 insert(__first, __last); 1654} 1655 1656template <class _Value, class _Hash, class _Pred, class _Alloc> 1657template <class _InputIterator> 1658unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1659 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1660 : __table_(__hf, __eql) { 1661 __table_.__rehash_multi(__n); 1662 insert(__first, __last); 1663} 1664 1665template <class _Value, class _Hash, class _Pred, class _Alloc> 1666template <class _InputIterator> 1667unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1668 _InputIterator __first, 1669 _InputIterator __last, 1670 size_type __n, 1671 const hasher& __hf, 1672 const key_equal& __eql, 1673 const allocator_type& __a) 1674 : __table_(__hf, __eql, __a) { 1675 __table_.__rehash_multi(__n); 1676 insert(__first, __last); 1677} 1678 1679template <class _Value, class _Hash, class _Pred, class _Alloc> 1680inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a) 1681 : __table_(__a) {} 1682 1683template <class _Value, class _Hash, class _Pred, class _Alloc> 1684unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u) 1685 : __table_(__u.__table_) { 1686 __table_.__rehash_multi(__u.bucket_count()); 1687 insert(__u.begin(), __u.end()); 1688} 1689 1690template <class _Value, class _Hash, class _Pred, class _Alloc> 1691unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1692 const unordered_multiset& __u, const allocator_type& __a) 1693 : __table_(__u.__table_, __a) { 1694 __table_.__rehash_multi(__u.bucket_count()); 1695 insert(__u.begin(), __u.end()); 1696} 1697 1698#ifndef _LIBCPP_CXX03_LANG 1699 1700template <class _Value, class _Hash, class _Pred, class _Alloc> 1701inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(unordered_multiset&& __u) 1702 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1703 : __table_(std::move(__u.__table_)) {} 1704 1705template <class _Value, class _Hash, class _Pred, class _Alloc> 1706unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1707 unordered_multiset&& __u, const allocator_type& __a) 1708 : __table_(std::move(__u.__table_), __a) { 1709 if (__a != __u.get_allocator()) { 1710 iterator __i = __u.begin(); 1711 while (__u.size() != 0) 1712 __table_.__insert_multi(std::move(__u.__table_.remove(__i++)->__get_value())); 1713 } 1714} 1715 1716template <class _Value, class _Hash, class _Pred, class _Alloc> 1717unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) { 1718 insert(__il.begin(), __il.end()); 1719} 1720 1721template <class _Value, class _Hash, class _Pred, class _Alloc> 1722unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1723 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1724 : __table_(__hf, __eql) { 1725 __table_.__rehash_multi(__n); 1726 insert(__il.begin(), __il.end()); 1727} 1728 1729template <class _Value, class _Hash, class _Pred, class _Alloc> 1730unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1731 initializer_list<value_type> __il, 1732 size_type __n, 1733 const hasher& __hf, 1734 const key_equal& __eql, 1735 const allocator_type& __a) 1736 : __table_(__hf, __eql, __a) { 1737 __table_.__rehash_multi(__n); 1738 insert(__il.begin(), __il.end()); 1739} 1740 1741template <class _Value, class _Hash, class _Pred, class _Alloc> 1742inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1743unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_multiset&& __u) 1744 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 1745 __table_ = std::move(__u.__table_); 1746 return *this; 1747} 1748 1749template <class _Value, class _Hash, class _Pred, class _Alloc> 1750inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1751unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 1752 __table_.__assign_multi(__il.begin(), __il.end()); 1753 return *this; 1754} 1755 1756#endif // _LIBCPP_CXX03_LANG 1757 1758template <class _Value, class _Hash, class _Pred, class _Alloc> 1759template <class _InputIterator> 1760inline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 1761 for (; __first != __last; ++__first) 1762 __table_.__insert_multi(*__first); 1763} 1764 1765template <class _Value, class _Hash, class _Pred, class _Alloc> 1766inline _LIBCPP_HIDE_FROM_ABI void 1767swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1768 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 1769 __x.swap(__y); 1770} 1771 1772#if _LIBCPP_STD_VER >= 20 1773template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> 1774inline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type 1775erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 1776 return std::__libcpp_erase_if_container(__c, __pred); 1777} 1778#endif 1779 1780template <class _Value, class _Hash, class _Pred, class _Alloc> 1781_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1782 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { 1783 if (__x.size() != __y.size()) 1784 return false; 1785 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1786 typedef pair<const_iterator, const_iterator> _EqRng; 1787 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { 1788 _EqRng __xeq = __x.equal_range(*__i); 1789 _EqRng __yeq = __y.equal_range(*__i); 1790 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || 1791 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1792 return false; 1793 __i = __xeq.second; 1794 } 1795 return true; 1796} 1797 1798#if _LIBCPP_STD_VER <= 17 1799 1800template <class _Value, class _Hash, class _Pred, class _Alloc> 1801inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1802 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { 1803 return !(__x == __y); 1804} 1805 1806#endif 1807 1808template <class _Value, class _Hash, class _Pred, class _Alloc> 1809struct __container_traits<unordered_multiset<_Value, _Hash, _Pred, _Alloc> > { 1810 // http://eel.is/c++draft/unord.req.except#2 1811 // For unordered associative containers, if an exception is thrown by any operation 1812 // other than the container's hash function from within an insert or emplace function 1813 // inserting a single element, the insertion has no effect. 1814 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = 1815 __nothrow_invokable<_Hash, const _Value&>::value; 1816}; 1817 1818_LIBCPP_END_NAMESPACE_STD 1819 1820#if _LIBCPP_STD_VER >= 17 1821_LIBCPP_BEGIN_NAMESPACE_STD 1822namespace pmr { 1823template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 1824using unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1825 1826template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 1827using unordered_multiset _LIBCPP_AVAILABILITY_PMR = 1828 std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1829} // namespace pmr 1830_LIBCPP_END_NAMESPACE_STD 1831#endif 1832 1833_LIBCPP_POP_MACROS 1834 1835#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 1836# include <cmath> 1837# include <concepts> 1838# include <cstdlib> 1839# include <functional> 1840# include <iterator> 1841# include <stdexcept> 1842# include <type_traits> 1843#endif 1844 1845#endif // _LIBCPP_UNORDERED_SET 1846