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