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