Debian Codegraph @

libcxx/include/__cxx03/ext/hash_set

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