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 #if defined(_MSC_VER) && ! defined(__clang__) 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 209 namespace __gnu_cxx { 210 211 using namespace std; 212 213 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 214 class _Alloc = allocator<_Value> > 215 class _LIBCPP_TYPE_VIS_ONLY hash_set 216 { 217 public: 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 227 private: 228 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 229 230 __table __table_; 231 232 public: 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 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 330 template <class _Value, class _Hash, class _Pred, class _Alloc> 331 hash_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 338 template <class _Value, class _Hash, class _Pred, class _Alloc> 339 hash_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 346 template <class _Value, class _Hash, class _Pred, class _Alloc> 347 template <class _InputIterator> 348 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( 349 _InputIterator __first, _InputIterator __last) 350 { 351 __table_.rehash(193); 352 insert(__first, __last); 353 } 354 355 template <class _Value, class _Hash, class _Pred, class _Alloc> 356 template <class _InputIterator> 357 hash_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 366 template <class _Value, class _Hash, class _Pred, class _Alloc> 367 template <class _InputIterator> 368 hash_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 377 template <class _Value, class _Hash, class _Pred, class _Alloc> 378 hash_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 386 template <class _Value, class _Hash, class _Pred, class _Alloc> 387 template <class _InputIterator> 388 inline _LIBCPP_INLINE_VISIBILITY 389 void 390 hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 391 _InputIterator __last) 392 { 393 for (; __first != __last; ++__first) 394 __table_.__insert_unique(*__first); 395 } 396 397 template <class _Value, class _Hash, class _Pred, class _Alloc> 398 inline _LIBCPP_INLINE_VISIBILITY 399 void 400 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 401 hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 402 { 403 __x.swap(__y); 404 } 405 406 template <class _Value, class _Hash, class _Pred, class _Alloc> 407 bool 408 operator==(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 425 template <class _Value, class _Hash, class _Pred, class _Alloc> 426 inline _LIBCPP_INLINE_VISIBILITY 427 bool 428 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, 429 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) 430 { 431 return !(__x == __y); 432 } 433 434 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 435 class _Alloc = allocator<_Value> > 436 class _LIBCPP_TYPE_VIS_ONLY hash_multiset 437 { 438 public: 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 448 private: 449 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 450 451 __table __table_; 452 453 public: 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 void insert(_InputIterator __first, _InputIterator __last); 506 507 _LIBCPP_INLINE_VISIBILITY 508 void erase(const_iterator __p) {__table_.erase(__p);} 509 _LIBCPP_INLINE_VISIBILITY 510 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 511 _LIBCPP_INLINE_VISIBILITY 512 void erase(const_iterator __first, const_iterator __last) 513 {__table_.erase(__first, __last);} 514 _LIBCPP_INLINE_VISIBILITY 515 void clear() {__table_.clear();} 516 517 _LIBCPP_INLINE_VISIBILITY 518 void swap(hash_multiset& __u) {__table_.swap(__u.__table_);} 519 520 _LIBCPP_INLINE_VISIBILITY 521 hasher hash_funct() const {return __table_.hash_function();} 522 _LIBCPP_INLINE_VISIBILITY 523 key_equal key_eq() const {return __table_.key_eq();} 524 525 _LIBCPP_INLINE_VISIBILITY 526 iterator find(const key_type& __k) {return __table_.find(__k);} 527 _LIBCPP_INLINE_VISIBILITY 528 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 529 _LIBCPP_INLINE_VISIBILITY 530 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 531 _LIBCPP_INLINE_VISIBILITY 532 pair<iterator, iterator> equal_range(const key_type& __k) 533 {return __table_.__equal_range_multi(__k);} 534 _LIBCPP_INLINE_VISIBILITY 535 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 536 {return __table_.__equal_range_multi(__k);} 537 538 _LIBCPP_INLINE_VISIBILITY 539 size_type bucket_count() const {return __table_.bucket_count();} 540 _LIBCPP_INLINE_VISIBILITY 541 size_type max_bucket_count() const {return __table_.max_bucket_count();} 542 543 _LIBCPP_INLINE_VISIBILITY 544 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);} 545 546 _LIBCPP_INLINE_VISIBILITY 547 void resize(size_type __n) {__table_.rehash(__n);} 548 }; 549 550 template <class _Value, class _Hash, class _Pred, class _Alloc> 551 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 552 size_type __n, const hasher& __hf, const key_equal& __eql) 553 : __table_(__hf, __eql) 554 { 555 __table_.rehash(__n); 556 } 557 558 template <class _Value, class _Hash, class _Pred, class _Alloc> 559 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 560 size_type __n, const hasher& __hf, const key_equal& __eql, 561 const allocator_type& __a) 562 : __table_(__hf, __eql, __a) 563 { 564 __table_.rehash(__n); 565 } 566 567 template <class _Value, class _Hash, class _Pred, class _Alloc> 568 template <class _InputIterator> 569 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 570 _InputIterator __first, _InputIterator __last) 571 { 572 __table_.rehash(193); 573 insert(__first, __last); 574 } 575 576 template <class _Value, class _Hash, class _Pred, class _Alloc> 577 template <class _InputIterator> 578 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 579 _InputIterator __first, _InputIterator __last, size_type __n, 580 const hasher& __hf, const key_equal& __eql) 581 : __table_(__hf, __eql) 582 { 583 __table_.rehash(__n); 584 insert(__first, __last); 585 } 586 587 template <class _Value, class _Hash, class _Pred, class _Alloc> 588 template <class _InputIterator> 589 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 590 _InputIterator __first, _InputIterator __last, size_type __n, 591 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 592 : __table_(__hf, __eql, __a) 593 { 594 __table_.rehash(__n); 595 insert(__first, __last); 596 } 597 598 template <class _Value, class _Hash, class _Pred, class _Alloc> 599 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( 600 const hash_multiset& __u) 601 : __table_(__u.__table_) 602 { 603 __table_.rehash(__u.bucket_count()); 604 insert(__u.begin(), __u.end()); 605 } 606 607 template <class _Value, class _Hash, class _Pred, class _Alloc> 608 template <class _InputIterator> 609 inline _LIBCPP_INLINE_VISIBILITY 610 void 611 hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 612 _InputIterator __last) 613 { 614 for (; __first != __last; ++__first) 615 __table_.__insert_multi(*__first); 616 } 617 618 template <class _Value, class _Hash, class _Pred, class _Alloc> 619 inline _LIBCPP_INLINE_VISIBILITY 620 void 621 swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 622 hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 623 { 624 __x.swap(__y); 625 } 626 627 template <class _Value, class _Hash, class _Pred, class _Alloc> 628 bool 629 operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 630 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 631 { 632 if (__x.size() != __y.size()) 633 return false; 634 typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 635 const_iterator; 636 typedef pair<const_iterator, const_iterator> _EqRng; 637 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 638 { 639 _EqRng __xeq = __x.equal_range(*__i); 640 _EqRng __yeq = __y.equal_range(*__i); 641 if (_VSTD::distance(__xeq.first, __xeq.second) != 642 _VSTD::distance(__yeq.first, __yeq.second) || 643 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 644 return false; 645 __i = __xeq.second; 646 } 647 return true; 648 } 649 650 template <class _Value, class _Hash, class _Pred, class _Alloc> 651 inline _LIBCPP_INLINE_VISIBILITY 652 bool 653 operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 654 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 655 { 656 return !(__x == __y); 657 } 658 659 } // __gnu_cxx 660 661 #endif // _LIBCPP_HASH_SET 662
