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