Warning, /include/c++/v1/ext/hash_set is written in an unsupported language. File is not indexed.
0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP_HASH_SET
0011 #define _LIBCPP_HASH_SET
0012
0013 /*
0014
0015 hash_set synopsis
0016
0017 namespace __gnu_cxx
0018 {
0019
0020 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
0021 class Alloc = allocator<Value>>
0022 class hash_set
0023 {
0024 public:
0025 // types
0026 typedef Value key_type;
0027 typedef key_type value_type;
0028 typedef Hash hasher;
0029 typedef Pred key_equal;
0030 typedef Alloc allocator_type;
0031 typedef value_type& reference;
0032 typedef const value_type& const_reference;
0033 typedef typename allocator_traits<allocator_type>::pointer pointer;
0034 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
0035 typedef typename allocator_traits<allocator_type>::size_type size_type;
0036 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
0037
0038 typedef /unspecified/ iterator;
0039 typedef /unspecified/ const_iterator;
0040
0041 explicit hash_set(size_type n = 193, const hasher& hf = hasher(),
0042 const key_equal& eql = key_equal(),
0043 const allocator_type& a = allocator_type());
0044 template <class InputIterator>
0045 hash_set(InputIterator f, InputIterator l,
0046 size_type n = 193, const hasher& hf = hasher(),
0047 const key_equal& eql = key_equal(),
0048 const allocator_type& a = allocator_type());
0049 hash_set(const hash_set&);
0050 ~hash_set();
0051 hash_set& operator=(const hash_set&);
0052
0053 allocator_type get_allocator() const;
0054
0055 bool empty() const;
0056 size_type size() const;
0057 size_type max_size() const;
0058
0059 iterator begin();
0060 iterator end();
0061 const_iterator begin() const;
0062 const_iterator end() const;
0063
0064 pair<iterator, bool> insert(const value_type& obj);
0065 template <class InputIterator>
0066 void insert(InputIterator first, InputIterator last);
0067
0068 void erase(const_iterator position);
0069 size_type erase(const key_type& k);
0070 void erase(const_iterator first, const_iterator last);
0071 void clear();
0072
0073 void swap(hash_set&);
0074
0075 hasher hash_funct() const;
0076 key_equal key_eq() const;
0077
0078 iterator find(const key_type& k);
0079 const_iterator find(const key_type& k) const;
0080 size_type count(const key_type& k) const;
0081 pair<iterator, iterator> equal_range(const key_type& k);
0082 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
0083
0084 size_type bucket_count() const;
0085 size_type max_bucket_count() const;
0086
0087 size_type elems_in_bucket(size_type n) const;
0088
0089 void resize(size_type n);
0090 };
0091
0092 template <class Value, class Hash, class Pred, class Alloc>
0093 void swap(hash_set<Value, Hash, Pred, Alloc>& x,
0094 hash_set<Value, Hash, Pred, Alloc>& y);
0095
0096 template <class Value, class Hash, class Pred, class Alloc>
0097 bool
0098 operator==(const hash_set<Value, Hash, Pred, Alloc>& x,
0099 const hash_set<Value, Hash, Pred, Alloc>& y);
0100
0101 template <class Value, class Hash, class Pred, class Alloc>
0102 bool
0103 operator!=(const hash_set<Value, Hash, Pred, Alloc>& x,
0104 const hash_set<Value, Hash, Pred, Alloc>& y);
0105
0106 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
0107 class Alloc = allocator<Value>>
0108 class hash_multiset
0109 {
0110 public:
0111 // types
0112 typedef Value key_type;
0113 typedef key_type value_type;
0114 typedef Hash hasher;
0115 typedef Pred key_equal;
0116 typedef Alloc allocator_type;
0117 typedef value_type& reference;
0118 typedef const value_type& const_reference;
0119 typedef typename allocator_traits<allocator_type>::pointer pointer;
0120 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
0121 typedef typename allocator_traits<allocator_type>::size_type size_type;
0122 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
0123
0124 typedef /unspecified/ iterator;
0125 typedef /unspecified/ const_iterator;
0126
0127 explicit hash_multiset(size_type n = 193, const hasher& hf = hasher(),
0128 const key_equal& eql = key_equal(),
0129 const allocator_type& a = allocator_type());
0130 template <class InputIterator>
0131 hash_multiset(InputIterator f, InputIterator l,
0132 size_type n = 193, const hasher& hf = hasher(),
0133 const key_equal& eql = key_equal(),
0134 const allocator_type& a = allocator_type());
0135 hash_multiset(const hash_multiset&);
0136 ~hash_multiset();
0137 hash_multiset& operator=(const hash_multiset&);
0138
0139 allocator_type get_allocator() const;
0140
0141 bool empty() const;
0142 size_type size() const;
0143 size_type max_size() const;
0144
0145 iterator begin();
0146 iterator end();
0147 const_iterator begin() const;
0148 const_iterator end() const;
0149
0150 iterator insert(const value_type& obj);
0151 template <class InputIterator>
0152 void insert(InputIterator first, InputIterator last);
0153
0154 void erase(const_iterator position);
0155 size_type erase(const key_type& k);
0156 void erase(const_iterator first, const_iterator last);
0157 void clear();
0158
0159 void swap(hash_multiset&);
0160
0161 hasher hash_funct() const;
0162 key_equal key_eq() const;
0163
0164 iterator find(const key_type& k);
0165 const_iterator find(const key_type& k) const;
0166 size_type count(const key_type& k) const;
0167 pair<iterator, iterator> equal_range(const key_type& k);
0168 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
0169
0170 size_type bucket_count() const;
0171 size_type max_bucket_count() const;
0172
0173 size_type elems_in_bucket(size_type n) const;
0174
0175 void resize(size_type n);
0176 };
0177
0178 template <class Value, class Hash, class Pred, class Alloc>
0179 void swap(hash_multiset<Value, Hash, Pred, Alloc>& x,
0180 hash_multiset<Value, Hash, Pred, Alloc>& y);
0181
0182 template <class Value, class Hash, class Pred, class Alloc>
0183 bool
0184 operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x,
0185 const hash_multiset<Value, Hash, Pred, Alloc>& y);
0186
0187 template <class Value, class Hash, class Pred, class Alloc>
0188 bool
0189 operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x,
0190 const hash_multiset<Value, Hash, Pred, Alloc>& y);
0191 } // __gnu_cxx
0192
0193 */
0194
0195 #if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
0196 # include <__cxx03/ext/hash_set>
0197 #else
0198 # include <__config>
0199 # include <__hash_table>
0200 # include <algorithm>
0201 # include <ext/__hash>
0202 # include <functional>
0203
0204 # if defined(__DEPRECATED) && __DEPRECATED
0205 # if defined(_LIBCPP_WARNING)
0206 _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>")
0207 # else
0208 # warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>
0209 # endif
0210 # endif
0211
0212 # if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0213 # pragma GCC system_header
0214 # endif
0215
0216 namespace __gnu_cxx {
0217
0218 template <class _Value,
0219 class _Hash = hash<_Value>,
0220 class _Pred = std::equal_to<_Value>,
0221 class _Alloc = std::allocator<_Value> >
0222 class _LIBCPP_TEMPLATE_VIS hash_set {
0223 public:
0224 // types
0225 typedef _Value key_type;
0226 typedef key_type value_type;
0227 typedef _Hash hasher;
0228 typedef _Pred key_equal;
0229 typedef _Alloc allocator_type;
0230 typedef value_type& reference;
0231 typedef const value_type& const_reference;
0232
0233 private:
0234 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
0235
0236 __table __table_;
0237
0238 public:
0239 typedef typename __table::pointer pointer;
0240 typedef typename __table::const_pointer const_pointer;
0241 typedef typename __table::size_type size_type;
0242 typedef typename __table::difference_type difference_type;
0243
0244 typedef typename __table::const_iterator iterator;
0245 typedef typename __table::const_iterator const_iterator;
0246
0247 _LIBCPP_HIDE_FROM_ABI hash_set() {}
0248 _LIBCPP_HIDE_FROM_ABI explicit hash_set(
0249 size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
0250 _LIBCPP_HIDE_FROM_ABI hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
0251 template <class _InputIterator>
0252 _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last);
0253 template <class _InputIterator>
0254 _LIBCPP_HIDE_FROM_ABI
0255 hash_set(_InputIterator __first,
0256 _InputIterator __last,
0257 size_type __n,
0258 const hasher& __hf = hasher(),
0259 const key_equal& __eql = key_equal());
0260 template <class _InputIterator>
0261 _LIBCPP_HIDE_FROM_ABI
0262 hash_set(_InputIterator __first,
0263 _InputIterator __last,
0264 size_type __n,
0265 const hasher& __hf,
0266 const key_equal& __eql,
0267 const allocator_type& __a);
0268 _LIBCPP_HIDE_FROM_ABI hash_set(const hash_set& __u);
0269
0270 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
0271
0272 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
0273 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
0274 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
0275
0276 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
0277 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
0278 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
0279 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
0280
0281 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) {
0282 return __table_.__insert_unique(__x);
0283 }
0284 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
0285 template <class _InputIterator>
0286 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
0287
0288 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); }
0289 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
0290 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); }
0291 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
0292
0293 _LIBCPP_HIDE_FROM_ABI void swap(hash_set& __u) { __table_.swap(__u.__table_); }
0294
0295 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); }
0296 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
0297
0298 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
0299 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
0300 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
0301 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
0302 return __table_.__equal_range_unique(__k);
0303 }
0304 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0305 return __table_.__equal_range_unique(__k);
0306 }
0307
0308 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
0309 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
0310
0311 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
0312
0313 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); }
0314 };
0315
0316 template <class _Value, class _Hash, class _Pred, class _Alloc>
0317 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, const hasher& __hf, const key_equal& __eql)
0318 : __table_(__hf, __eql) {
0319 __table_.__rehash_unique(__n);
0320 }
0321
0322 template <class _Value, class _Hash, class _Pred, class _Alloc>
0323 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
0324 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
0325 : __table_(__hf, __eql, __a) {
0326 __table_.__rehash_unique(__n);
0327 }
0328
0329 template <class _Value, class _Hash, class _Pred, class _Alloc>
0330 template <class _InputIterator>
0331 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(_InputIterator __first, _InputIterator __last) {
0332 insert(__first, __last);
0333 }
0334
0335 template <class _Value, class _Hash, class _Pred, class _Alloc>
0336 template <class _InputIterator>
0337 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
0338 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
0339 : __table_(__hf, __eql) {
0340 __table_.__rehash_unique(__n);
0341 insert(__first, __last);
0342 }
0343
0344 template <class _Value, class _Hash, class _Pred, class _Alloc>
0345 template <class _InputIterator>
0346 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
0347 _InputIterator __first,
0348 _InputIterator __last,
0349 size_type __n,
0350 const hasher& __hf,
0351 const key_equal& __eql,
0352 const allocator_type& __a)
0353 : __table_(__hf, __eql, __a) {
0354 __table_.__rehash_unique(__n);
0355 insert(__first, __last);
0356 }
0357
0358 template <class _Value, class _Hash, class _Pred, class _Alloc>
0359 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(const hash_set& __u) : __table_(__u.__table_) {
0360 __table_.__rehash_unique(__u.bucket_count());
0361 insert(__u.begin(), __u.end());
0362 }
0363
0364 template <class _Value, class _Hash, class _Pred, class _Alloc>
0365 template <class _InputIterator>
0366 inline void hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
0367 for (; __first != __last; ++__first)
0368 __table_.__insert_unique(*__first);
0369 }
0370
0371 template <class _Value, class _Hash, class _Pred, class _Alloc>
0372 inline _LIBCPP_HIDE_FROM_ABI void
0373 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
0374 __x.swap(__y);
0375 }
0376
0377 template <class _Value, class _Hash, class _Pred, class _Alloc>
0378 _LIBCPP_HIDE_FROM_ABI bool
0379 operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
0380 if (__x.size() != __y.size())
0381 return false;
0382 typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
0383 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
0384 const_iterator __j = __y.find(*__i);
0385 if (__j == __ey || !(*__i == *__j))
0386 return false;
0387 }
0388 return true;
0389 }
0390
0391 template <class _Value, class _Hash, class _Pred, class _Alloc>
0392 inline _LIBCPP_HIDE_FROM_ABI bool
0393 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
0394 return !(__x == __y);
0395 }
0396
0397 template <class _Value,
0398 class _Hash = hash<_Value>,
0399 class _Pred = std::equal_to<_Value>,
0400 class _Alloc = std::allocator<_Value> >
0401 class _LIBCPP_TEMPLATE_VIS hash_multiset {
0402 public:
0403 // types
0404 typedef _Value key_type;
0405 typedef key_type value_type;
0406 typedef _Hash hasher;
0407 typedef _Pred key_equal;
0408 typedef _Alloc allocator_type;
0409 typedef value_type& reference;
0410 typedef const value_type& const_reference;
0411
0412 private:
0413 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
0414
0415 __table __table_;
0416
0417 public:
0418 typedef typename __table::pointer pointer;
0419 typedef typename __table::const_pointer const_pointer;
0420 typedef typename __table::size_type size_type;
0421 typedef typename __table::difference_type difference_type;
0422
0423 typedef typename __table::const_iterator iterator;
0424 typedef typename __table::const_iterator const_iterator;
0425
0426 _LIBCPP_HIDE_FROM_ABI hash_multiset() {}
0427 explicit _LIBCPP_HIDE_FROM_ABI
0428 hash_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
0429 _LIBCPP_HIDE_FROM_ABI
0430 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
0431 template <class _InputIterator>
0432 _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last);
0433 template <class _InputIterator>
0434 _LIBCPP_HIDE_FROM_ABI
0435 hash_multiset(_InputIterator __first,
0436 _InputIterator __last,
0437 size_type __n,
0438 const hasher& __hf = hasher(),
0439 const key_equal& __eql = key_equal());
0440 template <class _InputIterator>
0441 _LIBCPP_HIDE_FROM_ABI hash_multiset(
0442 _InputIterator __first,
0443 _InputIterator __last,
0444 size_type __n,
0445 const hasher& __hf,
0446 const key_equal& __eql,
0447 const allocator_type& __a);
0448 _LIBCPP_HIDE_FROM_ABI hash_multiset(const hash_multiset& __u);
0449
0450 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
0451
0452 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
0453 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
0454 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
0455
0456 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
0457 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
0458 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
0459 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
0460
0461 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
0462 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); }
0463 template <class _InputIterator>
0464 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
0465
0466 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); }
0467 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
0468 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); }
0469 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
0470
0471 _LIBCPP_HIDE_FROM_ABI void swap(hash_multiset& __u) { __table_.swap(__u.__table_); }
0472
0473 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); }
0474 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
0475
0476 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
0477 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
0478 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
0479 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
0480 return __table_.__equal_range_multi(__k);
0481 }
0482 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0483 return __table_.__equal_range_multi(__k);
0484 }
0485
0486 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
0487 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
0488
0489 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
0490
0491 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); }
0492 };
0493
0494 template <class _Value, class _Hash, class _Pred, class _Alloc>
0495 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql)
0496 : __table_(__hf, __eql) {
0497 __table_.__rehash_multi(__n);
0498 }
0499
0500 template <class _Value, class _Hash, class _Pred, class _Alloc>
0501 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
0502 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
0503 : __table_(__hf, __eql, __a) {
0504 __table_.__rehash_multi(__n);
0505 }
0506
0507 template <class _Value, class _Hash, class _Pred, class _Alloc>
0508 template <class _InputIterator>
0509 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(_InputIterator __first, _InputIterator __last) {
0510 insert(__first, __last);
0511 }
0512
0513 template <class _Value, class _Hash, class _Pred, class _Alloc>
0514 template <class _InputIterator>
0515 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
0516 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
0517 : __table_(__hf, __eql) {
0518 __table_.__rehash_multi(__n);
0519 insert(__first, __last);
0520 }
0521
0522 template <class _Value, class _Hash, class _Pred, class _Alloc>
0523 template <class _InputIterator>
0524 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
0525 _InputIterator __first,
0526 _InputIterator __last,
0527 size_type __n,
0528 const hasher& __hf,
0529 const key_equal& __eql,
0530 const allocator_type& __a)
0531 : __table_(__hf, __eql, __a) {
0532 __table_.__rehash_multi(__n);
0533 insert(__first, __last);
0534 }
0535
0536 template <class _Value, class _Hash, class _Pred, class _Alloc>
0537 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(const hash_multiset& __u) : __table_(__u.__table_) {
0538 __table_.__rehash_multi(__u.bucket_count());
0539 insert(__u.begin(), __u.end());
0540 }
0541
0542 template <class _Value, class _Hash, class _Pred, class _Alloc>
0543 template <class _InputIterator>
0544 inline void hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
0545 for (; __first != __last; ++__first)
0546 __table_.__insert_multi(*__first);
0547 }
0548
0549 template <class _Value, class _Hash, class _Pred, class _Alloc>
0550 inline _LIBCPP_HIDE_FROM_ABI void
0551 swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
0552 __x.swap(__y);
0553 }
0554
0555 template <class _Value, class _Hash, class _Pred, class _Alloc>
0556 _LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
0557 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
0558 if (__x.size() != __y.size())
0559 return false;
0560 typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
0561 typedef std::pair<const_iterator, const_iterator> _EqRng;
0562 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
0563 _EqRng __xeq = __x.equal_range(*__i);
0564 _EqRng __yeq = __y.equal_range(*__i);
0565 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
0566 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
0567 return false;
0568 __i = __xeq.second;
0569 }
0570 return true;
0571 }
0572
0573 template <class _Value, class _Hash, class _Pred, class _Alloc>
0574 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
0575 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
0576 return !(__x == __y);
0577 }
0578
0579 } // namespace __gnu_cxx
0580
0581 # if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
0582 # include <concepts>
0583 # include <iterator>
0584 # include <type_traits>
0585 # endif
0586 #endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
0587
0588 #endif // _LIBCPP_HASH_SET
