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> // all public C++ headers provide the assertion handler 536#include <__availability> 537#include <__config> 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_resource/polymorphic_allocator.h> 548#include <__node_handle> 549#include <__ranges/concepts.h> 550#include <__ranges/container_compatible_range.h> 551#include <__ranges/from_range.h> 552#include <__type_traits/is_allocator.h> 553#include <__utility/forward.h> 554#include <version> 555 556// standard-mandated includes 557 558// [iterator.range] 559#include <__iterator/access.h> 560#include <__iterator/data.h> 561#include <__iterator/empty.h> 562#include <__iterator/reverse_access.h> 563#include <__iterator/size.h> 564 565// [unord.set.syn] 566#include <compare> 567#include <initializer_list> 568 569#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 570# pragma GCC system_header 571#endif 572 573_LIBCPP_PUSH_MACROS 574#include <__undef_macros> 575 576_LIBCPP_BEGIN_NAMESPACE_STD 577 578template <class _Value, class _Hash, class _Pred, class _Alloc> 579class unordered_multiset; 580 581template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > 582class _LIBCPP_TEMPLATE_VIS unordered_set { 583public: 584 // types 585 typedef _Value key_type; 586 typedef key_type value_type; 587 typedef __type_identity_t<_Hash> hasher; 588 typedef __type_identity_t<_Pred> key_equal; 589 typedef __type_identity_t<_Alloc> allocator_type; 590 typedef value_type& reference; 591 typedef const value_type& const_reference; 592 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 593 "Allocator::value_type must be same type as value_type"); 594 595 static_assert(is_same<allocator_type, __rebind_alloc<allocator_traits<allocator_type>, value_type> >::value, 596 "[allocator.requirements] states that rebinding an allocator to the same type should result in the " 597 "original allocator"); 598 599private: 600 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 601 602 __table __table_; 603 604public: 605 typedef typename __table::pointer pointer; 606 typedef typename __table::const_pointer const_pointer; 607 typedef typename __table::size_type size_type; 608 typedef typename __table::difference_type difference_type; 609 610 typedef typename __table::const_iterator iterator; 611 typedef typename __table::const_iterator const_iterator; 612 typedef typename __table::const_local_iterator local_iterator; 613 typedef typename __table::const_local_iterator const_local_iterator; 614 615#if _LIBCPP_STD_VER >= 17 616 typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 617 typedef __insert_return_type<iterator, node_type> insert_return_type; 618#endif 619 620 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 621 friend class _LIBCPP_TEMPLATE_VIS unordered_set; 622 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 623 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 624 625 _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 626 explicit _LIBCPP_HIDE_FROM_ABI 627 unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 628#if _LIBCPP_STD_VER >= 14 629 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a) 630 : unordered_set(__n, hasher(), key_equal(), __a) {} 631 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 632 : unordered_set(__n, __hf, key_equal(), __a) {} 633#endif 634 _LIBCPP_HIDE_FROM_ABI 635 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 636 template <class _InputIterator> 637 _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last); 638 template <class _InputIterator> 639 _LIBCPP_HIDE_FROM_ABI 640 unordered_set(_InputIterator __first, 641 _InputIterator __last, 642 size_type __n, 643 const hasher& __hf = hasher(), 644 const key_equal& __eql = key_equal()); 645 template <class _InputIterator> 646 _LIBCPP_HIDE_FROM_ABI unordered_set( 647 _InputIterator __first, 648 _InputIterator __last, 649 size_type __n, 650 const hasher& __hf, 651 const key_equal& __eql, 652 const allocator_type& __a); 653 654#if _LIBCPP_STD_VER >= 23 655 template <_ContainerCompatibleRange<value_type> _Range> 656 _LIBCPP_HIDE_FROM_ABI unordered_set( 657 from_range_t, 658 _Range&& __range, 659 size_type __n = /*implementation-defined*/ 0, 660 const hasher& __hf = hasher(), 661 const key_equal& __eql = key_equal(), 662 const allocator_type& __a = allocator_type()) 663 : __table_(__hf, __eql, __a) { 664 if (__n > 0) { 665 __table_.__rehash_unique(__n); 666 } 667 insert_range(std::forward<_Range>(__range)); 668 } 669#endif 670 671#if _LIBCPP_STD_VER >= 14 672 template <class _InputIterator> 673 inline _LIBCPP_HIDE_FROM_ABI 674 unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 675 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 676 template <class _InputIterator> 677 _LIBCPP_HIDE_FROM_ABI unordered_set( 678 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 679 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 680#endif 681 682#if _LIBCPP_STD_VER >= 23 683 template <_ContainerCompatibleRange<value_type> _Range> 684 _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 685 : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 686 687 template <_ContainerCompatibleRange<value_type> _Range> 688 _LIBCPP_HIDE_FROM_ABI 689 unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 690 : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 691#endif 692 693 _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a); 694 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u); 695 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a); 696#ifndef _LIBCPP_CXX03_LANG 697 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 698 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a); 699 _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il); 700 _LIBCPP_HIDE_FROM_ABI 701 unordered_set(initializer_list<value_type> __il, 702 size_type __n, 703 const hasher& __hf = hasher(), 704 const key_equal& __eql = key_equal()); 705 _LIBCPP_HIDE_FROM_ABI unordered_set( 706 initializer_list<value_type> __il, 707 size_type __n, 708 const hasher& __hf, 709 const key_equal& __eql, 710 const allocator_type& __a); 711# if _LIBCPP_STD_VER >= 14 712 inline _LIBCPP_HIDE_FROM_ABI 713 unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 714 : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 715 inline _LIBCPP_HIDE_FROM_ABI 716 unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 717 : unordered_set(__il, __n, __hf, key_equal(), __a) {} 718# endif 719#endif // _LIBCPP_CXX03_LANG 720 _LIBCPP_HIDE_FROM_ABI ~unordered_set() { 721 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 722 } 723 724 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) { 725 __table_ = __u.__table_; 726 return *this; 727 } 728#ifndef _LIBCPP_CXX03_LANG 729 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u) 730 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 731 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il); 732#endif // _LIBCPP_CXX03_LANG 733 734 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 735 return allocator_type(__table_.__node_alloc()); 736 } 737 738 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 739 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 740 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 741 742 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 743 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 744 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 745 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 746 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 747 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 748 749#ifndef _LIBCPP_CXX03_LANG 750 template <class... _Args> 751 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) { 752 return __table_.__emplace_unique(std::forward<_Args>(__args)...); 753 } 754 template <class... _Args> 755 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) { 756 return __table_.__emplace_unique(std::forward<_Args>(__args)...).first; 757 } 758 759 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) { 760 return __table_.__insert_unique(std::move(__x)); 761 } 762 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; } 763 764 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 765#endif // _LIBCPP_CXX03_LANG 766 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); } 767 768 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } 769 template <class _InputIterator> 770 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 771 772#if _LIBCPP_STD_VER >= 23 773 template <_ContainerCompatibleRange<value_type> _Range> 774 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 775 for (auto&& __element : __range) { 776 __table_.__insert_unique(std::forward<decltype(__element)>(__element)); 777 } 778 } 779#endif 780 781 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); } 782 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } 783 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 784 return __table_.erase(__first, __last); 785 } 786 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 787 788#if _LIBCPP_STD_VER >= 17 789 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) { 790 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 791 "node_type with incompatible allocator passed to unordered_set::insert()"); 792 return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh)); 793 } 794 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) { 795 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 796 "node_type with incompatible allocator passed to unordered_set::insert()"); 797 return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh)); 798 } 799 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 800 return __table_.template __node_handle_extract<node_type>(__key); 801 } 802 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 803 return __table_.template __node_handle_extract<node_type>(__it); 804 } 805 806 template <class _H2, class _P2> 807 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) { 808 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 809 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 810 __table_.__node_handle_merge_unique(__source.__table_); 811 } 812 template <class _H2, class _P2> 813 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) { 814 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 815 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 816 __table_.__node_handle_merge_unique(__source.__table_); 817 } 818 template <class _H2, class _P2> 819 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) { 820 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 821 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 822 __table_.__node_handle_merge_unique(__source.__table_); 823 } 824 template <class _H2, class _P2> 825 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) { 826 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 827 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 828 __table_.__node_handle_merge_unique(__source.__table_); 829 } 830#endif 831 832 _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) { 833 __table_.swap(__u.__table_); 834 } 835 836 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); } 837 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } 838 839 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 840 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 841#if _LIBCPP_STD_VER >= 20 842 template <class _K2, 843 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 844 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 845 return __table_.find(__k); 846 } 847 template <class _K2, 848 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 849 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 850 return __table_.find(__k); 851 } 852#endif // _LIBCPP_STD_VER >= 20 853 854 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } 855#if _LIBCPP_STD_VER >= 20 856 template <class _K2, 857 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 858 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 859 return __table_.__count_unique(__k); 860 } 861#endif // _LIBCPP_STD_VER >= 20 862 863#if _LIBCPP_STD_VER >= 20 864 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 865 866 template <class _K2, 867 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 868 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 869 return find(__k) != end(); 870 } 871#endif // _LIBCPP_STD_VER >= 20 872 873 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 874 return __table_.__equal_range_unique(__k); 875 } 876 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 877 return __table_.__equal_range_unique(__k); 878 } 879#if _LIBCPP_STD_VER >= 20 880 template <class _K2, 881 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 882 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 883 return __table_.__equal_range_unique(__k); 884 } 885 template <class _K2, 886 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 887 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 888 return __table_.__equal_range_unique(__k); 889 } 890#endif // _LIBCPP_STD_VER >= 20 891 892 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 893 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 894 895 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 896 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 897 898 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 899 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 900 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 901 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 902 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 903 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 904 905 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 906 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 907 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 908 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); } 909 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); } 910}; 911 912#if _LIBCPP_STD_VER >= 17 913template <class _InputIterator, 914 class _Hash = hash<__iter_value_type<_InputIterator>>, 915 class _Pred = equal_to<__iter_value_type<_InputIterator>>, 916 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 917 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 918 class = enable_if_t<!__is_allocator<_Hash>::value>, 919 class = enable_if_t<!is_integral<_Hash>::value>, 920 class = enable_if_t<!__is_allocator<_Pred>::value>, 921 class = enable_if_t<__is_allocator<_Allocator>::value>> 922unordered_set(_InputIterator, 923 _InputIterator, 924 typename allocator_traits<_Allocator>::size_type = 0, 925 _Hash = _Hash(), 926 _Pred = _Pred(), 927 _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 928 929# if _LIBCPP_STD_VER >= 23 930template <ranges::input_range _Range, 931 class _Hash = hash<ranges::range_value_t<_Range>>, 932 class _Pred = equal_to<ranges::range_value_t<_Range>>, 933 class _Allocator = allocator<ranges::range_value_t<_Range>>, 934 class = enable_if_t<!__is_allocator<_Hash>::value>, 935 class = enable_if_t<!is_integral<_Hash>::value>, 936 class = enable_if_t<!__is_allocator<_Pred>::value>, 937 class = enable_if_t<__is_allocator<_Allocator>::value>> 938unordered_set(from_range_t, 939 _Range&&, 940 typename allocator_traits<_Allocator>::size_type = 0, 941 _Hash = _Hash(), 942 _Pred = _Pred(), 943 _Allocator = _Allocator()) 944 -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 945# endif 946 947template <class _Tp, 948 class _Hash = hash<_Tp>, 949 class _Pred = equal_to<_Tp>, 950 class _Allocator = allocator<_Tp>, 951 class = enable_if_t<!__is_allocator<_Hash>::value>, 952 class = enable_if_t<!is_integral<_Hash>::value>, 953 class = enable_if_t<!__is_allocator<_Pred>::value>, 954 class = enable_if_t<__is_allocator<_Allocator>::value>> 955unordered_set(initializer_list<_Tp>, 956 typename allocator_traits<_Allocator>::size_type = 0, 957 _Hash = _Hash(), 958 _Pred = _Pred(), 959 _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 960 961template <class _InputIterator, 962 class _Allocator, 963 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 964 class = enable_if_t<__is_allocator<_Allocator>::value>> 965unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 966 -> unordered_set<__iter_value_type<_InputIterator>, 967 hash<__iter_value_type<_InputIterator>>, 968 equal_to<__iter_value_type<_InputIterator>>, 969 _Allocator>; 970 971template <class _InputIterator, 972 class _Hash, 973 class _Allocator, 974 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 975 class = enable_if_t<!__is_allocator<_Hash>::value>, 976 class = enable_if_t<!is_integral<_Hash>::value>, 977 class = enable_if_t<__is_allocator<_Allocator>::value>> 978unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 979 -> unordered_set<__iter_value_type<_InputIterator>, _Hash, equal_to<__iter_value_type<_InputIterator>>, _Allocator>; 980 981# if _LIBCPP_STD_VER >= 23 982 983template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 984unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 985 -> unordered_set<ranges::range_value_t<_Range>, 986 hash<ranges::range_value_t<_Range>>, 987 equal_to<ranges::range_value_t<_Range>>, 988 _Allocator>; 989 990template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 991unordered_set(from_range_t, _Range&&, _Allocator) 992 -> unordered_set<ranges::range_value_t<_Range>, 993 hash<ranges::range_value_t<_Range>>, 994 equal_to<ranges::range_value_t<_Range>>, 995 _Allocator>; 996 997template <ranges::input_range _Range, 998 class _Hash, 999 class _Allocator, 1000 class = enable_if_t<!__is_allocator<_Hash>::value>, 1001 class = enable_if_t<!is_integral<_Hash>::value>, 1002 class = enable_if_t<__is_allocator<_Allocator>::value>> 1003unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1004 -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 1005 1006# endif 1007 1008template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1009unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 1010 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 1011 1012template <class _Tp, 1013 class _Hash, 1014 class _Allocator, 1015 class = enable_if_t<!__is_allocator<_Hash>::value>, 1016 class = enable_if_t<!is_integral<_Hash>::value>, 1017 class = enable_if_t<__is_allocator<_Allocator>::value>> 1018unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1019 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 1020#endif 1021 1022template <class _Value, class _Hash, class _Pred, class _Alloc> 1023unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql) 1024 : __table_(__hf, __eql) { 1025 __table_.__rehash_unique(__n); 1026} 1027 1028template <class _Value, class _Hash, class _Pred, class _Alloc> 1029unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1030 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1031 : __table_(__hf, __eql, __a) { 1032 __table_.__rehash_unique(__n); 1033} 1034 1035template <class _Value, class _Hash, class _Pred, class _Alloc> 1036template <class _InputIterator> 1037unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) { 1038 insert(__first, __last); 1039} 1040 1041template <class _Value, class _Hash, class _Pred, class _Alloc> 1042template <class _InputIterator> 1043unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1044 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1045 : __table_(__hf, __eql) { 1046 __table_.__rehash_unique(__n); 1047 insert(__first, __last); 1048} 1049 1050template <class _Value, class _Hash, class _Pred, class _Alloc> 1051template <class _InputIterator> 1052unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1053 _InputIterator __first, 1054 _InputIterator __last, 1055 size_type __n, 1056 const hasher& __hf, 1057 const key_equal& __eql, 1058 const allocator_type& __a) 1059 : __table_(__hf, __eql, __a) { 1060 __table_.__rehash_unique(__n); 1061 insert(__first, __last); 1062} 1063 1064template <class _Value, class _Hash, class _Pred, class _Alloc> 1065inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {} 1066 1067template <class _Value, class _Hash, class _Pred, class _Alloc> 1068unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) { 1069 __table_.__rehash_unique(__u.bucket_count()); 1070 insert(__u.begin(), __u.end()); 1071} 1072 1073template <class _Value, class _Hash, class _Pred, class _Alloc> 1074unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a) 1075 : __table_(__u.__table_, __a) { 1076 __table_.__rehash_unique(__u.bucket_count()); 1077 insert(__u.begin(), __u.end()); 1078} 1079 1080#ifndef _LIBCPP_CXX03_LANG 1081 1082template <class _Value, class _Hash, class _Pred, class _Alloc> 1083inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u) 1084 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1085 : __table_(std::move(__u.__table_)) {} 1086 1087template <class _Value, class _Hash, class _Pred, class _Alloc> 1088unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u, const allocator_type& __a) 1089 : __table_(std::move(__u.__table_), __a) { 1090 if (__a != __u.get_allocator()) { 1091 iterator __i = __u.begin(); 1092 while (__u.size() != 0) 1093 __table_.__insert_unique(std::move(__u.__table_.remove(__i++)->__get_value())); 1094 } 1095} 1096 1097template <class _Value, class _Hash, class _Pred, class _Alloc> 1098unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(initializer_list<value_type> __il) { 1099 insert(__il.begin(), __il.end()); 1100} 1101 1102template <class _Value, class _Hash, class _Pred, class _Alloc> 1103unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1104 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1105 : __table_(__hf, __eql) { 1106 __table_.__rehash_unique(__n); 1107 insert(__il.begin(), __il.end()); 1108} 1109 1110template <class _Value, class _Hash, class _Pred, class _Alloc> 1111unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1112 initializer_list<value_type> __il, 1113 size_type __n, 1114 const hasher& __hf, 1115 const key_equal& __eql, 1116 const allocator_type& __a) 1117 : __table_(__hf, __eql, __a) { 1118 __table_.__rehash_unique(__n); 1119 insert(__il.begin(), __il.end()); 1120} 1121 1122template <class _Value, class _Hash, class _Pred, class _Alloc> 1123inline unordered_set<_Value, _Hash, _Pred, _Alloc>& 1124unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 1125 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 1126 __table_ = std::move(__u.__table_); 1127 return *this; 1128} 1129 1130template <class _Value, class _Hash, class _Pred, class _Alloc> 1131inline unordered_set<_Value, _Hash, _Pred, _Alloc>& 1132unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 1133 __table_.__assign_unique(__il.begin(), __il.end()); 1134 return *this; 1135} 1136 1137#endif // _LIBCPP_CXX03_LANG 1138 1139template <class _Value, class _Hash, class _Pred, class _Alloc> 1140template <class _InputIterator> 1141inline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 1142 for (; __first != __last; ++__first) 1143 __table_.__insert_unique(*__first); 1144} 1145 1146template <class _Value, class _Hash, class _Pred, class _Alloc> 1147inline _LIBCPP_HIDE_FROM_ABI void 1148swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1149 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 1150 __x.swap(__y); 1151} 1152 1153#if _LIBCPP_STD_VER >= 20 1154template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> 1155inline _LIBCPP_HIDE_FROM_ABI typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type 1156erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 1157 return std::__libcpp_erase_if_container(__c, __pred); 1158} 1159#endif 1160 1161template <class _Value, class _Hash, class _Pred, class _Alloc> 1162_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1163 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) { 1164 if (__x.size() != __y.size()) 1165 return false; 1166 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1167 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { 1168 const_iterator __j = __y.find(*__i); 1169 if (__j == __ey || !(*__i == *__j)) 1170 return false; 1171 } 1172 return true; 1173} 1174 1175#if _LIBCPP_STD_VER <= 17 1176 1177template <class _Value, class _Hash, class _Pred, class _Alloc> 1178inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1179 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) { 1180 return !(__x == __y); 1181} 1182 1183#endif 1184 1185template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > 1186class _LIBCPP_TEMPLATE_VIS unordered_multiset { 1187public: 1188 // types 1189 typedef _Value key_type; 1190 typedef key_type value_type; 1191 typedef __type_identity_t<_Hash> hasher; 1192 typedef __type_identity_t<_Pred> key_equal; 1193 typedef __type_identity_t<_Alloc> allocator_type; 1194 typedef value_type& reference; 1195 typedef const value_type& const_reference; 1196 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1197 "Allocator::value_type must be same type as value_type"); 1198 1199private: 1200 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 1201 1202 __table __table_; 1203 1204public: 1205 typedef typename __table::pointer pointer; 1206 typedef typename __table::const_pointer const_pointer; 1207 typedef typename __table::size_type size_type; 1208 typedef typename __table::difference_type difference_type; 1209 1210 typedef typename __table::const_iterator iterator; 1211 typedef typename __table::const_iterator const_iterator; 1212 typedef typename __table::const_local_iterator local_iterator; 1213 typedef typename __table::const_local_iterator const_local_iterator; 1214 1215#if _LIBCPP_STD_VER >= 17 1216 typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 1217#endif 1218 1219 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 1220 friend class _LIBCPP_TEMPLATE_VIS unordered_set; 1221 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 1222 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 1223 1224 _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 1225 explicit _LIBCPP_HIDE_FROM_ABI 1226 unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 1227 _LIBCPP_HIDE_FROM_ABI 1228 unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 1229#if _LIBCPP_STD_VER >= 14 1230 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a) 1231 : unordered_multiset(__n, hasher(), key_equal(), __a) {} 1232 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 1233 : unordered_multiset(__n, __hf, key_equal(), __a) {} 1234#endif 1235 template <class _InputIterator> 1236 _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last); 1237 template <class _InputIterator> 1238 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1239 _InputIterator __first, 1240 _InputIterator __last, 1241 size_type __n, 1242 const hasher& __hf = hasher(), 1243 const key_equal& __eql = key_equal()); 1244 template <class _InputIterator> 1245 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1246 _InputIterator __first, 1247 _InputIterator __last, 1248 size_type __n, 1249 const hasher& __hf, 1250 const key_equal& __eql, 1251 const allocator_type& __a); 1252 1253#if _LIBCPP_STD_VER >= 23 1254 template <_ContainerCompatibleRange<value_type> _Range> 1255 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1256 from_range_t, 1257 _Range&& __range, 1258 size_type __n = /*implementation-defined*/ 0, 1259 const hasher& __hf = hasher(), 1260 const key_equal& __eql = key_equal(), 1261 const allocator_type& __a = allocator_type()) 1262 : __table_(__hf, __eql, __a) { 1263 if (__n > 0) { 1264 __table_.__rehash_multi(__n); 1265 } 1266 insert_range(std::forward<_Range>(__range)); 1267 } 1268#endif 1269 1270#if _LIBCPP_STD_VER >= 14 1271 template <class _InputIterator> 1272 inline _LIBCPP_HIDE_FROM_ABI 1273 unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1274 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 1275 template <class _InputIterator> 1276 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1277 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 1278 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 1279#endif 1280 1281#if _LIBCPP_STD_VER >= 23 1282 template <_ContainerCompatibleRange<value_type> _Range> 1283 _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 1284 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 1285 1286 template <_ContainerCompatibleRange<value_type> _Range> 1287 _LIBCPP_HIDE_FROM_ABI 1288 unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 1289 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 1290#endif 1291 1292 _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a); 1293 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u); 1294 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 1295#ifndef _LIBCPP_CXX03_LANG 1296 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u) 1297 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1298 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 1299 _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il); 1300 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1301 initializer_list<value_type> __il, 1302 size_type __n, 1303 const hasher& __hf = hasher(), 1304 const key_equal& __eql = key_equal()); 1305 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1306 initializer_list<value_type> __il, 1307 size_type __n, 1308 const hasher& __hf, 1309 const key_equal& __eql, 1310 const allocator_type& __a); 1311# if _LIBCPP_STD_VER >= 14 1312 inline _LIBCPP_HIDE_FROM_ABI 1313 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1314 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 1315 inline _LIBCPP_HIDE_FROM_ABI 1316 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 1317 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 1318# endif 1319#endif // _LIBCPP_CXX03_LANG 1320 _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() { 1321 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 1322 } 1323 1324 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) { 1325 __table_ = __u.__table_; 1326 return *this; 1327 } 1328#ifndef _LIBCPP_CXX03_LANG 1329 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u) 1330 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1331 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il); 1332#endif // _LIBCPP_CXX03_LANG 1333 1334 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 1335 return allocator_type(__table_.__node_alloc()); 1336 } 1337 1338 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 1339 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 1340 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 1341 1342 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 1343 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 1344 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 1345 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 1346 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 1347 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 1348 1349#ifndef _LIBCPP_CXX03_LANG 1350 template <class... _Args> 1351 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { 1352 return __table_.__emplace_multi(std::forward<_Args>(__args)...); 1353 } 1354 template <class... _Args> 1355 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1356 return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...); 1357 } 1358 1359 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); } 1360 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) { 1361 return __table_.__insert_multi(__p, std::move(__x)); 1362 } 1363 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 1364#endif // _LIBCPP_CXX03_LANG 1365 1366 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); } 1367 1368 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) { 1369 return __table_.__insert_multi(__p, __x); 1370 } 1371 1372 template <class _InputIterator> 1373 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 1374 1375#if _LIBCPP_STD_VER >= 23 1376 template <_ContainerCompatibleRange<value_type> _Range> 1377 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 1378 for (auto&& __element : __range) { 1379 __table_.__insert_multi(std::forward<decltype(__element)>(__element)); 1380 } 1381 } 1382#endif 1383 1384#if _LIBCPP_STD_VER >= 17 1385 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) { 1386 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1387 "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1388 return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh)); 1389 } 1390 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 1391 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1392 "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1393 return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh)); 1394 } 1395 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) { 1396 return __table_.template __node_handle_extract<node_type>(__position); 1397 } 1398 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 1399 return __table_.template __node_handle_extract<node_type>(__key); 1400 } 1401 1402 template <class _H2, class _P2> 1403 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) { 1404 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1405 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1406 return __table_.__node_handle_merge_multi(__source.__table_); 1407 } 1408 template <class _H2, class _P2> 1409 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) { 1410 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1411 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1412 return __table_.__node_handle_merge_multi(__source.__table_); 1413 } 1414 template <class _H2, class _P2> 1415 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) { 1416 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1417 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1418 return __table_.__node_handle_merge_multi(__source.__table_); 1419 } 1420 template <class _H2, class _P2> 1421 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) { 1422 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1423 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1424 return __table_.__node_handle_merge_multi(__source.__table_); 1425 } 1426#endif 1427 1428 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); } 1429 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } 1430 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 1431 return __table_.erase(__first, __last); 1432 } 1433 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 1434 1435 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) { 1436 __table_.swap(__u.__table_); 1437 } 1438 1439 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); } 1440 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } 1441 1442 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 1443 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 1444#if _LIBCPP_STD_VER >= 20 1445 template <class _K2, 1446 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1447 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 1448 return __table_.find(__k); 1449 } 1450 template <class _K2, 1451 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1452 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 1453 return __table_.find(__k); 1454 } 1455#endif // _LIBCPP_STD_VER >= 20 1456 1457 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } 1458#if _LIBCPP_STD_VER >= 20 1459 template <class _K2, 1460 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1461 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 1462 return __table_.__count_multi(__k); 1463 } 1464#endif // _LIBCPP_STD_VER >= 20 1465 1466#if _LIBCPP_STD_VER >= 20 1467 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 1468 1469 template <class _K2, 1470 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1471 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 1472 return find(__k) != end(); 1473 } 1474#endif // _LIBCPP_STD_VER >= 20 1475 1476 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1477 return __table_.__equal_range_multi(__k); 1478 } 1479 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1480 return __table_.__equal_range_multi(__k); 1481 } 1482#if _LIBCPP_STD_VER >= 20 1483 template <class _K2, 1484 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1485 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 1486 return __table_.__equal_range_multi(__k); 1487 } 1488 template <class _K2, 1489 enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1490 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 1491 return __table_.__equal_range_multi(__k); 1492 } 1493#endif // _LIBCPP_STD_VER >= 20 1494 1495 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 1496 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 1497 1498 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 1499 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 1500 1501 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 1502 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 1503 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 1504 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 1505 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 1506 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 1507 1508 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 1509 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 1510 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 1511 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); } 1512 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); } 1513}; 1514 1515#if _LIBCPP_STD_VER >= 17 1516template <class _InputIterator, 1517 class _Hash = hash<__iter_value_type<_InputIterator>>, 1518 class _Pred = equal_to<__iter_value_type<_InputIterator>>, 1519 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 1520 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1521 class = enable_if_t<!__is_allocator<_Hash>::value>, 1522 class = enable_if_t<!is_integral<_Hash>::value>, 1523 class = enable_if_t<!__is_allocator<_Pred>::value>, 1524 class = enable_if_t<__is_allocator<_Allocator>::value>> 1525unordered_multiset( 1526 _InputIterator, 1527 _InputIterator, 1528 typename allocator_traits<_Allocator>::size_type = 0, 1529 _Hash = _Hash(), 1530 _Pred = _Pred(), 1531 _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 1532 1533# if _LIBCPP_STD_VER >= 23 1534template <ranges::input_range _Range, 1535 class _Hash = hash<ranges::range_value_t<_Range>>, 1536 class _Pred = equal_to<ranges::range_value_t<_Range>>, 1537 class _Allocator = allocator<ranges::range_value_t<_Range>>, 1538 class = enable_if_t<!__is_allocator<_Hash>::value>, 1539 class = enable_if_t<!is_integral<_Hash>::value>, 1540 class = enable_if_t<!__is_allocator<_Pred>::value>, 1541 class = enable_if_t<__is_allocator<_Allocator>::value>> 1542unordered_multiset( 1543 from_range_t, 1544 _Range&&, 1545 typename allocator_traits<_Allocator>::size_type = 0, 1546 _Hash = _Hash(), 1547 _Pred = _Pred(), 1548 _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 1549# endif 1550 1551template <class _Tp, 1552 class _Hash = hash<_Tp>, 1553 class _Pred = equal_to<_Tp>, 1554 class _Allocator = allocator<_Tp>, 1555 class = enable_if_t<!__is_allocator<_Hash>::value>, 1556 class = enable_if_t<!is_integral<_Hash>::value>, 1557 class = enable_if_t<!__is_allocator<_Pred>::value>, 1558 class = enable_if_t<__is_allocator<_Allocator>::value>> 1559unordered_multiset(initializer_list<_Tp>, 1560 typename allocator_traits<_Allocator>::size_type = 0, 1561 _Hash = _Hash(), 1562 _Pred = _Pred(), 1563 _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 1564 1565template <class _InputIterator, 1566 class _Allocator, 1567 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1568 class = enable_if_t<__is_allocator<_Allocator>::value>> 1569unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 1570 -> unordered_multiset<__iter_value_type<_InputIterator>, 1571 hash<__iter_value_type<_InputIterator>>, 1572 equal_to<__iter_value_type<_InputIterator>>, 1573 _Allocator>; 1574 1575template <class _InputIterator, 1576 class _Hash, 1577 class _Allocator, 1578 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1579 class = enable_if_t<!__is_allocator<_Hash>::value>, 1580 class = enable_if_t<!is_integral<_Hash>::value>, 1581 class = enable_if_t<__is_allocator<_Allocator>::value>> 1582unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1583 -> unordered_multiset<__iter_value_type<_InputIterator>, 1584 _Hash, 1585 equal_to<__iter_value_type<_InputIterator>>, 1586 _Allocator>; 1587 1588# if _LIBCPP_STD_VER >= 23 1589 1590template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1591unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 1592 -> unordered_multiset<ranges::range_value_t<_Range>, 1593 hash<ranges::range_value_t<_Range>>, 1594 equal_to<ranges::range_value_t<_Range>>, 1595 _Allocator>; 1596 1597template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1598unordered_multiset(from_range_t, _Range&&, _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, 1605 class _Hash, 1606 class _Allocator, 1607 class = enable_if_t<!__is_allocator<_Hash>::value>, 1608 class = enable_if_t<!is_integral<_Hash>::value>, 1609 class = enable_if_t<__is_allocator<_Allocator>::value>> 1610unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1611 -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 1612 1613# endif 1614 1615template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1616unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 1617 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 1618 1619template <class _Tp, 1620 class _Hash, 1621 class _Allocator, 1622 class = enable_if_t<!__is_allocator<_Hash>::value>, 1623 class = enable_if_t<!is_integral<_Hash>::value>, 1624 class = enable_if_t<__is_allocator<_Allocator>::value>> 1625unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1626 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 1627#endif 1628 1629template <class _Value, class _Hash, class _Pred, class _Alloc> 1630unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1631 size_type __n, const hasher& __hf, const key_equal& __eql) 1632 : __table_(__hf, __eql) { 1633 __table_.__rehash_multi(__n); 1634} 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, const allocator_type& __a) 1639 : __table_(__hf, __eql, __a) { 1640 __table_.__rehash_multi(__n); 1641} 1642 1643template <class _Value, class _Hash, class _Pred, class _Alloc> 1644template <class _InputIterator> 1645unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) { 1646 insert(__first, __last); 1647} 1648 1649template <class _Value, class _Hash, class _Pred, class _Alloc> 1650template <class _InputIterator> 1651unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1652 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1653 : __table_(__hf, __eql) { 1654 __table_.__rehash_multi(__n); 1655 insert(__first, __last); 1656} 1657 1658template <class _Value, class _Hash, class _Pred, class _Alloc> 1659template <class _InputIterator> 1660unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1661 _InputIterator __first, 1662 _InputIterator __last, 1663 size_type __n, 1664 const hasher& __hf, 1665 const key_equal& __eql, 1666 const allocator_type& __a) 1667 : __table_(__hf, __eql, __a) { 1668 __table_.__rehash_multi(__n); 1669 insert(__first, __last); 1670} 1671 1672template <class _Value, class _Hash, class _Pred, class _Alloc> 1673inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a) 1674 : __table_(__a) {} 1675 1676template <class _Value, class _Hash, class _Pred, class _Alloc> 1677unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u) 1678 : __table_(__u.__table_) { 1679 __table_.__rehash_multi(__u.bucket_count()); 1680 insert(__u.begin(), __u.end()); 1681} 1682 1683template <class _Value, class _Hash, class _Pred, class _Alloc> 1684unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1685 const unordered_multiset& __u, const allocator_type& __a) 1686 : __table_(__u.__table_, __a) { 1687 __table_.__rehash_multi(__u.bucket_count()); 1688 insert(__u.begin(), __u.end()); 1689} 1690 1691#ifndef _LIBCPP_CXX03_LANG 1692 1693template <class _Value, class _Hash, class _Pred, class _Alloc> 1694inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(unordered_multiset&& __u) 1695 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1696 : __table_(std::move(__u.__table_)) {} 1697 1698template <class _Value, class _Hash, class _Pred, class _Alloc> 1699unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1700 unordered_multiset&& __u, const allocator_type& __a) 1701 : __table_(std::move(__u.__table_), __a) { 1702 if (__a != __u.get_allocator()) { 1703 iterator __i = __u.begin(); 1704 while (__u.size() != 0) 1705 __table_.__insert_multi(std::move(__u.__table_.remove(__i++)->__get_value())); 1706 } 1707} 1708 1709template <class _Value, class _Hash, class _Pred, class _Alloc> 1710unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) { 1711 insert(__il.begin(), __il.end()); 1712} 1713 1714template <class _Value, class _Hash, class _Pred, class _Alloc> 1715unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1716 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1717 : __table_(__hf, __eql) { 1718 __table_.__rehash_multi(__n); 1719 insert(__il.begin(), __il.end()); 1720} 1721 1722template <class _Value, class _Hash, class _Pred, class _Alloc> 1723unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1724 initializer_list<value_type> __il, 1725 size_type __n, 1726 const hasher& __hf, 1727 const key_equal& __eql, 1728 const allocator_type& __a) 1729 : __table_(__hf, __eql, __a) { 1730 __table_.__rehash_multi(__n); 1731 insert(__il.begin(), __il.end()); 1732} 1733 1734template <class _Value, class _Hash, class _Pred, class _Alloc> 1735inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1736unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_multiset&& __u) 1737 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 1738 __table_ = std::move(__u.__table_); 1739 return *this; 1740} 1741 1742template <class _Value, class _Hash, class _Pred, class _Alloc> 1743inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1744unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 1745 __table_.__assign_multi(__il.begin(), __il.end()); 1746 return *this; 1747} 1748 1749#endif // _LIBCPP_CXX03_LANG 1750 1751template <class _Value, class _Hash, class _Pred, class _Alloc> 1752template <class _InputIterator> 1753inline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 1754 for (; __first != __last; ++__first) 1755 __table_.__insert_multi(*__first); 1756} 1757 1758template <class _Value, class _Hash, class _Pred, class _Alloc> 1759inline _LIBCPP_HIDE_FROM_ABI void 1760swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1761 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 1762 __x.swap(__y); 1763} 1764 1765#if _LIBCPP_STD_VER >= 20 1766template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> 1767inline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type 1768erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 1769 return std::__libcpp_erase_if_container(__c, __pred); 1770} 1771#endif 1772 1773template <class _Value, class _Hash, class _Pred, class _Alloc> 1774_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1775 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { 1776 if (__x.size() != __y.size()) 1777 return false; 1778 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1779 typedef pair<const_iterator, const_iterator> _EqRng; 1780 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { 1781 _EqRng __xeq = __x.equal_range(*__i); 1782 _EqRng __yeq = __y.equal_range(*__i); 1783 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || 1784 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1785 return false; 1786 __i = __xeq.second; 1787 } 1788 return true; 1789} 1790 1791#if _LIBCPP_STD_VER <= 17 1792 1793template <class _Value, class _Hash, class _Pred, class _Alloc> 1794inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1795 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { 1796 return !(__x == __y); 1797} 1798 1799#endif 1800 1801_LIBCPP_END_NAMESPACE_STD 1802 1803#if _LIBCPP_STD_VER >= 17 1804_LIBCPP_BEGIN_NAMESPACE_STD 1805namespace pmr { 1806template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 1807using unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1808 1809template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 1810using unordered_multiset _LIBCPP_AVAILABILITY_PMR = 1811 std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1812} // namespace pmr 1813_LIBCPP_END_NAMESPACE_STD 1814#endif 1815 1816_LIBCPP_POP_MACROS 1817 1818#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 1819# include <concepts> 1820# include <cstdlib> 1821# include <functional> 1822# include <iterator> 1823# include <stdexcept> 1824# include <type_traits> 1825#endif 1826 1827#endif // _LIBCPP_UNORDERED_SET 1828