unordered_map revision 253159
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 328253159Stheraventemplate <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value 329232950Stheraven#if __has_feature(is_final) 330232950Stheraven && !__is_final(_Hash) 331232950Stheraven#endif 332232950Stheraven > 333227825Stheravenclass __unordered_map_hasher 334227825Stheraven : private _Hash 335227825Stheraven{ 336227825Stheravenpublic: 337227825Stheraven _LIBCPP_INLINE_VISIBILITY 338227825Stheraven __unordered_map_hasher() 339227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 340227825Stheraven : _Hash() {} 341227825Stheraven _LIBCPP_INLINE_VISIBILITY 342227825Stheraven __unordered_map_hasher(const _Hash& __h) 343227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 344227825Stheraven : _Hash(__h) {} 345227825Stheraven _LIBCPP_INLINE_VISIBILITY 346227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return *this;} 347227825Stheraven _LIBCPP_INLINE_VISIBILITY 348232950Stheraven size_t operator()(const _Cp& __x) const 349253159Stheraven {return static_cast<const _Hash&>(*this)(__x.__cc.first);} 350232950Stheraven _LIBCPP_INLINE_VISIBILITY 351232950Stheraven size_t operator()(const _Key& __x) const 352227825Stheraven {return static_cast<const _Hash&>(*this)(__x);} 353227825Stheraven}; 354227825Stheraven 355253159Stheraventemplate <class _Key, class _Cp, class _Hash> 356253159Stheravenclass __unordered_map_hasher<_Key, _Cp, _Hash, false> 357227825Stheraven{ 358227825Stheraven _Hash __hash_; 359232950Stheraven 360227825Stheravenpublic: 361227825Stheraven _LIBCPP_INLINE_VISIBILITY 362227825Stheraven __unordered_map_hasher() 363227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 364227825Stheraven : __hash_() {} 365227825Stheraven _LIBCPP_INLINE_VISIBILITY 366227825Stheraven __unordered_map_hasher(const _Hash& __h) 367227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 368227825Stheraven : __hash_(__h) {} 369227825Stheraven _LIBCPP_INLINE_VISIBILITY 370227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 371227825Stheraven _LIBCPP_INLINE_VISIBILITY 372232950Stheraven size_t operator()(const _Cp& __x) const 373253159Stheraven {return __hash_(__x.__cc.first);} 374232950Stheraven _LIBCPP_INLINE_VISIBILITY 375232950Stheraven size_t operator()(const _Key& __x) const 376227825Stheraven {return __hash_(__x);} 377227825Stheraven}; 378227825Stheraven 379253159Stheraventemplate <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value 380232950Stheraven#if __has_feature(is_final) 381232950Stheraven && !__is_final(_Pred) 382232950Stheraven#endif 383232950Stheraven > 384227825Stheravenclass __unordered_map_equal 385227825Stheraven : private _Pred 386227825Stheraven{ 387227825Stheravenpublic: 388227825Stheraven _LIBCPP_INLINE_VISIBILITY 389227825Stheraven __unordered_map_equal() 390227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 391227825Stheraven : _Pred() {} 392227825Stheraven _LIBCPP_INLINE_VISIBILITY 393227825Stheraven __unordered_map_equal(const _Pred& __p) 394227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 395227825Stheraven : _Pred(__p) {} 396227825Stheraven _LIBCPP_INLINE_VISIBILITY 397227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return *this;} 398227825Stheraven _LIBCPP_INLINE_VISIBILITY 399232950Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 400253159Stheraven {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);} 401232950Stheraven _LIBCPP_INLINE_VISIBILITY 402232950Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 403253159Stheraven {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);} 404232950Stheraven _LIBCPP_INLINE_VISIBILITY 405232950Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 406253159Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);} 407227825Stheraven}; 408227825Stheraven 409253159Stheraventemplate <class _Key, class _Cp, class _Pred> 410253159Stheravenclass __unordered_map_equal<_Key, _Cp, _Pred, false> 411227825Stheraven{ 412227825Stheraven _Pred __pred_; 413232950Stheraven 414227825Stheravenpublic: 415227825Stheraven _LIBCPP_INLINE_VISIBILITY 416227825Stheraven __unordered_map_equal() 417227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 418227825Stheraven : __pred_() {} 419227825Stheraven _LIBCPP_INLINE_VISIBILITY 420227825Stheraven __unordered_map_equal(const _Pred& __p) 421227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 422227825Stheraven : __pred_(__p) {} 423227825Stheraven _LIBCPP_INLINE_VISIBILITY 424227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 425227825Stheraven _LIBCPP_INLINE_VISIBILITY 426232950Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 427253159Stheraven {return __pred_(__x.__cc.first, __y.__cc.first);} 428232950Stheraven _LIBCPP_INLINE_VISIBILITY 429232950Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 430253159Stheraven {return __pred_(__x.__cc.first, __y);} 431232950Stheraven _LIBCPP_INLINE_VISIBILITY 432232950Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 433253159Stheraven {return __pred_(__x, __y.__cc.first);} 434227825Stheraven}; 435227825Stheraven 436227825Stheraventemplate <class _Alloc> 437227825Stheravenclass __hash_map_node_destructor 438227825Stheraven{ 439227825Stheraven typedef _Alloc allocator_type; 440227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 441227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 442227825Stheravenpublic: 443227825Stheraven typedef typename __alloc_traits::pointer pointer; 444227825Stheravenprivate: 445253159Stheraven typedef typename value_type::value_type::first_type first_type; 446253159Stheraven typedef typename value_type::value_type::second_type second_type; 447227825Stheraven 448227825Stheraven allocator_type& __na_; 449227825Stheraven 450227825Stheraven __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 451227825Stheraven 452227825Stheravenpublic: 453227825Stheraven bool __first_constructed; 454227825Stheraven bool __second_constructed; 455227825Stheraven 456227825Stheraven _LIBCPP_INLINE_VISIBILITY 457227825Stheraven explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 458227825Stheraven : __na_(__na), 459227825Stheraven __first_constructed(false), 460227825Stheraven __second_constructed(false) 461227825Stheraven {} 462227825Stheraven 463227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 464227825Stheraven _LIBCPP_INLINE_VISIBILITY 465227825Stheraven __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 466227825Stheraven _NOEXCEPT 467227825Stheraven : __na_(__x.__na_), 468227825Stheraven __first_constructed(__x.__value_constructed), 469227825Stheraven __second_constructed(__x.__value_constructed) 470227825Stheraven { 471227825Stheraven __x.__value_constructed = false; 472227825Stheraven } 473227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 474227825Stheraven _LIBCPP_INLINE_VISIBILITY 475227825Stheraven __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 476227825Stheraven : __na_(__x.__na_), 477227825Stheraven __first_constructed(__x.__value_constructed), 478227825Stheraven __second_constructed(__x.__value_constructed) 479227825Stheraven { 480227825Stheraven const_cast<bool&>(__x.__value_constructed) = false; 481227825Stheraven } 482227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 483227825Stheraven 484227825Stheraven _LIBCPP_INLINE_VISIBILITY 485227825Stheraven void operator()(pointer __p) _NOEXCEPT 486227825Stheraven { 487227825Stheraven if (__second_constructed) 488253159Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second)); 489227825Stheraven if (__first_constructed) 490253159Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first)); 491227825Stheraven if (__p) 492227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 493227825Stheraven } 494227825Stheraven}; 495227825Stheraven 496227825Stheraventemplate <class _HashIterator> 497249998Sdimclass _LIBCPP_TYPE_VIS __hash_map_iterator 498227825Stheraven{ 499227825Stheraven _HashIterator __i_; 500227825Stheraven 501227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 502253159Stheraven typedef const typename _HashIterator::value_type::value_type::first_type key_type; 503253159Stheraven typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 504227825Stheravenpublic: 505227825Stheraven typedef forward_iterator_tag iterator_category; 506227825Stheraven typedef pair<key_type, mapped_type> value_type; 507227825Stheraven typedef typename _HashIterator::difference_type difference_type; 508227825Stheraven typedef value_type& reference; 509227825Stheraven typedef typename __pointer_traits::template 510227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 511227825Stheraven rebind<value_type> 512227825Stheraven#else 513227825Stheraven rebind<value_type>::other 514227825Stheraven#endif 515227825Stheraven pointer; 516227825Stheraven 517227825Stheraven _LIBCPP_INLINE_VISIBILITY 518227825Stheraven __hash_map_iterator() _NOEXCEPT {} 519227825Stheraven 520227825Stheraven _LIBCPP_INLINE_VISIBILITY 521227825Stheraven __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 522227825Stheraven 523227825Stheraven _LIBCPP_INLINE_VISIBILITY 524253159Stheraven reference operator*() const {return __i_->__cc;} 525227825Stheraven _LIBCPP_INLINE_VISIBILITY 526253159Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 527227825Stheraven 528227825Stheraven _LIBCPP_INLINE_VISIBILITY 529227825Stheraven __hash_map_iterator& operator++() {++__i_; return *this;} 530227825Stheraven _LIBCPP_INLINE_VISIBILITY 531227825Stheraven __hash_map_iterator operator++(int) 532227825Stheraven { 533227825Stheraven __hash_map_iterator __t(*this); 534227825Stheraven ++(*this); 535227825Stheraven return __t; 536227825Stheraven } 537227825Stheraven 538227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 539227825Stheraven bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 540227825Stheraven {return __x.__i_ == __y.__i_;} 541227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 542227825Stheraven bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 543227825Stheraven {return __x.__i_ != __y.__i_;} 544227825Stheraven 545249998Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map; 546249998Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap; 547249998Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator; 548249998Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator; 549249998Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator; 550227825Stheraven}; 551227825Stheraven 552227825Stheraventemplate <class _HashIterator> 553249998Sdimclass _LIBCPP_TYPE_VIS __hash_map_const_iterator 554227825Stheraven{ 555227825Stheraven _HashIterator __i_; 556227825Stheraven 557227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 558253159Stheraven typedef const typename _HashIterator::value_type::value_type::first_type key_type; 559253159Stheraven typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 560227825Stheravenpublic: 561227825Stheraven typedef forward_iterator_tag iterator_category; 562227825Stheraven typedef pair<key_type, mapped_type> value_type; 563227825Stheraven typedef typename _HashIterator::difference_type difference_type; 564227825Stheraven typedef const value_type& reference; 565227825Stheraven typedef typename __pointer_traits::template 566227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 567227825Stheraven rebind<const value_type> 568227825Stheraven#else 569227825Stheraven rebind<const value_type>::other 570227825Stheraven#endif 571227825Stheraven pointer; 572227825Stheraven 573227825Stheraven _LIBCPP_INLINE_VISIBILITY 574227825Stheraven __hash_map_const_iterator() _NOEXCEPT {} 575227825Stheraven 576227825Stheraven _LIBCPP_INLINE_VISIBILITY 577227825Stheraven __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 578227825Stheraven _LIBCPP_INLINE_VISIBILITY 579227825Stheraven __hash_map_const_iterator( 580227825Stheraven __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 581227825Stheraven _NOEXCEPT 582227825Stheraven : __i_(__i.__i_) {} 583227825Stheraven 584227825Stheraven _LIBCPP_INLINE_VISIBILITY 585253159Stheraven reference operator*() const {return __i_->__cc;} 586227825Stheraven _LIBCPP_INLINE_VISIBILITY 587253159Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 588227825Stheraven 589227825Stheraven _LIBCPP_INLINE_VISIBILITY 590227825Stheraven __hash_map_const_iterator& operator++() {++__i_; return *this;} 591227825Stheraven _LIBCPP_INLINE_VISIBILITY 592227825Stheraven __hash_map_const_iterator operator++(int) 593227825Stheraven { 594227825Stheraven __hash_map_const_iterator __t(*this); 595227825Stheraven ++(*this); 596227825Stheraven return __t; 597227825Stheraven } 598227825Stheraven 599227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 600227825Stheraven bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 601227825Stheraven {return __x.__i_ == __y.__i_;} 602227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 603227825Stheraven bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 604227825Stheraven {return __x.__i_ != __y.__i_;} 605227825Stheraven 606249998Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map; 607249998Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap; 608249998Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator; 609249998Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator; 610227825Stheraven}; 611227825Stheraven 612227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 613227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 614249998Sdimclass _LIBCPP_TYPE_VIS unordered_map 615227825Stheraven{ 616227825Stheravenpublic: 617227825Stheraven // types 618227825Stheraven typedef _Key key_type; 619227825Stheraven typedef _Tp mapped_type; 620227825Stheraven typedef _Hash hasher; 621227825Stheraven typedef _Pred key_equal; 622227825Stheraven typedef _Alloc allocator_type; 623227825Stheraven typedef pair<const key_type, mapped_type> value_type; 624253159Stheraven typedef pair<key_type, mapped_type> __nc_value_type; 625227825Stheraven typedef value_type& reference; 626227825Stheraven typedef const value_type& const_reference; 627227825Stheraven 628227825Stheravenprivate: 629253159Stheraven#if __cplusplus >= 201103L 630253159Stheraven union __value_type 631253159Stheraven { 632253159Stheraven typedef typename unordered_map::value_type value_type; 633253159Stheraven typedef typename unordered_map::__nc_value_type __nc_value_type; 634253159Stheraven value_type __cc; 635253159Stheraven __nc_value_type __nc; 636253159Stheraven 637253159Stheraven template <class ..._Args> 638253159Stheraven __value_type(_Args&& ...__args) 639253159Stheraven : __cc(std::forward<_Args>(__args)...) {} 640253159Stheraven 641253159Stheraven __value_type(const __value_type& __v) 642253159Stheraven : __cc(std::move(__v.__cc)) {} 643253159Stheraven 644253159Stheraven __value_type(__value_type&& __v) 645253159Stheraven : __nc(std::move(__v.__nc)) {} 646253159Stheraven 647253159Stheraven __value_type& operator=(const __value_type& __v) 648253159Stheraven {__nc = __v.__cc; return *this;} 649253159Stheraven 650253159Stheraven __value_type& operator=(__value_type&& __v) 651253159Stheraven {__nc = std::move(__v.__nc); return *this;} 652253159Stheraven 653253159Stheraven ~__value_type() {__cc.~value_type();} 654253159Stheraven }; 655253159Stheraven#else 656253159Stheraven struct __value_type 657253159Stheraven { 658253159Stheraven typedef typename unordered_map::value_type value_type; 659253159Stheraven value_type __cc; 660253159Stheraven 661253159Stheraven __value_type() {} 662253159Stheraven 663253159Stheraven template <class _A0> 664253159Stheraven __value_type(const _A0& __a0) 665253159Stheraven : __cc(__a0) {} 666253159Stheraven 667253159Stheraven template <class _A0, class _A1> 668253159Stheraven __value_type(const _A0& __a0, const _A1& __a1) 669253159Stheraven : __cc(__a0, __a1) {} 670253159Stheraven }; 671253159Stheraven#endif 672253159Stheraven typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 673253159Stheraven typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 674227825Stheraven typedef typename allocator_traits<allocator_type>::template 675227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 676227825Stheraven rebind_alloc<__value_type> 677227825Stheraven#else 678227825Stheraven rebind_alloc<__value_type>::other 679227825Stheraven#endif 680227825Stheraven __allocator_type; 681227825Stheraven 682227825Stheraven typedef __hash_table<__value_type, __hasher, 683227825Stheraven __key_equal, __allocator_type> __table; 684227825Stheraven 685227825Stheraven __table __table_; 686227825Stheraven 687227825Stheraven typedef typename __table::__node_pointer __node_pointer; 688227825Stheraven typedef typename __table::__node_const_pointer __node_const_pointer; 689227825Stheraven typedef typename __table::__node_traits __node_traits; 690227825Stheraven typedef typename __table::__node_allocator __node_allocator; 691227825Stheraven typedef typename __table::__node __node; 692232950Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 693232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 694227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 695227825Stheravenpublic: 696227825Stheraven typedef typename __alloc_traits::pointer pointer; 697227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 698227825Stheraven typedef typename __alloc_traits::size_type size_type; 699227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 700227825Stheraven 701227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 702227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 703227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 704227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 705227825Stheraven 706227825Stheraven _LIBCPP_INLINE_VISIBILITY 707227825Stheraven unordered_map() 708227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 709227825Stheraven {} // = default; 710227825Stheraven explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 711227825Stheraven const key_equal& __eql = key_equal()); 712227825Stheraven unordered_map(size_type __n, const hasher& __hf, 713227825Stheraven const key_equal& __eql, 714227825Stheraven const allocator_type& __a); 715227825Stheraven template <class _InputIterator> 716227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last); 717227825Stheraven template <class _InputIterator> 718227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 719227825Stheraven size_type __n, const hasher& __hf = hasher(), 720227825Stheraven const key_equal& __eql = key_equal()); 721227825Stheraven template <class _InputIterator> 722227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 723227825Stheraven size_type __n, const hasher& __hf, 724227825Stheraven const key_equal& __eql, 725227825Stheraven const allocator_type& __a); 726227825Stheraven explicit unordered_map(const allocator_type& __a); 727227825Stheraven unordered_map(const unordered_map& __u); 728227825Stheraven unordered_map(const unordered_map& __u, const allocator_type& __a); 729227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 730227825Stheraven unordered_map(unordered_map&& __u) 731227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 732227825Stheraven unordered_map(unordered_map&& __u, const allocator_type& __a); 733227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 734227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 735227825Stheraven unordered_map(initializer_list<value_type> __il); 736227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 737227825Stheraven const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 738227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 739227825Stheraven const hasher& __hf, const key_equal& __eql, 740227825Stheraven const allocator_type& __a); 741227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 742227825Stheraven // ~unordered_map() = default; 743227825Stheraven _LIBCPP_INLINE_VISIBILITY 744227825Stheraven unordered_map& operator=(const unordered_map& __u) 745227825Stheraven { 746253159Stheraven#if __cplusplus >= 201103L 747227825Stheraven __table_ = __u.__table_; 748253159Stheraven#else 749253159Stheraven __table_.clear(); 750253159Stheraven __table_.hash_function() = __u.__table_.hash_function(); 751253159Stheraven __table_.key_eq() = __u.__table_.key_eq(); 752253159Stheraven __table_.max_load_factor() = __u.__table_.max_load_factor(); 753253159Stheraven __table_.__copy_assign_alloc(__u.__table_); 754253159Stheraven insert(__u.begin(), __u.end()); 755253159Stheraven#endif 756227825Stheraven return *this; 757227825Stheraven } 758227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 759227825Stheraven unordered_map& operator=(unordered_map&& __u) 760227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 761227825Stheraven#endif 762227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 763227825Stheraven unordered_map& operator=(initializer_list<value_type> __il); 764227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 765227825Stheraven 766227825Stheraven _LIBCPP_INLINE_VISIBILITY 767227825Stheraven allocator_type get_allocator() const _NOEXCEPT 768227825Stheraven {return allocator_type(__table_.__node_alloc());} 769227825Stheraven 770227825Stheraven _LIBCPP_INLINE_VISIBILITY 771227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 772227825Stheraven _LIBCPP_INLINE_VISIBILITY 773227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 774227825Stheraven _LIBCPP_INLINE_VISIBILITY 775227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 776227825Stheraven 777227825Stheraven _LIBCPP_INLINE_VISIBILITY 778227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 779227825Stheraven _LIBCPP_INLINE_VISIBILITY 780227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 781227825Stheraven _LIBCPP_INLINE_VISIBILITY 782227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 783227825Stheraven _LIBCPP_INLINE_VISIBILITY 784227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 785227825Stheraven _LIBCPP_INLINE_VISIBILITY 786227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 787227825Stheraven _LIBCPP_INLINE_VISIBILITY 788227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 789227825Stheraven 790227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 791227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 792227825Stheraven 793241903Sdim template <class... _Args> 794241903Sdim pair<iterator, bool> emplace(_Args&&... __args); 795227825Stheraven 796241903Sdim template <class... _Args> 797227825Stheraven _LIBCPP_INLINE_VISIBILITY 798241903Sdim iterator emplace_hint(const_iterator, _Args&&... __args) 799241903Sdim {return emplace(_VSTD::forward<_Args>(__args)...).first;} 800227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 801227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 802227825Stheraven _LIBCPP_INLINE_VISIBILITY 803227825Stheraven pair<iterator, bool> insert(const value_type& __x) 804227825Stheraven {return __table_.__insert_unique(__x);} 805227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 806232950Stheraven template <class _Pp, 807232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 808227825Stheraven _LIBCPP_INLINE_VISIBILITY 809232950Stheraven pair<iterator, bool> insert(_Pp&& __x) 810232950Stheraven {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 811227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 812227825Stheraven _LIBCPP_INLINE_VISIBILITY 813227825Stheraven iterator insert(const_iterator, const value_type& __x) 814227825Stheraven {return insert(__x).first;} 815227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 816232950Stheraven template <class _Pp, 817232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 818227825Stheraven _LIBCPP_INLINE_VISIBILITY 819232950Stheraven iterator insert(const_iterator, _Pp&& __x) 820232950Stheraven {return insert(_VSTD::forward<_Pp>(__x)).first;} 821227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 822227825Stheraven template <class _InputIterator> 823227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 824227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 825227825Stheraven _LIBCPP_INLINE_VISIBILITY 826227825Stheraven void insert(initializer_list<value_type> __il) 827227825Stheraven {insert(__il.begin(), __il.end());} 828227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 829227825Stheraven 830227825Stheraven _LIBCPP_INLINE_VISIBILITY 831227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 832227825Stheraven _LIBCPP_INLINE_VISIBILITY 833227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 834227825Stheraven _LIBCPP_INLINE_VISIBILITY 835227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 836227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 837227825Stheraven _LIBCPP_INLINE_VISIBILITY 838227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 839227825Stheraven 840227825Stheraven _LIBCPP_INLINE_VISIBILITY 841227825Stheraven void swap(unordered_map& __u) 842227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 843227825Stheraven {__table_.swap(__u.__table_);} 844227825Stheraven 845227825Stheraven _LIBCPP_INLINE_VISIBILITY 846227825Stheraven hasher hash_function() const 847227825Stheraven {return __table_.hash_function().hash_function();} 848227825Stheraven _LIBCPP_INLINE_VISIBILITY 849227825Stheraven key_equal key_eq() const 850227825Stheraven {return __table_.key_eq().key_eq();} 851227825Stheraven 852227825Stheraven _LIBCPP_INLINE_VISIBILITY 853227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 854227825Stheraven _LIBCPP_INLINE_VISIBILITY 855227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 856227825Stheraven _LIBCPP_INLINE_VISIBILITY 857227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 858227825Stheraven _LIBCPP_INLINE_VISIBILITY 859227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 860227825Stheraven {return __table_.__equal_range_unique(__k);} 861227825Stheraven _LIBCPP_INLINE_VISIBILITY 862227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 863227825Stheraven {return __table_.__equal_range_unique(__k);} 864227825Stheraven 865227825Stheraven mapped_type& operator[](const key_type& __k); 866227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 867227825Stheraven mapped_type& operator[](key_type&& __k); 868227825Stheraven#endif 869227825Stheraven 870227825Stheraven mapped_type& at(const key_type& __k); 871227825Stheraven const mapped_type& at(const key_type& __k) const; 872227825Stheraven 873227825Stheraven _LIBCPP_INLINE_VISIBILITY 874227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 875227825Stheraven _LIBCPP_INLINE_VISIBILITY 876227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 877227825Stheraven 878227825Stheraven _LIBCPP_INLINE_VISIBILITY 879227825Stheraven size_type bucket_size(size_type __n) const 880227825Stheraven {return __table_.bucket_size(__n);} 881227825Stheraven _LIBCPP_INLINE_VISIBILITY 882227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 883227825Stheraven 884227825Stheraven _LIBCPP_INLINE_VISIBILITY 885227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 886227825Stheraven _LIBCPP_INLINE_VISIBILITY 887227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 888227825Stheraven _LIBCPP_INLINE_VISIBILITY 889227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 890227825Stheraven _LIBCPP_INLINE_VISIBILITY 891227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 892227825Stheraven _LIBCPP_INLINE_VISIBILITY 893227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 894227825Stheraven _LIBCPP_INLINE_VISIBILITY 895227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 896227825Stheraven 897227825Stheraven _LIBCPP_INLINE_VISIBILITY 898227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 899227825Stheraven _LIBCPP_INLINE_VISIBILITY 900227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 901227825Stheraven _LIBCPP_INLINE_VISIBILITY 902227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 903227825Stheraven _LIBCPP_INLINE_VISIBILITY 904227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 905227825Stheraven _LIBCPP_INLINE_VISIBILITY 906227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 907227825Stheraven 908227825Stheravenprivate: 909227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 910241903Sdim __node_holder __construct_node(); 911241903Sdim template <class _A0> 912253159Stheraven __node_holder 913241903Sdim __construct_node(_A0&& __a0); 914253159Stheraven __node_holder __construct_node_with_key(key_type&& __k); 915227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 916241903Sdim template <class _A0, class _A1, class ..._Args> 917241903Sdim __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 918227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 919253159Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 920253159Stheraven __node_holder __construct_node_with_key(const key_type& __k); 921227825Stheraven}; 922227825Stheraven 923227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 924227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 925227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 926227825Stheraven : __table_(__hf, __eql) 927227825Stheraven{ 928227825Stheraven __table_.rehash(__n); 929227825Stheraven} 930227825Stheraven 931227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 932227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 933227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 934227825Stheraven const allocator_type& __a) 935227825Stheraven : __table_(__hf, __eql, __a) 936227825Stheraven{ 937227825Stheraven __table_.rehash(__n); 938227825Stheraven} 939227825Stheraven 940227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 941227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 942227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 943227825Stheraven const allocator_type& __a) 944227825Stheraven : __table_(__a) 945227825Stheraven{ 946227825Stheraven} 947227825Stheraven 948227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 949227825Stheraventemplate <class _InputIterator> 950227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 951227825Stheraven _InputIterator __first, _InputIterator __last) 952227825Stheraven{ 953227825Stheraven insert(__first, __last); 954227825Stheraven} 955227825Stheraven 956227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 957227825Stheraventemplate <class _InputIterator> 958227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 959227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 960227825Stheraven const hasher& __hf, const key_equal& __eql) 961227825Stheraven : __table_(__hf, __eql) 962227825Stheraven{ 963227825Stheraven __table_.rehash(__n); 964227825Stheraven insert(__first, __last); 965227825Stheraven} 966227825Stheraven 967227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 968227825Stheraventemplate <class _InputIterator> 969227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 970227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 971227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 972227825Stheraven : __table_(__hf, __eql, __a) 973227825Stheraven{ 974227825Stheraven __table_.rehash(__n); 975227825Stheraven insert(__first, __last); 976227825Stheraven} 977227825Stheraven 978227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 979227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 980227825Stheraven const unordered_map& __u) 981227825Stheraven : __table_(__u.__table_) 982227825Stheraven{ 983227825Stheraven __table_.rehash(__u.bucket_count()); 984227825Stheraven insert(__u.begin(), __u.end()); 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, const allocator_type& __a) 990227825Stheraven : __table_(__u.__table_, __a) 991227825Stheraven{ 992227825Stheraven __table_.rehash(__u.bucket_count()); 993227825Stheraven insert(__u.begin(), __u.end()); 994227825Stheraven} 995227825Stheraven 996227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 997227825Stheraven 998227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 999227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1000227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1001227825Stheraven unordered_map&& __u) 1002227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1003227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1004227825Stheraven{ 1005227825Stheraven} 1006227825Stheraven 1007227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1008227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1009227825Stheraven unordered_map&& __u, const allocator_type& __a) 1010227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1011227825Stheraven{ 1012227825Stheraven if (__a != __u.get_allocator()) 1013227825Stheraven { 1014227825Stheraven iterator __i = __u.begin(); 1015227825Stheraven while (__u.size() != 0) 1016227825Stheraven __table_.__insert_unique( 1017227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1018227825Stheraven ); 1019227825Stheraven } 1020227825Stheraven} 1021227825Stheraven 1022227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1023227825Stheraven 1024227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1025227825Stheraven 1026227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1027227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1028227825Stheraven initializer_list<value_type> __il) 1029227825Stheraven{ 1030227825Stheraven insert(__il.begin(), __il.end()); 1031227825Stheraven} 1032227825Stheraven 1033227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1034227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1035227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1036227825Stheraven const key_equal& __eql) 1037227825Stheraven : __table_(__hf, __eql) 1038227825Stheraven{ 1039227825Stheraven __table_.rehash(__n); 1040227825Stheraven insert(__il.begin(), __il.end()); 1041227825Stheraven} 1042227825Stheraven 1043227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1044227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1045227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1046227825Stheraven const key_equal& __eql, const allocator_type& __a) 1047227825Stheraven : __table_(__hf, __eql, __a) 1048227825Stheraven{ 1049227825Stheraven __table_.rehash(__n); 1050227825Stheraven insert(__il.begin(), __il.end()); 1051227825Stheraven} 1052227825Stheraven 1053227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1054227825Stheraven 1055227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1056227825Stheraven 1057227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1058227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1059227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1060227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1061227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1062227825Stheraven{ 1063227825Stheraven __table_ = _VSTD::move(__u.__table_); 1064227825Stheraven return *this; 1065227825Stheraven} 1066227825Stheraven 1067227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1068227825Stheraven 1069227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1070227825Stheraven 1071227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1072227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1073227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1074227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1075227825Stheraven initializer_list<value_type> __il) 1076227825Stheraven{ 1077227825Stheraven __table_.__assign_unique(__il.begin(), __il.end()); 1078227825Stheraven return *this; 1079227825Stheraven} 1080227825Stheraven 1081227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1082227825Stheraven 1083227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1084227825Stheraven 1085227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1086227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1087241903Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1088227825Stheraven{ 1089227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1090232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1091241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1092227825Stheraven __h.get_deleter().__first_constructed = true; 1093227825Stheraven __h.get_deleter().__second_constructed = true; 1094227825Stheraven return __h; 1095227825Stheraven} 1096227825Stheraven 1097227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1098241903Sdimtemplate <class _A0> 1099253159Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1100227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1101227825Stheraven{ 1102227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1103232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1104227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1105227825Stheraven _VSTD::forward<_A0>(__a0)); 1106227825Stheraven __h.get_deleter().__first_constructed = true; 1107227825Stheraven __h.get_deleter().__second_constructed = true; 1108227825Stheraven return __h; 1109227825Stheraven} 1110227825Stheraven 1111241903Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1112253159Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1113253159Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k) 1114241903Sdim{ 1115241903Sdim __node_allocator& __na = __table_.__node_alloc(); 1116241903Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1117253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k)); 1118241903Sdim __h.get_deleter().__first_constructed = true; 1119253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1120241903Sdim __h.get_deleter().__second_constructed = true; 1121253159Stheraven return _VSTD::move(__h); 1122241903Sdim} 1123241903Sdim 1124227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1125227825Stheraven 1126227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1127241903Sdimtemplate <class _A0, class _A1, class ..._Args> 1128241903Sdimtypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1129241903Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1130241903Sdim _A1&& __a1, 1131241903Sdim _Args&&... __args) 1132241903Sdim{ 1133241903Sdim __node_allocator& __na = __table_.__node_alloc(); 1134241903Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1135241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1136241903Sdim _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1137241903Sdim _VSTD::forward<_Args>(__args)...); 1138241903Sdim __h.get_deleter().__first_constructed = true; 1139241903Sdim __h.get_deleter().__second_constructed = true; 1140241903Sdim return __h; 1141241903Sdim} 1142241903Sdim 1143241903Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1144241903Sdimtemplate <class... _Args> 1145227825Stheravenpair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1146241903Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1147227825Stheraven{ 1148241903Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1149227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1150227825Stheraven if (__r.second) 1151227825Stheraven __h.release(); 1152227825Stheraven return __r; 1153227825Stheraven} 1154227825Stheraven 1155227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1156253159Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1157227825Stheraven 1158227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1159227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1160253159Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1161227825Stheraven{ 1162227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1163232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1164253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1165227825Stheraven __h.get_deleter().__first_constructed = true; 1166253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1167227825Stheraven __h.get_deleter().__second_constructed = true; 1168227825Stheraven return _VSTD::move(__h); 1169227825Stheraven} 1170227825Stheraven 1171227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1172227825Stheraventemplate <class _InputIterator> 1173227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1174227825Stheravenvoid 1175227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1176227825Stheraven _InputIterator __last) 1177227825Stheraven{ 1178227825Stheraven for (; __first != __last; ++__first) 1179227825Stheraven __table_.__insert_unique(*__first); 1180227825Stheraven} 1181227825Stheraven 1182227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1183227825Stheraven_Tp& 1184227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1185227825Stheraven{ 1186227825Stheraven iterator __i = find(__k); 1187227825Stheraven if (__i != end()) 1188227825Stheraven return __i->second; 1189253159Stheraven __node_holder __h = __construct_node_with_key(__k); 1190227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1191227825Stheraven __h.release(); 1192227825Stheraven return __r.first->second; 1193227825Stheraven} 1194227825Stheraven 1195227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1196227825Stheraven 1197227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1198227825Stheraven_Tp& 1199227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1200227825Stheraven{ 1201227825Stheraven iterator __i = find(__k); 1202227825Stheraven if (__i != end()) 1203227825Stheraven return __i->second; 1204253159Stheraven __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); 1205227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1206227825Stheraven __h.release(); 1207227825Stheraven return __r.first->second; 1208227825Stheraven} 1209227825Stheraven 1210227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1211227825Stheraven 1212227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1213227825Stheraven_Tp& 1214227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1215227825Stheraven{ 1216227825Stheraven iterator __i = find(__k); 1217227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1218227825Stheraven if (__i == end()) 1219227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1220227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1221227825Stheraven return __i->second; 1222227825Stheraven} 1223227825Stheraven 1224227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1225227825Stheravenconst _Tp& 1226227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1227227825Stheraven{ 1228227825Stheraven const_iterator __i = find(__k); 1229227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1230227825Stheraven if (__i == end()) 1231227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1232227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1233227825Stheraven return __i->second; 1234227825Stheraven} 1235227825Stheraven 1236227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1237227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1238227825Stheravenvoid 1239227825Stheravenswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1240227825Stheraven unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1241227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1242227825Stheraven{ 1243227825Stheraven __x.swap(__y); 1244227825Stheraven} 1245227825Stheraven 1246227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1247227825Stheravenbool 1248227825Stheravenoperator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1249227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1250227825Stheraven{ 1251227825Stheraven if (__x.size() != __y.size()) 1252227825Stheraven return false; 1253227825Stheraven typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1254227825Stheraven const_iterator; 1255227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1256227825Stheraven __i != __ex; ++__i) 1257227825Stheraven { 1258227825Stheraven const_iterator __j = __y.find(__i->first); 1259227825Stheraven if (__j == __ey || !(*__i == *__j)) 1260227825Stheraven return false; 1261227825Stheraven } 1262227825Stheraven return true; 1263227825Stheraven} 1264227825Stheraven 1265227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1266227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1267227825Stheravenbool 1268227825Stheravenoperator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1269227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1270227825Stheraven{ 1271227825Stheraven return !(__x == __y); 1272227825Stheraven} 1273227825Stheraven 1274227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1275227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 1276249998Sdimclass _LIBCPP_TYPE_VIS unordered_multimap 1277227825Stheraven{ 1278227825Stheravenpublic: 1279227825Stheraven // types 1280227825Stheraven typedef _Key key_type; 1281227825Stheraven typedef _Tp mapped_type; 1282227825Stheraven typedef _Hash hasher; 1283227825Stheraven typedef _Pred key_equal; 1284227825Stheraven typedef _Alloc allocator_type; 1285227825Stheraven typedef pair<const key_type, mapped_type> value_type; 1286253159Stheraven typedef pair<key_type, mapped_type> __nc_value_type; 1287227825Stheraven typedef value_type& reference; 1288227825Stheraven typedef const value_type& const_reference; 1289227825Stheraven 1290227825Stheravenprivate: 1291253159Stheraven#if __cplusplus >= 201103L 1292253159Stheraven union __value_type 1293253159Stheraven { 1294253159Stheraven typedef typename unordered_multimap::value_type value_type; 1295253159Stheraven typedef typename unordered_multimap::__nc_value_type __nc_value_type; 1296253159Stheraven value_type __cc; 1297253159Stheraven __nc_value_type __nc; 1298253159Stheraven 1299253159Stheraven template <class ..._Args> 1300253159Stheraven __value_type(_Args&& ...__args) 1301253159Stheraven : __cc(std::forward<_Args>(__args)...) {} 1302253159Stheraven 1303253159Stheraven __value_type(const __value_type& __v) 1304253159Stheraven : __cc(std::move(__v.__cc)) {} 1305253159Stheraven 1306253159Stheraven __value_type(__value_type&& __v) 1307253159Stheraven : __nc(std::move(__v.__nc)) {} 1308253159Stheraven 1309253159Stheraven __value_type& operator=(const __value_type& __v) 1310253159Stheraven {__nc = __v.__cc; return *this;} 1311253159Stheraven 1312253159Stheraven __value_type& operator=(__value_type&& __v) 1313253159Stheraven {__nc = std::move(__v.__nc); return *this;} 1314253159Stheraven 1315253159Stheraven ~__value_type() {__cc.~value_type();} 1316253159Stheraven }; 1317253159Stheraven#else 1318253159Stheraven struct __value_type 1319253159Stheraven { 1320253159Stheraven typedef typename unordered_multimap::value_type value_type; 1321253159Stheraven value_type __cc; 1322253159Stheraven 1323253159Stheraven __value_type() {} 1324253159Stheraven 1325253159Stheraven template <class _A0> 1326253159Stheraven __value_type(const _A0& __a0) 1327253159Stheraven : __cc(__a0) {} 1328253159Stheraven 1329253159Stheraven template <class _A0, class _A1> 1330253159Stheraven __value_type(const _A0& __a0, const _A1& __a1) 1331253159Stheraven : __cc(__a0, __a1) {} 1332253159Stheraven }; 1333253159Stheraven#endif 1334253159Stheraven typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 1335253159Stheraven typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 1336227825Stheraven typedef typename allocator_traits<allocator_type>::template 1337227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1338227825Stheraven rebind_alloc<__value_type> 1339227825Stheraven#else 1340227825Stheraven rebind_alloc<__value_type>::other 1341227825Stheraven#endif 1342227825Stheraven __allocator_type; 1343227825Stheraven 1344227825Stheraven typedef __hash_table<__value_type, __hasher, 1345227825Stheraven __key_equal, __allocator_type> __table; 1346227825Stheraven 1347227825Stheraven __table __table_; 1348227825Stheraven 1349227825Stheraven typedef typename __table::__node_traits __node_traits; 1350227825Stheraven typedef typename __table::__node_allocator __node_allocator; 1351227825Stheraven typedef typename __table::__node __node; 1352232950Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 1353232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 1354227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 1355227825Stheravenpublic: 1356227825Stheraven typedef typename __alloc_traits::pointer pointer; 1357227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 1358227825Stheraven typedef typename __alloc_traits::size_type size_type; 1359227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 1360227825Stheraven 1361227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 1362227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1363227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1364227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1365227825Stheraven 1366227825Stheraven _LIBCPP_INLINE_VISIBILITY 1367227825Stheraven unordered_multimap() 1368227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1369227825Stheraven {} // = default; 1370227825Stheraven explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1371227825Stheraven const key_equal& __eql = key_equal()); 1372227825Stheraven unordered_multimap(size_type __n, const hasher& __hf, 1373227825Stheraven const key_equal& __eql, 1374227825Stheraven const allocator_type& __a); 1375227825Stheraven template <class _InputIterator> 1376227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last); 1377227825Stheraven template <class _InputIterator> 1378227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1379227825Stheraven size_type __n, const hasher& __hf = hasher(), 1380227825Stheraven const key_equal& __eql = key_equal()); 1381227825Stheraven template <class _InputIterator> 1382227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1383227825Stheraven size_type __n, const hasher& __hf, 1384227825Stheraven const key_equal& __eql, 1385227825Stheraven const allocator_type& __a); 1386227825Stheraven explicit unordered_multimap(const allocator_type& __a); 1387227825Stheraven unordered_multimap(const unordered_multimap& __u); 1388227825Stheraven unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1389227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1390227825Stheraven unordered_multimap(unordered_multimap&& __u) 1391227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1392227825Stheraven unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1393227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1394227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1395227825Stheraven unordered_multimap(initializer_list<value_type> __il); 1396227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1397227825Stheraven const hasher& __hf = hasher(), 1398227825Stheraven const key_equal& __eql = key_equal()); 1399227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1400227825Stheraven const hasher& __hf, const key_equal& __eql, 1401227825Stheraven const allocator_type& __a); 1402227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1403227825Stheraven // ~unordered_multimap() = default; 1404227825Stheraven _LIBCPP_INLINE_VISIBILITY 1405227825Stheraven unordered_multimap& operator=(const unordered_multimap& __u) 1406227825Stheraven { 1407253159Stheraven#if __cplusplus >= 201103L 1408227825Stheraven __table_ = __u.__table_; 1409253159Stheraven#else 1410253159Stheraven __table_.clear(); 1411253159Stheraven __table_.hash_function() = __u.__table_.hash_function(); 1412253159Stheraven __table_.key_eq() = __u.__table_.key_eq(); 1413253159Stheraven __table_.max_load_factor() = __u.__table_.max_load_factor(); 1414253159Stheraven __table_.__copy_assign_alloc(__u.__table_); 1415253159Stheraven insert(__u.begin(), __u.end()); 1416253159Stheraven#endif 1417227825Stheraven return *this; 1418227825Stheraven } 1419227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1420227825Stheraven unordered_multimap& operator=(unordered_multimap&& __u) 1421227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1422227825Stheraven#endif 1423227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1424227825Stheraven unordered_multimap& operator=(initializer_list<value_type> __il); 1425227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1426227825Stheraven 1427227825Stheraven _LIBCPP_INLINE_VISIBILITY 1428227825Stheraven allocator_type get_allocator() const _NOEXCEPT 1429227825Stheraven {return allocator_type(__table_.__node_alloc());} 1430227825Stheraven 1431227825Stheraven _LIBCPP_INLINE_VISIBILITY 1432227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1433227825Stheraven _LIBCPP_INLINE_VISIBILITY 1434227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 1435227825Stheraven _LIBCPP_INLINE_VISIBILITY 1436227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1437227825Stheraven 1438227825Stheraven _LIBCPP_INLINE_VISIBILITY 1439227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 1440227825Stheraven _LIBCPP_INLINE_VISIBILITY 1441227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 1442227825Stheraven _LIBCPP_INLINE_VISIBILITY 1443227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1444227825Stheraven _LIBCPP_INLINE_VISIBILITY 1445227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 1446227825Stheraven _LIBCPP_INLINE_VISIBILITY 1447227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1448227825Stheraven _LIBCPP_INLINE_VISIBILITY 1449227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 1450227825Stheraven 1451227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1452227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1453227825Stheraven 1454241903Sdim template <class... _Args> 1455241903Sdim iterator emplace(_Args&&... __args); 1456227825Stheraven 1457241903Sdim template <class... _Args> 1458241903Sdim iterator emplace_hint(const_iterator __p, _Args&&... __args); 1459227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1460227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1461227825Stheraven _LIBCPP_INLINE_VISIBILITY 1462227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1463227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1464232950Stheraven template <class _Pp, 1465232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1466227825Stheraven _LIBCPP_INLINE_VISIBILITY 1467232950Stheraven iterator insert(_Pp&& __x) 1468232950Stheraven {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1469227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1470227825Stheraven _LIBCPP_INLINE_VISIBILITY 1471227825Stheraven iterator insert(const_iterator __p, const value_type& __x) 1472227825Stheraven {return __table_.__insert_multi(__p.__i_, __x);} 1473227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1474232950Stheraven template <class _Pp, 1475232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1476227825Stheraven _LIBCPP_INLINE_VISIBILITY 1477232950Stheraven iterator insert(const_iterator __p, _Pp&& __x) 1478232950Stheraven {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1479227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1480227825Stheraven template <class _InputIterator> 1481227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 1482227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1483227825Stheraven _LIBCPP_INLINE_VISIBILITY 1484227825Stheraven void insert(initializer_list<value_type> __il) 1485227825Stheraven {insert(__il.begin(), __il.end());} 1486227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1487227825Stheraven 1488227825Stheraven _LIBCPP_INLINE_VISIBILITY 1489227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1490227825Stheraven _LIBCPP_INLINE_VISIBILITY 1491227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1492227825Stheraven _LIBCPP_INLINE_VISIBILITY 1493227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 1494227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 1495227825Stheraven _LIBCPP_INLINE_VISIBILITY 1496227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 1497227825Stheraven 1498227825Stheraven _LIBCPP_INLINE_VISIBILITY 1499227825Stheraven void swap(unordered_multimap& __u) 1500227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1501227825Stheraven {__table_.swap(__u.__table_);} 1502227825Stheraven 1503227825Stheraven _LIBCPP_INLINE_VISIBILITY 1504227825Stheraven hasher hash_function() const 1505227825Stheraven {return __table_.hash_function().hash_function();} 1506227825Stheraven _LIBCPP_INLINE_VISIBILITY 1507227825Stheraven key_equal key_eq() const 1508227825Stheraven {return __table_.key_eq().key_eq();} 1509227825Stheraven 1510227825Stheraven _LIBCPP_INLINE_VISIBILITY 1511227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 1512227825Stheraven _LIBCPP_INLINE_VISIBILITY 1513227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1514227825Stheraven _LIBCPP_INLINE_VISIBILITY 1515227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1516227825Stheraven _LIBCPP_INLINE_VISIBILITY 1517227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 1518227825Stheraven {return __table_.__equal_range_multi(__k);} 1519227825Stheraven _LIBCPP_INLINE_VISIBILITY 1520227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1521227825Stheraven {return __table_.__equal_range_multi(__k);} 1522227825Stheraven 1523227825Stheraven _LIBCPP_INLINE_VISIBILITY 1524227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1525227825Stheraven _LIBCPP_INLINE_VISIBILITY 1526227825Stheraven size_type max_bucket_count() const _NOEXCEPT 1527227825Stheraven {return __table_.max_bucket_count();} 1528227825Stheraven 1529227825Stheraven _LIBCPP_INLINE_VISIBILITY 1530227825Stheraven size_type bucket_size(size_type __n) const 1531227825Stheraven {return __table_.bucket_size(__n);} 1532227825Stheraven _LIBCPP_INLINE_VISIBILITY 1533227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1534227825Stheraven 1535227825Stheraven _LIBCPP_INLINE_VISIBILITY 1536227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1537227825Stheraven _LIBCPP_INLINE_VISIBILITY 1538227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1539227825Stheraven _LIBCPP_INLINE_VISIBILITY 1540227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1541227825Stheraven _LIBCPP_INLINE_VISIBILITY 1542227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1543227825Stheraven _LIBCPP_INLINE_VISIBILITY 1544227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1545227825Stheraven _LIBCPP_INLINE_VISIBILITY 1546227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1547227825Stheraven 1548227825Stheraven _LIBCPP_INLINE_VISIBILITY 1549227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1550227825Stheraven _LIBCPP_INLINE_VISIBILITY 1551227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1552227825Stheraven _LIBCPP_INLINE_VISIBILITY 1553227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1554227825Stheraven _LIBCPP_INLINE_VISIBILITY 1555227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1556227825Stheraven _LIBCPP_INLINE_VISIBILITY 1557227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1558227825Stheraven 1559227825Stheravenprivate: 1560241903Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1561241903Sdim __node_holder __construct_node(); 1562241903Sdim template <class _A0> 1563253159Stheraven __node_holder 1564241903Sdim __construct_node(_A0&& __a0); 1565241903Sdim#ifndef _LIBCPP_HAS_NO_VARIADICS 1566241903Sdim template <class _A0, class _A1, class ..._Args> 1567241903Sdim __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1568241903Sdim#endif // _LIBCPP_HAS_NO_VARIADICS 1569241903Sdim#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1570227825Stheraven}; 1571227825Stheraven 1572227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1573227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1574227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1575227825Stheraven : __table_(__hf, __eql) 1576227825Stheraven{ 1577227825Stheraven __table_.rehash(__n); 1578227825Stheraven} 1579227825Stheraven 1580227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1581227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1582227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1583227825Stheraven const allocator_type& __a) 1584227825Stheraven : __table_(__hf, __eql, __a) 1585227825Stheraven{ 1586227825Stheraven __table_.rehash(__n); 1587227825Stheraven} 1588227825Stheraven 1589227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1590227825Stheraventemplate <class _InputIterator> 1591227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1592227825Stheraven _InputIterator __first, _InputIterator __last) 1593227825Stheraven{ 1594227825Stheraven insert(__first, __last); 1595227825Stheraven} 1596227825Stheraven 1597227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1598227825Stheraventemplate <class _InputIterator> 1599227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1600227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1601227825Stheraven const hasher& __hf, const key_equal& __eql) 1602227825Stheraven : __table_(__hf, __eql) 1603227825Stheraven{ 1604227825Stheraven __table_.rehash(__n); 1605227825Stheraven insert(__first, __last); 1606227825Stheraven} 1607227825Stheraven 1608227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1609227825Stheraventemplate <class _InputIterator> 1610227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1611227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1612227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1613227825Stheraven : __table_(__hf, __eql, __a) 1614227825Stheraven{ 1615227825Stheraven __table_.rehash(__n); 1616227825Stheraven insert(__first, __last); 1617227825Stheraven} 1618227825Stheraven 1619227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1620227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1621227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1622227825Stheraven const allocator_type& __a) 1623227825Stheraven : __table_(__a) 1624227825Stheraven{ 1625227825Stheraven} 1626227825Stheraven 1627227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1628227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1629227825Stheraven const unordered_multimap& __u) 1630227825Stheraven : __table_(__u.__table_) 1631227825Stheraven{ 1632227825Stheraven __table_.rehash(__u.bucket_count()); 1633227825Stheraven insert(__u.begin(), __u.end()); 1634227825Stheraven} 1635227825Stheraven 1636227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1637227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1638227825Stheraven const unordered_multimap& __u, const allocator_type& __a) 1639227825Stheraven : __table_(__u.__table_, __a) 1640227825Stheraven{ 1641227825Stheraven __table_.rehash(__u.bucket_count()); 1642227825Stheraven insert(__u.begin(), __u.end()); 1643227825Stheraven} 1644227825Stheraven 1645227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1646227825Stheraven 1647227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1648227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1649227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1650227825Stheraven unordered_multimap&& __u) 1651227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1652227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1653227825Stheraven{ 1654227825Stheraven} 1655227825Stheraven 1656227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1657227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1658227825Stheraven unordered_multimap&& __u, const allocator_type& __a) 1659227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1660227825Stheraven{ 1661227825Stheraven if (__a != __u.get_allocator()) 1662227825Stheraven { 1663227825Stheraven iterator __i = __u.begin(); 1664227825Stheraven while (__u.size() != 0) 1665227825Stheraven{ 1666227825Stheraven __table_.__insert_multi( 1667227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1668227825Stheraven ); 1669227825Stheraven} 1670227825Stheraven } 1671227825Stheraven} 1672227825Stheraven 1673227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1674227825Stheraven 1675227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1676227825Stheraven 1677227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1678227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1679227825Stheraven initializer_list<value_type> __il) 1680227825Stheraven{ 1681227825Stheraven insert(__il.begin(), __il.end()); 1682227825Stheraven} 1683227825Stheraven 1684227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1685227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1686227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1687227825Stheraven const key_equal& __eql) 1688227825Stheraven : __table_(__hf, __eql) 1689227825Stheraven{ 1690227825Stheraven __table_.rehash(__n); 1691227825Stheraven insert(__il.begin(), __il.end()); 1692227825Stheraven} 1693227825Stheraven 1694227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1695227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1696227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1697227825Stheraven const key_equal& __eql, const allocator_type& __a) 1698227825Stheraven : __table_(__hf, __eql, __a) 1699227825Stheraven{ 1700227825Stheraven __table_.rehash(__n); 1701227825Stheraven insert(__il.begin(), __il.end()); 1702227825Stheraven} 1703227825Stheraven 1704227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1705227825Stheraven 1706227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1707227825Stheraven 1708227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1709227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1710227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1711227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1712227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1713227825Stheraven{ 1714227825Stheraven __table_ = _VSTD::move(__u.__table_); 1715227825Stheraven return *this; 1716227825Stheraven} 1717227825Stheraven 1718227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1719227825Stheraven 1720227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1721227825Stheraven 1722227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1723227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1724227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1725227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1726227825Stheraven initializer_list<value_type> __il) 1727227825Stheraven{ 1728227825Stheraven __table_.__assign_multi(__il.begin(), __il.end()); 1729227825Stheraven return *this; 1730227825Stheraven} 1731227825Stheraven 1732227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1733227825Stheraven 1734227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1735227825Stheraven 1736227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1737227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1738241903Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1739227825Stheraven{ 1740227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1741232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1742241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1743227825Stheraven __h.get_deleter().__first_constructed = true; 1744227825Stheraven __h.get_deleter().__second_constructed = true; 1745227825Stheraven return __h; 1746227825Stheraven} 1747227825Stheraven 1748227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1749241903Sdimtemplate <class _A0> 1750253159Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1751227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1752227825Stheraven{ 1753227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1754232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1755227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1756227825Stheraven _VSTD::forward<_A0>(__a0)); 1757227825Stheraven __h.get_deleter().__first_constructed = true; 1758227825Stheraven __h.get_deleter().__second_constructed = true; 1759227825Stheraven return __h; 1760227825Stheraven} 1761227825Stheraven 1762227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1763227825Stheraven 1764227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1765241903Sdimtemplate <class _A0, class _A1, class ..._Args> 1766241903Sdimtypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1767241903Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 1768241903Sdim _A0&& __a0, _A1&& __a1, _Args&&... __args) 1769241903Sdim{ 1770241903Sdim __node_allocator& __na = __table_.__node_alloc(); 1771241903Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1772241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1773241903Sdim _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1774241903Sdim _VSTD::forward<_Args>(__args)...); 1775241903Sdim __h.get_deleter().__first_constructed = true; 1776241903Sdim __h.get_deleter().__second_constructed = true; 1777241903Sdim return __h; 1778241903Sdim} 1779241903Sdim 1780241903Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1781241903Sdimtemplate <class... _Args> 1782227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1783241903Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1784227825Stheraven{ 1785241903Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1786227825Stheraven iterator __r = __table_.__node_insert_multi(__h.get()); 1787227825Stheraven __h.release(); 1788227825Stheraven return __r; 1789227825Stheraven} 1790227825Stheraven 1791227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1792241903Sdimtemplate <class... _Args> 1793227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1794227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 1795241903Sdim const_iterator __p, _Args&&... __args) 1796227825Stheraven{ 1797241903Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1798227825Stheraven iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 1799227825Stheraven __h.release(); 1800227825Stheraven return __r; 1801227825Stheraven} 1802227825Stheraven 1803227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1804227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1805227825Stheraven 1806227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1807227825Stheraventemplate <class _InputIterator> 1808227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1809227825Stheravenvoid 1810227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1811227825Stheraven _InputIterator __last) 1812227825Stheraven{ 1813227825Stheraven for (; __first != __last; ++__first) 1814227825Stheraven __table_.__insert_multi(*__first); 1815227825Stheraven} 1816227825Stheraven 1817227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1818227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1819227825Stheravenvoid 1820227825Stheravenswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1821227825Stheraven unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1822227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1823227825Stheraven{ 1824227825Stheraven __x.swap(__y); 1825227825Stheraven} 1826227825Stheraven 1827227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1828227825Stheravenbool 1829227825Stheravenoperator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1830227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1831227825Stheraven{ 1832227825Stheraven if (__x.size() != __y.size()) 1833227825Stheraven return false; 1834227825Stheraven typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1835227825Stheraven const_iterator; 1836227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 1837227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1838227825Stheraven { 1839227825Stheraven _EqRng __xeq = __x.equal_range(__i->first); 1840227825Stheraven _EqRng __yeq = __y.equal_range(__i->first); 1841227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 1842227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 1843227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1844227825Stheraven return false; 1845227825Stheraven __i = __xeq.second; 1846227825Stheraven } 1847227825Stheraven return true; 1848227825Stheraven} 1849227825Stheraven 1850227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1851227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1852227825Stheravenbool 1853227825Stheravenoperator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1854227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1855227825Stheraven{ 1856227825Stheraven return !(__x == __y); 1857227825Stheraven} 1858227825Stheraven 1859227825Stheraven_LIBCPP_END_NAMESPACE_STD 1860227825Stheraven 1861227825Stheraven#endif // _LIBCPP_UNORDERED_MAP 1862