Line data Source code
1 : // unordered_set implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2010-2021 Free Software Foundation, Inc.
4 : //
5 : // This file is part of the GNU ISO C++ Library. This library is free
6 : // software; you can redistribute it and/or modify it under the
7 : // terms of the GNU General Public License as published by the
8 : // Free Software Foundation; either version 3, or (at your option)
9 : // any later version.
10 :
11 : // This library is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 :
16 : // Under Section 7 of GPL version 3, you are granted additional
17 : // permissions described in the GCC Runtime Library Exception, version
18 : // 3.1, as published by the Free Software Foundation.
19 :
20 : // You should have received a copy of the GNU General Public License and
21 : // a copy of the GCC Runtime Library Exception along with this program;
22 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 : // <http://www.gnu.org/licenses/>.
24 :
25 : /** @file bits/unordered_set.h
26 : * This is an internal header file, included by other library headers.
27 : * Do not attempt to use it directly. @headername{unordered_set}
28 : */
29 :
30 : #ifndef _UNORDERED_SET_H
31 : #define _UNORDERED_SET_H
32 :
33 : namespace std _GLIBCXX_VISIBILITY(default)
34 : {
35 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
36 : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
37 :
38 : /// Base types for unordered_set.
39 : template<bool _Cache>
40 : using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
41 :
42 : template<typename _Value,
43 : typename _Hash = hash<_Value>,
44 : typename _Pred = std::equal_to<_Value>,
45 : typename _Alloc = std::allocator<_Value>,
46 : typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
47 : using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
48 : __detail::_Identity, _Pred, _Hash,
49 : __detail::_Mod_range_hashing,
50 : __detail::_Default_ranged_hash,
51 : __detail::_Prime_rehash_policy, _Tr>;
52 :
53 : /// Base types for unordered_multiset.
54 : template<bool _Cache>
55 : using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
56 :
57 : template<typename _Value,
58 : typename _Hash = hash<_Value>,
59 : typename _Pred = std::equal_to<_Value>,
60 : typename _Alloc = std::allocator<_Value>,
61 : typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>>
62 : using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
63 : __detail::_Identity,
64 : _Pred, _Hash,
65 : __detail::_Mod_range_hashing,
66 : __detail::_Default_ranged_hash,
67 : __detail::_Prime_rehash_policy, _Tr>;
68 :
69 : template<class _Value, class _Hash, class _Pred, class _Alloc>
70 : class unordered_multiset;
71 :
72 : /**
73 : * @brief A standard container composed of unique keys (containing
74 : * at most one of each key value) in which the elements' keys are
75 : * the elements themselves.
76 : *
77 : * @ingroup unordered_associative_containers
78 : *
79 : * @tparam _Value Type of key objects.
80 : * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
81 :
82 : * @tparam _Pred Predicate function object type, defaults to
83 : * equal_to<_Value>.
84 : *
85 : * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
86 : *
87 : * Meets the requirements of a <a href="tables.html#65">container</a>, and
88 : * <a href="tables.html#xx">unordered associative container</a>
89 : *
90 : * Base is _Hashtable, dispatched at compile time via template
91 : * alias __uset_hashtable.
92 : */
93 : template<typename _Value,
94 : typename _Hash = hash<_Value>,
95 : typename _Pred = equal_to<_Value>,
96 : typename _Alloc = allocator<_Value>>
97 : class unordered_set
98 : {
99 : typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
100 : _Hashtable _M_h;
101 :
102 : public:
103 : // typedefs:
104 : ///@{
105 : /// Public typedefs.
106 : typedef typename _Hashtable::key_type key_type;
107 : typedef typename _Hashtable::value_type value_type;
108 : typedef typename _Hashtable::hasher hasher;
109 : typedef typename _Hashtable::key_equal key_equal;
110 : typedef typename _Hashtable::allocator_type allocator_type;
111 : ///@}
112 :
113 : ///@{
114 : /// Iterator-related typedefs.
115 : typedef typename _Hashtable::pointer pointer;
116 : typedef typename _Hashtable::const_pointer const_pointer;
117 : typedef typename _Hashtable::reference reference;
118 : typedef typename _Hashtable::const_reference const_reference;
119 : typedef typename _Hashtable::iterator iterator;
120 : typedef typename _Hashtable::const_iterator const_iterator;
121 : typedef typename _Hashtable::local_iterator local_iterator;
122 : typedef typename _Hashtable::const_local_iterator const_local_iterator;
123 : typedef typename _Hashtable::size_type size_type;
124 : typedef typename _Hashtable::difference_type difference_type;
125 : ///@}
126 :
127 : #if __cplusplus > 201402L
128 : using node_type = typename _Hashtable::node_type;
129 : using insert_return_type = typename _Hashtable::insert_return_type;
130 : #endif
131 :
132 : // construct/destroy/copy
133 :
134 : /// Default constructor.
135 286 : unordered_set() = default;
136 :
137 : /**
138 : * @brief Default constructor creates no elements.
139 : * @param __n Minimal initial number of buckets.
140 : * @param __hf A hash functor.
141 : * @param __eql A key equality functor.
142 : * @param __a An allocator object.
143 : */
144 : explicit
145 : unordered_set(size_type __n,
146 : const hasher& __hf = hasher(),
147 : const key_equal& __eql = key_equal(),
148 : const allocator_type& __a = allocator_type())
149 : : _M_h(__n, __hf, __eql, __a)
150 : { }
151 :
152 : /**
153 : * @brief Builds an %unordered_set from a range.
154 : * @param __first An input iterator.
155 : * @param __last An input iterator.
156 : * @param __n Minimal initial number of buckets.
157 : * @param __hf A hash functor.
158 : * @param __eql A key equality functor.
159 : * @param __a An allocator object.
160 : *
161 : * Create an %unordered_set consisting of copies of the elements from
162 : * [__first,__last). This is linear in N (where N is
163 : * distance(__first,__last)).
164 : */
165 : template<typename _InputIterator>
166 : unordered_set(_InputIterator __first, _InputIterator __last,
167 : size_type __n = 0,
168 : const hasher& __hf = hasher(),
169 : const key_equal& __eql = key_equal(),
170 : const allocator_type& __a = allocator_type())
171 : : _M_h(__first, __last, __n, __hf, __eql, __a)
172 : { }
173 :
174 : /// Copy constructor.
175 : unordered_set(const unordered_set&) = default;
176 :
177 : /// Move constructor.
178 : unordered_set(unordered_set&&) = default;
179 :
180 : /**
181 : * @brief Creates an %unordered_set with no elements.
182 : * @param __a An allocator object.
183 : */
184 : explicit
185 : unordered_set(const allocator_type& __a)
186 : : _M_h(__a)
187 : { }
188 :
189 : /*
190 : * @brief Copy constructor with allocator argument.
191 : * @param __uset Input %unordered_set to copy.
192 : * @param __a An allocator object.
193 : */
194 : unordered_set(const unordered_set& __uset,
195 : const allocator_type& __a)
196 : : _M_h(__uset._M_h, __a)
197 : { }
198 :
199 : /*
200 : * @brief Move constructor with allocator argument.
201 : * @param __uset Input %unordered_set to move.
202 : * @param __a An allocator object.
203 : */
204 : unordered_set(unordered_set&& __uset,
205 : const allocator_type& __a)
206 : noexcept( noexcept(_Hashtable(std::move(__uset._M_h), __a)) )
207 : : _M_h(std::move(__uset._M_h), __a)
208 : { }
209 :
210 : /**
211 : * @brief Builds an %unordered_set from an initializer_list.
212 : * @param __l An initializer_list.
213 : * @param __n Minimal initial number of buckets.
214 : * @param __hf A hash functor.
215 : * @param __eql A key equality functor.
216 : * @param __a An allocator object.
217 : *
218 : * Create an %unordered_set consisting of copies of the elements in the
219 : * list. This is linear in N (where N is @a __l.size()).
220 : */
221 : unordered_set(initializer_list<value_type> __l,
222 : size_type __n = 0,
223 : const hasher& __hf = hasher(),
224 : const key_equal& __eql = key_equal(),
225 : const allocator_type& __a = allocator_type())
226 : : _M_h(__l, __n, __hf, __eql, __a)
227 : { }
228 :
229 : unordered_set(size_type __n, const allocator_type& __a)
230 : : unordered_set(__n, hasher(), key_equal(), __a)
231 : { }
232 :
233 : unordered_set(size_type __n, const hasher& __hf,
234 : const allocator_type& __a)
235 : : unordered_set(__n, __hf, key_equal(), __a)
236 : { }
237 :
238 : template<typename _InputIterator>
239 : unordered_set(_InputIterator __first, _InputIterator __last,
240 : size_type __n,
241 : const allocator_type& __a)
242 : : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
243 : { }
244 :
245 : template<typename _InputIterator>
246 : unordered_set(_InputIterator __first, _InputIterator __last,
247 : size_type __n, const hasher& __hf,
248 : const allocator_type& __a)
249 : : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
250 : { }
251 :
252 : unordered_set(initializer_list<value_type> __l,
253 : size_type __n,
254 : const allocator_type& __a)
255 : : unordered_set(__l, __n, hasher(), key_equal(), __a)
256 : { }
257 :
258 : unordered_set(initializer_list<value_type> __l,
259 : size_type __n, const hasher& __hf,
260 : const allocator_type& __a)
261 : : unordered_set(__l, __n, __hf, key_equal(), __a)
262 : { }
263 :
264 : /// Copy assignment operator.
265 : unordered_set&
266 : operator=(const unordered_set&) = default;
267 :
268 : /// Move assignment operator.
269 : unordered_set&
270 : operator=(unordered_set&&) = default;
271 :
272 : /**
273 : * @brief %Unordered_set list assignment operator.
274 : * @param __l An initializer_list.
275 : *
276 : * This function fills an %unordered_set with copies of the elements in
277 : * the initializer list @a __l.
278 : *
279 : * Note that the assignment completely changes the %unordered_set and
280 : * that the resulting %unordered_set's size is the same as the number
281 : * of elements assigned.
282 : */
283 : unordered_set&
284 : operator=(initializer_list<value_type> __l)
285 : {
286 : _M_h = __l;
287 : return *this;
288 : }
289 :
290 : /// Returns the allocator object used by the %unordered_set.
291 : allocator_type
292 : get_allocator() const noexcept
293 : { return _M_h.get_allocator(); }
294 :
295 : // size and capacity:
296 :
297 : /// Returns true if the %unordered_set is empty.
298 : _GLIBCXX_NODISCARD bool
299 : empty() const noexcept
300 : { return _M_h.empty(); }
301 :
302 : /// Returns the size of the %unordered_set.
303 : size_type
304 : size() const noexcept
305 : { return _M_h.size(); }
306 :
307 : /// Returns the maximum size of the %unordered_set.
308 : size_type
309 : max_size() const noexcept
310 : { return _M_h.max_size(); }
311 :
312 : // iterators.
313 :
314 : ///@{
315 : /**
316 : * Returns a read-only (constant) iterator that points to the first
317 : * element in the %unordered_set.
318 : */
319 : iterator
320 : begin() noexcept
321 : { return _M_h.begin(); }
322 :
323 : const_iterator
324 : begin() const noexcept
325 : { return _M_h.begin(); }
326 : ///@}
327 :
328 : ///@{
329 : /**
330 : * Returns a read-only (constant) iterator that points one past the last
331 : * element in the %unordered_set.
332 : */
333 : iterator
334 2 : end() noexcept
335 2 : { return _M_h.end(); }
336 :
337 : const_iterator
338 : end() const noexcept
339 : { return _M_h.end(); }
340 : ///@}
341 :
342 : /**
343 : * Returns a read-only (constant) iterator that points to the first
344 : * element in the %unordered_set.
345 : */
346 : const_iterator
347 : cbegin() const noexcept
348 : { return _M_h.begin(); }
349 :
350 : /**
351 : * Returns a read-only (constant) iterator that points one past the last
352 : * element in the %unordered_set.
353 : */
354 : const_iterator
355 : cend() const noexcept
356 : { return _M_h.end(); }
357 :
358 : // modifiers.
359 :
360 : /**
361 : * @brief Attempts to build and insert an element into the
362 : * %unordered_set.
363 : * @param __args Arguments used to generate an element.
364 : * @return A pair, of which the first element is an iterator that points
365 : * to the possibly inserted element, and the second is a bool
366 : * that is true if the element was actually inserted.
367 : *
368 : * This function attempts to build and insert an element into the
369 : * %unordered_set. An %unordered_set relies on unique keys and thus an
370 : * element is only inserted if it is not already present in the
371 : * %unordered_set.
372 : *
373 : * Insertion requires amortized constant time.
374 : */
375 : template<typename... _Args>
376 : std::pair<iterator, bool>
377 738 : emplace(_Args&&... __args)
378 738 : { return _M_h.emplace(std::forward<_Args>(__args)...); }
379 :
380 : /**
381 : * @brief Attempts to insert an element into the %unordered_set.
382 : * @param __pos An iterator that serves as a hint as to where the
383 : * element should be inserted.
384 : * @param __args Arguments used to generate the element to be
385 : * inserted.
386 : * @return An iterator that points to the element with key equivalent to
387 : * the one generated from @a __args (may or may not be the
388 : * element itself).
389 : *
390 : * This function is not concerned about whether the insertion took place,
391 : * and thus does not return a boolean like the single-argument emplace()
392 : * does. Note that the first parameter is only a hint and can
393 : * potentially improve the performance of the insertion process. A bad
394 : * hint would cause no gains in efficiency.
395 : *
396 : * For more on @a hinting, see:
397 : * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
398 : *
399 : * Insertion requires amortized constant time.
400 : */
401 : template<typename... _Args>
402 : iterator
403 : emplace_hint(const_iterator __pos, _Args&&... __args)
404 : { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
405 :
406 : ///@{
407 : /**
408 : * @brief Attempts to insert an element into the %unordered_set.
409 : * @param __x Element to be inserted.
410 : * @return A pair, of which the first element is an iterator that points
411 : * to the possibly inserted element, and the second is a bool
412 : * that is true if the element was actually inserted.
413 : *
414 : * This function attempts to insert an element into the %unordered_set.
415 : * An %unordered_set relies on unique keys and thus an element is only
416 : * inserted if it is not already present in the %unordered_set.
417 : *
418 : * Insertion requires amortized constant time.
419 : */
420 : std::pair<iterator, bool>
421 : insert(const value_type& __x)
422 : { return _M_h.insert(__x); }
423 :
424 : std::pair<iterator, bool>
425 : insert(value_type&& __x)
426 : { return _M_h.insert(std::move(__x)); }
427 : ///@}
428 :
429 : ///@{
430 : /**
431 : * @brief Attempts to insert an element into the %unordered_set.
432 : * @param __hint An iterator that serves as a hint as to where the
433 : * element should be inserted.
434 : * @param __x Element to be inserted.
435 : * @return An iterator that points to the element with key of
436 : * @a __x (may or may not be the element passed in).
437 : *
438 : * This function is not concerned about whether the insertion took place,
439 : * and thus does not return a boolean like the single-argument insert()
440 : * does. Note that the first parameter is only a hint and can
441 : * potentially improve the performance of the insertion process. A bad
442 : * hint would cause no gains in efficiency.
443 : *
444 : * For more on @a hinting, see:
445 : * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
446 : *
447 : * Insertion requires amortized constant.
448 : */
449 : iterator
450 : insert(const_iterator __hint, const value_type& __x)
451 : { return _M_h.insert(__hint, __x); }
452 :
453 : iterator
454 : insert(const_iterator __hint, value_type&& __x)
455 : { return _M_h.insert(__hint, std::move(__x)); }
456 : ///@}
457 :
458 : /**
459 : * @brief A template function that attempts to insert a range of
460 : * elements.
461 : * @param __first Iterator pointing to the start of the range to be
462 : * inserted.
463 : * @param __last Iterator pointing to the end of the range.
464 : *
465 : * Complexity similar to that of the range constructor.
466 : */
467 : template<typename _InputIterator>
468 : void
469 : insert(_InputIterator __first, _InputIterator __last)
470 : { _M_h.insert(__first, __last); }
471 :
472 : /**
473 : * @brief Attempts to insert a list of elements into the %unordered_set.
474 : * @param __l A std::initializer_list<value_type> of elements
475 : * to be inserted.
476 : *
477 : * Complexity similar to that of the range constructor.
478 : */
479 : void
480 : insert(initializer_list<value_type> __l)
481 : { _M_h.insert(__l); }
482 :
483 : #if __cplusplus > 201402L
484 : /// Extract a node.
485 : node_type
486 : extract(const_iterator __pos)
487 : {
488 : __glibcxx_assert(__pos != end());
489 : return _M_h.extract(__pos);
490 : }
491 :
492 : /// Extract a node.
493 : node_type
494 : extract(const key_type& __key)
495 : { return _M_h.extract(__key); }
496 :
497 : /// Re-insert an extracted node.
498 : insert_return_type
499 : insert(node_type&& __nh)
500 : { return _M_h._M_reinsert_node(std::move(__nh)); }
501 :
502 : /// Re-insert an extracted node.
503 : iterator
504 : insert(const_iterator, node_type&& __nh)
505 : { return _M_h._M_reinsert_node(std::move(__nh)).position; }
506 : #endif // C++17
507 :
508 : ///@{
509 : /**
510 : * @brief Erases an element from an %unordered_set.
511 : * @param __position An iterator pointing to the element to be erased.
512 : * @return An iterator pointing to the element immediately following
513 : * @a __position prior to the element being erased. If no such
514 : * element exists, end() is returned.
515 : *
516 : * This function erases an element, pointed to by the given iterator,
517 : * from an %unordered_set. Note that this function only erases the
518 : * element, and that if the element is itself a pointer, the pointed-to
519 : * memory is not touched in any way. Managing the pointer is the user's
520 : * responsibility.
521 : */
522 : iterator
523 : erase(const_iterator __position)
524 : { return _M_h.erase(__position); }
525 :
526 : // LWG 2059.
527 : iterator
528 : erase(iterator __position)
529 : { return _M_h.erase(__position); }
530 : ///@}
531 :
532 : /**
533 : * @brief Erases elements according to the provided key.
534 : * @param __x Key of element to be erased.
535 : * @return The number of elements erased.
536 : *
537 : * This function erases all the elements located by the given key from
538 : * an %unordered_set. For an %unordered_set the result of this function
539 : * can only be 0 (not present) or 1 (present).
540 : * Note that this function only erases the element, and that if
541 : * the element is itself a pointer, the pointed-to memory is not touched
542 : * in any way. Managing the pointer is the user's responsibility.
543 : */
544 : size_type
545 : erase(const key_type& __x)
546 : { return _M_h.erase(__x); }
547 :
548 : /**
549 : * @brief Erases a [__first,__last) range of elements from an
550 : * %unordered_set.
551 : * @param __first Iterator pointing to the start of the range to be
552 : * erased.
553 : * @param __last Iterator pointing to the end of the range to
554 : * be erased.
555 : * @return The iterator @a __last.
556 : *
557 : * This function erases a sequence of elements from an %unordered_set.
558 : * Note that this function only erases the element, and that if
559 : * the element is itself a pointer, the pointed-to memory is not touched
560 : * in any way. Managing the pointer is the user's responsibility.
561 : */
562 : iterator
563 : erase(const_iterator __first, const_iterator __last)
564 : { return _M_h.erase(__first, __last); }
565 :
566 : /**
567 : * Erases all elements in an %unordered_set. Note that this function only
568 : * erases the elements, and that if the elements themselves are pointers,
569 : * the pointed-to memory is not touched in any way. Managing the pointer
570 : * is the user's responsibility.
571 : */
572 : void
573 : clear() noexcept
574 : { _M_h.clear(); }
575 :
576 : /**
577 : * @brief Swaps data with another %unordered_set.
578 : * @param __x An %unordered_set of the same element and allocator
579 : * types.
580 : *
581 : * This exchanges the elements between two sets in constant time.
582 : * Note that the global std::swap() function is specialized such that
583 : * std::swap(s1,s2) will feed to this function.
584 : */
585 : void
586 : swap(unordered_set& __x)
587 : noexcept( noexcept(_M_h.swap(__x._M_h)) )
588 : { _M_h.swap(__x._M_h); }
589 :
590 : #if __cplusplus > 201402L
591 : template<typename, typename, typename>
592 : friend class std::_Hash_merge_helper;
593 :
594 : template<typename _H2, typename _P2>
595 : void
596 : merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
597 : {
598 : using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
599 : _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
600 : }
601 :
602 : template<typename _H2, typename _P2>
603 : void
604 : merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
605 : { merge(__source); }
606 :
607 : template<typename _H2, typename _P2>
608 : void
609 : merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
610 : {
611 : using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
612 : _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
613 : }
614 :
615 : template<typename _H2, typename _P2>
616 : void
617 : merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
618 : { merge(__source); }
619 : #endif // C++17
620 :
621 : // observers.
622 :
623 : /// Returns the hash functor object with which the %unordered_set was
624 : /// constructed.
625 : hasher
626 : hash_function() const
627 : { return _M_h.hash_function(); }
628 :
629 : /// Returns the key comparison object with which the %unordered_set was
630 : /// constructed.
631 : key_equal
632 : key_eq() const
633 : { return _M_h.key_eq(); }
634 :
635 : // lookup.
636 :
637 : ///@{
638 : /**
639 : * @brief Tries to locate an element in an %unordered_set.
640 : * @param __x Element to be located.
641 : * @return Iterator pointing to sought-after element, or end() if not
642 : * found.
643 : *
644 : * This function takes a key and tries to locate the element with which
645 : * the key matches. If successful the function returns an iterator
646 : * pointing to the sought after element. If unsuccessful it returns the
647 : * past-the-end ( @c end() ) iterator.
648 : */
649 : iterator
650 2 : find(const key_type& __x)
651 2 : { return _M_h.find(__x); }
652 :
653 : #if __cplusplus > 201703L
654 : template<typename _Kt>
655 : auto
656 : find(const _Kt& __k)
657 : -> decltype(_M_h._M_find_tr(__k))
658 : { return _M_h._M_find_tr(__k); }
659 : #endif
660 :
661 : const_iterator
662 : find(const key_type& __x) const
663 : { return _M_h.find(__x); }
664 :
665 : #if __cplusplus > 201703L
666 : template<typename _Kt>
667 : auto
668 : find(const _Kt& __k) const
669 : -> decltype(_M_h._M_find_tr(__k))
670 : { return _M_h._M_find_tr(__k); }
671 : #endif
672 : ///@}
673 :
674 : ///@{
675 : /**
676 : * @brief Finds the number of elements.
677 : * @param __x Element to located.
678 : * @return Number of elements with specified key.
679 : *
680 : * This function only makes sense for unordered_multisets; for
681 : * unordered_set the result will either be 0 (not present) or 1
682 : * (present).
683 : */
684 : size_type
685 : count(const key_type& __x) const
686 : { return _M_h.count(__x); }
687 :
688 : #if __cplusplus > 201703L
689 : template<typename _Kt>
690 : auto
691 : count(const _Kt& __k) const
692 : -> decltype(_M_h._M_count_tr(__k))
693 : { return _M_h._M_count_tr(__k); }
694 : #endif
695 : ///@}
696 :
697 : #if __cplusplus > 201703L
698 : ///@{
699 : /**
700 : * @brief Finds whether an element with the given key exists.
701 : * @param __x Key of elements to be located.
702 : * @return True if there is any element with the specified key.
703 : */
704 : bool
705 : contains(const key_type& __x) const
706 : { return _M_h.find(__x) != _M_h.end(); }
707 :
708 : template<typename _Kt>
709 : auto
710 : contains(const _Kt& __k) const
711 : -> decltype(_M_h._M_find_tr(__k), void(), true)
712 : { return _M_h._M_find_tr(__k) != _M_h.end(); }
713 : ///@}
714 : #endif
715 :
716 : ///@{
717 : /**
718 : * @brief Finds a subsequence matching given key.
719 : * @param __x Key to be located.
720 : * @return Pair of iterators that possibly points to the subsequence
721 : * matching given key.
722 : *
723 : * This function probably only makes sense for multisets.
724 : */
725 : std::pair<iterator, iterator>
726 : equal_range(const key_type& __x)
727 : { return _M_h.equal_range(__x); }
728 :
729 : #if __cplusplus > 201703L
730 : template<typename _Kt>
731 : auto
732 : equal_range(const _Kt& __k)
733 : -> decltype(_M_h._M_equal_range_tr(__k))
734 : { return _M_h._M_equal_range_tr(__k); }
735 : #endif
736 :
737 : std::pair<const_iterator, const_iterator>
738 : equal_range(const key_type& __x) const
739 : { return _M_h.equal_range(__x); }
740 :
741 : #if __cplusplus > 201703L
742 : template<typename _Kt>
743 : auto
744 : equal_range(const _Kt& __k) const
745 : -> decltype(_M_h._M_equal_range_tr(__k))
746 : { return _M_h._M_equal_range_tr(__k); }
747 : #endif
748 : ///@}
749 :
750 : // bucket interface.
751 :
752 : /// Returns the number of buckets of the %unordered_set.
753 : size_type
754 : bucket_count() const noexcept
755 : { return _M_h.bucket_count(); }
756 :
757 : /// Returns the maximum number of buckets of the %unordered_set.
758 : size_type
759 : max_bucket_count() const noexcept
760 : { return _M_h.max_bucket_count(); }
761 :
762 : /*
763 : * @brief Returns the number of elements in a given bucket.
764 : * @param __n A bucket index.
765 : * @return The number of elements in the bucket.
766 : */
767 : size_type
768 : bucket_size(size_type __n) const
769 : { return _M_h.bucket_size(__n); }
770 :
771 : /*
772 : * @brief Returns the bucket index of a given element.
773 : * @param __key A key instance.
774 : * @return The key bucket index.
775 : */
776 : size_type
777 : bucket(const key_type& __key) const
778 : { return _M_h.bucket(__key); }
779 :
780 : ///@{
781 : /**
782 : * @brief Returns a read-only (constant) iterator pointing to the first
783 : * bucket element.
784 : * @param __n The bucket index.
785 : * @return A read-only local iterator.
786 : */
787 : local_iterator
788 : begin(size_type __n)
789 : { return _M_h.begin(__n); }
790 :
791 : const_local_iterator
792 : begin(size_type __n) const
793 : { return _M_h.begin(__n); }
794 :
795 : const_local_iterator
796 : cbegin(size_type __n) const
797 : { return _M_h.cbegin(__n); }
798 : ///@}
799 :
800 : ///@{
801 : /**
802 : * @brief Returns a read-only (constant) iterator pointing to one past
803 : * the last bucket elements.
804 : * @param __n The bucket index.
805 : * @return A read-only local iterator.
806 : */
807 : local_iterator
808 : end(size_type __n)
809 : { return _M_h.end(__n); }
810 :
811 : const_local_iterator
812 : end(size_type __n) const
813 : { return _M_h.end(__n); }
814 :
815 : const_local_iterator
816 : cend(size_type __n) const
817 : { return _M_h.cend(__n); }
818 : ///@}
819 :
820 : // hash policy.
821 :
822 : /// Returns the average number of elements per bucket.
823 : float
824 : load_factor() const noexcept
825 : { return _M_h.load_factor(); }
826 :
827 : /// Returns a positive number that the %unordered_set tries to keep the
828 : /// load factor less than or equal to.
829 : float
830 : max_load_factor() const noexcept
831 : { return _M_h.max_load_factor(); }
832 :
833 : /**
834 : * @brief Change the %unordered_set maximum load factor.
835 : * @param __z The new maximum load factor.
836 : */
837 : void
838 : max_load_factor(float __z)
839 : { _M_h.max_load_factor(__z); }
840 :
841 : /**
842 : * @brief May rehash the %unordered_set.
843 : * @param __n The new number of buckets.
844 : *
845 : * Rehash will occur only if the new number of buckets respect the
846 : * %unordered_set maximum load factor.
847 : */
848 : void
849 : rehash(size_type __n)
850 : { _M_h.rehash(__n); }
851 :
852 : /**
853 : * @brief Prepare the %unordered_set for a specified number of
854 : * elements.
855 : * @param __n Number of elements required.
856 : *
857 : * Same as rehash(ceil(n / max_load_factor())).
858 : */
859 : void
860 : reserve(size_type __n)
861 : { _M_h.reserve(__n); }
862 :
863 : template<typename _Value1, typename _Hash1, typename _Pred1,
864 : typename _Alloc1>
865 : friend bool
866 : operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&,
867 : const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&);
868 : };
869 :
870 : #if __cpp_deduction_guides >= 201606
871 :
872 : template<typename _InputIterator,
873 : typename _Hash =
874 : hash<typename iterator_traits<_InputIterator>::value_type>,
875 : typename _Pred =
876 : equal_to<typename iterator_traits<_InputIterator>::value_type>,
877 : typename _Allocator =
878 : allocator<typename iterator_traits<_InputIterator>::value_type>,
879 : typename = _RequireInputIter<_InputIterator>,
880 : typename = _RequireNotAllocatorOrIntegral<_Hash>,
881 : typename = _RequireNotAllocator<_Pred>,
882 : typename = _RequireAllocator<_Allocator>>
883 : unordered_set(_InputIterator, _InputIterator,
884 : unordered_set<int>::size_type = {},
885 : _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
886 : -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
887 : _Hash, _Pred, _Allocator>;
888 :
889 : template<typename _Tp, typename _Hash = hash<_Tp>,
890 : typename _Pred = equal_to<_Tp>,
891 : typename _Allocator = allocator<_Tp>,
892 : typename = _RequireNotAllocatorOrIntegral<_Hash>,
893 : typename = _RequireNotAllocator<_Pred>,
894 : typename = _RequireAllocator<_Allocator>>
895 : unordered_set(initializer_list<_Tp>,
896 : unordered_set<int>::size_type = {},
897 : _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
898 : -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
899 :
900 : template<typename _InputIterator, typename _Allocator,
901 : typename = _RequireInputIter<_InputIterator>,
902 : typename = _RequireAllocator<_Allocator>>
903 : unordered_set(_InputIterator, _InputIterator,
904 : unordered_set<int>::size_type, _Allocator)
905 : -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
906 : hash<
907 : typename iterator_traits<_InputIterator>::value_type>,
908 : equal_to<
909 : typename iterator_traits<_InputIterator>::value_type>,
910 : _Allocator>;
911 :
912 : template<typename _InputIterator, typename _Hash, typename _Allocator,
913 : typename = _RequireInputIter<_InputIterator>,
914 : typename = _RequireNotAllocatorOrIntegral<_Hash>,
915 : typename = _RequireAllocator<_Allocator>>
916 : unordered_set(_InputIterator, _InputIterator,
917 : unordered_set<int>::size_type,
918 : _Hash, _Allocator)
919 : -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
920 : _Hash,
921 : equal_to<
922 : typename iterator_traits<_InputIterator>::value_type>,
923 : _Allocator>;
924 :
925 : template<typename _Tp, typename _Allocator,
926 : typename = _RequireAllocator<_Allocator>>
927 : unordered_set(initializer_list<_Tp>,
928 : unordered_set<int>::size_type, _Allocator)
929 : -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
930 :
931 : template<typename _Tp, typename _Hash, typename _Allocator,
932 : typename = _RequireNotAllocatorOrIntegral<_Hash>,
933 : typename = _RequireAllocator<_Allocator>>
934 : unordered_set(initializer_list<_Tp>,
935 : unordered_set<int>::size_type, _Hash, _Allocator)
936 : -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
937 :
938 : #endif
939 :
940 : /**
941 : * @brief A standard container composed of equivalent keys
942 : * (possibly containing multiple of each key value) in which the
943 : * elements' keys are the elements themselves.
944 : *
945 : * @ingroup unordered_associative_containers
946 : *
947 : * @tparam _Value Type of key objects.
948 : * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
949 : * @tparam _Pred Predicate function object type, defaults
950 : * to equal_to<_Value>.
951 : * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
952 : *
953 : * Meets the requirements of a <a href="tables.html#65">container</a>, and
954 : * <a href="tables.html#xx">unordered associative container</a>
955 : *
956 : * Base is _Hashtable, dispatched at compile time via template
957 : * alias __umset_hashtable.
958 : */
959 : template<typename _Value,
960 : typename _Hash = hash<_Value>,
961 : typename _Pred = equal_to<_Value>,
962 : typename _Alloc = allocator<_Value>>
963 : class unordered_multiset
964 : {
965 : typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
966 : _Hashtable _M_h;
967 :
968 : public:
969 : // typedefs:
970 : ///@{
971 : /// Public typedefs.
972 : typedef typename _Hashtable::key_type key_type;
973 : typedef typename _Hashtable::value_type value_type;
974 : typedef typename _Hashtable::hasher hasher;
975 : typedef typename _Hashtable::key_equal key_equal;
976 : typedef typename _Hashtable::allocator_type allocator_type;
977 : ///@}
978 :
979 : ///@{
980 : /// Iterator-related typedefs.
981 : typedef typename _Hashtable::pointer pointer;
982 : typedef typename _Hashtable::const_pointer const_pointer;
983 : typedef typename _Hashtable::reference reference;
984 : typedef typename _Hashtable::const_reference const_reference;
985 : typedef typename _Hashtable::iterator iterator;
986 : typedef typename _Hashtable::const_iterator const_iterator;
987 : typedef typename _Hashtable::local_iterator local_iterator;
988 : typedef typename _Hashtable::const_local_iterator const_local_iterator;
989 : typedef typename _Hashtable::size_type size_type;
990 : typedef typename _Hashtable::difference_type difference_type;
991 : ///@}
992 :
993 : #if __cplusplus > 201402L
994 : using node_type = typename _Hashtable::node_type;
995 : #endif
996 :
997 : // construct/destroy/copy
998 :
999 : /// Default constructor.
1000 : unordered_multiset() = default;
1001 :
1002 : /**
1003 : * @brief Default constructor creates no elements.
1004 : * @param __n Minimal initial number of buckets.
1005 : * @param __hf A hash functor.
1006 : * @param __eql A key equality functor.
1007 : * @param __a An allocator object.
1008 : */
1009 : explicit
1010 : unordered_multiset(size_type __n,
1011 : const hasher& __hf = hasher(),
1012 : const key_equal& __eql = key_equal(),
1013 : const allocator_type& __a = allocator_type())
1014 : : _M_h(__n, __hf, __eql, __a)
1015 : { }
1016 :
1017 : /**
1018 : * @brief Builds an %unordered_multiset from a range.
1019 : * @param __first An input iterator.
1020 : * @param __last An input iterator.
1021 : * @param __n Minimal initial number of buckets.
1022 : * @param __hf A hash functor.
1023 : * @param __eql A key equality functor.
1024 : * @param __a An allocator object.
1025 : *
1026 : * Create an %unordered_multiset consisting of copies of the elements
1027 : * from [__first,__last). This is linear in N (where N is
1028 : * distance(__first,__last)).
1029 : */
1030 : template<typename _InputIterator>
1031 : unordered_multiset(_InputIterator __first, _InputIterator __last,
1032 : size_type __n = 0,
1033 : const hasher& __hf = hasher(),
1034 : const key_equal& __eql = key_equal(),
1035 : const allocator_type& __a = allocator_type())
1036 : : _M_h(__first, __last, __n, __hf, __eql, __a)
1037 : { }
1038 :
1039 : /// Copy constructor.
1040 : unordered_multiset(const unordered_multiset&) = default;
1041 :
1042 : /// Move constructor.
1043 : unordered_multiset(unordered_multiset&&) = default;
1044 :
1045 : /**
1046 : * @brief Builds an %unordered_multiset from an initializer_list.
1047 : * @param __l An initializer_list.
1048 : * @param __n Minimal initial number of buckets.
1049 : * @param __hf A hash functor.
1050 : * @param __eql A key equality functor.
1051 : * @param __a An allocator object.
1052 : *
1053 : * Create an %unordered_multiset consisting of copies of the elements in
1054 : * the list. This is linear in N (where N is @a __l.size()).
1055 : */
1056 : unordered_multiset(initializer_list<value_type> __l,
1057 : size_type __n = 0,
1058 : const hasher& __hf = hasher(),
1059 : const key_equal& __eql = key_equal(),
1060 : const allocator_type& __a = allocator_type())
1061 : : _M_h(__l, __n, __hf, __eql, __a)
1062 : { }
1063 :
1064 : /// Copy assignment operator.
1065 : unordered_multiset&
1066 : operator=(const unordered_multiset&) = default;
1067 :
1068 : /// Move assignment operator.
1069 : unordered_multiset&
1070 : operator=(unordered_multiset&&) = default;
1071 :
1072 : /**
1073 : * @brief Creates an %unordered_multiset with no elements.
1074 : * @param __a An allocator object.
1075 : */
1076 : explicit
1077 : unordered_multiset(const allocator_type& __a)
1078 : : _M_h(__a)
1079 : { }
1080 :
1081 : /*
1082 : * @brief Copy constructor with allocator argument.
1083 : * @param __uset Input %unordered_multiset to copy.
1084 : * @param __a An allocator object.
1085 : */
1086 : unordered_multiset(const unordered_multiset& __umset,
1087 : const allocator_type& __a)
1088 : : _M_h(__umset._M_h, __a)
1089 : { }
1090 :
1091 : /*
1092 : * @brief Move constructor with allocator argument.
1093 : * @param __umset Input %unordered_multiset to move.
1094 : * @param __a An allocator object.
1095 : */
1096 : unordered_multiset(unordered_multiset&& __umset,
1097 : const allocator_type& __a)
1098 : noexcept( noexcept(_Hashtable(std::move(__umset._M_h), __a)) )
1099 : : _M_h(std::move(__umset._M_h), __a)
1100 : { }
1101 :
1102 : unordered_multiset(size_type __n, const allocator_type& __a)
1103 : : unordered_multiset(__n, hasher(), key_equal(), __a)
1104 : { }
1105 :
1106 : unordered_multiset(size_type __n, const hasher& __hf,
1107 : const allocator_type& __a)
1108 : : unordered_multiset(__n, __hf, key_equal(), __a)
1109 : { }
1110 :
1111 : template<typename _InputIterator>
1112 : unordered_multiset(_InputIterator __first, _InputIterator __last,
1113 : size_type __n,
1114 : const allocator_type& __a)
1115 : : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
1116 : { }
1117 :
1118 : template<typename _InputIterator>
1119 : unordered_multiset(_InputIterator __first, _InputIterator __last,
1120 : size_type __n, const hasher& __hf,
1121 : const allocator_type& __a)
1122 : : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
1123 : { }
1124 :
1125 : unordered_multiset(initializer_list<value_type> __l,
1126 : size_type __n,
1127 : const allocator_type& __a)
1128 : : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
1129 : { }
1130 :
1131 : unordered_multiset(initializer_list<value_type> __l,
1132 : size_type __n, const hasher& __hf,
1133 : const allocator_type& __a)
1134 : : unordered_multiset(__l, __n, __hf, key_equal(), __a)
1135 : { }
1136 :
1137 : /**
1138 : * @brief %Unordered_multiset list assignment operator.
1139 : * @param __l An initializer_list.
1140 : *
1141 : * This function fills an %unordered_multiset with copies of the elements
1142 : * in the initializer list @a __l.
1143 : *
1144 : * Note that the assignment completely changes the %unordered_multiset
1145 : * and that the resulting %unordered_multiset's size is the same as the
1146 : * number of elements assigned.
1147 : */
1148 : unordered_multiset&
1149 : operator=(initializer_list<value_type> __l)
1150 : {
1151 : _M_h = __l;
1152 : return *this;
1153 : }
1154 :
1155 : /// Returns the allocator object used by the %unordered_multiset.
1156 : allocator_type
1157 : get_allocator() const noexcept
1158 : { return _M_h.get_allocator(); }
1159 :
1160 : // size and capacity:
1161 :
1162 : /// Returns true if the %unordered_multiset is empty.
1163 : _GLIBCXX_NODISCARD bool
1164 : empty() const noexcept
1165 : { return _M_h.empty(); }
1166 :
1167 : /// Returns the size of the %unordered_multiset.
1168 : size_type
1169 : size() const noexcept
1170 : { return _M_h.size(); }
1171 :
1172 : /// Returns the maximum size of the %unordered_multiset.
1173 : size_type
1174 : max_size() const noexcept
1175 : { return _M_h.max_size(); }
1176 :
1177 : // iterators.
1178 :
1179 : ///@{
1180 : /**
1181 : * Returns a read-only (constant) iterator that points to the first
1182 : * element in the %unordered_multiset.
1183 : */
1184 : iterator
1185 : begin() noexcept
1186 : { return _M_h.begin(); }
1187 :
1188 : const_iterator
1189 : begin() const noexcept
1190 : { return _M_h.begin(); }
1191 : ///@}
1192 :
1193 : ///@{
1194 : /**
1195 : * Returns a read-only (constant) iterator that points one past the last
1196 : * element in the %unordered_multiset.
1197 : */
1198 : iterator
1199 : end() noexcept
1200 : { return _M_h.end(); }
1201 :
1202 : const_iterator
1203 : end() const noexcept
1204 : { return _M_h.end(); }
1205 : ///@}
1206 :
1207 : /**
1208 : * Returns a read-only (constant) iterator that points to the first
1209 : * element in the %unordered_multiset.
1210 : */
1211 : const_iterator
1212 : cbegin() const noexcept
1213 : { return _M_h.begin(); }
1214 :
1215 : /**
1216 : * Returns a read-only (constant) iterator that points one past the last
1217 : * element in the %unordered_multiset.
1218 : */
1219 : const_iterator
1220 : cend() const noexcept
1221 : { return _M_h.end(); }
1222 :
1223 : // modifiers.
1224 :
1225 : /**
1226 : * @brief Builds and insert an element into the %unordered_multiset.
1227 : * @param __args Arguments used to generate an element.
1228 : * @return An iterator that points to the inserted element.
1229 : *
1230 : * Insertion requires amortized constant time.
1231 : */
1232 : template<typename... _Args>
1233 : iterator
1234 : emplace(_Args&&... __args)
1235 : { return _M_h.emplace(std::forward<_Args>(__args)...); }
1236 :
1237 : /**
1238 : * @brief Inserts an element into the %unordered_multiset.
1239 : * @param __pos An iterator that serves as a hint as to where the
1240 : * element should be inserted.
1241 : * @param __args Arguments used to generate the element to be
1242 : * inserted.
1243 : * @return An iterator that points to the inserted element.
1244 : *
1245 : * Note that the first parameter is only a hint and can potentially
1246 : * improve the performance of the insertion process. A bad hint would
1247 : * cause no gains in efficiency.
1248 : *
1249 : * For more on @a hinting, see:
1250 : * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1251 : *
1252 : * Insertion requires amortized constant time.
1253 : */
1254 : template<typename... _Args>
1255 : iterator
1256 : emplace_hint(const_iterator __pos, _Args&&... __args)
1257 : { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1258 :
1259 : ///@{
1260 : /**
1261 : * @brief Inserts an element into the %unordered_multiset.
1262 : * @param __x Element to be inserted.
1263 : * @return An iterator that points to the inserted element.
1264 : *
1265 : * Insertion requires amortized constant time.
1266 : */
1267 : iterator
1268 : insert(const value_type& __x)
1269 : { return _M_h.insert(__x); }
1270 :
1271 : iterator
1272 : insert(value_type&& __x)
1273 : { return _M_h.insert(std::move(__x)); }
1274 : ///@}
1275 :
1276 : ///@{
1277 : /**
1278 : * @brief Inserts an element into the %unordered_multiset.
1279 : * @param __hint An iterator that serves as a hint as to where the
1280 : * element should be inserted.
1281 : * @param __x Element to be inserted.
1282 : * @return An iterator that points to the inserted element.
1283 : *
1284 : * Note that the first parameter is only a hint and can potentially
1285 : * improve the performance of the insertion process. A bad hint would
1286 : * cause no gains in efficiency.
1287 : *
1288 : * For more on @a hinting, see:
1289 : * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1290 : *
1291 : * Insertion requires amortized constant.
1292 : */
1293 : iterator
1294 : insert(const_iterator __hint, const value_type& __x)
1295 : { return _M_h.insert(__hint, __x); }
1296 :
1297 : iterator
1298 : insert(const_iterator __hint, value_type&& __x)
1299 : { return _M_h.insert(__hint, std::move(__x)); }
1300 : ///@}
1301 :
1302 : /**
1303 : * @brief A template function that inserts a range of elements.
1304 : * @param __first Iterator pointing to the start of the range to be
1305 : * inserted.
1306 : * @param __last Iterator pointing to the end of the range.
1307 : *
1308 : * Complexity similar to that of the range constructor.
1309 : */
1310 : template<typename _InputIterator>
1311 : void
1312 : insert(_InputIterator __first, _InputIterator __last)
1313 : { _M_h.insert(__first, __last); }
1314 :
1315 : /**
1316 : * @brief Inserts a list of elements into the %unordered_multiset.
1317 : * @param __l A std::initializer_list<value_type> of elements to be
1318 : * inserted.
1319 : *
1320 : * Complexity similar to that of the range constructor.
1321 : */
1322 : void
1323 : insert(initializer_list<value_type> __l)
1324 : { _M_h.insert(__l); }
1325 :
1326 : #if __cplusplus > 201402L
1327 : /// Extract a node.
1328 : node_type
1329 : extract(const_iterator __pos)
1330 : {
1331 : __glibcxx_assert(__pos != end());
1332 : return _M_h.extract(__pos);
1333 : }
1334 :
1335 : /// Extract a node.
1336 : node_type
1337 : extract(const key_type& __key)
1338 : { return _M_h.extract(__key); }
1339 :
1340 : /// Re-insert an extracted node.
1341 : iterator
1342 : insert(node_type&& __nh)
1343 : { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1344 :
1345 : /// Re-insert an extracted node.
1346 : iterator
1347 : insert(const_iterator __hint, node_type&& __nh)
1348 : { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1349 : #endif // C++17
1350 :
1351 : ///@{
1352 : /**
1353 : * @brief Erases an element from an %unordered_multiset.
1354 : * @param __position An iterator pointing to the element to be erased.
1355 : * @return An iterator pointing to the element immediately following
1356 : * @a __position prior to the element being erased. If no such
1357 : * element exists, end() is returned.
1358 : *
1359 : * This function erases an element, pointed to by the given iterator,
1360 : * from an %unordered_multiset.
1361 : *
1362 : * Note that this function only erases the element, and that if the
1363 : * element is itself a pointer, the pointed-to memory is not touched in
1364 : * any way. Managing the pointer is the user's responsibility.
1365 : */
1366 : iterator
1367 : erase(const_iterator __position)
1368 : { return _M_h.erase(__position); }
1369 :
1370 : // LWG 2059.
1371 : iterator
1372 : erase(iterator __position)
1373 : { return _M_h.erase(__position); }
1374 : ///@}
1375 :
1376 :
1377 : /**
1378 : * @brief Erases elements according to the provided key.
1379 : * @param __x Key of element to be erased.
1380 : * @return The number of elements erased.
1381 : *
1382 : * This function erases all the elements located by the given key from
1383 : * an %unordered_multiset.
1384 : *
1385 : * Note that this function only erases the element, and that if the
1386 : * element is itself a pointer, the pointed-to memory is not touched in
1387 : * any way. Managing the pointer is the user's responsibility.
1388 : */
1389 : size_type
1390 : erase(const key_type& __x)
1391 : { return _M_h.erase(__x); }
1392 :
1393 : /**
1394 : * @brief Erases a [__first,__last) range of elements from an
1395 : * %unordered_multiset.
1396 : * @param __first Iterator pointing to the start of the range to be
1397 : * erased.
1398 : * @param __last Iterator pointing to the end of the range to
1399 : * be erased.
1400 : * @return The iterator @a __last.
1401 : *
1402 : * This function erases a sequence of elements from an
1403 : * %unordered_multiset.
1404 : *
1405 : * Note that this function only erases the element, and that if
1406 : * the element is itself a pointer, the pointed-to memory is not touched
1407 : * in any way. Managing the pointer is the user's responsibility.
1408 : */
1409 : iterator
1410 : erase(const_iterator __first, const_iterator __last)
1411 : { return _M_h.erase(__first, __last); }
1412 :
1413 : /**
1414 : * Erases all elements in an %unordered_multiset.
1415 : *
1416 : * Note that this function only erases the elements, and that if the
1417 : * elements themselves are pointers, the pointed-to memory is not touched
1418 : * in any way. Managing the pointer is the user's responsibility.
1419 : */
1420 : void
1421 : clear() noexcept
1422 : { _M_h.clear(); }
1423 :
1424 : /**
1425 : * @brief Swaps data with another %unordered_multiset.
1426 : * @param __x An %unordered_multiset of the same element and allocator
1427 : * types.
1428 : *
1429 : * This exchanges the elements between two sets in constant time.
1430 : * Note that the global std::swap() function is specialized such that
1431 : * std::swap(s1,s2) will feed to this function.
1432 : */
1433 : void
1434 : swap(unordered_multiset& __x)
1435 : noexcept( noexcept(_M_h.swap(__x._M_h)) )
1436 : { _M_h.swap(__x._M_h); }
1437 :
1438 : #if __cplusplus > 201402L
1439 : template<typename, typename, typename>
1440 : friend class std::_Hash_merge_helper;
1441 :
1442 : template<typename _H2, typename _P2>
1443 : void
1444 : merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
1445 : {
1446 : using _Merge_helper
1447 : = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1448 : _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1449 : }
1450 :
1451 : template<typename _H2, typename _P2>
1452 : void
1453 : merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1454 : { merge(__source); }
1455 :
1456 : template<typename _H2, typename _P2>
1457 : void
1458 : merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1459 : {
1460 : using _Merge_helper
1461 : = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1462 : _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1463 : }
1464 :
1465 : template<typename _H2, typename _P2>
1466 : void
1467 : merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1468 : { merge(__source); }
1469 : #endif // C++17
1470 :
1471 : // observers.
1472 :
1473 : /// Returns the hash functor object with which the %unordered_multiset
1474 : /// was constructed.
1475 : hasher
1476 : hash_function() const
1477 : { return _M_h.hash_function(); }
1478 :
1479 : /// Returns the key comparison object with which the %unordered_multiset
1480 : /// was constructed.
1481 : key_equal
1482 : key_eq() const
1483 : { return _M_h.key_eq(); }
1484 :
1485 : // lookup.
1486 :
1487 : ///@{
1488 : /**
1489 : * @brief Tries to locate an element in an %unordered_multiset.
1490 : * @param __x Element to be located.
1491 : * @return Iterator pointing to sought-after element, or end() if not
1492 : * found.
1493 : *
1494 : * This function takes a key and tries to locate the element with which
1495 : * the key matches. If successful the function returns an iterator
1496 : * pointing to the sought after element. If unsuccessful it returns the
1497 : * past-the-end ( @c end() ) iterator.
1498 : */
1499 : iterator
1500 : find(const key_type& __x)
1501 : { return _M_h.find(__x); }
1502 :
1503 : #if __cplusplus > 201703L
1504 : template<typename _Kt>
1505 : auto
1506 : find(const _Kt& __x)
1507 : -> decltype(_M_h._M_find_tr(__x))
1508 : { return _M_h._M_find_tr(__x); }
1509 : #endif
1510 :
1511 : const_iterator
1512 : find(const key_type& __x) const
1513 : { return _M_h.find(__x); }
1514 :
1515 : #if __cplusplus > 201703L
1516 : template<typename _Kt>
1517 : auto
1518 : find(const _Kt& __x) const
1519 : -> decltype(_M_h._M_find_tr(__x))
1520 : { return _M_h._M_find_tr(__x); }
1521 : #endif
1522 : ///@}
1523 :
1524 : ///@{
1525 : /**
1526 : * @brief Finds the number of elements.
1527 : * @param __x Element to located.
1528 : * @return Number of elements with specified key.
1529 : */
1530 : size_type
1531 : count(const key_type& __x) const
1532 : { return _M_h.count(__x); }
1533 :
1534 : #if __cplusplus > 201703L
1535 : template<typename _Kt>
1536 : auto
1537 : count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
1538 : { return _M_h._M_count_tr(__x); }
1539 : #endif
1540 : ///@}
1541 :
1542 : #if __cplusplus > 201703L
1543 : ///@{
1544 : /**
1545 : * @brief Finds whether an element with the given key exists.
1546 : * @param __x Key of elements to be located.
1547 : * @return True if there is any element with the specified key.
1548 : */
1549 : bool
1550 : contains(const key_type& __x) const
1551 : { return _M_h.find(__x) != _M_h.end(); }
1552 :
1553 : template<typename _Kt>
1554 : auto
1555 : contains(const _Kt& __x) const
1556 : -> decltype(_M_h._M_find_tr(__x), void(), true)
1557 : { return _M_h._M_find_tr(__x) != _M_h.end(); }
1558 : ///@}
1559 : #endif
1560 :
1561 : ///@{
1562 : /**
1563 : * @brief Finds a subsequence matching given key.
1564 : * @param __x Key to be located.
1565 : * @return Pair of iterators that possibly points to the subsequence
1566 : * matching given key.
1567 : */
1568 : std::pair<iterator, iterator>
1569 : equal_range(const key_type& __x)
1570 : { return _M_h.equal_range(__x); }
1571 :
1572 : #if __cplusplus > 201703L
1573 : template<typename _Kt>
1574 : auto
1575 : equal_range(const _Kt& __x)
1576 : -> decltype(_M_h._M_equal_range_tr(__x))
1577 : { return _M_h._M_equal_range_tr(__x); }
1578 : #endif
1579 :
1580 : std::pair<const_iterator, const_iterator>
1581 : equal_range(const key_type& __x) const
1582 : { return _M_h.equal_range(__x); }
1583 :
1584 : #if __cplusplus > 201703L
1585 : template<typename _Kt>
1586 : auto
1587 : equal_range(const _Kt& __x) const
1588 : -> decltype(_M_h._M_equal_range_tr(__x))
1589 : { return _M_h._M_equal_range_tr(__x); }
1590 : #endif
1591 : ///@}
1592 :
1593 : // bucket interface.
1594 :
1595 : /// Returns the number of buckets of the %unordered_multiset.
1596 : size_type
1597 : bucket_count() const noexcept
1598 : { return _M_h.bucket_count(); }
1599 :
1600 : /// Returns the maximum number of buckets of the %unordered_multiset.
1601 : size_type
1602 : max_bucket_count() const noexcept
1603 : { return _M_h.max_bucket_count(); }
1604 :
1605 : /*
1606 : * @brief Returns the number of elements in a given bucket.
1607 : * @param __n A bucket index.
1608 : * @return The number of elements in the bucket.
1609 : */
1610 : size_type
1611 : bucket_size(size_type __n) const
1612 : { return _M_h.bucket_size(__n); }
1613 :
1614 : /*
1615 : * @brief Returns the bucket index of a given element.
1616 : * @param __key A key instance.
1617 : * @return The key bucket index.
1618 : */
1619 : size_type
1620 : bucket(const key_type& __key) const
1621 : { return _M_h.bucket(__key); }
1622 :
1623 : ///@{
1624 : /**
1625 : * @brief Returns a read-only (constant) iterator pointing to the first
1626 : * bucket element.
1627 : * @param __n The bucket index.
1628 : * @return A read-only local iterator.
1629 : */
1630 : local_iterator
1631 : begin(size_type __n)
1632 : { return _M_h.begin(__n); }
1633 :
1634 : const_local_iterator
1635 : begin(size_type __n) const
1636 : { return _M_h.begin(__n); }
1637 :
1638 : const_local_iterator
1639 : cbegin(size_type __n) const
1640 : { return _M_h.cbegin(__n); }
1641 : ///@}
1642 :
1643 : ///@{
1644 : /**
1645 : * @brief Returns a read-only (constant) iterator pointing to one past
1646 : * the last bucket elements.
1647 : * @param __n The bucket index.
1648 : * @return A read-only local iterator.
1649 : */
1650 : local_iterator
1651 : end(size_type __n)
1652 : { return _M_h.end(__n); }
1653 :
1654 : const_local_iterator
1655 : end(size_type __n) const
1656 : { return _M_h.end(__n); }
1657 :
1658 : const_local_iterator
1659 : cend(size_type __n) const
1660 : { return _M_h.cend(__n); }
1661 : ///@}
1662 :
1663 : // hash policy.
1664 :
1665 : /// Returns the average number of elements per bucket.
1666 : float
1667 : load_factor() const noexcept
1668 : { return _M_h.load_factor(); }
1669 :
1670 : /// Returns a positive number that the %unordered_multiset tries to keep the
1671 : /// load factor less than or equal to.
1672 : float
1673 : max_load_factor() const noexcept
1674 : { return _M_h.max_load_factor(); }
1675 :
1676 : /**
1677 : * @brief Change the %unordered_multiset maximum load factor.
1678 : * @param __z The new maximum load factor.
1679 : */
1680 : void
1681 : max_load_factor(float __z)
1682 : { _M_h.max_load_factor(__z); }
1683 :
1684 : /**
1685 : * @brief May rehash the %unordered_multiset.
1686 : * @param __n The new number of buckets.
1687 : *
1688 : * Rehash will occur only if the new number of buckets respect the
1689 : * %unordered_multiset maximum load factor.
1690 : */
1691 : void
1692 : rehash(size_type __n)
1693 : { _M_h.rehash(__n); }
1694 :
1695 : /**
1696 : * @brief Prepare the %unordered_multiset for a specified number of
1697 : * elements.
1698 : * @param __n Number of elements required.
1699 : *
1700 : * Same as rehash(ceil(n / max_load_factor())).
1701 : */
1702 : void
1703 : reserve(size_type __n)
1704 : { _M_h.reserve(__n); }
1705 :
1706 : template<typename _Value1, typename _Hash1, typename _Pred1,
1707 : typename _Alloc1>
1708 : friend bool
1709 : operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&,
1710 : const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&);
1711 : };
1712 :
1713 :
1714 : #if __cpp_deduction_guides >= 201606
1715 :
1716 : template<typename _InputIterator,
1717 : typename _Hash =
1718 : hash<typename iterator_traits<_InputIterator>::value_type>,
1719 : typename _Pred =
1720 : equal_to<typename iterator_traits<_InputIterator>::value_type>,
1721 : typename _Allocator =
1722 : allocator<typename iterator_traits<_InputIterator>::value_type>,
1723 : typename = _RequireInputIter<_InputIterator>,
1724 : typename = _RequireNotAllocatorOrIntegral<_Hash>,
1725 : typename = _RequireNotAllocator<_Pred>,
1726 : typename = _RequireAllocator<_Allocator>>
1727 : unordered_multiset(_InputIterator, _InputIterator,
1728 : unordered_multiset<int>::size_type = {},
1729 : _Hash = _Hash(), _Pred = _Pred(),
1730 : _Allocator = _Allocator())
1731 : -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1732 : _Hash, _Pred, _Allocator>;
1733 :
1734 : template<typename _Tp, typename _Hash = hash<_Tp>,
1735 : typename _Pred = equal_to<_Tp>,
1736 : typename _Allocator = allocator<_Tp>,
1737 : typename = _RequireNotAllocatorOrIntegral<_Hash>,
1738 : typename = _RequireNotAllocator<_Pred>,
1739 : typename = _RequireAllocator<_Allocator>>
1740 : unordered_multiset(initializer_list<_Tp>,
1741 : unordered_multiset<int>::size_type = {},
1742 : _Hash = _Hash(), _Pred = _Pred(),
1743 : _Allocator = _Allocator())
1744 : -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1745 :
1746 : template<typename _InputIterator, typename _Allocator,
1747 : typename = _RequireInputIter<_InputIterator>,
1748 : typename = _RequireAllocator<_Allocator>>
1749 : unordered_multiset(_InputIterator, _InputIterator,
1750 : unordered_multiset<int>::size_type, _Allocator)
1751 : -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1752 : hash<typename
1753 : iterator_traits<_InputIterator>::value_type>,
1754 : equal_to<typename
1755 : iterator_traits<_InputIterator>::value_type>,
1756 : _Allocator>;
1757 :
1758 : template<typename _InputIterator, typename _Hash, typename _Allocator,
1759 : typename = _RequireInputIter<_InputIterator>,
1760 : typename = _RequireNotAllocatorOrIntegral<_Hash>,
1761 : typename = _RequireAllocator<_Allocator>>
1762 : unordered_multiset(_InputIterator, _InputIterator,
1763 : unordered_multiset<int>::size_type,
1764 : _Hash, _Allocator)
1765 : -> unordered_multiset<typename
1766 : iterator_traits<_InputIterator>::value_type,
1767 : _Hash,
1768 : equal_to<
1769 : typename
1770 : iterator_traits<_InputIterator>::value_type>,
1771 : _Allocator>;
1772 :
1773 : template<typename _Tp, typename _Allocator,
1774 : typename = _RequireAllocator<_Allocator>>
1775 : unordered_multiset(initializer_list<_Tp>,
1776 : unordered_multiset<int>::size_type, _Allocator)
1777 : -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1778 :
1779 : template<typename _Tp, typename _Hash, typename _Allocator,
1780 : typename = _RequireNotAllocatorOrIntegral<_Hash>,
1781 : typename = _RequireAllocator<_Allocator>>
1782 : unordered_multiset(initializer_list<_Tp>,
1783 : unordered_multiset<int>::size_type, _Hash, _Allocator)
1784 : -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1785 :
1786 : #endif
1787 :
1788 : template<class _Value, class _Hash, class _Pred, class _Alloc>
1789 : inline void
1790 : swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1791 : unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1792 : noexcept(noexcept(__x.swap(__y)))
1793 : { __x.swap(__y); }
1794 :
1795 : template<class _Value, class _Hash, class _Pred, class _Alloc>
1796 : inline void
1797 : swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1798 : unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1799 : noexcept(noexcept(__x.swap(__y)))
1800 : { __x.swap(__y); }
1801 :
1802 : template<class _Value, class _Hash, class _Pred, class _Alloc>
1803 : inline bool
1804 : operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1805 : const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1806 : { return __x._M_h._M_equal(__y._M_h); }
1807 :
1808 : #if __cpp_impl_three_way_comparison < 201907L
1809 : template<class _Value, class _Hash, class _Pred, class _Alloc>
1810 : inline bool
1811 : operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1812 : const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1813 : { return !(__x == __y); }
1814 : #endif
1815 :
1816 : template<class _Value, class _Hash, class _Pred, class _Alloc>
1817 : inline bool
1818 : operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1819 : const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1820 : { return __x._M_h._M_equal(__y._M_h); }
1821 :
1822 : #if __cpp_impl_three_way_comparison < 201907L
1823 : template<class _Value, class _Hash, class _Pred, class _Alloc>
1824 : inline bool
1825 : operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1826 : const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1827 : { return !(__x == __y); }
1828 : #endif
1829 :
1830 : _GLIBCXX_END_NAMESPACE_CONTAINER
1831 :
1832 : #if __cplusplus > 201402L
1833 : // Allow std::unordered_set access to internals of compatible sets.
1834 : template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1835 : typename _Hash2, typename _Eq2>
1836 : struct _Hash_merge_helper<
1837 : _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
1838 : {
1839 : private:
1840 : template<typename... _Tp>
1841 : using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1842 : template<typename... _Tp>
1843 : using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1844 :
1845 : friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
1846 :
1847 : static auto&
1848 : _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1849 : { return __set._M_h; }
1850 :
1851 : static auto&
1852 : _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1853 : { return __set._M_h; }
1854 : };
1855 :
1856 : // Allow std::unordered_multiset access to internals of compatible sets.
1857 : template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1858 : typename _Hash2, typename _Eq2>
1859 : struct _Hash_merge_helper<
1860 : _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
1861 : _Hash2, _Eq2>
1862 : {
1863 : private:
1864 : template<typename... _Tp>
1865 : using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1866 : template<typename... _Tp>
1867 : using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1868 :
1869 : friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
1870 :
1871 : static auto&
1872 : _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1873 : { return __set._M_h; }
1874 :
1875 : static auto&
1876 : _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1877 : { return __set._M_h; }
1878 : };
1879 : #endif // C++17
1880 :
1881 : _GLIBCXX_END_NAMESPACE_VERSION
1882 : } // namespace std
1883 :
1884 : #endif /* _UNORDERED_SET_H */
|
