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