File Coverage

/usr/include/c++/5/bits/unordered_set.h
Criterion Covered Total %
statement 1 2 50.0
branch n/a
condition n/a
subroutine n/a
pod n/a
total 1 2 50.0


line stmt bran cond sub pod time code
1             // unordered_set implementation -*- C++ -*-
2              
3             // Copyright (C) 2010-2015 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             // .
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_CONTAINER
36              
37             /// Base types for unordered_set.
38             template
39             using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
40              
41             template
42             typename _Hash = hash<_Value>,
43             typename _Pred = std::equal_to<_Value>,
44             typename _Alloc = std::allocator<_Value>,
45             typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
46             using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
47             __detail::_Identity, _Pred, _Hash,
48             __detail::_Mod_range_hashing,
49             __detail::_Default_ranged_hash,
50             __detail::_Prime_rehash_policy, _Tr>;
51              
52             /// Base types for unordered_multiset.
53             template
54             using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
55              
56             template
57             typename _Hash = hash<_Value>,
58             typename _Pred = std::equal_to<_Value>,
59             typename _Alloc = std::allocator<_Value>,
60             typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>>
61             using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
62             __detail::_Identity,
63             _Pred, _Hash,
64             __detail::_Mod_range_hashing,
65             __detail::_Default_ranged_hash,
66             __detail::_Prime_rehash_policy, _Tr>;
67              
68             /**
69             * @brief A standard container composed of unique keys (containing
70             * at most one of each key value) in which the elements' keys are
71             * the elements themselves.
72             *
73             * @ingroup unordered_associative_containers
74             *
75             * @tparam _Value Type of key objects.
76             * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
77              
78             * @tparam _Pred Predicate function object type, defaults to
79             * equal_to<_Value>.
80             *
81             * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
82             *
83             * Meets the requirements of a container, and
84             * unordered associative container
85             *
86             * Base is _Hashtable, dispatched at compile time via template
87             * alias __uset_hashtable.
88             */
89             template
90             class _Hash = hash<_Value>,
91             class _Pred = std::equal_to<_Value>,
92             class _Alloc = std::allocator<_Value> >
93 18           class unordered_set
94             {
95             typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
96             _Hashtable _M_h;
97              
98             public:
99             // typedefs:
100             //@{
101             /// Public typedefs.
102             typedef typename _Hashtable::key_type key_type;
103             typedef typename _Hashtable::value_type value_type;
104             typedef typename _Hashtable::hasher hasher;
105             typedef typename _Hashtable::key_equal key_equal;
106             typedef typename _Hashtable::allocator_type allocator_type;
107             //@}
108              
109             //@{
110             /// Iterator-related typedefs.
111             typedef typename _Hashtable::pointer pointer;
112             typedef typename _Hashtable::const_pointer const_pointer;
113             typedef typename _Hashtable::reference reference;
114             typedef typename _Hashtable::const_reference const_reference;
115             typedef typename _Hashtable::iterator iterator;
116             typedef typename _Hashtable::const_iterator const_iterator;
117             typedef typename _Hashtable::local_iterator local_iterator;
118             typedef typename _Hashtable::const_local_iterator const_local_iterator;
119             typedef typename _Hashtable::size_type size_type;
120             typedef typename _Hashtable::difference_type difference_type;
121             //@}
122              
123             // construct/destroy/copy
124              
125             /// Default constructor.
126             unordered_set() = default;
127              
128             /**
129             * @brief Default constructor creates no elements.
130             * @param __n Minimal initial number of buckets.
131             * @param __hf A hash functor.
132             * @param __eql A key equality functor.
133             * @param __a An allocator object.
134             */
135             explicit
136             unordered_set(size_type __n,
137             const hasher& __hf = hasher(),
138             const key_equal& __eql = key_equal(),
139             const allocator_type& __a = allocator_type())
140             : _M_h(__n, __hf, __eql, __a)
141             { }
142              
143             /**
144             * @brief Builds an %unordered_set from a range.
145             * @param __first An input iterator.
146             * @param __last An input iterator.
147             * @param __n Minimal initial number of buckets.
148             * @param __hf A hash functor.
149             * @param __eql A key equality functor.
150             * @param __a An allocator object.
151             *
152             * Create an %unordered_set consisting of copies of the elements from
153             * [__first,__last). This is linear in N (where N is
154             * distance(__first,__last)).
155             */
156             template
157             unordered_set(_InputIterator __first, _InputIterator __last,
158             size_type __n = 0,
159             const hasher& __hf = hasher(),
160             const key_equal& __eql = key_equal(),
161             const allocator_type& __a = allocator_type())
162             : _M_h(__first, __last, __n, __hf, __eql, __a)
163             { }
164              
165             /// Copy constructor.
166             unordered_set(const unordered_set&) = default;
167              
168             /// Move constructor.
169             unordered_set(unordered_set&&) = default;
170              
171             /**
172             * @brief Creates an %unordered_set with no elements.
173             * @param __a An allocator object.
174             */
175             explicit
176             unordered_set(const allocator_type& __a)
177             : _M_h(__a)
178             { }
179              
180             /*
181             * @brief Copy constructor with allocator argument.
182             * @param __uset Input %unordered_set to copy.
183             * @param __a An allocator object.
184             */
185             unordered_set(const unordered_set& __uset,
186             const allocator_type& __a)
187             : _M_h(__uset._M_h, __a)
188             { }
189              
190             /*
191             * @brief Move constructor with allocator argument.
192             * @param __uset Input %unordered_set to move.
193             * @param __a An allocator object.
194             */
195             unordered_set(unordered_set&& __uset,
196             const allocator_type& __a)
197             : _M_h(std::move(__uset._M_h), __a)
198             { }
199              
200             /**
201             * @brief Builds an %unordered_set from an initializer_list.
202             * @param __l An initializer_list.
203             * @param __n Minimal initial number of buckets.
204             * @param __hf A hash functor.
205             * @param __eql A key equality functor.
206             * @param __a An allocator object.
207             *
208             * Create an %unordered_set consisting of copies of the elements in the
209             * list. This is linear in N (where N is @a __l.size()).
210             */
211             unordered_set(initializer_list __l,
212             size_type __n = 0,
213             const hasher& __hf = hasher(),
214             const key_equal& __eql = key_equal(),
215             const allocator_type& __a = allocator_type())
216             : _M_h(__l, __n, __hf, __eql, __a)
217             { }
218              
219             unordered_set(size_type __n, const allocator_type& __a)
220             : unordered_set(__n, hasher(), key_equal(), __a)
221             { }
222              
223             unordered_set(size_type __n, const hasher& __hf,
224             const allocator_type& __a)
225             : unordered_set(__n, __hf, key_equal(), __a)
226             { }
227              
228             template
229             unordered_set(_InputIterator __first, _InputIterator __last,
230             size_type __n,
231             const allocator_type& __a)
232             : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
233             { }
234              
235             template
236             unordered_set(_InputIterator __first, _InputIterator __last,
237             size_type __n, const hasher& __hf,
238             const allocator_type& __a)
239             : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
240             { }
241              
242             unordered_set(initializer_list __l,
243             size_type __n,
244             const allocator_type& __a)
245             : unordered_set(__l, __n, hasher(), key_equal(), __a)
246             { }
247              
248             unordered_set(initializer_list __l,
249             size_type __n, const hasher& __hf,
250             const allocator_type& __a)
251             : unordered_set(__l, __n, __hf, key_equal(), __a)
252             { }
253              
254             /// Copy assignment operator.
255             unordered_set&
256             operator=(const unordered_set&) = default;
257              
258             /// Move assignment operator.
259             unordered_set&
260             operator=(unordered_set&&) = default;
261              
262             /**
263             * @brief %Unordered_set list assignment operator.
264             * @param __l An initializer_list.
265             *
266             * This function fills an %unordered_set with copies of the elements in
267             * the initializer list @a __l.
268             *
269             * Note that the assignment completely changes the %unordered_set and
270             * that the resulting %unordered_set's size is the same as the number
271             * of elements assigned. Old data may be lost.
272             */
273             unordered_set&
274             operator=(initializer_list __l)
275             {
276             _M_h = __l;
277             return *this;
278             }
279              
280             /// Returns the allocator object with which the %unordered_set was
281             /// constructed.
282             allocator_type
283             get_allocator() const noexcept
284             { return _M_h.get_allocator(); }
285              
286             // size and capacity:
287              
288             /// Returns true if the %unordered_set is empty.
289             bool
290             empty() const noexcept
291             { return _M_h.empty(); }
292              
293             /// Returns the size of the %unordered_set.
294             size_type
295             size() const noexcept
296             { return _M_h.size(); }
297              
298             /// Returns the maximum size of the %unordered_set.
299             size_type
300             max_size() const noexcept
301             { return _M_h.max_size(); }
302              
303             // iterators.
304              
305             //@{
306             /**
307             * Returns a read-only (constant) iterator that points to the first
308             * element in the %unordered_set.
309             */
310             iterator
311             begin() noexcept
312             { return _M_h.begin(); }
313              
314             const_iterator
315             begin() const noexcept
316             { return _M_h.begin(); }
317             //@}
318              
319             //@{
320             /**
321             * Returns a read-only (constant) iterator that points one past the last
322             * element in the %unordered_set.
323             */
324             iterator
325             end() noexcept
326             { return _M_h.end(); }
327              
328             const_iterator
329             end() const noexcept
330             { return _M_h.end(); }
331             //@}
332              
333             /**
334             * Returns a read-only (constant) iterator that points to the first
335             * element in the %unordered_set.
336             */
337             const_iterator
338             cbegin() const noexcept
339             { return _M_h.begin(); }
340              
341             /**
342             * Returns a read-only (constant) iterator that points one past the last
343             * element in the %unordered_set.
344             */
345             const_iterator
346             cend() const noexcept
347             { return _M_h.end(); }
348              
349             // modifiers.
350              
351             /**
352             * @brief Attempts to build and insert an element into the
353             * %unordered_set.
354             * @param __args Arguments used to generate an element.
355             * @return A pair, of which the first element is an iterator that points
356             * to the possibly inserted element, and the second is a bool
357             * that is true if the element was actually inserted.
358             *
359             * This function attempts to build and insert an element into the
360             * %unordered_set. An %unordered_set relies on unique keys and thus an
361             * element is only inserted if it is not already present in the
362             * %unordered_set.
363             *
364             * Insertion requires amortized constant time.
365             */
366             template
367             std::pair
368             emplace(_Args&&... __args)
369             { return _M_h.emplace(std::forward<_Args>(__args)...); }
370              
371             /**
372             * @brief Attempts to insert an element into the %unordered_set.
373             * @param __pos An iterator that serves as a hint as to where the
374             * element should be inserted.
375             * @param __args Arguments used to generate the element to be
376             * inserted.
377             * @return An iterator that points to the element with key equivalent to
378             * the one generated from @a __args (may or may not be the
379             * element itself).
380             *
381             * This function is not concerned about whether the insertion took place,
382             * and thus does not return a boolean like the single-argument emplace()
383             * does. Note that the first parameter is only a hint and can
384             * potentially improve the performance of the insertion process. A bad
385             * hint would cause no gains in efficiency.
386             *
387             * For more on @a hinting, see:
388             * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
389             *
390             * Insertion requires amortized constant time.
391             */
392             template
393             iterator
394             emplace_hint(const_iterator __pos, _Args&&... __args)
395             { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
396              
397             //@{
398             /**
399             * @brief Attempts to insert an element into the %unordered_set.
400             * @param __x Element to be inserted.
401             * @return A pair, of which the first element is an iterator that points
402             * to the possibly inserted element, and the second is a bool
403             * that is true if the element was actually inserted.
404             *
405             * This function attempts to insert an element into the %unordered_set.
406             * An %unordered_set relies on unique keys and thus an element is only
407             * inserted if it is not already present in the %unordered_set.
408             *
409             * Insertion requires amortized constant time.
410             */
411             std::pair
412             insert(const value_type& __x)
413             { return _M_h.insert(__x); }
414              
415             std::pair
416             insert(value_type&& __x)
417             { return _M_h.insert(std::move(__x)); }
418             //@}
419              
420             //@{
421             /**
422             * @brief Attempts to insert an element into the %unordered_set.
423             * @param __hint An iterator that serves as a hint as to where the
424             * element should be inserted.
425             * @param __x Element to be inserted.
426             * @return An iterator that points to the element with key of
427             * @a __x (may or may not be the element passed in).
428             *
429             * This function is not concerned about whether the insertion took place,
430             * and thus does not return a boolean like the single-argument insert()
431             * does. Note that the first parameter is only a hint and can
432             * potentially improve the performance of the insertion process. A bad
433             * hint would cause no gains in efficiency.
434             *
435             * For more on @a hinting, see:
436             * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
437             *
438             * Insertion requires amortized constant.
439             */
440             iterator
441             insert(const_iterator __hint, const value_type& __x)
442             { return _M_h.insert(__hint, __x); }
443              
444             iterator
445             insert(const_iterator __hint, value_type&& __x)
446             { return _M_h.insert(__hint, std::move(__x)); }
447             //@}
448              
449             /**
450             * @brief A template function that attempts to insert a range of
451             * elements.
452             * @param __first Iterator pointing to the start of the range to be
453             * inserted.
454             * @param __last Iterator pointing to the end of the range.
455             *
456             * Complexity similar to that of the range constructor.
457             */
458             template
459             void
460             insert(_InputIterator __first, _InputIterator __last)
461             { _M_h.insert(__first, __last); }
462              
463             /**
464             * @brief Attempts to insert a list of elements into the %unordered_set.
465             * @param __l A std::initializer_list of elements
466             * to be inserted.
467             *
468             * Complexity similar to that of the range constructor.
469             */
470             void
471             insert(initializer_list __l)
472             { _M_h.insert(__l); }
473              
474             //@{
475             /**
476             * @brief Erases an element from an %unordered_set.
477             * @param __position An iterator pointing to the element to be erased.
478             * @return An iterator pointing to the element immediately following
479             * @a __position prior to the element being erased. If no such
480             * element exists, end() is returned.
481             *
482             * This function erases an element, pointed to by the given iterator,
483             * from an %unordered_set. Note that this function only erases the
484             * element, and that if the element is itself a pointer, the pointed-to
485             * memory is not touched in any way. Managing the pointer is the user's
486             * responsibility.
487             */
488             iterator
489             erase(const_iterator __position)
490             { return _M_h.erase(__position); }
491              
492             // LWG 2059.
493             iterator
494             erase(iterator __position)
495             { return _M_h.erase(__position); }
496             //@}
497              
498             /**
499             * @brief Erases elements according to the provided key.
500             * @param __x Key of element to be erased.
501             * @return The number of elements erased.
502             *
503             * This function erases all the elements located by the given key from
504             * an %unordered_set. For an %unordered_set the result of this function
505             * can only be 0 (not present) or 1 (present).
506             * Note that this function only erases the element, and that if
507             * the element is itself a pointer, the pointed-to memory is not touched
508             * in any way. Managing the pointer is the user's responsibility.
509             */
510             size_type
511             erase(const key_type& __x)
512             { return _M_h.erase(__x); }
513              
514             /**
515             * @brief Erases a [__first,__last) range of elements from an
516             * %unordered_set.
517             * @param __first Iterator pointing to the start of the range to be
518             * erased.
519             * @param __last Iterator pointing to the end of the range to
520             * be erased.
521             * @return The iterator @a __last.
522             *
523             * This function erases a sequence of elements from an %unordered_set.
524             * Note that this function only erases the element, and that if
525             * the element is itself a pointer, the pointed-to memory is not touched
526             * in any way. Managing the pointer is the user's responsibility.
527             */
528             iterator
529             erase(const_iterator __first, const_iterator __last)
530             { return _M_h.erase(__first, __last); }
531              
532             /**
533             * Erases all elements in an %unordered_set. Note that this function only
534             * erases the elements, and that if the elements themselves are pointers,
535             * the pointed-to memory is not touched in any way. Managing the pointer
536             * is the user's responsibility.
537             */
538             void
539             clear() noexcept
540             { _M_h.clear(); }
541              
542             /**
543             * @brief Swaps data with another %unordered_set.
544             * @param __x An %unordered_set of the same element and allocator
545             * types.
546             *
547             * This exchanges the elements between two sets in constant time.
548             * Note that the global std::swap() function is specialized such that
549             * std::swap(s1,s2) will feed to this function.
550             */
551             void
552             swap(unordered_set& __x)
553             noexcept( noexcept(_M_h.swap(__x._M_h)) )
554             { _M_h.swap(__x._M_h); }
555              
556             // observers.
557              
558             /// Returns the hash functor object with which the %unordered_set was
559             /// constructed.
560             hasher
561             hash_function() const
562             { return _M_h.hash_function(); }
563              
564             /// Returns the key comparison object with which the %unordered_set was
565             /// constructed.
566             key_equal
567             key_eq() const
568             { return _M_h.key_eq(); }
569              
570             // lookup.
571              
572             //@{
573             /**
574             * @brief Tries to locate an element in an %unordered_set.
575             * @param __x Element to be located.
576             * @return Iterator pointing to sought-after element, or end() if not
577             * found.
578             *
579             * This function takes a key and tries to locate the element with which
580             * the key matches. If successful the function returns an iterator
581             * pointing to the sought after element. If unsuccessful it returns the
582             * past-the-end ( @c end() ) iterator.
583             */
584             iterator
585             find(const key_type& __x)
586             { return _M_h.find(__x); }
587              
588             const_iterator
589             find(const key_type& __x) const
590             { return _M_h.find(__x); }
591             //@}
592              
593             /**
594             * @brief Finds the number of elements.
595             * @param __x Element to located.
596             * @return Number of elements with specified key.
597             *
598             * This function only makes sense for unordered_multisets; for
599             * unordered_set the result will either be 0 (not present) or 1
600             * (present).
601             */
602             size_type
603             count(const key_type& __x) const
604 0           { return _M_h.count(__x); }
605              
606             //@{
607             /**
608             * @brief Finds a subsequence matching given key.
609             * @param __x Key to be located.
610             * @return Pair of iterators that possibly points to the subsequence
611             * matching given key.
612             *
613             * This function probably only makes sense for multisets.
614             */
615             std::pair
616             equal_range(const key_type& __x)
617             { return _M_h.equal_range(__x); }
618              
619             std::pair
620             equal_range(const key_type& __x) const
621             { return _M_h.equal_range(__x); }
622             //@}
623              
624             // bucket interface.
625              
626             /// Returns the number of buckets of the %unordered_set.
627             size_type
628             bucket_count() const noexcept
629             { return _M_h.bucket_count(); }
630              
631             /// Returns the maximum number of buckets of the %unordered_set.
632             size_type
633             max_bucket_count() const noexcept
634             { return _M_h.max_bucket_count(); }
635              
636             /*
637             * @brief Returns the number of elements in a given bucket.
638             * @param __n A bucket index.
639             * @return The number of elements in the bucket.
640             */
641             size_type
642             bucket_size(size_type __n) const
643             { return _M_h.bucket_size(__n); }
644              
645             /*
646             * @brief Returns the bucket index of a given element.
647             * @param __key A key instance.
648             * @return The key bucket index.
649             */
650             size_type
651             bucket(const key_type& __key) const
652             { return _M_h.bucket(__key); }
653              
654             //@{
655             /**
656             * @brief Returns a read-only (constant) iterator pointing to the first
657             * bucket element.
658             * @param __n The bucket index.
659             * @return A read-only local iterator.
660             */
661             local_iterator
662             begin(size_type __n)
663             { return _M_h.begin(__n); }
664              
665             const_local_iterator
666             begin(size_type __n) const
667             { return _M_h.begin(__n); }
668              
669             const_local_iterator
670             cbegin(size_type __n) const
671             { return _M_h.cbegin(__n); }
672             //@}
673              
674             //@{
675             /**
676             * @brief Returns a read-only (constant) iterator pointing to one past
677             * the last bucket elements.
678             * @param __n The bucket index.
679             * @return A read-only local iterator.
680             */
681             local_iterator
682             end(size_type __n)
683             { return _M_h.end(__n); }
684              
685             const_local_iterator
686             end(size_type __n) const
687             { return _M_h.end(__n); }
688              
689             const_local_iterator
690             cend(size_type __n) const
691             { return _M_h.cend(__n); }
692             //@}
693              
694             // hash policy.
695              
696             /// Returns the average number of elements per bucket.
697             float
698             load_factor() const noexcept
699             { return _M_h.load_factor(); }
700              
701             /// Returns a positive number that the %unordered_set tries to keep the
702             /// load factor less than or equal to.
703             float
704             max_load_factor() const noexcept
705             { return _M_h.max_load_factor(); }
706              
707             /**
708             * @brief Change the %unordered_set maximum load factor.
709             * @param __z The new maximum load factor.
710             */
711             void
712             max_load_factor(float __z)
713             { _M_h.max_load_factor(__z); }
714              
715             /**
716             * @brief May rehash the %unordered_set.
717             * @param __n The new number of buckets.
718             *
719             * Rehash will occur only if the new number of buckets respect the
720             * %unordered_set maximum load factor.
721             */
722             void
723             rehash(size_type __n)
724             { _M_h.rehash(__n); }
725              
726             /**
727             * @brief Prepare the %unordered_set for a specified number of
728             * elements.
729             * @param __n Number of elements required.
730             *
731             * Same as rehash(ceil(n / max_load_factor())).
732             */
733             void
734             reserve(size_type __n)
735             { _M_h.reserve(__n); }
736              
737             template
738             typename _Alloc1>
739             friend bool
740             operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&,
741             const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&);
742             };
743              
744             /**
745             * @brief A standard container composed of equivalent keys
746             * (possibly containing multiple of each key value) in which the
747             * elements' keys are the elements themselves.
748             *
749             * @ingroup unordered_associative_containers
750             *
751             * @tparam _Value Type of key objects.
752             * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
753             * @tparam _Pred Predicate function object type, defaults
754             * to equal_to<_Value>.
755             * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
756             *
757             * Meets the requirements of a container, and
758             * unordered associative container
759             *
760             * Base is _Hashtable, dispatched at compile time via template
761             * alias __umset_hashtable.
762             */
763             template
764             class _Hash = hash<_Value>,
765             class _Pred = std::equal_to<_Value>,
766             class _Alloc = std::allocator<_Value> >
767             class unordered_multiset
768             {
769             typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
770             _Hashtable _M_h;
771              
772             public:
773             // typedefs:
774             //@{
775             /// Public typedefs.
776             typedef typename _Hashtable::key_type key_type;
777             typedef typename _Hashtable::value_type value_type;
778             typedef typename _Hashtable::hasher hasher;
779             typedef typename _Hashtable::key_equal key_equal;
780             typedef typename _Hashtable::allocator_type allocator_type;
781             //@}
782              
783             //@{
784             /// Iterator-related typedefs.
785             typedef typename _Hashtable::pointer pointer;
786             typedef typename _Hashtable::const_pointer const_pointer;
787             typedef typename _Hashtable::reference reference;
788             typedef typename _Hashtable::const_reference const_reference;
789             typedef typename _Hashtable::iterator iterator;
790             typedef typename _Hashtable::const_iterator const_iterator;
791             typedef typename _Hashtable::local_iterator local_iterator;
792             typedef typename _Hashtable::const_local_iterator const_local_iterator;
793             typedef typename _Hashtable::size_type size_type;
794             typedef typename _Hashtable::difference_type difference_type;
795             //@}
796              
797             // construct/destroy/copy
798              
799             /// Default constructor.
800             unordered_multiset() = default;
801              
802             /**
803             * @brief Default constructor creates no elements.
804             * @param __n Minimal initial number of buckets.
805             * @param __hf A hash functor.
806             * @param __eql A key equality functor.
807             * @param __a An allocator object.
808             */
809             explicit
810             unordered_multiset(size_type __n,
811             const hasher& __hf = hasher(),
812             const key_equal& __eql = key_equal(),
813             const allocator_type& __a = allocator_type())
814             : _M_h(__n, __hf, __eql, __a)
815             { }
816              
817             /**
818             * @brief Builds an %unordered_multiset from a range.
819             * @param __first An input iterator.
820             * @param __last An input iterator.
821             * @param __n Minimal initial number of buckets.
822             * @param __hf A hash functor.
823             * @param __eql A key equality functor.
824             * @param __a An allocator object.
825             *
826             * Create an %unordered_multiset consisting of copies of the elements
827             * from [__first,__last). This is linear in N (where N is
828             * distance(__first,__last)).
829             */
830             template
831             unordered_multiset(_InputIterator __first, _InputIterator __last,
832             size_type __n = 0,
833             const hasher& __hf = hasher(),
834             const key_equal& __eql = key_equal(),
835             const allocator_type& __a = allocator_type())
836             : _M_h(__first, __last, __n, __hf, __eql, __a)
837             { }
838              
839             /// Copy constructor.
840             unordered_multiset(const unordered_multiset&) = default;
841              
842             /// Move constructor.
843             unordered_multiset(unordered_multiset&&) = default;
844              
845             /**
846             * @brief Builds an %unordered_multiset from an initializer_list.
847             * @param __l An initializer_list.
848             * @param __n Minimal initial number of buckets.
849             * @param __hf A hash functor.
850             * @param __eql A key equality functor.
851             * @param __a An allocator object.
852             *
853             * Create an %unordered_multiset consisting of copies of the elements in
854             * the list. This is linear in N (where N is @a __l.size()).
855             */
856             unordered_multiset(initializer_list __l,
857             size_type __n = 0,
858             const hasher& __hf = hasher(),
859             const key_equal& __eql = key_equal(),
860             const allocator_type& __a = allocator_type())
861             : _M_h(__l, __n, __hf, __eql, __a)
862             { }
863              
864             /// Copy assignment operator.
865             unordered_multiset&
866             operator=(const unordered_multiset&) = default;
867              
868             /// Move assignment operator.
869             unordered_multiset&
870             operator=(unordered_multiset&&) = default;
871              
872             /**
873             * @brief Creates an %unordered_multiset with no elements.
874             * @param __a An allocator object.
875             */
876             explicit
877             unordered_multiset(const allocator_type& __a)
878             : _M_h(__a)
879             { }
880              
881             /*
882             * @brief Copy constructor with allocator argument.
883             * @param __uset Input %unordered_multiset to copy.
884             * @param __a An allocator object.
885             */
886             unordered_multiset(const unordered_multiset& __umset,
887             const allocator_type& __a)
888             : _M_h(__umset._M_h, __a)
889             { }
890              
891             /*
892             * @brief Move constructor with allocator argument.
893             * @param __umset Input %unordered_multiset to move.
894             * @param __a An allocator object.
895             */
896             unordered_multiset(unordered_multiset&& __umset,
897             const allocator_type& __a)
898             : _M_h(std::move(__umset._M_h), __a)
899             { }
900              
901             unordered_multiset(size_type __n, const allocator_type& __a)
902             : unordered_multiset(__n, hasher(), key_equal(), __a)
903             { }
904              
905             unordered_multiset(size_type __n, const hasher& __hf,
906             const allocator_type& __a)
907             : unordered_multiset(__n, __hf, key_equal(), __a)
908             { }
909              
910             template
911             unordered_multiset(_InputIterator __first, _InputIterator __last,
912             size_type __n,
913             const allocator_type& __a)
914             : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
915             { }
916              
917             template
918             unordered_multiset(_InputIterator __first, _InputIterator __last,
919             size_type __n, const hasher& __hf,
920             const allocator_type& __a)
921             : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
922             { }
923              
924             unordered_multiset(initializer_list __l,
925             size_type __n,
926             const allocator_type& __a)
927             : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
928             { }
929              
930             unordered_multiset(initializer_list __l,
931             size_type __n, const hasher& __hf,
932             const allocator_type& __a)
933             : unordered_multiset(__l, __n, __hf, key_equal(), __a)
934             { }
935              
936             /**
937             * @brief %Unordered_multiset list assignment operator.
938             * @param __l An initializer_list.
939             *
940             * This function fills an %unordered_multiset with copies of the elements
941             * in the initializer list @a __l.
942             *
943             * Note that the assignment completely changes the %unordered_multiset
944             * and that the resulting %unordered_multiset's size is the same as the
945             * number of elements assigned. Old data may be lost.
946             */
947             unordered_multiset&
948             operator=(initializer_list __l)
949             {
950             _M_h = __l;
951             return *this;
952             }
953              
954             /// Returns the allocator object with which the %unordered_multiset was
955             /// constructed.
956             allocator_type
957             get_allocator() const noexcept
958             { return _M_h.get_allocator(); }
959              
960             // size and capacity:
961              
962             /// Returns true if the %unordered_multiset is empty.
963             bool
964             empty() const noexcept
965             { return _M_h.empty(); }
966              
967             /// Returns the size of the %unordered_multiset.
968             size_type
969             size() const noexcept
970             { return _M_h.size(); }
971              
972             /// Returns the maximum size of the %unordered_multiset.
973             size_type
974             max_size() const noexcept
975             { return _M_h.max_size(); }
976              
977             // iterators.
978              
979             //@{
980             /**
981             * Returns a read-only (constant) iterator that points to the first
982             * element in the %unordered_multiset.
983             */
984             iterator
985             begin() noexcept
986             { return _M_h.begin(); }
987              
988             const_iterator
989             begin() const noexcept
990             { return _M_h.begin(); }
991             //@}
992              
993             //@{
994             /**
995             * Returns a read-only (constant) iterator that points one past the last
996             * element in the %unordered_multiset.
997             */
998             iterator
999             end() noexcept
1000             { return _M_h.end(); }
1001              
1002             const_iterator
1003             end() const noexcept
1004             { return _M_h.end(); }
1005             //@}
1006              
1007             /**
1008             * Returns a read-only (constant) iterator that points to the first
1009             * element in the %unordered_multiset.
1010             */
1011             const_iterator
1012             cbegin() const noexcept
1013             { return _M_h.begin(); }
1014              
1015             /**
1016             * Returns a read-only (constant) iterator that points one past the last
1017             * element in the %unordered_multiset.
1018             */
1019             const_iterator
1020             cend() const noexcept
1021             { return _M_h.end(); }
1022              
1023             // modifiers.
1024              
1025             /**
1026             * @brief Builds and insert an element into the %unordered_multiset.
1027             * @param __args Arguments used to generate an element.
1028             * @return An iterator that points to the inserted element.
1029             *
1030             * Insertion requires amortized constant time.
1031             */
1032             template
1033             iterator
1034             emplace(_Args&&... __args)
1035             { return _M_h.emplace(std::forward<_Args>(__args)...); }
1036              
1037             /**
1038             * @brief Inserts an element into the %unordered_multiset.
1039             * @param __pos An iterator that serves as a hint as to where the
1040             * element should be inserted.
1041             * @param __args Arguments used to generate the element to be
1042             * inserted.
1043             * @return An iterator that points to the inserted element.
1044             *
1045             * Note that the first parameter is only a hint and can potentially
1046             * improve the performance of the insertion process. A bad hint would
1047             * cause no gains in efficiency.
1048             *
1049             * For more on @a hinting, see:
1050             * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1051             *
1052             * Insertion requires amortized constant time.
1053             */
1054             template
1055             iterator
1056             emplace_hint(const_iterator __pos, _Args&&... __args)
1057             { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1058              
1059             //@{
1060             /**
1061             * @brief Inserts an element into the %unordered_multiset.
1062             * @param __x Element to be inserted.
1063             * @return An iterator that points to the inserted element.
1064             *
1065             * Insertion requires amortized constant time.
1066             */
1067             iterator
1068             insert(const value_type& __x)
1069             { return _M_h.insert(__x); }
1070              
1071             iterator
1072             insert(value_type&& __x)
1073             { return _M_h.insert(std::move(__x)); }
1074             //@}
1075              
1076             //@{
1077             /**
1078             * @brief Inserts an element into the %unordered_multiset.
1079             * @param __hint An iterator that serves as a hint as to where the
1080             * element should be inserted.
1081             * @param __x Element to be inserted.
1082             * @return An iterator that points to the inserted element.
1083             *
1084             * Note that the first parameter is only a hint and can potentially
1085             * improve the performance of the insertion process. A bad hint would
1086             * cause no gains in efficiency.
1087             *
1088             * For more on @a hinting, see:
1089             * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1090             *
1091             * Insertion requires amortized constant.
1092             */
1093             iterator
1094             insert(const_iterator __hint, const value_type& __x)
1095             { return _M_h.insert(__hint, __x); }
1096              
1097             iterator
1098             insert(const_iterator __hint, value_type&& __x)
1099             { return _M_h.insert(__hint, std::move(__x)); }
1100             //@}
1101              
1102             /**
1103             * @brief A template function that inserts a range of elements.
1104             * @param __first Iterator pointing to the start of the range to be
1105             * inserted.
1106             * @param __last Iterator pointing to the end of the range.
1107             *
1108             * Complexity similar to that of the range constructor.
1109             */
1110             template
1111             void
1112             insert(_InputIterator __first, _InputIterator __last)
1113             { _M_h.insert(__first, __last); }
1114              
1115             /**
1116             * @brief Inserts a list of elements into the %unordered_multiset.
1117             * @param __l A std::initializer_list of elements to be
1118             * inserted.
1119             *
1120             * Complexity similar to that of the range constructor.
1121             */
1122             void
1123             insert(initializer_list __l)
1124             { _M_h.insert(__l); }
1125              
1126             //@{
1127             /**
1128             * @brief Erases an element from an %unordered_multiset.
1129             * @param __position An iterator pointing to the element to be erased.
1130             * @return An iterator pointing to the element immediately following
1131             * @a __position prior to the element being erased. If no such
1132             * element exists, end() is returned.
1133             *
1134             * This function erases an element, pointed to by the given iterator,
1135             * from an %unordered_multiset.
1136             *
1137             * Note that this function only erases the element, and that if the
1138             * element is itself a pointer, the pointed-to memory is not touched in
1139             * any way. Managing the pointer is the user's responsibility.
1140             */
1141             iterator
1142             erase(const_iterator __position)
1143             { return _M_h.erase(__position); }
1144              
1145             // LWG 2059.
1146             iterator
1147             erase(iterator __position)
1148             { return _M_h.erase(__position); }
1149             //@}
1150              
1151              
1152             /**
1153             * @brief Erases elements according to the provided key.
1154             * @param __x Key of element to be erased.
1155             * @return The number of elements erased.
1156             *
1157             * This function erases all the elements located by the given key from
1158             * an %unordered_multiset.
1159             *
1160             * Note that this function only erases the element, and that if the
1161             * element is itself a pointer, the pointed-to memory is not touched in
1162             * any way. Managing the pointer is the user's responsibility.
1163             */
1164             size_type
1165             erase(const key_type& __x)
1166             { return _M_h.erase(__x); }
1167              
1168             /**
1169             * @brief Erases a [__first,__last) range of elements from an
1170             * %unordered_multiset.
1171             * @param __first Iterator pointing to the start of the range to be
1172             * erased.
1173             * @param __last Iterator pointing to the end of the range to
1174             * be erased.
1175             * @return The iterator @a __last.
1176             *
1177             * This function erases a sequence of elements from an
1178             * %unordered_multiset.
1179             *
1180             * Note that this function only erases the element, and that if
1181             * the element is itself a pointer, the pointed-to memory is not touched
1182             * in any way. Managing the pointer is the user's responsibility.
1183             */
1184             iterator
1185             erase(const_iterator __first, const_iterator __last)
1186             { return _M_h.erase(__first, __last); }
1187              
1188             /**
1189             * Erases all elements in an %unordered_multiset.
1190             *
1191             * Note that this function only erases the elements, and that if the
1192             * elements themselves are pointers, the pointed-to memory is not touched
1193             * in any way. Managing the pointer is the user's responsibility.
1194             */
1195             void
1196             clear() noexcept
1197             { _M_h.clear(); }
1198              
1199             /**
1200             * @brief Swaps data with another %unordered_multiset.
1201             * @param __x An %unordered_multiset of the same element and allocator
1202             * types.
1203             *
1204             * This exchanges the elements between two sets in constant time.
1205             * Note that the global std::swap() function is specialized such that
1206             * std::swap(s1,s2) will feed to this function.
1207             */
1208             void
1209             swap(unordered_multiset& __x)
1210             noexcept( noexcept(_M_h.swap(__x._M_h)) )
1211             { _M_h.swap(__x._M_h); }
1212              
1213             // observers.
1214              
1215             /// Returns the hash functor object with which the %unordered_multiset
1216             /// was constructed.
1217             hasher
1218             hash_function() const
1219             { return _M_h.hash_function(); }
1220              
1221             /// Returns the key comparison object with which the %unordered_multiset
1222             /// was constructed.
1223             key_equal
1224             key_eq() const
1225             { return _M_h.key_eq(); }
1226              
1227             // lookup.
1228              
1229             //@{
1230             /**
1231             * @brief Tries to locate an element in an %unordered_multiset.
1232             * @param __x Element to be located.
1233             * @return Iterator pointing to sought-after element, or end() if not
1234             * found.
1235             *
1236             * This function takes a key and tries to locate the element with which
1237             * the key matches. If successful the function returns an iterator
1238             * pointing to the sought after element. If unsuccessful it returns the
1239             * past-the-end ( @c end() ) iterator.
1240             */
1241             iterator
1242             find(const key_type& __x)
1243             { return _M_h.find(__x); }
1244              
1245             const_iterator
1246             find(const key_type& __x) const
1247             { return _M_h.find(__x); }
1248             //@}
1249              
1250             /**
1251             * @brief Finds the number of elements.
1252             * @param __x Element to located.
1253             * @return Number of elements with specified key.
1254             */
1255             size_type
1256             count(const key_type& __x) const
1257             { return _M_h.count(__x); }
1258              
1259             //@{
1260             /**
1261             * @brief Finds a subsequence matching given key.
1262             * @param __x Key to be located.
1263             * @return Pair of iterators that possibly points to the subsequence
1264             * matching given key.
1265             */
1266             std::pair
1267             equal_range(const key_type& __x)
1268             { return _M_h.equal_range(__x); }
1269              
1270             std::pair
1271             equal_range(const key_type& __x) const
1272             { return _M_h.equal_range(__x); }
1273             //@}
1274              
1275             // bucket interface.
1276              
1277             /// Returns the number of buckets of the %unordered_multiset.
1278             size_type
1279             bucket_count() const noexcept
1280             { return _M_h.bucket_count(); }
1281              
1282             /// Returns the maximum number of buckets of the %unordered_multiset.
1283             size_type
1284             max_bucket_count() const noexcept
1285             { return _M_h.max_bucket_count(); }
1286              
1287             /*
1288             * @brief Returns the number of elements in a given bucket.
1289             * @param __n A bucket index.
1290             * @return The number of elements in the bucket.
1291             */
1292             size_type
1293             bucket_size(size_type __n) const
1294             { return _M_h.bucket_size(__n); }
1295              
1296             /*
1297             * @brief Returns the bucket index of a given element.
1298             * @param __key A key instance.
1299             * @return The key bucket index.
1300             */
1301             size_type
1302             bucket(const key_type& __key) const
1303             { return _M_h.bucket(__key); }
1304              
1305             //@{
1306             /**
1307             * @brief Returns a read-only (constant) iterator pointing to the first
1308             * bucket element.
1309             * @param __n The bucket index.
1310             * @return A read-only local iterator.
1311             */
1312             local_iterator
1313             begin(size_type __n)
1314             { return _M_h.begin(__n); }
1315              
1316             const_local_iterator
1317             begin(size_type __n) const
1318             { return _M_h.begin(__n); }
1319              
1320             const_local_iterator
1321             cbegin(size_type __n) const
1322             { return _M_h.cbegin(__n); }
1323             //@}
1324              
1325             //@{
1326             /**
1327             * @brief Returns a read-only (constant) iterator pointing to one past
1328             * the last bucket elements.
1329             * @param __n The bucket index.
1330             * @return A read-only local iterator.
1331             */
1332             local_iterator
1333             end(size_type __n)
1334             { return _M_h.end(__n); }
1335              
1336             const_local_iterator
1337             end(size_type __n) const
1338             { return _M_h.end(__n); }
1339              
1340             const_local_iterator
1341             cend(size_type __n) const
1342             { return _M_h.cend(__n); }
1343             //@}
1344              
1345             // hash policy.
1346              
1347             /// Returns the average number of elements per bucket.
1348             float
1349             load_factor() const noexcept
1350             { return _M_h.load_factor(); }
1351              
1352             /// Returns a positive number that the %unordered_multiset tries to keep the
1353             /// load factor less than or equal to.
1354             float
1355             max_load_factor() const noexcept
1356             { return _M_h.max_load_factor(); }
1357              
1358             /**
1359             * @brief Change the %unordered_multiset maximum load factor.
1360             * @param __z The new maximum load factor.
1361             */
1362             void
1363             max_load_factor(float __z)
1364             { _M_h.max_load_factor(__z); }
1365              
1366             /**
1367             * @brief May rehash the %unordered_multiset.
1368             * @param __n The new number of buckets.
1369             *
1370             * Rehash will occur only if the new number of buckets respect the
1371             * %unordered_multiset maximum load factor.
1372             */
1373             void
1374             rehash(size_type __n)
1375             { _M_h.rehash(__n); }
1376              
1377             /**
1378             * @brief Prepare the %unordered_multiset for a specified number of
1379             * elements.
1380             * @param __n Number of elements required.
1381             *
1382             * Same as rehash(ceil(n / max_load_factor())).
1383             */
1384             void
1385             reserve(size_type __n)
1386             { _M_h.reserve(__n); }
1387              
1388             template
1389             typename _Alloc1>
1390             friend bool
1391             operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&,
1392             const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&);
1393             };
1394              
1395             template
1396             inline void
1397             swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1398             unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1399             { __x.swap(__y); }
1400              
1401             template
1402             inline void
1403             swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1404             unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1405             { __x.swap(__y); }
1406              
1407             template
1408             inline bool
1409             operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1410             const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1411             { return __x._M_h._M_equal(__y._M_h); }
1412              
1413             template
1414             inline bool
1415             operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1416             const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1417             { return !(__x == __y); }
1418              
1419             template
1420             inline bool
1421             operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1422             const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1423             { return __x._M_h._M_equal(__y._M_h); }
1424              
1425             template
1426             inline bool
1427             operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1428             const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1429             { return !(__x == __y); }
1430              
1431             _GLIBCXX_END_NAMESPACE_CONTAINER
1432             } // namespace std
1433              
1434             #endif /* _UNORDERED_SET_H */