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