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