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