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 18 namespace __gnu_cxx 19 { 20 21 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 22 class Alloc = allocator<Value>> 23 class hash_set 24 { 25 public: 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 93 template <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 97 template <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 102 template <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 107 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 108 class Alloc = allocator<Value>> 109 class hash_multiset 110 { 111 public: 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 179 template <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 183 template <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 188 template <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 205 namespace __gnu_cxx { 206 207 using namespace std; 208 209 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 210 class _Alloc = allocator<_Value> > 211 class _LIBCPP_VISIBLE hash_set 212 { 213 public: 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 223 private: 224 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 225 226 __table __table_; 227 228 public: 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 326 template <class _Value, class _Hash, class _Pred, class _Alloc> 327 hash_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 334 template <class _Value, class _Hash, class _Pred, class _Alloc> 335 hash_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 342 template <class _Value, class _Hash, class _Pred, class _Alloc> 343 template <class _InputIterator> 344 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 345 _InputIterator __first, _InputIterator __last) 346 { 347 __table_.rehash(193); 348 insert(__first, __last); 349 } 350 351 template <class _Value, class _Hash, class _Pred, class _Alloc> 352 template <class _InputIterator> 353 hash_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 362 template <class _Value, class _Hash, class _Pred, class _Alloc> 363 template <class _InputIterator> 364 hash_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 373 template <class _Value, class _Hash, class _Pred, class _Alloc> 374 hash_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 382 template <class _Value, class _Hash, class _Pred, class _Alloc> 383 template <class _InputIterator> 384 inline _LIBCPP_INLINE_VISIBILITY 385 void 386 hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 387 _InputIterator __last) 388 { 389 for (; __first != __last; ++__first) 390 __table_.__insert_unique(*__first); 391 } 392 393 template <class _Value, class _Hash, class _Pred, class _Alloc> 394 inline _LIBCPP_INLINE_VISIBILITY 395 void 396 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 397 hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 398 { 399 __x.swap(__y); 400 } 401 402 template <class _Value, class _Hash, class _Pred, class _Alloc> 403 bool 404 operator==(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 421 template <class _Value, class _Hash, class _Pred, class _Alloc> 422 inline _LIBCPP_INLINE_VISIBILITY 423 bool 424 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 425 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 426 { 427 return !(__x == __y); 428 } 429 430 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 431 class _Alloc = allocator<_Value> > 432 class _LIBCPP_VISIBLE hash_multiset 433 { 434 public: 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 444 private: 445 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 446 447 __table __table_; 448 449 public: 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 546 template <class _Value, class _Hash, class _Pred, class _Alloc> 547 hash_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 554 template <class _Value, class _Hash, class _Pred, class _Alloc> 555 hash_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 563 template <class _Value, class _Hash, class _Pred, class _Alloc> 564 template <class _InputIterator> 565 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 566 _InputIterator __first, _InputIterator __last) 567 { 568 __table_.rehash(193); 569 insert(__first, __last); 570 } 571 572 template <class _Value, class _Hash, class _Pred, class _Alloc> 573 template <class _InputIterator> 574 hash_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 583 template <class _Value, class _Hash, class _Pred, class _Alloc> 584 template <class _InputIterator> 585 hash_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 594 template <class _Value, class _Hash, class _Pred, class _Alloc> 595 hash_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 603 template <class _Value, class _Hash, class _Pred, class _Alloc> 604 template <class _InputIterator> 605 inline _LIBCPP_INLINE_VISIBILITY 606 void 607 hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 608 _InputIterator __last) 609 { 610 for (; __first != __last; ++__first) 611 __table_.__insert_multi(*__first); 612 } 613 614 template <class _Value, class _Hash, class _Pred, class _Alloc> 615 inline _LIBCPP_INLINE_VISIBILITY 616 void 617 swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 618 hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 619 { 620 __x.swap(__y); 621 } 622 623 template <class _Value, class _Hash, class _Pred, class _Alloc> 624 bool 625 operator==(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 646 template <class _Value, class _Hash, class _Pred, class _Alloc> 647 inline _LIBCPP_INLINE_VISIBILITY 648 bool 649 operator!=(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
