unordered_map revision 278724
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()); 72262801Sdim unordered_map(size_type n, const allocator_type& a) 73262801Sdim : unordered_map(n, hasher(), key_equal(), a) {} // C++14 74262801Sdim unordered_map(size_type n, const hasher& hf, const allocator_type& a) 75262801Sdim : unordered_map(n, hf, key_equal(), a) {} // C++14 76262801Sdim template <class InputIterator> 77262801Sdim unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 78262801Sdim : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14 79262801Sdim template <class InputIterator> 80262801Sdim unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, 81262801Sdim const allocator_type& a) 82262801Sdim : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14 83262801Sdim unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a) 84262801Sdim : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 85262801Sdim unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf, 86262801Sdim const allocator_type& a) 87262801Sdim : unordered_map(il, n, hf, key_equal(), a) {} // C++14 88227825Stheraven ~unordered_map(); 89227825Stheraven unordered_map& operator=(const unordered_map&); 90227825Stheraven unordered_map& operator=(unordered_map&&) 91227825Stheraven noexcept( 92227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 93227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 94227825Stheraven is_nothrow_move_assignable<hasher>::value && 95227825Stheraven is_nothrow_move_assignable<key_equal>::value); 96227825Stheraven unordered_map& operator=(initializer_list<value_type>); 97227825Stheraven 98227825Stheraven allocator_type get_allocator() const noexcept; 99227825Stheraven 100227825Stheraven bool empty() const noexcept; 101227825Stheraven size_type size() const noexcept; 102227825Stheraven size_type max_size() const noexcept; 103227825Stheraven 104227825Stheraven iterator begin() noexcept; 105227825Stheraven iterator end() noexcept; 106227825Stheraven const_iterator begin() const noexcept; 107227825Stheraven const_iterator end() const noexcept; 108227825Stheraven const_iterator cbegin() const noexcept; 109227825Stheraven const_iterator cend() const noexcept; 110227825Stheraven 111227825Stheraven template <class... Args> 112227825Stheraven pair<iterator, bool> emplace(Args&&... args); 113227825Stheraven template <class... Args> 114227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 115227825Stheraven pair<iterator, bool> insert(const value_type& obj); 116227825Stheraven template <class P> 117227825Stheraven pair<iterator, bool> insert(P&& obj); 118227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 119227825Stheraven template <class P> 120227825Stheraven iterator insert(const_iterator hint, P&& obj); 121227825Stheraven template <class InputIterator> 122227825Stheraven void insert(InputIterator first, InputIterator last); 123227825Stheraven void insert(initializer_list<value_type>); 124227825Stheraven 125227825Stheraven iterator erase(const_iterator position); 126227825Stheraven size_type erase(const key_type& k); 127227825Stheraven iterator erase(const_iterator first, const_iterator last); 128227825Stheraven void clear() noexcept; 129227825Stheraven 130227825Stheraven void swap(unordered_map&) 131227825Stheraven noexcept( 132227825Stheraven (!allocator_type::propagate_on_container_swap::value || 133227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 134227825Stheraven __is_nothrow_swappable<hasher>::value && 135227825Stheraven __is_nothrow_swappable<key_equal>::value); 136227825Stheraven 137227825Stheraven hasher hash_function() const; 138227825Stheraven key_equal key_eq() const; 139227825Stheraven 140227825Stheraven iterator find(const key_type& k); 141227825Stheraven const_iterator find(const key_type& k) const; 142227825Stheraven size_type count(const key_type& k) const; 143227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 144227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 145227825Stheraven 146227825Stheraven mapped_type& operator[](const key_type& k); 147227825Stheraven mapped_type& operator[](key_type&& k); 148227825Stheraven 149227825Stheraven mapped_type& at(const key_type& k); 150227825Stheraven const mapped_type& at(const key_type& k) const; 151227825Stheraven 152227825Stheraven size_type bucket_count() const noexcept; 153227825Stheraven size_type max_bucket_count() const noexcept; 154227825Stheraven 155227825Stheraven size_type bucket_size(size_type n) const; 156227825Stheraven size_type bucket(const key_type& k) const; 157227825Stheraven 158227825Stheraven local_iterator begin(size_type n); 159227825Stheraven local_iterator end(size_type n); 160227825Stheraven const_local_iterator begin(size_type n) const; 161227825Stheraven const_local_iterator end(size_type n) const; 162227825Stheraven const_local_iterator cbegin(size_type n) const; 163227825Stheraven const_local_iterator cend(size_type n) const; 164227825Stheraven 165227825Stheraven float load_factor() const noexcept; 166227825Stheraven float max_load_factor() const noexcept; 167227825Stheraven void max_load_factor(float z); 168227825Stheraven void rehash(size_type n); 169227825Stheraven void reserve(size_type n); 170227825Stheraven}; 171227825Stheraven 172227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 173227825Stheraven void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x, 174227825Stheraven unordered_map<Key, T, Hash, Pred, Alloc>& y) 175227825Stheraven noexcept(noexcept(x.swap(y))); 176227825Stheraven 177227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 178227825Stheraven bool 179227825Stheraven operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 180227825Stheraven const unordered_map<Key, T, Hash, Pred, Alloc>& y); 181227825Stheraven 182227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 183227825Stheraven bool 184227825Stheraven operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 185227825Stheraven const unordered_map<Key, T, Hash, Pred, Alloc>& y); 186227825Stheraven 187227825Stheraventemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 188227825Stheraven class Alloc = allocator<pair<const Key, T>>> 189227825Stheravenclass unordered_multimap 190227825Stheraven{ 191227825Stheravenpublic: 192227825Stheraven // types 193227825Stheraven typedef Key key_type; 194227825Stheraven typedef T mapped_type; 195227825Stheraven typedef Hash hasher; 196227825Stheraven typedef Pred key_equal; 197227825Stheraven typedef Alloc allocator_type; 198227825Stheraven typedef pair<const key_type, mapped_type> value_type; 199227825Stheraven typedef value_type& reference; 200227825Stheraven typedef const value_type& const_reference; 201227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 202227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 203227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 204227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 205227825Stheraven 206227825Stheraven typedef /unspecified/ iterator; 207227825Stheraven typedef /unspecified/ const_iterator; 208227825Stheraven typedef /unspecified/ local_iterator; 209227825Stheraven typedef /unspecified/ const_local_iterator; 210227825Stheraven 211227825Stheraven unordered_multimap() 212227825Stheraven noexcept( 213227825Stheraven is_nothrow_default_constructible<hasher>::value && 214227825Stheraven is_nothrow_default_constructible<key_equal>::value && 215227825Stheraven is_nothrow_default_constructible<allocator_type>::value); 216227825Stheraven explicit unordered_multimap(size_type n, const hasher& hf = hasher(), 217227825Stheraven const key_equal& eql = key_equal(), 218227825Stheraven const allocator_type& a = allocator_type()); 219227825Stheraven template <class InputIterator> 220227825Stheraven unordered_multimap(InputIterator f, InputIterator l, 221227825Stheraven size_type n = 0, const hasher& hf = hasher(), 222227825Stheraven const key_equal& eql = key_equal(), 223227825Stheraven const allocator_type& a = allocator_type()); 224227825Stheraven explicit unordered_multimap(const allocator_type&); 225227825Stheraven unordered_multimap(const unordered_multimap&); 226227825Stheraven unordered_multimap(const unordered_multimap&, const Allocator&); 227227825Stheraven unordered_multimap(unordered_multimap&&) 228227825Stheraven noexcept( 229227825Stheraven is_nothrow_move_constructible<hasher>::value && 230227825Stheraven is_nothrow_move_constructible<key_equal>::value && 231227825Stheraven is_nothrow_move_constructible<allocator_type>::value); 232227825Stheraven unordered_multimap(unordered_multimap&&, const Allocator&); 233227825Stheraven unordered_multimap(initializer_list<value_type>, size_type n = 0, 234227825Stheraven const hasher& hf = hasher(), const key_equal& eql = key_equal(), 235227825Stheraven const allocator_type& a = allocator_type()); 236262801Sdim unordered_multimap(size_type n, const allocator_type& a) 237262801Sdim : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14 238262801Sdim unordered_multimap(size_type n, const hasher& hf, const allocator_type& a) 239262801Sdim : unordered_multimap(n, hf, key_equal(), a) {} // C++14 240262801Sdim template <class InputIterator> 241262801Sdim unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 242262801Sdim : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14 243262801Sdim template <class InputIterator> 244262801Sdim unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, 245262801Sdim const allocator_type& a) 246262801Sdim : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14 247262801Sdim unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a) 248262801Sdim : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 249262801Sdim unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf, 250262801Sdim const allocator_type& a) 251262801Sdim : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14 252227825Stheraven ~unordered_multimap(); 253227825Stheraven unordered_multimap& operator=(const unordered_multimap&); 254227825Stheraven unordered_multimap& operator=(unordered_multimap&&) 255227825Stheraven noexcept( 256227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 257227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 258227825Stheraven is_nothrow_move_assignable<hasher>::value && 259227825Stheraven is_nothrow_move_assignable<key_equal>::value); 260227825Stheraven unordered_multimap& operator=(initializer_list<value_type>); 261227825Stheraven 262227825Stheraven allocator_type get_allocator() const noexcept; 263227825Stheraven 264227825Stheraven bool empty() const noexcept; 265227825Stheraven size_type size() const noexcept; 266227825Stheraven size_type max_size() const noexcept; 267227825Stheraven 268227825Stheraven iterator begin() noexcept; 269227825Stheraven iterator end() noexcept; 270227825Stheraven const_iterator begin() const noexcept; 271227825Stheraven const_iterator end() const noexcept; 272227825Stheraven const_iterator cbegin() const noexcept; 273227825Stheraven const_iterator cend() const noexcept; 274227825Stheraven 275227825Stheraven template <class... Args> 276227825Stheraven iterator emplace(Args&&... args); 277227825Stheraven template <class... Args> 278227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 279227825Stheraven iterator insert(const value_type& obj); 280227825Stheraven template <class P> 281227825Stheraven iterator insert(P&& obj); 282227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 283227825Stheraven template <class P> 284227825Stheraven iterator insert(const_iterator hint, P&& obj); 285227825Stheraven template <class InputIterator> 286227825Stheraven void insert(InputIterator first, InputIterator last); 287227825Stheraven void insert(initializer_list<value_type>); 288227825Stheraven 289227825Stheraven iterator erase(const_iterator position); 290227825Stheraven size_type erase(const key_type& k); 291227825Stheraven iterator erase(const_iterator first, const_iterator last); 292227825Stheraven void clear() noexcept; 293227825Stheraven 294227825Stheraven void swap(unordered_multimap&) 295227825Stheraven noexcept( 296227825Stheraven (!allocator_type::propagate_on_container_swap::value || 297227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 298227825Stheraven __is_nothrow_swappable<hasher>::value && 299227825Stheraven __is_nothrow_swappable<key_equal>::value); 300227825Stheraven 301227825Stheraven hasher hash_function() const; 302227825Stheraven key_equal key_eq() const; 303227825Stheraven 304227825Stheraven iterator find(const key_type& k); 305227825Stheraven const_iterator find(const key_type& k) const; 306227825Stheraven size_type count(const key_type& k) const; 307227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 308227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 309227825Stheraven 310227825Stheraven size_type bucket_count() const noexcept; 311227825Stheraven size_type max_bucket_count() const noexcept; 312227825Stheraven 313227825Stheraven size_type bucket_size(size_type n) const; 314227825Stheraven size_type bucket(const key_type& k) const; 315227825Stheraven 316227825Stheraven local_iterator begin(size_type n); 317227825Stheraven local_iterator end(size_type n); 318227825Stheraven const_local_iterator begin(size_type n) const; 319227825Stheraven const_local_iterator end(size_type n) const; 320227825Stheraven const_local_iterator cbegin(size_type n) const; 321227825Stheraven const_local_iterator cend(size_type n) const; 322227825Stheraven 323227825Stheraven float load_factor() const noexcept; 324227825Stheraven float max_load_factor() const noexcept; 325227825Stheraven void max_load_factor(float z); 326227825Stheraven void rehash(size_type n); 327227825Stheraven void reserve(size_type n); 328227825Stheraven}; 329227825Stheraven 330227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 331227825Stheraven void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 332227825Stheraven unordered_multimap<Key, T, Hash, Pred, Alloc>& y) 333227825Stheraven noexcept(noexcept(x.swap(y))); 334227825Stheraven 335227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 336227825Stheraven bool 337227825Stheraven operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 338227825Stheraven const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 339227825Stheraven 340227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 341227825Stheraven bool 342227825Stheraven operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 343227825Stheraven const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 344227825Stheraven 345227825Stheraven} // std 346227825Stheraven 347227825Stheraven*/ 348227825Stheraven 349227825Stheraven#include <__config> 350227825Stheraven#include <__hash_table> 351227825Stheraven#include <functional> 352227825Stheraven#include <stdexcept> 353227825Stheraven 354278724Sdim#include <__debug> 355278724Sdim 356227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 357227825Stheraven#pragma GCC system_header 358227825Stheraven#endif 359227825Stheraven 360227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 361227825Stheraven 362253159Stheraventemplate <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value 363232950Stheraven#if __has_feature(is_final) 364232950Stheraven && !__is_final(_Hash) 365232950Stheraven#endif 366232950Stheraven > 367227825Stheravenclass __unordered_map_hasher 368227825Stheraven : private _Hash 369227825Stheraven{ 370227825Stheravenpublic: 371227825Stheraven _LIBCPP_INLINE_VISIBILITY 372227825Stheraven __unordered_map_hasher() 373227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 374227825Stheraven : _Hash() {} 375227825Stheraven _LIBCPP_INLINE_VISIBILITY 376227825Stheraven __unordered_map_hasher(const _Hash& __h) 377227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 378227825Stheraven : _Hash(__h) {} 379227825Stheraven _LIBCPP_INLINE_VISIBILITY 380227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return *this;} 381227825Stheraven _LIBCPP_INLINE_VISIBILITY 382232950Stheraven size_t operator()(const _Cp& __x) const 383253159Stheraven {return static_cast<const _Hash&>(*this)(__x.__cc.first);} 384232950Stheraven _LIBCPP_INLINE_VISIBILITY 385232950Stheraven size_t operator()(const _Key& __x) const 386227825Stheraven {return static_cast<const _Hash&>(*this)(__x);} 387227825Stheraven}; 388227825Stheraven 389253159Stheraventemplate <class _Key, class _Cp, class _Hash> 390253159Stheravenclass __unordered_map_hasher<_Key, _Cp, _Hash, false> 391227825Stheraven{ 392227825Stheraven _Hash __hash_; 393232950Stheraven 394227825Stheravenpublic: 395227825Stheraven _LIBCPP_INLINE_VISIBILITY 396227825Stheraven __unordered_map_hasher() 397227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 398227825Stheraven : __hash_() {} 399227825Stheraven _LIBCPP_INLINE_VISIBILITY 400227825Stheraven __unordered_map_hasher(const _Hash& __h) 401227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 402227825Stheraven : __hash_(__h) {} 403227825Stheraven _LIBCPP_INLINE_VISIBILITY 404227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 405227825Stheraven _LIBCPP_INLINE_VISIBILITY 406232950Stheraven size_t operator()(const _Cp& __x) const 407253159Stheraven {return __hash_(__x.__cc.first);} 408232950Stheraven _LIBCPP_INLINE_VISIBILITY 409232950Stheraven size_t operator()(const _Key& __x) const 410227825Stheraven {return __hash_(__x);} 411227825Stheraven}; 412227825Stheraven 413253159Stheraventemplate <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value 414232950Stheraven#if __has_feature(is_final) 415232950Stheraven && !__is_final(_Pred) 416232950Stheraven#endif 417232950Stheraven > 418227825Stheravenclass __unordered_map_equal 419227825Stheraven : private _Pred 420227825Stheraven{ 421227825Stheravenpublic: 422227825Stheraven _LIBCPP_INLINE_VISIBILITY 423227825Stheraven __unordered_map_equal() 424227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 425227825Stheraven : _Pred() {} 426227825Stheraven _LIBCPP_INLINE_VISIBILITY 427227825Stheraven __unordered_map_equal(const _Pred& __p) 428227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 429227825Stheraven : _Pred(__p) {} 430227825Stheraven _LIBCPP_INLINE_VISIBILITY 431227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return *this;} 432227825Stheraven _LIBCPP_INLINE_VISIBILITY 433232950Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 434253159Stheraven {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);} 435232950Stheraven _LIBCPP_INLINE_VISIBILITY 436232950Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 437253159Stheraven {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);} 438232950Stheraven _LIBCPP_INLINE_VISIBILITY 439232950Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 440253159Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);} 441227825Stheraven}; 442227825Stheraven 443253159Stheraventemplate <class _Key, class _Cp, class _Pred> 444253159Stheravenclass __unordered_map_equal<_Key, _Cp, _Pred, false> 445227825Stheraven{ 446227825Stheraven _Pred __pred_; 447232950Stheraven 448227825Stheravenpublic: 449227825Stheraven _LIBCPP_INLINE_VISIBILITY 450227825Stheraven __unordered_map_equal() 451227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 452227825Stheraven : __pred_() {} 453227825Stheraven _LIBCPP_INLINE_VISIBILITY 454227825Stheraven __unordered_map_equal(const _Pred& __p) 455227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 456227825Stheraven : __pred_(__p) {} 457227825Stheraven _LIBCPP_INLINE_VISIBILITY 458227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 459227825Stheraven _LIBCPP_INLINE_VISIBILITY 460232950Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 461253159Stheraven {return __pred_(__x.__cc.first, __y.__cc.first);} 462232950Stheraven _LIBCPP_INLINE_VISIBILITY 463232950Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 464253159Stheraven {return __pred_(__x.__cc.first, __y);} 465232950Stheraven _LIBCPP_INLINE_VISIBILITY 466232950Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 467253159Stheraven {return __pred_(__x, __y.__cc.first);} 468227825Stheraven}; 469227825Stheraven 470227825Stheraventemplate <class _Alloc> 471227825Stheravenclass __hash_map_node_destructor 472227825Stheraven{ 473227825Stheraven typedef _Alloc allocator_type; 474227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 475227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 476227825Stheravenpublic: 477227825Stheraven typedef typename __alloc_traits::pointer pointer; 478227825Stheravenprivate: 479253159Stheraven typedef typename value_type::value_type::first_type first_type; 480253159Stheraven typedef typename value_type::value_type::second_type second_type; 481227825Stheraven 482227825Stheraven allocator_type& __na_; 483227825Stheraven 484227825Stheraven __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 485227825Stheraven 486227825Stheravenpublic: 487227825Stheraven bool __first_constructed; 488227825Stheraven bool __second_constructed; 489227825Stheraven 490227825Stheraven _LIBCPP_INLINE_VISIBILITY 491227825Stheraven explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 492227825Stheraven : __na_(__na), 493227825Stheraven __first_constructed(false), 494227825Stheraven __second_constructed(false) 495227825Stheraven {} 496227825Stheraven 497227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 498227825Stheraven _LIBCPP_INLINE_VISIBILITY 499227825Stheraven __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 500227825Stheraven _NOEXCEPT 501227825Stheraven : __na_(__x.__na_), 502227825Stheraven __first_constructed(__x.__value_constructed), 503227825Stheraven __second_constructed(__x.__value_constructed) 504227825Stheraven { 505227825Stheraven __x.__value_constructed = false; 506227825Stheraven } 507227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 508227825Stheraven _LIBCPP_INLINE_VISIBILITY 509227825Stheraven __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 510227825Stheraven : __na_(__x.__na_), 511227825Stheraven __first_constructed(__x.__value_constructed), 512227825Stheraven __second_constructed(__x.__value_constructed) 513227825Stheraven { 514227825Stheraven const_cast<bool&>(__x.__value_constructed) = false; 515227825Stheraven } 516227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 517227825Stheraven 518227825Stheraven _LIBCPP_INLINE_VISIBILITY 519227825Stheraven void operator()(pointer __p) _NOEXCEPT 520227825Stheraven { 521227825Stheraven if (__second_constructed) 522253159Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second)); 523227825Stheraven if (__first_constructed) 524253159Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first)); 525227825Stheraven if (__p) 526227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 527227825Stheraven } 528227825Stheraven}; 529227825Stheraven 530262801Sdim#if __cplusplus >= 201103L 531262801Sdim 532262801Sdimtemplate <class _Key, class _Tp> 533262801Sdimunion __hash_value_type 534262801Sdim{ 535262801Sdim typedef _Key key_type; 536262801Sdim typedef _Tp mapped_type; 537262801Sdim typedef pair<const key_type, mapped_type> value_type; 538262801Sdim typedef pair<key_type, mapped_type> __nc_value_type; 539262801Sdim 540262801Sdim value_type __cc; 541262801Sdim __nc_value_type __nc; 542262801Sdim 543262801Sdim template <class ..._Args> 544262801Sdim _LIBCPP_INLINE_VISIBILITY 545262801Sdim __hash_value_type(_Args&& ...__args) 546262801Sdim : __cc(std::forward<_Args>(__args)...) {} 547262801Sdim 548262801Sdim _LIBCPP_INLINE_VISIBILITY 549262801Sdim __hash_value_type(const __hash_value_type& __v) 550262801Sdim : __cc(__v.__cc) {} 551262801Sdim 552262801Sdim _LIBCPP_INLINE_VISIBILITY 553262801Sdim __hash_value_type(__hash_value_type&& __v) 554262801Sdim : __nc(std::move(__v.__nc)) {} 555262801Sdim 556262801Sdim _LIBCPP_INLINE_VISIBILITY 557262801Sdim __hash_value_type& operator=(const __hash_value_type& __v) 558262801Sdim {__nc = __v.__cc; return *this;} 559262801Sdim 560262801Sdim _LIBCPP_INLINE_VISIBILITY 561262801Sdim __hash_value_type& operator=(__hash_value_type&& __v) 562262801Sdim {__nc = std::move(__v.__nc); return *this;} 563262801Sdim 564262801Sdim _LIBCPP_INLINE_VISIBILITY 565262801Sdim ~__hash_value_type() {__cc.~value_type();} 566262801Sdim}; 567262801Sdim 568262801Sdim#else 569262801Sdim 570262801Sdimtemplate <class _Key, class _Tp> 571262801Sdimstruct __hash_value_type 572262801Sdim{ 573262801Sdim typedef _Key key_type; 574262801Sdim typedef _Tp mapped_type; 575262801Sdim typedef pair<const key_type, mapped_type> value_type; 576262801Sdim 577262801Sdim value_type __cc; 578262801Sdim 579262801Sdim _LIBCPP_INLINE_VISIBILITY 580262801Sdim __hash_value_type() {} 581262801Sdim 582262801Sdim template <class _A0> 583262801Sdim _LIBCPP_INLINE_VISIBILITY 584262801Sdim __hash_value_type(const _A0& __a0) 585262801Sdim : __cc(__a0) {} 586262801Sdim 587262801Sdim template <class _A0, class _A1> 588262801Sdim _LIBCPP_INLINE_VISIBILITY 589262801Sdim __hash_value_type(const _A0& __a0, const _A1& __a1) 590262801Sdim : __cc(__a0, __a1) {} 591262801Sdim}; 592262801Sdim 593262801Sdim#endif 594262801Sdim 595227825Stheraventemplate <class _HashIterator> 596262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator 597227825Stheraven{ 598227825Stheraven _HashIterator __i_; 599227825Stheraven 600227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 601253159Stheraven typedef const typename _HashIterator::value_type::value_type::first_type key_type; 602253159Stheraven typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 603227825Stheravenpublic: 604227825Stheraven typedef forward_iterator_tag iterator_category; 605227825Stheraven typedef pair<key_type, mapped_type> value_type; 606227825Stheraven typedef typename _HashIterator::difference_type difference_type; 607227825Stheraven typedef value_type& reference; 608227825Stheraven typedef typename __pointer_traits::template 609227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 610227825Stheraven rebind<value_type> 611227825Stheraven#else 612227825Stheraven rebind<value_type>::other 613227825Stheraven#endif 614227825Stheraven pointer; 615227825Stheraven 616227825Stheraven _LIBCPP_INLINE_VISIBILITY 617227825Stheraven __hash_map_iterator() _NOEXCEPT {} 618227825Stheraven 619227825Stheraven _LIBCPP_INLINE_VISIBILITY 620227825Stheraven __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 621227825Stheraven 622227825Stheraven _LIBCPP_INLINE_VISIBILITY 623253159Stheraven reference operator*() const {return __i_->__cc;} 624227825Stheraven _LIBCPP_INLINE_VISIBILITY 625253159Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 626227825Stheraven 627227825Stheraven _LIBCPP_INLINE_VISIBILITY 628227825Stheraven __hash_map_iterator& operator++() {++__i_; return *this;} 629227825Stheraven _LIBCPP_INLINE_VISIBILITY 630227825Stheraven __hash_map_iterator operator++(int) 631227825Stheraven { 632227825Stheraven __hash_map_iterator __t(*this); 633227825Stheraven ++(*this); 634227825Stheraven return __t; 635227825Stheraven } 636227825Stheraven 637227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 638227825Stheraven bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 639227825Stheraven {return __x.__i_ == __y.__i_;} 640227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 641227825Stheraven bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 642227825Stheraven {return __x.__i_ != __y.__i_;} 643227825Stheraven 644262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 645262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 646262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 647262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 648262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 649227825Stheraven}; 650227825Stheraven 651227825Stheraventemplate <class _HashIterator> 652262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator 653227825Stheraven{ 654227825Stheraven _HashIterator __i_; 655227825Stheraven 656227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 657253159Stheraven typedef const typename _HashIterator::value_type::value_type::first_type key_type; 658253159Stheraven typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 659227825Stheravenpublic: 660227825Stheraven typedef forward_iterator_tag iterator_category; 661227825Stheraven typedef pair<key_type, mapped_type> value_type; 662227825Stheraven typedef typename _HashIterator::difference_type difference_type; 663227825Stheraven typedef const value_type& reference; 664227825Stheraven typedef typename __pointer_traits::template 665227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 666227825Stheraven rebind<const value_type> 667227825Stheraven#else 668227825Stheraven rebind<const value_type>::other 669227825Stheraven#endif 670227825Stheraven pointer; 671227825Stheraven 672227825Stheraven _LIBCPP_INLINE_VISIBILITY 673227825Stheraven __hash_map_const_iterator() _NOEXCEPT {} 674227825Stheraven 675227825Stheraven _LIBCPP_INLINE_VISIBILITY 676227825Stheraven __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 677227825Stheraven _LIBCPP_INLINE_VISIBILITY 678227825Stheraven __hash_map_const_iterator( 679227825Stheraven __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 680227825Stheraven _NOEXCEPT 681227825Stheraven : __i_(__i.__i_) {} 682227825Stheraven 683227825Stheraven _LIBCPP_INLINE_VISIBILITY 684253159Stheraven reference operator*() const {return __i_->__cc;} 685227825Stheraven _LIBCPP_INLINE_VISIBILITY 686253159Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 687227825Stheraven 688227825Stheraven _LIBCPP_INLINE_VISIBILITY 689227825Stheraven __hash_map_const_iterator& operator++() {++__i_; return *this;} 690227825Stheraven _LIBCPP_INLINE_VISIBILITY 691227825Stheraven __hash_map_const_iterator operator++(int) 692227825Stheraven { 693227825Stheraven __hash_map_const_iterator __t(*this); 694227825Stheraven ++(*this); 695227825Stheraven return __t; 696227825Stheraven } 697227825Stheraven 698227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 699227825Stheraven bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 700227825Stheraven {return __x.__i_ == __y.__i_;} 701227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 702227825Stheraven bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 703227825Stheraven {return __x.__i_ != __y.__i_;} 704227825Stheraven 705262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 706262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 707262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 708262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 709227825Stheraven}; 710227825Stheraven 711227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 712227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 713262801Sdimclass _LIBCPP_TYPE_VIS_ONLY unordered_map 714227825Stheraven{ 715227825Stheravenpublic: 716227825Stheraven // types 717227825Stheraven typedef _Key key_type; 718227825Stheraven typedef _Tp mapped_type; 719227825Stheraven typedef _Hash hasher; 720227825Stheraven typedef _Pred key_equal; 721227825Stheraven typedef _Alloc allocator_type; 722227825Stheraven typedef pair<const key_type, mapped_type> value_type; 723253159Stheraven typedef pair<key_type, mapped_type> __nc_value_type; 724227825Stheraven typedef value_type& reference; 725227825Stheraven typedef const value_type& const_reference; 726262801Sdim static_assert((is_same<value_type, typename allocator_type::value_type>::value), 727262801Sdim "Invalid allocator::value_type"); 728227825Stheraven 729227825Stheravenprivate: 730262801Sdim typedef __hash_value_type<key_type, mapped_type> __value_type; 731253159Stheraven typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 732253159Stheraven typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 733227825Stheraven typedef typename allocator_traits<allocator_type>::template 734227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 735227825Stheraven rebind_alloc<__value_type> 736227825Stheraven#else 737227825Stheraven rebind_alloc<__value_type>::other 738227825Stheraven#endif 739227825Stheraven __allocator_type; 740227825Stheraven 741227825Stheraven typedef __hash_table<__value_type, __hasher, 742227825Stheraven __key_equal, __allocator_type> __table; 743227825Stheraven 744227825Stheraven __table __table_; 745227825Stheraven 746227825Stheraven typedef typename __table::__node_pointer __node_pointer; 747227825Stheraven typedef typename __table::__node_const_pointer __node_const_pointer; 748227825Stheraven typedef typename __table::__node_traits __node_traits; 749227825Stheraven typedef typename __table::__node_allocator __node_allocator; 750227825Stheraven typedef typename __table::__node __node; 751232950Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 752232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 753227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 754227825Stheravenpublic: 755227825Stheraven typedef typename __alloc_traits::pointer pointer; 756227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 757227825Stheraven typedef typename __alloc_traits::size_type size_type; 758227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 759227825Stheraven 760227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 761227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 762227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 763227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 764227825Stheraven 765227825Stheraven _LIBCPP_INLINE_VISIBILITY 766227825Stheraven unordered_map() 767227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 768262801Sdim { 769262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 770262801Sdim __get_db()->__insert_c(this); 771262801Sdim#endif 772262801Sdim } 773227825Stheraven explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 774227825Stheraven const key_equal& __eql = key_equal()); 775227825Stheraven unordered_map(size_type __n, const hasher& __hf, 776227825Stheraven const key_equal& __eql, 777227825Stheraven const allocator_type& __a); 778227825Stheraven template <class _InputIterator> 779227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last); 780227825Stheraven template <class _InputIterator> 781227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 782227825Stheraven size_type __n, const hasher& __hf = hasher(), 783227825Stheraven const key_equal& __eql = key_equal()); 784227825Stheraven template <class _InputIterator> 785227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 786227825Stheraven size_type __n, const hasher& __hf, 787227825Stheraven const key_equal& __eql, 788227825Stheraven const allocator_type& __a); 789227825Stheraven explicit unordered_map(const allocator_type& __a); 790227825Stheraven unordered_map(const unordered_map& __u); 791227825Stheraven unordered_map(const unordered_map& __u, const allocator_type& __a); 792227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 793227825Stheraven unordered_map(unordered_map&& __u) 794227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 795227825Stheraven unordered_map(unordered_map&& __u, const allocator_type& __a); 796227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 797227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 798227825Stheraven unordered_map(initializer_list<value_type> __il); 799227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 800227825Stheraven const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 801227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 802227825Stheraven const hasher& __hf, const key_equal& __eql, 803227825Stheraven const allocator_type& __a); 804227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 805262801Sdim#if _LIBCPP_STD_VER > 11 806262801Sdim _LIBCPP_INLINE_VISIBILITY 807262801Sdim unordered_map(size_type __n, const allocator_type& __a) 808262801Sdim : unordered_map(__n, hasher(), key_equal(), __a) {} 809262801Sdim _LIBCPP_INLINE_VISIBILITY 810262801Sdim unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a) 811262801Sdim : unordered_map(__n, __hf, key_equal(), __a) {} 812262801Sdim template <class _InputIterator> 813262801Sdim _LIBCPP_INLINE_VISIBILITY 814262801Sdim unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 815262801Sdim : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} 816262801Sdim template <class _InputIterator> 817262801Sdim _LIBCPP_INLINE_VISIBILITY 818262801Sdim unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 819262801Sdim const allocator_type& __a) 820262801Sdim : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} 821262801Sdim _LIBCPP_INLINE_VISIBILITY 822262801Sdim unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 823262801Sdim : unordered_map(__il, __n, hasher(), key_equal(), __a) {} 824262801Sdim _LIBCPP_INLINE_VISIBILITY 825262801Sdim unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 826262801Sdim const allocator_type& __a) 827262801Sdim : unordered_map(__il, __n, __hf, key_equal(), __a) {} 828262801Sdim#endif 829227825Stheraven // ~unordered_map() = default; 830227825Stheraven _LIBCPP_INLINE_VISIBILITY 831227825Stheraven unordered_map& operator=(const unordered_map& __u) 832227825Stheraven { 833253159Stheraven#if __cplusplus >= 201103L 834227825Stheraven __table_ = __u.__table_; 835253159Stheraven#else 836263272Sdim if (this != &__u) { 837263272Sdim __table_.clear(); 838263272Sdim __table_.hash_function() = __u.__table_.hash_function(); 839263272Sdim __table_.key_eq() = __u.__table_.key_eq(); 840263272Sdim __table_.max_load_factor() = __u.__table_.max_load_factor(); 841263272Sdim __table_.__copy_assign_alloc(__u.__table_); 842263272Sdim insert(__u.begin(), __u.end()); 843263272Sdim } 844253159Stheraven#endif 845227825Stheraven return *this; 846227825Stheraven } 847227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 848227825Stheraven unordered_map& operator=(unordered_map&& __u) 849227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 850227825Stheraven#endif 851227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 852227825Stheraven unordered_map& operator=(initializer_list<value_type> __il); 853227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 854227825Stheraven 855227825Stheraven _LIBCPP_INLINE_VISIBILITY 856227825Stheraven allocator_type get_allocator() const _NOEXCEPT 857227825Stheraven {return allocator_type(__table_.__node_alloc());} 858227825Stheraven 859227825Stheraven _LIBCPP_INLINE_VISIBILITY 860227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 861227825Stheraven _LIBCPP_INLINE_VISIBILITY 862227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 863227825Stheraven _LIBCPP_INLINE_VISIBILITY 864227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 865227825Stheraven 866227825Stheraven _LIBCPP_INLINE_VISIBILITY 867227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 868227825Stheraven _LIBCPP_INLINE_VISIBILITY 869227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 870227825Stheraven _LIBCPP_INLINE_VISIBILITY 871227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 872227825Stheraven _LIBCPP_INLINE_VISIBILITY 873227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 874227825Stheraven _LIBCPP_INLINE_VISIBILITY 875227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 876227825Stheraven _LIBCPP_INLINE_VISIBILITY 877227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 878227825Stheraven 879227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 880227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 881227825Stheraven 882241903Sdim template <class... _Args> 883241903Sdim pair<iterator, bool> emplace(_Args&&... __args); 884227825Stheraven 885241903Sdim template <class... _Args> 886227825Stheraven _LIBCPP_INLINE_VISIBILITY 887262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 888262801Sdim iterator emplace_hint(const_iterator __p, _Args&&... __args) 889262801Sdim { 890262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 891262801Sdim "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" 892262801Sdim " referring to this unordered_map"); 893262801Sdim return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 894262801Sdim } 895262801Sdim#else 896241903Sdim iterator emplace_hint(const_iterator, _Args&&... __args) 897241903Sdim {return emplace(_VSTD::forward<_Args>(__args)...).first;} 898262801Sdim#endif 899227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 900227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 901227825Stheraven _LIBCPP_INLINE_VISIBILITY 902227825Stheraven pair<iterator, bool> insert(const value_type& __x) 903227825Stheraven {return __table_.__insert_unique(__x);} 904227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 905232950Stheraven template <class _Pp, 906232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 907227825Stheraven _LIBCPP_INLINE_VISIBILITY 908232950Stheraven pair<iterator, bool> insert(_Pp&& __x) 909232950Stheraven {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 910227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 911227825Stheraven _LIBCPP_INLINE_VISIBILITY 912262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 913262801Sdim iterator insert(const_iterator __p, const value_type& __x) 914262801Sdim { 915262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 916262801Sdim "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" 917262801Sdim " referring to this unordered_map"); 918262801Sdim return insert(__x).first; 919262801Sdim } 920262801Sdim#else 921227825Stheraven iterator insert(const_iterator, const value_type& __x) 922227825Stheraven {return insert(__x).first;} 923262801Sdim#endif 924227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 925232950Stheraven template <class _Pp, 926232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 927227825Stheraven _LIBCPP_INLINE_VISIBILITY 928262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 929262801Sdim iterator insert(const_iterator __p, _Pp&& __x) 930262801Sdim { 931262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 932262801Sdim "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" 933262801Sdim " referring to this unordered_map"); 934262801Sdim return insert(_VSTD::forward<_Pp>(__x)).first; 935262801Sdim } 936262801Sdim#else 937232950Stheraven iterator insert(const_iterator, _Pp&& __x) 938232950Stheraven {return insert(_VSTD::forward<_Pp>(__x)).first;} 939262801Sdim#endif 940227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 941227825Stheraven template <class _InputIterator> 942227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 943227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 944227825Stheraven _LIBCPP_INLINE_VISIBILITY 945227825Stheraven void insert(initializer_list<value_type> __il) 946227825Stheraven {insert(__il.begin(), __il.end());} 947227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 948227825Stheraven 949227825Stheraven _LIBCPP_INLINE_VISIBILITY 950227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 951227825Stheraven _LIBCPP_INLINE_VISIBILITY 952227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 953227825Stheraven _LIBCPP_INLINE_VISIBILITY 954227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 955227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 956227825Stheraven _LIBCPP_INLINE_VISIBILITY 957227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 958227825Stheraven 959227825Stheraven _LIBCPP_INLINE_VISIBILITY 960227825Stheraven void swap(unordered_map& __u) 961227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 962227825Stheraven {__table_.swap(__u.__table_);} 963227825Stheraven 964227825Stheraven _LIBCPP_INLINE_VISIBILITY 965227825Stheraven hasher hash_function() const 966227825Stheraven {return __table_.hash_function().hash_function();} 967227825Stheraven _LIBCPP_INLINE_VISIBILITY 968227825Stheraven key_equal key_eq() const 969227825Stheraven {return __table_.key_eq().key_eq();} 970227825Stheraven 971227825Stheraven _LIBCPP_INLINE_VISIBILITY 972227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 973227825Stheraven _LIBCPP_INLINE_VISIBILITY 974227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 975227825Stheraven _LIBCPP_INLINE_VISIBILITY 976227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 977227825Stheraven _LIBCPP_INLINE_VISIBILITY 978227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 979227825Stheraven {return __table_.__equal_range_unique(__k);} 980227825Stheraven _LIBCPP_INLINE_VISIBILITY 981227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 982227825Stheraven {return __table_.__equal_range_unique(__k);} 983227825Stheraven 984227825Stheraven mapped_type& operator[](const key_type& __k); 985227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 986227825Stheraven mapped_type& operator[](key_type&& __k); 987227825Stheraven#endif 988227825Stheraven 989227825Stheraven mapped_type& at(const key_type& __k); 990227825Stheraven const mapped_type& at(const key_type& __k) const; 991227825Stheraven 992227825Stheraven _LIBCPP_INLINE_VISIBILITY 993227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 994227825Stheraven _LIBCPP_INLINE_VISIBILITY 995227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 996227825Stheraven 997227825Stheraven _LIBCPP_INLINE_VISIBILITY 998227825Stheraven size_type bucket_size(size_type __n) const 999227825Stheraven {return __table_.bucket_size(__n);} 1000227825Stheraven _LIBCPP_INLINE_VISIBILITY 1001227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1002227825Stheraven 1003227825Stheraven _LIBCPP_INLINE_VISIBILITY 1004227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1005227825Stheraven _LIBCPP_INLINE_VISIBILITY 1006227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1007227825Stheraven _LIBCPP_INLINE_VISIBILITY 1008227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1009227825Stheraven _LIBCPP_INLINE_VISIBILITY 1010227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1011227825Stheraven _LIBCPP_INLINE_VISIBILITY 1012227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1013227825Stheraven _LIBCPP_INLINE_VISIBILITY 1014227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1015227825Stheraven 1016227825Stheraven _LIBCPP_INLINE_VISIBILITY 1017227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1018227825Stheraven _LIBCPP_INLINE_VISIBILITY 1019227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1020227825Stheraven _LIBCPP_INLINE_VISIBILITY 1021227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1022227825Stheraven _LIBCPP_INLINE_VISIBILITY 1023227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1024227825Stheraven _LIBCPP_INLINE_VISIBILITY 1025227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1026227825Stheraven 1027262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1028262801Sdim 1029262801Sdim bool __dereferenceable(const const_iterator* __i) const 1030262801Sdim {return __table_.__dereferenceable(&__i->__i_);} 1031262801Sdim bool __decrementable(const const_iterator* __i) const 1032262801Sdim {return __table_.__decrementable(&__i->__i_);} 1033262801Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1034262801Sdim {return __table_.__addable(&__i->__i_, __n);} 1035262801Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1036262801Sdim {return __table_.__addable(&__i->__i_, __n);} 1037262801Sdim 1038262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1039262801Sdim 1040227825Stheravenprivate: 1041227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1042241903Sdim __node_holder __construct_node(); 1043241903Sdim template <class _A0> 1044253159Stheraven __node_holder 1045241903Sdim __construct_node(_A0&& __a0); 1046253159Stheraven __node_holder __construct_node_with_key(key_type&& __k); 1047227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1048241903Sdim template <class _A0, class _A1, class ..._Args> 1049241903Sdim __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1050227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1051253159Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1052253159Stheraven __node_holder __construct_node_with_key(const key_type& __k); 1053227825Stheraven}; 1054227825Stheraven 1055227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1056227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1057227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1058227825Stheraven : __table_(__hf, __eql) 1059227825Stheraven{ 1060262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1061262801Sdim __get_db()->__insert_c(this); 1062262801Sdim#endif 1063227825Stheraven __table_.rehash(__n); 1064227825Stheraven} 1065227825Stheraven 1066227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1067227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1068227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1069227825Stheraven const allocator_type& __a) 1070227825Stheraven : __table_(__hf, __eql, __a) 1071227825Stheraven{ 1072262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1073262801Sdim __get_db()->__insert_c(this); 1074262801Sdim#endif 1075227825Stheraven __table_.rehash(__n); 1076227825Stheraven} 1077227825Stheraven 1078227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1079227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1080227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1081227825Stheraven const allocator_type& __a) 1082227825Stheraven : __table_(__a) 1083227825Stheraven{ 1084262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1085262801Sdim __get_db()->__insert_c(this); 1086262801Sdim#endif 1087227825Stheraven} 1088227825Stheraven 1089227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1090227825Stheraventemplate <class _InputIterator> 1091227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1092227825Stheraven _InputIterator __first, _InputIterator __last) 1093227825Stheraven{ 1094262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1095262801Sdim __get_db()->__insert_c(this); 1096262801Sdim#endif 1097227825Stheraven insert(__first, __last); 1098227825Stheraven} 1099227825Stheraven 1100227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1101227825Stheraventemplate <class _InputIterator> 1102227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1103227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1104227825Stheraven const hasher& __hf, const key_equal& __eql) 1105227825Stheraven : __table_(__hf, __eql) 1106227825Stheraven{ 1107262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1108262801Sdim __get_db()->__insert_c(this); 1109262801Sdim#endif 1110227825Stheraven __table_.rehash(__n); 1111227825Stheraven insert(__first, __last); 1112227825Stheraven} 1113227825Stheraven 1114227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1115227825Stheraventemplate <class _InputIterator> 1116227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1117227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1118227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1119227825Stheraven : __table_(__hf, __eql, __a) 1120227825Stheraven{ 1121262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1122262801Sdim __get_db()->__insert_c(this); 1123262801Sdim#endif 1124227825Stheraven __table_.rehash(__n); 1125227825Stheraven insert(__first, __last); 1126227825Stheraven} 1127227825Stheraven 1128227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1129227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1130227825Stheraven const unordered_map& __u) 1131227825Stheraven : __table_(__u.__table_) 1132227825Stheraven{ 1133262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1134262801Sdim __get_db()->__insert_c(this); 1135262801Sdim#endif 1136227825Stheraven __table_.rehash(__u.bucket_count()); 1137227825Stheraven insert(__u.begin(), __u.end()); 1138227825Stheraven} 1139227825Stheraven 1140227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1141227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1142227825Stheraven const unordered_map& __u, const allocator_type& __a) 1143227825Stheraven : __table_(__u.__table_, __a) 1144227825Stheraven{ 1145262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1146262801Sdim __get_db()->__insert_c(this); 1147262801Sdim#endif 1148227825Stheraven __table_.rehash(__u.bucket_count()); 1149227825Stheraven insert(__u.begin(), __u.end()); 1150227825Stheraven} 1151227825Stheraven 1152227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1153227825Stheraven 1154227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1155227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1156227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1157227825Stheraven unordered_map&& __u) 1158227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1159227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1160227825Stheraven{ 1161262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1162262801Sdim __get_db()->__insert_c(this); 1163262801Sdim __get_db()->swap(this, &__u); 1164262801Sdim#endif 1165227825Stheraven} 1166227825Stheraven 1167227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1168227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1169227825Stheraven unordered_map&& __u, const allocator_type& __a) 1170227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1171227825Stheraven{ 1172262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1173262801Sdim __get_db()->__insert_c(this); 1174262801Sdim#endif 1175227825Stheraven if (__a != __u.get_allocator()) 1176227825Stheraven { 1177227825Stheraven iterator __i = __u.begin(); 1178227825Stheraven while (__u.size() != 0) 1179227825Stheraven __table_.__insert_unique( 1180227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1181227825Stheraven ); 1182227825Stheraven } 1183262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1184262801Sdim else 1185262801Sdim __get_db()->swap(this, &__u); 1186262801Sdim#endif 1187227825Stheraven} 1188227825Stheraven 1189227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1190227825Stheraven 1191227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1192227825Stheraven 1193227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1194227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1195227825Stheraven initializer_list<value_type> __il) 1196227825Stheraven{ 1197262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1198262801Sdim __get_db()->__insert_c(this); 1199262801Sdim#endif 1200227825Stheraven insert(__il.begin(), __il.end()); 1201227825Stheraven} 1202227825Stheraven 1203227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1204227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1205227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1206227825Stheraven const key_equal& __eql) 1207227825Stheraven : __table_(__hf, __eql) 1208227825Stheraven{ 1209262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1210262801Sdim __get_db()->__insert_c(this); 1211262801Sdim#endif 1212227825Stheraven __table_.rehash(__n); 1213227825Stheraven insert(__il.begin(), __il.end()); 1214227825Stheraven} 1215227825Stheraven 1216227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1217227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1218227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1219227825Stheraven const key_equal& __eql, const allocator_type& __a) 1220227825Stheraven : __table_(__hf, __eql, __a) 1221227825Stheraven{ 1222262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1223262801Sdim __get_db()->__insert_c(this); 1224262801Sdim#endif 1225227825Stheraven __table_.rehash(__n); 1226227825Stheraven insert(__il.begin(), __il.end()); 1227227825Stheraven} 1228227825Stheraven 1229227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1230227825Stheraven 1231227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1232227825Stheraven 1233227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1234227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1235227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1236227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1237227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1238227825Stheraven{ 1239227825Stheraven __table_ = _VSTD::move(__u.__table_); 1240227825Stheraven return *this; 1241227825Stheraven} 1242227825Stheraven 1243227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1244227825Stheraven 1245227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1246227825Stheraven 1247227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1248227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1249227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1250227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1251227825Stheraven initializer_list<value_type> __il) 1252227825Stheraven{ 1253227825Stheraven __table_.__assign_unique(__il.begin(), __il.end()); 1254227825Stheraven return *this; 1255227825Stheraven} 1256227825Stheraven 1257227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1258227825Stheraven 1259227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1260227825Stheraven 1261227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1262227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1263241903Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1264227825Stheraven{ 1265227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1266232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1267241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1268227825Stheraven __h.get_deleter().__first_constructed = true; 1269227825Stheraven __h.get_deleter().__second_constructed = true; 1270227825Stheraven return __h; 1271227825Stheraven} 1272227825Stheraven 1273227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1274241903Sdimtemplate <class _A0> 1275253159Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1276227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1277227825Stheraven{ 1278227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1279232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1280227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1281227825Stheraven _VSTD::forward<_A0>(__a0)); 1282227825Stheraven __h.get_deleter().__first_constructed = true; 1283227825Stheraven __h.get_deleter().__second_constructed = true; 1284227825Stheraven return __h; 1285227825Stheraven} 1286227825Stheraven 1287241903Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1288253159Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1289253159Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k) 1290241903Sdim{ 1291241903Sdim __node_allocator& __na = __table_.__node_alloc(); 1292241903Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1293253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k)); 1294241903Sdim __h.get_deleter().__first_constructed = true; 1295253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1296241903Sdim __h.get_deleter().__second_constructed = true; 1297262801Sdim return __h; 1298241903Sdim} 1299241903Sdim 1300227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1301227825Stheraven 1302227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1303241903Sdimtemplate <class _A0, class _A1, class ..._Args> 1304241903Sdimtypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1305241903Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1306241903Sdim _A1&& __a1, 1307241903Sdim _Args&&... __args) 1308241903Sdim{ 1309241903Sdim __node_allocator& __na = __table_.__node_alloc(); 1310241903Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1311241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1312241903Sdim _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1313241903Sdim _VSTD::forward<_Args>(__args)...); 1314241903Sdim __h.get_deleter().__first_constructed = true; 1315241903Sdim __h.get_deleter().__second_constructed = true; 1316241903Sdim return __h; 1317241903Sdim} 1318241903Sdim 1319241903Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1320241903Sdimtemplate <class... _Args> 1321227825Stheravenpair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1322241903Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1323227825Stheraven{ 1324241903Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1325227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1326227825Stheraven if (__r.second) 1327227825Stheraven __h.release(); 1328227825Stheraven return __r; 1329227825Stheraven} 1330227825Stheraven 1331227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1332253159Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1333227825Stheraven 1334227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1335227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1336253159Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1337227825Stheraven{ 1338227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1339232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1340253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1341227825Stheraven __h.get_deleter().__first_constructed = true; 1342253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1343227825Stheraven __h.get_deleter().__second_constructed = true; 1344262801Sdim return _VSTD::move(__h); // explicitly moved for C++03 1345227825Stheraven} 1346227825Stheraven 1347227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1348227825Stheraventemplate <class _InputIterator> 1349227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1350227825Stheravenvoid 1351227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1352227825Stheraven _InputIterator __last) 1353227825Stheraven{ 1354227825Stheraven for (; __first != __last; ++__first) 1355227825Stheraven __table_.__insert_unique(*__first); 1356227825Stheraven} 1357227825Stheraven 1358227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1359227825Stheraven_Tp& 1360227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1361227825Stheraven{ 1362227825Stheraven iterator __i = find(__k); 1363227825Stheraven if (__i != end()) 1364227825Stheraven return __i->second; 1365253159Stheraven __node_holder __h = __construct_node_with_key(__k); 1366227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1367227825Stheraven __h.release(); 1368227825Stheraven return __r.first->second; 1369227825Stheraven} 1370227825Stheraven 1371227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1372227825Stheraven 1373227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1374227825Stheraven_Tp& 1375227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1376227825Stheraven{ 1377227825Stheraven iterator __i = find(__k); 1378227825Stheraven if (__i != end()) 1379227825Stheraven return __i->second; 1380253159Stheraven __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); 1381227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1382227825Stheraven __h.release(); 1383227825Stheraven return __r.first->second; 1384227825Stheraven} 1385227825Stheraven 1386227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1387227825Stheraven 1388227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1389227825Stheraven_Tp& 1390227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1391227825Stheraven{ 1392227825Stheraven iterator __i = find(__k); 1393227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1394227825Stheraven if (__i == end()) 1395227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1396227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1397227825Stheraven return __i->second; 1398227825Stheraven} 1399227825Stheraven 1400227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1401227825Stheravenconst _Tp& 1402227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1403227825Stheraven{ 1404227825Stheraven const_iterator __i = find(__k); 1405227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1406227825Stheraven if (__i == end()) 1407227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1408227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1409227825Stheraven return __i->second; 1410227825Stheraven} 1411227825Stheraven 1412227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1413227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1414227825Stheravenvoid 1415227825Stheravenswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1416227825Stheraven unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1417227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1418227825Stheraven{ 1419227825Stheraven __x.swap(__y); 1420227825Stheraven} 1421227825Stheraven 1422227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1423227825Stheravenbool 1424227825Stheravenoperator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1425227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1426227825Stheraven{ 1427227825Stheraven if (__x.size() != __y.size()) 1428227825Stheraven return false; 1429227825Stheraven typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1430227825Stheraven const_iterator; 1431227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1432227825Stheraven __i != __ex; ++__i) 1433227825Stheraven { 1434227825Stheraven const_iterator __j = __y.find(__i->first); 1435227825Stheraven if (__j == __ey || !(*__i == *__j)) 1436227825Stheraven return false; 1437227825Stheraven } 1438227825Stheraven return true; 1439227825Stheraven} 1440227825Stheraven 1441227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1442227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1443227825Stheravenbool 1444227825Stheravenoperator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1445227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1446227825Stheraven{ 1447227825Stheraven return !(__x == __y); 1448227825Stheraven} 1449227825Stheraven 1450227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1451227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 1452262801Sdimclass _LIBCPP_TYPE_VIS_ONLY unordered_multimap 1453227825Stheraven{ 1454227825Stheravenpublic: 1455227825Stheraven // types 1456227825Stheraven typedef _Key key_type; 1457227825Stheraven typedef _Tp mapped_type; 1458227825Stheraven typedef _Hash hasher; 1459227825Stheraven typedef _Pred key_equal; 1460227825Stheraven typedef _Alloc allocator_type; 1461227825Stheraven typedef pair<const key_type, mapped_type> value_type; 1462253159Stheraven typedef pair<key_type, mapped_type> __nc_value_type; 1463227825Stheraven typedef value_type& reference; 1464227825Stheraven typedef const value_type& const_reference; 1465262801Sdim static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1466262801Sdim "Invalid allocator::value_type"); 1467227825Stheraven 1468227825Stheravenprivate: 1469262801Sdim typedef __hash_value_type<key_type, mapped_type> __value_type; 1470253159Stheraven typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 1471253159Stheraven typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 1472227825Stheraven typedef typename allocator_traits<allocator_type>::template 1473227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1474227825Stheraven rebind_alloc<__value_type> 1475227825Stheraven#else 1476227825Stheraven rebind_alloc<__value_type>::other 1477227825Stheraven#endif 1478227825Stheraven __allocator_type; 1479227825Stheraven 1480227825Stheraven typedef __hash_table<__value_type, __hasher, 1481227825Stheraven __key_equal, __allocator_type> __table; 1482227825Stheraven 1483227825Stheraven __table __table_; 1484227825Stheraven 1485227825Stheraven typedef typename __table::__node_traits __node_traits; 1486227825Stheraven typedef typename __table::__node_allocator __node_allocator; 1487227825Stheraven typedef typename __table::__node __node; 1488232950Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 1489232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 1490227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 1491227825Stheravenpublic: 1492227825Stheraven typedef typename __alloc_traits::pointer pointer; 1493227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 1494227825Stheraven typedef typename __alloc_traits::size_type size_type; 1495227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 1496227825Stheraven 1497227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 1498227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1499227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1500227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1501227825Stheraven 1502227825Stheraven _LIBCPP_INLINE_VISIBILITY 1503227825Stheraven unordered_multimap() 1504227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1505262801Sdim { 1506262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1507262801Sdim __get_db()->__insert_c(this); 1508262801Sdim#endif 1509262801Sdim } 1510227825Stheraven explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1511227825Stheraven const key_equal& __eql = key_equal()); 1512227825Stheraven unordered_multimap(size_type __n, const hasher& __hf, 1513227825Stheraven const key_equal& __eql, 1514227825Stheraven const allocator_type& __a); 1515227825Stheraven template <class _InputIterator> 1516227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last); 1517227825Stheraven template <class _InputIterator> 1518227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1519227825Stheraven size_type __n, const hasher& __hf = hasher(), 1520227825Stheraven const key_equal& __eql = key_equal()); 1521227825Stheraven template <class _InputIterator> 1522227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1523227825Stheraven size_type __n, const hasher& __hf, 1524227825Stheraven const key_equal& __eql, 1525227825Stheraven const allocator_type& __a); 1526227825Stheraven explicit unordered_multimap(const allocator_type& __a); 1527227825Stheraven unordered_multimap(const unordered_multimap& __u); 1528227825Stheraven unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1529227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1530227825Stheraven unordered_multimap(unordered_multimap&& __u) 1531227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1532227825Stheraven unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1533227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1534227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1535227825Stheraven unordered_multimap(initializer_list<value_type> __il); 1536227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1537227825Stheraven const hasher& __hf = hasher(), 1538227825Stheraven const key_equal& __eql = key_equal()); 1539227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1540227825Stheraven const hasher& __hf, const key_equal& __eql, 1541227825Stheraven const allocator_type& __a); 1542227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1543262801Sdim#if _LIBCPP_STD_VER > 11 1544262801Sdim _LIBCPP_INLINE_VISIBILITY 1545262801Sdim unordered_multimap(size_type __n, const allocator_type& __a) 1546262801Sdim : unordered_multimap(__n, hasher(), key_equal(), __a) {} 1547262801Sdim _LIBCPP_INLINE_VISIBILITY 1548262801Sdim unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 1549262801Sdim : unordered_multimap(__n, __hf, key_equal(), __a) {} 1550262801Sdim template <class _InputIterator> 1551262801Sdim _LIBCPP_INLINE_VISIBILITY 1552262801Sdim unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1553262801Sdim : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 1554262801Sdim template <class _InputIterator> 1555262801Sdim _LIBCPP_INLINE_VISIBILITY 1556262801Sdim unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 1557262801Sdim const allocator_type& __a) 1558262801Sdim : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 1559262801Sdim _LIBCPP_INLINE_VISIBILITY 1560262801Sdim unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1561262801Sdim : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 1562262801Sdim _LIBCPP_INLINE_VISIBILITY 1563262801Sdim unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1564262801Sdim const allocator_type& __a) 1565262801Sdim : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 1566262801Sdim#endif 1567227825Stheraven // ~unordered_multimap() = default; 1568227825Stheraven _LIBCPP_INLINE_VISIBILITY 1569227825Stheraven unordered_multimap& operator=(const unordered_multimap& __u) 1570227825Stheraven { 1571253159Stheraven#if __cplusplus >= 201103L 1572227825Stheraven __table_ = __u.__table_; 1573253159Stheraven#else 1574263272Sdim if (this != &__u) { 1575263272Sdim __table_.clear(); 1576263272Sdim __table_.hash_function() = __u.__table_.hash_function(); 1577263272Sdim __table_.key_eq() = __u.__table_.key_eq(); 1578263272Sdim __table_.max_load_factor() = __u.__table_.max_load_factor(); 1579263272Sdim __table_.__copy_assign_alloc(__u.__table_); 1580263272Sdim insert(__u.begin(), __u.end()); 1581263272Sdim } 1582253159Stheraven#endif 1583227825Stheraven return *this; 1584227825Stheraven } 1585227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1586227825Stheraven unordered_multimap& operator=(unordered_multimap&& __u) 1587227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1588227825Stheraven#endif 1589227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1590227825Stheraven unordered_multimap& operator=(initializer_list<value_type> __il); 1591227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1592227825Stheraven 1593227825Stheraven _LIBCPP_INLINE_VISIBILITY 1594227825Stheraven allocator_type get_allocator() const _NOEXCEPT 1595227825Stheraven {return allocator_type(__table_.__node_alloc());} 1596227825Stheraven 1597227825Stheraven _LIBCPP_INLINE_VISIBILITY 1598227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1599227825Stheraven _LIBCPP_INLINE_VISIBILITY 1600227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 1601227825Stheraven _LIBCPP_INLINE_VISIBILITY 1602227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1603227825Stheraven 1604227825Stheraven _LIBCPP_INLINE_VISIBILITY 1605227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 1606227825Stheraven _LIBCPP_INLINE_VISIBILITY 1607227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 1608227825Stheraven _LIBCPP_INLINE_VISIBILITY 1609227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1610227825Stheraven _LIBCPP_INLINE_VISIBILITY 1611227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 1612227825Stheraven _LIBCPP_INLINE_VISIBILITY 1613227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1614227825Stheraven _LIBCPP_INLINE_VISIBILITY 1615227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 1616227825Stheraven 1617227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1618227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1619227825Stheraven 1620241903Sdim template <class... _Args> 1621241903Sdim iterator emplace(_Args&&... __args); 1622227825Stheraven 1623241903Sdim template <class... _Args> 1624241903Sdim iterator emplace_hint(const_iterator __p, _Args&&... __args); 1625227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1626227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1627227825Stheraven _LIBCPP_INLINE_VISIBILITY 1628227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1629227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1630232950Stheraven template <class _Pp, 1631232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1632227825Stheraven _LIBCPP_INLINE_VISIBILITY 1633232950Stheraven iterator insert(_Pp&& __x) 1634232950Stheraven {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1635227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1636227825Stheraven _LIBCPP_INLINE_VISIBILITY 1637227825Stheraven iterator insert(const_iterator __p, const value_type& __x) 1638227825Stheraven {return __table_.__insert_multi(__p.__i_, __x);} 1639227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1640232950Stheraven template <class _Pp, 1641232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1642227825Stheraven _LIBCPP_INLINE_VISIBILITY 1643232950Stheraven iterator insert(const_iterator __p, _Pp&& __x) 1644232950Stheraven {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1645227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1646227825Stheraven template <class _InputIterator> 1647227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 1648227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1649227825Stheraven _LIBCPP_INLINE_VISIBILITY 1650227825Stheraven void insert(initializer_list<value_type> __il) 1651227825Stheraven {insert(__il.begin(), __il.end());} 1652227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1653227825Stheraven 1654227825Stheraven _LIBCPP_INLINE_VISIBILITY 1655227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1656227825Stheraven _LIBCPP_INLINE_VISIBILITY 1657227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1658227825Stheraven _LIBCPP_INLINE_VISIBILITY 1659227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 1660227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 1661227825Stheraven _LIBCPP_INLINE_VISIBILITY 1662227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 1663227825Stheraven 1664227825Stheraven _LIBCPP_INLINE_VISIBILITY 1665227825Stheraven void swap(unordered_multimap& __u) 1666227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1667227825Stheraven {__table_.swap(__u.__table_);} 1668227825Stheraven 1669227825Stheraven _LIBCPP_INLINE_VISIBILITY 1670227825Stheraven hasher hash_function() const 1671227825Stheraven {return __table_.hash_function().hash_function();} 1672227825Stheraven _LIBCPP_INLINE_VISIBILITY 1673227825Stheraven key_equal key_eq() const 1674227825Stheraven {return __table_.key_eq().key_eq();} 1675227825Stheraven 1676227825Stheraven _LIBCPP_INLINE_VISIBILITY 1677227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 1678227825Stheraven _LIBCPP_INLINE_VISIBILITY 1679227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1680227825Stheraven _LIBCPP_INLINE_VISIBILITY 1681227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1682227825Stheraven _LIBCPP_INLINE_VISIBILITY 1683227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 1684227825Stheraven {return __table_.__equal_range_multi(__k);} 1685227825Stheraven _LIBCPP_INLINE_VISIBILITY 1686227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1687227825Stheraven {return __table_.__equal_range_multi(__k);} 1688227825Stheraven 1689227825Stheraven _LIBCPP_INLINE_VISIBILITY 1690227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1691227825Stheraven _LIBCPP_INLINE_VISIBILITY 1692227825Stheraven size_type max_bucket_count() const _NOEXCEPT 1693227825Stheraven {return __table_.max_bucket_count();} 1694227825Stheraven 1695227825Stheraven _LIBCPP_INLINE_VISIBILITY 1696227825Stheraven size_type bucket_size(size_type __n) const 1697227825Stheraven {return __table_.bucket_size(__n);} 1698227825Stheraven _LIBCPP_INLINE_VISIBILITY 1699227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1700227825Stheraven 1701227825Stheraven _LIBCPP_INLINE_VISIBILITY 1702227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1703227825Stheraven _LIBCPP_INLINE_VISIBILITY 1704227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1705227825Stheraven _LIBCPP_INLINE_VISIBILITY 1706227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1707227825Stheraven _LIBCPP_INLINE_VISIBILITY 1708227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1709227825Stheraven _LIBCPP_INLINE_VISIBILITY 1710227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1711227825Stheraven _LIBCPP_INLINE_VISIBILITY 1712227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1713227825Stheraven 1714227825Stheraven _LIBCPP_INLINE_VISIBILITY 1715227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1716227825Stheraven _LIBCPP_INLINE_VISIBILITY 1717227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1718227825Stheraven _LIBCPP_INLINE_VISIBILITY 1719227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1720227825Stheraven _LIBCPP_INLINE_VISIBILITY 1721227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1722227825Stheraven _LIBCPP_INLINE_VISIBILITY 1723227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1724227825Stheraven 1725262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1726262801Sdim 1727262801Sdim bool __dereferenceable(const const_iterator* __i) const 1728262801Sdim {return __table_.__dereferenceable(&__i->__i_);} 1729262801Sdim bool __decrementable(const const_iterator* __i) const 1730262801Sdim {return __table_.__decrementable(&__i->__i_);} 1731262801Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1732262801Sdim {return __table_.__addable(&__i->__i_, __n);} 1733262801Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1734262801Sdim {return __table_.__addable(&__i->__i_, __n);} 1735262801Sdim 1736262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1737262801Sdim 1738227825Stheravenprivate: 1739241903Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1740241903Sdim __node_holder __construct_node(); 1741241903Sdim template <class _A0> 1742253159Stheraven __node_holder 1743241903Sdim __construct_node(_A0&& __a0); 1744241903Sdim#ifndef _LIBCPP_HAS_NO_VARIADICS 1745241903Sdim template <class _A0, class _A1, class ..._Args> 1746241903Sdim __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1747241903Sdim#endif // _LIBCPP_HAS_NO_VARIADICS 1748241903Sdim#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1749227825Stheraven}; 1750227825Stheraven 1751227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1752227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1753227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1754227825Stheraven : __table_(__hf, __eql) 1755227825Stheraven{ 1756262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1757262801Sdim __get_db()->__insert_c(this); 1758262801Sdim#endif 1759227825Stheraven __table_.rehash(__n); 1760227825Stheraven} 1761227825Stheraven 1762227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1763227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1764227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1765227825Stheraven const allocator_type& __a) 1766227825Stheraven : __table_(__hf, __eql, __a) 1767227825Stheraven{ 1768262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1769262801Sdim __get_db()->__insert_c(this); 1770262801Sdim#endif 1771227825Stheraven __table_.rehash(__n); 1772227825Stheraven} 1773227825Stheraven 1774227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1775227825Stheraventemplate <class _InputIterator> 1776227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1777227825Stheraven _InputIterator __first, _InputIterator __last) 1778227825Stheraven{ 1779262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1780262801Sdim __get_db()->__insert_c(this); 1781262801Sdim#endif 1782227825Stheraven insert(__first, __last); 1783227825Stheraven} 1784227825Stheraven 1785227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1786227825Stheraventemplate <class _InputIterator> 1787227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1788227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1789227825Stheraven const hasher& __hf, const key_equal& __eql) 1790227825Stheraven : __table_(__hf, __eql) 1791227825Stheraven{ 1792262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1793262801Sdim __get_db()->__insert_c(this); 1794262801Sdim#endif 1795227825Stheraven __table_.rehash(__n); 1796227825Stheraven insert(__first, __last); 1797227825Stheraven} 1798227825Stheraven 1799227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1800227825Stheraventemplate <class _InputIterator> 1801227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1802227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1803227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1804227825Stheraven : __table_(__hf, __eql, __a) 1805227825Stheraven{ 1806262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1807262801Sdim __get_db()->__insert_c(this); 1808262801Sdim#endif 1809227825Stheraven __table_.rehash(__n); 1810227825Stheraven insert(__first, __last); 1811227825Stheraven} 1812227825Stheraven 1813227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1814227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1815227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1816227825Stheraven const allocator_type& __a) 1817227825Stheraven : __table_(__a) 1818227825Stheraven{ 1819262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1820262801Sdim __get_db()->__insert_c(this); 1821262801Sdim#endif 1822227825Stheraven} 1823227825Stheraven 1824227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1825227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1826227825Stheraven const unordered_multimap& __u) 1827227825Stheraven : __table_(__u.__table_) 1828227825Stheraven{ 1829262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1830262801Sdim __get_db()->__insert_c(this); 1831262801Sdim#endif 1832227825Stheraven __table_.rehash(__u.bucket_count()); 1833227825Stheraven insert(__u.begin(), __u.end()); 1834227825Stheraven} 1835227825Stheraven 1836227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1837227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1838227825Stheraven const unordered_multimap& __u, const allocator_type& __a) 1839227825Stheraven : __table_(__u.__table_, __a) 1840227825Stheraven{ 1841262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1842262801Sdim __get_db()->__insert_c(this); 1843262801Sdim#endif 1844227825Stheraven __table_.rehash(__u.bucket_count()); 1845227825Stheraven insert(__u.begin(), __u.end()); 1846227825Stheraven} 1847227825Stheraven 1848227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1849227825Stheraven 1850227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1851227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1852227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1853227825Stheraven unordered_multimap&& __u) 1854227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1855227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1856227825Stheraven{ 1857262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1858262801Sdim __get_db()->__insert_c(this); 1859262801Sdim __get_db()->swap(this, &__u); 1860262801Sdim#endif 1861227825Stheraven} 1862227825Stheraven 1863227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1864227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1865227825Stheraven unordered_multimap&& __u, const allocator_type& __a) 1866227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1867227825Stheraven{ 1868262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1869262801Sdim __get_db()->__insert_c(this); 1870262801Sdim#endif 1871227825Stheraven if (__a != __u.get_allocator()) 1872227825Stheraven { 1873227825Stheraven iterator __i = __u.begin(); 1874227825Stheraven while (__u.size() != 0) 1875262801Sdim { 1876227825Stheraven __table_.__insert_multi( 1877227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1878227825Stheraven ); 1879262801Sdim } 1880227825Stheraven } 1881262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1882262801Sdim else 1883262801Sdim __get_db()->swap(this, &__u); 1884262801Sdim#endif 1885227825Stheraven} 1886227825Stheraven 1887227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1888227825Stheraven 1889227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1890227825Stheraven 1891227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1892227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1893227825Stheraven initializer_list<value_type> __il) 1894227825Stheraven{ 1895262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1896262801Sdim __get_db()->__insert_c(this); 1897262801Sdim#endif 1898227825Stheraven insert(__il.begin(), __il.end()); 1899227825Stheraven} 1900227825Stheraven 1901227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1902227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1903227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1904227825Stheraven const key_equal& __eql) 1905227825Stheraven : __table_(__hf, __eql) 1906227825Stheraven{ 1907262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1908262801Sdim __get_db()->__insert_c(this); 1909262801Sdim#endif 1910227825Stheraven __table_.rehash(__n); 1911227825Stheraven insert(__il.begin(), __il.end()); 1912227825Stheraven} 1913227825Stheraven 1914227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1915227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1916227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1917227825Stheraven const key_equal& __eql, const allocator_type& __a) 1918227825Stheraven : __table_(__hf, __eql, __a) 1919227825Stheraven{ 1920262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1921262801Sdim __get_db()->__insert_c(this); 1922262801Sdim#endif 1923227825Stheraven __table_.rehash(__n); 1924227825Stheraven insert(__il.begin(), __il.end()); 1925227825Stheraven} 1926227825Stheraven 1927227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1928227825Stheraven 1929227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1930227825Stheraven 1931227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1932227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1933227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1934227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1935227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1936227825Stheraven{ 1937227825Stheraven __table_ = _VSTD::move(__u.__table_); 1938227825Stheraven return *this; 1939227825Stheraven} 1940227825Stheraven 1941227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1942227825Stheraven 1943227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1944227825Stheraven 1945227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1946227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1947227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1948227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1949227825Stheraven initializer_list<value_type> __il) 1950227825Stheraven{ 1951227825Stheraven __table_.__assign_multi(__il.begin(), __il.end()); 1952227825Stheraven return *this; 1953227825Stheraven} 1954227825Stheraven 1955227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1956227825Stheraven 1957227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1958227825Stheraven 1959227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1960227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1961241903Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1962227825Stheraven{ 1963227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1964232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1965241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1966227825Stheraven __h.get_deleter().__first_constructed = true; 1967227825Stheraven __h.get_deleter().__second_constructed = true; 1968227825Stheraven return __h; 1969227825Stheraven} 1970227825Stheraven 1971227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1972241903Sdimtemplate <class _A0> 1973253159Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1974227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1975227825Stheraven{ 1976227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1977232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1978227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1979227825Stheraven _VSTD::forward<_A0>(__a0)); 1980227825Stheraven __h.get_deleter().__first_constructed = true; 1981227825Stheraven __h.get_deleter().__second_constructed = true; 1982227825Stheraven return __h; 1983227825Stheraven} 1984227825Stheraven 1985227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1986227825Stheraven 1987227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1988241903Sdimtemplate <class _A0, class _A1, class ..._Args> 1989241903Sdimtypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1990241903Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 1991241903Sdim _A0&& __a0, _A1&& __a1, _Args&&... __args) 1992241903Sdim{ 1993241903Sdim __node_allocator& __na = __table_.__node_alloc(); 1994241903Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1995241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1996241903Sdim _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1997241903Sdim _VSTD::forward<_Args>(__args)...); 1998241903Sdim __h.get_deleter().__first_constructed = true; 1999241903Sdim __h.get_deleter().__second_constructed = true; 2000241903Sdim return __h; 2001241903Sdim} 2002241903Sdim 2003241903Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2004241903Sdimtemplate <class... _Args> 2005227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2006241903Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 2007227825Stheraven{ 2008241903Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2009227825Stheraven iterator __r = __table_.__node_insert_multi(__h.get()); 2010227825Stheraven __h.release(); 2011227825Stheraven return __r; 2012227825Stheraven} 2013227825Stheraven 2014227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2015241903Sdimtemplate <class... _Args> 2016227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2017227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 2018241903Sdim const_iterator __p, _Args&&... __args) 2019227825Stheraven{ 2020241903Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2021227825Stheraven iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 2022227825Stheraven __h.release(); 2023227825Stheraven return __r; 2024227825Stheraven} 2025227825Stheraven 2026227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 2027227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2028227825Stheraven 2029227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2030227825Stheraventemplate <class _InputIterator> 2031227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2032227825Stheravenvoid 2033227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 2034227825Stheraven _InputIterator __last) 2035227825Stheraven{ 2036227825Stheraven for (; __first != __last; ++__first) 2037227825Stheraven __table_.__insert_multi(*__first); 2038227825Stheraven} 2039227825Stheraven 2040227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2041227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2042227825Stheravenvoid 2043227825Stheravenswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2044227825Stheraven unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2045227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2046227825Stheraven{ 2047227825Stheraven __x.swap(__y); 2048227825Stheraven} 2049227825Stheraven 2050227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2051227825Stheravenbool 2052227825Stheravenoperator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2053227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2054227825Stheraven{ 2055227825Stheraven if (__x.size() != __y.size()) 2056227825Stheraven return false; 2057227825Stheraven typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 2058227825Stheraven const_iterator; 2059227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 2060227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 2061227825Stheraven { 2062227825Stheraven _EqRng __xeq = __x.equal_range(__i->first); 2063227825Stheraven _EqRng __yeq = __y.equal_range(__i->first); 2064227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 2065227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 2066227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2067227825Stheraven return false; 2068227825Stheraven __i = __xeq.second; 2069227825Stheraven } 2070227825Stheraven return true; 2071227825Stheraven} 2072227825Stheraven 2073227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2074227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2075227825Stheravenbool 2076227825Stheravenoperator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2077227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2078227825Stheraven{ 2079227825Stheraven return !(__x == __y); 2080227825Stheraven} 2081227825Stheraven 2082227825Stheraven_LIBCPP_END_NAMESPACE_STD 2083227825Stheraven 2084227825Stheraven#endif // _LIBCPP_UNORDERED_MAP 2085