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 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 unordered_set; 634 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 635 friend class 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_.__emplace_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_.__emplace_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_.__emplace_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_.__emplace_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_.__emplace_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 static _LIBCPP_CONSTEXPR const bool __reservable = true; 1201}; 1202 1203template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > 1204class unordered_multiset { 1205public: 1206 // types 1207 typedef _Value key_type; 1208 typedef key_type value_type; 1209 typedef __type_identity_t<_Hash> hasher; 1210 typedef __type_identity_t<_Pred> key_equal; 1211 typedef __type_identity_t<_Alloc> allocator_type; 1212 typedef value_type& reference; 1213 typedef const value_type& const_reference; 1214 static_assert(is_same<value_type, typename allocator_type::value_type>::value, 1215 "Allocator::value_type must be same type as value_type"); 1216 1217private: 1218 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 1219 1220 __table __table_; 1221 1222public: 1223 typedef typename __table::pointer pointer; 1224 typedef typename __table::const_pointer const_pointer; 1225 typedef typename __table::size_type size_type; 1226 typedef typename __table::difference_type difference_type; 1227 1228 typedef typename __table::const_iterator iterator; 1229 typedef typename __table::const_iterator const_iterator; 1230 typedef typename __table::const_local_iterator local_iterator; 1231 typedef typename __table::const_local_iterator const_local_iterator; 1232 1233# if _LIBCPP_STD_VER >= 17 1234 typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 1235# endif 1236 1237 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 1238 friend class unordered_set; 1239 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 1240 friend class unordered_multiset; 1241 1242 _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 1243 explicit _LIBCPP_HIDE_FROM_ABI 1244 unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 1245 _LIBCPP_HIDE_FROM_ABI 1246 unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 1247# if _LIBCPP_STD_VER >= 14 1248 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a) 1249 : unordered_multiset(__n, hasher(), key_equal(), __a) {} 1250 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 1251 : unordered_multiset(__n, __hf, key_equal(), __a) {} 1252# endif 1253 template <class _InputIterator> 1254 _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last); 1255 template <class _InputIterator> 1256 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1257 _InputIterator __first, 1258 _InputIterator __last, 1259 size_type __n, 1260 const hasher& __hf = hasher(), 1261 const key_equal& __eql = key_equal()); 1262 template <class _InputIterator> 1263 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1264 _InputIterator __first, 1265 _InputIterator __last, 1266 size_type __n, 1267 const hasher& __hf, 1268 const key_equal& __eql, 1269 const allocator_type& __a); 1270 1271# if _LIBCPP_STD_VER >= 23 1272 template <_ContainerCompatibleRange<value_type> _Range> 1273 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1274 from_range_t, 1275 _Range&& __range, 1276 size_type __n = /*implementation-defined*/ 0, 1277 const hasher& __hf = hasher(), 1278 const key_equal& __eql = key_equal(), 1279 const allocator_type& __a = allocator_type()) 1280 : __table_(__hf, __eql, __a) { 1281 if (__n > 0) { 1282 __table_.__rehash_multi(__n); 1283 } 1284 insert_range(std::forward<_Range>(__range)); 1285 } 1286# endif 1287 1288# if _LIBCPP_STD_VER >= 14 1289 template <class _InputIterator> 1290 inline _LIBCPP_HIDE_FROM_ABI 1291 unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1292 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 1293 template <class _InputIterator> 1294 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1295 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 1296 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 1297# endif 1298 1299# if _LIBCPP_STD_VER >= 23 1300 template <_ContainerCompatibleRange<value_type> _Range> 1301 _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 1302 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 1303 1304 template <_ContainerCompatibleRange<value_type> _Range> 1305 _LIBCPP_HIDE_FROM_ABI 1306 unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 1307 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 1308# endif 1309 1310 _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a); 1311 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u); 1312 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 1313# ifndef _LIBCPP_CXX03_LANG 1314 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u) 1315 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1316 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 1317 _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il); 1318 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1319 initializer_list<value_type> __il, 1320 size_type __n, 1321 const hasher& __hf = hasher(), 1322 const key_equal& __eql = key_equal()); 1323 _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1324 initializer_list<value_type> __il, 1325 size_type __n, 1326 const hasher& __hf, 1327 const key_equal& __eql, 1328 const allocator_type& __a); 1329# if _LIBCPP_STD_VER >= 14 1330 inline _LIBCPP_HIDE_FROM_ABI 1331 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1332 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 1333 inline _LIBCPP_HIDE_FROM_ABI 1334 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 1335 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 1336# endif 1337# endif // _LIBCPP_CXX03_LANG 1338 _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() { 1339 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 1340 } 1341 1342 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) { 1343 __table_ = __u.__table_; 1344 return *this; 1345 } 1346# ifndef _LIBCPP_CXX03_LANG 1347 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u) 1348 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1349 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il); 1350# endif // _LIBCPP_CXX03_LANG 1351 1352 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 1353 return allocator_type(__table_.__node_alloc()); 1354 } 1355 1356 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 1357 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 1358 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 1359 1360 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 1361 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 1362 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 1363 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 1364 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 1365 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 1366 1367# ifndef _LIBCPP_CXX03_LANG 1368 template <class... _Args> 1369 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { 1370 return __table_.__emplace_multi(std::forward<_Args>(__args)...); 1371 } 1372 template <class... _Args> 1373 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1374 return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...); 1375 } 1376 1377 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__emplace_multi(std::move(__x)); } 1378 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) { 1379 return __table_.__emplace_hint_multi(__p, std::move(__x)); 1380 } 1381 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 1382# endif // _LIBCPP_CXX03_LANG 1383 1384 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__emplace_multi(__x); } 1385 1386 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) { 1387 return __table_.__emplace_hint_multi(__p, __x); 1388 } 1389 1390 template <class _InputIterator> 1391 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 1392 1393# if _LIBCPP_STD_VER >= 23 1394 template <_ContainerCompatibleRange<value_type> _Range> 1395 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 1396 for (auto&& __element : __range) { 1397 __table_.__emplace_multi(std::forward<decltype(__element)>(__element)); 1398 } 1399 } 1400# endif 1401 1402# if _LIBCPP_STD_VER >= 17 1403 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) { 1404 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1405 "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1406 return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh)); 1407 } 1408 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 1409 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 1410 "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1411 return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh)); 1412 } 1413 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) { 1414 return __table_.template __node_handle_extract<node_type>(__position); 1415 } 1416 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 1417 return __table_.template __node_handle_extract<node_type>(__key); 1418 } 1419 1420 template <class _H2, class _P2> 1421 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) { 1422 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1423 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1424 return __table_.__node_handle_merge_multi(__source.__table_); 1425 } 1426 template <class _H2, class _P2> 1427 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) { 1428 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1429 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1430 return __table_.__node_handle_merge_multi(__source.__table_); 1431 } 1432 template <class _H2, class _P2> 1433 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) { 1434 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1435 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1436 return __table_.__node_handle_merge_multi(__source.__table_); 1437 } 1438 template <class _H2, class _P2> 1439 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) { 1440 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1441 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 1442 return __table_.__node_handle_merge_multi(__source.__table_); 1443 } 1444# endif 1445 1446 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); } 1447 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } 1448 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 1449 return __table_.erase(__first, __last); 1450 } 1451 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 1452 1453 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) { 1454 __table_.swap(__u.__table_); 1455 } 1456 1457 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); } 1458 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } 1459 1460 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 1461 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 1462# if _LIBCPP_STD_VER >= 20 1463 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1464 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 1465 return __table_.find(__k); 1466 } 1467 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1468 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 1469 return __table_.find(__k); 1470 } 1471# endif // _LIBCPP_STD_VER >= 20 1472 1473 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } 1474# if _LIBCPP_STD_VER >= 20 1475 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1476 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 1477 return __table_.__count_multi(__k); 1478 } 1479# endif // _LIBCPP_STD_VER >= 20 1480 1481# if _LIBCPP_STD_VER >= 20 1482 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 1483 1484 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1485 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 1486 return find(__k) != end(); 1487 } 1488# endif // _LIBCPP_STD_VER >= 20 1489 1490 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1491 return __table_.__equal_range_multi(__k); 1492 } 1493 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1494 return __table_.__equal_range_multi(__k); 1495 } 1496# if _LIBCPP_STD_VER >= 20 1497 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1498 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 1499 return __table_.__equal_range_multi(__k); 1500 } 1501 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr> 1502 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 1503 return __table_.__equal_range_multi(__k); 1504 } 1505# endif // _LIBCPP_STD_VER >= 20 1506 1507 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 1508 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 1509 1510 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 1511 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 1512 1513 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 1514 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 1515 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 1516 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 1517 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 1518 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 1519 1520 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 1521 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 1522 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 1523 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); } 1524 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); } 1525}; 1526 1527# if _LIBCPP_STD_VER >= 17 1528template <class _InputIterator, 1529 class _Hash = hash<__iter_value_type<_InputIterator>>, 1530 class _Pred = equal_to<__iter_value_type<_InputIterator>>, 1531 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 1532 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1533 class = enable_if_t<!__is_allocator<_Hash>::value>, 1534 class = enable_if_t<!is_integral<_Hash>::value>, 1535 class = enable_if_t<!__is_allocator<_Pred>::value>, 1536 class = enable_if_t<__is_allocator<_Allocator>::value>> 1537unordered_multiset( 1538 _InputIterator, 1539 _InputIterator, 1540 typename allocator_traits<_Allocator>::size_type = 0, 1541 _Hash = _Hash(), 1542 _Pred = _Pred(), 1543 _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 1544 1545# if _LIBCPP_STD_VER >= 23 1546template <ranges::input_range _Range, 1547 class _Hash = hash<ranges::range_value_t<_Range>>, 1548 class _Pred = equal_to<ranges::range_value_t<_Range>>, 1549 class _Allocator = allocator<ranges::range_value_t<_Range>>, 1550 class = enable_if_t<!__is_allocator<_Hash>::value>, 1551 class = enable_if_t<!is_integral<_Hash>::value>, 1552 class = enable_if_t<!__is_allocator<_Pred>::value>, 1553 class = enable_if_t<__is_allocator<_Allocator>::value>> 1554unordered_multiset( 1555 from_range_t, 1556 _Range&&, 1557 typename allocator_traits<_Allocator>::size_type = 0, 1558 _Hash = _Hash(), 1559 _Pred = _Pred(), 1560 _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 1561# endif 1562 1563template <class _Tp, 1564 class _Hash = hash<_Tp>, 1565 class _Pred = equal_to<_Tp>, 1566 class _Allocator = allocator<_Tp>, 1567 class = enable_if_t<!__is_allocator<_Hash>::value>, 1568 class = enable_if_t<!is_integral<_Hash>::value>, 1569 class = enable_if_t<!__is_allocator<_Pred>::value>, 1570 class = enable_if_t<__is_allocator<_Allocator>::value>> 1571unordered_multiset(initializer_list<_Tp>, 1572 typename allocator_traits<_Allocator>::size_type = 0, 1573 _Hash = _Hash(), 1574 _Pred = _Pred(), 1575 _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 1576 1577template <class _InputIterator, 1578 class _Allocator, 1579 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1580 class = enable_if_t<__is_allocator<_Allocator>::value>> 1581unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 1582 -> unordered_multiset<__iter_value_type<_InputIterator>, 1583 hash<__iter_value_type<_InputIterator>>, 1584 equal_to<__iter_value_type<_InputIterator>>, 1585 _Allocator>; 1586 1587template <class _InputIterator, 1588 class _Hash, 1589 class _Allocator, 1590 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1591 class = enable_if_t<!__is_allocator<_Hash>::value>, 1592 class = enable_if_t<!is_integral<_Hash>::value>, 1593 class = enable_if_t<__is_allocator<_Allocator>::value>> 1594unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1595 -> unordered_multiset<__iter_value_type<_InputIterator>, 1596 _Hash, 1597 equal_to<__iter_value_type<_InputIterator>>, 1598 _Allocator>; 1599 1600# if _LIBCPP_STD_VER >= 23 1601 1602template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1603unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 1604 -> unordered_multiset<ranges::range_value_t<_Range>, 1605 hash<ranges::range_value_t<_Range>>, 1606 equal_to<ranges::range_value_t<_Range>>, 1607 _Allocator>; 1608 1609template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1610unordered_multiset(from_range_t, _Range&&, _Allocator) 1611 -> unordered_multiset<ranges::range_value_t<_Range>, 1612 hash<ranges::range_value_t<_Range>>, 1613 equal_to<ranges::range_value_t<_Range>>, 1614 _Allocator>; 1615 1616template <ranges::input_range _Range, 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(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1623 -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 1624 1625# endif 1626 1627template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 1628unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 1629 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 1630 1631template <class _Tp, 1632 class _Hash, 1633 class _Allocator, 1634 class = enable_if_t<!__is_allocator<_Hash>::value>, 1635 class = enable_if_t<!is_integral<_Hash>::value>, 1636 class = enable_if_t<__is_allocator<_Allocator>::value>> 1637unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1638 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 1639# endif 1640 1641template <class _Value, class _Hash, class _Pred, class _Alloc> 1642unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1643 size_type __n, const hasher& __hf, const key_equal& __eql) 1644 : __table_(__hf, __eql) { 1645 __table_.__rehash_multi(__n); 1646} 1647 1648template <class _Value, class _Hash, class _Pred, class _Alloc> 1649unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1650 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1651 : __table_(__hf, __eql, __a) { 1652 __table_.__rehash_multi(__n); 1653} 1654 1655template <class _Value, class _Hash, class _Pred, class _Alloc> 1656template <class _InputIterator> 1657unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) { 1658 insert(__first, __last); 1659} 1660 1661template <class _Value, class _Hash, class _Pred, class _Alloc> 1662template <class _InputIterator> 1663unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1664 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1665 : __table_(__hf, __eql) { 1666 __table_.__rehash_multi(__n); 1667 insert(__first, __last); 1668} 1669 1670template <class _Value, class _Hash, class _Pred, class _Alloc> 1671template <class _InputIterator> 1672unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1673 _InputIterator __first, 1674 _InputIterator __last, 1675 size_type __n, 1676 const hasher& __hf, 1677 const key_equal& __eql, 1678 const allocator_type& __a) 1679 : __table_(__hf, __eql, __a) { 1680 __table_.__rehash_multi(__n); 1681 insert(__first, __last); 1682} 1683 1684template <class _Value, class _Hash, class _Pred, class _Alloc> 1685inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a) 1686 : __table_(__a) {} 1687 1688template <class _Value, class _Hash, class _Pred, class _Alloc> 1689unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u) 1690 : __table_(__u.__table_) { 1691 __table_.__rehash_multi(__u.bucket_count()); 1692 insert(__u.begin(), __u.end()); 1693} 1694 1695template <class _Value, class _Hash, class _Pred, class _Alloc> 1696unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1697 const unordered_multiset& __u, const allocator_type& __a) 1698 : __table_(__u.__table_, __a) { 1699 __table_.__rehash_multi(__u.bucket_count()); 1700 insert(__u.begin(), __u.end()); 1701} 1702 1703# ifndef _LIBCPP_CXX03_LANG 1704 1705template <class _Value, class _Hash, class _Pred, class _Alloc> 1706inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(unordered_multiset&& __u) 1707 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1708 : __table_(std::move(__u.__table_)) {} 1709 1710template <class _Value, class _Hash, class _Pred, class _Alloc> 1711unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1712 unordered_multiset&& __u, const allocator_type& __a) 1713 : __table_(std::move(__u.__table_), __a) { 1714 if (__a != __u.get_allocator()) { 1715 iterator __i = __u.begin(); 1716 while (__u.size() != 0) 1717 __table_.__emplace_multi(std::move(__u.__table_.remove(__i++)->__get_value())); 1718 } 1719} 1720 1721template <class _Value, class _Hash, class _Pred, class _Alloc> 1722unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) { 1723 insert(__il.begin(), __il.end()); 1724} 1725 1726template <class _Value, class _Hash, class _Pred, class _Alloc> 1727unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1728 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1729 : __table_(__hf, __eql) { 1730 __table_.__rehash_multi(__n); 1731 insert(__il.begin(), __il.end()); 1732} 1733 1734template <class _Value, class _Hash, class _Pred, class _Alloc> 1735unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1736 initializer_list<value_type> __il, 1737 size_type __n, 1738 const hasher& __hf, 1739 const key_equal& __eql, 1740 const allocator_type& __a) 1741 : __table_(__hf, __eql, __a) { 1742 __table_.__rehash_multi(__n); 1743 insert(__il.begin(), __il.end()); 1744} 1745 1746template <class _Value, class _Hash, class _Pred, class _Alloc> 1747inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1748unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_multiset&& __u) 1749 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 1750 __table_ = std::move(__u.__table_); 1751 return *this; 1752} 1753 1754template <class _Value, class _Hash, class _Pred, class _Alloc> 1755inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1756unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 1757 __table_.__assign_multi(__il.begin(), __il.end()); 1758 return *this; 1759} 1760 1761# endif // _LIBCPP_CXX03_LANG 1762 1763template <class _Value, class _Hash, class _Pred, class _Alloc> 1764template <class _InputIterator> 1765inline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 1766 for (; __first != __last; ++__first) 1767 __table_.__emplace_multi(*__first); 1768} 1769 1770template <class _Value, class _Hash, class _Pred, class _Alloc> 1771inline _LIBCPP_HIDE_FROM_ABI void 1772swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1773 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 1774 __x.swap(__y); 1775} 1776 1777# if _LIBCPP_STD_VER >= 20 1778template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> 1779inline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type 1780erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 1781 return std::__libcpp_erase_if_container(__c, __pred); 1782} 1783# endif 1784 1785template <class _Value, class _Hash, class _Pred, class _Alloc> 1786_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1787 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { 1788 if (__x.size() != __y.size()) 1789 return false; 1790 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1791 typedef pair<const_iterator, const_iterator> _EqRng; 1792 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { 1793 _EqRng __xeq = __x.equal_range(*__i); 1794 _EqRng __yeq = __y.equal_range(*__i); 1795 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || 1796 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1797 return false; 1798 __i = __xeq.second; 1799 } 1800 return true; 1801} 1802 1803# if _LIBCPP_STD_VER <= 17 1804 1805template <class _Value, class _Hash, class _Pred, class _Alloc> 1806inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1807 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { 1808 return !(__x == __y); 1809} 1810 1811# endif 1812 1813template <class _Value, class _Hash, class _Pred, class _Alloc> 1814struct __container_traits<unordered_multiset<_Value, _Hash, _Pred, _Alloc> > { 1815 // http://eel.is/c++draft/unord.req.except#2 1816 // For unordered associative containers, if an exception is thrown by any operation 1817 // other than the container's hash function from within an insert or emplace function 1818 // inserting a single element, the insertion has no effect. 1819 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = 1820 __is_nothrow_invocable_v<_Hash, const _Value&>; 1821 1822 static _LIBCPP_CONSTEXPR const bool __reservable = true; 1823}; 1824 1825_LIBCPP_END_NAMESPACE_STD 1826 1827# if _LIBCPP_STD_VER >= 17 1828_LIBCPP_BEGIN_NAMESPACE_STD 1829namespace pmr { 1830template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 1831using unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1832 1833template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 1834using unordered_multiset _LIBCPP_AVAILABILITY_PMR = 1835 std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1836} // namespace pmr 1837_LIBCPP_END_NAMESPACE_STD 1838# endif 1839 1840_LIBCPP_POP_MACROS 1841 1842# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 1843# include <cmath> 1844# include <concepts> 1845# include <cstdlib> 1846# include <functional> 1847# include <iterator> 1848# include <stdexcept> 1849# include <type_traits> 1850# endif 1851#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) 1852 1853#endif // _LIBCPP_UNORDERED_SET 1854