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