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