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