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