1// -*- C++ -*- 2//===-------------------------- unordered_set -----------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is dual licensed under the MIT and the University of Illinois Open 7// Source Licenses. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP_UNORDERED_SET 12#define _LIBCPP_UNORDERED_SET 13 14/* 15 16 unordered_set synopsis 17 18#include <initializer_list> 19 20namespace std 21{ 22 23template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 24 class Alloc = allocator<Value>> 25class unordered_set 26{ 27public: 28 // types 29 typedef Value key_type; 30 typedef key_type value_type; 31 typedef Hash hasher; 32 typedef Pred key_equal; 33 typedef Alloc allocator_type; 34 typedef value_type& reference; 35 typedef const value_type& const_reference; 36 typedef typename allocator_traits<allocator_type>::pointer pointer; 37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 38 typedef typename allocator_traits<allocator_type>::size_type size_type; 39 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 40 41 typedef /unspecified/ iterator; 42 typedef /unspecified/ const_iterator; 43 typedef /unspecified/ local_iterator; 44 typedef /unspecified/ const_local_iterator; 45 46 unordered_set() 47 noexcept( 48 is_nothrow_default_constructible<hasher>::value && 49 is_nothrow_default_constructible<key_equal>::value && 50 is_nothrow_default_constructible<allocator_type>::value); 51 explicit unordered_set(size_type n, const hasher& hf = hasher(), 52 const key_equal& eql = key_equal(), 53 const allocator_type& a = allocator_type()); 54 template <class InputIterator> 55 unordered_set(InputIterator f, InputIterator l, 56 size_type n = 0, const hasher& hf = hasher(), 57 const key_equal& eql = key_equal(), 58 const allocator_type& a = allocator_type()); 59 explicit unordered_set(const allocator_type&); 60 unordered_set(const unordered_set&); 61 unordered_set(const unordered_set&, const Allocator&); 62 unordered_set(unordered_set&&) 63 noexcept( 64 is_nothrow_move_constructible<hasher>::value && 65 is_nothrow_move_constructible<key_equal>::value && 66 is_nothrow_move_constructible<allocator_type>::value); 67 unordered_set(unordered_set&&, const Allocator&); 68 unordered_set(initializer_list<value_type>, size_type n = 0, 69 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 70 const allocator_type& a = allocator_type()); 71 unordered_set(size_type n, const allocator_type& a); // C++14 72 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14 73 template <class InputIterator> 74 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 75 template <class InputIterator> 76 unordered_set(InputIterator f, InputIterator l, size_type n, 77 const hasher& hf, const allocator_type& a); // C++14 78 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 79 unordered_set(initializer_list<value_type> il, size_type n, 80 const hasher& hf, const allocator_type& a); // C++14 81 ~unordered_set(); 82 unordered_set& operator=(const unordered_set&); 83 unordered_set& operator=(unordered_set&&) 84 noexcept( 85 allocator_type::propagate_on_container_move_assignment::value && 86 is_nothrow_move_assignable<allocator_type>::value && 87 is_nothrow_move_assignable<hasher>::value && 88 is_nothrow_move_assignable<key_equal>::value); 89 unordered_set& operator=(initializer_list<value_type>); 90 91 allocator_type get_allocator() const noexcept; 92 93 bool empty() const noexcept; 94 size_type size() const noexcept; 95 size_type max_size() const noexcept; 96 97 iterator begin() noexcept; 98 iterator end() noexcept; 99 const_iterator begin() const noexcept; 100 const_iterator end() const noexcept; 101 const_iterator cbegin() const noexcept; 102 const_iterator cend() const noexcept; 103 104 template <class... Args> 105 pair<iterator, bool> emplace(Args&&... args); 106 template <class... Args> 107 iterator emplace_hint(const_iterator position, Args&&... args); 108 pair<iterator, bool> insert(const value_type& obj); 109 pair<iterator, bool> insert(value_type&& obj); 110 iterator insert(const_iterator hint, const value_type& obj); 111 iterator insert(const_iterator hint, value_type&& obj); 112 template <class InputIterator> 113 void insert(InputIterator first, InputIterator last); 114 void insert(initializer_list<value_type>); 115 116 iterator erase(const_iterator position); 117 iterator erase(iterator position); // C++14 118 size_type erase(const key_type& k); 119 iterator erase(const_iterator first, const_iterator last); 120 void clear() noexcept; 121 122 void swap(unordered_set&) 123 noexcept(allocator_traits<Allocator>::is_always_equal::value && 124 noexcept(swap(declval<hasher&>(), declval<hasher&>())) && 125 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17 126 127 hasher hash_function() const; 128 key_equal key_eq() const; 129 130 iterator find(const key_type& k); 131 const_iterator find(const key_type& k) const; 132 size_type count(const key_type& k) const; 133 pair<iterator, iterator> equal_range(const key_type& k); 134 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 135 136 size_type bucket_count() const noexcept; 137 size_type max_bucket_count() const noexcept; 138 139 size_type bucket_size(size_type n) const; 140 size_type bucket(const key_type& k) const; 141 142 local_iterator begin(size_type n); 143 local_iterator end(size_type n); 144 const_local_iterator begin(size_type n) const; 145 const_local_iterator end(size_type n) const; 146 const_local_iterator cbegin(size_type n) const; 147 const_local_iterator cend(size_type n) const; 148 149 float load_factor() const noexcept; 150 float max_load_factor() const noexcept; 151 void max_load_factor(float z); 152 void rehash(size_type n); 153 void reserve(size_type n); 154}; 155 156template <class Value, class Hash, class Pred, class Alloc> 157 void swap(unordered_set<Value, Hash, Pred, Alloc>& x, 158 unordered_set<Value, Hash, Pred, Alloc>& y) 159 noexcept(noexcept(x.swap(y))); 160 161template <class Value, class Hash, class Pred, class Alloc> 162 bool 163 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x, 164 const unordered_set<Value, Hash, Pred, Alloc>& y); 165 166template <class Value, class Hash, class Pred, class Alloc> 167 bool 168 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x, 169 const unordered_set<Value, Hash, Pred, Alloc>& y); 170 171template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 172 class Alloc = allocator<Value>> 173class unordered_multiset 174{ 175public: 176 // types 177 typedef Value key_type; 178 typedef key_type value_type; 179 typedef Hash hasher; 180 typedef Pred key_equal; 181 typedef Alloc allocator_type; 182 typedef value_type& reference; 183 typedef const value_type& const_reference; 184 typedef typename allocator_traits<allocator_type>::pointer pointer; 185 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 186 typedef typename allocator_traits<allocator_type>::size_type size_type; 187 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 188 189 typedef /unspecified/ iterator; 190 typedef /unspecified/ const_iterator; 191 typedef /unspecified/ local_iterator; 192 typedef /unspecified/ const_local_iterator; 193 194 unordered_multiset() 195 noexcept( 196 is_nothrow_default_constructible<hasher>::value && 197 is_nothrow_default_constructible<key_equal>::value && 198 is_nothrow_default_constructible<allocator_type>::value); 199 explicit unordered_multiset(size_type n, const hasher& hf = hasher(), 200 const key_equal& eql = key_equal(), 201 const allocator_type& a = allocator_type()); 202 template <class InputIterator> 203 unordered_multiset(InputIterator f, InputIterator l, 204 size_type n = 0, const hasher& hf = hasher(), 205 const key_equal& eql = key_equal(), 206 const allocator_type& a = allocator_type()); 207 explicit unordered_multiset(const allocator_type&); 208 unordered_multiset(const unordered_multiset&); 209 unordered_multiset(const unordered_multiset&, const Allocator&); 210 unordered_multiset(unordered_multiset&&) 211 noexcept( 212 is_nothrow_move_constructible<hasher>::value && 213 is_nothrow_move_constructible<key_equal>::value && 214 is_nothrow_move_constructible<allocator_type>::value); 215 unordered_multiset(unordered_multiset&&, const Allocator&); 216 unordered_multiset(initializer_list<value_type>, size_type n = /see below/, 217 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 218 const allocator_type& a = allocator_type()); 219 unordered_multiset(size_type n, const allocator_type& a); // C++14 220 unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14 221 template <class InputIterator> 222 unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 223 template <class InputIterator> 224 unordered_multiset(InputIterator f, InputIterator l, size_type n, 225 const hasher& hf, const allocator_type& a); // C++14 226 unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 227 unordered_multiset(initializer_list<value_type> il, size_type n, 228 const hasher& hf, const allocator_type& a); // C++14 229 ~unordered_multiset(); 230 unordered_multiset& operator=(const unordered_multiset&); 231 unordered_multiset& operator=(unordered_multiset&&) 232 noexcept( 233 allocator_type::propagate_on_container_move_assignment::value && 234 is_nothrow_move_assignable<allocator_type>::value && 235 is_nothrow_move_assignable<hasher>::value && 236 is_nothrow_move_assignable<key_equal>::value); 237 unordered_multiset& operator=(initializer_list<value_type>); 238 239 allocator_type get_allocator() const noexcept; 240 241 bool empty() const noexcept; 242 size_type size() const noexcept; 243 size_type max_size() const noexcept; 244 245 iterator begin() noexcept; 246 iterator end() noexcept; 247 const_iterator begin() const noexcept; 248 const_iterator end() const noexcept; 249 const_iterator cbegin() const noexcept; 250 const_iterator cend() const noexcept; 251 252 template <class... Args> 253 iterator emplace(Args&&... args); 254 template <class... Args> 255 iterator emplace_hint(const_iterator position, Args&&... args); 256 iterator insert(const value_type& obj); 257 iterator insert(value_type&& obj); 258 iterator insert(const_iterator hint, const value_type& obj); 259 iterator insert(const_iterator hint, value_type&& obj); 260 template <class InputIterator> 261 void insert(InputIterator first, InputIterator last); 262 void insert(initializer_list<value_type>); 263 264 iterator erase(const_iterator position); 265 iterator erase(iterator position); // C++14 266 size_type erase(const key_type& k); 267 iterator erase(const_iterator first, const_iterator last); 268 void clear() noexcept; 269 270 void swap(unordered_multiset&) 271 noexcept(allocator_traits<Allocator>::is_always_equal::value && 272 noexcept(swap(declval<hasher&>(), declval<hasher&>())) && 273 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17 274 275 hasher hash_function() const; 276 key_equal key_eq() const; 277 278 iterator find(const key_type& k); 279 const_iterator find(const key_type& k) const; 280 size_type count(const key_type& k) const; 281 pair<iterator, iterator> equal_range(const key_type& k); 282 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 283 284 size_type bucket_count() const noexcept; 285 size_type max_bucket_count() const noexcept; 286 287 size_type bucket_size(size_type n) const; 288 size_type bucket(const key_type& k) const; 289 290 local_iterator begin(size_type n); 291 local_iterator end(size_type n); 292 const_local_iterator begin(size_type n) const; 293 const_local_iterator end(size_type n) const; 294 const_local_iterator cbegin(size_type n) const; 295 const_local_iterator cend(size_type n) const; 296 297 float load_factor() const noexcept; 298 float max_load_factor() const noexcept; 299 void max_load_factor(float z); 300 void rehash(size_type n); 301 void reserve(size_type n); 302}; 303 304template <class Value, class Hash, class Pred, class Alloc> 305 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x, 306 unordered_multiset<Value, Hash, Pred, Alloc>& y) 307 noexcept(noexcept(x.swap(y))); 308 309template <class Value, class Hash, class Pred, class Alloc> 310 bool 311 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 312 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 313 314template <class Value, class Hash, class Pred, class Alloc> 315 bool 316 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 317 const unordered_multiset<Value, Hash, Pred, Alloc>& y); 318} // std 319 320*/ 321 322#include <__config> 323#include <__hash_table> 324#include <functional> 325 326#include <__debug> 327 328#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 329#pragma GCC system_header 330#endif 331 332_LIBCPP_BEGIN_NAMESPACE_STD 333 334template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 335 class _Alloc = allocator<_Value> > 336class _LIBCPP_TEMPLATE_VIS unordered_set 337{ 338public: 339 // types 340 typedef _Value key_type; 341 typedef key_type value_type; 342 typedef _Hash hasher; 343 typedef _Pred key_equal; 344 typedef _Alloc allocator_type; 345 typedef value_type& reference; 346 typedef const value_type& const_reference; 347 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 348 "Invalid allocator::value_type"); 349 350private: 351 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 352 353 __table __table_; 354 355public: 356 typedef typename __table::pointer pointer; 357 typedef typename __table::const_pointer const_pointer; 358 typedef typename __table::size_type size_type; 359 typedef typename __table::difference_type difference_type; 360 361 typedef typename __table::const_iterator iterator; 362 typedef typename __table::const_iterator const_iterator; 363 typedef typename __table::const_local_iterator local_iterator; 364 typedef typename __table::const_local_iterator const_local_iterator; 365 366 _LIBCPP_INLINE_VISIBILITY 367 unordered_set() 368 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 369 { 370#if _LIBCPP_DEBUG_LEVEL >= 2 371 __get_db()->__insert_c(this); 372#endif 373 } 374 explicit unordered_set(size_type __n, const hasher& __hf = hasher(), 375 const key_equal& __eql = key_equal()); 376#if _LIBCPP_STD_VER > 11 377 inline _LIBCPP_INLINE_VISIBILITY 378 unordered_set(size_type __n, const allocator_type& __a) 379 : unordered_set(__n, hasher(), key_equal(), __a) {} 380 inline _LIBCPP_INLINE_VISIBILITY 381 unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 382 : unordered_set(__n, __hf, key_equal(), __a) {} 383#endif 384 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, 385 const allocator_type& __a); 386 template <class _InputIterator> 387 unordered_set(_InputIterator __first, _InputIterator __last); 388 template <class _InputIterator> 389 unordered_set(_InputIterator __first, _InputIterator __last, 390 size_type __n, const hasher& __hf = hasher(), 391 const key_equal& __eql = key_equal()); 392 template <class _InputIterator> 393 unordered_set(_InputIterator __first, _InputIterator __last, 394 size_type __n, const hasher& __hf, const key_equal& __eql, 395 const allocator_type& __a); 396#if _LIBCPP_STD_VER > 11 397 template <class _InputIterator> 398 inline _LIBCPP_INLINE_VISIBILITY 399 unordered_set(_InputIterator __first, _InputIterator __last, 400 size_type __n, const allocator_type& __a) 401 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 402 template <class _InputIterator> 403 unordered_set(_InputIterator __first, _InputIterator __last, 404 size_type __n, const hasher& __hf, const allocator_type& __a) 405 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 406#endif 407 _LIBCPP_INLINE_VISIBILITY 408 explicit unordered_set(const allocator_type& __a); 409 unordered_set(const unordered_set& __u); 410 unordered_set(const unordered_set& __u, const allocator_type& __a); 411#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 412 _LIBCPP_INLINE_VISIBILITY 413 unordered_set(unordered_set&& __u) 414 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 415 unordered_set(unordered_set&& __u, const allocator_type& __a); 416#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 417#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 418 unordered_set(initializer_list<value_type> __il); 419 unordered_set(initializer_list<value_type> __il, size_type __n, 420 const hasher& __hf = hasher(), 421 const key_equal& __eql = key_equal()); 422 unordered_set(initializer_list<value_type> __il, size_type __n, 423 const hasher& __hf, const key_equal& __eql, 424 const allocator_type& __a); 425#if _LIBCPP_STD_VER > 11 426 inline _LIBCPP_INLINE_VISIBILITY 427 unordered_set(initializer_list<value_type> __il, size_type __n, 428 const allocator_type& __a) 429 : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 430 inline _LIBCPP_INLINE_VISIBILITY 431 unordered_set(initializer_list<value_type> __il, size_type __n, 432 const hasher& __hf, const allocator_type& __a) 433 : unordered_set(__il, __n, __hf, key_equal(), __a) {} 434#endif 435#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 436 // ~unordered_set() = default; 437 _LIBCPP_INLINE_VISIBILITY 438 unordered_set& operator=(const unordered_set& __u) 439 { 440 __table_ = __u.__table_; 441 return *this; 442 } 443#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 444 _LIBCPP_INLINE_VISIBILITY 445 unordered_set& operator=(unordered_set&& __u) 446 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 447#endif 448#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 449 _LIBCPP_INLINE_VISIBILITY 450 unordered_set& operator=(initializer_list<value_type> __il); 451#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 452 453 _LIBCPP_INLINE_VISIBILITY 454 allocator_type get_allocator() const _NOEXCEPT 455 {return allocator_type(__table_.__node_alloc());} 456 457 _LIBCPP_INLINE_VISIBILITY 458 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 459 _LIBCPP_INLINE_VISIBILITY 460 size_type size() const _NOEXCEPT {return __table_.size();} 461 _LIBCPP_INLINE_VISIBILITY 462 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 463 464 _LIBCPP_INLINE_VISIBILITY 465 iterator begin() _NOEXCEPT {return __table_.begin();} 466 _LIBCPP_INLINE_VISIBILITY 467 iterator end() _NOEXCEPT {return __table_.end();} 468 _LIBCPP_INLINE_VISIBILITY 469 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 470 _LIBCPP_INLINE_VISIBILITY 471 const_iterator end() const _NOEXCEPT {return __table_.end();} 472 _LIBCPP_INLINE_VISIBILITY 473 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 474 _LIBCPP_INLINE_VISIBILITY 475 const_iterator cend() const _NOEXCEPT {return __table_.end();} 476 477#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 478 template <class... _Args> 479 _LIBCPP_INLINE_VISIBILITY 480 pair<iterator, bool> emplace(_Args&&... __args) 481 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 482 template <class... _Args> 483 _LIBCPP_INLINE_VISIBILITY 484#if _LIBCPP_DEBUG_LEVEL >= 2 485 iterator emplace_hint(const_iterator __p, _Args&&... __args) 486 { 487 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 488 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not" 489 " referring to this unordered_set"); 490 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 491 } 492#else 493 iterator emplace_hint(const_iterator, _Args&&... __args) 494 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} 495#endif 496#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 497 _LIBCPP_INLINE_VISIBILITY 498 pair<iterator, bool> insert(const value_type& __x) 499 {return __table_.__insert_unique(__x);} 500#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 501 _LIBCPP_INLINE_VISIBILITY 502 pair<iterator, bool> insert(value_type&& __x) 503 {return __table_.__insert_unique(_VSTD::move(__x));} 504#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 505 _LIBCPP_INLINE_VISIBILITY 506#if _LIBCPP_DEBUG_LEVEL >= 2 507 iterator insert(const_iterator __p, const value_type& __x) 508 { 509 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 510 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not" 511 " referring to this unordered_set"); 512 return insert(__x).first; 513 } 514#else 515 iterator insert(const_iterator, const value_type& __x) 516 {return insert(__x).first;} 517#endif 518#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 519 _LIBCPP_INLINE_VISIBILITY 520#if _LIBCPP_DEBUG_LEVEL >= 2 521 iterator insert(const_iterator __p, value_type&& __x) 522 { 523 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 524 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not" 525 " referring to this unordered_set"); 526 return insert(_VSTD::move(__x)).first; 527 } 528#else 529 iterator insert(const_iterator, value_type&& __x) 530 {return insert(_VSTD::move(__x)).first;} 531#endif 532#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 533 template <class _InputIterator> 534 _LIBCPP_INLINE_VISIBILITY 535 void insert(_InputIterator __first, _InputIterator __last); 536#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 537 _LIBCPP_INLINE_VISIBILITY 538 void insert(initializer_list<value_type> __il) 539 {insert(__il.begin(), __il.end());} 540#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 541 542 _LIBCPP_INLINE_VISIBILITY 543 iterator erase(const_iterator __p) {return __table_.erase(__p);} 544 _LIBCPP_INLINE_VISIBILITY 545 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 546 _LIBCPP_INLINE_VISIBILITY 547 iterator erase(const_iterator __first, const_iterator __last) 548 {return __table_.erase(__first, __last);} 549 _LIBCPP_INLINE_VISIBILITY 550 void clear() _NOEXCEPT {__table_.clear();} 551 552 _LIBCPP_INLINE_VISIBILITY 553 void swap(unordered_set& __u) 554 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 555 {__table_.swap(__u.__table_);} 556 557 _LIBCPP_INLINE_VISIBILITY 558 hasher hash_function() const {return __table_.hash_function();} 559 _LIBCPP_INLINE_VISIBILITY 560 key_equal key_eq() const {return __table_.key_eq();} 561 562 _LIBCPP_INLINE_VISIBILITY 563 iterator find(const key_type& __k) {return __table_.find(__k);} 564 _LIBCPP_INLINE_VISIBILITY 565 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 566 _LIBCPP_INLINE_VISIBILITY 567 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 568 _LIBCPP_INLINE_VISIBILITY 569 pair<iterator, iterator> equal_range(const key_type& __k) 570 {return __table_.__equal_range_unique(__k);} 571 _LIBCPP_INLINE_VISIBILITY 572 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 573 {return __table_.__equal_range_unique(__k);} 574 575 _LIBCPP_INLINE_VISIBILITY 576 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 577 _LIBCPP_INLINE_VISIBILITY 578 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 579 580 _LIBCPP_INLINE_VISIBILITY 581 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 582 _LIBCPP_INLINE_VISIBILITY 583 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 584 585 _LIBCPP_INLINE_VISIBILITY 586 local_iterator begin(size_type __n) {return __table_.begin(__n);} 587 _LIBCPP_INLINE_VISIBILITY 588 local_iterator end(size_type __n) {return __table_.end(__n);} 589 _LIBCPP_INLINE_VISIBILITY 590 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 591 _LIBCPP_INLINE_VISIBILITY 592 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 593 _LIBCPP_INLINE_VISIBILITY 594 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 595 _LIBCPP_INLINE_VISIBILITY 596 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 597 598 _LIBCPP_INLINE_VISIBILITY 599 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 600 _LIBCPP_INLINE_VISIBILITY 601 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 602 _LIBCPP_INLINE_VISIBILITY 603 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 604 _LIBCPP_INLINE_VISIBILITY 605 void rehash(size_type __n) {__table_.rehash(__n);} 606 _LIBCPP_INLINE_VISIBILITY 607 void reserve(size_type __n) {__table_.reserve(__n);} 608 609#if _LIBCPP_DEBUG_LEVEL >= 2 610 611 bool __dereferenceable(const const_iterator* __i) const 612 {return __table_.__dereferenceable(__i);} 613 bool __decrementable(const const_iterator* __i) const 614 {return __table_.__decrementable(__i);} 615 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 616 {return __table_.__addable(__i, __n);} 617 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 618 {return __table_.__addable(__i, __n);} 619 620#endif // _LIBCPP_DEBUG_LEVEL >= 2 621 622}; 623 624template <class _Value, class _Hash, class _Pred, class _Alloc> 625unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 626 const hasher& __hf, const key_equal& __eql) 627 : __table_(__hf, __eql) 628{ 629#if _LIBCPP_DEBUG_LEVEL >= 2 630 __get_db()->__insert_c(this); 631#endif 632 __table_.rehash(__n); 633} 634 635template <class _Value, class _Hash, class _Pred, class _Alloc> 636unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 637 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 638 : __table_(__hf, __eql, __a) 639{ 640#if _LIBCPP_DEBUG_LEVEL >= 2 641 __get_db()->__insert_c(this); 642#endif 643 __table_.rehash(__n); 644} 645 646template <class _Value, class _Hash, class _Pred, class _Alloc> 647template <class _InputIterator> 648unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 649 _InputIterator __first, _InputIterator __last) 650{ 651#if _LIBCPP_DEBUG_LEVEL >= 2 652 __get_db()->__insert_c(this); 653#endif 654 insert(__first, __last); 655} 656 657template <class _Value, class _Hash, class _Pred, class _Alloc> 658template <class _InputIterator> 659unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 660 _InputIterator __first, _InputIterator __last, size_type __n, 661 const hasher& __hf, const key_equal& __eql) 662 : __table_(__hf, __eql) 663{ 664#if _LIBCPP_DEBUG_LEVEL >= 2 665 __get_db()->__insert_c(this); 666#endif 667 __table_.rehash(__n); 668 insert(__first, __last); 669} 670 671template <class _Value, class _Hash, class _Pred, class _Alloc> 672template <class _InputIterator> 673unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 674 _InputIterator __first, _InputIterator __last, size_type __n, 675 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 676 : __table_(__hf, __eql, __a) 677{ 678#if _LIBCPP_DEBUG_LEVEL >= 2 679 __get_db()->__insert_c(this); 680#endif 681 __table_.rehash(__n); 682 insert(__first, __last); 683} 684 685template <class _Value, class _Hash, class _Pred, class _Alloc> 686inline 687unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 688 const allocator_type& __a) 689 : __table_(__a) 690{ 691#if _LIBCPP_DEBUG_LEVEL >= 2 692 __get_db()->__insert_c(this); 693#endif 694} 695 696template <class _Value, class _Hash, class _Pred, class _Alloc> 697unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 698 const unordered_set& __u) 699 : __table_(__u.__table_) 700{ 701#if _LIBCPP_DEBUG_LEVEL >= 2 702 __get_db()->__insert_c(this); 703#endif 704 __table_.rehash(__u.bucket_count()); 705 insert(__u.begin(), __u.end()); 706} 707 708template <class _Value, class _Hash, class _Pred, class _Alloc> 709unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 710 const unordered_set& __u, const allocator_type& __a) 711 : __table_(__u.__table_, __a) 712{ 713#if _LIBCPP_DEBUG_LEVEL >= 2 714 __get_db()->__insert_c(this); 715#endif 716 __table_.rehash(__u.bucket_count()); 717 insert(__u.begin(), __u.end()); 718} 719 720#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 721 722template <class _Value, class _Hash, class _Pred, class _Alloc> 723inline 724unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 725 unordered_set&& __u) 726 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 727 : __table_(_VSTD::move(__u.__table_)) 728{ 729#if _LIBCPP_DEBUG_LEVEL >= 2 730 __get_db()->__insert_c(this); 731 __get_db()->swap(this, &__u); 732#endif 733} 734 735template <class _Value, class _Hash, class _Pred, class _Alloc> 736unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 737 unordered_set&& __u, const allocator_type& __a) 738 : __table_(_VSTD::move(__u.__table_), __a) 739{ 740#if _LIBCPP_DEBUG_LEVEL >= 2 741 __get_db()->__insert_c(this); 742#endif 743 if (__a != __u.get_allocator()) 744 { 745 iterator __i = __u.begin(); 746 while (__u.size() != 0) 747 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 748 } 749#if _LIBCPP_DEBUG_LEVEL >= 2 750 else 751 __get_db()->swap(this, &__u); 752#endif 753} 754 755#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 756 757#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 758 759template <class _Value, class _Hash, class _Pred, class _Alloc> 760unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 761 initializer_list<value_type> __il) 762{ 763#if _LIBCPP_DEBUG_LEVEL >= 2 764 __get_db()->__insert_c(this); 765#endif 766 insert(__il.begin(), __il.end()); 767} 768 769template <class _Value, class _Hash, class _Pred, class _Alloc> 770unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 771 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 772 const key_equal& __eql) 773 : __table_(__hf, __eql) 774{ 775#if _LIBCPP_DEBUG_LEVEL >= 2 776 __get_db()->__insert_c(this); 777#endif 778 __table_.rehash(__n); 779 insert(__il.begin(), __il.end()); 780} 781 782template <class _Value, class _Hash, class _Pred, class _Alloc> 783unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 784 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 785 const key_equal& __eql, const allocator_type& __a) 786 : __table_(__hf, __eql, __a) 787{ 788#if _LIBCPP_DEBUG_LEVEL >= 2 789 __get_db()->__insert_c(this); 790#endif 791 __table_.rehash(__n); 792 insert(__il.begin(), __il.end()); 793} 794 795#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 796 797#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 798 799template <class _Value, class _Hash, class _Pred, class _Alloc> 800inline 801unordered_set<_Value, _Hash, _Pred, _Alloc>& 802unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 803 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 804{ 805 __table_ = _VSTD::move(__u.__table_); 806 return *this; 807} 808 809#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 810 811#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 812 813template <class _Value, class _Hash, class _Pred, class _Alloc> 814inline 815unordered_set<_Value, _Hash, _Pred, _Alloc>& 816unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 817 initializer_list<value_type> __il) 818{ 819 __table_.__assign_unique(__il.begin(), __il.end()); 820 return *this; 821} 822 823#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 824 825template <class _Value, class _Hash, class _Pred, class _Alloc> 826template <class _InputIterator> 827inline 828void 829unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 830 _InputIterator __last) 831{ 832 for (; __first != __last; ++__first) 833 __table_.__insert_unique(*__first); 834} 835 836template <class _Value, class _Hash, class _Pred, class _Alloc> 837inline _LIBCPP_INLINE_VISIBILITY 838void 839swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 840 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 841 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 842{ 843 __x.swap(__y); 844} 845 846template <class _Value, class _Hash, class _Pred, class _Alloc> 847bool 848operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 849 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 850{ 851 if (__x.size() != __y.size()) 852 return false; 853 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 854 const_iterator; 855 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 856 __i != __ex; ++__i) 857 { 858 const_iterator __j = __y.find(*__i); 859 if (__j == __ey || !(*__i == *__j)) 860 return false; 861 } 862 return true; 863} 864 865template <class _Value, class _Hash, class _Pred, class _Alloc> 866inline _LIBCPP_INLINE_VISIBILITY 867bool 868operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 869 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 870{ 871 return !(__x == __y); 872} 873 874template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 875 class _Alloc = allocator<_Value> > 876class _LIBCPP_TEMPLATE_VIS unordered_multiset 877{ 878public: 879 // types 880 typedef _Value key_type; 881 typedef key_type value_type; 882 typedef _Hash hasher; 883 typedef _Pred key_equal; 884 typedef _Alloc allocator_type; 885 typedef value_type& reference; 886 typedef const value_type& const_reference; 887 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 888 "Invalid allocator::value_type"); 889 890private: 891 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 892 893 __table __table_; 894 895public: 896 typedef typename __table::pointer pointer; 897 typedef typename __table::const_pointer const_pointer; 898 typedef typename __table::size_type size_type; 899 typedef typename __table::difference_type difference_type; 900 901 typedef typename __table::const_iterator iterator; 902 typedef typename __table::const_iterator const_iterator; 903 typedef typename __table::const_local_iterator local_iterator; 904 typedef typename __table::const_local_iterator const_local_iterator; 905 906 _LIBCPP_INLINE_VISIBILITY 907 unordered_multiset() 908 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 909 { 910#if _LIBCPP_DEBUG_LEVEL >= 2 911 __get_db()->__insert_c(this); 912#endif 913 } 914 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), 915 const key_equal& __eql = key_equal()); 916 unordered_multiset(size_type __n, const hasher& __hf, 917 const key_equal& __eql, const allocator_type& __a); 918#if _LIBCPP_STD_VER > 11 919 inline _LIBCPP_INLINE_VISIBILITY 920 unordered_multiset(size_type __n, const allocator_type& __a) 921 : unordered_multiset(__n, hasher(), key_equal(), __a) {} 922 inline _LIBCPP_INLINE_VISIBILITY 923 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 924 : unordered_multiset(__n, __hf, key_equal(), __a) {} 925#endif 926 template <class _InputIterator> 927 unordered_multiset(_InputIterator __first, _InputIterator __last); 928 template <class _InputIterator> 929 unordered_multiset(_InputIterator __first, _InputIterator __last, 930 size_type __n, const hasher& __hf = hasher(), 931 const key_equal& __eql = key_equal()); 932 template <class _InputIterator> 933 unordered_multiset(_InputIterator __first, _InputIterator __last, 934 size_type __n , const hasher& __hf, 935 const key_equal& __eql, const allocator_type& __a); 936#if _LIBCPP_STD_VER > 11 937 template <class _InputIterator> 938 inline _LIBCPP_INLINE_VISIBILITY 939 unordered_multiset(_InputIterator __first, _InputIterator __last, 940 size_type __n, const allocator_type& __a) 941 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 942 template <class _InputIterator> 943 inline _LIBCPP_INLINE_VISIBILITY 944 unordered_multiset(_InputIterator __first, _InputIterator __last, 945 size_type __n, const hasher& __hf, const allocator_type& __a) 946 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 947#endif 948 _LIBCPP_INLINE_VISIBILITY 949 explicit unordered_multiset(const allocator_type& __a); 950 unordered_multiset(const unordered_multiset& __u); 951 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 952#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 953 _LIBCPP_INLINE_VISIBILITY 954 unordered_multiset(unordered_multiset&& __u) 955 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 956 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 957#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 958#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 959 unordered_multiset(initializer_list<value_type> __il); 960 unordered_multiset(initializer_list<value_type> __il, size_type __n, 961 const hasher& __hf = hasher(), 962 const key_equal& __eql = key_equal()); 963 unordered_multiset(initializer_list<value_type> __il, size_type __n, 964 const hasher& __hf, const key_equal& __eql, 965 const allocator_type& __a); 966#if _LIBCPP_STD_VER > 11 967 inline _LIBCPP_INLINE_VISIBILITY 968 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 969 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 970 inline _LIBCPP_INLINE_VISIBILITY 971 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 972 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 973#endif 974#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 975 // ~unordered_multiset() = default; 976 _LIBCPP_INLINE_VISIBILITY 977 unordered_multiset& operator=(const unordered_multiset& __u) 978 { 979 __table_ = __u.__table_; 980 return *this; 981 } 982#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 983 _LIBCPP_INLINE_VISIBILITY 984 unordered_multiset& operator=(unordered_multiset&& __u) 985 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 986#endif 987#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 988 unordered_multiset& operator=(initializer_list<value_type> __il); 989#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 990 991 _LIBCPP_INLINE_VISIBILITY 992 allocator_type get_allocator() const _NOEXCEPT 993 {return allocator_type(__table_.__node_alloc());} 994 995 _LIBCPP_INLINE_VISIBILITY 996 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 997 _LIBCPP_INLINE_VISIBILITY 998 size_type size() const _NOEXCEPT {return __table_.size();} 999 _LIBCPP_INLINE_VISIBILITY 1000 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1001 1002 _LIBCPP_INLINE_VISIBILITY 1003 iterator begin() _NOEXCEPT {return __table_.begin();} 1004 _LIBCPP_INLINE_VISIBILITY 1005 iterator end() _NOEXCEPT {return __table_.end();} 1006 _LIBCPP_INLINE_VISIBILITY 1007 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1008 _LIBCPP_INLINE_VISIBILITY 1009 const_iterator end() const _NOEXCEPT {return __table_.end();} 1010 _LIBCPP_INLINE_VISIBILITY 1011 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1012 _LIBCPP_INLINE_VISIBILITY 1013 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1014 1015#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1016 template <class... _Args> 1017 _LIBCPP_INLINE_VISIBILITY 1018 iterator emplace(_Args&&... __args) 1019 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1020 template <class... _Args> 1021 _LIBCPP_INLINE_VISIBILITY 1022 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1023 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1024#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1025 _LIBCPP_INLINE_VISIBILITY 1026 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1027#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1028 _LIBCPP_INLINE_VISIBILITY 1029 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 1030#endif 1031 _LIBCPP_INLINE_VISIBILITY 1032 iterator insert(const_iterator __p, const value_type& __x) 1033 {return __table_.__insert_multi(__p, __x);} 1034#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1035 _LIBCPP_INLINE_VISIBILITY 1036 iterator insert(const_iterator __p, value_type&& __x) 1037 {return __table_.__insert_multi(__p, _VSTD::move(__x));} 1038#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1039 template <class _InputIterator> 1040 _LIBCPP_INLINE_VISIBILITY 1041 void insert(_InputIterator __first, _InputIterator __last); 1042#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1043 _LIBCPP_INLINE_VISIBILITY 1044 void insert(initializer_list<value_type> __il) 1045 {insert(__il.begin(), __il.end());} 1046#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1047 1048 _LIBCPP_INLINE_VISIBILITY 1049 iterator erase(const_iterator __p) {return __table_.erase(__p);} 1050 _LIBCPP_INLINE_VISIBILITY 1051 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1052 _LIBCPP_INLINE_VISIBILITY 1053 iterator erase(const_iterator __first, const_iterator __last) 1054 {return __table_.erase(__first, __last);} 1055 _LIBCPP_INLINE_VISIBILITY 1056 void clear() _NOEXCEPT {__table_.clear();} 1057 1058 _LIBCPP_INLINE_VISIBILITY 1059 void swap(unordered_multiset& __u) 1060 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1061 {__table_.swap(__u.__table_);} 1062 1063 _LIBCPP_INLINE_VISIBILITY 1064 hasher hash_function() const {return __table_.hash_function();} 1065 _LIBCPP_INLINE_VISIBILITY 1066 key_equal key_eq() const {return __table_.key_eq();} 1067 1068 _LIBCPP_INLINE_VISIBILITY 1069 iterator find(const key_type& __k) {return __table_.find(__k);} 1070 _LIBCPP_INLINE_VISIBILITY 1071 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1072 _LIBCPP_INLINE_VISIBILITY 1073 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1074 _LIBCPP_INLINE_VISIBILITY 1075 pair<iterator, iterator> equal_range(const key_type& __k) 1076 {return __table_.__equal_range_multi(__k);} 1077 _LIBCPP_INLINE_VISIBILITY 1078 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1079 {return __table_.__equal_range_multi(__k);} 1080 1081 _LIBCPP_INLINE_VISIBILITY 1082 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1083 _LIBCPP_INLINE_VISIBILITY 1084 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 1085 1086 _LIBCPP_INLINE_VISIBILITY 1087 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 1088 _LIBCPP_INLINE_VISIBILITY 1089 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1090 1091 _LIBCPP_INLINE_VISIBILITY 1092 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1093 _LIBCPP_INLINE_VISIBILITY 1094 local_iterator end(size_type __n) {return __table_.end(__n);} 1095 _LIBCPP_INLINE_VISIBILITY 1096 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1097 _LIBCPP_INLINE_VISIBILITY 1098 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1099 _LIBCPP_INLINE_VISIBILITY 1100 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1101 _LIBCPP_INLINE_VISIBILITY 1102 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1103 1104 _LIBCPP_INLINE_VISIBILITY 1105 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1106 _LIBCPP_INLINE_VISIBILITY 1107 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1108 _LIBCPP_INLINE_VISIBILITY 1109 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1110 _LIBCPP_INLINE_VISIBILITY 1111 void rehash(size_type __n) {__table_.rehash(__n);} 1112 _LIBCPP_INLINE_VISIBILITY 1113 void reserve(size_type __n) {__table_.reserve(__n);} 1114 1115#if _LIBCPP_DEBUG_LEVEL >= 2 1116 1117 bool __dereferenceable(const const_iterator* __i) const 1118 {return __table_.__dereferenceable(__i);} 1119 bool __decrementable(const const_iterator* __i) const 1120 {return __table_.__decrementable(__i);} 1121 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1122 {return __table_.__addable(__i, __n);} 1123 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1124 {return __table_.__addable(__i, __n);} 1125 1126#endif // _LIBCPP_DEBUG_LEVEL >= 2 1127 1128}; 1129 1130template <class _Value, class _Hash, class _Pred, class _Alloc> 1131unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1132 size_type __n, const hasher& __hf, const key_equal& __eql) 1133 : __table_(__hf, __eql) 1134{ 1135#if _LIBCPP_DEBUG_LEVEL >= 2 1136 __get_db()->__insert_c(this); 1137#endif 1138 __table_.rehash(__n); 1139} 1140 1141template <class _Value, class _Hash, class _Pred, class _Alloc> 1142unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1143 size_type __n, const hasher& __hf, const key_equal& __eql, 1144 const allocator_type& __a) 1145 : __table_(__hf, __eql, __a) 1146{ 1147#if _LIBCPP_DEBUG_LEVEL >= 2 1148 __get_db()->__insert_c(this); 1149#endif 1150 __table_.rehash(__n); 1151} 1152 1153template <class _Value, class _Hash, class _Pred, class _Alloc> 1154template <class _InputIterator> 1155unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1156 _InputIterator __first, _InputIterator __last) 1157{ 1158#if _LIBCPP_DEBUG_LEVEL >= 2 1159 __get_db()->__insert_c(this); 1160#endif 1161 insert(__first, __last); 1162} 1163 1164template <class _Value, class _Hash, class _Pred, class _Alloc> 1165template <class _InputIterator> 1166unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1167 _InputIterator __first, _InputIterator __last, size_type __n, 1168 const hasher& __hf, const key_equal& __eql) 1169 : __table_(__hf, __eql) 1170{ 1171#if _LIBCPP_DEBUG_LEVEL >= 2 1172 __get_db()->__insert_c(this); 1173#endif 1174 __table_.rehash(__n); 1175 insert(__first, __last); 1176} 1177 1178template <class _Value, class _Hash, class _Pred, class _Alloc> 1179template <class _InputIterator> 1180unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1181 _InputIterator __first, _InputIterator __last, size_type __n, 1182 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1183 : __table_(__hf, __eql, __a) 1184{ 1185#if _LIBCPP_DEBUG_LEVEL >= 2 1186 __get_db()->__insert_c(this); 1187#endif 1188 __table_.rehash(__n); 1189 insert(__first, __last); 1190} 1191 1192template <class _Value, class _Hash, class _Pred, class _Alloc> 1193inline 1194unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1195 const allocator_type& __a) 1196 : __table_(__a) 1197{ 1198#if _LIBCPP_DEBUG_LEVEL >= 2 1199 __get_db()->__insert_c(this); 1200#endif 1201} 1202 1203template <class _Value, class _Hash, class _Pred, class _Alloc> 1204unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1205 const unordered_multiset& __u) 1206 : __table_(__u.__table_) 1207{ 1208#if _LIBCPP_DEBUG_LEVEL >= 2 1209 __get_db()->__insert_c(this); 1210#endif 1211 __table_.rehash(__u.bucket_count()); 1212 insert(__u.begin(), __u.end()); 1213} 1214 1215template <class _Value, class _Hash, class _Pred, class _Alloc> 1216unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1217 const unordered_multiset& __u, const allocator_type& __a) 1218 : __table_(__u.__table_, __a) 1219{ 1220#if _LIBCPP_DEBUG_LEVEL >= 2 1221 __get_db()->__insert_c(this); 1222#endif 1223 __table_.rehash(__u.bucket_count()); 1224 insert(__u.begin(), __u.end()); 1225} 1226 1227#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1228 1229template <class _Value, class _Hash, class _Pred, class _Alloc> 1230inline 1231unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1232 unordered_multiset&& __u) 1233 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1234 : __table_(_VSTD::move(__u.__table_)) 1235{ 1236#if _LIBCPP_DEBUG_LEVEL >= 2 1237 __get_db()->__insert_c(this); 1238 __get_db()->swap(this, &__u); 1239#endif 1240} 1241 1242template <class _Value, class _Hash, class _Pred, class _Alloc> 1243unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1244 unordered_multiset&& __u, const allocator_type& __a) 1245 : __table_(_VSTD::move(__u.__table_), __a) 1246{ 1247#if _LIBCPP_DEBUG_LEVEL >= 2 1248 __get_db()->__insert_c(this); 1249#endif 1250 if (__a != __u.get_allocator()) 1251 { 1252 iterator __i = __u.begin(); 1253 while (__u.size() != 0) 1254 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 1255 } 1256#if _LIBCPP_DEBUG_LEVEL >= 2 1257 else 1258 __get_db()->swap(this, &__u); 1259#endif 1260} 1261 1262#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1263 1264#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1265 1266template <class _Value, class _Hash, class _Pred, class _Alloc> 1267unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1268 initializer_list<value_type> __il) 1269{ 1270#if _LIBCPP_DEBUG_LEVEL >= 2 1271 __get_db()->__insert_c(this); 1272#endif 1273 insert(__il.begin(), __il.end()); 1274} 1275 1276template <class _Value, class _Hash, class _Pred, class _Alloc> 1277unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1278 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1279 const key_equal& __eql) 1280 : __table_(__hf, __eql) 1281{ 1282#if _LIBCPP_DEBUG_LEVEL >= 2 1283 __get_db()->__insert_c(this); 1284#endif 1285 __table_.rehash(__n); 1286 insert(__il.begin(), __il.end()); 1287} 1288 1289template <class _Value, class _Hash, class _Pred, class _Alloc> 1290unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1291 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1292 const key_equal& __eql, const allocator_type& __a) 1293 : __table_(__hf, __eql, __a) 1294{ 1295#if _LIBCPP_DEBUG_LEVEL >= 2 1296 __get_db()->__insert_c(this); 1297#endif 1298 __table_.rehash(__n); 1299 insert(__il.begin(), __il.end()); 1300} 1301 1302#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1303 1304#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1305 1306template <class _Value, class _Hash, class _Pred, class _Alloc> 1307inline 1308unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1309unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1310 unordered_multiset&& __u) 1311 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1312{ 1313 __table_ = _VSTD::move(__u.__table_); 1314 return *this; 1315} 1316 1317#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1318 1319#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1320 1321template <class _Value, class _Hash, class _Pred, class _Alloc> 1322inline 1323unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1324unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 1325 initializer_list<value_type> __il) 1326{ 1327 __table_.__assign_multi(__il.begin(), __il.end()); 1328 return *this; 1329} 1330 1331#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1332 1333template <class _Value, class _Hash, class _Pred, class _Alloc> 1334template <class _InputIterator> 1335inline 1336void 1337unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1338 _InputIterator __last) 1339{ 1340 for (; __first != __last; ++__first) 1341 __table_.__insert_multi(*__first); 1342} 1343 1344template <class _Value, class _Hash, class _Pred, class _Alloc> 1345inline _LIBCPP_INLINE_VISIBILITY 1346void 1347swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1348 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1349 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1350{ 1351 __x.swap(__y); 1352} 1353 1354template <class _Value, class _Hash, class _Pred, class _Alloc> 1355bool 1356operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1357 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1358{ 1359 if (__x.size() != __y.size()) 1360 return false; 1361 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 1362 const_iterator; 1363 typedef pair<const_iterator, const_iterator> _EqRng; 1364 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1365 { 1366 _EqRng __xeq = __x.equal_range(*__i); 1367 _EqRng __yeq = __y.equal_range(*__i); 1368 if (_VSTD::distance(__xeq.first, __xeq.second) != 1369 _VSTD::distance(__yeq.first, __yeq.second) || 1370 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1371 return false; 1372 __i = __xeq.second; 1373 } 1374 return true; 1375} 1376 1377template <class _Value, class _Hash, class _Pred, class _Alloc> 1378inline _LIBCPP_INLINE_VISIBILITY 1379bool 1380operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1381 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1382{ 1383 return !(__x == __y); 1384} 1385 1386_LIBCPP_END_NAMESPACE_STD 1387 1388#endif // _LIBCPP_UNORDERED_SET 1389