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