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