unordered_map revision 241900
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===-------------------------- unordered_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_UNORDERED_MAP 12227825Stheraven#define _LIBCPP_UNORDERED_MAP 13227825Stheraven 14227825Stheraven/* 15227825Stheraven 16227825Stheraven unordered_map synopsis 17227825Stheraven 18227825Stheraven#include <initializer_list> 19227825Stheraven 20227825Stheravennamespace std 21227825Stheraven{ 22227825Stheraven 23227825Stheraventemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 24227825Stheraven class Alloc = allocator<pair<const Key, T>>> 25227825Stheravenclass unordered_map 26227825Stheraven{ 27227825Stheravenpublic: 28227825Stheraven // types 29227825Stheraven typedef Key key_type; 30227825Stheraven typedef T mapped_type; 31227825Stheraven typedef Hash hasher; 32227825Stheraven typedef Pred key_equal; 33227825Stheraven typedef Alloc allocator_type; 34227825Stheraven typedef pair<const key_type, mapped_type> value_type; 35227825Stheraven typedef value_type& reference; 36227825Stheraven typedef const value_type& const_reference; 37227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 38227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 39227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 40227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 41227825Stheraven 42227825Stheraven typedef /unspecified/ iterator; 43227825Stheraven typedef /unspecified/ const_iterator; 44227825Stheraven typedef /unspecified/ local_iterator; 45227825Stheraven typedef /unspecified/ const_local_iterator; 46227825Stheraven 47227825Stheraven unordered_map() 48227825Stheraven noexcept( 49227825Stheraven is_nothrow_default_constructible<hasher>::value && 50227825Stheraven is_nothrow_default_constructible<key_equal>::value && 51227825Stheraven is_nothrow_default_constructible<allocator_type>::value); 52227825Stheraven explicit unordered_map(size_type n, const hasher& hf = hasher(), 53227825Stheraven const key_equal& eql = key_equal(), 54227825Stheraven const allocator_type& a = allocator_type()); 55227825Stheraven template <class InputIterator> 56227825Stheraven unordered_map(InputIterator f, InputIterator l, 57227825Stheraven size_type n = 0, const hasher& hf = hasher(), 58227825Stheraven const key_equal& eql = key_equal(), 59227825Stheraven const allocator_type& a = allocator_type()); 60227825Stheraven explicit unordered_map(const allocator_type&); 61227825Stheraven unordered_map(const unordered_map&); 62227825Stheraven unordered_map(const unordered_map&, const Allocator&); 63227825Stheraven unordered_map(unordered_map&&) 64227825Stheraven noexcept( 65227825Stheraven is_nothrow_move_constructible<hasher>::value && 66227825Stheraven is_nothrow_move_constructible<key_equal>::value && 67227825Stheraven is_nothrow_move_constructible<allocator_type>::value); 68227825Stheraven unordered_map(unordered_map&&, const Allocator&); 69227825Stheraven unordered_map(initializer_list<value_type>, size_type n = 0, 70227825Stheraven const hasher& hf = hasher(), const key_equal& eql = key_equal(), 71227825Stheraven const allocator_type& a = allocator_type()); 72227825Stheraven ~unordered_map(); 73227825Stheraven unordered_map& operator=(const unordered_map&); 74227825Stheraven unordered_map& operator=(unordered_map&&) 75227825Stheraven noexcept( 76227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 77227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 78227825Stheraven is_nothrow_move_assignable<hasher>::value && 79227825Stheraven is_nothrow_move_assignable<key_equal>::value); 80227825Stheraven unordered_map& operator=(initializer_list<value_type>); 81227825Stheraven 82227825Stheraven allocator_type get_allocator() const noexcept; 83227825Stheraven 84227825Stheraven bool empty() const noexcept; 85227825Stheraven size_type size() const noexcept; 86227825Stheraven size_type max_size() const noexcept; 87227825Stheraven 88227825Stheraven iterator begin() noexcept; 89227825Stheraven iterator end() noexcept; 90227825Stheraven const_iterator begin() const noexcept; 91227825Stheraven const_iterator end() const noexcept; 92227825Stheraven const_iterator cbegin() const noexcept; 93227825Stheraven const_iterator cend() const noexcept; 94227825Stheraven 95227825Stheraven template <class... Args> 96227825Stheraven pair<iterator, bool> emplace(Args&&... args); 97227825Stheraven template <class... Args> 98227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 99227825Stheraven pair<iterator, bool> insert(const value_type& obj); 100227825Stheraven template <class P> 101227825Stheraven pair<iterator, bool> insert(P&& obj); 102227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 103227825Stheraven template <class P> 104227825Stheraven iterator insert(const_iterator hint, P&& obj); 105227825Stheraven template <class InputIterator> 106227825Stheraven void insert(InputIterator first, InputIterator last); 107227825Stheraven void insert(initializer_list<value_type>); 108227825Stheraven 109227825Stheraven iterator erase(const_iterator position); 110227825Stheraven size_type erase(const key_type& k); 111227825Stheraven iterator erase(const_iterator first, const_iterator last); 112227825Stheraven void clear() noexcept; 113227825Stheraven 114227825Stheraven void swap(unordered_map&) 115227825Stheraven noexcept( 116227825Stheraven (!allocator_type::propagate_on_container_swap::value || 117227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 118227825Stheraven __is_nothrow_swappable<hasher>::value && 119227825Stheraven __is_nothrow_swappable<key_equal>::value); 120227825Stheraven 121227825Stheraven hasher hash_function() const; 122227825Stheraven key_equal key_eq() const; 123227825Stheraven 124227825Stheraven iterator find(const key_type& k); 125227825Stheraven const_iterator find(const key_type& k) const; 126227825Stheraven size_type count(const key_type& k) const; 127227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 128227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 129227825Stheraven 130227825Stheraven mapped_type& operator[](const key_type& k); 131227825Stheraven mapped_type& operator[](key_type&& k); 132227825Stheraven 133227825Stheraven mapped_type& at(const key_type& k); 134227825Stheraven const mapped_type& at(const key_type& k) const; 135227825Stheraven 136227825Stheraven size_type bucket_count() const noexcept; 137227825Stheraven size_type max_bucket_count() const noexcept; 138227825Stheraven 139227825Stheraven size_type bucket_size(size_type n) const; 140227825Stheraven size_type bucket(const key_type& k) const; 141227825Stheraven 142227825Stheraven local_iterator begin(size_type n); 143227825Stheraven local_iterator end(size_type n); 144227825Stheraven const_local_iterator begin(size_type n) const; 145227825Stheraven const_local_iterator end(size_type n) const; 146227825Stheraven const_local_iterator cbegin(size_type n) const; 147227825Stheraven const_local_iterator cend(size_type n) const; 148227825Stheraven 149227825Stheraven float load_factor() const noexcept; 150227825Stheraven float max_load_factor() const noexcept; 151227825Stheraven void max_load_factor(float z); 152227825Stheraven void rehash(size_type n); 153227825Stheraven void reserve(size_type n); 154227825Stheraven}; 155227825Stheraven 156227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 157227825Stheraven void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x, 158227825Stheraven unordered_map<Key, T, Hash, Pred, Alloc>& y) 159227825Stheraven noexcept(noexcept(x.swap(y))); 160227825Stheraven 161227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 162227825Stheraven bool 163227825Stheraven operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 164227825Stheraven const unordered_map<Key, T, Hash, Pred, Alloc>& y); 165227825Stheraven 166227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 167227825Stheraven bool 168227825Stheraven operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 169227825Stheraven const unordered_map<Key, T, Hash, Pred, Alloc>& y); 170227825Stheraven 171227825Stheraventemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 172227825Stheraven class Alloc = allocator<pair<const Key, T>>> 173227825Stheravenclass unordered_multimap 174227825Stheraven{ 175227825Stheravenpublic: 176227825Stheraven // types 177227825Stheraven typedef Key key_type; 178227825Stheraven typedef T mapped_type; 179227825Stheraven typedef Hash hasher; 180227825Stheraven typedef Pred key_equal; 181227825Stheraven typedef Alloc allocator_type; 182227825Stheraven typedef pair<const key_type, mapped_type> value_type; 183227825Stheraven typedef value_type& reference; 184227825Stheraven typedef const value_type& const_reference; 185227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 186227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 187227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 188227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 189227825Stheraven 190227825Stheraven typedef /unspecified/ iterator; 191227825Stheraven typedef /unspecified/ const_iterator; 192227825Stheraven typedef /unspecified/ local_iterator; 193227825Stheraven typedef /unspecified/ const_local_iterator; 194227825Stheraven 195227825Stheraven unordered_multimap() 196227825Stheraven noexcept( 197227825Stheraven is_nothrow_default_constructible<hasher>::value && 198227825Stheraven is_nothrow_default_constructible<key_equal>::value && 199227825Stheraven is_nothrow_default_constructible<allocator_type>::value); 200227825Stheraven explicit unordered_multimap(size_type n, const hasher& hf = hasher(), 201227825Stheraven const key_equal& eql = key_equal(), 202227825Stheraven const allocator_type& a = allocator_type()); 203227825Stheraven template <class InputIterator> 204227825Stheraven unordered_multimap(InputIterator f, InputIterator l, 205227825Stheraven size_type n = 0, const hasher& hf = hasher(), 206227825Stheraven const key_equal& eql = key_equal(), 207227825Stheraven const allocator_type& a = allocator_type()); 208227825Stheraven explicit unordered_multimap(const allocator_type&); 209227825Stheraven unordered_multimap(const unordered_multimap&); 210227825Stheraven unordered_multimap(const unordered_multimap&, const Allocator&); 211227825Stheraven unordered_multimap(unordered_multimap&&) 212227825Stheraven noexcept( 213227825Stheraven is_nothrow_move_constructible<hasher>::value && 214227825Stheraven is_nothrow_move_constructible<key_equal>::value && 215227825Stheraven is_nothrow_move_constructible<allocator_type>::value); 216227825Stheraven unordered_multimap(unordered_multimap&&, const Allocator&); 217227825Stheraven unordered_multimap(initializer_list<value_type>, size_type n = 0, 218227825Stheraven const hasher& hf = hasher(), const key_equal& eql = key_equal(), 219227825Stheraven const allocator_type& a = allocator_type()); 220227825Stheraven ~unordered_multimap(); 221227825Stheraven unordered_multimap& operator=(const unordered_multimap&); 222227825Stheraven unordered_multimap& operator=(unordered_multimap&&) 223227825Stheraven noexcept( 224227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 225227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 226227825Stheraven is_nothrow_move_assignable<hasher>::value && 227227825Stheraven is_nothrow_move_assignable<key_equal>::value); 228227825Stheraven unordered_multimap& operator=(initializer_list<value_type>); 229227825Stheraven 230227825Stheraven allocator_type get_allocator() const noexcept; 231227825Stheraven 232227825Stheraven bool empty() const noexcept; 233227825Stheraven size_type size() const noexcept; 234227825Stheraven size_type max_size() const noexcept; 235227825Stheraven 236227825Stheraven iterator begin() noexcept; 237227825Stheraven iterator end() noexcept; 238227825Stheraven const_iterator begin() const noexcept; 239227825Stheraven const_iterator end() const noexcept; 240227825Stheraven const_iterator cbegin() const noexcept; 241227825Stheraven const_iterator cend() const noexcept; 242227825Stheraven 243227825Stheraven template <class... Args> 244227825Stheraven iterator emplace(Args&&... args); 245227825Stheraven template <class... Args> 246227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 247227825Stheraven iterator insert(const value_type& obj); 248227825Stheraven template <class P> 249227825Stheraven iterator insert(P&& obj); 250227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 251227825Stheraven template <class P> 252227825Stheraven iterator insert(const_iterator hint, P&& obj); 253227825Stheraven template <class InputIterator> 254227825Stheraven void insert(InputIterator first, InputIterator last); 255227825Stheraven void insert(initializer_list<value_type>); 256227825Stheraven 257227825Stheraven iterator erase(const_iterator position); 258227825Stheraven size_type erase(const key_type& k); 259227825Stheraven iterator erase(const_iterator first, const_iterator last); 260227825Stheraven void clear() noexcept; 261227825Stheraven 262227825Stheraven void swap(unordered_multimap&) 263227825Stheraven noexcept( 264227825Stheraven (!allocator_type::propagate_on_container_swap::value || 265227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 266227825Stheraven __is_nothrow_swappable<hasher>::value && 267227825Stheraven __is_nothrow_swappable<key_equal>::value); 268227825Stheraven 269227825Stheraven hasher hash_function() const; 270227825Stheraven key_equal key_eq() const; 271227825Stheraven 272227825Stheraven iterator find(const key_type& k); 273227825Stheraven const_iterator find(const key_type& k) const; 274227825Stheraven size_type count(const key_type& k) const; 275227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 276227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 277227825Stheraven 278227825Stheraven size_type bucket_count() const noexcept; 279227825Stheraven size_type max_bucket_count() const noexcept; 280227825Stheraven 281227825Stheraven size_type bucket_size(size_type n) const; 282227825Stheraven size_type bucket(const key_type& k) const; 283227825Stheraven 284227825Stheraven local_iterator begin(size_type n); 285227825Stheraven local_iterator end(size_type n); 286227825Stheraven const_local_iterator begin(size_type n) const; 287227825Stheraven const_local_iterator end(size_type n) const; 288227825Stheraven const_local_iterator cbegin(size_type n) const; 289227825Stheraven const_local_iterator cend(size_type n) const; 290227825Stheraven 291227825Stheraven float load_factor() const noexcept; 292227825Stheraven float max_load_factor() const noexcept; 293227825Stheraven void max_load_factor(float z); 294227825Stheraven void rehash(size_type n); 295227825Stheraven void reserve(size_type n); 296227825Stheraven}; 297227825Stheraven 298227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 299227825Stheraven void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 300227825Stheraven unordered_multimap<Key, T, Hash, Pred, Alloc>& y) 301227825Stheraven noexcept(noexcept(x.swap(y))); 302227825Stheraven 303227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 304227825Stheraven bool 305227825Stheraven operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 306227825Stheraven const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 307227825Stheraven 308227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 309227825Stheraven bool 310227825Stheraven operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 311227825Stheraven const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 312227825Stheraven 313227825Stheraven} // std 314227825Stheraven 315227825Stheraven*/ 316227825Stheraven 317227825Stheraven#include <__config> 318227825Stheraven#include <__hash_table> 319227825Stheraven#include <functional> 320227825Stheraven#include <stdexcept> 321227825Stheraven 322227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 323227825Stheraven#pragma GCC system_header 324227825Stheraven#endif 325227825Stheraven 326227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 327227825Stheraven 328232924Stheraventemplate <class _Key, class _Tp, class _Hash, bool = is_empty<_Hash>::value 329232924Stheraven#if __has_feature(is_final) 330232924Stheraven && !__is_final(_Hash) 331232924Stheraven#endif 332232924Stheraven > 333227825Stheravenclass __unordered_map_hasher 334227825Stheraven : private _Hash 335227825Stheraven{ 336232924Stheraven typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; 337232924Stheraven typedef pair<const _Key, _Tp> _Cp; 338227825Stheravenpublic: 339227825Stheraven _LIBCPP_INLINE_VISIBILITY 340227825Stheraven __unordered_map_hasher() 341227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 342227825Stheraven : _Hash() {} 343227825Stheraven _LIBCPP_INLINE_VISIBILITY 344227825Stheraven __unordered_map_hasher(const _Hash& __h) 345227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 346227825Stheraven : _Hash(__h) {} 347227825Stheraven _LIBCPP_INLINE_VISIBILITY 348227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return *this;} 349227825Stheraven _LIBCPP_INLINE_VISIBILITY 350232924Stheraven size_t operator()(const _Pp& __x) const 351227825Stheraven {return static_cast<const _Hash&>(*this)(__x.first);} 352227825Stheraven _LIBCPP_INLINE_VISIBILITY 353232924Stheraven size_t operator()(const _Cp& __x) const 354232924Stheraven {return static_cast<const _Hash&>(*this)(__x.first);} 355232924Stheraven _LIBCPP_INLINE_VISIBILITY 356232924Stheraven size_t operator()(const _Key& __x) const 357227825Stheraven {return static_cast<const _Hash&>(*this)(__x);} 358227825Stheraven}; 359227825Stheraven 360232924Stheraventemplate <class _Key, class _Tp, class _Hash> 361232924Stheravenclass __unordered_map_hasher<_Key, _Tp, _Hash, false> 362227825Stheraven{ 363227825Stheraven _Hash __hash_; 364232924Stheraven 365232924Stheraven typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; 366232924Stheraven typedef pair<const _Key, _Tp> _Cp; 367227825Stheravenpublic: 368227825Stheraven _LIBCPP_INLINE_VISIBILITY 369227825Stheraven __unordered_map_hasher() 370227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 371227825Stheraven : __hash_() {} 372227825Stheraven _LIBCPP_INLINE_VISIBILITY 373227825Stheraven __unordered_map_hasher(const _Hash& __h) 374227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 375227825Stheraven : __hash_(__h) {} 376227825Stheraven _LIBCPP_INLINE_VISIBILITY 377227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 378227825Stheraven _LIBCPP_INLINE_VISIBILITY 379232924Stheraven size_t operator()(const _Pp& __x) const 380227825Stheraven {return __hash_(__x.first);} 381227825Stheraven _LIBCPP_INLINE_VISIBILITY 382232924Stheraven size_t operator()(const _Cp& __x) const 383232924Stheraven {return __hash_(__x.first);} 384232924Stheraven _LIBCPP_INLINE_VISIBILITY 385232924Stheraven size_t operator()(const _Key& __x) const 386227825Stheraven {return __hash_(__x);} 387227825Stheraven}; 388227825Stheraven 389232924Stheraventemplate <class _Key, class _Tp, class _Pred, bool = is_empty<_Pred>::value 390232924Stheraven#if __has_feature(is_final) 391232924Stheraven && !__is_final(_Pred) 392232924Stheraven#endif 393232924Stheraven > 394227825Stheravenclass __unordered_map_equal 395227825Stheraven : private _Pred 396227825Stheraven{ 397232924Stheraven typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; 398232924Stheraven typedef pair<const _Key, _Tp> _Cp; 399227825Stheravenpublic: 400227825Stheraven _LIBCPP_INLINE_VISIBILITY 401227825Stheraven __unordered_map_equal() 402227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 403227825Stheraven : _Pred() {} 404227825Stheraven _LIBCPP_INLINE_VISIBILITY 405227825Stheraven __unordered_map_equal(const _Pred& __p) 406227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 407227825Stheraven : _Pred(__p) {} 408227825Stheraven _LIBCPP_INLINE_VISIBILITY 409227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return *this;} 410227825Stheraven _LIBCPP_INLINE_VISIBILITY 411232924Stheraven bool operator()(const _Pp& __x, const _Pp& __y) const 412227825Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 413227825Stheraven _LIBCPP_INLINE_VISIBILITY 414232924Stheraven bool operator()(const _Pp& __x, const _Cp& __y) const 415232924Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 416227825Stheraven _LIBCPP_INLINE_VISIBILITY 417232924Stheraven bool operator()(const _Pp& __x, const _Key& __y) const 418227825Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y);} 419227825Stheraven _LIBCPP_INLINE_VISIBILITY 420232924Stheraven bool operator()(const _Cp& __x, const _Pp& __y) const 421232924Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 422232924Stheraven _LIBCPP_INLINE_VISIBILITY 423232924Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 424232924Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 425232924Stheraven _LIBCPP_INLINE_VISIBILITY 426232924Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 427232924Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y);} 428232924Stheraven _LIBCPP_INLINE_VISIBILITY 429232924Stheraven bool operator()(const _Key& __x, const _Pp& __y) const 430232924Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.first);} 431232924Stheraven _LIBCPP_INLINE_VISIBILITY 432232924Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 433232924Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.first);} 434232924Stheraven _LIBCPP_INLINE_VISIBILITY 435232924Stheraven bool operator()(const _Key& __x, const _Key& __y) const 436227825Stheraven {return static_cast<const _Pred&>(*this)(__x, __y);} 437227825Stheraven}; 438227825Stheraven 439232924Stheraventemplate <class _Key, class _Tp, class _Pred> 440232924Stheravenclass __unordered_map_equal<_Key, _Tp, _Pred, false> 441227825Stheraven{ 442227825Stheraven _Pred __pred_; 443232924Stheraven 444232924Stheraven typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; 445232924Stheraven typedef pair<const _Key, _Tp> _Cp; 446227825Stheravenpublic: 447227825Stheraven _LIBCPP_INLINE_VISIBILITY 448227825Stheraven __unordered_map_equal() 449227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 450227825Stheraven : __pred_() {} 451227825Stheraven _LIBCPP_INLINE_VISIBILITY 452227825Stheraven __unordered_map_equal(const _Pred& __p) 453227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 454227825Stheraven : __pred_(__p) {} 455227825Stheraven _LIBCPP_INLINE_VISIBILITY 456227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 457227825Stheraven _LIBCPP_INLINE_VISIBILITY 458232924Stheraven bool operator()(const _Pp& __x, const _Pp& __y) const 459227825Stheraven {return __pred_(__x.first, __y.first);} 460227825Stheraven _LIBCPP_INLINE_VISIBILITY 461232924Stheraven bool operator()(const _Pp& __x, const _Cp& __y) const 462232924Stheraven {return __pred_(__x.first, __y.first);} 463227825Stheraven _LIBCPP_INLINE_VISIBILITY 464232924Stheraven bool operator()(const _Pp& __x, const _Key& __y) const 465227825Stheraven {return __pred_(__x.first, __y);} 466227825Stheraven _LIBCPP_INLINE_VISIBILITY 467232924Stheraven bool operator()(const _Cp& __x, const _Pp& __y) const 468232924Stheraven {return __pred_(__x.first, __y.first);} 469232924Stheraven _LIBCPP_INLINE_VISIBILITY 470232924Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 471232924Stheraven {return __pred_(__x.first, __y.first);} 472232924Stheraven _LIBCPP_INLINE_VISIBILITY 473232924Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 474232924Stheraven {return __pred_(__x.first, __y);} 475232924Stheraven _LIBCPP_INLINE_VISIBILITY 476232924Stheraven bool operator()(const _Key& __x, const _Pp& __y) const 477232924Stheraven {return __pred_(__x, __y.first);} 478232924Stheraven _LIBCPP_INLINE_VISIBILITY 479232924Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 480232924Stheraven {return __pred_(__x, __y.first);} 481232924Stheraven _LIBCPP_INLINE_VISIBILITY 482232924Stheraven bool operator()(const _Key& __x, const _Key& __y) const 483227825Stheraven {return __pred_(__x, __y);} 484227825Stheraven}; 485227825Stheraven 486227825Stheraventemplate <class _Alloc> 487227825Stheravenclass __hash_map_node_destructor 488227825Stheraven{ 489227825Stheraven typedef _Alloc allocator_type; 490227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 491227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 492227825Stheravenpublic: 493227825Stheraven typedef typename __alloc_traits::pointer pointer; 494227825Stheravenprivate: 495227825Stheraven typedef typename value_type::first_type first_type; 496227825Stheraven typedef typename value_type::second_type second_type; 497227825Stheraven 498227825Stheraven allocator_type& __na_; 499227825Stheraven 500227825Stheraven __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 501227825Stheraven 502227825Stheravenpublic: 503227825Stheraven bool __first_constructed; 504227825Stheraven bool __second_constructed; 505227825Stheraven 506227825Stheraven _LIBCPP_INLINE_VISIBILITY 507227825Stheraven explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 508227825Stheraven : __na_(__na), 509227825Stheraven __first_constructed(false), 510227825Stheraven __second_constructed(false) 511227825Stheraven {} 512227825Stheraven 513227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 514227825Stheraven _LIBCPP_INLINE_VISIBILITY 515227825Stheraven __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 516227825Stheraven _NOEXCEPT 517227825Stheraven : __na_(__x.__na_), 518227825Stheraven __first_constructed(__x.__value_constructed), 519227825Stheraven __second_constructed(__x.__value_constructed) 520227825Stheraven { 521227825Stheraven __x.__value_constructed = false; 522227825Stheraven } 523227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 524227825Stheraven _LIBCPP_INLINE_VISIBILITY 525227825Stheraven __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 526227825Stheraven : __na_(__x.__na_), 527227825Stheraven __first_constructed(__x.__value_constructed), 528227825Stheraven __second_constructed(__x.__value_constructed) 529227825Stheraven { 530227825Stheraven const_cast<bool&>(__x.__value_constructed) = false; 531227825Stheraven } 532227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 533227825Stheraven 534227825Stheraven _LIBCPP_INLINE_VISIBILITY 535227825Stheraven void operator()(pointer __p) _NOEXCEPT 536227825Stheraven { 537227825Stheraven if (__second_constructed) 538227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second)); 539227825Stheraven if (__first_constructed) 540227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); 541227825Stheraven if (__p) 542227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 543227825Stheraven } 544227825Stheraven}; 545227825Stheraven 546227825Stheraventemplate <class _HashIterator> 547227825Stheravenclass _LIBCPP_VISIBLE __hash_map_iterator 548227825Stheraven{ 549227825Stheraven _HashIterator __i_; 550227825Stheraven 551227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 552227825Stheraven typedef const typename _HashIterator::value_type::first_type key_type; 553227825Stheraven typedef typename _HashIterator::value_type::second_type mapped_type; 554227825Stheravenpublic: 555227825Stheraven typedef forward_iterator_tag iterator_category; 556227825Stheraven typedef pair<key_type, mapped_type> value_type; 557227825Stheraven typedef typename _HashIterator::difference_type difference_type; 558227825Stheraven typedef value_type& reference; 559227825Stheraven typedef typename __pointer_traits::template 560227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 561227825Stheraven rebind<value_type> 562227825Stheraven#else 563227825Stheraven rebind<value_type>::other 564227825Stheraven#endif 565227825Stheraven pointer; 566227825Stheraven 567227825Stheraven _LIBCPP_INLINE_VISIBILITY 568227825Stheraven __hash_map_iterator() _NOEXCEPT {} 569227825Stheraven 570227825Stheraven _LIBCPP_INLINE_VISIBILITY 571227825Stheraven __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 572227825Stheraven 573227825Stheraven _LIBCPP_INLINE_VISIBILITY 574227825Stheraven reference operator*() const {return *operator->();} 575227825Stheraven _LIBCPP_INLINE_VISIBILITY 576227825Stheraven pointer operator->() const {return (pointer)__i_.operator->();} 577227825Stheraven 578227825Stheraven _LIBCPP_INLINE_VISIBILITY 579227825Stheraven __hash_map_iterator& operator++() {++__i_; return *this;} 580227825Stheraven _LIBCPP_INLINE_VISIBILITY 581227825Stheraven __hash_map_iterator operator++(int) 582227825Stheraven { 583227825Stheraven __hash_map_iterator __t(*this); 584227825Stheraven ++(*this); 585227825Stheraven return __t; 586227825Stheraven } 587227825Stheraven 588227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 589227825Stheraven bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 590227825Stheraven {return __x.__i_ == __y.__i_;} 591227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 592227825Stheraven bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 593227825Stheraven {return __x.__i_ != __y.__i_;} 594227825Stheraven 595227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; 596227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; 597227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator; 598227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator; 599227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator; 600227825Stheraven}; 601227825Stheraven 602227825Stheraventemplate <class _HashIterator> 603227825Stheravenclass _LIBCPP_VISIBLE __hash_map_const_iterator 604227825Stheraven{ 605227825Stheraven _HashIterator __i_; 606227825Stheraven 607227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 608227825Stheraven typedef const typename _HashIterator::value_type::first_type key_type; 609227825Stheraven typedef typename _HashIterator::value_type::second_type mapped_type; 610227825Stheravenpublic: 611227825Stheraven typedef forward_iterator_tag iterator_category; 612227825Stheraven typedef pair<key_type, mapped_type> value_type; 613227825Stheraven typedef typename _HashIterator::difference_type difference_type; 614227825Stheraven typedef const value_type& reference; 615227825Stheraven typedef typename __pointer_traits::template 616227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 617227825Stheraven rebind<const value_type> 618227825Stheraven#else 619227825Stheraven rebind<const value_type>::other 620227825Stheraven#endif 621227825Stheraven pointer; 622227825Stheraven 623227825Stheraven _LIBCPP_INLINE_VISIBILITY 624227825Stheraven __hash_map_const_iterator() _NOEXCEPT {} 625227825Stheraven 626227825Stheraven _LIBCPP_INLINE_VISIBILITY 627227825Stheraven __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 628227825Stheraven _LIBCPP_INLINE_VISIBILITY 629227825Stheraven __hash_map_const_iterator( 630227825Stheraven __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 631227825Stheraven _NOEXCEPT 632227825Stheraven : __i_(__i.__i_) {} 633227825Stheraven 634227825Stheraven _LIBCPP_INLINE_VISIBILITY 635227825Stheraven reference operator*() const {return *operator->();} 636227825Stheraven _LIBCPP_INLINE_VISIBILITY 637227825Stheraven pointer operator->() const {return (pointer)__i_.operator->();} 638227825Stheraven 639227825Stheraven _LIBCPP_INLINE_VISIBILITY 640227825Stheraven __hash_map_const_iterator& operator++() {++__i_; return *this;} 641227825Stheraven _LIBCPP_INLINE_VISIBILITY 642227825Stheraven __hash_map_const_iterator operator++(int) 643227825Stheraven { 644227825Stheraven __hash_map_const_iterator __t(*this); 645227825Stheraven ++(*this); 646227825Stheraven return __t; 647227825Stheraven } 648227825Stheraven 649227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 650227825Stheraven bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 651227825Stheraven {return __x.__i_ == __y.__i_;} 652227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 653227825Stheraven bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 654227825Stheraven {return __x.__i_ != __y.__i_;} 655227825Stheraven 656227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; 657227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; 658227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator; 659227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator; 660227825Stheraven}; 661227825Stheraven 662227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 663227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 664227825Stheravenclass _LIBCPP_VISIBLE unordered_map 665227825Stheraven{ 666227825Stheravenpublic: 667227825Stheraven // types 668227825Stheraven typedef _Key key_type; 669227825Stheraven typedef _Tp mapped_type; 670227825Stheraven typedef _Hash hasher; 671227825Stheraven typedef _Pred key_equal; 672227825Stheraven typedef _Alloc allocator_type; 673227825Stheraven typedef pair<const key_type, mapped_type> value_type; 674227825Stheraven typedef value_type& reference; 675227825Stheraven typedef const value_type& const_reference; 676227825Stheraven 677227825Stheravenprivate: 678227825Stheraven typedef pair<key_type, mapped_type> __value_type; 679232924Stheraven typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher; 680232924Stheraven typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal; 681227825Stheraven typedef typename allocator_traits<allocator_type>::template 682227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 683227825Stheraven rebind_alloc<__value_type> 684227825Stheraven#else 685227825Stheraven rebind_alloc<__value_type>::other 686227825Stheraven#endif 687227825Stheraven __allocator_type; 688227825Stheraven 689227825Stheraven typedef __hash_table<__value_type, __hasher, 690227825Stheraven __key_equal, __allocator_type> __table; 691227825Stheraven 692227825Stheraven __table __table_; 693227825Stheraven 694227825Stheraven typedef typename __table::__node_pointer __node_pointer; 695227825Stheraven typedef typename __table::__node_const_pointer __node_const_pointer; 696227825Stheraven typedef typename __table::__node_traits __node_traits; 697227825Stheraven typedef typename __table::__node_allocator __node_allocator; 698227825Stheraven typedef typename __table::__node __node; 699232924Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 700232924Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 701227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 702227825Stheravenpublic: 703227825Stheraven typedef typename __alloc_traits::pointer pointer; 704227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 705227825Stheraven typedef typename __alloc_traits::size_type size_type; 706227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 707227825Stheraven 708227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 709227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 710227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 711227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 712227825Stheraven 713227825Stheraven _LIBCPP_INLINE_VISIBILITY 714227825Stheraven unordered_map() 715227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 716227825Stheraven {} // = default; 717227825Stheraven explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 718227825Stheraven const key_equal& __eql = key_equal()); 719227825Stheraven unordered_map(size_type __n, const hasher& __hf, 720227825Stheraven const key_equal& __eql, 721227825Stheraven const allocator_type& __a); 722227825Stheraven template <class _InputIterator> 723227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last); 724227825Stheraven template <class _InputIterator> 725227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 726227825Stheraven size_type __n, const hasher& __hf = hasher(), 727227825Stheraven const key_equal& __eql = key_equal()); 728227825Stheraven template <class _InputIterator> 729227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 730227825Stheraven size_type __n, const hasher& __hf, 731227825Stheraven const key_equal& __eql, 732227825Stheraven const allocator_type& __a); 733227825Stheraven explicit unordered_map(const allocator_type& __a); 734227825Stheraven unordered_map(const unordered_map& __u); 735227825Stheraven unordered_map(const unordered_map& __u, const allocator_type& __a); 736227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 737227825Stheraven unordered_map(unordered_map&& __u) 738227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 739227825Stheraven unordered_map(unordered_map&& __u, const allocator_type& __a); 740227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 741227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 742227825Stheraven unordered_map(initializer_list<value_type> __il); 743227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 744227825Stheraven const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 745227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 746227825Stheraven const hasher& __hf, const key_equal& __eql, 747227825Stheraven const allocator_type& __a); 748227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 749227825Stheraven // ~unordered_map() = default; 750227825Stheraven _LIBCPP_INLINE_VISIBILITY 751227825Stheraven unordered_map& operator=(const unordered_map& __u) 752227825Stheraven { 753227825Stheraven __table_ = __u.__table_; 754227825Stheraven return *this; 755227825Stheraven } 756227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 757227825Stheraven unordered_map& operator=(unordered_map&& __u) 758227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 759227825Stheraven#endif 760227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 761227825Stheraven unordered_map& operator=(initializer_list<value_type> __il); 762227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 763227825Stheraven 764227825Stheraven _LIBCPP_INLINE_VISIBILITY 765227825Stheraven allocator_type get_allocator() const _NOEXCEPT 766227825Stheraven {return allocator_type(__table_.__node_alloc());} 767227825Stheraven 768227825Stheraven _LIBCPP_INLINE_VISIBILITY 769227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 770227825Stheraven _LIBCPP_INLINE_VISIBILITY 771227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 772227825Stheraven _LIBCPP_INLINE_VISIBILITY 773227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 774227825Stheraven 775227825Stheraven _LIBCPP_INLINE_VISIBILITY 776227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 777227825Stheraven _LIBCPP_INLINE_VISIBILITY 778227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 779227825Stheraven _LIBCPP_INLINE_VISIBILITY 780227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 781227825Stheraven _LIBCPP_INLINE_VISIBILITY 782227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 783227825Stheraven _LIBCPP_INLINE_VISIBILITY 784227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 785227825Stheraven _LIBCPP_INLINE_VISIBILITY 786227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 787227825Stheraven 788227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 789227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 790227825Stheraven 791241900Sdim template <class... _Args> 792241900Sdim pair<iterator, bool> emplace(_Args&&... __args); 793227825Stheraven 794241900Sdim template <class... _Args> 795227825Stheraven _LIBCPP_INLINE_VISIBILITY 796241900Sdim iterator emplace_hint(const_iterator, _Args&&... __args) 797241900Sdim {return emplace(_VSTD::forward<_Args>(__args)...).first;} 798227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 799227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 800227825Stheraven _LIBCPP_INLINE_VISIBILITY 801227825Stheraven pair<iterator, bool> insert(const value_type& __x) 802227825Stheraven {return __table_.__insert_unique(__x);} 803227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 804232924Stheraven template <class _Pp, 805232924Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 806227825Stheraven _LIBCPP_INLINE_VISIBILITY 807232924Stheraven pair<iterator, bool> insert(_Pp&& __x) 808232924Stheraven {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 809227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 810227825Stheraven _LIBCPP_INLINE_VISIBILITY 811227825Stheraven iterator insert(const_iterator, const value_type& __x) 812227825Stheraven {return insert(__x).first;} 813227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 814232924Stheraven template <class _Pp, 815232924Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 816227825Stheraven _LIBCPP_INLINE_VISIBILITY 817232924Stheraven iterator insert(const_iterator, _Pp&& __x) 818232924Stheraven {return insert(_VSTD::forward<_Pp>(__x)).first;} 819227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 820227825Stheraven template <class _InputIterator> 821227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 822227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 823227825Stheraven _LIBCPP_INLINE_VISIBILITY 824227825Stheraven void insert(initializer_list<value_type> __il) 825227825Stheraven {insert(__il.begin(), __il.end());} 826227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 827227825Stheraven 828227825Stheraven _LIBCPP_INLINE_VISIBILITY 829227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 830227825Stheraven _LIBCPP_INLINE_VISIBILITY 831227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 832227825Stheraven _LIBCPP_INLINE_VISIBILITY 833227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 834227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 835227825Stheraven _LIBCPP_INLINE_VISIBILITY 836227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 837227825Stheraven 838227825Stheraven _LIBCPP_INLINE_VISIBILITY 839227825Stheraven void swap(unordered_map& __u) 840227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 841227825Stheraven {__table_.swap(__u.__table_);} 842227825Stheraven 843227825Stheraven _LIBCPP_INLINE_VISIBILITY 844227825Stheraven hasher hash_function() const 845227825Stheraven {return __table_.hash_function().hash_function();} 846227825Stheraven _LIBCPP_INLINE_VISIBILITY 847227825Stheraven key_equal key_eq() const 848227825Stheraven {return __table_.key_eq().key_eq();} 849227825Stheraven 850227825Stheraven _LIBCPP_INLINE_VISIBILITY 851227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 852227825Stheraven _LIBCPP_INLINE_VISIBILITY 853227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 854227825Stheraven _LIBCPP_INLINE_VISIBILITY 855227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 856227825Stheraven _LIBCPP_INLINE_VISIBILITY 857227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 858227825Stheraven {return __table_.__equal_range_unique(__k);} 859227825Stheraven _LIBCPP_INLINE_VISIBILITY 860227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 861227825Stheraven {return __table_.__equal_range_unique(__k);} 862227825Stheraven 863227825Stheraven mapped_type& operator[](const key_type& __k); 864227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 865227825Stheraven mapped_type& operator[](key_type&& __k); 866227825Stheraven#endif 867227825Stheraven 868227825Stheraven mapped_type& at(const key_type& __k); 869227825Stheraven const mapped_type& at(const key_type& __k) const; 870227825Stheraven 871227825Stheraven _LIBCPP_INLINE_VISIBILITY 872227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 873227825Stheraven _LIBCPP_INLINE_VISIBILITY 874227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 875227825Stheraven 876227825Stheraven _LIBCPP_INLINE_VISIBILITY 877227825Stheraven size_type bucket_size(size_type __n) const 878227825Stheraven {return __table_.bucket_size(__n);} 879227825Stheraven _LIBCPP_INLINE_VISIBILITY 880227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 881227825Stheraven 882227825Stheraven _LIBCPP_INLINE_VISIBILITY 883227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 884227825Stheraven _LIBCPP_INLINE_VISIBILITY 885227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 886227825Stheraven _LIBCPP_INLINE_VISIBILITY 887227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 888227825Stheraven _LIBCPP_INLINE_VISIBILITY 889227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 890227825Stheraven _LIBCPP_INLINE_VISIBILITY 891227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 892227825Stheraven _LIBCPP_INLINE_VISIBILITY 893227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 894227825Stheraven 895227825Stheraven _LIBCPP_INLINE_VISIBILITY 896227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 897227825Stheraven _LIBCPP_INLINE_VISIBILITY 898227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 899227825Stheraven _LIBCPP_INLINE_VISIBILITY 900227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 901227825Stheraven _LIBCPP_INLINE_VISIBILITY 902227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 903227825Stheraven _LIBCPP_INLINE_VISIBILITY 904227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 905227825Stheraven 906227825Stheravenprivate: 907227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 908241900Sdim __node_holder __construct_node(); 909241900Sdim template <class _A0> 910241900Sdim typename enable_if 911241900Sdim < 912241900Sdim is_constructible<value_type, _A0>::value, 913241900Sdim __node_holder 914241900Sdim >::type 915241900Sdim __construct_node(_A0&& __a0); 916241900Sdim template <class _A0> 917241900Sdim typename enable_if 918241900Sdim < 919241900Sdim is_constructible<key_type, _A0>::value, 920241900Sdim __node_holder 921241900Sdim >::type 922241900Sdim __construct_node(_A0&& __a0); 923227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 924241900Sdim template <class _A0, class _A1, class ..._Args> 925241900Sdim __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 926227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 927227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 928227825Stheraven __node_holder __construct_node(const key_type& __k); 929227825Stheraven#endif 930227825Stheraven}; 931227825Stheraven 932227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 933227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 934227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 935227825Stheraven : __table_(__hf, __eql) 936227825Stheraven{ 937227825Stheraven __table_.rehash(__n); 938227825Stheraven} 939227825Stheraven 940227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 941227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 942227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 943227825Stheraven const allocator_type& __a) 944227825Stheraven : __table_(__hf, __eql, __a) 945227825Stheraven{ 946227825Stheraven __table_.rehash(__n); 947227825Stheraven} 948227825Stheraven 949227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 950227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 951227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 952227825Stheraven const allocator_type& __a) 953227825Stheraven : __table_(__a) 954227825Stheraven{ 955227825Stheraven} 956227825Stheraven 957227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 958227825Stheraventemplate <class _InputIterator> 959227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 960227825Stheraven _InputIterator __first, _InputIterator __last) 961227825Stheraven{ 962227825Stheraven insert(__first, __last); 963227825Stheraven} 964227825Stheraven 965227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 966227825Stheraventemplate <class _InputIterator> 967227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 968227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 969227825Stheraven const hasher& __hf, const key_equal& __eql) 970227825Stheraven : __table_(__hf, __eql) 971227825Stheraven{ 972227825Stheraven __table_.rehash(__n); 973227825Stheraven insert(__first, __last); 974227825Stheraven} 975227825Stheraven 976227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 977227825Stheraventemplate <class _InputIterator> 978227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 979227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 980227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 981227825Stheraven : __table_(__hf, __eql, __a) 982227825Stheraven{ 983227825Stheraven __table_.rehash(__n); 984227825Stheraven insert(__first, __last); 985227825Stheraven} 986227825Stheraven 987227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 988227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 989227825Stheraven const unordered_map& __u) 990227825Stheraven : __table_(__u.__table_) 991227825Stheraven{ 992227825Stheraven __table_.rehash(__u.bucket_count()); 993227825Stheraven insert(__u.begin(), __u.end()); 994227825Stheraven} 995227825Stheraven 996227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 997227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 998227825Stheraven const unordered_map& __u, const allocator_type& __a) 999227825Stheraven : __table_(__u.__table_, __a) 1000227825Stheraven{ 1001227825Stheraven __table_.rehash(__u.bucket_count()); 1002227825Stheraven insert(__u.begin(), __u.end()); 1003227825Stheraven} 1004227825Stheraven 1005227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1006227825Stheraven 1007227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1008227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1009227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1010227825Stheraven unordered_map&& __u) 1011227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1012227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1013227825Stheraven{ 1014227825Stheraven} 1015227825Stheraven 1016227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1017227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1018227825Stheraven unordered_map&& __u, const allocator_type& __a) 1019227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1020227825Stheraven{ 1021227825Stheraven if (__a != __u.get_allocator()) 1022227825Stheraven { 1023227825Stheraven iterator __i = __u.begin(); 1024227825Stheraven while (__u.size() != 0) 1025227825Stheraven __table_.__insert_unique( 1026227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1027227825Stheraven ); 1028227825Stheraven } 1029227825Stheraven} 1030227825Stheraven 1031227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1032227825Stheraven 1033227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1034227825Stheraven 1035227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1036227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1037227825Stheraven initializer_list<value_type> __il) 1038227825Stheraven{ 1039227825Stheraven insert(__il.begin(), __il.end()); 1040227825Stheraven} 1041227825Stheraven 1042227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1043227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1044227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1045227825Stheraven const key_equal& __eql) 1046227825Stheraven : __table_(__hf, __eql) 1047227825Stheraven{ 1048227825Stheraven __table_.rehash(__n); 1049227825Stheraven insert(__il.begin(), __il.end()); 1050227825Stheraven} 1051227825Stheraven 1052227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1053227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1054227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1055227825Stheraven const key_equal& __eql, const allocator_type& __a) 1056227825Stheraven : __table_(__hf, __eql, __a) 1057227825Stheraven{ 1058227825Stheraven __table_.rehash(__n); 1059227825Stheraven insert(__il.begin(), __il.end()); 1060227825Stheraven} 1061227825Stheraven 1062227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1063227825Stheraven 1064227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1065227825Stheraven 1066227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1067227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1068227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1069227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1070227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1071227825Stheraven{ 1072227825Stheraven __table_ = _VSTD::move(__u.__table_); 1073227825Stheraven return *this; 1074227825Stheraven} 1075227825Stheraven 1076227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1077227825Stheraven 1078227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1079227825Stheraven 1080227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1081227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1082227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1083227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1084227825Stheraven initializer_list<value_type> __il) 1085227825Stheraven{ 1086227825Stheraven __table_.__assign_unique(__il.begin(), __il.end()); 1087227825Stheraven return *this; 1088227825Stheraven} 1089227825Stheraven 1090227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1091227825Stheraven 1092227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1093227825Stheraven 1094227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1095227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1096241900Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1097227825Stheraven{ 1098227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1099232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1100241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1101227825Stheraven __h.get_deleter().__first_constructed = true; 1102227825Stheraven __h.get_deleter().__second_constructed = true; 1103227825Stheraven return __h; 1104227825Stheraven} 1105227825Stheraven 1106227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1107241900Sdimtemplate <class _A0> 1108241900Sdimtypename enable_if 1109241900Sdim< 1110241900Sdim is_constructible<pair<const _Key, _Tp>, _A0>::value, 1111241900Sdim typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1112241900Sdim>::type 1113227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1114227825Stheraven{ 1115227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1116232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1117227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1118227825Stheraven _VSTD::forward<_A0>(__a0)); 1119227825Stheraven __h.get_deleter().__first_constructed = true; 1120227825Stheraven __h.get_deleter().__second_constructed = true; 1121227825Stheraven return __h; 1122227825Stheraven} 1123227825Stheraven 1124241900Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1125241900Sdimtemplate <class _A0> 1126241900Sdimtypename enable_if 1127241900Sdim< 1128241900Sdim is_constructible<_Key, _A0>::value, 1129241900Sdim typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1130241900Sdim>::type 1131241900Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1132241900Sdim{ 1133241900Sdim __node_allocator& __na = __table_.__node_alloc(); 1134241900Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1135241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), 1136241900Sdim _VSTD::forward<_A0>(__a0)); 1137241900Sdim __h.get_deleter().__first_constructed = true; 1138241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1139241900Sdim __h.get_deleter().__second_constructed = true; 1140241900Sdim return __h; 1141241900Sdim} 1142241900Sdim 1143227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1144227825Stheraven 1145227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1146241900Sdimtemplate <class _A0, class _A1, class ..._Args> 1147241900Sdimtypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1148241900Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1149241900Sdim _A1&& __a1, 1150241900Sdim _Args&&... __args) 1151241900Sdim{ 1152241900Sdim __node_allocator& __na = __table_.__node_alloc(); 1153241900Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1154241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1155241900Sdim _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1156241900Sdim _VSTD::forward<_Args>(__args)...); 1157241900Sdim __h.get_deleter().__first_constructed = true; 1158241900Sdim __h.get_deleter().__second_constructed = true; 1159241900Sdim return __h; 1160241900Sdim} 1161241900Sdim 1162241900Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1163241900Sdimtemplate <class... _Args> 1164227825Stheravenpair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1165241900Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1166227825Stheraven{ 1167241900Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1168227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1169227825Stheraven if (__r.second) 1170227825Stheraven __h.release(); 1171227825Stheraven return __r; 1172227825Stheraven} 1173227825Stheraven 1174227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1175227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1176227825Stheraven 1177227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1178227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1179227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) 1180227825Stheraven{ 1181227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1182232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1183227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); 1184227825Stheraven __h.get_deleter().__first_constructed = true; 1185227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1186227825Stheraven __h.get_deleter().__second_constructed = true; 1187227825Stheraven return _VSTD::move(__h); 1188227825Stheraven} 1189227825Stheraven 1190227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1191227825Stheraven 1192227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1193227825Stheraventemplate <class _InputIterator> 1194227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1195227825Stheravenvoid 1196227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1197227825Stheraven _InputIterator __last) 1198227825Stheraven{ 1199227825Stheraven for (; __first != __last; ++__first) 1200227825Stheraven __table_.__insert_unique(*__first); 1201227825Stheraven} 1202227825Stheraven 1203227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1204227825Stheraven_Tp& 1205227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1206227825Stheraven{ 1207227825Stheraven iterator __i = find(__k); 1208227825Stheraven if (__i != end()) 1209227825Stheraven return __i->second; 1210227825Stheraven __node_holder __h = __construct_node(__k); 1211227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1212227825Stheraven __h.release(); 1213227825Stheraven return __r.first->second; 1214227825Stheraven} 1215227825Stheraven 1216227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1217227825Stheraven 1218227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1219227825Stheraven_Tp& 1220227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1221227825Stheraven{ 1222227825Stheraven iterator __i = find(__k); 1223227825Stheraven if (__i != end()) 1224227825Stheraven return __i->second; 1225227825Stheraven __node_holder __h = __construct_node(_VSTD::move(__k)); 1226227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1227227825Stheraven __h.release(); 1228227825Stheraven return __r.first->second; 1229227825Stheraven} 1230227825Stheraven 1231227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1232227825Stheraven 1233227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1234227825Stheraven_Tp& 1235227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1236227825Stheraven{ 1237227825Stheraven iterator __i = find(__k); 1238227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1239227825Stheraven if (__i == end()) 1240227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1241227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1242227825Stheraven return __i->second; 1243227825Stheraven} 1244227825Stheraven 1245227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1246227825Stheravenconst _Tp& 1247227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1248227825Stheraven{ 1249227825Stheraven const_iterator __i = find(__k); 1250227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1251227825Stheraven if (__i == end()) 1252227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1253227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1254227825Stheraven return __i->second; 1255227825Stheraven} 1256227825Stheraven 1257227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1258227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1259227825Stheravenvoid 1260227825Stheravenswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1261227825Stheraven unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1262227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1263227825Stheraven{ 1264227825Stheraven __x.swap(__y); 1265227825Stheraven} 1266227825Stheraven 1267227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1268227825Stheravenbool 1269227825Stheravenoperator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1270227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1271227825Stheraven{ 1272227825Stheraven if (__x.size() != __y.size()) 1273227825Stheraven return false; 1274227825Stheraven typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1275227825Stheraven const_iterator; 1276227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1277227825Stheraven __i != __ex; ++__i) 1278227825Stheraven { 1279227825Stheraven const_iterator __j = __y.find(__i->first); 1280227825Stheraven if (__j == __ey || !(*__i == *__j)) 1281227825Stheraven return false; 1282227825Stheraven } 1283227825Stheraven return true; 1284227825Stheraven} 1285227825Stheraven 1286227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1287227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1288227825Stheravenbool 1289227825Stheravenoperator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1290227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1291227825Stheraven{ 1292227825Stheraven return !(__x == __y); 1293227825Stheraven} 1294227825Stheraven 1295227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1296227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 1297227825Stheravenclass _LIBCPP_VISIBLE unordered_multimap 1298227825Stheraven{ 1299227825Stheravenpublic: 1300227825Stheraven // types 1301227825Stheraven typedef _Key key_type; 1302227825Stheraven typedef _Tp mapped_type; 1303227825Stheraven typedef _Hash hasher; 1304227825Stheraven typedef _Pred key_equal; 1305227825Stheraven typedef _Alloc allocator_type; 1306227825Stheraven typedef pair<const key_type, mapped_type> value_type; 1307227825Stheraven typedef value_type& reference; 1308227825Stheraven typedef const value_type& const_reference; 1309227825Stheraven 1310227825Stheravenprivate: 1311227825Stheraven typedef pair<key_type, mapped_type> __value_type; 1312232924Stheraven typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher; 1313232924Stheraven typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal; 1314227825Stheraven typedef typename allocator_traits<allocator_type>::template 1315227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1316227825Stheraven rebind_alloc<__value_type> 1317227825Stheraven#else 1318227825Stheraven rebind_alloc<__value_type>::other 1319227825Stheraven#endif 1320227825Stheraven __allocator_type; 1321227825Stheraven 1322227825Stheraven typedef __hash_table<__value_type, __hasher, 1323227825Stheraven __key_equal, __allocator_type> __table; 1324227825Stheraven 1325227825Stheraven __table __table_; 1326227825Stheraven 1327227825Stheraven typedef typename __table::__node_traits __node_traits; 1328227825Stheraven typedef typename __table::__node_allocator __node_allocator; 1329227825Stheraven typedef typename __table::__node __node; 1330232924Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 1331232924Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 1332227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 1333227825Stheravenpublic: 1334227825Stheraven typedef typename __alloc_traits::pointer pointer; 1335227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 1336227825Stheraven typedef typename __alloc_traits::size_type size_type; 1337227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 1338227825Stheraven 1339227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 1340227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1341227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1342227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1343227825Stheraven 1344227825Stheraven _LIBCPP_INLINE_VISIBILITY 1345227825Stheraven unordered_multimap() 1346227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1347227825Stheraven {} // = default; 1348227825Stheraven explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1349227825Stheraven const key_equal& __eql = key_equal()); 1350227825Stheraven unordered_multimap(size_type __n, const hasher& __hf, 1351227825Stheraven const key_equal& __eql, 1352227825Stheraven const allocator_type& __a); 1353227825Stheraven template <class _InputIterator> 1354227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last); 1355227825Stheraven template <class _InputIterator> 1356227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1357227825Stheraven size_type __n, const hasher& __hf = hasher(), 1358227825Stheraven const key_equal& __eql = key_equal()); 1359227825Stheraven template <class _InputIterator> 1360227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1361227825Stheraven size_type __n, const hasher& __hf, 1362227825Stheraven const key_equal& __eql, 1363227825Stheraven const allocator_type& __a); 1364227825Stheraven explicit unordered_multimap(const allocator_type& __a); 1365227825Stheraven unordered_multimap(const unordered_multimap& __u); 1366227825Stheraven unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1367227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1368227825Stheraven unordered_multimap(unordered_multimap&& __u) 1369227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1370227825Stheraven unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1371227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1372227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1373227825Stheraven unordered_multimap(initializer_list<value_type> __il); 1374227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1375227825Stheraven const hasher& __hf = hasher(), 1376227825Stheraven const key_equal& __eql = key_equal()); 1377227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1378227825Stheraven const hasher& __hf, const key_equal& __eql, 1379227825Stheraven const allocator_type& __a); 1380227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1381227825Stheraven // ~unordered_multimap() = default; 1382227825Stheraven _LIBCPP_INLINE_VISIBILITY 1383227825Stheraven unordered_multimap& operator=(const unordered_multimap& __u) 1384227825Stheraven { 1385227825Stheraven __table_ = __u.__table_; 1386227825Stheraven return *this; 1387227825Stheraven } 1388227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1389227825Stheraven unordered_multimap& operator=(unordered_multimap&& __u) 1390227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1391227825Stheraven#endif 1392227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1393227825Stheraven unordered_multimap& operator=(initializer_list<value_type> __il); 1394227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1395227825Stheraven 1396227825Stheraven _LIBCPP_INLINE_VISIBILITY 1397227825Stheraven allocator_type get_allocator() const _NOEXCEPT 1398227825Stheraven {return allocator_type(__table_.__node_alloc());} 1399227825Stheraven 1400227825Stheraven _LIBCPP_INLINE_VISIBILITY 1401227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1402227825Stheraven _LIBCPP_INLINE_VISIBILITY 1403227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 1404227825Stheraven _LIBCPP_INLINE_VISIBILITY 1405227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1406227825Stheraven 1407227825Stheraven _LIBCPP_INLINE_VISIBILITY 1408227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 1409227825Stheraven _LIBCPP_INLINE_VISIBILITY 1410227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 1411227825Stheraven _LIBCPP_INLINE_VISIBILITY 1412227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1413227825Stheraven _LIBCPP_INLINE_VISIBILITY 1414227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 1415227825Stheraven _LIBCPP_INLINE_VISIBILITY 1416227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1417227825Stheraven _LIBCPP_INLINE_VISIBILITY 1418227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 1419227825Stheraven 1420227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1421227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1422227825Stheraven 1423241900Sdim template <class... _Args> 1424241900Sdim iterator emplace(_Args&&... __args); 1425227825Stheraven 1426241900Sdim template <class... _Args> 1427241900Sdim iterator emplace_hint(const_iterator __p, _Args&&... __args); 1428227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1429227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1430227825Stheraven _LIBCPP_INLINE_VISIBILITY 1431227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1432227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1433232924Stheraven template <class _Pp, 1434232924Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1435227825Stheraven _LIBCPP_INLINE_VISIBILITY 1436232924Stheraven iterator insert(_Pp&& __x) 1437232924Stheraven {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1438227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1439227825Stheraven _LIBCPP_INLINE_VISIBILITY 1440227825Stheraven iterator insert(const_iterator __p, const value_type& __x) 1441227825Stheraven {return __table_.__insert_multi(__p.__i_, __x);} 1442227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1443232924Stheraven template <class _Pp, 1444232924Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1445227825Stheraven _LIBCPP_INLINE_VISIBILITY 1446232924Stheraven iterator insert(const_iterator __p, _Pp&& __x) 1447232924Stheraven {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1448227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1449227825Stheraven template <class _InputIterator> 1450227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 1451227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1452227825Stheraven _LIBCPP_INLINE_VISIBILITY 1453227825Stheraven void insert(initializer_list<value_type> __il) 1454227825Stheraven {insert(__il.begin(), __il.end());} 1455227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1456227825Stheraven 1457227825Stheraven _LIBCPP_INLINE_VISIBILITY 1458227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1459227825Stheraven _LIBCPP_INLINE_VISIBILITY 1460227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1461227825Stheraven _LIBCPP_INLINE_VISIBILITY 1462227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 1463227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 1464227825Stheraven _LIBCPP_INLINE_VISIBILITY 1465227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 1466227825Stheraven 1467227825Stheraven _LIBCPP_INLINE_VISIBILITY 1468227825Stheraven void swap(unordered_multimap& __u) 1469227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1470227825Stheraven {__table_.swap(__u.__table_);} 1471227825Stheraven 1472227825Stheraven _LIBCPP_INLINE_VISIBILITY 1473227825Stheraven hasher hash_function() const 1474227825Stheraven {return __table_.hash_function().hash_function();} 1475227825Stheraven _LIBCPP_INLINE_VISIBILITY 1476227825Stheraven key_equal key_eq() const 1477227825Stheraven {return __table_.key_eq().key_eq();} 1478227825Stheraven 1479227825Stheraven _LIBCPP_INLINE_VISIBILITY 1480227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 1481227825Stheraven _LIBCPP_INLINE_VISIBILITY 1482227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1483227825Stheraven _LIBCPP_INLINE_VISIBILITY 1484227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1485227825Stheraven _LIBCPP_INLINE_VISIBILITY 1486227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 1487227825Stheraven {return __table_.__equal_range_multi(__k);} 1488227825Stheraven _LIBCPP_INLINE_VISIBILITY 1489227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1490227825Stheraven {return __table_.__equal_range_multi(__k);} 1491227825Stheraven 1492227825Stheraven _LIBCPP_INLINE_VISIBILITY 1493227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1494227825Stheraven _LIBCPP_INLINE_VISIBILITY 1495227825Stheraven size_type max_bucket_count() const _NOEXCEPT 1496227825Stheraven {return __table_.max_bucket_count();} 1497227825Stheraven 1498227825Stheraven _LIBCPP_INLINE_VISIBILITY 1499227825Stheraven size_type bucket_size(size_type __n) const 1500227825Stheraven {return __table_.bucket_size(__n);} 1501227825Stheraven _LIBCPP_INLINE_VISIBILITY 1502227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1503227825Stheraven 1504227825Stheraven _LIBCPP_INLINE_VISIBILITY 1505227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1506227825Stheraven _LIBCPP_INLINE_VISIBILITY 1507227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1508227825Stheraven _LIBCPP_INLINE_VISIBILITY 1509227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1510227825Stheraven _LIBCPP_INLINE_VISIBILITY 1511227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1512227825Stheraven _LIBCPP_INLINE_VISIBILITY 1513227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1514227825Stheraven _LIBCPP_INLINE_VISIBILITY 1515227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1516227825Stheraven 1517227825Stheraven _LIBCPP_INLINE_VISIBILITY 1518227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1519227825Stheraven _LIBCPP_INLINE_VISIBILITY 1520227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1521227825Stheraven _LIBCPP_INLINE_VISIBILITY 1522227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1523227825Stheraven _LIBCPP_INLINE_VISIBILITY 1524227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1525227825Stheraven _LIBCPP_INLINE_VISIBILITY 1526227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1527227825Stheraven 1528227825Stheravenprivate: 1529241900Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1530241900Sdim __node_holder __construct_node(); 1531241900Sdim template <class _A0> 1532241900Sdim typename enable_if 1533241900Sdim < 1534241900Sdim is_constructible<value_type, _A0>::value, 1535241900Sdim __node_holder 1536241900Sdim >::type 1537241900Sdim __construct_node(_A0&& __a0); 1538241900Sdim template <class _A0> 1539241900Sdim typename enable_if 1540241900Sdim < 1541241900Sdim is_constructible<key_type, _A0>::value, 1542241900Sdim __node_holder 1543241900Sdim >::type 1544241900Sdim __construct_node(_A0&& __a0); 1545241900Sdim#ifndef _LIBCPP_HAS_NO_VARIADICS 1546241900Sdim template <class _A0, class _A1, class ..._Args> 1547241900Sdim __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1548241900Sdim#endif // _LIBCPP_HAS_NO_VARIADICS 1549241900Sdim#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1550227825Stheraven}; 1551227825Stheraven 1552227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1553227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1554227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1555227825Stheraven : __table_(__hf, __eql) 1556227825Stheraven{ 1557227825Stheraven __table_.rehash(__n); 1558227825Stheraven} 1559227825Stheraven 1560227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1561227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1562227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1563227825Stheraven const allocator_type& __a) 1564227825Stheraven : __table_(__hf, __eql, __a) 1565227825Stheraven{ 1566227825Stheraven __table_.rehash(__n); 1567227825Stheraven} 1568227825Stheraven 1569227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1570227825Stheraventemplate <class _InputIterator> 1571227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1572227825Stheraven _InputIterator __first, _InputIterator __last) 1573227825Stheraven{ 1574227825Stheraven insert(__first, __last); 1575227825Stheraven} 1576227825Stheraven 1577227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1578227825Stheraventemplate <class _InputIterator> 1579227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1580227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1581227825Stheraven const hasher& __hf, const key_equal& __eql) 1582227825Stheraven : __table_(__hf, __eql) 1583227825Stheraven{ 1584227825Stheraven __table_.rehash(__n); 1585227825Stheraven insert(__first, __last); 1586227825Stheraven} 1587227825Stheraven 1588227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1589227825Stheraventemplate <class _InputIterator> 1590227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1591227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1592227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1593227825Stheraven : __table_(__hf, __eql, __a) 1594227825Stheraven{ 1595227825Stheraven __table_.rehash(__n); 1596227825Stheraven insert(__first, __last); 1597227825Stheraven} 1598227825Stheraven 1599227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1600227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1601227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1602227825Stheraven const allocator_type& __a) 1603227825Stheraven : __table_(__a) 1604227825Stheraven{ 1605227825Stheraven} 1606227825Stheraven 1607227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1608227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1609227825Stheraven const unordered_multimap& __u) 1610227825Stheraven : __table_(__u.__table_) 1611227825Stheraven{ 1612227825Stheraven __table_.rehash(__u.bucket_count()); 1613227825Stheraven insert(__u.begin(), __u.end()); 1614227825Stheraven} 1615227825Stheraven 1616227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1617227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1618227825Stheraven const unordered_multimap& __u, const allocator_type& __a) 1619227825Stheraven : __table_(__u.__table_, __a) 1620227825Stheraven{ 1621227825Stheraven __table_.rehash(__u.bucket_count()); 1622227825Stheraven insert(__u.begin(), __u.end()); 1623227825Stheraven} 1624227825Stheraven 1625227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1626227825Stheraven 1627227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1628227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1629227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1630227825Stheraven unordered_multimap&& __u) 1631227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1632227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1633227825Stheraven{ 1634227825Stheraven} 1635227825Stheraven 1636227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1637227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1638227825Stheraven unordered_multimap&& __u, const allocator_type& __a) 1639227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1640227825Stheraven{ 1641227825Stheraven if (__a != __u.get_allocator()) 1642227825Stheraven { 1643227825Stheraven iterator __i = __u.begin(); 1644227825Stheraven while (__u.size() != 0) 1645227825Stheraven{ 1646227825Stheraven __table_.__insert_multi( 1647227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1648227825Stheraven ); 1649227825Stheraven} 1650227825Stheraven } 1651227825Stheraven} 1652227825Stheraven 1653227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1654227825Stheraven 1655227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1656227825Stheraven 1657227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1658227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1659227825Stheraven initializer_list<value_type> __il) 1660227825Stheraven{ 1661227825Stheraven insert(__il.begin(), __il.end()); 1662227825Stheraven} 1663227825Stheraven 1664227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1665227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1666227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1667227825Stheraven const key_equal& __eql) 1668227825Stheraven : __table_(__hf, __eql) 1669227825Stheraven{ 1670227825Stheraven __table_.rehash(__n); 1671227825Stheraven insert(__il.begin(), __il.end()); 1672227825Stheraven} 1673227825Stheraven 1674227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1675227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1676227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1677227825Stheraven const key_equal& __eql, const allocator_type& __a) 1678227825Stheraven : __table_(__hf, __eql, __a) 1679227825Stheraven{ 1680227825Stheraven __table_.rehash(__n); 1681227825Stheraven insert(__il.begin(), __il.end()); 1682227825Stheraven} 1683227825Stheraven 1684227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1685227825Stheraven 1686227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1687227825Stheraven 1688227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1689227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1690227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1691227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1692227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1693227825Stheraven{ 1694227825Stheraven __table_ = _VSTD::move(__u.__table_); 1695227825Stheraven return *this; 1696227825Stheraven} 1697227825Stheraven 1698227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1699227825Stheraven 1700227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1701227825Stheraven 1702227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1703227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1704227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1705227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1706227825Stheraven initializer_list<value_type> __il) 1707227825Stheraven{ 1708227825Stheraven __table_.__assign_multi(__il.begin(), __il.end()); 1709227825Stheraven return *this; 1710227825Stheraven} 1711227825Stheraven 1712227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1713227825Stheraven 1714227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1715227825Stheraven 1716227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1717227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1718241900Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1719227825Stheraven{ 1720227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1721232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1722241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1723227825Stheraven __h.get_deleter().__first_constructed = true; 1724227825Stheraven __h.get_deleter().__second_constructed = true; 1725227825Stheraven return __h; 1726227825Stheraven} 1727227825Stheraven 1728227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1729241900Sdimtemplate <class _A0> 1730241900Sdimtypename enable_if 1731241900Sdim< 1732241900Sdim is_constructible<pair<const _Key, _Tp>, _A0>::value, 1733241900Sdim typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1734241900Sdim>::type 1735227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1736227825Stheraven{ 1737227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1738232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1739227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1740227825Stheraven _VSTD::forward<_A0>(__a0)); 1741227825Stheraven __h.get_deleter().__first_constructed = true; 1742227825Stheraven __h.get_deleter().__second_constructed = true; 1743227825Stheraven return __h; 1744227825Stheraven} 1745227825Stheraven 1746241900Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1747241900Sdimtemplate <class _A0> 1748241900Sdimtypename enable_if 1749241900Sdim< 1750241900Sdim is_constructible<_Key, _A0>::value, 1751241900Sdim typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1752241900Sdim>::type 1753241900Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1754241900Sdim{ 1755241900Sdim __node_allocator& __na = __table_.__node_alloc(); 1756241900Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1757241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), 1758241900Sdim _VSTD::forward<_A0>(__a0)); 1759241900Sdim __h.get_deleter().__first_constructed = true; 1760241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1761241900Sdim __h.get_deleter().__second_constructed = true; 1762241900Sdim return __h; 1763241900Sdim} 1764241900Sdim 1765227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1766227825Stheraven 1767227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1768241900Sdimtemplate <class _A0, class _A1, class ..._Args> 1769241900Sdimtypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1770241900Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 1771241900Sdim _A0&& __a0, _A1&& __a1, _Args&&... __args) 1772241900Sdim{ 1773241900Sdim __node_allocator& __na = __table_.__node_alloc(); 1774241900Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1775241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1776241900Sdim _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1777241900Sdim _VSTD::forward<_Args>(__args)...); 1778241900Sdim __h.get_deleter().__first_constructed = true; 1779241900Sdim __h.get_deleter().__second_constructed = true; 1780241900Sdim return __h; 1781241900Sdim} 1782241900Sdim 1783241900Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1784241900Sdimtemplate <class... _Args> 1785227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1786241900Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1787227825Stheraven{ 1788241900Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1789227825Stheraven iterator __r = __table_.__node_insert_multi(__h.get()); 1790227825Stheraven __h.release(); 1791227825Stheraven return __r; 1792227825Stheraven} 1793227825Stheraven 1794227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1795241900Sdimtemplate <class... _Args> 1796227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1797227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 1798241900Sdim const_iterator __p, _Args&&... __args) 1799227825Stheraven{ 1800241900Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1801227825Stheraven iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 1802227825Stheraven __h.release(); 1803227825Stheraven return __r; 1804227825Stheraven} 1805227825Stheraven 1806227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1807227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1808227825Stheraven 1809227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1810227825Stheraventemplate <class _InputIterator> 1811227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1812227825Stheravenvoid 1813227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1814227825Stheraven _InputIterator __last) 1815227825Stheraven{ 1816227825Stheraven for (; __first != __last; ++__first) 1817227825Stheraven __table_.__insert_multi(*__first); 1818227825Stheraven} 1819227825Stheraven 1820227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1821227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1822227825Stheravenvoid 1823227825Stheravenswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1824227825Stheraven unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1825227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1826227825Stheraven{ 1827227825Stheraven __x.swap(__y); 1828227825Stheraven} 1829227825Stheraven 1830227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1831227825Stheravenbool 1832227825Stheravenoperator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1833227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1834227825Stheraven{ 1835227825Stheraven if (__x.size() != __y.size()) 1836227825Stheraven return false; 1837227825Stheraven typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1838227825Stheraven const_iterator; 1839227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 1840227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1841227825Stheraven { 1842227825Stheraven _EqRng __xeq = __x.equal_range(__i->first); 1843227825Stheraven _EqRng __yeq = __y.equal_range(__i->first); 1844227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 1845227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 1846227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1847227825Stheraven return false; 1848227825Stheraven __i = __xeq.second; 1849227825Stheraven } 1850227825Stheraven return true; 1851227825Stheraven} 1852227825Stheraven 1853227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1854227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1855227825Stheravenbool 1856227825Stheravenoperator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1857227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1858227825Stheraven{ 1859227825Stheraven return !(__x == __y); 1860227825Stheraven} 1861227825Stheraven 1862227825Stheraven_LIBCPP_END_NAMESPACE_STD 1863227825Stheraven 1864227825Stheraven#endif // _LIBCPP_UNORDERED_MAP 1865