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