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