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