1// -*- C++ -*- 2//===------------------------- hash_set ------------------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is dual licensed under the MIT and the University of Illinois Open 7// Source Licenses. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP_HASH_SET 12#define _LIBCPP_HASH_SET 13 14/* 15 16 hash_set synopsis 17 18namespace __gnu_cxx 19{ 20 21template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 22 class Alloc = allocator<Value>> 23class hash_set 24{ 25public: 26 // types 27 typedef Value key_type; 28 typedef key_type value_type; 29 typedef Hash hasher; 30 typedef Pred key_equal; 31 typedef Alloc allocator_type; 32 typedef value_type& reference; 33 typedef const value_type& const_reference; 34 typedef typename allocator_traits<allocator_type>::pointer pointer; 35 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 36 typedef typename allocator_traits<allocator_type>::size_type size_type; 37 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 38 39 typedef /unspecified/ iterator; 40 typedef /unspecified/ const_iterator; 41 42 explicit hash_set(size_type n = 193, const hasher& hf = hasher(), 43 const key_equal& eql = key_equal(), 44 const allocator_type& a = allocator_type()); 45 template <class InputIterator> 46 hash_set(InputIterator f, InputIterator l, 47 size_type n = 193, const hasher& hf = hasher(), 48 const key_equal& eql = key_equal(), 49 const allocator_type& a = allocator_type()); 50 hash_set(const hash_set&); 51 ~hash_set(); 52 hash_set& operator=(const hash_set&); 53 54 allocator_type get_allocator() const; 55 56 bool empty() const; 57 size_type size() const; 58 size_type max_size() const; 59 60 iterator begin(); 61 iterator end(); 62 const_iterator begin() const; 63 const_iterator end() const; 64 65 pair<iterator, bool> insert(const value_type& obj); 66 template <class InputIterator> 67 void insert(InputIterator first, InputIterator last); 68 69 void erase(const_iterator position); 70 size_type erase(const key_type& k); 71 void erase(const_iterator first, const_iterator last); 72 void clear(); 73 74 void swap(hash_set&); 75 76 hasher hash_funct() const; 77 key_equal key_eq() const; 78 79 iterator find(const key_type& k); 80 const_iterator find(const key_type& k) const; 81 size_type count(const key_type& k) const; 82 pair<iterator, iterator> equal_range(const key_type& k); 83 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 84 85 size_type bucket_count() const; 86 size_type max_bucket_count() const; 87 88 size_type elems_in_bucket(size_type n) const; 89 90 void resize(size_type n); 91}; 92 93template <class Value, class Hash, class Pred, class Alloc> 94 void swap(hash_set<Value, Hash, Pred, Alloc>& x, 95 hash_set<Value, Hash, Pred, Alloc>& y); 96 97template <class Value, class Hash, class Pred, class Alloc> 98 bool 99 operator==(const hash_set<Value, Hash, Pred, Alloc>& x, 100 const hash_set<Value, Hash, Pred, Alloc>& y); 101 102template <class Value, class Hash, class Pred, class Alloc> 103 bool 104 operator!=(const hash_set<Value, Hash, Pred, Alloc>& x, 105 const hash_set<Value, Hash, Pred, Alloc>& y); 106 107template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 108 class Alloc = allocator<Value>> 109class hash_multiset 110{ 111public: 112 // types 113 typedef Value key_type; 114 typedef key_type value_type; 115 typedef Hash hasher; 116 typedef Pred key_equal; 117 typedef Alloc allocator_type; 118 typedef value_type& reference; 119 typedef const value_type& const_reference; 120 typedef typename allocator_traits<allocator_type>::pointer pointer; 121 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 122 typedef typename allocator_traits<allocator_type>::size_type size_type; 123 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 124 125 typedef /unspecified/ iterator; 126 typedef /unspecified/ const_iterator; 127 128 explicit hash_multiset(size_type n = 193, const hasher& hf = hasher(), 129 const key_equal& eql = key_equal(), 130 const allocator_type& a = allocator_type()); 131 template <class InputIterator> 132 hash_multiset(InputIterator f, InputIterator l, 133 size_type n = 193, const hasher& hf = hasher(), 134 const key_equal& eql = key_equal(), 135 const allocator_type& a = allocator_type()); 136 hash_multiset(const hash_multiset&); 137 ~hash_multiset(); 138 hash_multiset& operator=(const hash_multiset&); 139 140 allocator_type get_allocator() const; 141 142 bool empty() const; 143 size_type size() const; 144 size_type max_size() const; 145 146 iterator begin(); 147 iterator end(); 148 const_iterator begin() const; 149 const_iterator end() const; 150 151 iterator insert(const value_type& obj); 152 template <class InputIterator> 153 void insert(InputIterator first, InputIterator last); 154 155 void erase(const_iterator position); 156 size_type erase(const key_type& k); 157 void erase(const_iterator first, const_iterator last); 158 void clear(); 159 160 void swap(hash_multiset&); 161 162 hasher hash_funct() const; 163 key_equal key_eq() const; 164 165 iterator find(const key_type& k); 166 const_iterator find(const key_type& k) const; 167 size_type count(const key_type& k) const; 168 pair<iterator, iterator> equal_range(const key_type& k); 169 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 170 171 size_type bucket_count() const; 172 size_type max_bucket_count() const; 173 174 size_type elems_in_bucket(size_type n) const; 175 176 void resize(size_type n); 177}; 178 179template <class Value, class Hash, class Pred, class Alloc> 180 void swap(hash_multiset<Value, Hash, Pred, Alloc>& x, 181 hash_multiset<Value, Hash, Pred, Alloc>& y); 182 183template <class Value, class Hash, class Pred, class Alloc> 184 bool 185 operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x, 186 const hash_multiset<Value, Hash, Pred, Alloc>& y); 187 188template <class Value, class Hash, class Pred, class Alloc> 189 bool 190 operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x, 191 const hash_multiset<Value, Hash, Pred, Alloc>& y); 192} // __gnu_cxx 193 194*/ 195 196#include <__config> 197#include <__hash_table> 198#include <functional> 199#include <ext/__hash> 200 201#if __DEPRECATED 202#if defined(_LIBCPP_MSVC) 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 209namespace __gnu_cxx { 210 211using namespace std; 212 213template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 214 class _Alloc = allocator<_Value> > 215class _LIBCPP_TEMPLATE_VIS hash_set 216{ 217public: 218 // types 219 typedef _Value key_type; 220 typedef key_type value_type; 221 typedef _Hash hasher; 222 typedef _Pred key_equal; 223 typedef _Alloc allocator_type; 224 typedef value_type& reference; 225 typedef const value_type& const_reference; 226 227private: 228 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 229 230 __table __table_; 231 232public: 233 typedef typename __table::pointer pointer; 234 typedef typename __table::const_pointer const_pointer; 235 typedef typename __table::size_type size_type; 236 typedef typename __table::difference_type difference_type; 237 238 typedef typename __table::const_iterator iterator; 239 typedef typename __table::const_iterator const_iterator; 240 241 _LIBCPP_INLINE_VISIBILITY 242 hash_set() {__table_.rehash(193);} 243 explicit hash_set(size_type __n, const hasher& __hf = hasher(), 244 const key_equal& __eql = key_equal()); 245 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 246 const allocator_type& __a); 247 template <class _InputIterator> 248 hash_set(_InputIterator __first, _InputIterator __last); 249 template <class _InputIterator> 250 hash_set(_InputIterator __first, _InputIterator __last, 251 size_type __n, const hasher& __hf = hasher(), 252 const key_equal& __eql = key_equal()); 253 template <class _InputIterator> 254 hash_set(_InputIterator __first, _InputIterator __last, 255 size_type __n, const hasher& __hf, const key_equal& __eql, 256 const allocator_type& __a); 257 hash_set(const hash_set& __u); 258 259 _LIBCPP_INLINE_VISIBILITY 260 allocator_type get_allocator() const 261 {return allocator_type(__table_.__node_alloc());} 262 263 _LIBCPP_INLINE_VISIBILITY 264 bool empty() const {return __table_.size() == 0;} 265 _LIBCPP_INLINE_VISIBILITY 266 size_type size() const {return __table_.size();} 267 _LIBCPP_INLINE_VISIBILITY 268 size_type max_size() const {return __table_.max_size();} 269 270 _LIBCPP_INLINE_VISIBILITY 271 iterator begin() {return __table_.begin();} 272 _LIBCPP_INLINE_VISIBILITY 273 iterator end() {return __table_.end();} 274 _LIBCPP_INLINE_VISIBILITY 275 const_iterator begin() const {return __table_.begin();} 276 _LIBCPP_INLINE_VISIBILITY 277 const_iterator end() const {return __table_.end();} 278 279 _LIBCPP_INLINE_VISIBILITY 280 pair<iterator, bool> insert(const value_type& __x) 281 {return __table_.__insert_unique(__x);} 282 _LIBCPP_INLINE_VISIBILITY 283 iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} 284 template <class _InputIterator> 285 _LIBCPP_INLINE_VISIBILITY 286 void insert(_InputIterator __first, _InputIterator __last); 287 288 _LIBCPP_INLINE_VISIBILITY 289 void erase(const_iterator __p) {__table_.erase(__p);} 290 _LIBCPP_INLINE_VISIBILITY 291 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 292 _LIBCPP_INLINE_VISIBILITY 293 void erase(const_iterator __first, const_iterator __last) 294 {__table_.erase(__first, __last);} 295 _LIBCPP_INLINE_VISIBILITY 296 void clear() {__table_.clear();} 297 298 _LIBCPP_INLINE_VISIBILITY 299 void swap(hash_set& __u) {__table_.swap(__u.__table_);} 300 301 _LIBCPP_INLINE_VISIBILITY 302 hasher hash_funct() const {return __table_.hash_function();} 303 _LIBCPP_INLINE_VISIBILITY 304 key_equal key_eq() const {return __table_.key_eq();} 305 306 _LIBCPP_INLINE_VISIBILITY 307 iterator find(const key_type& __k) {return __table_.find(__k);} 308 _LIBCPP_INLINE_VISIBILITY 309 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 310 _LIBCPP_INLINE_VISIBILITY 311 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 312 _LIBCPP_INLINE_VISIBILITY 313 pair<iterator, iterator> equal_range(const key_type& __k) 314 {return __table_.__equal_range_unique(__k);} 315 _LIBCPP_INLINE_VISIBILITY 316 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 317 {return __table_.__equal_range_unique(__k);} 318 319 _LIBCPP_INLINE_VISIBILITY 320 size_type bucket_count() const {return __table_.bucket_count();} 321 _LIBCPP_INLINE_VISIBILITY 322 size_type max_bucket_count() const {return __table_.max_bucket_count();} 323 324 _LIBCPP_INLINE_VISIBILITY 325 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 326 327 _LIBCPP_INLINE_VISIBILITY 328 void resize(size_type __n) {__table_.rehash(__n);} 329}; 330 331template <class _Value, class _Hash, class _Pred, class _Alloc> 332hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, 333 const hasher& __hf, const key_equal& __eql) 334 : __table_(__hf, __eql) 335{ 336 __table_.rehash(__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, const allocator_type& __a) 342 : __table_(__hf, __eql, __a) 343{ 344 __table_.rehash(__n); 345} 346 347template <class _Value, class _Hash, class _Pred, class _Alloc> 348template <class _InputIterator> 349hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 350 _InputIterator __first, _InputIterator __last) 351{ 352 __table_.rehash(193); 353 insert(__first, __last); 354} 355 356template <class _Value, class _Hash, class _Pred, class _Alloc> 357template <class _InputIterator> 358hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 359 _InputIterator __first, _InputIterator __last, size_type __n, 360 const hasher& __hf, const key_equal& __eql) 361 : __table_(__hf, __eql) 362{ 363 __table_.rehash(__n); 364 insert(__first, __last); 365} 366 367template <class _Value, class _Hash, class _Pred, class _Alloc> 368template <class _InputIterator> 369hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 370 _InputIterator __first, _InputIterator __last, size_type __n, 371 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 372 : __table_(__hf, __eql, __a) 373{ 374 __table_.rehash(__n); 375 insert(__first, __last); 376} 377 378template <class _Value, class _Hash, class _Pred, class _Alloc> 379hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 380 const hash_set& __u) 381 : __table_(__u.__table_) 382{ 383 __table_.rehash(__u.bucket_count()); 384 insert(__u.begin(), __u.end()); 385} 386 387template <class _Value, class _Hash, class _Pred, class _Alloc> 388template <class _InputIterator> 389inline 390void 391hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 392 _InputIterator __last) 393{ 394 for (; __first != __last; ++__first) 395 __table_.__insert_unique(*__first); 396} 397 398template <class _Value, class _Hash, class _Pred, class _Alloc> 399inline _LIBCPP_INLINE_VISIBILITY 400void 401swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 402 hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 403{ 404 __x.swap(__y); 405} 406 407template <class _Value, class _Hash, class _Pred, class _Alloc> 408bool 409operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 410 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 411{ 412 if (__x.size() != __y.size()) 413 return false; 414 typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 415 const_iterator; 416 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 417 __i != __ex; ++__i) 418 { 419 const_iterator __j = __y.find(*__i); 420 if (__j == __ey || !(*__i == *__j)) 421 return false; 422 } 423 return true; 424} 425 426template <class _Value, class _Hash, class _Pred, class _Alloc> 427inline _LIBCPP_INLINE_VISIBILITY 428bool 429operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 430 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 431{ 432 return !(__x == __y); 433} 434 435template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 436 class _Alloc = allocator<_Value> > 437class _LIBCPP_TEMPLATE_VIS hash_multiset 438{ 439public: 440 // types 441 typedef _Value key_type; 442 typedef key_type value_type; 443 typedef _Hash hasher; 444 typedef _Pred key_equal; 445 typedef _Alloc allocator_type; 446 typedef value_type& reference; 447 typedef const value_type& const_reference; 448 449private: 450 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 451 452 __table __table_; 453 454public: 455 typedef typename __table::pointer pointer; 456 typedef typename __table::const_pointer const_pointer; 457 typedef typename __table::size_type size_type; 458 typedef typename __table::difference_type difference_type; 459 460 typedef typename __table::const_iterator iterator; 461 typedef typename __table::const_iterator const_iterator; 462 463 _LIBCPP_INLINE_VISIBILITY 464 hash_multiset() {__table_.rehash(193);} 465 explicit hash_multiset(size_type __n, const hasher& __hf = hasher(), 466 const key_equal& __eql = key_equal()); 467 hash_multiset(size_type __n, const hasher& __hf, 468 const key_equal& __eql, const allocator_type& __a); 469 template <class _InputIterator> 470 hash_multiset(_InputIterator __first, _InputIterator __last); 471 template <class _InputIterator> 472 hash_multiset(_InputIterator __first, _InputIterator __last, 473 size_type __n, const hasher& __hf = hasher(), 474 const key_equal& __eql = key_equal()); 475 template <class _InputIterator> 476 hash_multiset(_InputIterator __first, _InputIterator __last, 477 size_type __n , const hasher& __hf, 478 const key_equal& __eql, const allocator_type& __a); 479 hash_multiset(const hash_multiset& __u); 480 481 _LIBCPP_INLINE_VISIBILITY 482 allocator_type get_allocator() const 483 {return allocator_type(__table_.__node_alloc());} 484 485 _LIBCPP_INLINE_VISIBILITY 486 bool empty() const {return __table_.size() == 0;} 487 _LIBCPP_INLINE_VISIBILITY 488 size_type size() const {return __table_.size();} 489 _LIBCPP_INLINE_VISIBILITY 490 size_type max_size() const {return __table_.max_size();} 491 492 _LIBCPP_INLINE_VISIBILITY 493 iterator begin() {return __table_.begin();} 494 _LIBCPP_INLINE_VISIBILITY 495 iterator end() {return __table_.end();} 496 _LIBCPP_INLINE_VISIBILITY 497 const_iterator begin() const {return __table_.begin();} 498 _LIBCPP_INLINE_VISIBILITY 499 const_iterator end() const {return __table_.end();} 500 501 _LIBCPP_INLINE_VISIBILITY 502 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 503 _LIBCPP_INLINE_VISIBILITY 504 iterator insert(const_iterator, const value_type& __x) {return insert(__x);} 505 template <class _InputIterator> 506 _LIBCPP_INLINE_VISIBILITY 507 void insert(_InputIterator __first, _InputIterator __last); 508 509 _LIBCPP_INLINE_VISIBILITY 510 void erase(const_iterator __p) {__table_.erase(__p);} 511 _LIBCPP_INLINE_VISIBILITY 512 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 513 _LIBCPP_INLINE_VISIBILITY 514 void erase(const_iterator __first, const_iterator __last) 515 {__table_.erase(__first, __last);} 516 _LIBCPP_INLINE_VISIBILITY 517 void clear() {__table_.clear();} 518 519 _LIBCPP_INLINE_VISIBILITY 520 void swap(hash_multiset& __u) {__table_.swap(__u.__table_);} 521 522 _LIBCPP_INLINE_VISIBILITY 523 hasher hash_funct() const {return __table_.hash_function();} 524 _LIBCPP_INLINE_VISIBILITY 525 key_equal key_eq() const {return __table_.key_eq();} 526 527 _LIBCPP_INLINE_VISIBILITY 528 iterator find(const key_type& __k) {return __table_.find(__k);} 529 _LIBCPP_INLINE_VISIBILITY 530 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 531 _LIBCPP_INLINE_VISIBILITY 532 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 533 _LIBCPP_INLINE_VISIBILITY 534 pair<iterator, iterator> equal_range(const key_type& __k) 535 {return __table_.__equal_range_multi(__k);} 536 _LIBCPP_INLINE_VISIBILITY 537 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 538 {return __table_.__equal_range_multi(__k);} 539 540 _LIBCPP_INLINE_VISIBILITY 541 size_type bucket_count() const {return __table_.bucket_count();} 542 _LIBCPP_INLINE_VISIBILITY 543 size_type max_bucket_count() const {return __table_.max_bucket_count();} 544 545 _LIBCPP_INLINE_VISIBILITY 546 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 547 548 _LIBCPP_INLINE_VISIBILITY 549 void resize(size_type __n) {__table_.rehash(__n);} 550}; 551 552template <class _Value, class _Hash, class _Pred, class _Alloc> 553hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 554 size_type __n, const hasher& __hf, const key_equal& __eql) 555 : __table_(__hf, __eql) 556{ 557 __table_.rehash(__n); 558} 559 560template <class _Value, class _Hash, class _Pred, class _Alloc> 561hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 562 size_type __n, const hasher& __hf, const key_equal& __eql, 563 const allocator_type& __a) 564 : __table_(__hf, __eql, __a) 565{ 566 __table_.rehash(__n); 567} 568 569template <class _Value, class _Hash, class _Pred, class _Alloc> 570template <class _InputIterator> 571hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 572 _InputIterator __first, _InputIterator __last) 573{ 574 __table_.rehash(193); 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 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} // __gnu_cxx 662 663#endif // _LIBCPP_HASH_SET 664