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