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