File Coverage

/usr/include/c++/5/bits/unordered_map.h
Criterion Covered Total %
statement 10 10 100.0
branch n/a
condition n/a
subroutine n/a
pod n/a
total 10 10 100.0


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