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