Debian Codegraph @

libcxx/include/__cxx03/unordered_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_UNORDERED_SET
11 #define _LIBCPP___CXX03_UNORDERED_SET
12
13 // clang-format off
14
15 /*
16
17 unordered_set synopsis
18
19 #include <__cxx03/initializer_list>
20
21 namespace std
22 {
23
24 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
25 class Alloc = allocator<Value>>
26 class unordered_set
27 {
28 public:
29 // types
30 typedef Value key_type;
31 typedef key_type value_type;
32 typedef Hash hasher;
33 typedef Pred key_equal;
34 typedef Alloc allocator_type;
35 typedef value_type& reference;
36 typedef const value_type& const_reference;
37 typedef typename allocator_traits<allocator_type>::pointer pointer;
38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
39 typedef typename allocator_traits<allocator_type>::size_type size_type;
40 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
41
42 typedef /unspecified/ iterator;
43 typedef /unspecified/ const_iterator;
44 typedef /unspecified/ local_iterator;
45 typedef /unspecified/ const_local_iterator;
46
47 typedef unspecified node_type unspecified; // C++17
48 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
49
50 unordered_set()
51 noexcept(
52 is_nothrow_default_constructible<hasher>::value &&
53 is_nothrow_default_constructible<key_equal>::value &&
54 is_nothrow_default_constructible<allocator_type>::value);
55 explicit unordered_set(size_type n, const hasher& hf = hasher(),
56 const key_equal& eql = key_equal(),
57 const allocator_type& a = allocator_type());
58 template <class InputIterator>
59 unordered_set(InputIterator f, InputIterator l,
60 size_type n = 0, const hasher& hf = hasher(),
61 const key_equal& eql = key_equal(),
62 const allocator_type& a = allocator_type());
63 template<container-compatible-range<value_type> R>
64 unordered_set(from_range_t, R&& rg, size_type n = see below,
65 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
66 const allocator_type& a = allocator_type()); // C++23
67 explicit unordered_set(const allocator_type&);
68 unordered_set(const unordered_set&);
69 unordered_set(const unordered_set&, const Allocator&);
70 unordered_set(unordered_set&&)
71 noexcept(
72 is_nothrow_move_constructible<hasher>::value &&
73 is_nothrow_move_constructible<key_equal>::value &&
74 is_nothrow_move_constructible<allocator_type>::value);
75 unordered_set(unordered_set&&, const Allocator&);
76 unordered_set(initializer_list<value_type>, size_type n = 0,
77 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
78 const allocator_type& a = allocator_type());
79 unordered_set(size_type n, const allocator_type& a); // C++14
80 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
81 template <class InputIterator>
82 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
83 template <class InputIterator>
84 unordered_set(InputIterator f, InputIterator l, size_type n,
85 const hasher& hf, const allocator_type& a); // C++14
86 template<container-compatible-range<value_type> R>
87 unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a)
88 : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
89 template<container-compatible-range<value_type> R>
90 unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
91 : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23
92 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
93 unordered_set(initializer_list<value_type> il, size_type n,
94 const hasher& hf, const allocator_type& a); // C++14
95 ~unordered_set();
96 unordered_set& operator=(const unordered_set&);
97 unordered_set& operator=(unordered_set&&)
98 noexcept(
99 allocator_type::propagate_on_container_move_assignment::value &&
100 is_nothrow_move_assignable<allocator_type>::value &&
101 is_nothrow_move_assignable<hasher>::value &&
102 is_nothrow_move_assignable<key_equal>::value);
103 unordered_set& operator=(initializer_list<value_type>);
104
105 allocator_type get_allocator() const noexcept;
106
107 bool empty() const noexcept;
108 size_type size() const noexcept;
109 size_type max_size() const noexcept;
110
111 iterator begin() noexcept;
112 iterator end() noexcept;
113 const_iterator begin() const noexcept;
114 const_iterator end() const noexcept;
115 const_iterator cbegin() const noexcept;
116 const_iterator cend() const noexcept;
117
118 template <class... Args>
119 pair<iterator, bool> emplace(Args&&... args);
120 template <class... Args>
121 iterator emplace_hint(const_iterator position, Args&&... args);
122 pair<iterator, bool> insert(const value_type& obj);
123 pair<iterator, bool> insert(value_type&& obj);
124 iterator insert(const_iterator hint, const value_type& obj);
125 iterator insert(const_iterator hint, value_type&& obj);
126 template <class InputIterator>
127 void insert(InputIterator first, InputIterator last);
128 template<container-compatible-range<value_type> R>
129 void insert_range(R&& rg); // C++23
130 void insert(initializer_list<value_type>);
131
132 node_type extract(const_iterator position); // C++17
133 node_type extract(const key_type& x); // C++17
134 insert_return_type insert(node_type&& nh); // C++17
135 iterator insert(const_iterator hint, node_type&& nh); // C++17
136
137 iterator erase(const_iterator position);
138 iterator erase(iterator position); // C++14
139 size_type erase(const key_type& k);
140 iterator erase(const_iterator first, const_iterator last);
141 void clear() noexcept;
142
143 template<class H2, class P2>
144 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17
145 template<class H2, class P2>
146 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17
147 template<class H2, class P2>
148 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17
149 template<class H2, class P2>
150 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17
151
152 void swap(unordered_set&)
153 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
154 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
155 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
156
157 hasher hash_function() const;
158 key_equal key_eq() const;
159
160 iterator find(const key_type& k);
161 const_iterator find(const key_type& k) const;
162 template<typename K>
163 iterator find(const K& x); // C++20
164 template<typename K>
165 const_iterator find(const K& x) const; // C++20
166 size_type count(const key_type& k) const;
167 template<typename K>
168 size_type count(const K& k) const; // C++20
169 bool contains(const key_type& k) const; // C++20
170 template<typename K>
171 bool contains(const K& k) const; // C++20
172 pair<iterator, iterator> equal_range(const key_type& k);
173 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
174 template<typename K>
175 pair<iterator, iterator> equal_range(const K& k); // C++20
176 template<typename K>
177 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
178
179 size_type bucket_count() const noexcept;
180 size_type max_bucket_count() const noexcept;
181
182 size_type bucket_size(size_type n) const;
183 size_type bucket(const key_type& k) const;
184
185 local_iterator begin(size_type n);
186 local_iterator end(size_type n);
187 const_local_iterator begin(size_type n) const;
188 const_local_iterator end(size_type n) const;
189 const_local_iterator cbegin(size_type n) const;
190 const_local_iterator cend(size_type n) const;
191
192 float load_factor() const noexcept;
193 float max_load_factor() const noexcept;
194 void max_load_factor(float z);
195 void rehash(size_type n);
196 void reserve(size_type n);
197 };
198
199 template<class InputIterator,
200 class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
201 class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
202 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
203 unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
204 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
205 -> unordered_set<typename iterator_traits<InputIterator>::value_type,
206 Hash, Pred, Allocator>; // C++17
207
208 template<ranges::input_range R,
209 class Hash = hash<ranges::range_value_t<R>>,
210 class Pred = equal_to<ranges::range_value_t<R>>,
211 class Allocator = allocator<ranges::range_value_t<R>>>
212 unordered_set(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())
213 -> unordered_set<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23
214
215 template<class T, class Hash = hash<T>,
216 class Pred = equal_to<T>, class Allocator = allocator<T>>
217 unordered_set(initializer_list<T>, typename see below::size_type = see below,
218 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
219 -> unordered_set<T, Hash, Pred, Allocator>; // C++17
220
221 template<class InputIterator, class Allocator>
222 unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
223 -> unordered_set<typename iterator_traits<InputIterator>::value_type,
224 hash<typename iterator_traits<InputIterator>::value_type>,
225 equal_to<typename iterator_traits<InputIterator>::value_type>,
226 Allocator>; // C++17
227
228 template<class InputIterator, class Hash, class Allocator>
229 unordered_set(InputIterator, InputIterator, typename see below::size_type,
230 Hash, Allocator)
231 -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,
232 equal_to<typename iterator_traits<InputIterator>::value_type>,
233 Allocator>; // C++17
234
235 template<ranges::input_range R, class Allocator>
236 unordered_set(from_range_t, R&&, typename see below::size_type, Allocator)
237 -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
238 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
239
240 template<ranges::input_range R, class Allocator>
241 unordered_set(from_range_t, R&&, Allocator)
242 -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
243 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
244
245 template<ranges::input_range R, class Hash, class Allocator>
246 unordered_set(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
247 -> unordered_set<ranges::range_value_t<R>, Hash,
248 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
249
250 template<class T, class Allocator>
251 unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
252 -> unordered_set<T, hash<T>, equal_to<T>, Allocator>; // C++17
253
254 template<class T, class Hash, class Allocator>
255 unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
256 -> unordered_set<T, Hash, equal_to<T>, Allocator>; // C++17
257
258 template <class Value, class Hash, class Pred, class Alloc>
259 void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
260 unordered_set<Value, Hash, Pred, Alloc>& y)
261 noexcept(noexcept(x.swap(y)));
262
263 template <class Value, class Hash, class Pred, class Alloc>
264 bool
265 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
266 const unordered_set<Value, Hash, Pred, Alloc>& y);
267
268 template <class Value, class Hash, class Pred, class Alloc>
269 bool
270 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
271 const unordered_set<Value, Hash, Pred, Alloc>& y); // removed in C++20
272
273 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
274 class Alloc = allocator<Value>>
275 class unordered_multiset
276 {
277 public:
278 // types
279 typedef Value key_type;
280 typedef key_type value_type;
281 typedef Hash hasher;
282 typedef Pred key_equal;
283 typedef Alloc allocator_type;
284 typedef value_type& reference;
285 typedef const value_type& const_reference;
286 typedef typename allocator_traits<allocator_type>::pointer pointer;
287 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
288 typedef typename allocator_traits<allocator_type>::size_type size_type;
289 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
290
291 typedef /unspecified/ iterator;
292 typedef /unspecified/ const_iterator;
293 typedef /unspecified/ local_iterator;
294 typedef /unspecified/ const_local_iterator;
295
296 typedef unspecified node_type unspecified; // C++17
297
298 unordered_multiset()
299 noexcept(
300 is_nothrow_default_constructible<hasher>::value &&
301 is_nothrow_default_constructible<key_equal>::value &&
302 is_nothrow_default_constructible<allocator_type>::value);
303 explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
304 const key_equal& eql = key_equal(),
305 const allocator_type& a = allocator_type());
306 template <class InputIterator>
307 unordered_multiset(InputIterator f, InputIterator l,
308 size_type n = 0, const hasher& hf = hasher(),
309 const key_equal& eql = key_equal(),
310 const allocator_type& a = allocator_type());
311 template<container-compatible-range<value_type> R>
312 unordered_multiset(from_range_t, R&& rg, size_type n = see below,
313 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
314 const allocator_type& a = allocator_type()); // C++23
315 explicit unordered_multiset(const allocator_type&);
316 unordered_multiset(const unordered_multiset&);
317 unordered_multiset(const unordered_multiset&, const Allocator&);
318 unordered_multiset(unordered_multiset&&)
319 noexcept(
320 is_nothrow_move_constructible<hasher>::value &&
321 is_nothrow_move_constructible<key_equal>::value &&
322 is_nothrow_move_constructible<allocator_type>::value);
323 unordered_multiset(unordered_multiset&&, const Allocator&);
324 unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
325 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
326 const allocator_type& a = allocator_type());
327 unordered_multiset(size_type n, const allocator_type& a); // C++14
328 unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
329 template <class InputIterator>
330 unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
331 template <class InputIterator>
332 unordered_multiset(InputIterator f, InputIterator l, size_type n,
333 const hasher& hf, const allocator_type& a); // C++14
334 template<container-compatible-range<value_type> R>
335 unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a)
336 : unordered_multiset(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
337 template<container-compatible-range<value_type> R>
338 unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
339 : unordered_multiset(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23
340 unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
341 unordered_multiset(initializer_list<value_type> il, size_type n,
342 const hasher& hf, const allocator_type& a); // C++14
343 ~unordered_multiset();
344 unordered_multiset& operator=(const unordered_multiset&);
345 unordered_multiset& operator=(unordered_multiset&&)
346 noexcept(
347 allocator_type::propagate_on_container_move_assignment::value &&
348 is_nothrow_move_assignable<allocator_type>::value &&
349 is_nothrow_move_assignable<hasher>::value &&
350 is_nothrow_move_assignable<key_equal>::value);
351 unordered_multiset& operator=(initializer_list<value_type>);
352
353 allocator_type get_allocator() const noexcept;
354
355 bool empty() const noexcept;
356 size_type size() const noexcept;
357 size_type max_size() const noexcept;
358
359 iterator begin() noexcept;
360 iterator end() noexcept;
361 const_iterator begin() const noexcept;
362 const_iterator end() const noexcept;
363 const_iterator cbegin() const noexcept;
364 const_iterator cend() const noexcept;
365
366 template <class... Args>
367 iterator emplace(Args&&... args);
368 template <class... Args>
369 iterator emplace_hint(const_iterator position, Args&&... args);
370 iterator insert(const value_type& obj);
371 iterator insert(value_type&& obj);
372 iterator insert(const_iterator hint, const value_type& obj);
373 iterator insert(const_iterator hint, value_type&& obj);
374 template <class InputIterator>
375 void insert(InputIterator first, InputIterator last);
376 template<container-compatible-range<value_type> R>
377 void insert_range(R&& rg); // C++23
378 void insert(initializer_list<value_type>);
379
380 node_type extract(const_iterator position); // C++17
381 node_type extract(const key_type& x); // C++17
382 iterator insert(node_type&& nh); // C++17
383 iterator insert(const_iterator hint, node_type&& nh); // C++17
384
385 iterator erase(const_iterator position);
386 iterator erase(iterator position); // C++14
387 size_type erase(const key_type& k);
388 iterator erase(const_iterator first, const_iterator last);
389 void clear() noexcept;
390
391 template<class H2, class P2>
392 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17
393 template<class H2, class P2>
394 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17
395 template<class H2, class P2>
396 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17
397 template<class H2, class P2>
398 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17
399
400 void swap(unordered_multiset&)
401 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
402 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
403 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
404
405 hasher hash_function() const;
406 key_equal key_eq() const;
407
408 iterator find(const key_type& k);
409 const_iterator find(const key_type& k) const;
410 template<typename K>
411 iterator find(const K& x); // C++20
412 template<typename K>
413 const_iterator find(const K& x) const; // C++20
414 size_type count(const key_type& k) const;
415 template<typename K>
416 size_type count(const K& k) const; // C++20
417 bool contains(const key_type& k) const; // C++20
418 template<typename K>
419 bool contains(const K& k) const; // C++20
420 pair<iterator, iterator> equal_range(const key_type& k);
421 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
422 template<typename K>
423 pair<iterator, iterator> equal_range(const K& k); // C++20
424 template<typename K>
425 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
426
427 size_type bucket_count() const noexcept;
428 size_type max_bucket_count() const noexcept;
429
430 size_type bucket_size(size_type n) const;
431 size_type bucket(const key_type& k) const;
432
433 local_iterator begin(size_type n);
434 local_iterator end(size_type n);
435 const_local_iterator begin(size_type n) const;
436 const_local_iterator end(size_type n) const;
437 const_local_iterator cbegin(size_type n) const;
438 const_local_iterator cend(size_type n) const;
439
440 float load_factor() const noexcept;
441 float max_load_factor() const noexcept;
442 void max_load_factor(float z);
443 void rehash(size_type n);
444 void reserve(size_type n);
445 };
446
447 template<class InputIterator,
448 class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
449 class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
450 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
451 unordered_multiset(InputIterator, InputIterator, see below::size_type = see below,
452 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
453 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
454 Hash, Pred, Allocator>; // C++17
455
456 template<ranges::input_range R,
457 class Hash = hash<ranges::range_value_t<R>>,
458 class Pred = equal_to<ranges::range_value_t<R>>,
459 class Allocator = allocator<ranges::range_value_t<R>>>
460 unordered_multiset(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())
461 -> unordered_multiset<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23
462
463 template<class T, class Hash = hash<T>,
464 class Pred = equal_to<T>, class Allocator = allocator<T>>
465 unordered_multiset(initializer_list<T>, typename see below::size_type = see below,
466 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
467 -> unordered_multiset<T, Hash, Pred, Allocator>; // C++17
468
469 template<class InputIterator, class Allocator>
470 unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
471 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
472 hash<typename iterator_traits<InputIterator>::value_type>,
473 equal_to<typename iterator_traits<InputIterator>::value_type>,
474 Allocator>; // C++17
475
476 template<class InputIterator, class Hash, class Allocator>
477 unordered_multiset(InputIterator, InputIterator, typename see below::size_type,
478 Hash, Allocator)
479 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash,
480 equal_to<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
481
482 template<ranges::input_range R, class Allocator>
483 unordered_multiset(from_range_t, R&&, typename see below::size_type, Allocator)
484 -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
485 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
486
487 template<ranges::input_range R, class Allocator>
488 unordered_multiset(from_range_t, R&&, Allocator)
489 -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
490 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
491
492 template<ranges::input_range R, class Hash, class Allocator>
493 unordered_multiset(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
494 -> unordered_multiset<ranges::range_value_t<R>, Hash,
495 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
496
497 template<class T, class Allocator>
498 unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
499 -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>; // C++17
500
501 template<class T, class Hash, class Allocator>
502 unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
503 -> unordered_multiset<T, Hash, equal_to<T>, Allocator>; // C++17
504
505 template <class Value, class Hash, class Pred, class Alloc>
506 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
507 unordered_multiset<Value, Hash, Pred, Alloc>& y)
508 noexcept(noexcept(x.swap(y)));
509
510 template <class K, class T, class H, class P, class A, class Predicate>
511 typename unordered_set<K, T, H, P, A>::size_type
512 erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20
513
514 template <class K, class T, class H, class P, class A, class Predicate>
515 typename unordered_multiset<K, T, H, P, A>::size_type
516 erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20
517
518
519 template <class Value, class Hash, class Pred, class Alloc>
520 bool
521 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
522 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
523
524 template <class Value, class Hash, class Pred, class Alloc>
525 bool
526 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
527 const unordered_multiset<Value, Hash, Pred, Alloc>& y); // removed in C++20
528 } // std
529
530 */
531
532 // clang-format on
533
534 #include <__cxx03/__algorithm/is_permutation.h>
535 #include <__cxx03/__assert>
536 #include <__cxx03/__config>
537 #include <__cxx03/__functional/operations.h>
538 #include <__cxx03/__hash_table>
539 #include <__cxx03/__iterator/distance.h>
540 #include <__cxx03/__iterator/erase_if_container.h>
541 #include <__cxx03/__iterator/iterator_traits.h>
542 #include <__cxx03/__memory/addressof.h>
543 #include <__cxx03/__memory/allocator.h>
544 #include <__cxx03/__type_traits/is_allocator.h>
545 #include <__cxx03/__utility/forward.h>
546 #include <__cxx03/version>
547
548 // standard-mandated includes
549
550 // [iterator.range]
551 #include <__cxx03/__iterator/access.h>
552
553 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
554 # pragma GCC system_header
555 #endif
556
557 _LIBCPP_PUSH_MACROS
558 #include <__cxx03/__undef_macros>
559
560 _LIBCPP_BEGIN_NAMESPACE_STD
561
562 template <class _Value, class _Hash, class _Pred, class _Alloc>
563 class unordered_multiset;
564
565 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
566 class _LIBCPP_TEMPLATE_VIS unordered_set {
567 public:
568 // types
569 typedef _Value key_type;
570 typedef key_type value_type;
571 typedef __type_identity_t<_Hash> hasher;
572 typedef __type_identity_t<_Pred> key_equal;
573 typedef __type_identity_t<_Alloc> allocator_type;
574 typedef value_type& reference;
575 typedef const value_type& const_reference;
576 static_assert(__check_valid_allocator<allocator_type>::value, "");
577 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
578 "Allocator::value_type must be same type as value_type");
579
580 private:
581 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
582
583 __table __table_;
584
585 public:
586 typedef typename __table::pointer pointer;
587 typedef typename __table::const_pointer const_pointer;
588 typedef typename __table::size_type size_type;
589 typedef typename __table::difference_type difference_type;
590
591 typedef typename __table::const_iterator iterator;
592 typedef typename __table::const_iterator const_iterator;
593 typedef typename __table::const_local_iterator local_iterator;
594 typedef typename __table::const_local_iterator const_local_iterator;
595
596 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
597 friend class _LIBCPP_TEMPLATE_VIS unordered_set;
598 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
599 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
600
601 _LIBCPP_HIDE_FROM_ABI unordered_set() {}
602 explicit _LIBCPP_HIDE_FROM_ABI
603 unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
604
605 _LIBCPP_HIDE_FROM_ABI
606 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
607 template <class _InputIterator>
608 _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last);
609 template <class _InputIterator>
610 _LIBCPP_HIDE_FROM_ABI
611 unordered_set(_InputIterator __first,
612 _InputIterator __last,
613 size_type __n,
614 const hasher& __hf = hasher(),
615 const key_equal& __eql = key_equal());
616 template <class _InputIterator>
617 _LIBCPP_HIDE_FROM_ABI unordered_set(
618 _InputIterator __first,
619 _InputIterator __last,
620 size_type __n,
621 const hasher& __hf,
622 const key_equal& __eql,
623 const allocator_type& __a);
624
625 _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a);
626 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u);
627 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a);
628
629 _LIBCPP_HIDE_FROM_ABI ~unordered_set() {
630 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
631 }
632
633 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) {
634 __table_ = __u.__table_;
635 return *this;
636 }
637
638 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
639 return allocator_type(__table_.__node_alloc());
640 }
641
642 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
643 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
644 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
645
646 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
647 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
648 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
649 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
650 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
651 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
652
653 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
654
655 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
656 template <class _InputIterator>
657 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
658
659 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
660 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
661 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
662 return __table_.erase(__first, __last);
663 }
664 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
665
666 _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) { __table_.swap(__u.__table_); }
667
668 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
669 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
670
671 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
672 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
673
674 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
675
676 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
677 return __table_.__equal_range_unique(__k);
678 }
679 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
680 return __table_.__equal_range_unique(__k);
681 }
682
683 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
684 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
685
686 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
687 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
688
689 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
690 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
691 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
692 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
693 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
694 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
695
696 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
697 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
698 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
699 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
700 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
701 };
702
703 template <class _Value, class _Hash, class _Pred, class _Alloc>
704 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql)
705 : __table_(__hf, __eql) {
706 __table_.__rehash_unique(__n);
707 }
708
709 template <class _Value, class _Hash, class _Pred, class _Alloc>
710 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
711 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
712 : __table_(__hf, __eql, __a) {
713 __table_.__rehash_unique(__n);
714 }
715
716 template <class _Value, class _Hash, class _Pred, class _Alloc>
717 template <class _InputIterator>
718 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) {
719 insert(__first, __last);
720 }
721
722 template <class _Value, class _Hash, class _Pred, class _Alloc>
723 template <class _InputIterator>
724 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
725 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
726 : __table_(__hf, __eql) {
727 __table_.__rehash_unique(__n);
728 insert(__first, __last);
729 }
730
731 template <class _Value, class _Hash, class _Pred, class _Alloc>
732 template <class _InputIterator>
733 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
734 _InputIterator __first,
735 _InputIterator __last,
736 size_type __n,
737 const hasher& __hf,
738 const key_equal& __eql,
739 const allocator_type& __a)
740 : __table_(__hf, __eql, __a) {
741 __table_.__rehash_unique(__n);
742 insert(__first, __last);
743 }
744
745 template <class _Value, class _Hash, class _Pred, class _Alloc>
746 inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {}
747
748 template <class _Value, class _Hash, class _Pred, class _Alloc>
749 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) {
750 __table_.__rehash_unique(__u.bucket_count());
751 insert(__u.begin(), __u.end());
752 }
753
754 template <class _Value, class _Hash, class _Pred, class _Alloc>
755 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a)
756 : __table_(__u.__table_, __a) {
757 __table_.__rehash_unique(__u.bucket_count());
758 insert(__u.begin(), __u.end());
759 }
760
761 template <class _Value, class _Hash, class _Pred, class _Alloc>
762 template <class _InputIterator>
763 inline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
764 for (; __first != __last; ++__first)
765 __table_.__insert_unique(*__first);
766 }
767
768 template <class _Value, class _Hash, class _Pred, class _Alloc>
769 inline _LIBCPP_HIDE_FROM_ABI void
770 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
771 __x.swap(__y);
772 }
773
774 template <class _Value, class _Hash, class _Pred, class _Alloc>
775 _LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
776 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
777 if (__x.size() != __y.size())
778 return false;
779 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
780 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
781 const_iterator __j = __y.find(*__i);
782 if (__j == __ey || !(*__i == *__j))
783 return false;
784 }
785 return true;
786 }
787
788 template <class _Value, class _Hash, class _Pred, class _Alloc>
789 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
790 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
791 return !(__x == __y);
792 }
793
794 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
795 class _LIBCPP_TEMPLATE_VIS unordered_multiset {
796 public:
797 // types
798 typedef _Value key_type;
799 typedef key_type value_type;
800 typedef __type_identity_t<_Hash> hasher;
801 typedef __type_identity_t<_Pred> key_equal;
802 typedef __type_identity_t<_Alloc> allocator_type;
803 typedef value_type& reference;
804 typedef const value_type& const_reference;
805 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
806 "Allocator::value_type must be same type as value_type");
807
808 private:
809 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
810
811 __table __table_;
812
813 public:
814 typedef typename __table::pointer pointer;
815 typedef typename __table::const_pointer const_pointer;
816 typedef typename __table::size_type size_type;
817 typedef typename __table::difference_type difference_type;
818
819 typedef typename __table::const_iterator iterator;
820 typedef typename __table::const_iterator const_iterator;
821 typedef typename __table::const_local_iterator local_iterator;
822 typedef typename __table::const_local_iterator const_local_iterator;
823
824 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
825 friend class _LIBCPP_TEMPLATE_VIS unordered_set;
826 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
827 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
828
829 _LIBCPP_HIDE_FROM_ABI unordered_multiset() {}
830 explicit _LIBCPP_HIDE_FROM_ABI
831 unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
832 _LIBCPP_HIDE_FROM_ABI
833 unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
834
835 template <class _InputIterator>
836 _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last);
837 template <class _InputIterator>
838 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
839 _InputIterator __first,
840 _InputIterator __last,
841 size_type __n,
842 const hasher& __hf = hasher(),
843 const key_equal& __eql = key_equal());
844 template <class _InputIterator>
845 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
846 _InputIterator __first,
847 _InputIterator __last,
848 size_type __n,
849 const hasher& __hf,
850 const key_equal& __eql,
851 const allocator_type& __a);
852
853 _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a);
854 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u);
855 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
856
857 _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() {
858 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
859 }
860
861 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) {
862 __table_ = __u.__table_;
863 return *this;
864 }
865
866 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
867 return allocator_type(__table_.__node_alloc());
868 }
869
870 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
871 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
872 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
873
874 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
875 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
876 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
877 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
878 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
879 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
880
881 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
882
883 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
884 return __table_.__insert_multi(__p, __x);
885 }
886
887 template <class _InputIterator>
888 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
889
890 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
891 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
892 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
893 return __table_.erase(__first, __last);
894 }
895 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
896
897 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) { __table_.swap(__u.__table_); }
898
899 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
900 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
901
902 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
903 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
904
905 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
906
907 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
908 return __table_.__equal_range_multi(__k);
909 }
910 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
911 return __table_.__equal_range_multi(__k);
912 }
913
914 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
915 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
916
917 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
918 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
919
920 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
921 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
922 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
923 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
924 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
925 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
926
927 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
928 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
929 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
930 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
931 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
932 };
933
934 template <class _Value, class _Hash, class _Pred, class _Alloc>
935 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
936 size_type __n, const hasher& __hf, const key_equal& __eql)
937 : __table_(__hf, __eql) {
938 __table_.__rehash_multi(__n);
939 }
940
941 template <class _Value, class _Hash, class _Pred, class _Alloc>
942 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
943 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
944 : __table_(__hf, __eql, __a) {
945 __table_.__rehash_multi(__n);
946 }
947
948 template <class _Value, class _Hash, class _Pred, class _Alloc>
949 template <class _InputIterator>
950 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) {
951 insert(__first, __last);
952 }
953
954 template <class _Value, class _Hash, class _Pred, class _Alloc>
955 template <class _InputIterator>
956 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
957 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
958 : __table_(__hf, __eql) {
959 __table_.__rehash_multi(__n);
960 insert(__first, __last);
961 }
962
963 template <class _Value, class _Hash, class _Pred, class _Alloc>
964 template <class _InputIterator>
965 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
966 _InputIterator __first,
967 _InputIterator __last,
968 size_type __n,
969 const hasher& __hf,
970 const key_equal& __eql,
971 const allocator_type& __a)
972 : __table_(__hf, __eql, __a) {
973 __table_.__rehash_multi(__n);
974 insert(__first, __last);
975 }
976
977 template <class _Value, class _Hash, class _Pred, class _Alloc>
978 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a)
979 : __table_(__a) {}
980
981 template <class _Value, class _Hash, class _Pred, class _Alloc>
982 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u)
983 : __table_(__u.__table_) {
984 __table_.__rehash_multi(__u.bucket_count());
985 insert(__u.begin(), __u.end());
986 }
987
988 template <class _Value, class _Hash, class _Pred, class _Alloc>
989 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
990 const unordered_multiset& __u, const allocator_type& __a)
991 : __table_(__u.__table_, __a) {
992 __table_.__rehash_multi(__u.bucket_count());
993 insert(__u.begin(), __u.end());
994 }
995
996 template <class _Value, class _Hash, class _Pred, class _Alloc>
997 template <class _InputIterator>
998 inline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
999 for (; __first != __last; ++__first)
1000 __table_.__insert_multi(*__first);
1001 }
1002
1003 template <class _Value, class _Hash, class _Pred, class _Alloc>
1004 inline _LIBCPP_HIDE_FROM_ABI void
1005 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1006 __x.swap(__y);
1007 }
1008
1009 template <class _Value, class _Hash, class _Pred, class _Alloc>
1010 _LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1011 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1012 if (__x.size() != __y.size())
1013 return false;
1014 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1015 typedef pair<const_iterator, const_iterator> _EqRng;
1016 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
1017 _EqRng __xeq = __x.equal_range(*__i);
1018 _EqRng __yeq = __y.equal_range(*__i);
1019 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
1020 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1021 return false;
1022 __i = __xeq.second;
1023 }
1024 return true;
1025 }
1026
1027 template <class _Value, class _Hash, class _Pred, class _Alloc>
1028 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1029 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1030 return !(__x == __y);
1031 }
1032
1033 _LIBCPP_END_NAMESPACE_STD
1034
1035 _LIBCPP_POP_MACROS
1036
1037 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)
1038 # include <__cxx03/cstdlib>
1039 # include <__cxx03/functional>
1040 # include <__cxx03/iterator>
1041 # include <__cxx03/stdexcept>
1042 # include <__cxx03/type_traits>
1043 #endif
1044
1045 #endif // _LIBCPP___CXX03_UNORDERED_SET