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