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