1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_HASH_SET 11#define _LIBCPP_HASH_SET 12 13/* 14 15 hash_set synopsis 16 17namespace __gnu_cxx 18{ 19 20template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 21 class Alloc = allocator<Value>> 22class hash_set 23{ 24public: 25 // types 26 typedef Value key_type; 27 typedef key_type value_type; 28 typedef Hash hasher; 29 typedef Pred key_equal; 30 typedef Alloc allocator_type; 31 typedef value_type& reference; 32 typedef const value_type& const_reference; 33 typedef typename allocator_traits<allocator_type>::pointer pointer; 34 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 35 typedef typename allocator_traits<allocator_type>::size_type size_type; 36 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 37 38 typedef /unspecified/ iterator; 39 typedef /unspecified/ const_iterator; 40 41 explicit hash_set(size_type n = 193, const hasher& hf = hasher(), 42 const key_equal& eql = key_equal(), 43 const allocator_type& a = allocator_type()); 44 template <class InputIterator> 45 hash_set(InputIterator f, InputIterator l, 46 size_type n = 193, const hasher& hf = hasher(), 47 const key_equal& eql = key_equal(), 48 const allocator_type& a = allocator_type()); 49 hash_set(const hash_set&); 50 ~hash_set(); 51 hash_set& operator=(const hash_set&); 52 53 allocator_type get_allocator() const; 54 55 bool empty() const; 56 size_type size() const; 57 size_type max_size() const; 58 59 iterator begin(); 60 iterator end(); 61 const_iterator begin() const; 62 const_iterator end() const; 63 64 pair<iterator, bool> insert(const value_type& obj); 65 template <class InputIterator> 66 void insert(InputIterator first, InputIterator last); 67 68 void erase(const_iterator position); 69 size_type erase(const key_type& k); 70 void erase(const_iterator first, const_iterator last); 71 void clear(); 72 73 void swap(hash_set&); 74 75 hasher hash_funct() const; 76 key_equal key_eq() const; 77 78 iterator find(const key_type& k); 79 const_iterator find(const key_type& k) const; 80 size_type count(const key_type& k) const; 81 pair<iterator, iterator> equal_range(const key_type& k); 82 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 83 84 size_type bucket_count() const; 85 size_type max_bucket_count() const; 86 87 size_type elems_in_bucket(size_type n) const; 88 89 void resize(size_type n); 90}; 91 92template <class Value, class Hash, class Pred, class Alloc> 93 void swap(hash_set<Value, Hash, Pred, Alloc>& x, 94 hash_set<Value, Hash, Pred, Alloc>& y); 95 96template <class Value, class Hash, class Pred, class Alloc> 97 bool 98 operator==(const hash_set<Value, Hash, Pred, Alloc>& x, 99 const hash_set<Value, Hash, Pred, Alloc>& y); 100 101template <class Value, class Hash, class Pred, class Alloc> 102 bool 103 operator!=(const hash_set<Value, Hash, Pred, Alloc>& x, 104 const hash_set<Value, Hash, Pred, Alloc>& y); 105 106template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 107 class Alloc = allocator<Value>> 108class hash_multiset 109{ 110public: 111 // types 112 typedef Value key_type; 113 typedef key_type value_type; 114 typedef Hash hasher; 115 typedef Pred key_equal; 116 typedef Alloc allocator_type; 117 typedef value_type& reference; 118 typedef const value_type& const_reference; 119 typedef typename allocator_traits<allocator_type>::pointer pointer; 120 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 121 typedef typename allocator_traits<allocator_type>::size_type size_type; 122 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 123 124 typedef /unspecified/ iterator; 125 typedef /unspecified/ const_iterator; 126 127 explicit hash_multiset(size_type n = 193, const hasher& hf = hasher(), 128 const key_equal& eql = key_equal(), 129 const allocator_type& a = allocator_type()); 130 template <class InputIterator> 131 hash_multiset(InputIterator f, InputIterator l, 132 size_type n = 193, const hasher& hf = hasher(), 133 const key_equal& eql = key_equal(), 134 const allocator_type& a = allocator_type()); 135 hash_multiset(const hash_multiset&); 136 ~hash_multiset(); 137 hash_multiset& operator=(const hash_multiset&); 138 139 allocator_type get_allocator() const; 140 141 bool empty() const; 142 size_type size() const; 143 size_type max_size() const; 144 145 iterator begin(); 146 iterator end(); 147 const_iterator begin() const; 148 const_iterator end() const; 149 150 iterator insert(const value_type& obj); 151 template <class InputIterator> 152 void insert(InputIterator first, InputIterator last); 153 154 void erase(const_iterator position); 155 size_type erase(const key_type& k); 156 void erase(const_iterator first, const_iterator last); 157 void clear(); 158 159 void swap(hash_multiset&); 160 161 hasher hash_funct() const; 162 key_equal key_eq() const; 163 164 iterator find(const key_type& k); 165 const_iterator find(const key_type& k) const; 166 size_type count(const key_type& k) const; 167 pair<iterator, iterator> equal_range(const key_type& k); 168 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 169 170 size_type bucket_count() const; 171 size_type max_bucket_count() const; 172 173 size_type elems_in_bucket(size_type n) const; 174 175 void resize(size_type n); 176}; 177 178template <class Value, class Hash, class Pred, class Alloc> 179 void swap(hash_multiset<Value, Hash, Pred, Alloc>& x, 180 hash_multiset<Value, Hash, Pred, Alloc>& y); 181 182template <class Value, class Hash, class Pred, class Alloc> 183 bool 184 operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x, 185 const hash_multiset<Value, Hash, Pred, Alloc>& y); 186 187template <class Value, class Hash, class Pred, class Alloc> 188 bool 189 operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x, 190 const hash_multiset<Value, Hash, Pred, Alloc>& y); 191} // __gnu_cxx 192 193*/ 194 195#include <__assert> // all public C++ headers provide the assertion handler 196#include <__config> 197#include <__hash_table> 198#include <algorithm> 199#include <ext/__hash> 200#include <functional> 201 202#if defined(__DEPRECATED) && __DEPRECATED 203#if defined(_LIBCPP_WARNING) 204 _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>") 205#else 206# warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set> 207#endif 208#endif 209 210#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 211# pragma GCC system_header 212#endif 213 214namespace __gnu_cxx { 215 216 217template <class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>, 218 class _Alloc = std::allocator<_Value> > 219class _LIBCPP_TEMPLATE_VIS hash_set 220{ 221public: 222 // types 223 typedef _Value key_type; 224 typedef key_type value_type; 225 typedef _Hash hasher; 226 typedef _Pred key_equal; 227 typedef _Alloc allocator_type; 228 typedef value_type& reference; 229 typedef const value_type& const_reference; 230 231private: 232 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table; 233 234 __table __table_; 235 236public: 237 typedef typename __table::pointer pointer; 238 typedef typename __table::const_pointer const_pointer; 239 typedef typename __table::size_type size_type; 240 typedef typename __table::difference_type difference_type; 241 242 typedef typename __table::const_iterator iterator; 243 typedef typename __table::const_iterator const_iterator; 244 245 _LIBCPP_INLINE_VISIBILITY 246 hash_set() { } 247 _LIBCPP_HIDE_FROM_ABI explicit hash_set(size_type __n, const hasher& __hf = hasher(), 248 const key_equal& __eql = key_equal()); 249 _LIBCPP_HIDE_FROM_ABI hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 250 const allocator_type& __a); 251 template <class _InputIterator> 252 _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last); 253 template <class _InputIterator> 254 _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last, 255 size_type __n, const hasher& __hf = hasher(), 256 const key_equal& __eql = key_equal()); 257 template <class _InputIterator> 258 _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last, 259 size_type __n, const hasher& __hf, const key_equal& __eql, 260 const allocator_type& __a); 261 _LIBCPP_HIDE_FROM_ABI hash_set(const hash_set& __u); 262 263 _LIBCPP_INLINE_VISIBILITY 264 allocator_type get_allocator() const 265 {return allocator_type(__table_.__node_alloc());} 266 267 _LIBCPP_INLINE_VISIBILITY 268 bool empty() const {return __table_.size() == 0;} 269 _LIBCPP_INLINE_VISIBILITY 270 size_type size() const {return __table_.size();} 271 _LIBCPP_INLINE_VISIBILITY 272 size_type max_size() const {return __table_.max_size();} 273 274 _LIBCPP_INLINE_VISIBILITY 275 iterator begin() {return __table_.begin();} 276 _LIBCPP_INLINE_VISIBILITY 277 iterator end() {return __table_.end();} 278 _LIBCPP_INLINE_VISIBILITY 279 const_iterator begin() const {return __table_.begin();} 280 _LIBCPP_INLINE_VISIBILITY 281 const_iterator end() const {return __table_.end();} 282 283 _LIBCPP_INLINE_VISIBILITY 284 std::pair<iterator, bool> insert(const value_type& __x) 285 {return __table_.__insert_unique(__x);} 286 _LIBCPP_INLINE_VISIBILITY 287 iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} 288 template <class _InputIterator> 289 _LIBCPP_INLINE_VISIBILITY 290 void insert(_InputIterator __first, _InputIterator __last); 291 292 _LIBCPP_INLINE_VISIBILITY 293 void erase(const_iterator __p) {__table_.erase(__p);} 294 _LIBCPP_INLINE_VISIBILITY 295 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 296 _LIBCPP_INLINE_VISIBILITY 297 void erase(const_iterator __first, const_iterator __last) 298 {__table_.erase(__first, __last);} 299 _LIBCPP_INLINE_VISIBILITY 300 void clear() {__table_.clear();} 301 302 _LIBCPP_INLINE_VISIBILITY 303 void swap(hash_set& __u) {__table_.swap(__u.__table_);} 304 305 _LIBCPP_INLINE_VISIBILITY 306 hasher hash_funct() const {return __table_.hash_function();} 307 _LIBCPP_INLINE_VISIBILITY 308 key_equal key_eq() const {return __table_.key_eq();} 309 310 _LIBCPP_INLINE_VISIBILITY 311 iterator find(const key_type& __k) {return __table_.find(__k);} 312 _LIBCPP_INLINE_VISIBILITY 313 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 314 _LIBCPP_INLINE_VISIBILITY 315 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 316 _LIBCPP_INLINE_VISIBILITY 317 std::pair<iterator, iterator> equal_range(const key_type& __k) 318 {return __table_.__equal_range_unique(__k);} 319 _LIBCPP_INLINE_VISIBILITY 320 std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 321 {return __table_.__equal_range_unique(__k);} 322 323 _LIBCPP_INLINE_VISIBILITY 324 size_type bucket_count() const {return __table_.bucket_count();} 325 _LIBCPP_INLINE_VISIBILITY 326 size_type max_bucket_count() const {return __table_.max_bucket_count();} 327 328 _LIBCPP_INLINE_VISIBILITY 329 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 330 331 _LIBCPP_INLINE_VISIBILITY 332 void resize(size_type __n) {__table_.__rehash_unique(__n);} 333}; 334 335template <class _Value, class _Hash, class _Pred, class _Alloc> 336hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, 337 const hasher& __hf, const key_equal& __eql) 338 : __table_(__hf, __eql) 339{ 340 __table_.__rehash_unique(__n); 341} 342 343template <class _Value, class _Hash, class _Pred, class _Alloc> 344hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, 345 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 346 : __table_(__hf, __eql, __a) 347{ 348 __table_.__rehash_unique(__n); 349} 350 351template <class _Value, class _Hash, class _Pred, class _Alloc> 352template <class _InputIterator> 353hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 354 _InputIterator __first, _InputIterator __last) 355{ 356 insert(__first, __last); 357} 358 359template <class _Value, class _Hash, class _Pred, class _Alloc> 360template <class _InputIterator> 361hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 362 _InputIterator __first, _InputIterator __last, size_type __n, 363 const hasher& __hf, const key_equal& __eql) 364 : __table_(__hf, __eql) 365{ 366 __table_.__rehash_unique(__n); 367 insert(__first, __last); 368} 369 370template <class _Value, class _Hash, class _Pred, class _Alloc> 371template <class _InputIterator> 372hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 373 _InputIterator __first, _InputIterator __last, size_type __n, 374 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 375 : __table_(__hf, __eql, __a) 376{ 377 __table_.__rehash_unique(__n); 378 insert(__first, __last); 379} 380 381template <class _Value, class _Hash, class _Pred, class _Alloc> 382hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 383 const hash_set& __u) 384 : __table_(__u.__table_) 385{ 386 __table_.__rehash_unique(__u.bucket_count()); 387 insert(__u.begin(), __u.end()); 388} 389 390template <class _Value, class _Hash, class _Pred, class _Alloc> 391template <class _InputIterator> 392inline 393void 394hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 395 _InputIterator __last) 396{ 397 for (; __first != __last; ++__first) 398 __table_.__insert_unique(*__first); 399} 400 401template <class _Value, class _Hash, class _Pred, class _Alloc> 402inline _LIBCPP_INLINE_VISIBILITY 403void 404swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 405 hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 406{ 407 __x.swap(__y); 408} 409 410template <class _Value, class _Hash, class _Pred, class _Alloc> 411_LIBCPP_HIDE_FROM_ABI bool 412operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 413 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 414{ 415 if (__x.size() != __y.size()) 416 return false; 417 typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 418 const_iterator; 419 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 420 __i != __ex; ++__i) 421 { 422 const_iterator __j = __y.find(*__i); 423 if (__j == __ey || !(*__i == *__j)) 424 return false; 425 } 426 return true; 427} 428 429template <class _Value, class _Hash, class _Pred, class _Alloc> 430inline _LIBCPP_INLINE_VISIBILITY 431bool 432operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 433 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 434{ 435 return !(__x == __y); 436} 437 438template <class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>, 439 class _Alloc = std::allocator<_Value> > 440class _LIBCPP_TEMPLATE_VIS hash_multiset 441{ 442public: 443 // types 444 typedef _Value key_type; 445 typedef key_type value_type; 446 typedef _Hash hasher; 447 typedef _Pred key_equal; 448 typedef _Alloc allocator_type; 449 typedef value_type& reference; 450 typedef const value_type& const_reference; 451 452private: 453 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table; 454 455 __table __table_; 456 457public: 458 typedef typename __table::pointer pointer; 459 typedef typename __table::const_pointer const_pointer; 460 typedef typename __table::size_type size_type; 461 typedef typename __table::difference_type difference_type; 462 463 typedef typename __table::const_iterator iterator; 464 typedef typename __table::const_iterator const_iterator; 465 466 _LIBCPP_INLINE_VISIBILITY 467 hash_multiset() { } 468 explicit _LIBCPP_HIDE_FROM_ABI hash_multiset(size_type __n, const hasher& __hf = hasher(), 469 const key_equal& __eql = key_equal()); 470 _LIBCPP_HIDE_FROM_ABI hash_multiset(size_type __n, const hasher& __hf, 471 const key_equal& __eql, const allocator_type& __a); 472 template <class _InputIterator> 473 _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last); 474 template <class _InputIterator> 475 _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last, 476 size_type __n, const hasher& __hf = hasher(), 477 const key_equal& __eql = key_equal()); 478 template <class _InputIterator> 479 _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last, 480 size_type __n , const hasher& __hf, 481 const key_equal& __eql, const allocator_type& __a); 482 _LIBCPP_HIDE_FROM_ABI hash_multiset(const hash_multiset& __u); 483 484 _LIBCPP_INLINE_VISIBILITY 485 allocator_type get_allocator() const 486 {return allocator_type(__table_.__node_alloc());} 487 488 _LIBCPP_INLINE_VISIBILITY 489 bool empty() const {return __table_.size() == 0;} 490 _LIBCPP_INLINE_VISIBILITY 491 size_type size() const {return __table_.size();} 492 _LIBCPP_INLINE_VISIBILITY 493 size_type max_size() const {return __table_.max_size();} 494 495 _LIBCPP_INLINE_VISIBILITY 496 iterator begin() {return __table_.begin();} 497 _LIBCPP_INLINE_VISIBILITY 498 iterator end() {return __table_.end();} 499 _LIBCPP_INLINE_VISIBILITY 500 const_iterator begin() const {return __table_.begin();} 501 _LIBCPP_INLINE_VISIBILITY 502 const_iterator end() const {return __table_.end();} 503 504 _LIBCPP_INLINE_VISIBILITY 505 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 506 _LIBCPP_INLINE_VISIBILITY 507 iterator insert(const_iterator, const value_type& __x) {return insert(__x);} 508 template <class _InputIterator> 509 _LIBCPP_INLINE_VISIBILITY 510 void insert(_InputIterator __first, _InputIterator __last); 511 512 _LIBCPP_INLINE_VISIBILITY 513 void erase(const_iterator __p) {__table_.erase(__p);} 514 _LIBCPP_INLINE_VISIBILITY 515 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 516 _LIBCPP_INLINE_VISIBILITY 517 void erase(const_iterator __first, const_iterator __last) 518 {__table_.erase(__first, __last);} 519 _LIBCPP_INLINE_VISIBILITY 520 void clear() {__table_.clear();} 521 522 _LIBCPP_INLINE_VISIBILITY 523 void swap(hash_multiset& __u) {__table_.swap(__u.__table_);} 524 525 _LIBCPP_INLINE_VISIBILITY 526 hasher hash_funct() const {return __table_.hash_function();} 527 _LIBCPP_INLINE_VISIBILITY 528 key_equal key_eq() const {return __table_.key_eq();} 529 530 _LIBCPP_INLINE_VISIBILITY 531 iterator find(const key_type& __k) {return __table_.find(__k);} 532 _LIBCPP_INLINE_VISIBILITY 533 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 534 _LIBCPP_INLINE_VISIBILITY 535 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 536 _LIBCPP_INLINE_VISIBILITY 537 std::pair<iterator, iterator> equal_range(const key_type& __k) 538 {return __table_.__equal_range_multi(__k);} 539 _LIBCPP_INLINE_VISIBILITY 540 std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 541 {return __table_.__equal_range_multi(__k);} 542 543 _LIBCPP_INLINE_VISIBILITY 544 size_type bucket_count() const {return __table_.bucket_count();} 545 _LIBCPP_INLINE_VISIBILITY 546 size_type max_bucket_count() const {return __table_.max_bucket_count();} 547 548 _LIBCPP_INLINE_VISIBILITY 549 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 550 551 _LIBCPP_INLINE_VISIBILITY 552 void resize(size_type __n) {__table_.__rehash_multi(__n);} 553}; 554 555template <class _Value, class _Hash, class _Pred, class _Alloc> 556hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 557 size_type __n, const hasher& __hf, const key_equal& __eql) 558 : __table_(__hf, __eql) 559{ 560 __table_.__rehash_multi(__n); 561} 562 563template <class _Value, class _Hash, class _Pred, class _Alloc> 564hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 565 size_type __n, const hasher& __hf, const key_equal& __eql, 566 const allocator_type& __a) 567 : __table_(__hf, __eql, __a) 568{ 569 __table_.__rehash_multi(__n); 570} 571 572template <class _Value, class _Hash, class _Pred, class _Alloc> 573template <class _InputIterator> 574hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 575 _InputIterator __first, _InputIterator __last) 576{ 577 insert(__first, __last); 578} 579 580template <class _Value, class _Hash, class _Pred, class _Alloc> 581template <class _InputIterator> 582hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 583 _InputIterator __first, _InputIterator __last, size_type __n, 584 const hasher& __hf, const key_equal& __eql) 585 : __table_(__hf, __eql) 586{ 587 __table_.__rehash_multi(__n); 588 insert(__first, __last); 589} 590 591template <class _Value, class _Hash, class _Pred, class _Alloc> 592template <class _InputIterator> 593hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 594 _InputIterator __first, _InputIterator __last, size_type __n, 595 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 596 : __table_(__hf, __eql, __a) 597{ 598 __table_.__rehash_multi(__n); 599 insert(__first, __last); 600} 601 602template <class _Value, class _Hash, class _Pred, class _Alloc> 603hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 604 const hash_multiset& __u) 605 : __table_(__u.__table_) 606{ 607 __table_.__rehash_multi(__u.bucket_count()); 608 insert(__u.begin(), __u.end()); 609} 610 611template <class _Value, class _Hash, class _Pred, class _Alloc> 612template <class _InputIterator> 613inline 614void 615hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 616 _InputIterator __last) 617{ 618 for (; __first != __last; ++__first) 619 __table_.__insert_multi(*__first); 620} 621 622template <class _Value, class _Hash, class _Pred, class _Alloc> 623inline _LIBCPP_INLINE_VISIBILITY 624void 625swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 626 hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 627{ 628 __x.swap(__y); 629} 630 631template <class _Value, class _Hash, class _Pred, class _Alloc> 632_LIBCPP_HIDE_FROM_ABI bool 633operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 634 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 635{ 636 if (__x.size() != __y.size()) 637 return false; 638 typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 639 const_iterator; 640 typedef std::pair<const_iterator, const_iterator> _EqRng; 641 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 642 { 643 _EqRng __xeq = __x.equal_range(*__i); 644 _EqRng __yeq = __y.equal_range(*__i); 645 if (_VSTD::distance(__xeq.first, __xeq.second) != 646 _VSTD::distance(__yeq.first, __yeq.second) || 647 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 648 return false; 649 __i = __xeq.second; 650 } 651 return true; 652} 653 654template <class _Value, class _Hash, class _Pred, class _Alloc> 655inline _LIBCPP_INLINE_VISIBILITY 656bool 657operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 658 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 659{ 660 return !(__x == __y); 661} 662 663} // namespace __gnu_cxx 664 665#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 666# include <concepts> 667# include <iterator> 668# include <type_traits> 669#endif 670 671#endif // _LIBCPP_HASH_SET 672