hash_map revision 256281
153813Simp// -*- C++ -*- 2120330Simp//===-------------------------- hash_map ----------------------------------===// 3100213Simp// 452506Simp// The LLVM Compiler Infrastructure 552506Simp// 6140752Simp// This file is dual licensed under the MIT and the University of Illinois Open 752506Simp// Source Licenses. See LICENSE.TXT for details. 852506Simp// 952506Simp//===----------------------------------------------------------------------===// 1052506Simp 1152506Simp#ifndef _LIBCPP_HASH_MAP 1252506Simp#define _LIBCPP_HASH_MAP 1352506Simp 1452506Simp/* 1552506Simp 1652506Simp hash_map synopsis 1752506Simp 1852506Simpnamespace __gnu_cxx 1952506Simp{ 2052506Simp 2152506Simptemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 2252506Simp class Alloc = allocator<pair<const Key, T>>> 2352506Simpclass hash_map 2452506Simp{ 2552506Simppublic: 2652506Simp // types 2752506Simp typedef Key key_type; 2852506Simp typedef T mapped_type; 2952506Simp typedef Hash hasher; 3052506Simp typedef Pred key_equal; 3152506Simp typedef Alloc allocator_type; 3252506Simp typedef pair<const key_type, mapped_type> value_type; 3352506Simp typedef value_type& reference; 3452506Simp typedef const value_type& const_reference; 3552506Simp typedef typename allocator_traits<allocator_type>::pointer pointer; 3652506Simp typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 3752506Simp typedef typename allocator_traits<allocator_type>::size_type size_type; 3852506Simp typedef typename allocator_traits<allocator_type>::difference_type difference_type; 3952506Simp 4052506Simp typedef /unspecified/ iterator; 41140752Simp typedef /unspecified/ const_iterator; 42140752Simp 43140752Simp explicit hash_map(size_type n = 193, const hasher& hf = hasher(), 44140752Simp const key_equal& eql = key_equal(), 45140752Simp const allocator_type& a = allocator_type()); 46140752Simp template <class InputIterator> 47140752Simp hash_map(InputIterator f, InputIterator l, 48140752Simp size_type n = 193, const hasher& hf = hasher(), 49140752Simp const key_equal& eql = key_equal(), 50140752Simp const allocator_type& a = allocator_type()); 51140752Simp hash_map(const hash_map&); 52140752Simp ~hash_map(); 53140752Simp hash_map& operator=(const hash_map&); 54140752Simp 55140752Simp allocator_type get_allocator() const; 56140752Simp 57140752Simp bool empty() const; 58140752Simp size_type size() const; 59140752Simp size_type max_size() const; 60140752Simp 61140752Simp iterator begin(); 62140752Simp iterator end(); 63140752Simp const_iterator begin() const; 64140752Simp const_iterator end() const; 65140752Simp 66140752Simp pair<iterator, bool> insert(const value_type& obj); 67140752Simp template <class InputIterator> 6852506Simp void insert(InputIterator first, InputIterator last); 69140749Simp 70140749Simp void erase(const_iterator position); 71140749Simp size_type erase(const key_type& k); 72140749Simp void erase(const_iterator first, const_iterator last); 73140749Simp void clear(); 7486269Simp 7552506Simp void swap(hash_map&); 7652506Simp 77140793Simp hasher hash_funct() const; 78140793Simp key_equal key_eq() const; 7958545Simp 8052506Simp iterator find(const key_type& k); 8165039Simp const_iterator find(const key_type& k) const; 8265039Simp size_type count(const key_type& k) const; 8352506Simp pair<iterator, iterator> equal_range(const key_type& k); 84140793Simp pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 85148141Simp 86140793Simp mapped_type& operator[](const key_type& k); 8752506Simp 8852506Simp size_type bucket_count() const; 8952506Simp size_type max_bucket_count() const; 9052506Simp 9158545Simp size_type elems_in_bucket(size_type n) const; 9252506Simp 9386455Simp void resize(size_type n); 9479270Simp}; 95107359Snon 9652506Simptemplate <class Key, class T, class Hash, class Pred, class Alloc> 9786269Simp void swap(hash_map<Key, T, Hash, Pred, Alloc>& x, 9886455Simp hash_map<Key, T, Hash, Pred, Alloc>& y); 99119225Simp 10052506Simptemplate <class Key, class T, class Hash, class Pred, class Alloc> 101140749Simp bool 10286455Simp operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x, 10358545Simp const hash_map<Key, T, Hash, Pred, Alloc>& y); 104104854Simp 105140886Simptemplate <class Key, class T, class Hash, class Pred, class Alloc> 10652506Simp bool 10786455Simp operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x, 10852506Simp const hash_map<Key, T, Hash, Pred, Alloc>& y); 10986455Simp 11053813Simptemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 111148141Simp class Alloc = allocator<pair<const Key, T>>> 112100213Simpclass hash_multimap 11358545Simp{ 11489945Simppublic: 11584514Simp // types 116147872Simp typedef Key key_type; 11758545Simp typedef T mapped_type; 118119234Simp typedef Hash hasher; 11969138Speter typedef Pred key_equal; 120118634Simp typedef Alloc allocator_type; 12152506Simp typedef pair<const key_type, mapped_type> value_type; 12258545Simp typedef value_type& reference; 123140837Simp typedef const value_type& const_reference; 124140793Simp typedef typename allocator_traits<allocator_type>::pointer pointer; 125140793Simp typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 126147872Simp typedef typename allocator_traits<allocator_type>::size_type size_type; 127140793Simp typedef typename allocator_traits<allocator_type>::difference_type difference_type; 12858545Simp 12965039Simp typedef /unspecified/ iterator; 13092471Simp typedef /unspecified/ const_iterator; 131140793Simp 132116207Simp explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(), 13384514Simp const key_equal& eql = key_equal(), 13479270Simp const allocator_type& a = allocator_type()); 135140793Simp template <class InputIterator> 13679270Simp hash_multimap(InputIterator f, InputIterator l, 137117438Simp size_type n = 193, const hasher& hf = hasher(), 138117602Simp const key_equal& eql = key_equal(), 139148141Simp const allocator_type& a = allocator_type()); 140118895Simp explicit hash_multimap(const allocator_type&); 141119240Simp hash_multimap(const hash_multimap&); 142119240Simp ~hash_multimap(); 143119240Simp hash_multimap& operator=(const hash_multimap&); 144119240Simp 14593620Simp allocator_type get_allocator() const; 14686455Simp 147119240Simp bool empty() const; 148119240Simp size_type size() const; 149119240Simp size_type max_size() const; 150119240Simp 151119240Simp iterator begin(); 152147872Simp iterator end(); 153140793Simp const_iterator begin() const; 154119240Simp const_iterator end() const; 155141122Simp 156141122Simp iterator insert(const value_type& obj); 157141122Simp template <class InputIterator> 158141122Simp void insert(InputIterator first, InputIterator last); 159141122Simp 160141122Simp void erase(const_iterator position); 161141122Simp size_type erase(const key_type& k); 162141122Simp void erase(const_iterator first, const_iterator last); 163145247Sdamien void clear(); 164141122Simp 165119240Simp void swap(hash_multimap&); 166119240Simp 167140792Simp hasher hash_funct() const; 168140792Simp key_equal key_eq() const; 169141122Simp 170119240Simp iterator find(const key_type& k); 171140793Simp const_iterator find(const key_type& k) const; 17286455Simp size_type count(const key_type& k) const; 17386455Simp pair<iterator, iterator> equal_range(const key_type& k); 17489945Simp pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 17553813Simp 17671279Simp size_type bucket_count() const; 17771283Simp size_type max_bucket_count() const; 178113667Ssanpei 17953813Simp size_type elems_in_bucket(size_type n) const; 18052506Simp 181140793Simp void resize(size_type n); 182140792Simp}; 183107359Snon 18471283Simptemplate <class Key, class T, class Hash, class Pred, class Alloc> 18552506Simp void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x, 18652506Simp hash_multimap<Key, T, Hash, Pred, Alloc>& y); 18786269Simp 18886269Simptemplate <class Key, class T, class Hash, class Pred, class Alloc> 18952506Simp bool 19053813Simp operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x, 19152506Simp const hash_multimap<Key, T, Hash, Pred, Alloc>& y); 19265039Simp 19386269Simptemplate <class Key, class T, class Hash, class Pred, class Alloc> 19486269Simp bool 19586269Simp operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x, 196135002Semax const hash_multimap<Key, T, Hash, Pred, Alloc>& y); 19786269Simp 19852506Simp} // __gnu_cxx 19952506Simp 20052506Simp*/ 20193893Simp 20286455Simp#include <__config> 20384514Simp#include <__hash_table> 20452506Simp#include <functional> 205104854Simp#include <stdexcept> 206104854Simp#include <ext/__hash> 20794461Simp 20886269Simp#if __DEPRECATED 20986269Simp#warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map> 21086269Simp#endif 211147872Simp 21286269Simp#pragma GCC system_header 21386269Simp 21486269Simpnamespace __gnu_cxx { 21586269Simp 21686269Simpusing namespace std; 21786269Simp 218117614Simptemplate <class _Tp, class _Hash, bool = is_empty<_Hash>::value 219117614Simp#if __has_feature(is_final) 220117614Simp && !__is_final(_Hash) 22186269Simp#endif 22286269Simp > 22386269Simpclass __hash_map_hasher 224140793Simp : private _Hash 225140793Simp{ 226140793Simppublic: 227140793Simp _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : _Hash() {} 22886455Simp _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : _Hash(__h) {} 22986455Simp _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return *this;} 23086455Simp _LIBCPP_INLINE_VISIBILITY 231116207Simp size_t operator()(const _Tp& __x) const 232116207Simp {return static_cast<const _Hash&>(*this)(__x.first);} 233116207Simp _LIBCPP_INLINE_VISIBILITY 234117438Simp size_t operator()(const typename _Tp::first_type& __x) const 235117445Ssimokawa {return static_cast<const _Hash&>(*this)(__x);} 236117438Simp}; 23786269Simp 23886269Simptemplate <class _Tp, class _Hash> 23986269Simpclass __hash_map_hasher<_Tp, _Hash, false> 24086269Simp{ 241104854Simp _Hash __hash_; 24286269Simppublic: 24387757Simp _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : __hash_() {} 24487757Simp _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : __hash_(__h) {} 24587757Simp _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return __hash_;} 24686455Simp _LIBCPP_INLINE_VISIBILITY 24786455Simp size_t operator()(const _Tp& __x) const 24886455Simp {return __hash_(__x.first);} 249119231Simp _LIBCPP_INLINE_VISIBILITY 250147872Simp size_t operator()(const typename _Tp::first_type& __x) const 251147872Simp {return __hash_(__x);} 252119231Simp}; 253147956Simp 254119231Simptemplate <class _Tp, class _Pred, bool = is_empty<_Pred>::value 255119231Simp#if __has_feature(is_final) 25686269Simp && !__is_final(_Pred) 257147872Simp#endif 258117759Simp > 259147872Simpclass __hash_map_equal 26086269Simp : private _Pred 261109455Sshiba{ 262104854Simppublic: 26387044Simp _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : _Pred() {} 26486269Simp _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : _Pred(__p) {} 26565039Simp _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return *this;} 26686269Simp _LIBCPP_INLINE_VISIBILITY 267147872Simp bool operator()(const _Tp& __x, const _Tp& __y) const 26865039Simp {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 26965039Simp _LIBCPP_INLINE_VISIBILITY 27052506Simp bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 27186455Simp {return static_cast<const _Pred&>(*this)(__x, __y.first);} 27252506Simp _LIBCPP_INLINE_VISIBILITY 273147872Simp bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 274147872Simp {return static_cast<const _Pred&>(*this)(__x.first, __y);} 27552506Simp _LIBCPP_INLINE_VISIBILITY 27686269Simp bool operator()(const typename _Tp::first_type& __x, 27786269Simp const typename _Tp::first_type& __y) const 27886269Simp {return static_cast<const _Pred&>(*this)(__x, __y);} 27953813Simp}; 28052506Simp 28152506Simptemplate <class _Tp, class _Pred> 28252506Simpclass __hash_map_equal<_Tp, _Pred, false> 28352506Simp{ 28452506Simp _Pred __pred_; 28552506Simppublic: 28652506Simp _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : __pred_() {} 287119225Simp _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : __pred_(__p) {} 288119225Simp _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return __pred_;} 289119225Simp _LIBCPP_INLINE_VISIBILITY 290119225Simp bool operator()(const _Tp& __x, const _Tp& __y) const 29186455Simp {return __pred_(__x.first, __y.first);} 29286455Simp _LIBCPP_INLINE_VISIBILITY 29386455Simp bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 29489945Simp {return __pred_(__x, __y.first);} 29589945Simp _LIBCPP_INLINE_VISIBILITY 29689945Simp bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 29771279Simp {return __pred_(__x.first, __y);} 29871279Simp _LIBCPP_INLINE_VISIBILITY 29971279Simp bool operator()(const typename _Tp::first_type& __x, 30086269Simp const typename _Tp::first_type& __y) const 301100213Simp {return __pred_(__x, __y);} 302147579Simp}; 30371279Simp 30486269Simptemplate <class _Alloc> 30586269Simpclass __hash_map_node_destructor 30686269Simp{ 30789945Simp typedef _Alloc allocator_type; 30889945Simp typedef allocator_traits<allocator_type> __alloc_traits; 30989945Simp typedef typename __alloc_traits::value_type::value_type value_type; 31086269Simppublic: 31186269Simp typedef typename __alloc_traits::pointer pointer; 31286269Simpprivate: 31352506Simp typedef typename value_type::first_type first_type; 314139963Simp typedef typename value_type::second_type second_type; 31552506Simp 31686269Simp allocator_type& __na_; 31753813Simp 318120330Simp __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 31953813Simp 320100213Simppublic: 321100213Simp bool __first_constructed; 322100213Simp bool __second_constructed; 323140886Simp 324147872Simp _LIBCPP_INLINE_VISIBILITY 325140887Simp explicit __hash_map_node_destructor(allocator_type& __na) 326140886Simp : __na_(__na), 32792471Simp __first_constructed(false), 32892471Simp __second_constructed(false) 32992471Simp {} 33052506Simp 33171279Simp#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 33265039Simp _LIBCPP_INLINE_VISIBILITY 33365039Simp __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 33465039Simp : __na_(__x.__na_), 33565039Simp __first_constructed(__x.__value_constructed), 33687044Simp __second_constructed(__x.__value_constructed) 33765039Simp { 33852506Simp __x.__value_constructed = false; 33965039Simp } 34089103Simp#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 34153813Simp _LIBCPP_INLINE_VISIBILITY 34252506Simp __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 34365039Simp : __na_(__x.__na_), 34486269Simp __first_constructed(__x.__value_constructed), 34565039Simp __second_constructed(__x.__value_constructed) 346121960Simp { 347129164Simp const_cast<bool&>(__x.__value_constructed) = false; 34865039Simp } 349119213Simp#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 350127422Simp 351140520Simp _LIBCPP_INLINE_VISIBILITY 352140520Simp void operator()(pointer __p) 353140520Simp { 354119213Simp if (__second_constructed) 35552506Simp __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second)); 35679270Simp if (__first_constructed) 357117764Simp __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); 35852506Simp if (__p) 35986269Simp __alloc_traits::deallocate(__na_, __p, 1); 36086269Simp } 361147872Simp}; 36265039Simp 36386269Simptemplate <class _HashIterator> 36486269Simpclass _LIBCPP_TYPE_VIS __hash_map_iterator 36586269Simp{ 36658545Simp _HashIterator __i_; 36771279Simp 36858545Simp typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 36952506Simp typedef const typename _HashIterator::value_type::first_type key_type; 37086269Simp typedef typename _HashIterator::value_type::second_type mapped_type; 37158545Simppublic: 37252506Simp typedef forward_iterator_tag iterator_category; 37352506Simp typedef pair<key_type, mapped_type> value_type; 37452506Simp typedef typename _HashIterator::difference_type difference_type; 37586269Simp typedef value_type& reference; 37686269Simp typedef typename __pointer_traits::template 377148141Simp#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 378148141Simp rebind<value_type> 37986269Simp#else 38086269Simp rebind<value_type>::other 38186269Simp#endif 382107359Snon pointer; 38386269Simp 384140749Simp _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {} 385140749Simp 386140749Simp _LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {} 38752506Simp 388147956Simp _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();} 38986269Simp _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();} 39052506Simp 39153813Simp _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;} 39252506Simp _LIBCPP_INLINE_VISIBILITY 39352506Simp __hash_map_iterator operator++(int) 39458545Simp { 395140515Simp __hash_map_iterator __t(*this); 39658545Simp ++(*this); 39758545Simp return __t; 398118895Simp } 399118895Simp 400118895Simp friend _LIBCPP_INLINE_VISIBILITY 40186269Simp bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 40286269Simp {return __x.__i_ == __y.__i_;} 40386269Simp friend _LIBCPP_INLINE_VISIBILITY 404147872Simp bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 40586455Simp {return __x.__i_ != __y.__i_;} 40686269Simp 40786269Simp template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS hash_map; 40886269Simp template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS hash_multimap; 409147872Simp template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator; 410147872Simp template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator; 411147872Simp template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator; 412104831Simp}; 413106891Simp 414106891Simptemplate <class _HashIterator> 415147872Simpclass _LIBCPP_TYPE_VIS __hash_map_const_iterator 416147872Simp{ 41786269Simp _HashIterator __i_; 41886455Simp 41986455Simp typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 42093620Simp typedef const typename _HashIterator::value_type::first_type key_type; 42186455Simp typedef typename _HashIterator::value_type::second_type mapped_type; 42279270Simppublic: 423147872Simp typedef forward_iterator_tag iterator_category; 424147872Simp typedef pair<key_type, mapped_type> value_type; 425147872Simp typedef typename _HashIterator::difference_type difference_type; 426147872Simp typedef const value_type& reference; 42779270Simp typedef typename __pointer_traits::template 428147872Simp#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 42979270Simp rebind<value_type> 430140792Simp#else 431140792Simp rebind<value_type>::other 432140792Simp#endif 43358545Simp pointer; 434100213Simp 43558545Simp _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {} 43658545Simp 43793620Simp _LIBCPP_INLINE_VISIBILITY 43893620Simp __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {} 43993620Simp _LIBCPP_INLINE_VISIBILITY 44093620Simp __hash_map_const_iterator( 44165039Simp __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 442140957Simp : __i_(__i.__i_) {} 44365039Simp 444121586Simp _LIBCPP_INLINE_VISIBILITY 445121584Simp reference operator*() const {return *operator->();} 44665039Simp _LIBCPP_INLINE_VISIBILITY 447104854Simp pointer operator->() const {return (pointer)__i_.operator->();} 448147956Simp 449147956Simp _LIBCPP_INLINE_VISIBILITY 450147956Simp __hash_map_const_iterator& operator++() {++__i_; return *this;} 451147872Simp _LIBCPP_INLINE_VISIBILITY 452147872Simp __hash_map_const_iterator operator++(int) 453104854Simp { 45458545Simp __hash_map_const_iterator __t(*this); 45558545Simp ++(*this); 45665039Simp return __t; 457107359Snon } 458148141Simp 459141223Simp friend _LIBCPP_INLINE_VISIBILITY 46086269Simp bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 461124789Sume {return __x.__i_ == __y.__i_;} 46258545Simp friend _LIBCPP_INLINE_VISIBILITY 463104831Simp bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 464141122Simp {return __x.__i_ != __y.__i_;} 465104831Simp 466147872Simp template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS hash_map; 467147872Simp template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS hash_multimap; 468147872Simp template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator; 46986455Simp template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator; 470120275Simp}; 47186455Simp 47286455Simptemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 47393622Simp class _Alloc = allocator<pair<const _Key, _Tp> > > 47486455Simpclass _LIBCPP_TYPE_VIS hash_map 47584514Simp{ 47684514Simppublic: 477147872Simp // types 478147872Simp typedef _Key key_type; 479147872Simp typedef _Tp mapped_type; 48084514Simp typedef _Tp data_type; 481107359Snon typedef _Hash hasher; 482107359Snon typedef _Pred key_equal; 483107359Snon typedef _Alloc allocator_type; 48486455Simp typedef pair<const key_type, mapped_type> value_type; 485120330Simp typedef value_type& reference; 48686455Simp typedef const value_type& const_reference; 487147872Simp 488147872Simpprivate: 489147872Simp typedef pair<key_type, mapped_type> __value_type; 490147872Simp typedef __hash_map_hasher<__value_type, hasher> __hasher; 491147872Simp typedef __hash_map_equal<__value_type, key_equal> __key_equal; 49286455Simp typedef typename allocator_traits<allocator_type>::template 49386269Simp#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 494109103Sshiba rebind_alloc<__value_type> 495147988Stakawata#else 49652506Simp rebind_alloc<__value_type>::other 497140837Simp#endif 498147872Simp __allocator_type; 499140837Simp 500142260Simp typedef __hash_table<__value_type, __hasher, 501147872Simp __key_equal, __allocator_type> __table; 502140837Simp 503145247Sdamien __table __table_; 504145247Sdamien 505145247Sdamien typedef typename __table::__node_pointer __node_pointer; 50686269Simp typedef typename __table::__node_const_pointer __node_const_pointer; 50786269Simp typedef typename __table::__node_traits __node_traits; 50886269Simp typedef typename __table::__node_allocator __node_allocator; 509147872Simp typedef typename __table::__node __node; 510147872Simp typedef __hash_map_node_destructor<__node_allocator> _Dp; 511147872Simp typedef unique_ptr<__node, _Dp> __node_holder; 51286269Simp typedef allocator_traits<allocator_type> __alloc_traits; 51386269Simppublic: 51486269Simp typedef typename __alloc_traits::pointer pointer; 51586269Simp typedef typename __alloc_traits::const_pointer const_pointer; 51686269Simp typedef typename __alloc_traits::size_type size_type; 51786269Simp typedef typename __alloc_traits::difference_type difference_type; 51852506Simp 51952506Simp typedef __hash_map_iterator<typename __table::iterator> iterator; 52052506Simp typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 521118063Simp 522118063Simp _LIBCPP_INLINE_VISIBILITY hash_map() {__table_.rehash(193);} 523118063Simp explicit hash_map(size_type __n, const hasher& __hf = hasher(), 524117602Simp const key_equal& __eql = key_equal()); 525117602Simp hash_map(size_type __n, const hasher& __hf, 526117602Simp const key_equal& __eql, 52752506Simp const allocator_type& __a); 52852506Simp template <class _InputIterator> 52953813Simp hash_map(_InputIterator __first, _InputIterator __last); 53053813Simp template <class _InputIterator> 53152506Simp hash_map(_InputIterator __first, _InputIterator __last, 53286269Simp size_type __n, const hasher& __hf = hasher(), 533147796Simp const key_equal& __eql = key_equal()); 53486269Simp template <class _InputIterator> 53586269Simp hash_map(_InputIterator __first, _InputIterator __last, 53686269Simp size_type __n, const hasher& __hf, 53752506Simp const key_equal& __eql, 53879270Simp const allocator_type& __a); 53989103Simp hash_map(const hash_map& __u); 54052506Simp 54152506Simp _LIBCPP_INLINE_VISIBILITY 542147872Simp allocator_type get_allocator() const 54386269Simp {return allocator_type(__table_.__node_alloc());} 544147872Simp 54571279Simp _LIBCPP_INLINE_VISIBILITY 546118063Simp bool empty() const {return __table_.size() == 0;} 54752506Simp _LIBCPP_INLINE_VISIBILITY 54886269Simp size_type size() const {return __table_.size();} 54986269Simp _LIBCPP_INLINE_VISIBILITY 55086269Simp size_type max_size() const {return __table_.max_size();} 55152506Simp 55286269Simp _LIBCPP_INLINE_VISIBILITY 55352506Simp iterator begin() {return __table_.begin();} 55486269Simp _LIBCPP_INLINE_VISIBILITY 55552506Simp iterator end() {return __table_.end();} 556104854Simp _LIBCPP_INLINE_VISIBILITY 557148141Simp const_iterator begin() const {return __table_.begin();} 558124015Skato _LIBCPP_INLINE_VISIBILITY 559147872Simp const_iterator end() const {return __table_.end();} 56052506Simp 56186269Simp _LIBCPP_INLINE_VISIBILITY 562147872Simp pair<iterator, bool> insert(const value_type& __x) 56386269Simp {return __table_.__insert_unique(__x);} 56486269Simp _LIBCPP_INLINE_VISIBILITY 56586269Simp iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} 56686269Simp template <class _InputIterator> 56786269Simp void insert(_InputIterator __first, _InputIterator __last); 568107359Snon 569107359Snon _LIBCPP_INLINE_VISIBILITY 570107359Snon void erase(const_iterator __p) {__table_.erase(__p.__i_);} 57165039Simp _LIBCPP_INLINE_VISIBILITY 572120898Simp size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 57365039Simp _LIBCPP_INLINE_VISIBILITY 574128064Srsm void erase(const_iterator __first, const_iterator __last) 575128064Srsm {__table_.erase(__first.__i_, __last.__i_);} 576128064Srsm _LIBCPP_INLINE_VISIBILITY 57786571Simp void clear() {__table_.clear();} 57886269Simp 57986269Simp _LIBCPP_INLINE_VISIBILITY 58079270Simp void swap(hash_map& __u) {__table_.swap(__u.__table_);} 58165039Simp 582128064Srsm _LIBCPP_INLINE_VISIBILITY 583128064Srsm hasher hash_funct() const 584128064Srsm {return __table_.hash_function().hash_function();} 58586269Simp _LIBCPP_INLINE_VISIBILITY 586128064Srsm key_equal key_eq() const 587128064Srsm {return __table_.key_eq().key_eq();} 588128064Srsm 589128064Srsm _LIBCPP_INLINE_VISIBILITY 590128064Srsm iterator find(const key_type& __k) {return __table_.find(__k);} 59152506Simp _LIBCPP_INLINE_VISIBILITY 59284514Simp const_iterator find(const key_type& __k) const {return __table_.find(__k);} 59384514Simp _LIBCPP_INLINE_VISIBILITY 59484514Simp size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 59586269Simp _LIBCPP_INLINE_VISIBILITY 59686269Simp pair<iterator, iterator> equal_range(const key_type& __k) 59786269Simp {return __table_.__equal_range_unique(__k);} 59886269Simp _LIBCPP_INLINE_VISIBILITY 59952506Simp pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 60093622Simp {return __table_.__equal_range_unique(__k);} 601103169Simp 60286269Simp mapped_type& operator[](const key_type& __k); 60386269Simp 60486269Simp _LIBCPP_INLINE_VISIBILITY 605113667Ssanpei size_type bucket_count() const {return __table_.bucket_count();} 60686269Simp _LIBCPP_INLINE_VISIBILITY 607104854Simp size_type max_bucket_count() const {return __table_.max_bucket_count();} 60886269Simp 60958545Simp _LIBCPP_INLINE_VISIBILITY 61058545Simp size_type elems_in_bucket(size_type __n) const 611120330Simp {return __table_.bucket_size(__n);} 612107359Snon 613116481Simp _LIBCPP_INLINE_VISIBILITY 61486281Simp void resize(size_type __n) {__table_.rehash(__n);} 61558545Simp 616119215Simpprivate: 617107359Snon __node_holder __construct_node(const key_type& __k); 61893620Simp}; 619118634Simp 62086392Simptemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 621107359Snonhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 622114089Simp size_type __n, const hasher& __hf, const key_equal& __eql) 62386269Simp : __table_(__hf, __eql) 62486269Simp{ 62586269Simp __table_.rehash(__n); 62686269Simp} 627141930Simp 62886269Simptemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 629113318Simphash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 630107359Snon size_type __n, const hasher& __hf, const key_equal& __eql, 63186269Simp const allocator_type& __a) 632110935Sshiba : __table_(__hf, __eql, __a) 63386580Simp{ 63452506Simp __table_.rehash(__n); 63552506Simp} 636104854Simp 63793622Simptemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 638110175Sshibatemplate <class _InputIterator> 63986269Simphash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 640104854Simp _InputIterator __first, _InputIterator __last) 641103169Simp{ 642113318Simp __table_.rehash(193); 64386269Simp insert(__first, __last); 644113322Simp} 64558545Simp 64686269Simptemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 64758545Simptemplate <class _InputIterator> 648104854Simphash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 64958545Simp _InputIterator __first, _InputIterator __last, size_type __n, 65079270Simp const hasher& __hf, const key_equal& __eql) 65179270Simp : __table_(__hf, __eql) 65265039Simp{ 65379270Simp __table_.rehash(__n); 65486269Simp insert(__first, __last); 655113318Simp} 65686269Simp 65786269Simptemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 65886269Simptemplate <class _InputIterator> 65986269Simphash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 660104854Simp _InputIterator __first, _InputIterator __last, size_type __n, 661112356Simp const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 662104854Simp : __table_(__hf, __eql, __a) 66358545Simp{ 66486269Simp __table_.rehash(__n); 66586269Simp insert(__first, __last); 66658545Simp} 66786269Simp 66858545Simptemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 669107359Snonhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 67058545Simp const hash_map& __u) 671120290Simp : __table_(__u.__table_) 672116481Simp{ 673120330Simp __table_.rehash(__u.bucket_count()); 674120330Simp insert(__u.begin(), __u.end()); 675120330Simp} 676120330Simp 677107359Snontemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 67886269Simptypename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 679107359Snonhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) 68058545Simp{ 681119215Simp __node_allocator& __na = __table_.__node_alloc(); 682140837Simp __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 683107359Snon __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); 684140837Simp __h.get_deleter().__first_constructed = true; 68593620Simp __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 68686269Simp __h.get_deleter().__second_constructed = true; 687107359Snon return _VSTD::move(__h); 68886269Simp} 689118634Simp 69071283Simptemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 69186269Simptemplate <class _InputIterator> 69279270Simpinline _LIBCPP_INLINE_VISIBILITY 693107359Snonvoid 694107359Snonhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 69579270Simp _InputIterator __last) 696114089Simp{ 697115754Simp for (; __first != __last; ++__first) 698141930Simp __table_.__insert_unique(*__first); 69986269Simp} 70086269Simp 70186269Simptemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 70286269Simp_Tp& 703109103Sshibahash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 704107359Snon{ 705107359Snon iterator __i = find(__k); 706107359Snon if (__i != end()) 707107359Snon return __i->second; 708109103Sshiba __node_holder __h = __construct_node(__k); 709147988Stakawata pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 71089103Simp __h.release(); 71186269Simp return __r.first->second; 712147872Simp} 713147872Simp 714147872Simptemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 71586269Simpinline _LIBCPP_INLINE_VISIBILITY 71686269Simpvoid 717141930Simpswap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 71886269Simp hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 719113318Simp{ 720107359Snon __x.swap(__y); 72186269Simp} 72286269Simp 723110935Sshibatemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 72474634Simpbool 725operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 726 const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 727{ 728 if (__x.size() != __y.size()) 729 return false; 730 typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 731 const_iterator; 732 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 733 __i != __ex; ++__i) 734 { 735 const_iterator __j = __y.find(__i->first); 736 if (__j == __ey || !(*__i == *__j)) 737 return false; 738 } 739 return true; 740} 741 742template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 743inline _LIBCPP_INLINE_VISIBILITY 744bool 745operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 746 const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 747{ 748 return !(__x == __y); 749} 750 751template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 752 class _Alloc = allocator<pair<const _Key, _Tp> > > 753class _LIBCPP_TYPE_VIS hash_multimap 754{ 755public: 756 // types 757 typedef _Key key_type; 758 typedef _Tp mapped_type; 759 typedef _Tp data_type; 760 typedef _Hash hasher; 761 typedef _Pred key_equal; 762 typedef _Alloc allocator_type; 763 typedef pair<const key_type, mapped_type> value_type; 764 typedef value_type& reference; 765 typedef const value_type& const_reference; 766 767private: 768 typedef pair<key_type, mapped_type> __value_type; 769 typedef __hash_map_hasher<__value_type, hasher> __hasher; 770 typedef __hash_map_equal<__value_type, key_equal> __key_equal; 771 typedef typename allocator_traits<allocator_type>::template 772#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 773 rebind_alloc<__value_type> 774#else 775 rebind_alloc<__value_type>::other 776#endif 777 __allocator_type; 778 779 typedef __hash_table<__value_type, __hasher, 780 __key_equal, __allocator_type> __table; 781 782 __table __table_; 783 784 typedef typename __table::__node_traits __node_traits; 785 typedef typename __table::__node_allocator __node_allocator; 786 typedef typename __table::__node __node; 787 typedef __hash_map_node_destructor<__node_allocator> _Dp; 788 typedef unique_ptr<__node, _Dp> __node_holder; 789 typedef allocator_traits<allocator_type> __alloc_traits; 790public: 791 typedef typename __alloc_traits::pointer pointer; 792 typedef typename __alloc_traits::const_pointer const_pointer; 793 typedef typename __alloc_traits::size_type size_type; 794 typedef typename __alloc_traits::difference_type difference_type; 795 796 typedef __hash_map_iterator<typename __table::iterator> iterator; 797 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 798 799 _LIBCPP_INLINE_VISIBILITY 800 hash_multimap() {__table_.rehash(193);} 801 explicit hash_multimap(size_type __n, const hasher& __hf = hasher(), 802 const key_equal& __eql = key_equal()); 803 hash_multimap(size_type __n, const hasher& __hf, 804 const key_equal& __eql, 805 const allocator_type& __a); 806 template <class _InputIterator> 807 hash_multimap(_InputIterator __first, _InputIterator __last); 808 template <class _InputIterator> 809 hash_multimap(_InputIterator __first, _InputIterator __last, 810 size_type __n, const hasher& __hf = hasher(), 811 const key_equal& __eql = key_equal()); 812 template <class _InputIterator> 813 hash_multimap(_InputIterator __first, _InputIterator __last, 814 size_type __n, const hasher& __hf, 815 const key_equal& __eql, 816 const allocator_type& __a); 817 hash_multimap(const hash_multimap& __u); 818 819 _LIBCPP_INLINE_VISIBILITY 820 allocator_type get_allocator() const 821 {return allocator_type(__table_.__node_alloc());} 822 823 _LIBCPP_INLINE_VISIBILITY 824 bool empty() const {return __table_.size() == 0;} 825 _LIBCPP_INLINE_VISIBILITY 826 size_type size() const {return __table_.size();} 827 _LIBCPP_INLINE_VISIBILITY 828 size_type max_size() const {return __table_.max_size();} 829 830 _LIBCPP_INLINE_VISIBILITY 831 iterator begin() {return __table_.begin();} 832 _LIBCPP_INLINE_VISIBILITY 833 iterator end() {return __table_.end();} 834 _LIBCPP_INLINE_VISIBILITY 835 const_iterator begin() const {return __table_.begin();} 836 _LIBCPP_INLINE_VISIBILITY 837 const_iterator end() const {return __table_.end();} 838 839 _LIBCPP_INLINE_VISIBILITY 840 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 841 _LIBCPP_INLINE_VISIBILITY 842 iterator insert(const_iterator, const value_type& __x) {return insert(__x);} 843 template <class _InputIterator> 844 void insert(_InputIterator __first, _InputIterator __last); 845 846 _LIBCPP_INLINE_VISIBILITY 847 void erase(const_iterator __p) {__table_.erase(__p.__i_);} 848 _LIBCPP_INLINE_VISIBILITY 849 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 850 _LIBCPP_INLINE_VISIBILITY 851 void erase(const_iterator __first, const_iterator __last) 852 {__table_.erase(__first.__i_, __last.__i_);} 853 _LIBCPP_INLINE_VISIBILITY 854 void clear() {__table_.clear();} 855 856 _LIBCPP_INLINE_VISIBILITY 857 void swap(hash_multimap& __u) {__table_.swap(__u.__table_);} 858 859 _LIBCPP_INLINE_VISIBILITY 860 hasher hash_funct() const 861 {return __table_.hash_function().hash_function();} 862 _LIBCPP_INLINE_VISIBILITY 863 key_equal key_eq() const 864 {return __table_.key_eq().key_eq();} 865 866 _LIBCPP_INLINE_VISIBILITY 867 iterator find(const key_type& __k) {return __table_.find(__k);} 868 _LIBCPP_INLINE_VISIBILITY 869 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 870 _LIBCPP_INLINE_VISIBILITY 871 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 872 _LIBCPP_INLINE_VISIBILITY 873 pair<iterator, iterator> equal_range(const key_type& __k) 874 {return __table_.__equal_range_multi(__k);} 875 _LIBCPP_INLINE_VISIBILITY 876 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 877 {return __table_.__equal_range_multi(__k);} 878 879 _LIBCPP_INLINE_VISIBILITY 880 size_type bucket_count() const {return __table_.bucket_count();} 881 _LIBCPP_INLINE_VISIBILITY 882 size_type max_bucket_count() const {return __table_.max_bucket_count();} 883 884 _LIBCPP_INLINE_VISIBILITY 885 size_type elems_in_bucket(size_type __n) const 886 {return __table_.bucket_size(__n);} 887 888 _LIBCPP_INLINE_VISIBILITY 889 void resize(size_type __n) {__table_.rehash(__n);} 890}; 891 892template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 893hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 894 size_type __n, const hasher& __hf, const key_equal& __eql) 895 : __table_(__hf, __eql) 896{ 897 __table_.rehash(__n); 898} 899 900template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 901hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 902 size_type __n, const hasher& __hf, const key_equal& __eql, 903 const allocator_type& __a) 904 : __table_(__hf, __eql, __a) 905{ 906 __table_.rehash(__n); 907} 908 909template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 910template <class _InputIterator> 911hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 912 _InputIterator __first, _InputIterator __last) 913{ 914 __table_.rehash(193); 915 insert(__first, __last); 916} 917 918template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 919template <class _InputIterator> 920hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 921 _InputIterator __first, _InputIterator __last, size_type __n, 922 const hasher& __hf, const key_equal& __eql) 923 : __table_(__hf, __eql) 924{ 925 __table_.rehash(__n); 926 insert(__first, __last); 927} 928 929template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 930template <class _InputIterator> 931hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 932 _InputIterator __first, _InputIterator __last, size_type __n, 933 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 934 : __table_(__hf, __eql, __a) 935{ 936 __table_.rehash(__n); 937 insert(__first, __last); 938} 939 940template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 941hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 942 const hash_multimap& __u) 943 : __table_(__u.__table_) 944{ 945 __table_.rehash(__u.bucket_count()); 946 insert(__u.begin(), __u.end()); 947} 948 949template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 950template <class _InputIterator> 951inline _LIBCPP_INLINE_VISIBILITY 952void 953hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 954 _InputIterator __last) 955{ 956 for (; __first != __last; ++__first) 957 __table_.__insert_multi(*__first); 958} 959 960template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 961inline _LIBCPP_INLINE_VISIBILITY 962void 963swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 964 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 965{ 966 __x.swap(__y); 967} 968 969template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 970bool 971operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 972 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 973{ 974 if (__x.size() != __y.size()) 975 return false; 976 typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 977 const_iterator; 978 typedef pair<const_iterator, const_iterator> _EqRng; 979 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 980 { 981 _EqRng __xeq = __x.equal_range(__i->first); 982 _EqRng __yeq = __y.equal_range(__i->first); 983 if (_VSTD::distance(__xeq.first, __xeq.second) != 984 _VSTD::distance(__yeq.first, __yeq.second) || 985 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 986 return false; 987 __i = __xeq.second; 988 } 989 return true; 990} 991 992template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 993inline _LIBCPP_INLINE_VISIBILITY 994bool 995operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 996 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 997{ 998 return !(__x == __y); 999} 1000 1001} // __gnu_cxx 1002 1003#endif // _LIBCPP_HASH_MAP 1004