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