Warning, /include/c++/v1/__cxx03/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___CXX03_HASH_SET
0011 #define _LIBCPP___CXX03_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 #include <__cxx03/__config>
0196 #include <__cxx03/__hash_table>
0197 #include <__cxx03/algorithm>
0198 #include <__cxx03/ext/__hash>
0199 #include <__cxx03/functional>
0200
0201 #if defined(__DEPRECATED) && __DEPRECATED
0202 # if defined(_LIBCPP_WARNING)
0203 _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>")
0204 # else
0205 # warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>
0206 # endif
0207 #endif
0208
0209 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0210 # pragma GCC system_header
0211 #endif
0212
0213 namespace __gnu_cxx {
0214
0215 template <class _Value,
0216 class _Hash = hash<_Value>,
0217 class _Pred = std::equal_to<_Value>,
0218 class _Alloc = std::allocator<_Value> >
0219 class _LIBCPP_TEMPLATE_VIS hash_set {
0220 public:
0221 // types
0222 typedef _Value key_type;
0223 typedef key_type value_type;
0224 typedef _Hash hasher;
0225 typedef _Pred key_equal;
0226 typedef _Alloc allocator_type;
0227 typedef value_type& reference;
0228 typedef const value_type& const_reference;
0229
0230 private:
0231 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
0232
0233 __table __table_;
0234
0235 public:
0236 typedef typename __table::pointer pointer;
0237 typedef typename __table::const_pointer const_pointer;
0238 typedef typename __table::size_type size_type;
0239 typedef typename __table::difference_type difference_type;
0240
0241 typedef typename __table::const_iterator iterator;
0242 typedef typename __table::const_iterator const_iterator;
0243
0244 _LIBCPP_HIDE_FROM_ABI hash_set() {}
0245 _LIBCPP_HIDE_FROM_ABI explicit hash_set(
0246 size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
0247 _LIBCPP_HIDE_FROM_ABI hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
0248 template <class _InputIterator>
0249 _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last);
0250 template <class _InputIterator>
0251 _LIBCPP_HIDE_FROM_ABI
0252 hash_set(_InputIterator __first,
0253 _InputIterator __last,
0254 size_type __n,
0255 const hasher& __hf = hasher(),
0256 const key_equal& __eql = key_equal());
0257 template <class _InputIterator>
0258 _LIBCPP_HIDE_FROM_ABI
0259 hash_set(_InputIterator __first,
0260 _InputIterator __last,
0261 size_type __n,
0262 const hasher& __hf,
0263 const key_equal& __eql,
0264 const allocator_type& __a);
0265 _LIBCPP_HIDE_FROM_ABI hash_set(const hash_set& __u);
0266
0267 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
0268
0269 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
0270 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
0271 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
0272
0273 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
0274 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
0275 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
0276 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
0277
0278 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) {
0279 return __table_.__insert_unique(__x);
0280 }
0281 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
0282 template <class _InputIterator>
0283 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
0284
0285 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); }
0286 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
0287 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); }
0288 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
0289
0290 _LIBCPP_HIDE_FROM_ABI void swap(hash_set& __u) { __table_.swap(__u.__table_); }
0291
0292 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); }
0293 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
0294
0295 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
0296 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
0297 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
0298 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
0299 return __table_.__equal_range_unique(__k);
0300 }
0301 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0302 return __table_.__equal_range_unique(__k);
0303 }
0304
0305 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
0306 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
0307
0308 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
0309
0310 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); }
0311 };
0312
0313 template <class _Value, class _Hash, class _Pred, class _Alloc>
0314 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, const hasher& __hf, const key_equal& __eql)
0315 : __table_(__hf, __eql) {
0316 __table_.__rehash_unique(__n);
0317 }
0318
0319 template <class _Value, class _Hash, class _Pred, class _Alloc>
0320 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
0321 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
0322 : __table_(__hf, __eql, __a) {
0323 __table_.__rehash_unique(__n);
0324 }
0325
0326 template <class _Value, class _Hash, class _Pred, class _Alloc>
0327 template <class _InputIterator>
0328 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(_InputIterator __first, _InputIterator __last) {
0329 insert(__first, __last);
0330 }
0331
0332 template <class _Value, class _Hash, class _Pred, class _Alloc>
0333 template <class _InputIterator>
0334 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
0335 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
0336 : __table_(__hf, __eql) {
0337 __table_.__rehash_unique(__n);
0338 insert(__first, __last);
0339 }
0340
0341 template <class _Value, class _Hash, class _Pred, class _Alloc>
0342 template <class _InputIterator>
0343 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
0344 _InputIterator __first,
0345 _InputIterator __last,
0346 size_type __n,
0347 const hasher& __hf,
0348 const key_equal& __eql,
0349 const allocator_type& __a)
0350 : __table_(__hf, __eql, __a) {
0351 __table_.__rehash_unique(__n);
0352 insert(__first, __last);
0353 }
0354
0355 template <class _Value, class _Hash, class _Pred, class _Alloc>
0356 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(const hash_set& __u) : __table_(__u.__table_) {
0357 __table_.__rehash_unique(__u.bucket_count());
0358 insert(__u.begin(), __u.end());
0359 }
0360
0361 template <class _Value, class _Hash, class _Pred, class _Alloc>
0362 template <class _InputIterator>
0363 inline void hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
0364 for (; __first != __last; ++__first)
0365 __table_.__insert_unique(*__first);
0366 }
0367
0368 template <class _Value, class _Hash, class _Pred, class _Alloc>
0369 inline _LIBCPP_HIDE_FROM_ABI void
0370 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
0371 __x.swap(__y);
0372 }
0373
0374 template <class _Value, class _Hash, class _Pred, class _Alloc>
0375 _LIBCPP_HIDE_FROM_ABI bool
0376 operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
0377 if (__x.size() != __y.size())
0378 return false;
0379 typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
0380 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
0381 const_iterator __j = __y.find(*__i);
0382 if (__j == __ey || !(*__i == *__j))
0383 return false;
0384 }
0385 return true;
0386 }
0387
0388 template <class _Value, class _Hash, class _Pred, class _Alloc>
0389 inline _LIBCPP_HIDE_FROM_ABI bool
0390 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
0391 return !(__x == __y);
0392 }
0393
0394 template <class _Value,
0395 class _Hash = hash<_Value>,
0396 class _Pred = std::equal_to<_Value>,
0397 class _Alloc = std::allocator<_Value> >
0398 class _LIBCPP_TEMPLATE_VIS hash_multiset {
0399 public:
0400 // types
0401 typedef _Value key_type;
0402 typedef key_type value_type;
0403 typedef _Hash hasher;
0404 typedef _Pred key_equal;
0405 typedef _Alloc allocator_type;
0406 typedef value_type& reference;
0407 typedef const value_type& const_reference;
0408
0409 private:
0410 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
0411
0412 __table __table_;
0413
0414 public:
0415 typedef typename __table::pointer pointer;
0416 typedef typename __table::const_pointer const_pointer;
0417 typedef typename __table::size_type size_type;
0418 typedef typename __table::difference_type difference_type;
0419
0420 typedef typename __table::const_iterator iterator;
0421 typedef typename __table::const_iterator const_iterator;
0422
0423 _LIBCPP_HIDE_FROM_ABI hash_multiset() {}
0424 explicit _LIBCPP_HIDE_FROM_ABI
0425 hash_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
0426 _LIBCPP_HIDE_FROM_ABI
0427 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
0428 template <class _InputIterator>
0429 _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last);
0430 template <class _InputIterator>
0431 _LIBCPP_HIDE_FROM_ABI
0432 hash_multiset(_InputIterator __first,
0433 _InputIterator __last,
0434 size_type __n,
0435 const hasher& __hf = hasher(),
0436 const key_equal& __eql = key_equal());
0437 template <class _InputIterator>
0438 _LIBCPP_HIDE_FROM_ABI hash_multiset(
0439 _InputIterator __first,
0440 _InputIterator __last,
0441 size_type __n,
0442 const hasher& __hf,
0443 const key_equal& __eql,
0444 const allocator_type& __a);
0445 _LIBCPP_HIDE_FROM_ABI hash_multiset(const hash_multiset& __u);
0446
0447 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
0448
0449 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
0450 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
0451 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
0452
0453 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
0454 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
0455 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
0456 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
0457
0458 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
0459 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); }
0460 template <class _InputIterator>
0461 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
0462
0463 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); }
0464 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
0465 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); }
0466 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
0467
0468 _LIBCPP_HIDE_FROM_ABI void swap(hash_multiset& __u) { __table_.swap(__u.__table_); }
0469
0470 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); }
0471 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
0472
0473 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
0474 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
0475 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
0476 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
0477 return __table_.__equal_range_multi(__k);
0478 }
0479 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0480 return __table_.__equal_range_multi(__k);
0481 }
0482
0483 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
0484 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
0485
0486 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
0487
0488 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); }
0489 };
0490
0491 template <class _Value, class _Hash, class _Pred, class _Alloc>
0492 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql)
0493 : __table_(__hf, __eql) {
0494 __table_.__rehash_multi(__n);
0495 }
0496
0497 template <class _Value, class _Hash, class _Pred, class _Alloc>
0498 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
0499 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
0500 : __table_(__hf, __eql, __a) {
0501 __table_.__rehash_multi(__n);
0502 }
0503
0504 template <class _Value, class _Hash, class _Pred, class _Alloc>
0505 template <class _InputIterator>
0506 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(_InputIterator __first, _InputIterator __last) {
0507 insert(__first, __last);
0508 }
0509
0510 template <class _Value, class _Hash, class _Pred, class _Alloc>
0511 template <class _InputIterator>
0512 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
0513 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
0514 : __table_(__hf, __eql) {
0515 __table_.__rehash_multi(__n);
0516 insert(__first, __last);
0517 }
0518
0519 template <class _Value, class _Hash, class _Pred, class _Alloc>
0520 template <class _InputIterator>
0521 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
0522 _InputIterator __first,
0523 _InputIterator __last,
0524 size_type __n,
0525 const hasher& __hf,
0526 const key_equal& __eql,
0527 const allocator_type& __a)
0528 : __table_(__hf, __eql, __a) {
0529 __table_.__rehash_multi(__n);
0530 insert(__first, __last);
0531 }
0532
0533 template <class _Value, class _Hash, class _Pred, class _Alloc>
0534 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(const hash_multiset& __u) : __table_(__u.__table_) {
0535 __table_.__rehash_multi(__u.bucket_count());
0536 insert(__u.begin(), __u.end());
0537 }
0538
0539 template <class _Value, class _Hash, class _Pred, class _Alloc>
0540 template <class _InputIterator>
0541 inline void hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
0542 for (; __first != __last; ++__first)
0543 __table_.__insert_multi(*__first);
0544 }
0545
0546 template <class _Value, class _Hash, class _Pred, class _Alloc>
0547 inline _LIBCPP_HIDE_FROM_ABI void
0548 swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
0549 __x.swap(__y);
0550 }
0551
0552 template <class _Value, class _Hash, class _Pred, class _Alloc>
0553 _LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
0554 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
0555 if (__x.size() != __y.size())
0556 return false;
0557 typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
0558 typedef std::pair<const_iterator, const_iterator> _EqRng;
0559 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
0560 _EqRng __xeq = __x.equal_range(*__i);
0561 _EqRng __yeq = __y.equal_range(*__i);
0562 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
0563 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
0564 return false;
0565 __i = __xeq.second;
0566 }
0567 return true;
0568 }
0569
0570 template <class _Value, class _Hash, class _Pred, class _Alloc>
0571 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
0572 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
0573 return !(__x == __y);
0574 }
0575
0576 } // namespace __gnu_cxx
0577
0578 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
0579 # include <__cxx03/concepts>
0580 # include <__cxx03/iterator>
0581 # include <__cxx03/type_traits>
0582 #endif
0583
0584 #endif // _LIBCPP___CXX03_HASH_SET
