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