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