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 <__config> 196#include <__hash_table> 197#include <ext/__hash> 198#include <functional> 199 200#if defined(__DEPRECATED) && __DEPRECATED 201#if defined(_LIBCPP_WARNING) 202 _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>") 203#else 204# warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set> 205#endif 206#endif 207 208#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 209#pragma GCC system_header 210#endif 211 212namespace __gnu_cxx { 213 214 215template <class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>, 216 class _Alloc = std::allocator<_Value> > 217class _LIBCPP_TEMPLATE_VIS hash_set 218{ 219public: 220 // types 221 typedef _Value key_type; 222 typedef key_type value_type; 223 typedef _Hash hasher; 224 typedef _Pred key_equal; 225 typedef _Alloc allocator_type; 226 typedef value_type& reference; 227 typedef const value_type& const_reference; 228 229private: 230 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table; 231 232 __table __table_; 233 234public: 235 typedef typename __table::pointer pointer; 236 typedef typename __table::const_pointer const_pointer; 237 typedef typename __table::size_type size_type; 238 typedef typename __table::difference_type difference_type; 239 240 typedef typename __table::const_iterator iterator; 241 typedef typename __table::const_iterator const_iterator; 242 243 _LIBCPP_INLINE_VISIBILITY 244 hash_set() { } 245 explicit hash_set(size_type __n, const hasher& __hf = hasher(), 246 const key_equal& __eql = key_equal()); 247 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 248 const allocator_type& __a); 249 template <class _InputIterator> 250 hash_set(_InputIterator __first, _InputIterator __last); 251 template <class _InputIterator> 252 hash_set(_InputIterator __first, _InputIterator __last, 253 size_type __n, const hasher& __hf = hasher(), 254 const key_equal& __eql = key_equal()); 255 template <class _InputIterator> 256 hash_set(_InputIterator __first, _InputIterator __last, 257 size_type __n, const hasher& __hf, const key_equal& __eql, 258 const allocator_type& __a); 259 hash_set(const hash_set& __u); 260 261 _LIBCPP_INLINE_VISIBILITY 262 allocator_type get_allocator() const 263 {return allocator_type(__table_.__node_alloc());} 264 265 _LIBCPP_INLINE_VISIBILITY 266 bool empty() const {return __table_.size() == 0;} 267 _LIBCPP_INLINE_VISIBILITY 268 size_type size() const {return __table_.size();} 269 _LIBCPP_INLINE_VISIBILITY 270 size_type max_size() const {return __table_.max_size();} 271 272 _LIBCPP_INLINE_VISIBILITY 273 iterator begin() {return __table_.begin();} 274 _LIBCPP_INLINE_VISIBILITY 275 iterator end() {return __table_.end();} 276 _LIBCPP_INLINE_VISIBILITY 277 const_iterator begin() const {return __table_.begin();} 278 _LIBCPP_INLINE_VISIBILITY 279 const_iterator end() const {return __table_.end();} 280 281 _LIBCPP_INLINE_VISIBILITY 282 std::pair<iterator, bool> insert(const value_type& __x) 283 {return __table_.__insert_unique(__x);} 284 _LIBCPP_INLINE_VISIBILITY 285 iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} 286 template <class _InputIterator> 287 _LIBCPP_INLINE_VISIBILITY 288 void insert(_InputIterator __first, _InputIterator __last); 289 290 _LIBCPP_INLINE_VISIBILITY 291 void erase(const_iterator __p) {__table_.erase(__p);} 292 _LIBCPP_INLINE_VISIBILITY 293 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 294 _LIBCPP_INLINE_VISIBILITY 295 void erase(const_iterator __first, const_iterator __last) 296 {__table_.erase(__first, __last);} 297 _LIBCPP_INLINE_VISIBILITY 298 void clear() {__table_.clear();} 299 300 _LIBCPP_INLINE_VISIBILITY 301 void swap(hash_set& __u) {__table_.swap(__u.__table_);} 302 303 _LIBCPP_INLINE_VISIBILITY 304 hasher hash_funct() const {return __table_.hash_function();} 305 _LIBCPP_INLINE_VISIBILITY 306 key_equal key_eq() const {return __table_.key_eq();} 307 308 _LIBCPP_INLINE_VISIBILITY 309 iterator find(const key_type& __k) {return __table_.find(__k);} 310 _LIBCPP_INLINE_VISIBILITY 311 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 312 _LIBCPP_INLINE_VISIBILITY 313 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 314 _LIBCPP_INLINE_VISIBILITY 315 std::pair<iterator, iterator> equal_range(const key_type& __k) 316 {return __table_.__equal_range_unique(__k);} 317 _LIBCPP_INLINE_VISIBILITY 318 std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 319 {return __table_.__equal_range_unique(__k);} 320 321 _LIBCPP_INLINE_VISIBILITY 322 size_type bucket_count() const {return __table_.bucket_count();} 323 _LIBCPP_INLINE_VISIBILITY 324 size_type max_bucket_count() const {return __table_.max_bucket_count();} 325 326 _LIBCPP_INLINE_VISIBILITY 327 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 328 329 _LIBCPP_INLINE_VISIBILITY 330 void resize(size_type __n) {__table_.rehash(__n);} 331}; 332 333template <class _Value, class _Hash, class _Pred, class _Alloc> 334hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, 335 const hasher& __hf, const key_equal& __eql) 336 : __table_(__hf, __eql) 337{ 338 __table_.rehash(__n); 339} 340 341template <class _Value, class _Hash, class _Pred, class _Alloc> 342hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, 343 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 344 : __table_(__hf, __eql, __a) 345{ 346 __table_.rehash(__n); 347} 348 349template <class _Value, class _Hash, class _Pred, class _Alloc> 350template <class _InputIterator> 351hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 352 _InputIterator __first, _InputIterator __last) 353{ 354 insert(__first, __last); 355} 356 357template <class _Value, class _Hash, class _Pred, class _Alloc> 358template <class _InputIterator> 359hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 360 _InputIterator __first, _InputIterator __last, size_type __n, 361 const hasher& __hf, const key_equal& __eql) 362 : __table_(__hf, __eql) 363{ 364 __table_.rehash(__n); 365 insert(__first, __last); 366} 367 368template <class _Value, class _Hash, class _Pred, class _Alloc> 369template <class _InputIterator> 370hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 371 _InputIterator __first, _InputIterator __last, size_type __n, 372 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 373 : __table_(__hf, __eql, __a) 374{ 375 __table_.rehash(__n); 376 insert(__first, __last); 377} 378 379template <class _Value, class _Hash, class _Pred, class _Alloc> 380hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 381 const hash_set& __u) 382 : __table_(__u.__table_) 383{ 384 __table_.rehash(__u.bucket_count()); 385 insert(__u.begin(), __u.end()); 386} 387 388template <class _Value, class _Hash, class _Pred, class _Alloc> 389template <class _InputIterator> 390inline 391void 392hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 393 _InputIterator __last) 394{ 395 for (; __first != __last; ++__first) 396 __table_.__insert_unique(*__first); 397} 398 399template <class _Value, class _Hash, class _Pred, class _Alloc> 400inline _LIBCPP_INLINE_VISIBILITY 401void 402swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 403 hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 404{ 405 __x.swap(__y); 406} 407 408template <class _Value, class _Hash, class _Pred, class _Alloc> 409bool 410operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 411 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 412{ 413 if (__x.size() != __y.size()) 414 return false; 415 typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 416 const_iterator; 417 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 418 __i != __ex; ++__i) 419 { 420 const_iterator __j = __y.find(*__i); 421 if (__j == __ey || !(*__i == *__j)) 422 return false; 423 } 424 return true; 425} 426 427template <class _Value, class _Hash, class _Pred, class _Alloc> 428inline _LIBCPP_INLINE_VISIBILITY 429bool 430operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 431 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 432{ 433 return !(__x == __y); 434} 435 436template <class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>, 437 class _Alloc = std::allocator<_Value> > 438class _LIBCPP_TEMPLATE_VIS hash_multiset 439{ 440public: 441 // types 442 typedef _Value key_type; 443 typedef key_type value_type; 444 typedef _Hash hasher; 445 typedef _Pred key_equal; 446 typedef _Alloc allocator_type; 447 typedef value_type& reference; 448 typedef const value_type& const_reference; 449 450private: 451 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table; 452 453 __table __table_; 454 455public: 456 typedef typename __table::pointer pointer; 457 typedef typename __table::const_pointer const_pointer; 458 typedef typename __table::size_type size_type; 459 typedef typename __table::difference_type difference_type; 460 461 typedef typename __table::const_iterator iterator; 462 typedef typename __table::const_iterator const_iterator; 463 464 _LIBCPP_INLINE_VISIBILITY 465 hash_multiset() { } 466 explicit hash_multiset(size_type __n, const hasher& __hf = hasher(), 467 const key_equal& __eql = key_equal()); 468 hash_multiset(size_type __n, const hasher& __hf, 469 const key_equal& __eql, const allocator_type& __a); 470 template <class _InputIterator> 471 hash_multiset(_InputIterator __first, _InputIterator __last); 472 template <class _InputIterator> 473 hash_multiset(_InputIterator __first, _InputIterator __last, 474 size_type __n, const hasher& __hf = hasher(), 475 const key_equal& __eql = key_equal()); 476 template <class _InputIterator> 477 hash_multiset(_InputIterator __first, _InputIterator __last, 478 size_type __n , const hasher& __hf, 479 const key_equal& __eql, const allocator_type& __a); 480 hash_multiset(const hash_multiset& __u); 481 482 _LIBCPP_INLINE_VISIBILITY 483 allocator_type get_allocator() const 484 {return allocator_type(__table_.__node_alloc());} 485 486 _LIBCPP_INLINE_VISIBILITY 487 bool empty() const {return __table_.size() == 0;} 488 _LIBCPP_INLINE_VISIBILITY 489 size_type size() const {return __table_.size();} 490 _LIBCPP_INLINE_VISIBILITY 491 size_type max_size() const {return __table_.max_size();} 492 493 _LIBCPP_INLINE_VISIBILITY 494 iterator begin() {return __table_.begin();} 495 _LIBCPP_INLINE_VISIBILITY 496 iterator end() {return __table_.end();} 497 _LIBCPP_INLINE_VISIBILITY 498 const_iterator begin() const {return __table_.begin();} 499 _LIBCPP_INLINE_VISIBILITY 500 const_iterator end() const {return __table_.end();} 501 502 _LIBCPP_INLINE_VISIBILITY 503 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 504 _LIBCPP_INLINE_VISIBILITY 505 iterator insert(const_iterator, const value_type& __x) {return insert(__x);} 506 template <class _InputIterator> 507 _LIBCPP_INLINE_VISIBILITY 508 void insert(_InputIterator __first, _InputIterator __last); 509 510 _LIBCPP_INLINE_VISIBILITY 511 void erase(const_iterator __p) {__table_.erase(__p);} 512 _LIBCPP_INLINE_VISIBILITY 513 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 514 _LIBCPP_INLINE_VISIBILITY 515 void erase(const_iterator __first, const_iterator __last) 516 {__table_.erase(__first, __last);} 517 _LIBCPP_INLINE_VISIBILITY 518 void clear() {__table_.clear();} 519 520 _LIBCPP_INLINE_VISIBILITY 521 void swap(hash_multiset& __u) {__table_.swap(__u.__table_);} 522 523 _LIBCPP_INLINE_VISIBILITY 524 hasher hash_funct() const {return __table_.hash_function();} 525 _LIBCPP_INLINE_VISIBILITY 526 key_equal key_eq() const {return __table_.key_eq();} 527 528 _LIBCPP_INLINE_VISIBILITY 529 iterator find(const key_type& __k) {return __table_.find(__k);} 530 _LIBCPP_INLINE_VISIBILITY 531 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 532 _LIBCPP_INLINE_VISIBILITY 533 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 534 _LIBCPP_INLINE_VISIBILITY 535 std::pair<iterator, iterator> equal_range(const key_type& __k) 536 {return __table_.__equal_range_multi(__k);} 537 _LIBCPP_INLINE_VISIBILITY 538 std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 539 {return __table_.__equal_range_multi(__k);} 540 541 _LIBCPP_INLINE_VISIBILITY 542 size_type bucket_count() const {return __table_.bucket_count();} 543 _LIBCPP_INLINE_VISIBILITY 544 size_type max_bucket_count() const {return __table_.max_bucket_count();} 545 546 _LIBCPP_INLINE_VISIBILITY 547 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 548 549 _LIBCPP_INLINE_VISIBILITY 550 void resize(size_type __n) {__table_.rehash(__n);} 551}; 552 553template <class _Value, class _Hash, class _Pred, class _Alloc> 554hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 555 size_type __n, const hasher& __hf, const key_equal& __eql) 556 : __table_(__hf, __eql) 557{ 558 __table_.rehash(__n); 559} 560 561template <class _Value, class _Hash, class _Pred, class _Alloc> 562hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 563 size_type __n, const hasher& __hf, const key_equal& __eql, 564 const allocator_type& __a) 565 : __table_(__hf, __eql, __a) 566{ 567 __table_.rehash(__n); 568} 569 570template <class _Value, class _Hash, class _Pred, class _Alloc> 571template <class _InputIterator> 572hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 573 _InputIterator __first, _InputIterator __last) 574{ 575 insert(__first, __last); 576} 577 578template <class _Value, class _Hash, class _Pred, class _Alloc> 579template <class _InputIterator> 580hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 581 _InputIterator __first, _InputIterator __last, size_type __n, 582 const hasher& __hf, const key_equal& __eql) 583 : __table_(__hf, __eql) 584{ 585 __table_.rehash(__n); 586 insert(__first, __last); 587} 588 589template <class _Value, class _Hash, class _Pred, class _Alloc> 590template <class _InputIterator> 591hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 592 _InputIterator __first, _InputIterator __last, size_type __n, 593 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 594 : __table_(__hf, __eql, __a) 595{ 596 __table_.rehash(__n); 597 insert(__first, __last); 598} 599 600template <class _Value, class _Hash, class _Pred, class _Alloc> 601hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 602 const hash_multiset& __u) 603 : __table_(__u.__table_) 604{ 605 __table_.rehash(__u.bucket_count()); 606 insert(__u.begin(), __u.end()); 607} 608 609template <class _Value, class _Hash, class _Pred, class _Alloc> 610template <class _InputIterator> 611inline 612void 613hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 614 _InputIterator __last) 615{ 616 for (; __first != __last; ++__first) 617 __table_.__insert_multi(*__first); 618} 619 620template <class _Value, class _Hash, class _Pred, class _Alloc> 621inline _LIBCPP_INLINE_VISIBILITY 622void 623swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 624 hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 625{ 626 __x.swap(__y); 627} 628 629template <class _Value, class _Hash, class _Pred, class _Alloc> 630bool 631operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 632 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 633{ 634 if (__x.size() != __y.size()) 635 return false; 636 typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 637 const_iterator; 638 typedef std::pair<const_iterator, const_iterator> _EqRng; 639 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 640 { 641 _EqRng __xeq = __x.equal_range(*__i); 642 _EqRng __yeq = __y.equal_range(*__i); 643 if (_VSTD::distance(__xeq.first, __xeq.second) != 644 _VSTD::distance(__yeq.first, __yeq.second) || 645 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 646 return false; 647 __i = __xeq.second; 648 } 649 return true; 650} 651 652template <class _Value, class _Hash, class _Pred, class _Alloc> 653inline _LIBCPP_INLINE_VISIBILITY 654bool 655operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 656 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 657{ 658 return !(__x == __y); 659} 660 661} // namespace __gnu_cxx 662 663#endif // _LIBCPP_HASH_SET 664