xref: /freebsd/contrib/llvm-project/libcxx/include/ext/hash_map (revision cd0c3137f8a21968ce147251633b8dbdde8829e7)
10b57cec5SDimitry Andric// -*- C++ -*-
20b57cec5SDimitry Andric//===-------------------------- hash_map ----------------------------------===//
30b57cec5SDimitry Andric//
40b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
50b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information.
60b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
70b57cec5SDimitry Andric//
80b57cec5SDimitry Andric//===----------------------------------------------------------------------===//
90b57cec5SDimitry Andric
100b57cec5SDimitry Andric#ifndef _LIBCPP_HASH_MAP
110b57cec5SDimitry Andric#define _LIBCPP_HASH_MAP
120b57cec5SDimitry Andric
130b57cec5SDimitry Andric/*
140b57cec5SDimitry Andric
150b57cec5SDimitry Andric    hash_map synopsis
160b57cec5SDimitry Andric
170b57cec5SDimitry Andricnamespace __gnu_cxx
180b57cec5SDimitry Andric{
190b57cec5SDimitry Andric
200b57cec5SDimitry Andrictemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
210b57cec5SDimitry Andric          class Alloc = allocator<pair<const Key, T>>>
220b57cec5SDimitry Andricclass hash_map
230b57cec5SDimitry Andric{
240b57cec5SDimitry Andricpublic:
250b57cec5SDimitry Andric    // types
260b57cec5SDimitry Andric    typedef Key                                                        key_type;
270b57cec5SDimitry Andric    typedef T                                                          mapped_type;
280b57cec5SDimitry Andric    typedef Hash                                                       hasher;
290b57cec5SDimitry Andric    typedef Pred                                                       key_equal;
300b57cec5SDimitry Andric    typedef Alloc                                                      allocator_type;
310b57cec5SDimitry Andric    typedef pair<const key_type, mapped_type>                          value_type;
320b57cec5SDimitry Andric    typedef value_type&                                                reference;
330b57cec5SDimitry Andric    typedef const value_type&                                          const_reference;
340b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::pointer         pointer;
350b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
360b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::size_type       size_type;
370b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
380b57cec5SDimitry Andric
390b57cec5SDimitry Andric    typedef /unspecified/ iterator;
400b57cec5SDimitry Andric    typedef /unspecified/ const_iterator;
410b57cec5SDimitry Andric
420b57cec5SDimitry Andric    explicit hash_map(size_type n = 193, const hasher& hf = hasher(),
430b57cec5SDimitry Andric                           const key_equal& eql = key_equal(),
440b57cec5SDimitry Andric                           const allocator_type& a = allocator_type());
450b57cec5SDimitry Andric    template <class InputIterator>
460b57cec5SDimitry Andric        hash_map(InputIterator f, InputIterator l,
470b57cec5SDimitry Andric                      size_type n = 193, const hasher& hf = hasher(),
480b57cec5SDimitry Andric                      const key_equal& eql = key_equal(),
490b57cec5SDimitry Andric                      const allocator_type& a = allocator_type());
500b57cec5SDimitry Andric    hash_map(const hash_map&);
510b57cec5SDimitry Andric    ~hash_map();
520b57cec5SDimitry Andric    hash_map& operator=(const hash_map&);
530b57cec5SDimitry Andric
540b57cec5SDimitry Andric    allocator_type get_allocator() const;
550b57cec5SDimitry Andric
560b57cec5SDimitry Andric    bool      empty() const;
570b57cec5SDimitry Andric    size_type size() const;
580b57cec5SDimitry Andric    size_type max_size() const;
590b57cec5SDimitry Andric
600b57cec5SDimitry Andric    iterator       begin();
610b57cec5SDimitry Andric    iterator       end();
620b57cec5SDimitry Andric    const_iterator begin()  const;
630b57cec5SDimitry Andric    const_iterator end()    const;
640b57cec5SDimitry Andric
650b57cec5SDimitry Andric    pair<iterator, bool> insert(const value_type& obj);
660b57cec5SDimitry Andric    template <class InputIterator>
670b57cec5SDimitry Andric        void insert(InputIterator first, InputIterator last);
680b57cec5SDimitry Andric
690b57cec5SDimitry Andric    void erase(const_iterator position);
700b57cec5SDimitry Andric    size_type erase(const key_type& k);
710b57cec5SDimitry Andric    void erase(const_iterator first, const_iterator last);
720b57cec5SDimitry Andric    void clear();
730b57cec5SDimitry Andric
740b57cec5SDimitry Andric    void swap(hash_map&);
750b57cec5SDimitry Andric
760b57cec5SDimitry Andric    hasher hash_funct() const;
770b57cec5SDimitry Andric    key_equal key_eq() const;
780b57cec5SDimitry Andric
790b57cec5SDimitry Andric    iterator       find(const key_type& k);
800b57cec5SDimitry Andric    const_iterator find(const key_type& k) const;
810b57cec5SDimitry Andric    size_type count(const key_type& k) const;
820b57cec5SDimitry Andric    pair<iterator, iterator>             equal_range(const key_type& k);
830b57cec5SDimitry Andric    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
840b57cec5SDimitry Andric
850b57cec5SDimitry Andric    mapped_type& operator[](const key_type& k);
860b57cec5SDimitry Andric
870b57cec5SDimitry Andric    size_type bucket_count() const;
880b57cec5SDimitry Andric    size_type max_bucket_count() const;
890b57cec5SDimitry Andric
900b57cec5SDimitry Andric    size_type elems_in_bucket(size_type n) const;
910b57cec5SDimitry Andric
920b57cec5SDimitry Andric    void resize(size_type n);
930b57cec5SDimitry Andric};
940b57cec5SDimitry Andric
950b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
960b57cec5SDimitry Andric    void swap(hash_map<Key, T, Hash, Pred, Alloc>& x,
970b57cec5SDimitry Andric              hash_map<Key, T, Hash, Pred, Alloc>& y);
980b57cec5SDimitry Andric
990b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
1000b57cec5SDimitry Andric    bool
1010b57cec5SDimitry Andric    operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x,
1020b57cec5SDimitry Andric               const hash_map<Key, T, Hash, Pred, Alloc>& y);
1030b57cec5SDimitry Andric
1040b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
1050b57cec5SDimitry Andric    bool
1060b57cec5SDimitry Andric    operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x,
1070b57cec5SDimitry Andric               const hash_map<Key, T, Hash, Pred, Alloc>& y);
1080b57cec5SDimitry Andric
1090b57cec5SDimitry Andrictemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
1100b57cec5SDimitry Andric          class Alloc = allocator<pair<const Key, T>>>
1110b57cec5SDimitry Andricclass hash_multimap
1120b57cec5SDimitry Andric{
1130b57cec5SDimitry Andricpublic:
1140b57cec5SDimitry Andric    // types
1150b57cec5SDimitry Andric    typedef Key                                                        key_type;
1160b57cec5SDimitry Andric    typedef T                                                          mapped_type;
1170b57cec5SDimitry Andric    typedef Hash                                                       hasher;
1180b57cec5SDimitry Andric    typedef Pred                                                       key_equal;
1190b57cec5SDimitry Andric    typedef Alloc                                                      allocator_type;
1200b57cec5SDimitry Andric    typedef pair<const key_type, mapped_type>                          value_type;
1210b57cec5SDimitry Andric    typedef value_type&                                                reference;
1220b57cec5SDimitry Andric    typedef const value_type&                                          const_reference;
1230b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::pointer         pointer;
1240b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
1250b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::size_type       size_type;
1260b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
1270b57cec5SDimitry Andric
1280b57cec5SDimitry Andric    typedef /unspecified/ iterator;
1290b57cec5SDimitry Andric    typedef /unspecified/ const_iterator;
1300b57cec5SDimitry Andric
1310b57cec5SDimitry Andric    explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(),
1320b57cec5SDimitry Andric                           const key_equal& eql = key_equal(),
1330b57cec5SDimitry Andric                           const allocator_type& a = allocator_type());
1340b57cec5SDimitry Andric    template <class InputIterator>
1350b57cec5SDimitry Andric        hash_multimap(InputIterator f, InputIterator l,
1360b57cec5SDimitry Andric                      size_type n = 193, const hasher& hf = hasher(),
1370b57cec5SDimitry Andric                      const key_equal& eql = key_equal(),
1380b57cec5SDimitry Andric                      const allocator_type& a = allocator_type());
1390b57cec5SDimitry Andric    explicit hash_multimap(const allocator_type&);
1400b57cec5SDimitry Andric    hash_multimap(const hash_multimap&);
1410b57cec5SDimitry Andric    ~hash_multimap();
1420b57cec5SDimitry Andric    hash_multimap& operator=(const hash_multimap&);
1430b57cec5SDimitry Andric
1440b57cec5SDimitry Andric    allocator_type get_allocator() const;
1450b57cec5SDimitry Andric
1460b57cec5SDimitry Andric    bool      empty() const;
1470b57cec5SDimitry Andric    size_type size() const;
1480b57cec5SDimitry Andric    size_type max_size() const;
1490b57cec5SDimitry Andric
1500b57cec5SDimitry Andric    iterator       begin();
1510b57cec5SDimitry Andric    iterator       end();
1520b57cec5SDimitry Andric    const_iterator begin()  const;
1530b57cec5SDimitry Andric    const_iterator end()    const;
1540b57cec5SDimitry Andric
1550b57cec5SDimitry Andric    iterator insert(const value_type& obj);
1560b57cec5SDimitry Andric    template <class InputIterator>
1570b57cec5SDimitry Andric        void insert(InputIterator first, InputIterator last);
1580b57cec5SDimitry Andric
1590b57cec5SDimitry Andric    void erase(const_iterator position);
1600b57cec5SDimitry Andric    size_type erase(const key_type& k);
1610b57cec5SDimitry Andric    void erase(const_iterator first, const_iterator last);
1620b57cec5SDimitry Andric    void clear();
1630b57cec5SDimitry Andric
1640b57cec5SDimitry Andric    void swap(hash_multimap&);
1650b57cec5SDimitry Andric
1660b57cec5SDimitry Andric    hasher hash_funct() const;
1670b57cec5SDimitry Andric    key_equal key_eq() const;
1680b57cec5SDimitry Andric
1690b57cec5SDimitry Andric    iterator       find(const key_type& k);
1700b57cec5SDimitry Andric    const_iterator find(const key_type& k) const;
1710b57cec5SDimitry Andric    size_type count(const key_type& k) const;
1720b57cec5SDimitry Andric    pair<iterator, iterator>             equal_range(const key_type& k);
1730b57cec5SDimitry Andric    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
1740b57cec5SDimitry Andric
1750b57cec5SDimitry Andric    size_type bucket_count() const;
1760b57cec5SDimitry Andric    size_type max_bucket_count() const;
1770b57cec5SDimitry Andric
1780b57cec5SDimitry Andric    size_type elems_in_bucket(size_type n) const;
1790b57cec5SDimitry Andric
1800b57cec5SDimitry Andric    void resize(size_type n);
1810b57cec5SDimitry Andric};
1820b57cec5SDimitry Andric
1830b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
1840b57cec5SDimitry Andric    void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x,
1850b57cec5SDimitry Andric              hash_multimap<Key, T, Hash, Pred, Alloc>& y);
1860b57cec5SDimitry Andric
1870b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
1880b57cec5SDimitry Andric    bool
1890b57cec5SDimitry Andric    operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
1900b57cec5SDimitry Andric               const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
1910b57cec5SDimitry Andric
1920b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
1930b57cec5SDimitry Andric    bool
1940b57cec5SDimitry Andric    operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
1950b57cec5SDimitry Andric               const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
1960b57cec5SDimitry Andric
1970b57cec5SDimitry Andric}  // __gnu_cxx
1980b57cec5SDimitry Andric
1990b57cec5SDimitry Andric*/
2000b57cec5SDimitry Andric
2010b57cec5SDimitry Andric#include <__config>
2020b57cec5SDimitry Andric#include <__hash_table>
2030b57cec5SDimitry Andric#include <functional>
2040b57cec5SDimitry Andric#include <stdexcept>
2050b57cec5SDimitry Andric#include <type_traits>
2060b57cec5SDimitry Andric#include <ext/__hash>
2070b57cec5SDimitry Andric
2080b57cec5SDimitry Andric#if __DEPRECATED
2090b57cec5SDimitry Andric#if defined(_LIBCPP_WARNING)
2100b57cec5SDimitry Andric    _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated.  Migrate to <unordered_map>")
2110b57cec5SDimitry Andric#else
2120b57cec5SDimitry Andric#   warning Use of the header <ext/hash_map> is deprecated.  Migrate to <unordered_map>
2130b57cec5SDimitry Andric#endif
2140b57cec5SDimitry Andric#endif
2150b57cec5SDimitry Andric
2160b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
2170b57cec5SDimitry Andric#pragma GCC system_header
2180b57cec5SDimitry Andric#endif
2190b57cec5SDimitry Andric
2200b57cec5SDimitry Andricnamespace __gnu_cxx {
2210b57cec5SDimitry Andric
2220b57cec5SDimitry Andrictemplate <class _Tp, class _Hash,
2230b57cec5SDimitry Andric          bool = std::is_empty<_Hash>::value && !std::__libcpp_is_final<_Hash>::value
2240b57cec5SDimitry Andric        >
2250b57cec5SDimitry Andricclass __hash_map_hasher
2260b57cec5SDimitry Andric    : private _Hash
2270b57cec5SDimitry Andric{
2280b57cec5SDimitry Andricpublic:
2290b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : _Hash() {}
2300b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : _Hash(__h) {}
2310b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return *this;}
2320b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2330b57cec5SDimitry Andric    size_t operator()(const _Tp& __x) const
2340b57cec5SDimitry Andric        {return static_cast<const _Hash&>(*this)(__x.first);}
2350b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2360b57cec5SDimitry Andric    size_t operator()(const typename _Tp::first_type& __x) const
2370b57cec5SDimitry Andric        {return static_cast<const _Hash&>(*this)(__x);}
2380b57cec5SDimitry Andric};
2390b57cec5SDimitry Andric
2400b57cec5SDimitry Andrictemplate <class _Tp, class _Hash>
2410b57cec5SDimitry Andricclass __hash_map_hasher<_Tp, _Hash, false>
2420b57cec5SDimitry Andric{
2430b57cec5SDimitry Andric    _Hash __hash_;
2440b57cec5SDimitry Andricpublic:
2450b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : __hash_() {}
2460b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : __hash_(__h) {}
2470b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return __hash_;}
2480b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2490b57cec5SDimitry Andric    size_t operator()(const _Tp& __x) const
2500b57cec5SDimitry Andric        {return __hash_(__x.first);}
2510b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2520b57cec5SDimitry Andric    size_t operator()(const typename _Tp::first_type& __x) const
2530b57cec5SDimitry Andric        {return __hash_(__x);}
2540b57cec5SDimitry Andric};
2550b57cec5SDimitry Andric
2560b57cec5SDimitry Andrictemplate <class _Tp, class _Pred,
2570b57cec5SDimitry Andric          bool = std::is_empty<_Pred>::value && !std::__libcpp_is_final<_Pred>::value
2580b57cec5SDimitry Andric         >
2590b57cec5SDimitry Andricclass __hash_map_equal
2600b57cec5SDimitry Andric    : private _Pred
2610b57cec5SDimitry Andric{
2620b57cec5SDimitry Andricpublic:
2630b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : _Pred() {}
2640b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : _Pred(__p) {}
2650b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return *this;}
2660b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2670b57cec5SDimitry Andric    bool operator()(const _Tp& __x, const _Tp& __y) const
2680b57cec5SDimitry Andric        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
2690b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2700b57cec5SDimitry Andric    bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
2710b57cec5SDimitry Andric        {return static_cast<const _Pred&>(*this)(__x, __y.first);}
2720b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2730b57cec5SDimitry Andric    bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
2740b57cec5SDimitry Andric        {return static_cast<const _Pred&>(*this)(__x.first, __y);}
2750b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2760b57cec5SDimitry Andric    bool operator()(const typename _Tp::first_type& __x,
2770b57cec5SDimitry Andric                    const typename _Tp::first_type& __y) const
2780b57cec5SDimitry Andric        {return static_cast<const _Pred&>(*this)(__x, __y);}
2790b57cec5SDimitry Andric};
2800b57cec5SDimitry Andric
2810b57cec5SDimitry Andrictemplate <class _Tp, class _Pred>
2820b57cec5SDimitry Andricclass __hash_map_equal<_Tp, _Pred, false>
2830b57cec5SDimitry Andric{
2840b57cec5SDimitry Andric    _Pred __pred_;
2850b57cec5SDimitry Andricpublic:
2860b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : __pred_() {}
2870b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : __pred_(__p) {}
2880b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return __pred_;}
2890b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2900b57cec5SDimitry Andric    bool operator()(const _Tp& __x, const _Tp& __y) const
2910b57cec5SDimitry Andric        {return __pred_(__x.first, __y.first);}
2920b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2930b57cec5SDimitry Andric    bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
2940b57cec5SDimitry Andric        {return __pred_(__x, __y.first);}
2950b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2960b57cec5SDimitry Andric    bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
2970b57cec5SDimitry Andric        {return __pred_(__x.first, __y);}
2980b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
2990b57cec5SDimitry Andric    bool operator()(const typename _Tp::first_type& __x,
3000b57cec5SDimitry Andric                    const typename _Tp::first_type& __y) const
3010b57cec5SDimitry Andric        {return __pred_(__x, __y);}
3020b57cec5SDimitry Andric};
3030b57cec5SDimitry Andric
3040b57cec5SDimitry Andrictemplate <class _Alloc>
3050b57cec5SDimitry Andricclass __hash_map_node_destructor
3060b57cec5SDimitry Andric{
3070b57cec5SDimitry Andric    typedef _Alloc                              allocator_type;
3080b57cec5SDimitry Andric    typedef std::allocator_traits<allocator_type>    __alloc_traits;
3090b57cec5SDimitry Andric    typedef typename __alloc_traits::value_type::__node_value_type value_type;
3100b57cec5SDimitry Andricpublic:
3110b57cec5SDimitry Andric    typedef typename __alloc_traits::pointer    pointer;
3120b57cec5SDimitry Andricprivate:
3130b57cec5SDimitry Andric    typedef typename value_type::first_type     first_type;
3140b57cec5SDimitry Andric    typedef typename value_type::second_type    second_type;
3150b57cec5SDimitry Andric
3160b57cec5SDimitry Andric    allocator_type& __na_;
3170b57cec5SDimitry Andric
3180b57cec5SDimitry Andricpublic:
3190b57cec5SDimitry Andric    bool __first_constructed;
3200b57cec5SDimitry Andric    bool __second_constructed;
3210b57cec5SDimitry Andric
322*cd0c3137SDimitry Andric    __hash_map_node_destructor(__hash_map_node_destructor const&) = default;
323*cd0c3137SDimitry Andric    __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;
324*cd0c3137SDimitry Andric
3250b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
3260b57cec5SDimitry Andric    explicit __hash_map_node_destructor(allocator_type& __na)
3270b57cec5SDimitry Andric        : __na_(__na),
3280b57cec5SDimitry Andric          __first_constructed(false),
3290b57cec5SDimitry Andric          __second_constructed(false)
3300b57cec5SDimitry Andric        {}
3310b57cec5SDimitry Andric
3320b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
3330b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
3340b57cec5SDimitry Andric    __hash_map_node_destructor(std::__hash_node_destructor<allocator_type>&& __x)
3350b57cec5SDimitry Andric        : __na_(__x.__na_),
3360b57cec5SDimitry Andric          __first_constructed(__x.__value_constructed),
3370b57cec5SDimitry Andric          __second_constructed(__x.__value_constructed)
3380b57cec5SDimitry Andric        {
3390b57cec5SDimitry Andric            __x.__value_constructed = false;
3400b57cec5SDimitry Andric        }
3410b57cec5SDimitry Andric#else  // _LIBCPP_CXX03_LANG
3420b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
3430b57cec5SDimitry Andric    __hash_map_node_destructor(const std::__hash_node_destructor<allocator_type>& __x)
3440b57cec5SDimitry Andric        : __na_(__x.__na_),
3450b57cec5SDimitry Andric          __first_constructed(__x.__value_constructed),
3460b57cec5SDimitry Andric          __second_constructed(__x.__value_constructed)
3470b57cec5SDimitry Andric        {
3480b57cec5SDimitry Andric            const_cast<bool&>(__x.__value_constructed) = false;
3490b57cec5SDimitry Andric        }
3500b57cec5SDimitry Andric#endif  // _LIBCPP_CXX03_LANG
3510b57cec5SDimitry Andric
3520b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
3530b57cec5SDimitry Andric    void operator()(pointer __p)
3540b57cec5SDimitry Andric    {
3550b57cec5SDimitry Andric        if (__second_constructed)
3560b57cec5SDimitry Andric            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
3570b57cec5SDimitry Andric        if (__first_constructed)
3580b57cec5SDimitry Andric            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
3590b57cec5SDimitry Andric        if (__p)
3600b57cec5SDimitry Andric            __alloc_traits::deallocate(__na_, __p, 1);
3610b57cec5SDimitry Andric    }
3620b57cec5SDimitry Andric};
3630b57cec5SDimitry Andric
3640b57cec5SDimitry Andrictemplate <class _HashIterator>
3650b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS __hash_map_iterator
3660b57cec5SDimitry Andric{
3670b57cec5SDimitry Andric    _HashIterator __i_;
3680b57cec5SDimitry Andric
3690b57cec5SDimitry Andric    typedef const typename _HashIterator::value_type::first_type key_type;
3700b57cec5SDimitry Andric    typedef typename _HashIterator::value_type::second_type      mapped_type;
3710b57cec5SDimitry Andricpublic:
3720b57cec5SDimitry Andric    typedef std::forward_iterator_tag                            iterator_category;
3730b57cec5SDimitry Andric    typedef std::pair<key_type, mapped_type>                     value_type;
3740b57cec5SDimitry Andric    typedef typename _HashIterator::difference_type              difference_type;
3750b57cec5SDimitry Andric    typedef value_type&                                          reference;
3760b57cec5SDimitry Andric    typedef typename std::__rebind_pointer<typename _HashIterator::pointer, value_type>::type
3770b57cec5SDimitry Andric        pointer;
3780b57cec5SDimitry Andric
3790b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {}
3800b57cec5SDimitry Andric
3810b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {}
3820b57cec5SDimitry Andric
3830b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();}
3840b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();}
3850b57cec5SDimitry Andric
3860b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;}
3870b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
3880b57cec5SDimitry Andric    __hash_map_iterator operator++(int)
3890b57cec5SDimitry Andric    {
3900b57cec5SDimitry Andric        __hash_map_iterator __t(*this);
3910b57cec5SDimitry Andric        ++(*this);
3920b57cec5SDimitry Andric        return __t;
3930b57cec5SDimitry Andric    }
3940b57cec5SDimitry Andric
3950b57cec5SDimitry Andric    friend _LIBCPP_INLINE_VISIBILITY
3960b57cec5SDimitry Andric    bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
3970b57cec5SDimitry Andric        {return __x.__i_ == __y.__i_;}
3980b57cec5SDimitry Andric    friend _LIBCPP_INLINE_VISIBILITY
3990b57cec5SDimitry Andric    bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
4000b57cec5SDimitry Andric        {return __x.__i_ != __y.__i_;}
4010b57cec5SDimitry Andric
4020b57cec5SDimitry Andric    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_map;
4030b57cec5SDimitry Andric    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_multimap;
4040b57cec5SDimitry Andric    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
4050b57cec5SDimitry Andric    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
4060b57cec5SDimitry Andric    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
4070b57cec5SDimitry Andric};
4080b57cec5SDimitry Andric
4090b57cec5SDimitry Andrictemplate <class _HashIterator>
4100b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator
4110b57cec5SDimitry Andric{
4120b57cec5SDimitry Andric    _HashIterator __i_;
4130b57cec5SDimitry Andric
4140b57cec5SDimitry Andric    typedef const typename _HashIterator::value_type::first_type key_type;
4150b57cec5SDimitry Andric    typedef typename _HashIterator::value_type::second_type      mapped_type;
4160b57cec5SDimitry Andricpublic:
4170b57cec5SDimitry Andric    typedef std::forward_iterator_tag                            iterator_category;
4180b57cec5SDimitry Andric    typedef std::pair<key_type, mapped_type>                     value_type;
4190b57cec5SDimitry Andric    typedef typename _HashIterator::difference_type              difference_type;
4200b57cec5SDimitry Andric    typedef const value_type&                                    reference;
4210b57cec5SDimitry Andric    typedef typename std::__rebind_pointer<typename _HashIterator::pointer, const value_type>::type
4220b57cec5SDimitry Andric        pointer;
4230b57cec5SDimitry Andric
4240b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {}
4250b57cec5SDimitry Andric
4260b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
4270b57cec5SDimitry Andric    __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}
4280b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
4290b57cec5SDimitry Andric    __hash_map_const_iterator(
4300b57cec5SDimitry Andric            __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
4310b57cec5SDimitry Andric                : __i_(__i.__i_) {}
4320b57cec5SDimitry Andric
4330b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
4340b57cec5SDimitry Andric    reference operator*() const {return *operator->();}
4350b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
4360b57cec5SDimitry Andric    pointer operator->() const {return (pointer)__i_.operator->();}
4370b57cec5SDimitry Andric
4380b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
4390b57cec5SDimitry Andric    __hash_map_const_iterator& operator++() {++__i_; return *this;}
4400b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
4410b57cec5SDimitry Andric    __hash_map_const_iterator operator++(int)
4420b57cec5SDimitry Andric    {
4430b57cec5SDimitry Andric        __hash_map_const_iterator __t(*this);
4440b57cec5SDimitry Andric        ++(*this);
4450b57cec5SDimitry Andric        return __t;
4460b57cec5SDimitry Andric    }
4470b57cec5SDimitry Andric
4480b57cec5SDimitry Andric    friend _LIBCPP_INLINE_VISIBILITY
4490b57cec5SDimitry Andric    bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
4500b57cec5SDimitry Andric        {return __x.__i_ == __y.__i_;}
4510b57cec5SDimitry Andric    friend _LIBCPP_INLINE_VISIBILITY
4520b57cec5SDimitry Andric    bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
4530b57cec5SDimitry Andric        {return __x.__i_ != __y.__i_;}
4540b57cec5SDimitry Andric
4550b57cec5SDimitry Andric    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_map;
4560b57cec5SDimitry Andric    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_multimap;
4570b57cec5SDimitry Andric    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
4580b57cec5SDimitry Andric    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
4590b57cec5SDimitry Andric};
4600b57cec5SDimitry Andric
4610b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>,
4620b57cec5SDimitry Andric          class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
4630b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS hash_map
4640b57cec5SDimitry Andric{
4650b57cec5SDimitry Andricpublic:
4660b57cec5SDimitry Andric    // types
4670b57cec5SDimitry Andric    typedef _Key                                           key_type;
4680b57cec5SDimitry Andric    typedef _Tp                                            mapped_type;
4690b57cec5SDimitry Andric    typedef _Tp                                            data_type;
4700b57cec5SDimitry Andric    typedef _Hash                                          hasher;
4710b57cec5SDimitry Andric    typedef _Pred                                          key_equal;
4720b57cec5SDimitry Andric    typedef _Alloc                                         allocator_type;
4730b57cec5SDimitry Andric    typedef std::pair<const key_type, mapped_type>         value_type;
4740b57cec5SDimitry Andric    typedef value_type&                                    reference;
4750b57cec5SDimitry Andric    typedef const value_type&                              const_reference;
4760b57cec5SDimitry Andric
4770b57cec5SDimitry Andricprivate:
4780b57cec5SDimitry Andric    typedef std::pair<key_type, mapped_type>                    __value_type;
4790b57cec5SDimitry Andric    typedef __hash_map_hasher<__value_type, hasher>   __hasher;
4800b57cec5SDimitry Andric    typedef __hash_map_equal<__value_type, key_equal> __key_equal;
4810b57cec5SDimitry Andric    typedef typename std::__rebind_alloc_helper<
4820b57cec5SDimitry Andric        std::allocator_traits<allocator_type>, __value_type>::type __allocator_type;
4830b57cec5SDimitry Andric
4840b57cec5SDimitry Andric    typedef std::__hash_table<__value_type, __hasher,
4850b57cec5SDimitry Andric                         __key_equal,  __allocator_type>   __table;
4860b57cec5SDimitry Andric
4870b57cec5SDimitry Andric    __table __table_;
4880b57cec5SDimitry Andric
4890b57cec5SDimitry Andric    typedef typename __table::__node_pointer               __node_pointer;
4900b57cec5SDimitry Andric    typedef typename __table::__node_const_pointer         __node_const_pointer;
4910b57cec5SDimitry Andric    typedef typename __table::__node_traits                __node_traits;
4920b57cec5SDimitry Andric    typedef typename __table::__node_allocator             __node_allocator;
4930b57cec5SDimitry Andric    typedef typename __table::__node                       __node;
4940b57cec5SDimitry Andric    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
4950b57cec5SDimitry Andric    typedef std::unique_ptr<__node, _Dp>                   __node_holder;
4960b57cec5SDimitry Andric    typedef std::allocator_traits<allocator_type>          __alloc_traits;
4970b57cec5SDimitry Andricpublic:
4980b57cec5SDimitry Andric    typedef typename __alloc_traits::pointer         pointer;
4990b57cec5SDimitry Andric    typedef typename __alloc_traits::const_pointer   const_pointer;
5000b57cec5SDimitry Andric    typedef typename __alloc_traits::size_type       size_type;
5010b57cec5SDimitry Andric    typedef typename __alloc_traits::difference_type difference_type;
5020b57cec5SDimitry Andric
5030b57cec5SDimitry Andric    typedef __hash_map_iterator<typename __table::iterator>       iterator;
5040b57cec5SDimitry Andric    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
5050b57cec5SDimitry Andric
5060b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY hash_map() {__table_.rehash(193);}
5070b57cec5SDimitry Andric    explicit hash_map(size_type __n, const hasher& __hf = hasher(),
5080b57cec5SDimitry Andric                           const key_equal& __eql = key_equal());
5090b57cec5SDimitry Andric    hash_map(size_type __n, const hasher& __hf,
5100b57cec5SDimitry Andric                  const key_equal& __eql,
5110b57cec5SDimitry Andric                  const allocator_type& __a);
5120b57cec5SDimitry Andric    template <class _InputIterator>
5130b57cec5SDimitry Andric        hash_map(_InputIterator __first, _InputIterator __last);
5140b57cec5SDimitry Andric    template <class _InputIterator>
5150b57cec5SDimitry Andric        hash_map(_InputIterator __first, _InputIterator __last,
5160b57cec5SDimitry Andric                      size_type __n, const hasher& __hf = hasher(),
5170b57cec5SDimitry Andric                      const key_equal& __eql = key_equal());
5180b57cec5SDimitry Andric    template <class _InputIterator>
5190b57cec5SDimitry Andric        hash_map(_InputIterator __first, _InputIterator __last,
5200b57cec5SDimitry Andric                      size_type __n, const hasher& __hf,
5210b57cec5SDimitry Andric                      const key_equal& __eql,
5220b57cec5SDimitry Andric                      const allocator_type& __a);
5230b57cec5SDimitry Andric    hash_map(const hash_map& __u);
5240b57cec5SDimitry Andric
5250b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5260b57cec5SDimitry Andric    allocator_type get_allocator() const
5270b57cec5SDimitry Andric        {return allocator_type(__table_.__node_alloc());}
5280b57cec5SDimitry Andric
5290b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5300b57cec5SDimitry Andric    bool      empty() const {return __table_.size() == 0;}
5310b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5320b57cec5SDimitry Andric    size_type size() const  {return __table_.size();}
5330b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5340b57cec5SDimitry Andric    size_type max_size() const {return __table_.max_size();}
5350b57cec5SDimitry Andric
5360b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5370b57cec5SDimitry Andric    iterator       begin()        {return __table_.begin();}
5380b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5390b57cec5SDimitry Andric    iterator       end()          {return __table_.end();}
5400b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5410b57cec5SDimitry Andric    const_iterator begin()  const {return __table_.begin();}
5420b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5430b57cec5SDimitry Andric    const_iterator end()    const {return __table_.end();}
5440b57cec5SDimitry Andric
5450b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5460b57cec5SDimitry Andric    std::pair<iterator, bool> insert(const value_type& __x)
5470b57cec5SDimitry Andric        {return __table_.__insert_unique(__x);}
5480b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5490b57cec5SDimitry Andric    iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
5500b57cec5SDimitry Andric    template <class _InputIterator>
5510b57cec5SDimitry Andric        _LIBCPP_INLINE_VISIBILITY
5520b57cec5SDimitry Andric        void insert(_InputIterator __first, _InputIterator __last);
5530b57cec5SDimitry Andric
5540b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5550b57cec5SDimitry Andric    void erase(const_iterator __p) {__table_.erase(__p.__i_);}
5560b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5570b57cec5SDimitry Andric    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
5580b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5590b57cec5SDimitry Andric    void erase(const_iterator __first, const_iterator __last)
5600b57cec5SDimitry Andric        {__table_.erase(__first.__i_, __last.__i_);}
5610b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5620b57cec5SDimitry Andric    void clear() {__table_.clear();}
5630b57cec5SDimitry Andric
5640b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5650b57cec5SDimitry Andric    void swap(hash_map& __u) {__table_.swap(__u.__table_);}
5660b57cec5SDimitry Andric
5670b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5680b57cec5SDimitry Andric    hasher hash_funct() const
5690b57cec5SDimitry Andric        {return __table_.hash_function().hash_function();}
5700b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5710b57cec5SDimitry Andric    key_equal key_eq() const
5720b57cec5SDimitry Andric        {return __table_.key_eq().key_eq();}
5730b57cec5SDimitry Andric
5740b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5750b57cec5SDimitry Andric    iterator       find(const key_type& __k)       {return __table_.find(__k);}
5760b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5770b57cec5SDimitry Andric    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
5780b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5790b57cec5SDimitry Andric    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
5800b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5810b57cec5SDimitry Andric    std::pair<iterator, iterator>             equal_range(const key_type& __k)
5820b57cec5SDimitry Andric        {return __table_.__equal_range_unique(__k);}
5830b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5840b57cec5SDimitry Andric    std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
5850b57cec5SDimitry Andric        {return __table_.__equal_range_unique(__k);}
5860b57cec5SDimitry Andric
5870b57cec5SDimitry Andric    mapped_type& operator[](const key_type& __k);
5880b57cec5SDimitry Andric
5890b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5900b57cec5SDimitry Andric    size_type bucket_count() const {return __table_.bucket_count();}
5910b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5920b57cec5SDimitry Andric    size_type max_bucket_count() const {return __table_.max_bucket_count();}
5930b57cec5SDimitry Andric
5940b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5950b57cec5SDimitry Andric    size_type elems_in_bucket(size_type __n) const
5960b57cec5SDimitry Andric        {return __table_.bucket_size(__n);}
5970b57cec5SDimitry Andric
5980b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
5990b57cec5SDimitry Andric    void resize(size_type __n) {__table_.rehash(__n);}
6000b57cec5SDimitry Andric
6010b57cec5SDimitry Andricprivate:
6020b57cec5SDimitry Andric    __node_holder __construct_node(const key_type& __k);
6030b57cec5SDimitry Andric};
6040b57cec5SDimitry Andric
6050b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
6060b57cec5SDimitry Andrichash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
6070b57cec5SDimitry Andric        size_type __n, const hasher& __hf, const key_equal& __eql)
6080b57cec5SDimitry Andric    : __table_(__hf, __eql)
6090b57cec5SDimitry Andric{
6100b57cec5SDimitry Andric    __table_.rehash(__n);
6110b57cec5SDimitry Andric}
6120b57cec5SDimitry Andric
6130b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
6140b57cec5SDimitry Andrichash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
6150b57cec5SDimitry Andric        size_type __n, const hasher& __hf, const key_equal& __eql,
6160b57cec5SDimitry Andric        const allocator_type& __a)
6170b57cec5SDimitry Andric    : __table_(__hf, __eql, __a)
6180b57cec5SDimitry Andric{
6190b57cec5SDimitry Andric    __table_.rehash(__n);
6200b57cec5SDimitry Andric}
6210b57cec5SDimitry Andric
6220b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
6230b57cec5SDimitry Andrictemplate <class _InputIterator>
6240b57cec5SDimitry Andrichash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
6250b57cec5SDimitry Andric        _InputIterator __first, _InputIterator __last)
6260b57cec5SDimitry Andric{
6270b57cec5SDimitry Andric    __table_.rehash(193);
6280b57cec5SDimitry Andric    insert(__first, __last);
6290b57cec5SDimitry Andric}
6300b57cec5SDimitry Andric
6310b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
6320b57cec5SDimitry Andrictemplate <class _InputIterator>
6330b57cec5SDimitry Andrichash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
6340b57cec5SDimitry Andric        _InputIterator __first, _InputIterator __last, size_type __n,
6350b57cec5SDimitry Andric        const hasher& __hf, const key_equal& __eql)
6360b57cec5SDimitry Andric    : __table_(__hf, __eql)
6370b57cec5SDimitry Andric{
6380b57cec5SDimitry Andric    __table_.rehash(__n);
6390b57cec5SDimitry Andric    insert(__first, __last);
6400b57cec5SDimitry Andric}
6410b57cec5SDimitry Andric
6420b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
6430b57cec5SDimitry Andrictemplate <class _InputIterator>
6440b57cec5SDimitry Andrichash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
6450b57cec5SDimitry Andric        _InputIterator __first, _InputIterator __last, size_type __n,
6460b57cec5SDimitry Andric        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
6470b57cec5SDimitry Andric    : __table_(__hf, __eql, __a)
6480b57cec5SDimitry Andric{
6490b57cec5SDimitry Andric    __table_.rehash(__n);
6500b57cec5SDimitry Andric    insert(__first, __last);
6510b57cec5SDimitry Andric}
6520b57cec5SDimitry Andric
6530b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
6540b57cec5SDimitry Andrichash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
6550b57cec5SDimitry Andric        const hash_map& __u)
6560b57cec5SDimitry Andric    : __table_(__u.__table_)
6570b57cec5SDimitry Andric{
6580b57cec5SDimitry Andric    __table_.rehash(__u.bucket_count());
6590b57cec5SDimitry Andric    insert(__u.begin(), __u.end());
6600b57cec5SDimitry Andric}
6610b57cec5SDimitry Andric
6620b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
6630b57cec5SDimitry Andrictypename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
6640b57cec5SDimitry Andrichash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
6650b57cec5SDimitry Andric{
6660b57cec5SDimitry Andric    __node_allocator& __na = __table_.__node_alloc();
6670b57cec5SDimitry Andric    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
6680b57cec5SDimitry Andric    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
6690b57cec5SDimitry Andric    __h.get_deleter().__first_constructed = true;
6700b57cec5SDimitry Andric    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
6710b57cec5SDimitry Andric    __h.get_deleter().__second_constructed = true;
6720b57cec5SDimitry Andric    return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
6730b57cec5SDimitry Andric}
6740b57cec5SDimitry Andric
6750b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
6760b57cec5SDimitry Andrictemplate <class _InputIterator>
6770b57cec5SDimitry Andricinline
6780b57cec5SDimitry Andricvoid
6790b57cec5SDimitry Andrichash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
6800b57cec5SDimitry Andric                                                       _InputIterator __last)
6810b57cec5SDimitry Andric{
6820b57cec5SDimitry Andric    for (; __first != __last; ++__first)
6830b57cec5SDimitry Andric        __table_.__insert_unique(*__first);
6840b57cec5SDimitry Andric}
6850b57cec5SDimitry Andric
6860b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
6870b57cec5SDimitry Andric_Tp&
6880b57cec5SDimitry Andrichash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
6890b57cec5SDimitry Andric{
6900b57cec5SDimitry Andric    iterator __i = find(__k);
6910b57cec5SDimitry Andric    if (__i != end())
6920b57cec5SDimitry Andric        return __i->second;
6930b57cec5SDimitry Andric    __node_holder __h = __construct_node(__k);
6940b57cec5SDimitry Andric    std::pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
6950b57cec5SDimitry Andric    __h.release();
6960b57cec5SDimitry Andric    return __r.first->second;
6970b57cec5SDimitry Andric}
6980b57cec5SDimitry Andric
6990b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
7000b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
7010b57cec5SDimitry Andricvoid
7020b57cec5SDimitry Andricswap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
7030b57cec5SDimitry Andric     hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
7040b57cec5SDimitry Andric{
7050b57cec5SDimitry Andric    __x.swap(__y);
7060b57cec5SDimitry Andric}
7070b57cec5SDimitry Andric
7080b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
7090b57cec5SDimitry Andricbool
7100b57cec5SDimitry Andricoperator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
7110b57cec5SDimitry Andric           const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
7120b57cec5SDimitry Andric{
7130b57cec5SDimitry Andric    if (__x.size() != __y.size())
7140b57cec5SDimitry Andric        return false;
7150b57cec5SDimitry Andric    typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
7160b57cec5SDimitry Andric                                                                 const_iterator;
7170b57cec5SDimitry Andric    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
7180b57cec5SDimitry Andric            __i != __ex; ++__i)
7190b57cec5SDimitry Andric    {
7200b57cec5SDimitry Andric        const_iterator __j = __y.find(__i->first);
7210b57cec5SDimitry Andric        if (__j == __ey || !(*__i == *__j))
7220b57cec5SDimitry Andric            return false;
7230b57cec5SDimitry Andric    }
7240b57cec5SDimitry Andric    return true;
7250b57cec5SDimitry Andric}
7260b57cec5SDimitry Andric
7270b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
7280b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
7290b57cec5SDimitry Andricbool
7300b57cec5SDimitry Andricoperator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
7310b57cec5SDimitry Andric           const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
7320b57cec5SDimitry Andric{
7330b57cec5SDimitry Andric    return !(__x == __y);
7340b57cec5SDimitry Andric}
7350b57cec5SDimitry Andric
7360b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>,
7370b57cec5SDimitry Andric          class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
7380b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS hash_multimap
7390b57cec5SDimitry Andric{
7400b57cec5SDimitry Andricpublic:
7410b57cec5SDimitry Andric    // types
7420b57cec5SDimitry Andric    typedef _Key                                           key_type;
7430b57cec5SDimitry Andric    typedef _Tp                                            mapped_type;
7440b57cec5SDimitry Andric    typedef _Tp                                            data_type;
7450b57cec5SDimitry Andric    typedef _Hash                                          hasher;
7460b57cec5SDimitry Andric    typedef _Pred                                          key_equal;
7470b57cec5SDimitry Andric    typedef _Alloc                                         allocator_type;
7480b57cec5SDimitry Andric    typedef std::pair<const key_type, mapped_type>         value_type;
7490b57cec5SDimitry Andric    typedef value_type&                                    reference;
7500b57cec5SDimitry Andric    typedef const value_type&                              const_reference;
7510b57cec5SDimitry Andric
7520b57cec5SDimitry Andricprivate:
7530b57cec5SDimitry Andric    typedef std::pair<key_type, mapped_type>               __value_type;
7540b57cec5SDimitry Andric    typedef __hash_map_hasher<__value_type, hasher>   __hasher;
7550b57cec5SDimitry Andric    typedef __hash_map_equal<__value_type, key_equal> __key_equal;
7560b57cec5SDimitry Andric    typedef typename std::__rebind_alloc_helper<std::allocator_traits<allocator_type>, __value_type>::type __allocator_type;
7570b57cec5SDimitry Andric
7580b57cec5SDimitry Andric    typedef std::__hash_table<__value_type, __hasher,
7590b57cec5SDimitry Andric                         __key_equal,  __allocator_type>   __table;
7600b57cec5SDimitry Andric
7610b57cec5SDimitry Andric    __table __table_;
7620b57cec5SDimitry Andric
7630b57cec5SDimitry Andric    typedef typename __table::__node_traits                __node_traits;
7640b57cec5SDimitry Andric    typedef typename __table::__node_allocator             __node_allocator;
7650b57cec5SDimitry Andric    typedef typename __table::__node                       __node;
7660b57cec5SDimitry Andric    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
7670b57cec5SDimitry Andric    typedef std::unique_ptr<__node, _Dp>                         __node_holder;
7680b57cec5SDimitry Andric    typedef std::allocator_traits<allocator_type>               __alloc_traits;
7690b57cec5SDimitry Andricpublic:
7700b57cec5SDimitry Andric    typedef typename __alloc_traits::pointer         pointer;
7710b57cec5SDimitry Andric    typedef typename __alloc_traits::const_pointer   const_pointer;
7720b57cec5SDimitry Andric    typedef typename __alloc_traits::size_type       size_type;
7730b57cec5SDimitry Andric    typedef typename __alloc_traits::difference_type difference_type;
7740b57cec5SDimitry Andric
7750b57cec5SDimitry Andric    typedef __hash_map_iterator<typename __table::iterator>       iterator;
7760b57cec5SDimitry Andric    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
7770b57cec5SDimitry Andric
7780b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
7790b57cec5SDimitry Andric    hash_multimap() {__table_.rehash(193);}
7800b57cec5SDimitry Andric    explicit hash_multimap(size_type __n, const hasher& __hf = hasher(),
7810b57cec5SDimitry Andric                                const key_equal& __eql = key_equal());
7820b57cec5SDimitry Andric    hash_multimap(size_type __n, const hasher& __hf,
7830b57cec5SDimitry Andric                                const key_equal& __eql,
7840b57cec5SDimitry Andric                                const allocator_type& __a);
7850b57cec5SDimitry Andric    template <class _InputIterator>
7860b57cec5SDimitry Andric        hash_multimap(_InputIterator __first, _InputIterator __last);
7870b57cec5SDimitry Andric    template <class _InputIterator>
7880b57cec5SDimitry Andric        hash_multimap(_InputIterator __first, _InputIterator __last,
7890b57cec5SDimitry Andric                      size_type __n, const hasher& __hf = hasher(),
7900b57cec5SDimitry Andric                      const key_equal& __eql = key_equal());
7910b57cec5SDimitry Andric    template <class _InputIterator>
7920b57cec5SDimitry Andric        hash_multimap(_InputIterator __first, _InputIterator __last,
7930b57cec5SDimitry Andric                      size_type __n, const hasher& __hf,
7940b57cec5SDimitry Andric                      const key_equal& __eql,
7950b57cec5SDimitry Andric                      const allocator_type& __a);
7960b57cec5SDimitry Andric    hash_multimap(const hash_multimap& __u);
7970b57cec5SDimitry Andric
7980b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
7990b57cec5SDimitry Andric    allocator_type get_allocator() const
8000b57cec5SDimitry Andric        {return allocator_type(__table_.__node_alloc());}
8010b57cec5SDimitry Andric
8020b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8030b57cec5SDimitry Andric    bool      empty() const {return __table_.size() == 0;}
8040b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8050b57cec5SDimitry Andric    size_type size() const  {return __table_.size();}
8060b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8070b57cec5SDimitry Andric    size_type max_size() const {return __table_.max_size();}
8080b57cec5SDimitry Andric
8090b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8100b57cec5SDimitry Andric    iterator       begin()        {return __table_.begin();}
8110b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8120b57cec5SDimitry Andric    iterator       end()          {return __table_.end();}
8130b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8140b57cec5SDimitry Andric    const_iterator begin()  const {return __table_.begin();}
8150b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8160b57cec5SDimitry Andric    const_iterator end()    const {return __table_.end();}
8170b57cec5SDimitry Andric
8180b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8190b57cec5SDimitry Andric    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
8200b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8210b57cec5SDimitry Andric    iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
8220b57cec5SDimitry Andric    template <class _InputIterator>
8230b57cec5SDimitry Andric        _LIBCPP_INLINE_VISIBILITY
8240b57cec5SDimitry Andric        void insert(_InputIterator __first, _InputIterator __last);
8250b57cec5SDimitry Andric
8260b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8270b57cec5SDimitry Andric    void erase(const_iterator __p) {__table_.erase(__p.__i_);}
8280b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8290b57cec5SDimitry Andric    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
8300b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8310b57cec5SDimitry Andric    void erase(const_iterator __first, const_iterator __last)
8320b57cec5SDimitry Andric        {__table_.erase(__first.__i_, __last.__i_);}
8330b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8340b57cec5SDimitry Andric    void clear() {__table_.clear();}
8350b57cec5SDimitry Andric
8360b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8370b57cec5SDimitry Andric    void swap(hash_multimap& __u) {__table_.swap(__u.__table_);}
8380b57cec5SDimitry Andric
8390b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8400b57cec5SDimitry Andric    hasher hash_funct() const
8410b57cec5SDimitry Andric        {return __table_.hash_function().hash_function();}
8420b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8430b57cec5SDimitry Andric    key_equal key_eq() const
8440b57cec5SDimitry Andric        {return __table_.key_eq().key_eq();}
8450b57cec5SDimitry Andric
8460b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8470b57cec5SDimitry Andric    iterator       find(const key_type& __k)       {return __table_.find(__k);}
8480b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8490b57cec5SDimitry Andric    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
8500b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8510b57cec5SDimitry Andric    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
8520b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8530b57cec5SDimitry Andric    std::pair<iterator, iterator>             equal_range(const key_type& __k)
8540b57cec5SDimitry Andric        {return __table_.__equal_range_multi(__k);}
8550b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8560b57cec5SDimitry Andric    std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
8570b57cec5SDimitry Andric        {return __table_.__equal_range_multi(__k);}
8580b57cec5SDimitry Andric
8590b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8600b57cec5SDimitry Andric    size_type bucket_count() const {return __table_.bucket_count();}
8610b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8620b57cec5SDimitry Andric    size_type max_bucket_count() const {return __table_.max_bucket_count();}
8630b57cec5SDimitry Andric
8640b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8650b57cec5SDimitry Andric    size_type elems_in_bucket(size_type __n) const
8660b57cec5SDimitry Andric        {return __table_.bucket_size(__n);}
8670b57cec5SDimitry Andric
8680b57cec5SDimitry Andric    _LIBCPP_INLINE_VISIBILITY
8690b57cec5SDimitry Andric    void resize(size_type __n) {__table_.rehash(__n);}
8700b57cec5SDimitry Andric};
8710b57cec5SDimitry Andric
8720b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
8730b57cec5SDimitry Andrichash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
8740b57cec5SDimitry Andric        size_type __n, const hasher& __hf, const key_equal& __eql)
8750b57cec5SDimitry Andric    : __table_(__hf, __eql)
8760b57cec5SDimitry Andric{
8770b57cec5SDimitry Andric    __table_.rehash(__n);
8780b57cec5SDimitry Andric}
8790b57cec5SDimitry Andric
8800b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
8810b57cec5SDimitry Andrichash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
8820b57cec5SDimitry Andric        size_type __n, const hasher& __hf, const key_equal& __eql,
8830b57cec5SDimitry Andric        const allocator_type& __a)
8840b57cec5SDimitry Andric    : __table_(__hf, __eql, __a)
8850b57cec5SDimitry Andric{
8860b57cec5SDimitry Andric    __table_.rehash(__n);
8870b57cec5SDimitry Andric}
8880b57cec5SDimitry Andric
8890b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
8900b57cec5SDimitry Andrictemplate <class _InputIterator>
8910b57cec5SDimitry Andrichash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
8920b57cec5SDimitry Andric        _InputIterator __first, _InputIterator __last)
8930b57cec5SDimitry Andric{
8940b57cec5SDimitry Andric    __table_.rehash(193);
8950b57cec5SDimitry Andric    insert(__first, __last);
8960b57cec5SDimitry Andric}
8970b57cec5SDimitry Andric
8980b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
8990b57cec5SDimitry Andrictemplate <class _InputIterator>
9000b57cec5SDimitry Andrichash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
9010b57cec5SDimitry Andric        _InputIterator __first, _InputIterator __last, size_type __n,
9020b57cec5SDimitry Andric        const hasher& __hf, const key_equal& __eql)
9030b57cec5SDimitry Andric    : __table_(__hf, __eql)
9040b57cec5SDimitry Andric{
9050b57cec5SDimitry Andric    __table_.rehash(__n);
9060b57cec5SDimitry Andric    insert(__first, __last);
9070b57cec5SDimitry Andric}
9080b57cec5SDimitry Andric
9090b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
9100b57cec5SDimitry Andrictemplate <class _InputIterator>
9110b57cec5SDimitry Andrichash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
9120b57cec5SDimitry Andric        _InputIterator __first, _InputIterator __last, size_type __n,
9130b57cec5SDimitry Andric        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
9140b57cec5SDimitry Andric    : __table_(__hf, __eql, __a)
9150b57cec5SDimitry Andric{
9160b57cec5SDimitry Andric    __table_.rehash(__n);
9170b57cec5SDimitry Andric    insert(__first, __last);
9180b57cec5SDimitry Andric}
9190b57cec5SDimitry Andric
9200b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
9210b57cec5SDimitry Andrichash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
9220b57cec5SDimitry Andric        const hash_multimap& __u)
9230b57cec5SDimitry Andric    : __table_(__u.__table_)
9240b57cec5SDimitry Andric{
9250b57cec5SDimitry Andric    __table_.rehash(__u.bucket_count());
9260b57cec5SDimitry Andric    insert(__u.begin(), __u.end());
9270b57cec5SDimitry Andric}
9280b57cec5SDimitry Andric
9290b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
9300b57cec5SDimitry Andrictemplate <class _InputIterator>
9310b57cec5SDimitry Andricinline
9320b57cec5SDimitry Andricvoid
9330b57cec5SDimitry Andrichash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
9340b57cec5SDimitry Andric                                                            _InputIterator __last)
9350b57cec5SDimitry Andric{
9360b57cec5SDimitry Andric    for (; __first != __last; ++__first)
9370b57cec5SDimitry Andric        __table_.__insert_multi(*__first);
9380b57cec5SDimitry Andric}
9390b57cec5SDimitry Andric
9400b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
9410b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
9420b57cec5SDimitry Andricvoid
9430b57cec5SDimitry Andricswap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
9440b57cec5SDimitry Andric     hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
9450b57cec5SDimitry Andric{
9460b57cec5SDimitry Andric    __x.swap(__y);
9470b57cec5SDimitry Andric}
9480b57cec5SDimitry Andric
9490b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
9500b57cec5SDimitry Andricbool
9510b57cec5SDimitry Andricoperator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
9520b57cec5SDimitry Andric           const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
9530b57cec5SDimitry Andric{
9540b57cec5SDimitry Andric    if (__x.size() != __y.size())
9550b57cec5SDimitry Andric        return false;
9560b57cec5SDimitry Andric    typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
9570b57cec5SDimitry Andric                                                                 const_iterator;
9580b57cec5SDimitry Andric    typedef std::pair<const_iterator, const_iterator> _EqRng;
9590b57cec5SDimitry Andric    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
9600b57cec5SDimitry Andric    {
9610b57cec5SDimitry Andric        _EqRng __xeq = __x.equal_range(__i->first);
9620b57cec5SDimitry Andric        _EqRng __yeq = __y.equal_range(__i->first);
9630b57cec5SDimitry Andric        if (_VSTD::distance(__xeq.first, __xeq.second) !=
9640b57cec5SDimitry Andric            _VSTD::distance(__yeq.first, __yeq.second) ||
9650b57cec5SDimitry Andric                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
9660b57cec5SDimitry Andric            return false;
9670b57cec5SDimitry Andric        __i = __xeq.second;
9680b57cec5SDimitry Andric    }
9690b57cec5SDimitry Andric    return true;
9700b57cec5SDimitry Andric}
9710b57cec5SDimitry Andric
9720b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
9730b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY
9740b57cec5SDimitry Andricbool
9750b57cec5SDimitry Andricoperator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
9760b57cec5SDimitry Andric           const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
9770b57cec5SDimitry Andric{
9780b57cec5SDimitry Andric    return !(__x == __y);
9790b57cec5SDimitry Andric}
9800b57cec5SDimitry Andric
9810b57cec5SDimitry Andric} // __gnu_cxx
9820b57cec5SDimitry Andric
9830b57cec5SDimitry Andric#endif  // _LIBCPP_HASH_MAP
984