hash_map revision 278724
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> 206227825Stheraven#include <ext/__hash> 207227825Stheraven 208227825Stheraven#if __DEPRECATED 209262801Sdim#if defined(_MSC_VER) && ! defined(__clang__) 210262801Sdim _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>") 211262801Sdim#else 212262801Sdim# warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map> 213227825Stheraven#endif 214262801Sdim#endif 215227825Stheraven 216227825Stheraven#pragma GCC system_header 217227825Stheraven 218227825Stheravennamespace __gnu_cxx { 219227825Stheraven 220227825Stheravenusing namespace std; 221227825Stheraven 222232950Stheraventemplate <class _Tp, class _Hash, bool = is_empty<_Hash>::value 223232950Stheraven#if __has_feature(is_final) 224232950Stheraven && !__is_final(_Hash) 225232950Stheraven#endif 226232950Stheraven > 227227825Stheravenclass __hash_map_hasher 228227825Stheraven : private _Hash 229227825Stheraven{ 230227825Stheravenpublic: 231227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : _Hash() {} 232227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : _Hash(__h) {} 233227825Stheraven _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return *this;} 234227825Stheraven _LIBCPP_INLINE_VISIBILITY 235227825Stheraven size_t operator()(const _Tp& __x) const 236227825Stheraven {return static_cast<const _Hash&>(*this)(__x.first);} 237227825Stheraven _LIBCPP_INLINE_VISIBILITY 238227825Stheraven size_t operator()(const typename _Tp::first_type& __x) const 239227825Stheraven {return static_cast<const _Hash&>(*this)(__x);} 240227825Stheraven}; 241227825Stheraven 242227825Stheraventemplate <class _Tp, class _Hash> 243227825Stheravenclass __hash_map_hasher<_Tp, _Hash, false> 244227825Stheraven{ 245227825Stheraven _Hash __hash_; 246227825Stheravenpublic: 247227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : __hash_() {} 248227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : __hash_(__h) {} 249227825Stheraven _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return __hash_;} 250227825Stheraven _LIBCPP_INLINE_VISIBILITY 251227825Stheraven size_t operator()(const _Tp& __x) const 252227825Stheraven {return __hash_(__x.first);} 253227825Stheraven _LIBCPP_INLINE_VISIBILITY 254227825Stheraven size_t operator()(const typename _Tp::first_type& __x) const 255227825Stheraven {return __hash_(__x);} 256227825Stheraven}; 257227825Stheraven 258232950Stheraventemplate <class _Tp, class _Pred, bool = is_empty<_Pred>::value 259232950Stheraven#if __has_feature(is_final) 260232950Stheraven && !__is_final(_Pred) 261232950Stheraven#endif 262232950Stheraven > 263227825Stheravenclass __hash_map_equal 264227825Stheraven : private _Pred 265227825Stheraven{ 266227825Stheravenpublic: 267227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : _Pred() {} 268227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : _Pred(__p) {} 269227825Stheraven _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return *this;} 270227825Stheraven _LIBCPP_INLINE_VISIBILITY 271227825Stheraven bool operator()(const _Tp& __x, const _Tp& __y) const 272227825Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 273227825Stheraven _LIBCPP_INLINE_VISIBILITY 274227825Stheraven bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 275227825Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.first);} 276227825Stheraven _LIBCPP_INLINE_VISIBILITY 277227825Stheraven bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 278227825Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y);} 279227825Stheraven _LIBCPP_INLINE_VISIBILITY 280227825Stheraven bool operator()(const typename _Tp::first_type& __x, 281227825Stheraven const typename _Tp::first_type& __y) const 282227825Stheraven {return static_cast<const _Pred&>(*this)(__x, __y);} 283227825Stheraven}; 284227825Stheraven 285227825Stheraventemplate <class _Tp, class _Pred> 286227825Stheravenclass __hash_map_equal<_Tp, _Pred, false> 287227825Stheraven{ 288227825Stheraven _Pred __pred_; 289227825Stheravenpublic: 290227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : __pred_() {} 291227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : __pred_(__p) {} 292227825Stheraven _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return __pred_;} 293227825Stheraven _LIBCPP_INLINE_VISIBILITY 294227825Stheraven bool operator()(const _Tp& __x, const _Tp& __y) const 295227825Stheraven {return __pred_(__x.first, __y.first);} 296227825Stheraven _LIBCPP_INLINE_VISIBILITY 297227825Stheraven bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 298227825Stheraven {return __pred_(__x, __y.first);} 299227825Stheraven _LIBCPP_INLINE_VISIBILITY 300227825Stheraven bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 301227825Stheraven {return __pred_(__x.first, __y);} 302227825Stheraven _LIBCPP_INLINE_VISIBILITY 303227825Stheraven bool operator()(const typename _Tp::first_type& __x, 304227825Stheraven const typename _Tp::first_type& __y) const 305227825Stheraven {return __pred_(__x, __y);} 306227825Stheraven}; 307227825Stheraven 308227825Stheraventemplate <class _Alloc> 309227825Stheravenclass __hash_map_node_destructor 310227825Stheraven{ 311227825Stheraven typedef _Alloc allocator_type; 312227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 313227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 314227825Stheravenpublic: 315227825Stheraven typedef typename __alloc_traits::pointer pointer; 316227825Stheravenprivate: 317227825Stheraven typedef typename value_type::first_type first_type; 318227825Stheraven typedef typename value_type::second_type second_type; 319227825Stheraven 320227825Stheraven allocator_type& __na_; 321227825Stheraven 322227825Stheraven __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 323227825Stheraven 324227825Stheravenpublic: 325227825Stheraven bool __first_constructed; 326227825Stheraven bool __second_constructed; 327227825Stheraven 328227825Stheraven _LIBCPP_INLINE_VISIBILITY 329227825Stheraven explicit __hash_map_node_destructor(allocator_type& __na) 330227825Stheraven : __na_(__na), 331227825Stheraven __first_constructed(false), 332227825Stheraven __second_constructed(false) 333227825Stheraven {} 334227825Stheraven 335227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 336227825Stheraven _LIBCPP_INLINE_VISIBILITY 337227825Stheraven __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 338227825Stheraven : __na_(__x.__na_), 339227825Stheraven __first_constructed(__x.__value_constructed), 340227825Stheraven __second_constructed(__x.__value_constructed) 341227825Stheraven { 342227825Stheraven __x.__value_constructed = false; 343227825Stheraven } 344227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 345227825Stheraven _LIBCPP_INLINE_VISIBILITY 346227825Stheraven __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 347227825Stheraven : __na_(__x.__na_), 348227825Stheraven __first_constructed(__x.__value_constructed), 349227825Stheraven __second_constructed(__x.__value_constructed) 350227825Stheraven { 351227825Stheraven const_cast<bool&>(__x.__value_constructed) = false; 352227825Stheraven } 353227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 354227825Stheraven 355227825Stheraven _LIBCPP_INLINE_VISIBILITY 356227825Stheraven void operator()(pointer __p) 357227825Stheraven { 358227825Stheraven if (__second_constructed) 359227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second)); 360227825Stheraven if (__first_constructed) 361227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); 362227825Stheraven if (__p) 363227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 364227825Stheraven } 365227825Stheraven}; 366227825Stheraven 367227825Stheraventemplate <class _HashIterator> 368262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator 369227825Stheraven{ 370227825Stheraven _HashIterator __i_; 371227825Stheraven 372227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 373227825Stheraven typedef const typename _HashIterator::value_type::first_type key_type; 374227825Stheraven typedef typename _HashIterator::value_type::second_type mapped_type; 375227825Stheravenpublic: 376227825Stheraven typedef forward_iterator_tag iterator_category; 377227825Stheraven typedef pair<key_type, mapped_type> value_type; 378227825Stheraven typedef typename _HashIterator::difference_type difference_type; 379227825Stheraven typedef value_type& reference; 380227825Stheraven typedef typename __pointer_traits::template 381227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 382227825Stheraven rebind<value_type> 383227825Stheraven#else 384227825Stheraven rebind<value_type>::other 385227825Stheraven#endif 386227825Stheraven pointer; 387227825Stheraven 388227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {} 389227825Stheraven 390227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {} 391227825Stheraven 392227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();} 393227825Stheraven _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();} 394227825Stheraven 395227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;} 396227825Stheraven _LIBCPP_INLINE_VISIBILITY 397227825Stheraven __hash_map_iterator operator++(int) 398227825Stheraven { 399227825Stheraven __hash_map_iterator __t(*this); 400227825Stheraven ++(*this); 401227825Stheraven return __t; 402227825Stheraven } 403227825Stheraven 404227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 405227825Stheraven bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 406227825Stheraven {return __x.__i_ == __y.__i_;} 407227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 408227825Stheraven bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 409227825Stheraven {return __x.__i_ != __y.__i_;} 410227825Stheraven 411262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_map; 412262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_multimap; 413262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 414262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 415262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 416227825Stheraven}; 417227825Stheraven 418227825Stheraventemplate <class _HashIterator> 419262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator 420227825Stheraven{ 421227825Stheraven _HashIterator __i_; 422227825Stheraven 423227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 424227825Stheraven typedef const typename _HashIterator::value_type::first_type key_type; 425227825Stheraven typedef typename _HashIterator::value_type::second_type mapped_type; 426227825Stheravenpublic: 427227825Stheraven typedef forward_iterator_tag iterator_category; 428227825Stheraven typedef pair<key_type, mapped_type> value_type; 429227825Stheraven typedef typename _HashIterator::difference_type difference_type; 430227825Stheraven typedef const value_type& reference; 431227825Stheraven typedef typename __pointer_traits::template 432227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 433278724Sdim rebind<const value_type> 434227825Stheraven#else 435278724Sdim rebind<const value_type>::other 436227825Stheraven#endif 437227825Stheraven pointer; 438227825Stheraven 439227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {} 440227825Stheraven 441227825Stheraven _LIBCPP_INLINE_VISIBILITY 442227825Stheraven __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {} 443227825Stheraven _LIBCPP_INLINE_VISIBILITY 444227825Stheraven __hash_map_const_iterator( 445227825Stheraven __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 446227825Stheraven : __i_(__i.__i_) {} 447227825Stheraven 448227825Stheraven _LIBCPP_INLINE_VISIBILITY 449227825Stheraven reference operator*() const {return *operator->();} 450227825Stheraven _LIBCPP_INLINE_VISIBILITY 451227825Stheraven pointer operator->() const {return (pointer)__i_.operator->();} 452227825Stheraven 453227825Stheraven _LIBCPP_INLINE_VISIBILITY 454227825Stheraven __hash_map_const_iterator& operator++() {++__i_; return *this;} 455227825Stheraven _LIBCPP_INLINE_VISIBILITY 456227825Stheraven __hash_map_const_iterator operator++(int) 457227825Stheraven { 458227825Stheraven __hash_map_const_iterator __t(*this); 459227825Stheraven ++(*this); 460227825Stheraven return __t; 461227825Stheraven } 462227825Stheraven 463227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 464227825Stheraven bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 465227825Stheraven {return __x.__i_ == __y.__i_;} 466227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 467227825Stheraven bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 468227825Stheraven {return __x.__i_ != __y.__i_;} 469227825Stheraven 470262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_map; 471262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_multimap; 472262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 473262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 474227825Stheraven}; 475227825Stheraven 476227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 477227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 478262801Sdimclass _LIBCPP_TYPE_VIS_ONLY hash_map 479227825Stheraven{ 480227825Stheravenpublic: 481227825Stheraven // types 482227825Stheraven typedef _Key key_type; 483227825Stheraven typedef _Tp mapped_type; 484227825Stheraven typedef _Tp data_type; 485227825Stheraven typedef _Hash hasher; 486227825Stheraven typedef _Pred key_equal; 487227825Stheraven typedef _Alloc allocator_type; 488227825Stheraven typedef pair<const key_type, mapped_type> value_type; 489227825Stheraven typedef value_type& reference; 490227825Stheraven typedef const value_type& const_reference; 491227825Stheraven 492227825Stheravenprivate: 493227825Stheraven typedef pair<key_type, mapped_type> __value_type; 494227825Stheraven typedef __hash_map_hasher<__value_type, hasher> __hasher; 495227825Stheraven typedef __hash_map_equal<__value_type, key_equal> __key_equal; 496227825Stheraven typedef typename allocator_traits<allocator_type>::template 497227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 498227825Stheraven rebind_alloc<__value_type> 499227825Stheraven#else 500227825Stheraven rebind_alloc<__value_type>::other 501227825Stheraven#endif 502227825Stheraven __allocator_type; 503227825Stheraven 504227825Stheraven typedef __hash_table<__value_type, __hasher, 505227825Stheraven __key_equal, __allocator_type> __table; 506227825Stheraven 507227825Stheraven __table __table_; 508227825Stheraven 509227825Stheraven typedef typename __table::__node_pointer __node_pointer; 510227825Stheraven typedef typename __table::__node_const_pointer __node_const_pointer; 511227825Stheraven typedef typename __table::__node_traits __node_traits; 512227825Stheraven typedef typename __table::__node_allocator __node_allocator; 513227825Stheraven typedef typename __table::__node __node; 514232950Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 515232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 516227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 517227825Stheravenpublic: 518227825Stheraven typedef typename __alloc_traits::pointer pointer; 519227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 520227825Stheraven typedef typename __alloc_traits::size_type size_type; 521227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 522227825Stheraven 523227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 524227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 525227825Stheraven 526227825Stheraven _LIBCPP_INLINE_VISIBILITY hash_map() {__table_.rehash(193);} 527227825Stheraven explicit hash_map(size_type __n, const hasher& __hf = hasher(), 528227825Stheraven const key_equal& __eql = key_equal()); 529227825Stheraven hash_map(size_type __n, const hasher& __hf, 530227825Stheraven const key_equal& __eql, 531227825Stheraven const allocator_type& __a); 532227825Stheraven template <class _InputIterator> 533227825Stheraven hash_map(_InputIterator __first, _InputIterator __last); 534227825Stheraven template <class _InputIterator> 535227825Stheraven hash_map(_InputIterator __first, _InputIterator __last, 536227825Stheraven size_type __n, const hasher& __hf = hasher(), 537227825Stheraven const key_equal& __eql = key_equal()); 538227825Stheraven template <class _InputIterator> 539227825Stheraven hash_map(_InputIterator __first, _InputIterator __last, 540227825Stheraven size_type __n, const hasher& __hf, 541227825Stheraven const key_equal& __eql, 542227825Stheraven const allocator_type& __a); 543227825Stheraven hash_map(const hash_map& __u); 544227825Stheraven 545227825Stheraven _LIBCPP_INLINE_VISIBILITY 546227825Stheraven allocator_type get_allocator() const 547227825Stheraven {return allocator_type(__table_.__node_alloc());} 548227825Stheraven 549227825Stheraven _LIBCPP_INLINE_VISIBILITY 550227825Stheraven bool empty() const {return __table_.size() == 0;} 551227825Stheraven _LIBCPP_INLINE_VISIBILITY 552227825Stheraven size_type size() const {return __table_.size();} 553227825Stheraven _LIBCPP_INLINE_VISIBILITY 554227825Stheraven size_type max_size() const {return __table_.max_size();} 555227825Stheraven 556227825Stheraven _LIBCPP_INLINE_VISIBILITY 557227825Stheraven iterator begin() {return __table_.begin();} 558227825Stheraven _LIBCPP_INLINE_VISIBILITY 559227825Stheraven iterator end() {return __table_.end();} 560227825Stheraven _LIBCPP_INLINE_VISIBILITY 561227825Stheraven const_iterator begin() const {return __table_.begin();} 562227825Stheraven _LIBCPP_INLINE_VISIBILITY 563227825Stheraven const_iterator end() const {return __table_.end();} 564227825Stheraven 565227825Stheraven _LIBCPP_INLINE_VISIBILITY 566227825Stheraven pair<iterator, bool> insert(const value_type& __x) 567227825Stheraven {return __table_.__insert_unique(__x);} 568227825Stheraven _LIBCPP_INLINE_VISIBILITY 569227825Stheraven iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} 570227825Stheraven template <class _InputIterator> 571227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 572227825Stheraven 573227825Stheraven _LIBCPP_INLINE_VISIBILITY 574227825Stheraven void erase(const_iterator __p) {__table_.erase(__p.__i_);} 575227825Stheraven _LIBCPP_INLINE_VISIBILITY 576227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 577227825Stheraven _LIBCPP_INLINE_VISIBILITY 578227825Stheraven void erase(const_iterator __first, const_iterator __last) 579227825Stheraven {__table_.erase(__first.__i_, __last.__i_);} 580227825Stheraven _LIBCPP_INLINE_VISIBILITY 581227825Stheraven void clear() {__table_.clear();} 582227825Stheraven 583227825Stheraven _LIBCPP_INLINE_VISIBILITY 584227825Stheraven void swap(hash_map& __u) {__table_.swap(__u.__table_);} 585227825Stheraven 586227825Stheraven _LIBCPP_INLINE_VISIBILITY 587227825Stheraven hasher hash_funct() const 588227825Stheraven {return __table_.hash_function().hash_function();} 589227825Stheraven _LIBCPP_INLINE_VISIBILITY 590227825Stheraven key_equal key_eq() const 591227825Stheraven {return __table_.key_eq().key_eq();} 592227825Stheraven 593227825Stheraven _LIBCPP_INLINE_VISIBILITY 594227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 595227825Stheraven _LIBCPP_INLINE_VISIBILITY 596227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 597227825Stheraven _LIBCPP_INLINE_VISIBILITY 598227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 599227825Stheraven _LIBCPP_INLINE_VISIBILITY 600227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 601227825Stheraven {return __table_.__equal_range_unique(__k);} 602227825Stheraven _LIBCPP_INLINE_VISIBILITY 603227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 604227825Stheraven {return __table_.__equal_range_unique(__k);} 605227825Stheraven 606227825Stheraven mapped_type& operator[](const key_type& __k); 607227825Stheraven 608227825Stheraven _LIBCPP_INLINE_VISIBILITY 609227825Stheraven size_type bucket_count() const {return __table_.bucket_count();} 610227825Stheraven _LIBCPP_INLINE_VISIBILITY 611227825Stheraven size_type max_bucket_count() const {return __table_.max_bucket_count();} 612227825Stheraven 613227825Stheraven _LIBCPP_INLINE_VISIBILITY 614227825Stheraven size_type elems_in_bucket(size_type __n) const 615227825Stheraven {return __table_.bucket_size(__n);} 616227825Stheraven 617227825Stheraven _LIBCPP_INLINE_VISIBILITY 618227825Stheraven void resize(size_type __n) {__table_.rehash(__n);} 619227825Stheraven 620227825Stheravenprivate: 621227825Stheraven __node_holder __construct_node(const key_type& __k); 622227825Stheraven}; 623227825Stheraven 624227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 625227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 626227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 627227825Stheraven : __table_(__hf, __eql) 628227825Stheraven{ 629227825Stheraven __table_.rehash(__n); 630227825Stheraven} 631227825Stheraven 632227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 633227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 634227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 635227825Stheraven const allocator_type& __a) 636227825Stheraven : __table_(__hf, __eql, __a) 637227825Stheraven{ 638227825Stheraven __table_.rehash(__n); 639227825Stheraven} 640227825Stheraven 641227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 642227825Stheraventemplate <class _InputIterator> 643227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 644227825Stheraven _InputIterator __first, _InputIterator __last) 645227825Stheraven{ 646227825Stheraven __table_.rehash(193); 647227825Stheraven insert(__first, __last); 648227825Stheraven} 649227825Stheraven 650227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 651227825Stheraventemplate <class _InputIterator> 652227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 653227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 654227825Stheraven const hasher& __hf, const key_equal& __eql) 655227825Stheraven : __table_(__hf, __eql) 656227825Stheraven{ 657227825Stheraven __table_.rehash(__n); 658227825Stheraven insert(__first, __last); 659227825Stheraven} 660227825Stheraven 661227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 662227825Stheraventemplate <class _InputIterator> 663227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 664227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 665227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 666227825Stheraven : __table_(__hf, __eql, __a) 667227825Stheraven{ 668227825Stheraven __table_.rehash(__n); 669227825Stheraven insert(__first, __last); 670227825Stheraven} 671227825Stheraven 672227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 673227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 674227825Stheraven const hash_map& __u) 675227825Stheraven : __table_(__u.__table_) 676227825Stheraven{ 677227825Stheraven __table_.rehash(__u.bucket_count()); 678227825Stheraven insert(__u.begin(), __u.end()); 679227825Stheraven} 680227825Stheraven 681227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 682227825Stheraventypename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 683227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) 684227825Stheraven{ 685227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 686232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 687227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); 688227825Stheraven __h.get_deleter().__first_constructed = true; 689227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 690227825Stheraven __h.get_deleter().__second_constructed = true; 691262801Sdim return _VSTD::move(__h); // explicitly moved for C++03 692227825Stheraven} 693227825Stheraven 694227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 695227825Stheraventemplate <class _InputIterator> 696227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 697227825Stheravenvoid 698227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 699227825Stheraven _InputIterator __last) 700227825Stheraven{ 701227825Stheraven for (; __first != __last; ++__first) 702227825Stheraven __table_.__insert_unique(*__first); 703227825Stheraven} 704227825Stheraven 705227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 706227825Stheraven_Tp& 707227825Stheravenhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 708227825Stheraven{ 709227825Stheraven iterator __i = find(__k); 710227825Stheraven if (__i != end()) 711227825Stheraven return __i->second; 712227825Stheraven __node_holder __h = __construct_node(__k); 713227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 714227825Stheraven __h.release(); 715227825Stheraven return __r.first->second; 716227825Stheraven} 717227825Stheraven 718227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 719227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 720227825Stheravenvoid 721227825Stheravenswap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 722227825Stheraven hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 723227825Stheraven{ 724227825Stheraven __x.swap(__y); 725227825Stheraven} 726227825Stheraven 727227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 728227825Stheravenbool 729227825Stheravenoperator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 730227825Stheraven const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 731227825Stheraven{ 732227825Stheraven if (__x.size() != __y.size()) 733227825Stheraven return false; 734227825Stheraven typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 735227825Stheraven const_iterator; 736227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 737227825Stheraven __i != __ex; ++__i) 738227825Stheraven { 739227825Stheraven const_iterator __j = __y.find(__i->first); 740227825Stheraven if (__j == __ey || !(*__i == *__j)) 741227825Stheraven return false; 742227825Stheraven } 743227825Stheraven return true; 744227825Stheraven} 745227825Stheraven 746227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 747227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 748227825Stheravenbool 749227825Stheravenoperator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 750227825Stheraven const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 751227825Stheraven{ 752227825Stheraven return !(__x == __y); 753227825Stheraven} 754227825Stheraven 755227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 756227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 757262801Sdimclass _LIBCPP_TYPE_VIS_ONLY hash_multimap 758227825Stheraven{ 759227825Stheravenpublic: 760227825Stheraven // types 761227825Stheraven typedef _Key key_type; 762227825Stheraven typedef _Tp mapped_type; 763227825Stheraven typedef _Tp data_type; 764227825Stheraven typedef _Hash hasher; 765227825Stheraven typedef _Pred key_equal; 766227825Stheraven typedef _Alloc allocator_type; 767227825Stheraven typedef pair<const key_type, mapped_type> value_type; 768227825Stheraven typedef value_type& reference; 769227825Stheraven typedef const value_type& const_reference; 770227825Stheraven 771227825Stheravenprivate: 772227825Stheraven typedef pair<key_type, mapped_type> __value_type; 773227825Stheraven typedef __hash_map_hasher<__value_type, hasher> __hasher; 774227825Stheraven typedef __hash_map_equal<__value_type, key_equal> __key_equal; 775227825Stheraven typedef typename allocator_traits<allocator_type>::template 776227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 777227825Stheraven rebind_alloc<__value_type> 778227825Stheraven#else 779227825Stheraven rebind_alloc<__value_type>::other 780227825Stheraven#endif 781227825Stheraven __allocator_type; 782227825Stheraven 783227825Stheraven typedef __hash_table<__value_type, __hasher, 784227825Stheraven __key_equal, __allocator_type> __table; 785227825Stheraven 786227825Stheraven __table __table_; 787227825Stheraven 788227825Stheraven typedef typename __table::__node_traits __node_traits; 789227825Stheraven typedef typename __table::__node_allocator __node_allocator; 790227825Stheraven typedef typename __table::__node __node; 791232950Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 792232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 793227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 794227825Stheravenpublic: 795227825Stheraven typedef typename __alloc_traits::pointer pointer; 796227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 797227825Stheraven typedef typename __alloc_traits::size_type size_type; 798227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 799227825Stheraven 800227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 801227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 802227825Stheraven 803227825Stheraven _LIBCPP_INLINE_VISIBILITY 804227825Stheraven hash_multimap() {__table_.rehash(193);} 805227825Stheraven explicit hash_multimap(size_type __n, const hasher& __hf = hasher(), 806227825Stheraven const key_equal& __eql = key_equal()); 807227825Stheraven hash_multimap(size_type __n, const hasher& __hf, 808227825Stheraven const key_equal& __eql, 809227825Stheraven const allocator_type& __a); 810227825Stheraven template <class _InputIterator> 811227825Stheraven hash_multimap(_InputIterator __first, _InputIterator __last); 812227825Stheraven template <class _InputIterator> 813227825Stheraven hash_multimap(_InputIterator __first, _InputIterator __last, 814227825Stheraven size_type __n, const hasher& __hf = hasher(), 815227825Stheraven const key_equal& __eql = key_equal()); 816227825Stheraven template <class _InputIterator> 817227825Stheraven hash_multimap(_InputIterator __first, _InputIterator __last, 818227825Stheraven size_type __n, const hasher& __hf, 819227825Stheraven const key_equal& __eql, 820227825Stheraven const allocator_type& __a); 821227825Stheraven hash_multimap(const hash_multimap& __u); 822227825Stheraven 823227825Stheraven _LIBCPP_INLINE_VISIBILITY 824227825Stheraven allocator_type get_allocator() const 825227825Stheraven {return allocator_type(__table_.__node_alloc());} 826227825Stheraven 827227825Stheraven _LIBCPP_INLINE_VISIBILITY 828227825Stheraven bool empty() const {return __table_.size() == 0;} 829227825Stheraven _LIBCPP_INLINE_VISIBILITY 830227825Stheraven size_type size() const {return __table_.size();} 831227825Stheraven _LIBCPP_INLINE_VISIBILITY 832227825Stheraven size_type max_size() const {return __table_.max_size();} 833227825Stheraven 834227825Stheraven _LIBCPP_INLINE_VISIBILITY 835227825Stheraven iterator begin() {return __table_.begin();} 836227825Stheraven _LIBCPP_INLINE_VISIBILITY 837227825Stheraven iterator end() {return __table_.end();} 838227825Stheraven _LIBCPP_INLINE_VISIBILITY 839227825Stheraven const_iterator begin() const {return __table_.begin();} 840227825Stheraven _LIBCPP_INLINE_VISIBILITY 841227825Stheraven const_iterator end() const {return __table_.end();} 842227825Stheraven 843227825Stheraven _LIBCPP_INLINE_VISIBILITY 844227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 845227825Stheraven _LIBCPP_INLINE_VISIBILITY 846227825Stheraven iterator insert(const_iterator, const value_type& __x) {return insert(__x);} 847227825Stheraven template <class _InputIterator> 848227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 849227825Stheraven 850227825Stheraven _LIBCPP_INLINE_VISIBILITY 851227825Stheraven void erase(const_iterator __p) {__table_.erase(__p.__i_);} 852227825Stheraven _LIBCPP_INLINE_VISIBILITY 853227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 854227825Stheraven _LIBCPP_INLINE_VISIBILITY 855227825Stheraven void erase(const_iterator __first, const_iterator __last) 856227825Stheraven {__table_.erase(__first.__i_, __last.__i_);} 857227825Stheraven _LIBCPP_INLINE_VISIBILITY 858227825Stheraven void clear() {__table_.clear();} 859227825Stheraven 860227825Stheraven _LIBCPP_INLINE_VISIBILITY 861227825Stheraven void swap(hash_multimap& __u) {__table_.swap(__u.__table_);} 862227825Stheraven 863227825Stheraven _LIBCPP_INLINE_VISIBILITY 864227825Stheraven hasher hash_funct() const 865227825Stheraven {return __table_.hash_function().hash_function();} 866227825Stheraven _LIBCPP_INLINE_VISIBILITY 867227825Stheraven key_equal key_eq() const 868227825Stheraven {return __table_.key_eq().key_eq();} 869227825Stheraven 870227825Stheraven _LIBCPP_INLINE_VISIBILITY 871227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 872227825Stheraven _LIBCPP_INLINE_VISIBILITY 873227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 874227825Stheraven _LIBCPP_INLINE_VISIBILITY 875227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 876227825Stheraven _LIBCPP_INLINE_VISIBILITY 877227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 878227825Stheraven {return __table_.__equal_range_multi(__k);} 879227825Stheraven _LIBCPP_INLINE_VISIBILITY 880227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 881227825Stheraven {return __table_.__equal_range_multi(__k);} 882227825Stheraven 883227825Stheraven _LIBCPP_INLINE_VISIBILITY 884227825Stheraven size_type bucket_count() const {return __table_.bucket_count();} 885227825Stheraven _LIBCPP_INLINE_VISIBILITY 886227825Stheraven size_type max_bucket_count() const {return __table_.max_bucket_count();} 887227825Stheraven 888227825Stheraven _LIBCPP_INLINE_VISIBILITY 889227825Stheraven size_type elems_in_bucket(size_type __n) const 890227825Stheraven {return __table_.bucket_size(__n);} 891227825Stheraven 892227825Stheraven _LIBCPP_INLINE_VISIBILITY 893227825Stheraven void resize(size_type __n) {__table_.rehash(__n);} 894227825Stheraven}; 895227825Stheraven 896227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 897227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 898227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 899227825Stheraven : __table_(__hf, __eql) 900227825Stheraven{ 901227825Stheraven __table_.rehash(__n); 902227825Stheraven} 903227825Stheraven 904227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 905227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 906227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 907227825Stheraven const allocator_type& __a) 908227825Stheraven : __table_(__hf, __eql, __a) 909227825Stheraven{ 910227825Stheraven __table_.rehash(__n); 911227825Stheraven} 912227825Stheraven 913227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 914227825Stheraventemplate <class _InputIterator> 915227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 916227825Stheraven _InputIterator __first, _InputIterator __last) 917227825Stheraven{ 918227825Stheraven __table_.rehash(193); 919227825Stheraven insert(__first, __last); 920227825Stheraven} 921227825Stheraven 922227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 923227825Stheraventemplate <class _InputIterator> 924227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 925227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 926227825Stheraven const hasher& __hf, const key_equal& __eql) 927227825Stheraven : __table_(__hf, __eql) 928227825Stheraven{ 929227825Stheraven __table_.rehash(__n); 930227825Stheraven insert(__first, __last); 931227825Stheraven} 932227825Stheraven 933227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 934227825Stheraventemplate <class _InputIterator> 935227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 936227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 937227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 938227825Stheraven : __table_(__hf, __eql, __a) 939227825Stheraven{ 940227825Stheraven __table_.rehash(__n); 941227825Stheraven insert(__first, __last); 942227825Stheraven} 943227825Stheraven 944227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 945227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 946227825Stheraven const hash_multimap& __u) 947227825Stheraven : __table_(__u.__table_) 948227825Stheraven{ 949227825Stheraven __table_.rehash(__u.bucket_count()); 950227825Stheraven insert(__u.begin(), __u.end()); 951227825Stheraven} 952227825Stheraven 953227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 954227825Stheraventemplate <class _InputIterator> 955227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 956227825Stheravenvoid 957227825Stheravenhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 958227825Stheraven _InputIterator __last) 959227825Stheraven{ 960227825Stheraven for (; __first != __last; ++__first) 961227825Stheraven __table_.__insert_multi(*__first); 962227825Stheraven} 963227825Stheraven 964227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 965227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 966227825Stheravenvoid 967227825Stheravenswap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 968227825Stheraven hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 969227825Stheraven{ 970227825Stheraven __x.swap(__y); 971227825Stheraven} 972227825Stheraven 973227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 974227825Stheravenbool 975227825Stheravenoperator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 976227825Stheraven const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 977227825Stheraven{ 978227825Stheraven if (__x.size() != __y.size()) 979227825Stheraven return false; 980227825Stheraven typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 981227825Stheraven const_iterator; 982227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 983227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 984227825Stheraven { 985227825Stheraven _EqRng __xeq = __x.equal_range(__i->first); 986227825Stheraven _EqRng __yeq = __y.equal_range(__i->first); 987227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 988227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 989227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 990227825Stheraven return false; 991227825Stheraven __i = __xeq.second; 992227825Stheraven } 993227825Stheraven return true; 994227825Stheraven} 995227825Stheraven 996227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 997227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 998227825Stheravenbool 999227825Stheravenoperator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1000227825Stheraven const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1001227825Stheraven{ 1002227825Stheraven return !(__x == __y); 1003227825Stheraven} 1004227825Stheraven 1005227825Stheraven} // __gnu_cxx 1006227825Stheraven 1007227825Stheraven#endif // _LIBCPP_HASH_MAP 1008