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 <__debug> 391#include <__functional/is_transparent.h> 392#include <__hash_table> 393#include <__node_handle> 394#include <__utility/forward.h> 395#include <compare> 396#include <functional> 397#include <iterator> // __libcpp_erase_if_container 398#include <version> 399 400#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 401#pragma GCC system_header 402#endif 403 404_LIBCPP_BEGIN_NAMESPACE_STD 405 406template <class _Value, class _Hash, class _Pred, class _Alloc> 407class unordered_multiset; 408 409template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 410 class _Alloc = allocator<_Value> > 411class _LIBCPP_TEMPLATE_VIS unordered_set 412{ 413public: 414 // types 415 typedef _Value key_type; 416 typedef key_type value_type; 417 typedef __identity_t<_Hash> hasher; 418 typedef __identity_t<_Pred> key_equal; 419 typedef __identity_t<_Alloc> allocator_type; 420 typedef value_type& reference; 421 typedef const value_type& const_reference; 422 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 423 "Invalid allocator::value_type"); 424 425private: 426 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 427 428 __table __table_; 429 430public: 431 typedef typename __table::pointer pointer; 432 typedef typename __table::const_pointer const_pointer; 433 typedef typename __table::size_type size_type; 434 typedef typename __table::difference_type difference_type; 435 436 typedef typename __table::const_iterator iterator; 437 typedef typename __table::const_iterator const_iterator; 438 typedef typename __table::const_local_iterator local_iterator; 439 typedef typename __table::const_local_iterator const_local_iterator; 440 441#if _LIBCPP_STD_VER > 14 442 typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 443 typedef __insert_return_type<iterator, node_type> insert_return_type; 444#endif 445 446 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 447 friend class _LIBCPP_TEMPLATE_VIS unordered_set; 448 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 449 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 450 451 _LIBCPP_INLINE_VISIBILITY 452 unordered_set() 453 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 454 { 455#if _LIBCPP_DEBUG_LEVEL == 2 456 __get_db()->__insert_c(this); 457#endif 458 } 459 explicit unordered_set(size_type __n, const hasher& __hf = hasher(), 460 const key_equal& __eql = key_equal()); 461#if _LIBCPP_STD_VER > 11 462 inline _LIBCPP_INLINE_VISIBILITY 463 unordered_set(size_type __n, const allocator_type& __a) 464 : unordered_set(__n, hasher(), key_equal(), __a) {} 465 inline _LIBCPP_INLINE_VISIBILITY 466 unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 467 : unordered_set(__n, __hf, key_equal(), __a) {} 468#endif 469 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, 470 const allocator_type& __a); 471 template <class _InputIterator> 472 unordered_set(_InputIterator __first, _InputIterator __last); 473 template <class _InputIterator> 474 unordered_set(_InputIterator __first, _InputIterator __last, 475 size_type __n, const hasher& __hf = hasher(), 476 const key_equal& __eql = key_equal()); 477 template <class _InputIterator> 478 unordered_set(_InputIterator __first, _InputIterator __last, 479 size_type __n, const hasher& __hf, const key_equal& __eql, 480 const allocator_type& __a); 481#if _LIBCPP_STD_VER > 11 482 template <class _InputIterator> 483 inline _LIBCPP_INLINE_VISIBILITY 484 unordered_set(_InputIterator __first, _InputIterator __last, 485 size_type __n, const allocator_type& __a) 486 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 487 template <class _InputIterator> 488 unordered_set(_InputIterator __first, _InputIterator __last, 489 size_type __n, const hasher& __hf, const allocator_type& __a) 490 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 491#endif 492 _LIBCPP_INLINE_VISIBILITY 493 explicit unordered_set(const allocator_type& __a); 494 unordered_set(const unordered_set& __u); 495 unordered_set(const unordered_set& __u, const allocator_type& __a); 496#ifndef _LIBCPP_CXX03_LANG 497 _LIBCPP_INLINE_VISIBILITY 498 unordered_set(unordered_set&& __u) 499 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 500 unordered_set(unordered_set&& __u, const allocator_type& __a); 501 unordered_set(initializer_list<value_type> __il); 502 unordered_set(initializer_list<value_type> __il, size_type __n, 503 const hasher& __hf = hasher(), 504 const key_equal& __eql = key_equal()); 505 unordered_set(initializer_list<value_type> __il, size_type __n, 506 const hasher& __hf, const key_equal& __eql, 507 const allocator_type& __a); 508#if _LIBCPP_STD_VER > 11 509 inline _LIBCPP_INLINE_VISIBILITY 510 unordered_set(initializer_list<value_type> __il, size_type __n, 511 const allocator_type& __a) 512 : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 513 inline _LIBCPP_INLINE_VISIBILITY 514 unordered_set(initializer_list<value_type> __il, size_type __n, 515 const hasher& __hf, const allocator_type& __a) 516 : unordered_set(__il, __n, __hf, key_equal(), __a) {} 517#endif 518#endif // _LIBCPP_CXX03_LANG 519 _LIBCPP_INLINE_VISIBILITY 520 ~unordered_set() { 521 static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 522 } 523 524 _LIBCPP_INLINE_VISIBILITY 525 unordered_set& operator=(const unordered_set& __u) 526 { 527 __table_ = __u.__table_; 528 return *this; 529 } 530#ifndef _LIBCPP_CXX03_LANG 531 _LIBCPP_INLINE_VISIBILITY 532 unordered_set& operator=(unordered_set&& __u) 533 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 534 _LIBCPP_INLINE_VISIBILITY 535 unordered_set& operator=(initializer_list<value_type> __il); 536#endif // _LIBCPP_CXX03_LANG 537 538 _LIBCPP_INLINE_VISIBILITY 539 allocator_type get_allocator() const _NOEXCEPT 540 {return allocator_type(__table_.__node_alloc());} 541 542 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 543 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 544 _LIBCPP_INLINE_VISIBILITY 545 size_type size() const _NOEXCEPT {return __table_.size();} 546 _LIBCPP_INLINE_VISIBILITY 547 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 548 549 _LIBCPP_INLINE_VISIBILITY 550 iterator begin() _NOEXCEPT {return __table_.begin();} 551 _LIBCPP_INLINE_VISIBILITY 552 iterator end() _NOEXCEPT {return __table_.end();} 553 _LIBCPP_INLINE_VISIBILITY 554 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 555 _LIBCPP_INLINE_VISIBILITY 556 const_iterator end() const _NOEXCEPT {return __table_.end();} 557 _LIBCPP_INLINE_VISIBILITY 558 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 559 _LIBCPP_INLINE_VISIBILITY 560 const_iterator cend() const _NOEXCEPT {return __table_.end();} 561 562#ifndef _LIBCPP_CXX03_LANG 563 template <class... _Args> 564 _LIBCPP_INLINE_VISIBILITY 565 pair<iterator, bool> emplace(_Args&&... __args) 566 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 567 template <class... _Args> 568 _LIBCPP_INLINE_VISIBILITY 569#if _LIBCPP_DEBUG_LEVEL == 2 570 iterator emplace_hint(const_iterator __p, _Args&&... __args) 571 { 572 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 573 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not" 574 " referring to this unordered_set"); 575 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 576 } 577#else 578 iterator emplace_hint(const_iterator, _Args&&... __args) 579 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} 580#endif 581 582 _LIBCPP_INLINE_VISIBILITY 583 pair<iterator, bool> insert(value_type&& __x) 584 {return __table_.__insert_unique(_VSTD::move(__x));} 585 _LIBCPP_INLINE_VISIBILITY 586#if _LIBCPP_DEBUG_LEVEL == 2 587 iterator insert(const_iterator __p, value_type&& __x) 588 { 589 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 590 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not" 591 " referring to this unordered_set"); 592 return insert(_VSTD::move(__x)).first; 593 } 594#else 595 iterator insert(const_iterator, value_type&& __x) 596 {return insert(_VSTD::move(__x)).first;} 597#endif 598 _LIBCPP_INLINE_VISIBILITY 599 void insert(initializer_list<value_type> __il) 600 {insert(__il.begin(), __il.end());} 601#endif // _LIBCPP_CXX03_LANG 602 _LIBCPP_INLINE_VISIBILITY 603 pair<iterator, bool> insert(const value_type& __x) 604 {return __table_.__insert_unique(__x);} 605 606 _LIBCPP_INLINE_VISIBILITY 607#if _LIBCPP_DEBUG_LEVEL == 2 608 iterator insert(const_iterator __p, const value_type& __x) 609 { 610 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 611 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not" 612 " referring to this unordered_set"); 613 return insert(__x).first; 614 } 615#else 616 iterator insert(const_iterator, const value_type& __x) 617 {return insert(__x).first;} 618#endif 619 template <class _InputIterator> 620 _LIBCPP_INLINE_VISIBILITY 621 void insert(_InputIterator __first, _InputIterator __last); 622 623 _LIBCPP_INLINE_VISIBILITY 624 iterator erase(const_iterator __p) {return __table_.erase(__p);} 625 _LIBCPP_INLINE_VISIBILITY 626 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 627 _LIBCPP_INLINE_VISIBILITY 628 iterator erase(const_iterator __first, const_iterator __last) 629 {return __table_.erase(__first, __last);} 630 _LIBCPP_INLINE_VISIBILITY 631 void clear() _NOEXCEPT {__table_.clear();} 632 633#if _LIBCPP_STD_VER > 14 634 _LIBCPP_INLINE_VISIBILITY 635 insert_return_type insert(node_type&& __nh) 636 { 637 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 638 "node_type with incompatible allocator passed to unordered_set::insert()"); 639 return __table_.template __node_handle_insert_unique< 640 node_type, insert_return_type>(_VSTD::move(__nh)); 641 } 642 _LIBCPP_INLINE_VISIBILITY 643 iterator insert(const_iterator __h, node_type&& __nh) 644 { 645 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 646 "node_type with incompatible allocator passed to unordered_set::insert()"); 647 return __table_.template __node_handle_insert_unique<node_type>( 648 __h, _VSTD::move(__nh)); 649 } 650 _LIBCPP_INLINE_VISIBILITY 651 node_type extract(key_type const& __key) 652 { 653 return __table_.template __node_handle_extract<node_type>(__key); 654 } 655 _LIBCPP_INLINE_VISIBILITY 656 node_type extract(const_iterator __it) 657 { 658 return __table_.template __node_handle_extract<node_type>(__it); 659 } 660 661 template<class _H2, class _P2> 662 _LIBCPP_INLINE_VISIBILITY 663 void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) 664 { 665 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 666 "merging container with incompatible allocator"); 667 __table_.__node_handle_merge_unique(__source.__table_); 668 } 669 template<class _H2, class _P2> 670 _LIBCPP_INLINE_VISIBILITY 671 void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) 672 { 673 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 674 "merging container with incompatible allocator"); 675 __table_.__node_handle_merge_unique(__source.__table_); 676 } 677 template<class _H2, class _P2> 678 _LIBCPP_INLINE_VISIBILITY 679 void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) 680 { 681 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 682 "merging container with incompatible allocator"); 683 __table_.__node_handle_merge_unique(__source.__table_); 684 } 685 template<class _H2, class _P2> 686 _LIBCPP_INLINE_VISIBILITY 687 void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) 688 { 689 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 690 "merging container with incompatible allocator"); 691 __table_.__node_handle_merge_unique(__source.__table_); 692 } 693#endif 694 695 _LIBCPP_INLINE_VISIBILITY 696 void swap(unordered_set& __u) 697 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 698 {__table_.swap(__u.__table_);} 699 700 _LIBCPP_INLINE_VISIBILITY 701 hasher hash_function() const {return __table_.hash_function();} 702 _LIBCPP_INLINE_VISIBILITY 703 key_equal key_eq() const {return __table_.key_eq();} 704 705 _LIBCPP_INLINE_VISIBILITY 706 iterator find(const key_type& __k) {return __table_.find(__k);} 707 _LIBCPP_INLINE_VISIBILITY 708 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 709#if _LIBCPP_STD_VER > 17 710 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 711 _LIBCPP_INLINE_VISIBILITY 712 iterator find(const _K2& __k) {return __table_.find(__k);} 713 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 714 _LIBCPP_INLINE_VISIBILITY 715 const_iterator find(const _K2& __k) const {return __table_.find(__k);} 716#endif // _LIBCPP_STD_VER > 17 717 718 _LIBCPP_INLINE_VISIBILITY 719 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 720#if _LIBCPP_STD_VER > 17 721 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 722 _LIBCPP_INLINE_VISIBILITY 723 size_type count(const _K2& __k) const {return __table_.__count_unique(__k);} 724#endif // _LIBCPP_STD_VER > 17 725 726#if _LIBCPP_STD_VER > 17 727 _LIBCPP_INLINE_VISIBILITY 728 bool contains(const key_type& __k) const {return find(__k) != end();} 729 730 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 731 _LIBCPP_INLINE_VISIBILITY 732 bool contains(const _K2& __k) const {return find(__k) != end();} 733#endif // _LIBCPP_STD_VER > 17 734 735 _LIBCPP_INLINE_VISIBILITY 736 pair<iterator, iterator> equal_range(const key_type& __k) 737 {return __table_.__equal_range_unique(__k);} 738 _LIBCPP_INLINE_VISIBILITY 739 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 740 {return __table_.__equal_range_unique(__k);} 741#if _LIBCPP_STD_VER > 17 742 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 743 _LIBCPP_INLINE_VISIBILITY 744 pair<iterator, iterator> equal_range(const _K2& __k) 745 {return __table_.__equal_range_unique(__k);} 746 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 747 _LIBCPP_INLINE_VISIBILITY 748 pair<const_iterator, const_iterator> equal_range(const _K2& __k) const 749 {return __table_.__equal_range_unique(__k);} 750#endif // _LIBCPP_STD_VER > 17 751 752 _LIBCPP_INLINE_VISIBILITY 753 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 754 _LIBCPP_INLINE_VISIBILITY 755 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 756 757 _LIBCPP_INLINE_VISIBILITY 758 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 759 _LIBCPP_INLINE_VISIBILITY 760 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 761 762 _LIBCPP_INLINE_VISIBILITY 763 local_iterator begin(size_type __n) {return __table_.begin(__n);} 764 _LIBCPP_INLINE_VISIBILITY 765 local_iterator end(size_type __n) {return __table_.end(__n);} 766 _LIBCPP_INLINE_VISIBILITY 767 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 768 _LIBCPP_INLINE_VISIBILITY 769 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 770 _LIBCPP_INLINE_VISIBILITY 771 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 772 _LIBCPP_INLINE_VISIBILITY 773 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 774 775 _LIBCPP_INLINE_VISIBILITY 776 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 777 _LIBCPP_INLINE_VISIBILITY 778 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 779 _LIBCPP_INLINE_VISIBILITY 780 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 781 _LIBCPP_INLINE_VISIBILITY 782 void rehash(size_type __n) {__table_.rehash(__n);} 783 _LIBCPP_INLINE_VISIBILITY 784 void reserve(size_type __n) {__table_.reserve(__n);} 785 786#if _LIBCPP_DEBUG_LEVEL == 2 787 788 bool __dereferenceable(const const_iterator* __i) const 789 {return __table_.__dereferenceable(__i);} 790 bool __decrementable(const const_iterator* __i) const 791 {return __table_.__decrementable(__i);} 792 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 793 {return __table_.__addable(__i, __n);} 794 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 795 {return __table_.__addable(__i, __n);} 796 797#endif // _LIBCPP_DEBUG_LEVEL == 2 798 799}; 800 801#if _LIBCPP_STD_VER >= 17 802template<class _InputIterator, 803 class _Hash = hash<__iter_value_type<_InputIterator>>, 804 class _Pred = equal_to<__iter_value_type<_InputIterator>>, 805 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 806 class = enable_if_t<!__is_allocator<_Hash>::value>, 807 class = enable_if_t<!is_integral<_Hash>::value>, 808 class = enable_if_t<!__is_allocator<_Pred>::value>, 809 class = enable_if_t<__is_allocator<_Allocator>::value>> 810unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0, 811 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 812 -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 813 814template<class _Tp, class _Hash = hash<_Tp>, 815 class _Pred = equal_to<_Tp>, 816 class _Allocator = allocator<_Tp>, 817 class = enable_if_t<!__is_allocator<_Hash>::value>, 818 class = enable_if_t<!is_integral<_Hash>::value>, 819 class = enable_if_t<!__is_allocator<_Pred>::value>, 820 class = enable_if_t<__is_allocator<_Allocator>::value>> 821unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0, 822 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 823 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 824 825template<class _InputIterator, class _Allocator, 826 class = enable_if_t<__is_allocator<_Allocator>::value>> 827unordered_set(_InputIterator, _InputIterator, 828 typename allocator_traits<_Allocator>::size_type, _Allocator) 829 -> unordered_set<__iter_value_type<_InputIterator>, 830 hash<__iter_value_type<_InputIterator>>, 831 equal_to<__iter_value_type<_InputIterator>>, 832 _Allocator>; 833 834template<class _InputIterator, class _Hash, class _Allocator, 835 class = enable_if_t<!__is_allocator<_Hash>::value>, 836 class = enable_if_t<!is_integral<_Hash>::value>, 837 class = enable_if_t<__is_allocator<_Allocator>::value>> 838unordered_set(_InputIterator, _InputIterator, 839 typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 840 -> unordered_set<__iter_value_type<_InputIterator>, _Hash, 841 equal_to<__iter_value_type<_InputIterator>>, 842 _Allocator>; 843 844template<class _Tp, class _Allocator, 845 class = enable_if_t<__is_allocator<_Allocator>::value>> 846unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 847 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 848 849template<class _Tp, class _Hash, class _Allocator, 850 class = enable_if_t<!__is_allocator<_Hash>::value>, 851 class = enable_if_t<!is_integral<_Hash>::value>, 852 class = enable_if_t<__is_allocator<_Allocator>::value>> 853unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 854 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 855#endif 856 857template <class _Value, class _Hash, class _Pred, class _Alloc> 858unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 859 const hasher& __hf, const key_equal& __eql) 860 : __table_(__hf, __eql) 861{ 862#if _LIBCPP_DEBUG_LEVEL == 2 863 __get_db()->__insert_c(this); 864#endif 865 __table_.rehash(__n); 866} 867 868template <class _Value, class _Hash, class _Pred, class _Alloc> 869unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 870 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 871 : __table_(__hf, __eql, __a) 872{ 873#if _LIBCPP_DEBUG_LEVEL == 2 874 __get_db()->__insert_c(this); 875#endif 876 __table_.rehash(__n); 877} 878 879template <class _Value, class _Hash, class _Pred, class _Alloc> 880template <class _InputIterator> 881unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 882 _InputIterator __first, _InputIterator __last) 883{ 884#if _LIBCPP_DEBUG_LEVEL == 2 885 __get_db()->__insert_c(this); 886#endif 887 insert(__first, __last); 888} 889 890template <class _Value, class _Hash, class _Pred, class _Alloc> 891template <class _InputIterator> 892unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 893 _InputIterator __first, _InputIterator __last, size_type __n, 894 const hasher& __hf, const key_equal& __eql) 895 : __table_(__hf, __eql) 896{ 897#if _LIBCPP_DEBUG_LEVEL == 2 898 __get_db()->__insert_c(this); 899#endif 900 __table_.rehash(__n); 901 insert(__first, __last); 902} 903 904template <class _Value, class _Hash, class _Pred, class _Alloc> 905template <class _InputIterator> 906unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 907 _InputIterator __first, _InputIterator __last, size_type __n, 908 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 909 : __table_(__hf, __eql, __a) 910{ 911#if _LIBCPP_DEBUG_LEVEL == 2 912 __get_db()->__insert_c(this); 913#endif 914 __table_.rehash(__n); 915 insert(__first, __last); 916} 917 918template <class _Value, class _Hash, class _Pred, class _Alloc> 919inline 920unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 921 const allocator_type& __a) 922 : __table_(__a) 923{ 924#if _LIBCPP_DEBUG_LEVEL == 2 925 __get_db()->__insert_c(this); 926#endif 927} 928 929template <class _Value, class _Hash, class _Pred, class _Alloc> 930unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 931 const unordered_set& __u) 932 : __table_(__u.__table_) 933{ 934#if _LIBCPP_DEBUG_LEVEL == 2 935 __get_db()->__insert_c(this); 936#endif 937 __table_.rehash(__u.bucket_count()); 938 insert(__u.begin(), __u.end()); 939} 940 941template <class _Value, class _Hash, class _Pred, class _Alloc> 942unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 943 const unordered_set& __u, const allocator_type& __a) 944 : __table_(__u.__table_, __a) 945{ 946#if _LIBCPP_DEBUG_LEVEL == 2 947 __get_db()->__insert_c(this); 948#endif 949 __table_.rehash(__u.bucket_count()); 950 insert(__u.begin(), __u.end()); 951} 952 953#ifndef _LIBCPP_CXX03_LANG 954 955template <class _Value, class _Hash, class _Pred, class _Alloc> 956inline 957unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 958 unordered_set&& __u) 959 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 960 : __table_(_VSTD::move(__u.__table_)) 961{ 962#if _LIBCPP_DEBUG_LEVEL == 2 963 __get_db()->__insert_c(this); 964 __get_db()->swap(this, &__u); 965#endif 966} 967 968template <class _Value, class _Hash, class _Pred, class _Alloc> 969unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 970 unordered_set&& __u, const allocator_type& __a) 971 : __table_(_VSTD::move(__u.__table_), __a) 972{ 973#if _LIBCPP_DEBUG_LEVEL == 2 974 __get_db()->__insert_c(this); 975#endif 976 if (__a != __u.get_allocator()) 977 { 978 iterator __i = __u.begin(); 979 while (__u.size() != 0) 980 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 981 } 982#if _LIBCPP_DEBUG_LEVEL == 2 983 else 984 __get_db()->swap(this, &__u); 985#endif 986} 987 988template <class _Value, class _Hash, class _Pred, class _Alloc> 989unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 990 initializer_list<value_type> __il) 991{ 992#if _LIBCPP_DEBUG_LEVEL == 2 993 __get_db()->__insert_c(this); 994#endif 995 insert(__il.begin(), __il.end()); 996} 997 998template <class _Value, class _Hash, class _Pred, class _Alloc> 999unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1000 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1001 const key_equal& __eql) 1002 : __table_(__hf, __eql) 1003{ 1004#if _LIBCPP_DEBUG_LEVEL == 2 1005 __get_db()->__insert_c(this); 1006#endif 1007 __table_.rehash(__n); 1008 insert(__il.begin(), __il.end()); 1009} 1010 1011template <class _Value, class _Hash, class _Pred, class _Alloc> 1012unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1013 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1014 const key_equal& __eql, const allocator_type& __a) 1015 : __table_(__hf, __eql, __a) 1016{ 1017#if _LIBCPP_DEBUG_LEVEL == 2 1018 __get_db()->__insert_c(this); 1019#endif 1020 __table_.rehash(__n); 1021 insert(__il.begin(), __il.end()); 1022} 1023 1024template <class _Value, class _Hash, class _Pred, class _Alloc> 1025inline 1026unordered_set<_Value, _Hash, _Pred, _Alloc>& 1027unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 1028 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1029{ 1030 __table_ = _VSTD::move(__u.__table_); 1031 return *this; 1032} 1033 1034template <class _Value, class _Hash, class _Pred, class _Alloc> 1035inline 1036unordered_set<_Value, _Hash, _Pred, _Alloc>& 1037unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 1038 initializer_list<value_type> __il) 1039{ 1040 __table_.__assign_unique(__il.begin(), __il.end()); 1041 return *this; 1042} 1043 1044#endif // _LIBCPP_CXX03_LANG 1045 1046template <class _Value, class _Hash, class _Pred, class _Alloc> 1047template <class _InputIterator> 1048inline 1049void 1050unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1051 _InputIterator __last) 1052{ 1053 for (; __first != __last; ++__first) 1054 __table_.__insert_unique(*__first); 1055} 1056 1057template <class _Value, class _Hash, class _Pred, class _Alloc> 1058inline _LIBCPP_INLINE_VISIBILITY 1059void 1060swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1061 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1062 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1063{ 1064 __x.swap(__y); 1065} 1066 1067#if _LIBCPP_STD_VER > 17 1068template <class _Value, class _Hash, class _Pred, class _Alloc, 1069 class _Predicate> 1070inline _LIBCPP_INLINE_VISIBILITY 1071 typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type 1072 erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, 1073 _Predicate __pred) { 1074 return _VSTD::__libcpp_erase_if_container(__c, __pred); 1075} 1076#endif 1077 1078template <class _Value, class _Hash, class _Pred, class _Alloc> 1079bool 1080operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1081 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1082{ 1083 if (__x.size() != __y.size()) 1084 return false; 1085 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 1086 const_iterator; 1087 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1088 __i != __ex; ++__i) 1089 { 1090 const_iterator __j = __y.find(*__i); 1091 if (__j == __ey || !(*__i == *__j)) 1092 return false; 1093 } 1094 return true; 1095} 1096 1097template <class _Value, class _Hash, class _Pred, class _Alloc> 1098inline _LIBCPP_INLINE_VISIBILITY 1099bool 1100operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1101 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1102{ 1103 return !(__x == __y); 1104} 1105 1106template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 1107 class _Alloc = allocator<_Value> > 1108class _LIBCPP_TEMPLATE_VIS unordered_multiset 1109{ 1110public: 1111 // types 1112 typedef _Value key_type; 1113 typedef key_type value_type; 1114 typedef __identity_t<_Hash> hasher; 1115 typedef __identity_t<_Pred> key_equal; 1116 typedef __identity_t<_Alloc> allocator_type; 1117 typedef value_type& reference; 1118 typedef const value_type& const_reference; 1119 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1120 "Invalid allocator::value_type"); 1121 1122private: 1123 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 1124 1125 __table __table_; 1126 1127public: 1128 typedef typename __table::pointer pointer; 1129 typedef typename __table::const_pointer const_pointer; 1130 typedef typename __table::size_type size_type; 1131 typedef typename __table::difference_type difference_type; 1132 1133 typedef typename __table::const_iterator iterator; 1134 typedef typename __table::const_iterator const_iterator; 1135 typedef typename __table::const_local_iterator local_iterator; 1136 typedef typename __table::const_local_iterator const_local_iterator; 1137 1138#if _LIBCPP_STD_VER > 14 1139 typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 1140#endif 1141 1142 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 1143 friend class _LIBCPP_TEMPLATE_VIS unordered_set; 1144 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 1145 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 1146 1147 _LIBCPP_INLINE_VISIBILITY 1148 unordered_multiset() 1149 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1150 { 1151#if _LIBCPP_DEBUG_LEVEL == 2 1152 __get_db()->__insert_c(this); 1153#endif 1154 } 1155 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), 1156 const key_equal& __eql = key_equal()); 1157 unordered_multiset(size_type __n, const hasher& __hf, 1158 const key_equal& __eql, const allocator_type& __a); 1159#if _LIBCPP_STD_VER > 11 1160 inline _LIBCPP_INLINE_VISIBILITY 1161 unordered_multiset(size_type __n, const allocator_type& __a) 1162 : unordered_multiset(__n, hasher(), key_equal(), __a) {} 1163 inline _LIBCPP_INLINE_VISIBILITY 1164 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 1165 : unordered_multiset(__n, __hf, key_equal(), __a) {} 1166#endif 1167 template <class _InputIterator> 1168 unordered_multiset(_InputIterator __first, _InputIterator __last); 1169 template <class _InputIterator> 1170 unordered_multiset(_InputIterator __first, _InputIterator __last, 1171 size_type __n, const hasher& __hf = hasher(), 1172 const key_equal& __eql = key_equal()); 1173 template <class _InputIterator> 1174 unordered_multiset(_InputIterator __first, _InputIterator __last, 1175 size_type __n , const hasher& __hf, 1176 const key_equal& __eql, const allocator_type& __a); 1177#if _LIBCPP_STD_VER > 11 1178 template <class _InputIterator> 1179 inline _LIBCPP_INLINE_VISIBILITY 1180 unordered_multiset(_InputIterator __first, _InputIterator __last, 1181 size_type __n, const allocator_type& __a) 1182 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 1183 template <class _InputIterator> 1184 inline _LIBCPP_INLINE_VISIBILITY 1185 unordered_multiset(_InputIterator __first, _InputIterator __last, 1186 size_type __n, const hasher& __hf, const allocator_type& __a) 1187 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 1188#endif 1189 _LIBCPP_INLINE_VISIBILITY 1190 explicit unordered_multiset(const allocator_type& __a); 1191 unordered_multiset(const unordered_multiset& __u); 1192 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 1193#ifndef _LIBCPP_CXX03_LANG 1194 _LIBCPP_INLINE_VISIBILITY 1195 unordered_multiset(unordered_multiset&& __u) 1196 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1197 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 1198 unordered_multiset(initializer_list<value_type> __il); 1199 unordered_multiset(initializer_list<value_type> __il, size_type __n, 1200 const hasher& __hf = hasher(), 1201 const key_equal& __eql = key_equal()); 1202 unordered_multiset(initializer_list<value_type> __il, size_type __n, 1203 const hasher& __hf, const key_equal& __eql, 1204 const allocator_type& __a); 1205#if _LIBCPP_STD_VER > 11 1206 inline _LIBCPP_INLINE_VISIBILITY 1207 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1208 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 1209 inline _LIBCPP_INLINE_VISIBILITY 1210 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 1211 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 1212#endif 1213#endif // _LIBCPP_CXX03_LANG 1214 _LIBCPP_INLINE_VISIBILITY 1215 ~unordered_multiset() { 1216 static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 1217 } 1218 1219 _LIBCPP_INLINE_VISIBILITY 1220 unordered_multiset& operator=(const unordered_multiset& __u) 1221 { 1222 __table_ = __u.__table_; 1223 return *this; 1224 } 1225#ifndef _LIBCPP_CXX03_LANG 1226 _LIBCPP_INLINE_VISIBILITY 1227 unordered_multiset& operator=(unordered_multiset&& __u) 1228 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1229 unordered_multiset& operator=(initializer_list<value_type> __il); 1230#endif // _LIBCPP_CXX03_LANG 1231 1232 _LIBCPP_INLINE_VISIBILITY 1233 allocator_type get_allocator() const _NOEXCEPT 1234 {return allocator_type(__table_.__node_alloc());} 1235 1236 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1237 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1238 _LIBCPP_INLINE_VISIBILITY 1239 size_type size() const _NOEXCEPT {return __table_.size();} 1240 _LIBCPP_INLINE_VISIBILITY 1241 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1242 1243 _LIBCPP_INLINE_VISIBILITY 1244 iterator begin() _NOEXCEPT {return __table_.begin();} 1245 _LIBCPP_INLINE_VISIBILITY 1246 iterator end() _NOEXCEPT {return __table_.end();} 1247 _LIBCPP_INLINE_VISIBILITY 1248 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1249 _LIBCPP_INLINE_VISIBILITY 1250 const_iterator end() const _NOEXCEPT {return __table_.end();} 1251 _LIBCPP_INLINE_VISIBILITY 1252 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1253 _LIBCPP_INLINE_VISIBILITY 1254 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1255 1256#ifndef _LIBCPP_CXX03_LANG 1257 template <class... _Args> 1258 _LIBCPP_INLINE_VISIBILITY 1259 iterator emplace(_Args&&... __args) 1260 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1261 template <class... _Args> 1262 _LIBCPP_INLINE_VISIBILITY 1263 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1264 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1265 1266 _LIBCPP_INLINE_VISIBILITY 1267 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 1268 _LIBCPP_INLINE_VISIBILITY 1269 iterator insert(const_iterator __p, value_type&& __x) 1270 {return __table_.__insert_multi(__p, _VSTD::move(__x));} 1271 _LIBCPP_INLINE_VISIBILITY 1272 void insert(initializer_list<value_type> __il) 1273 {insert(__il.begin(), __il.end());} 1274#endif // _LIBCPP_CXX03_LANG 1275 1276 _LIBCPP_INLINE_VISIBILITY 1277 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1278 1279 _LIBCPP_INLINE_VISIBILITY 1280 iterator insert(const_iterator __p, const value_type& __x) 1281 {return __table_.__insert_multi(__p, __x);} 1282 1283 template <class _InputIterator> 1284 _LIBCPP_INLINE_VISIBILITY 1285 void insert(_InputIterator __first, _InputIterator __last); 1286 1287#if _LIBCPP_STD_VER > 14 1288 _LIBCPP_INLINE_VISIBILITY 1289 iterator insert(node_type&& __nh) 1290 { 1291 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1292 "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1293 return __table_.template __node_handle_insert_multi<node_type>( 1294 _VSTD::move(__nh)); 1295 } 1296 _LIBCPP_INLINE_VISIBILITY 1297 iterator insert(const_iterator __hint, node_type&& __nh) 1298 { 1299 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1300 "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1301 return __table_.template __node_handle_insert_multi<node_type>( 1302 __hint, _VSTD::move(__nh)); 1303 } 1304 _LIBCPP_INLINE_VISIBILITY 1305 node_type extract(const_iterator __position) 1306 { 1307 return __table_.template __node_handle_extract<node_type>( 1308 __position); 1309 } 1310 _LIBCPP_INLINE_VISIBILITY 1311 node_type extract(key_type const& __key) 1312 { 1313 return __table_.template __node_handle_extract<node_type>(__key); 1314 } 1315 1316 template <class _H2, class _P2> 1317 _LIBCPP_INLINE_VISIBILITY 1318 void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) 1319 { 1320 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1321 "merging container with incompatible allocator"); 1322 return __table_.__node_handle_merge_multi(__source.__table_); 1323 } 1324 template <class _H2, class _P2> 1325 _LIBCPP_INLINE_VISIBILITY 1326 void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) 1327 { 1328 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1329 "merging container with incompatible allocator"); 1330 return __table_.__node_handle_merge_multi(__source.__table_); 1331 } 1332 template <class _H2, class _P2> 1333 _LIBCPP_INLINE_VISIBILITY 1334 void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) 1335 { 1336 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1337 "merging container with incompatible allocator"); 1338 return __table_.__node_handle_merge_multi(__source.__table_); 1339 } 1340 template <class _H2, class _P2> 1341 _LIBCPP_INLINE_VISIBILITY 1342 void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) 1343 { 1344 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1345 "merging container with incompatible allocator"); 1346 return __table_.__node_handle_merge_multi(__source.__table_); 1347 } 1348#endif 1349 1350 _LIBCPP_INLINE_VISIBILITY 1351 iterator erase(const_iterator __p) {return __table_.erase(__p);} 1352 _LIBCPP_INLINE_VISIBILITY 1353 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1354 _LIBCPP_INLINE_VISIBILITY 1355 iterator erase(const_iterator __first, const_iterator __last) 1356 {return __table_.erase(__first, __last);} 1357 _LIBCPP_INLINE_VISIBILITY 1358 void clear() _NOEXCEPT {__table_.clear();} 1359 1360 _LIBCPP_INLINE_VISIBILITY 1361 void swap(unordered_multiset& __u) 1362 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1363 {__table_.swap(__u.__table_);} 1364 1365 _LIBCPP_INLINE_VISIBILITY 1366 hasher hash_function() const {return __table_.hash_function();} 1367 _LIBCPP_INLINE_VISIBILITY 1368 key_equal key_eq() const {return __table_.key_eq();} 1369 1370 _LIBCPP_INLINE_VISIBILITY 1371 iterator find(const key_type& __k) {return __table_.find(__k);} 1372 _LIBCPP_INLINE_VISIBILITY 1373 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1374#if _LIBCPP_STD_VER > 17 1375 template<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1376 _LIBCPP_INLINE_VISIBILITY 1377 iterator find(const _K2& __k) {return __table_.find(__k);} 1378 template<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1379 _LIBCPP_INLINE_VISIBILITY 1380 const_iterator find(const _K2& __k) const {return __table_.find(__k);} 1381#endif // _LIBCPP_STD_VER > 17 1382 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<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1387 _LIBCPP_INLINE_VISIBILITY 1388 size_type count(const _K2& __k) const {return __table_.__count_multi(__k);} 1389#endif // _LIBCPP_STD_VER > 17 1390 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<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1396 _LIBCPP_INLINE_VISIBILITY 1397 bool contains(const _K2& __k) const {return find(__k) != end();} 1398#endif // _LIBCPP_STD_VER > 17 1399 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<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1408 _LIBCPP_INLINE_VISIBILITY 1409 pair<iterator, iterator> equal_range(const _K2& __k) 1410 {return __table_.__equal_range_multi(__k);} 1411 template<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1412 _LIBCPP_INLINE_VISIBILITY 1413 pair<const_iterator, const_iterator> equal_range(const _K2& __k) const 1414 {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#if _LIBCPP_STD_VER >= 17 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 = enable_if_t<!__is_allocator<_Hash>::value>, 1472 class = enable_if_t<!is_integral<_Hash>::value>, 1473 class = enable_if_t<!__is_allocator<_Pred>::value>, 1474 class = enable_if_t<__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 = enable_if_t<!__is_allocator<_Hash>::value>, 1482 class = enable_if_t<!is_integral<_Hash>::value>, 1483 class = enable_if_t<!__is_allocator<_Pred>::value>, 1484 class = enable_if_t<__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 = enable_if_t<__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 = enable_if_t<!__is_allocator<_Hash>::value>, 1499 class = enable_if_t<!is_integral<_Hash>::value>, 1500 class = enable_if_t<__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 = enable_if_t<__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 = enable_if_t<!__is_allocator<_Hash>::value>, 1514 class = enable_if_t<!is_integral<_Hash>::value>, 1515 class = enable_if_t<__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