1227825Stheraven// -*- C++ -*- 2227825Stheraven//===-------------------------- hash_map ----------------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP_HASH_MAP 12227825Stheraven#define _LIBCPP_HASH_MAP 13227825Stheraven 14227825Stheraven/* 15227825Stheraven 16227825Stheraven hash_map synopsis 17227825Stheraven 18227825Stheravennamespace __gnu_cxx 19227825Stheraven{ 20227825Stheraven 21227825Stheraventemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 22227825Stheraven class Alloc = allocator<pair<const Key, T>>> 23227825Stheravenclass hash_map 24227825Stheraven{ 25227825Stheravenpublic: 26227825Stheraven // types 27227825Stheraven typedef Key key_type; 28227825Stheraven typedef T mapped_type; 29227825Stheraven typedef Hash hasher; 30227825Stheraven typedef Pred key_equal; 31227825Stheraven typedef Alloc allocator_type; 32227825Stheraven typedef pair<const key_type, mapped_type> value_type; 33227825Stheraven typedef value_type& reference; 34227825Stheraven typedef const value_type& const_reference; 35227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 36227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 37227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 38227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 39227825Stheraven 40227825Stheraven typedef /unspecified/ iterator; 41227825Stheraven typedef /unspecified/ const_iterator; 42227825Stheraven 43227825Stheraven explicit hash_map(size_type n = 193, const hasher& hf = hasher(), 44227825Stheraven const key_equal& eql = key_equal(), 45227825Stheraven const allocator_type& a = allocator_type()); 46227825Stheraven template <class InputIterator> 47227825Stheraven hash_map(InputIterator f, InputIterator l, 48227825Stheraven size_type n = 193, const hasher& hf = hasher(), 49227825Stheraven const key_equal& eql = key_equal(), 50227825Stheraven const allocator_type& a = allocator_type()); 51227825Stheraven hash_map(const hash_map&); 52227825Stheraven ~hash_map(); 53227825Stheraven hash_map& operator=(const hash_map&); 54227825Stheraven 55227825Stheraven allocator_type get_allocator() const; 56227825Stheraven 57227825Stheraven bool empty() const; 58227825Stheraven size_type size() const; 59227825Stheraven size_type max_size() const; 60227825Stheraven 61227825Stheraven iterator begin(); 62227825Stheraven iterator end(); 63227825Stheraven const_iterator begin() const; 64227825Stheraven const_iterator end() const; 65227825Stheraven 66227825Stheraven pair<iterator, bool> insert(const value_type& obj); 67227825Stheraven template <class InputIterator> 68227825Stheraven void insert(InputIterator first, InputIterator last); 69227825Stheraven 70227825Stheraven void erase(const_iterator position); 71227825Stheraven size_type erase(const key_type& k); 72227825Stheraven void erase(const_iterator first, const_iterator last); 73227825Stheraven void clear(); 74227825Stheraven 75227825Stheraven void swap(hash_map&); 76227825Stheraven 77227825Stheraven hasher hash_funct() const; 78227825Stheraven key_equal key_eq() const; 79227825Stheraven 80227825Stheraven iterator find(const key_type& k); 81227825Stheraven const_iterator find(const key_type& k) const; 82227825Stheraven size_type count(const key_type& k) const; 83227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 84227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 85227825Stheraven 86227825Stheraven mapped_type& operator[](const key_type& k); 87227825Stheraven 88227825Stheraven size_type bucket_count() const; 89227825Stheraven size_type max_bucket_count() const; 90227825Stheraven 91227825Stheraven size_type elems_in_bucket(size_type n) const; 92227825Stheraven 93227825Stheraven void resize(size_type n); 94227825Stheraven}; 95227825Stheraven 96227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 97227825Stheraven void swap(hash_map<Key, T, Hash, Pred, Alloc>& x, 98227825Stheraven hash_map<Key, T, Hash, Pred, Alloc>& y); 99227825Stheraven 100227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 101227825Stheraven bool 102227825Stheraven operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x, 103227825Stheraven const hash_map<Key, T, Hash, Pred, Alloc>& y); 104227825Stheraven 105227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 106227825Stheraven bool 107227825Stheraven operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x, 108227825Stheraven const hash_map<Key, T, Hash, Pred, Alloc>& y); 109227825Stheraven 110227825Stheraventemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 111227825Stheraven class Alloc = allocator<pair<const Key, T>>> 112227825Stheravenclass hash_multimap 113227825Stheraven{ 114227825Stheravenpublic: 115227825Stheraven // types 116227825Stheraven typedef Key key_type; 117227825Stheraven typedef T mapped_type; 118227825Stheraven typedef Hash hasher; 119227825Stheraven typedef Pred key_equal; 120227825Stheraven typedef Alloc allocator_type; 121227825Stheraven typedef pair<const key_type, mapped_type> value_type; 122227825Stheraven typedef value_type& reference; 123227825Stheraven typedef const value_type& const_reference; 124227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 125227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 126227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 127227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 128227825Stheraven 129227825Stheraven typedef /unspecified/ iterator; 130227825Stheraven typedef /unspecified/ const_iterator; 131227825Stheraven 132227825Stheraven explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(), 133227825Stheraven const key_equal& eql = key_equal(), 134227825Stheraven const allocator_type& a = allocator_type()); 135227825Stheraven template <class InputIterator> 136227825Stheraven hash_multimap(InputIterator f, InputIterator l, 137227825Stheraven size_type n = 193, const hasher& hf = hasher(), 138227825Stheraven const key_equal& eql = key_equal(), 139227825Stheraven const allocator_type& a = allocator_type()); 140227825Stheraven explicit hash_multimap(const allocator_type&); 141227825Stheraven hash_multimap(const hash_multimap&); 142227825Stheraven ~hash_multimap(); 143227825Stheraven hash_multimap& operator=(const hash_multimap&); 144227825Stheraven 145227825Stheraven allocator_type get_allocator() const; 146227825Stheraven 147227825Stheraven bool empty() const; 148227825Stheraven size_type size() const; 149227825Stheraven size_type max_size() const; 150227825Stheraven 151227825Stheraven iterator begin(); 152227825Stheraven iterator end(); 153227825Stheraven const_iterator begin() const; 154227825Stheraven const_iterator end() const; 155227825Stheraven 156227825Stheraven iterator insert(const value_type& obj); 157227825Stheraven template <class InputIterator> 158227825Stheraven void insert(InputIterator first, InputIterator last); 159227825Stheraven 160227825Stheraven void erase(const_iterator position); 161227825Stheraven size_type erase(const key_type& k); 162227825Stheraven void erase(const_iterator first, const_iterator last); 163227825Stheraven void clear(); 164227825Stheraven 165227825Stheraven void swap(hash_multimap&); 166227825Stheraven 167227825Stheraven hasher hash_funct() const; 168227825Stheraven key_equal key_eq() const; 169227825Stheraven 170227825Stheraven iterator find(const key_type& k); 171227825Stheraven const_iterator find(const key_type& k) const; 172227825Stheraven size_type count(const key_type& k) const; 173227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 174227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 175227825Stheraven 176227825Stheraven size_type bucket_count() const; 177227825Stheraven size_type max_bucket_count() const; 178227825Stheraven 179227825Stheraven size_type elems_in_bucket(size_type n) const; 180227825Stheraven 181227825Stheraven void resize(size_type n); 182227825Stheraven}; 183227825Stheraven 184227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 185227825Stheraven void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x, 186227825Stheraven hash_multimap<Key, T, Hash, Pred, Alloc>& y); 187227825Stheraven 188227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 189227825Stheraven bool 190227825Stheraven operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x, 191227825Stheraven const hash_multimap<Key, T, Hash, Pred, Alloc>& y); 192227825Stheraven 193227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 194227825Stheraven bool 195227825Stheraven operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x, 196227825Stheraven const hash_multimap<Key, T, Hash, Pred, Alloc>& y); 197227825Stheraven 198227825Stheraven} // __gnu_cxx 199227825Stheraven 200227825Stheraven*/ 201227825Stheraven 202227825Stheraven#include <__config> 203227825Stheraven#include <__hash_table> 204227825Stheraven#include <functional> 205227825Stheraven#include <stdexcept> 206288943Sdim#include <type_traits> 207227825Stheraven#include <ext/__hash> 208227825Stheraven 209227825Stheraven#if __DEPRECATED 210261272Sdim#if defined(_MSC_VER) && ! defined(__clang__) 211261272Sdim _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>") 212261272Sdim#else 213261272Sdim# warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map> 214227825Stheraven#endif 215261272Sdim#endif 216227825Stheraven 217288943Sdim#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 218227825Stheraven#pragma GCC system_header 219288943Sdim#endif 220227825Stheraven 221227825Stheravennamespace __gnu_cxx { 222227825Stheraven 223227825Stheravenusing namespace std; 224227825Stheraven 225288943Sdimtemplate <class _Tp, class _Hash, 226288943Sdim bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value 227232924Stheraven > 228227825Stheravenclass __hash_map_hasher 229227825Stheraven : private _Hash 230227825Stheraven{ 231227825Stheravenpublic: 232227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : _Hash() {} 233227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : _Hash(__h) {} 234227825Stheraven _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return *this;} 235227825Stheraven _LIBCPP_INLINE_VISIBILITY 236227825Stheraven size_t operator()(const _Tp& __x) const 237227825Stheraven {return static_cast<const _Hash&>(*this)(__x.first);} 238227825Stheraven _LIBCPP_INLINE_VISIBILITY 239227825Stheraven size_t operator()(const typename _Tp::first_type& __x) const 240227825Stheraven {return static_cast<const _Hash&>(*this)(__x);} 241227825Stheraven}; 242227825Stheraven 243227825Stheraventemplate <class _Tp, class _Hash> 244227825Stheravenclass __hash_map_hasher<_Tp, _Hash, false> 245227825Stheraven{ 246227825Stheraven _Hash __hash_; 247227825Stheravenpublic: 248227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : __hash_() {} 249227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : __hash_(__h) {} 250227825Stheraven _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return __hash_;} 251227825Stheraven _LIBCPP_INLINE_VISIBILITY 252227825Stheraven size_t operator()(const _Tp& __x) const 253227825Stheraven {return __hash_(__x.first);} 254227825Stheraven _LIBCPP_INLINE_VISIBILITY 255227825Stheraven size_t operator()(const typename _Tp::first_type& __x) const 256227825Stheraven {return __hash_(__x);} 257227825Stheraven}; 258227825Stheraven 259288943Sdimtemplate <class _Tp, class _Pred, 260288943Sdim bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value 261232924Stheraven > 262227825Stheravenclass __hash_map_equal 263227825Stheraven : private _Pred 264227825Stheraven{ 265227825Stheravenpublic: 266227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : _Pred() {} 267227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : _Pred(__p) {} 268227825Stheraven _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return *this;} 269227825Stheraven _LIBCPP_INLINE_VISIBILITY 270227825Stheraven bool operator()(const _Tp& __x, const _Tp& __y) const 271227825Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 272227825Stheraven _LIBCPP_INLINE_VISIBILITY 273227825Stheraven bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 274227825Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.first);} 275227825Stheraven _LIBCPP_INLINE_VISIBILITY 276227825Stheraven bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 277227825Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y);} 278227825Stheraven _LIBCPP_INLINE_VISIBILITY 279227825Stheraven bool operator()(const typename _Tp::first_type& __x, 280227825Stheraven const typename _Tp::first_type& __y) const 281227825Stheraven {return static_cast<const _Pred&>(*this)(__x, __y);} 282227825Stheraven}; 283227825Stheraven 284227825Stheraventemplate <class _Tp, class _Pred> 285227825Stheravenclass __hash_map_equal<_Tp, _Pred, false> 286227825Stheraven{ 287227825Stheraven _Pred __pred_; 288227825Stheravenpublic: 289227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : __pred_() {} 290227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : __pred_(__p) {} 291227825Stheraven _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return __pred_;} 292227825Stheraven _LIBCPP_INLINE_VISIBILITY 293227825Stheraven bool operator()(const _Tp& __x, const _Tp& __y) const 294227825Stheraven {return __pred_(__x.first, __y.first);} 295227825Stheraven _LIBCPP_INLINE_VISIBILITY 296227825Stheraven bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 297227825Stheraven {return __pred_(__x, __y.first);} 298227825Stheraven _LIBCPP_INLINE_VISIBILITY 299227825Stheraven bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 300227825Stheraven {return __pred_(__x.first, __y);} 301227825Stheraven _LIBCPP_INLINE_VISIBILITY 302227825Stheraven bool operator()(const typename _Tp::first_type& __x, 303227825Stheraven const typename _Tp::first_type& __y) const 304227825Stheraven {return __pred_(__x, __y);} 305227825Stheraven}; 306227825Stheraven 307227825Stheraventemplate <class _Alloc> 308227825Stheravenclass __hash_map_node_destructor 309227825Stheraven{ 310227825Stheraven typedef _Alloc allocator_type; 311227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 312227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 313227825Stheravenpublic: 314227825Stheraven typedef typename __alloc_traits::pointer pointer; 315227825Stheravenprivate: 316227825Stheraven typedef typename value_type::first_type first_type; 317227825Stheraven typedef typename value_type::second_type second_type; 318227825Stheraven 319227825Stheraven allocator_type& __na_; 320227825Stheraven 321227825Stheraven __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 322227825Stheraven 323227825Stheravenpublic: 324227825Stheraven bool __first_constructed; 325227825Stheraven bool __second_constructed; 326227825Stheraven 327227825Stheraven _LIBCPP_INLINE_VISIBILITY 328227825Stheraven explicit __hash_map_node_destructor(allocator_type& __na) 329227825Stheraven : __na_(__na), 330227825Stheraven __first_constructed(false), 331227825Stheraven __second_constructed(false) 332227825Stheraven {} 333227825Stheraven 334227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 335227825Stheraven _LIBCPP_INLINE_VISIBILITY 336227825Stheraven __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 337227825Stheraven : __na_(__x.__na_), 338227825Stheraven __first_constructed(__x.__value_constructed), 339227825Stheraven __second_constructed(__x.__value_constructed) 340227825Stheraven { 341227825Stheraven __x.__value_constructed = false; 342227825Stheraven } 343227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 344227825Stheraven _LIBCPP_INLINE_VISIBILITY 345227825Stheraven __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 346227825Stheraven : __na_(__x.__na_), 347227825Stheraven __first_constructed(__x.__value_constructed), 348227825Stheraven __second_constructed(__x.__value_constructed) 349227825Stheraven { 350227825Stheraven const_cast<bool&>(__x.__value_constructed) = false; 351227825Stheraven } 352227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 353227825Stheraven 354227825Stheraven _LIBCPP_INLINE_VISIBILITY 355227825Stheraven void operator()(pointer __p) 356227825Stheraven { 357227825Stheraven if (__second_constructed) 358227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second)); 359227825Stheraven if (__first_constructed) 360227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); 361227825Stheraven if (__p) 362227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 363227825Stheraven } 364227825Stheraven}; 365227825Stheraven 366227825Stheraventemplate <class _HashIterator> 367261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator 368227825Stheraven{ 369227825Stheraven _HashIterator __i_; 370227825Stheraven 371227825Stheraven typedef const typename _HashIterator::value_type::first_type key_type; 372227825Stheraven typedef typename _HashIterator::value_type::second_type mapped_type; 373227825Stheravenpublic: 374227825Stheraven typedef forward_iterator_tag iterator_category; 375227825Stheraven typedef pair<key_type, mapped_type> value_type; 376227825Stheraven typedef typename _HashIterator::difference_type difference_type; 377227825Stheraven typedef value_type& reference; 378300770Sdim typedef typename __rebind_pointer<typename _HashIterator::pointer, value_type>::type 379300770Sdim pointer; 380227825Stheraven 381227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {} 382227825Stheraven 383227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {} 384227825Stheraven 385227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();} 386227825Stheraven _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();} 387227825Stheraven 388227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;} 389227825Stheraven _LIBCPP_INLINE_VISIBILITY 390227825Stheraven __hash_map_iterator operator++(int) 391227825Stheraven { 392227825Stheraven __hash_map_iterator __t(*this); 393227825Stheraven ++(*this); 394227825Stheraven return __t; 395227825Stheraven } 396227825Stheraven 397227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 398227825Stheraven bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 399227825Stheraven {return __x.__i_ == __y.__i_;} 400227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 401227825Stheraven bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 402227825Stheraven {return __x.__i_ != __y.__i_;} 403227825Stheraven 404261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_map; 405261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_multimap; 406261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 407261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 408261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 409227825Stheraven}; 410227825Stheraven 411227825Stheraventemplate <class _HashIterator> 412261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator 413227825Stheraven{ 414227825Stheraven _HashIterator __i_; 415227825Stheraven 416227825Stheraven typedef const typename _HashIterator::value_type::first_type key_type; 417227825Stheraven typedef typename _HashIterator::value_type::second_type mapped_type; 418227825Stheravenpublic: 419227825Stheraven typedef forward_iterator_tag iterator_category; 420227825Stheraven typedef pair<key_type, mapped_type> value_type; 421227825Stheraven typedef typename _HashIterator::difference_type difference_type; 422227825Stheraven typedef const value_type& reference; 423300770Sdim typedef typename __rebind_pointer<typename _HashIterator::pointer, const value_type>::type 424300770Sdim pointer; 425227825Stheraven 426227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {} 427227825Stheraven 428227825Stheraven _LIBCPP_INLINE_VISIBILITY 429227825Stheraven __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {} 430227825Stheraven _LIBCPP_INLINE_VISIBILITY 431227825Stheraven __hash_map_const_iterator( 432227825Stheraven __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 433227825Stheraven : __i_(__i.__i_) {} 434227825Stheraven 435227825Stheraven _LIBCPP_INLINE_VISIBILITY 436227825Stheraven reference operator*() const {return *operator->();} 437227825Stheraven _LIBCPP_INLINE_VISIBILITY 438227825Stheraven pointer operator->() const {return (pointer)__i_.operator->();} 439227825Stheraven 440227825Stheraven _LIBCPP_INLINE_VISIBILITY 441227825Stheraven __hash_map_const_iterator& operator++() {++__i_; return *this;} 442227825Stheraven _LIBCPP_INLINE_VISIBILITY 443227825Stheraven __hash_map_const_iterator operator++(int) 444227825Stheraven { 445227825Stheraven __hash_map_const_iterator __t(*this); 446227825Stheraven ++(*this); 447227825Stheraven return __t; 448227825Stheraven } 449227825Stheraven 450227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 451227825Stheraven bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 452227825Stheraven {return __x.__i_ == __y.__i_;} 453227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 454227825Stheraven bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 455227825Stheraven {return __x.__i_ != __y.__i_;} 456227825Stheraven 457261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_map; 458261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_multimap; 459261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 460261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 461227825Stheraven}; 462227825Stheraven 463227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 464227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 465261272Sdimclass _LIBCPP_TYPE_VIS_ONLY hash_map 466227825Stheraven{ 467227825Stheravenpublic: 468227825Stheraven // types 469227825Stheraven typedef _Key key_type; 470227825Stheraven typedef _Tp mapped_type; 471227825Stheraven typedef _Tp data_type; 472227825Stheraven typedef _Hash hasher; 473227825Stheraven typedef _Pred key_equal; 474227825Stheraven typedef _Alloc allocator_type; 475227825Stheraven typedef pair<const key_type, mapped_type> value_type; 476227825Stheraven typedef value_type& reference; 477227825Stheraven typedef const value_type& const_reference; 478227825Stheraven 479227825Stheravenprivate: 480227825Stheraven typedef pair<key_type, mapped_type> __value_type; 481227825Stheraven typedef __hash_map_hasher<__value_type, hasher> __hasher; 482227825Stheraven typedef __hash_map_equal<__value_type, key_equal> __key_equal; 483288943Sdim typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __value_type>::type __allocator_type; 484227825Stheraven 485227825Stheraven typedef __hash_table<__value_type, __hasher, 486227825Stheraven __key_equal, __allocator_type> __table; 487227825Stheraven 488227825Stheraven __table __table_; 489227825Stheraven 490227825Stheraven typedef typename __table::__node_pointer __node_pointer; 491227825Stheraven typedef typename __table::__node_const_pointer __node_const_pointer; 492227825Stheraven typedef typename __table::__node_traits __node_traits; 493227825Stheraven typedef typename __table::__node_allocator __node_allocator; 494227825Stheraven typedef typename __table::__node __node; 495232924Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 496232924Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 497227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 498227825Stheravenpublic: 499227825Stheraven typedef typename __alloc_traits::pointer pointer; 500227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 501227825Stheraven typedef typename __alloc_traits::size_type size_type; 502227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 503227825Stheraven 504227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 505227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 506227825Stheraven 507227825Stheraven _LIBCPP_INLINE_VISIBILITY hash_map() {__table_.rehash(193);} 508227825Stheraven explicit hash_map(size_type __n, const hasher& __hf = hasher(), 509227825Stheraven const key_equal& __eql = key_equal()); 510227825Stheraven hash_map(size_type __n, const hasher& __hf, 511227825Stheraven const key_equal& __eql, 512227825Stheraven const allocator_type& __a); 513227825Stheraven template <class _InputIterator> 514227825Stheraven hash_map(_InputIterator __first, _InputIterator __last); 515227825Stheraven template <class _InputIterator> 516227825Stheraven hash_map(_InputIterator __first, _InputIterator __last, 517227825Stheraven size_type __n, const hasher& __hf = hasher(), 518227825Stheraven const key_equal& __eql = key_equal()); 519227825Stheraven template <class _InputIterator> 520227825Stheraven hash_map(_InputIterator __first, _InputIterator __last, 521227825Stheraven size_type __n, const hasher& __hf, 522227825Stheraven const key_equal& __eql, 523227825Stheraven const allocator_type& __a); 524227825Stheraven hash_map(const hash_map& __u); 525227825Stheraven 526227825Stheraven _LIBCPP_INLINE_VISIBILITY 527227825Stheraven allocator_type get_allocator() const 528227825Stheraven {return allocator_type(__table_.__node_alloc());} 529227825Stheraven 530227825Stheraven _LIBCPP_INLINE_VISIBILITY 531227825Stheraven bool empty() const {return __table_.size() == 0;} 532227825Stheraven _LIBCPP_INLINE_VISIBILITY 533227825Stheraven size_type size() const {return __table_.size();} 534227825Stheraven _LIBCPP_INLINE_VISIBILITY 535227825Stheraven size_type max_size() const {return __table_.max_size();} 536227825Stheraven 537227825Stheraven _LIBCPP_INLINE_VISIBILITY 538227825Stheraven iterator begin() {return __table_.begin();} 539227825Stheraven _LIBCPP_INLINE_VISIBILITY 540227825Stheraven iterator end() {return __table_.end();} 541227825Stheraven _LIBCPP_INLINE_VISIBILITY 542227825Stheraven const_iterator begin() const {return __table_.begin();} 543227825Stheraven _LIBCPP_INLINE_VISIBILITY 544227825Stheraven const_iterator end() const {return __table_.end();} 545227825Stheraven 546227825Stheraven _LIBCPP_INLINE_VISIBILITY 547227825Stheraven pair<iterator, bool> insert(const value_type& __x) 548227825Stheraven {return __table_.__insert_unique(__x);} 549227825Stheraven _LIBCPP_INLINE_VISIBILITY 550227825Stheraven iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} 551227825Stheraven template <class _InputIterator> 552227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 553227825Stheraven 554227825Stheraven _LIBCPP_INLINE_VISIBILITY 555227825Stheraven void erase(const_iterator __p) {__table_.erase(__p.__i_);} 556227825Stheraven _LIBCPP_INLINE_VISIBILITY 557227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 558227825Stheraven _LIBCPP_INLINE_VISIBILITY 559227825Stheraven void erase(const_iterator __first, const_iterator __last) 560227825Stheraven {__table_.erase(__first.__i_, __last.__i_);} 561227825Stheraven _LIBCPP_INLINE_VISIBILITY 562227825Stheraven void clear() {__table_.clear();} 563227825Stheraven 564227825Stheraven _LIBCPP_INLINE_VISIBILITY 565227825Stheraven void swap(hash_map& __u) {__table_.swap(__u.__table_);} 566227825Stheraven 567227825Stheraven _LIBCPP_INLINE_VISIBILITY 568227825Stheraven hasher hash_funct() const 569227825Stheraven {return __table_.hash_function().hash_function();} 570227825Stheraven _LIBCPP_INLINE_VISIBILITY 571227825Stheraven key_equal key_eq() const 572227825Stheraven {return __table_.key_eq().key_eq();} 573227825Stheraven 574227825Stheraven _LIBCPP_INLINE_VISIBILITY 575227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 576227825Stheraven _LIBCPP_INLINE_VISIBILITY 577227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 578227825Stheraven _LIBCPP_INLINE_VISIBILITY 579227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 580227825Stheraven _LIBCPP_INLINE_VISIBILITY 581227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 582227825Stheraven {return __table_.__equal_range_unique(__k);} 583227825Stheraven _LIBCPP_INLINE_VISIBILITY 584227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 585227825Stheraven {return __table_.__equal_range_unique(__k);} 586227825Stheraven 587227825Stheraven mapped_type& operator[](const key_type& __k); 588227825Stheraven 589227825Stheraven _LIBCPP_INLINE_VISIBILITY 590227825Stheraven size_type bucket_count() const {return __table_.bucket_count();} 591227825Stheraven _LIBCPP_INLINE_VISIBILITY 592227825Stheraven size_type max_bucket_count() const {return __table_.max_bucket_count();} 593227825Stheraven 594227825Stheraven _LIBCPP_INLINE_VISIBILITY 595227825Stheraven size_type elems_in_bucket(size_type __n) const 596227825Stheraven {return __table_.bucket_size(__n);} 597227825Stheraven 598227825Stheraven _LIBCPP_INLINE_VISIBILITY 599227825Stheraven void resize(size_type __n) {__table_.rehash(__n);} 600227825Stheraven 601227825Stheravenprivate: 602227825Stheraven __node_holder __construct_node(const key_type& __k); 603227825Stheraven}; 604227825Stheraven 605227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 606227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 607227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 608227825Stheraven : __table_(__hf, __eql) 609227825Stheraven{ 610227825Stheraven __table_.rehash(__n); 611227825Stheraven} 612227825Stheraven 613227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 614227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 615227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 616227825Stheraven const allocator_type& __a) 617227825Stheraven : __table_(__hf, __eql, __a) 618227825Stheraven{ 619227825Stheraven __table_.rehash(__n); 620227825Stheraven} 621227825Stheraven 622227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 623227825Stheraventemplate <class _InputIterator> 624227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 625227825Stheraven _InputIterator __first, _InputIterator __last) 626227825Stheraven{ 627227825Stheraven __table_.rehash(193); 628227825Stheraven insert(__first, __last); 629227825Stheraven} 630227825Stheraven 631227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 632227825Stheraventemplate <class _InputIterator> 633227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 634227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 635227825Stheraven const hasher& __hf, const key_equal& __eql) 636227825Stheraven : __table_(__hf, __eql) 637227825Stheraven{ 638227825Stheraven __table_.rehash(__n); 639227825Stheraven insert(__first, __last); 640227825Stheraven} 641227825Stheraven 642227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 643227825Stheraventemplate <class _InputIterator> 644227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 645227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 646227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 647227825Stheraven : __table_(__hf, __eql, __a) 648227825Stheraven{ 649227825Stheraven __table_.rehash(__n); 650227825Stheraven insert(__first, __last); 651227825Stheraven} 652227825Stheraven 653227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 654227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 655227825Stheraven const hash_map& __u) 656227825Stheraven : __table_(__u.__table_) 657227825Stheraven{ 658227825Stheraven __table_.rehash(__u.bucket_count()); 659227825Stheraven insert(__u.begin(), __u.end()); 660227825Stheraven} 661227825Stheraven 662227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 663227825Stheraventypename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 664227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) 665227825Stheraven{ 666227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 667232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 668227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); 669227825Stheraven __h.get_deleter().__first_constructed = true; 670227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 671227825Stheraven __h.get_deleter().__second_constructed = true; 672300770Sdim return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 673227825Stheraven} 674227825Stheraven 675227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 676227825Stheraventemplate <class _InputIterator> 677227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 678227825Stheravenvoid 679227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 680227825Stheraven _InputIterator __last) 681227825Stheraven{ 682227825Stheraven for (; __first != __last; ++__first) 683227825Stheraven __table_.__insert_unique(*__first); 684227825Stheraven} 685227825Stheraven 686227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 687227825Stheraven_Tp& 688227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 689227825Stheraven{ 690227825Stheraven iterator __i = find(__k); 691227825Stheraven if (__i != end()) 692227825Stheraven return __i->second; 693227825Stheraven __node_holder __h = __construct_node(__k); 694227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 695227825Stheraven __h.release(); 696227825Stheraven return __r.first->second; 697227825Stheraven} 698227825Stheraven 699227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 700227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 701227825Stheravenvoid 702227825Stheravenswap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 703227825Stheraven hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 704227825Stheraven{ 705227825Stheraven __x.swap(__y); 706227825Stheraven} 707227825Stheraven 708227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 709227825Stheravenbool 710227825Stheravenoperator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 711227825Stheraven const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 712227825Stheraven{ 713227825Stheraven if (__x.size() != __y.size()) 714227825Stheraven return false; 715227825Stheraven typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 716227825Stheraven const_iterator; 717227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 718227825Stheraven __i != __ex; ++__i) 719227825Stheraven { 720227825Stheraven const_iterator __j = __y.find(__i->first); 721227825Stheraven if (__j == __ey || !(*__i == *__j)) 722227825Stheraven return false; 723227825Stheraven } 724227825Stheraven return true; 725227825Stheraven} 726227825Stheraven 727227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 728227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 729227825Stheravenbool 730227825Stheravenoperator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 731227825Stheraven const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 732227825Stheraven{ 733227825Stheraven return !(__x == __y); 734227825Stheraven} 735227825Stheraven 736227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 737227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 738261272Sdimclass _LIBCPP_TYPE_VIS_ONLY hash_multimap 739227825Stheraven{ 740227825Stheravenpublic: 741227825Stheraven // types 742227825Stheraven typedef _Key key_type; 743227825Stheraven typedef _Tp mapped_type; 744227825Stheraven typedef _Tp data_type; 745227825Stheraven typedef _Hash hasher; 746227825Stheraven typedef _Pred key_equal; 747227825Stheraven typedef _Alloc allocator_type; 748227825Stheraven typedef pair<const key_type, mapped_type> value_type; 749227825Stheraven typedef value_type& reference; 750227825Stheraven typedef const value_type& const_reference; 751227825Stheraven 752227825Stheravenprivate: 753227825Stheraven typedef pair<key_type, mapped_type> __value_type; 754227825Stheraven typedef __hash_map_hasher<__value_type, hasher> __hasher; 755227825Stheraven typedef __hash_map_equal<__value_type, key_equal> __key_equal; 756288943Sdim typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __value_type>::type __allocator_type; 757227825Stheraven 758227825Stheraven typedef __hash_table<__value_type, __hasher, 759227825Stheraven __key_equal, __allocator_type> __table; 760227825Stheraven 761227825Stheraven __table __table_; 762227825Stheraven 763227825Stheraven typedef typename __table::__node_traits __node_traits; 764227825Stheraven typedef typename __table::__node_allocator __node_allocator; 765227825Stheraven typedef typename __table::__node __node; 766232924Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 767232924Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 768227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 769227825Stheravenpublic: 770227825Stheraven typedef typename __alloc_traits::pointer pointer; 771227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 772227825Stheraven typedef typename __alloc_traits::size_type size_type; 773227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 774227825Stheraven 775227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 776227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 777227825Stheraven 778227825Stheraven _LIBCPP_INLINE_VISIBILITY 779227825Stheraven hash_multimap() {__table_.rehash(193);} 780227825Stheraven explicit hash_multimap(size_type __n, const hasher& __hf = hasher(), 781227825Stheraven const key_equal& __eql = key_equal()); 782227825Stheraven hash_multimap(size_type __n, const hasher& __hf, 783227825Stheraven const key_equal& __eql, 784227825Stheraven const allocator_type& __a); 785227825Stheraven template <class _InputIterator> 786227825Stheraven hash_multimap(_InputIterator __first, _InputIterator __last); 787227825Stheraven template <class _InputIterator> 788227825Stheraven hash_multimap(_InputIterator __first, _InputIterator __last, 789227825Stheraven size_type __n, const hasher& __hf = hasher(), 790227825Stheraven const key_equal& __eql = key_equal()); 791227825Stheraven template <class _InputIterator> 792227825Stheraven hash_multimap(_InputIterator __first, _InputIterator __last, 793227825Stheraven size_type __n, const hasher& __hf, 794227825Stheraven const key_equal& __eql, 795227825Stheraven const allocator_type& __a); 796227825Stheraven hash_multimap(const hash_multimap& __u); 797227825Stheraven 798227825Stheraven _LIBCPP_INLINE_VISIBILITY 799227825Stheraven allocator_type get_allocator() const 800227825Stheraven {return allocator_type(__table_.__node_alloc());} 801227825Stheraven 802227825Stheraven _LIBCPP_INLINE_VISIBILITY 803227825Stheraven bool empty() const {return __table_.size() == 0;} 804227825Stheraven _LIBCPP_INLINE_VISIBILITY 805227825Stheraven size_type size() const {return __table_.size();} 806227825Stheraven _LIBCPP_INLINE_VISIBILITY 807227825Stheraven size_type max_size() const {return __table_.max_size();} 808227825Stheraven 809227825Stheraven _LIBCPP_INLINE_VISIBILITY 810227825Stheraven iterator begin() {return __table_.begin();} 811227825Stheraven _LIBCPP_INLINE_VISIBILITY 812227825Stheraven iterator end() {return __table_.end();} 813227825Stheraven _LIBCPP_INLINE_VISIBILITY 814227825Stheraven const_iterator begin() const {return __table_.begin();} 815227825Stheraven _LIBCPP_INLINE_VISIBILITY 816227825Stheraven const_iterator end() const {return __table_.end();} 817227825Stheraven 818227825Stheraven _LIBCPP_INLINE_VISIBILITY 819227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 820227825Stheraven _LIBCPP_INLINE_VISIBILITY 821227825Stheraven iterator insert(const_iterator, const value_type& __x) {return insert(__x);} 822227825Stheraven template <class _InputIterator> 823227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 824227825Stheraven 825227825Stheraven _LIBCPP_INLINE_VISIBILITY 826227825Stheraven void erase(const_iterator __p) {__table_.erase(__p.__i_);} 827227825Stheraven _LIBCPP_INLINE_VISIBILITY 828227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 829227825Stheraven _LIBCPP_INLINE_VISIBILITY 830227825Stheraven void erase(const_iterator __first, const_iterator __last) 831227825Stheraven {__table_.erase(__first.__i_, __last.__i_);} 832227825Stheraven _LIBCPP_INLINE_VISIBILITY 833227825Stheraven void clear() {__table_.clear();} 834227825Stheraven 835227825Stheraven _LIBCPP_INLINE_VISIBILITY 836227825Stheraven void swap(hash_multimap& __u) {__table_.swap(__u.__table_);} 837227825Stheraven 838227825Stheraven _LIBCPP_INLINE_VISIBILITY 839227825Stheraven hasher hash_funct() const 840227825Stheraven {return __table_.hash_function().hash_function();} 841227825Stheraven _LIBCPP_INLINE_VISIBILITY 842227825Stheraven key_equal key_eq() const 843227825Stheraven {return __table_.key_eq().key_eq();} 844227825Stheraven 845227825Stheraven _LIBCPP_INLINE_VISIBILITY 846227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 847227825Stheraven _LIBCPP_INLINE_VISIBILITY 848227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 849227825Stheraven _LIBCPP_INLINE_VISIBILITY 850227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 851227825Stheraven _LIBCPP_INLINE_VISIBILITY 852227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 853227825Stheraven {return __table_.__equal_range_multi(__k);} 854227825Stheraven _LIBCPP_INLINE_VISIBILITY 855227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 856227825Stheraven {return __table_.__equal_range_multi(__k);} 857227825Stheraven 858227825Stheraven _LIBCPP_INLINE_VISIBILITY 859227825Stheraven size_type bucket_count() const {return __table_.bucket_count();} 860227825Stheraven _LIBCPP_INLINE_VISIBILITY 861227825Stheraven size_type max_bucket_count() const {return __table_.max_bucket_count();} 862227825Stheraven 863227825Stheraven _LIBCPP_INLINE_VISIBILITY 864227825Stheraven size_type elems_in_bucket(size_type __n) const 865227825Stheraven {return __table_.bucket_size(__n);} 866227825Stheraven 867227825Stheraven _LIBCPP_INLINE_VISIBILITY 868227825Stheraven void resize(size_type __n) {__table_.rehash(__n);} 869227825Stheraven}; 870227825Stheraven 871227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 872227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 873227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 874227825Stheraven : __table_(__hf, __eql) 875227825Stheraven{ 876227825Stheraven __table_.rehash(__n); 877227825Stheraven} 878227825Stheraven 879227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 880227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 881227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 882227825Stheraven const allocator_type& __a) 883227825Stheraven : __table_(__hf, __eql, __a) 884227825Stheraven{ 885227825Stheraven __table_.rehash(__n); 886227825Stheraven} 887227825Stheraven 888227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 889227825Stheraventemplate <class _InputIterator> 890227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 891227825Stheraven _InputIterator __first, _InputIterator __last) 892227825Stheraven{ 893227825Stheraven __table_.rehash(193); 894227825Stheraven insert(__first, __last); 895227825Stheraven} 896227825Stheraven 897227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 898227825Stheraventemplate <class _InputIterator> 899227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 900227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 901227825Stheraven const hasher& __hf, const key_equal& __eql) 902227825Stheraven : __table_(__hf, __eql) 903227825Stheraven{ 904227825Stheraven __table_.rehash(__n); 905227825Stheraven insert(__first, __last); 906227825Stheraven} 907227825Stheraven 908227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 909227825Stheraventemplate <class _InputIterator> 910227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 911227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 912227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 913227825Stheraven : __table_(__hf, __eql, __a) 914227825Stheraven{ 915227825Stheraven __table_.rehash(__n); 916227825Stheraven insert(__first, __last); 917227825Stheraven} 918227825Stheraven 919227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 920227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 921227825Stheraven const hash_multimap& __u) 922227825Stheraven : __table_(__u.__table_) 923227825Stheraven{ 924227825Stheraven __table_.rehash(__u.bucket_count()); 925227825Stheraven insert(__u.begin(), __u.end()); 926227825Stheraven} 927227825Stheraven 928227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 929227825Stheraventemplate <class _InputIterator> 930227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 931227825Stheravenvoid 932227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 933227825Stheraven _InputIterator __last) 934227825Stheraven{ 935227825Stheraven for (; __first != __last; ++__first) 936227825Stheraven __table_.__insert_multi(*__first); 937227825Stheraven} 938227825Stheraven 939227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 940227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 941227825Stheravenvoid 942227825Stheravenswap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 943227825Stheraven hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 944227825Stheraven{ 945227825Stheraven __x.swap(__y); 946227825Stheraven} 947227825Stheraven 948227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 949227825Stheravenbool 950227825Stheravenoperator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 951227825Stheraven const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 952227825Stheraven{ 953227825Stheraven if (__x.size() != __y.size()) 954227825Stheraven return false; 955227825Stheraven typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 956227825Stheraven const_iterator; 957227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 958227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 959227825Stheraven { 960227825Stheraven _EqRng __xeq = __x.equal_range(__i->first); 961227825Stheraven _EqRng __yeq = __y.equal_range(__i->first); 962227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 963227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 964227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 965227825Stheraven return false; 966227825Stheraven __i = __xeq.second; 967227825Stheraven } 968227825Stheraven return true; 969227825Stheraven} 970227825Stheraven 971227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 972227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 973227825Stheravenbool 974227825Stheravenoperator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 975227825Stheraven const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 976227825Stheraven{ 977227825Stheraven return !(__x == __y); 978227825Stheraven} 979227825Stheraven 980227825Stheraven} // __gnu_cxx 981227825Stheraven 982227825Stheraven#endif // _LIBCPP_HASH_MAP 983