unordered_map revision 263272
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 354227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 355227825Stheraven#pragma GCC system_header 356227825Stheraven#endif 357227825Stheraven 358227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 359227825Stheraven 360253159Stheraventemplate <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value 361232950Stheraven#if __has_feature(is_final) 362232950Stheraven && !__is_final(_Hash) 363232950Stheraven#endif 364232950Stheraven > 365227825Stheravenclass __unordered_map_hasher 366227825Stheraven : private _Hash 367227825Stheraven{ 368227825Stheravenpublic: 369227825Stheraven _LIBCPP_INLINE_VISIBILITY 370227825Stheraven __unordered_map_hasher() 371227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 372227825Stheraven : _Hash() {} 373227825Stheraven _LIBCPP_INLINE_VISIBILITY 374227825Stheraven __unordered_map_hasher(const _Hash& __h) 375227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 376227825Stheraven : _Hash(__h) {} 377227825Stheraven _LIBCPP_INLINE_VISIBILITY 378227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return *this;} 379227825Stheraven _LIBCPP_INLINE_VISIBILITY 380232950Stheraven size_t operator()(const _Cp& __x) const 381253159Stheraven {return static_cast<const _Hash&>(*this)(__x.__cc.first);} 382232950Stheraven _LIBCPP_INLINE_VISIBILITY 383232950Stheraven size_t operator()(const _Key& __x) const 384227825Stheraven {return static_cast<const _Hash&>(*this)(__x);} 385227825Stheraven}; 386227825Stheraven 387253159Stheraventemplate <class _Key, class _Cp, class _Hash> 388253159Stheravenclass __unordered_map_hasher<_Key, _Cp, _Hash, false> 389227825Stheraven{ 390227825Stheraven _Hash __hash_; 391232950Stheraven 392227825Stheravenpublic: 393227825Stheraven _LIBCPP_INLINE_VISIBILITY 394227825Stheraven __unordered_map_hasher() 395227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 396227825Stheraven : __hash_() {} 397227825Stheraven _LIBCPP_INLINE_VISIBILITY 398227825Stheraven __unordered_map_hasher(const _Hash& __h) 399227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 400227825Stheraven : __hash_(__h) {} 401227825Stheraven _LIBCPP_INLINE_VISIBILITY 402227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 403227825Stheraven _LIBCPP_INLINE_VISIBILITY 404232950Stheraven size_t operator()(const _Cp& __x) const 405253159Stheraven {return __hash_(__x.__cc.first);} 406232950Stheraven _LIBCPP_INLINE_VISIBILITY 407232950Stheraven size_t operator()(const _Key& __x) const 408227825Stheraven {return __hash_(__x);} 409227825Stheraven}; 410227825Stheraven 411253159Stheraventemplate <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value 412232950Stheraven#if __has_feature(is_final) 413232950Stheraven && !__is_final(_Pred) 414232950Stheraven#endif 415232950Stheraven > 416227825Stheravenclass __unordered_map_equal 417227825Stheraven : private _Pred 418227825Stheraven{ 419227825Stheravenpublic: 420227825Stheraven _LIBCPP_INLINE_VISIBILITY 421227825Stheraven __unordered_map_equal() 422227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 423227825Stheraven : _Pred() {} 424227825Stheraven _LIBCPP_INLINE_VISIBILITY 425227825Stheraven __unordered_map_equal(const _Pred& __p) 426227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 427227825Stheraven : _Pred(__p) {} 428227825Stheraven _LIBCPP_INLINE_VISIBILITY 429227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return *this;} 430227825Stheraven _LIBCPP_INLINE_VISIBILITY 431232950Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 432253159Stheraven {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);} 433232950Stheraven _LIBCPP_INLINE_VISIBILITY 434232950Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 435253159Stheraven {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);} 436232950Stheraven _LIBCPP_INLINE_VISIBILITY 437232950Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 438253159Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);} 439227825Stheraven}; 440227825Stheraven 441253159Stheraventemplate <class _Key, class _Cp, class _Pred> 442253159Stheravenclass __unordered_map_equal<_Key, _Cp, _Pred, false> 443227825Stheraven{ 444227825Stheraven _Pred __pred_; 445232950Stheraven 446227825Stheravenpublic: 447227825Stheraven _LIBCPP_INLINE_VISIBILITY 448227825Stheraven __unordered_map_equal() 449227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 450227825Stheraven : __pred_() {} 451227825Stheraven _LIBCPP_INLINE_VISIBILITY 452227825Stheraven __unordered_map_equal(const _Pred& __p) 453227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 454227825Stheraven : __pred_(__p) {} 455227825Stheraven _LIBCPP_INLINE_VISIBILITY 456227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 457227825Stheraven _LIBCPP_INLINE_VISIBILITY 458232950Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 459253159Stheraven {return __pred_(__x.__cc.first, __y.__cc.first);} 460232950Stheraven _LIBCPP_INLINE_VISIBILITY 461232950Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 462253159Stheraven {return __pred_(__x.__cc.first, __y);} 463232950Stheraven _LIBCPP_INLINE_VISIBILITY 464232950Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 465253159Stheraven {return __pred_(__x, __y.__cc.first);} 466227825Stheraven}; 467227825Stheraven 468227825Stheraventemplate <class _Alloc> 469227825Stheravenclass __hash_map_node_destructor 470227825Stheraven{ 471227825Stheraven typedef _Alloc allocator_type; 472227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 473227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 474227825Stheravenpublic: 475227825Stheraven typedef typename __alloc_traits::pointer pointer; 476227825Stheravenprivate: 477253159Stheraven typedef typename value_type::value_type::first_type first_type; 478253159Stheraven typedef typename value_type::value_type::second_type second_type; 479227825Stheraven 480227825Stheraven allocator_type& __na_; 481227825Stheraven 482227825Stheraven __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 483227825Stheraven 484227825Stheravenpublic: 485227825Stheraven bool __first_constructed; 486227825Stheraven bool __second_constructed; 487227825Stheraven 488227825Stheraven _LIBCPP_INLINE_VISIBILITY 489227825Stheraven explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 490227825Stheraven : __na_(__na), 491227825Stheraven __first_constructed(false), 492227825Stheraven __second_constructed(false) 493227825Stheraven {} 494227825Stheraven 495227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 496227825Stheraven _LIBCPP_INLINE_VISIBILITY 497227825Stheraven __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 498227825Stheraven _NOEXCEPT 499227825Stheraven : __na_(__x.__na_), 500227825Stheraven __first_constructed(__x.__value_constructed), 501227825Stheraven __second_constructed(__x.__value_constructed) 502227825Stheraven { 503227825Stheraven __x.__value_constructed = false; 504227825Stheraven } 505227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 506227825Stheraven _LIBCPP_INLINE_VISIBILITY 507227825Stheraven __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 508227825Stheraven : __na_(__x.__na_), 509227825Stheraven __first_constructed(__x.__value_constructed), 510227825Stheraven __second_constructed(__x.__value_constructed) 511227825Stheraven { 512227825Stheraven const_cast<bool&>(__x.__value_constructed) = false; 513227825Stheraven } 514227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 515227825Stheraven 516227825Stheraven _LIBCPP_INLINE_VISIBILITY 517227825Stheraven void operator()(pointer __p) _NOEXCEPT 518227825Stheraven { 519227825Stheraven if (__second_constructed) 520253159Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second)); 521227825Stheraven if (__first_constructed) 522253159Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first)); 523227825Stheraven if (__p) 524227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 525227825Stheraven } 526227825Stheraven}; 527227825Stheraven 528262801Sdim#if __cplusplus >= 201103L 529262801Sdim 530262801Sdimtemplate <class _Key, class _Tp> 531262801Sdimunion __hash_value_type 532262801Sdim{ 533262801Sdim typedef _Key key_type; 534262801Sdim typedef _Tp mapped_type; 535262801Sdim typedef pair<const key_type, mapped_type> value_type; 536262801Sdim typedef pair<key_type, mapped_type> __nc_value_type; 537262801Sdim 538262801Sdim value_type __cc; 539262801Sdim __nc_value_type __nc; 540262801Sdim 541262801Sdim template <class ..._Args> 542262801Sdim _LIBCPP_INLINE_VISIBILITY 543262801Sdim __hash_value_type(_Args&& ...__args) 544262801Sdim : __cc(std::forward<_Args>(__args)...) {} 545262801Sdim 546262801Sdim _LIBCPP_INLINE_VISIBILITY 547262801Sdim __hash_value_type(const __hash_value_type& __v) 548262801Sdim : __cc(__v.__cc) {} 549262801Sdim 550262801Sdim _LIBCPP_INLINE_VISIBILITY 551262801Sdim __hash_value_type(__hash_value_type&& __v) 552262801Sdim : __nc(std::move(__v.__nc)) {} 553262801Sdim 554262801Sdim _LIBCPP_INLINE_VISIBILITY 555262801Sdim __hash_value_type& operator=(const __hash_value_type& __v) 556262801Sdim {__nc = __v.__cc; return *this;} 557262801Sdim 558262801Sdim _LIBCPP_INLINE_VISIBILITY 559262801Sdim __hash_value_type& operator=(__hash_value_type&& __v) 560262801Sdim {__nc = std::move(__v.__nc); return *this;} 561262801Sdim 562262801Sdim _LIBCPP_INLINE_VISIBILITY 563262801Sdim ~__hash_value_type() {__cc.~value_type();} 564262801Sdim}; 565262801Sdim 566262801Sdim#else 567262801Sdim 568262801Sdimtemplate <class _Key, class _Tp> 569262801Sdimstruct __hash_value_type 570262801Sdim{ 571262801Sdim typedef _Key key_type; 572262801Sdim typedef _Tp mapped_type; 573262801Sdim typedef pair<const key_type, mapped_type> value_type; 574262801Sdim 575262801Sdim value_type __cc; 576262801Sdim 577262801Sdim _LIBCPP_INLINE_VISIBILITY 578262801Sdim __hash_value_type() {} 579262801Sdim 580262801Sdim template <class _A0> 581262801Sdim _LIBCPP_INLINE_VISIBILITY 582262801Sdim __hash_value_type(const _A0& __a0) 583262801Sdim : __cc(__a0) {} 584262801Sdim 585262801Sdim template <class _A0, class _A1> 586262801Sdim _LIBCPP_INLINE_VISIBILITY 587262801Sdim __hash_value_type(const _A0& __a0, const _A1& __a1) 588262801Sdim : __cc(__a0, __a1) {} 589262801Sdim}; 590262801Sdim 591262801Sdim#endif 592262801Sdim 593227825Stheraventemplate <class _HashIterator> 594262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator 595227825Stheraven{ 596227825Stheraven _HashIterator __i_; 597227825Stheraven 598227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 599253159Stheraven typedef const typename _HashIterator::value_type::value_type::first_type key_type; 600253159Stheraven typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 601227825Stheravenpublic: 602227825Stheraven typedef forward_iterator_tag iterator_category; 603227825Stheraven typedef pair<key_type, mapped_type> value_type; 604227825Stheraven typedef typename _HashIterator::difference_type difference_type; 605227825Stheraven typedef value_type& reference; 606227825Stheraven typedef typename __pointer_traits::template 607227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 608227825Stheraven rebind<value_type> 609227825Stheraven#else 610227825Stheraven rebind<value_type>::other 611227825Stheraven#endif 612227825Stheraven pointer; 613227825Stheraven 614227825Stheraven _LIBCPP_INLINE_VISIBILITY 615227825Stheraven __hash_map_iterator() _NOEXCEPT {} 616227825Stheraven 617227825Stheraven _LIBCPP_INLINE_VISIBILITY 618227825Stheraven __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 619227825Stheraven 620227825Stheraven _LIBCPP_INLINE_VISIBILITY 621253159Stheraven reference operator*() const {return __i_->__cc;} 622227825Stheraven _LIBCPP_INLINE_VISIBILITY 623253159Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 624227825Stheraven 625227825Stheraven _LIBCPP_INLINE_VISIBILITY 626227825Stheraven __hash_map_iterator& operator++() {++__i_; return *this;} 627227825Stheraven _LIBCPP_INLINE_VISIBILITY 628227825Stheraven __hash_map_iterator operator++(int) 629227825Stheraven { 630227825Stheraven __hash_map_iterator __t(*this); 631227825Stheraven ++(*this); 632227825Stheraven return __t; 633227825Stheraven } 634227825Stheraven 635227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 636227825Stheraven bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 637227825Stheraven {return __x.__i_ == __y.__i_;} 638227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 639227825Stheraven bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 640227825Stheraven {return __x.__i_ != __y.__i_;} 641227825Stheraven 642262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 643262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 644262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 645262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 646262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 647227825Stheraven}; 648227825Stheraven 649227825Stheraventemplate <class _HashIterator> 650262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator 651227825Stheraven{ 652227825Stheraven _HashIterator __i_; 653227825Stheraven 654227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 655253159Stheraven typedef const typename _HashIterator::value_type::value_type::first_type key_type; 656253159Stheraven typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 657227825Stheravenpublic: 658227825Stheraven typedef forward_iterator_tag iterator_category; 659227825Stheraven typedef pair<key_type, mapped_type> value_type; 660227825Stheraven typedef typename _HashIterator::difference_type difference_type; 661227825Stheraven typedef const value_type& reference; 662227825Stheraven typedef typename __pointer_traits::template 663227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 664227825Stheraven rebind<const value_type> 665227825Stheraven#else 666227825Stheraven rebind<const value_type>::other 667227825Stheraven#endif 668227825Stheraven pointer; 669227825Stheraven 670227825Stheraven _LIBCPP_INLINE_VISIBILITY 671227825Stheraven __hash_map_const_iterator() _NOEXCEPT {} 672227825Stheraven 673227825Stheraven _LIBCPP_INLINE_VISIBILITY 674227825Stheraven __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 675227825Stheraven _LIBCPP_INLINE_VISIBILITY 676227825Stheraven __hash_map_const_iterator( 677227825Stheraven __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 678227825Stheraven _NOEXCEPT 679227825Stheraven : __i_(__i.__i_) {} 680227825Stheraven 681227825Stheraven _LIBCPP_INLINE_VISIBILITY 682253159Stheraven reference operator*() const {return __i_->__cc;} 683227825Stheraven _LIBCPP_INLINE_VISIBILITY 684253159Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 685227825Stheraven 686227825Stheraven _LIBCPP_INLINE_VISIBILITY 687227825Stheraven __hash_map_const_iterator& operator++() {++__i_; return *this;} 688227825Stheraven _LIBCPP_INLINE_VISIBILITY 689227825Stheraven __hash_map_const_iterator operator++(int) 690227825Stheraven { 691227825Stheraven __hash_map_const_iterator __t(*this); 692227825Stheraven ++(*this); 693227825Stheraven return __t; 694227825Stheraven } 695227825Stheraven 696227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 697227825Stheraven bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 698227825Stheraven {return __x.__i_ == __y.__i_;} 699227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 700227825Stheraven bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 701227825Stheraven {return __x.__i_ != __y.__i_;} 702227825Stheraven 703262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 704262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 705262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 706262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 707227825Stheraven}; 708227825Stheraven 709227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 710227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 711262801Sdimclass _LIBCPP_TYPE_VIS_ONLY unordered_map 712227825Stheraven{ 713227825Stheravenpublic: 714227825Stheraven // types 715227825Stheraven typedef _Key key_type; 716227825Stheraven typedef _Tp mapped_type; 717227825Stheraven typedef _Hash hasher; 718227825Stheraven typedef _Pred key_equal; 719227825Stheraven typedef _Alloc allocator_type; 720227825Stheraven typedef pair<const key_type, mapped_type> value_type; 721253159Stheraven typedef pair<key_type, mapped_type> __nc_value_type; 722227825Stheraven typedef value_type& reference; 723227825Stheraven typedef const value_type& const_reference; 724262801Sdim static_assert((is_same<value_type, typename allocator_type::value_type>::value), 725262801Sdim "Invalid allocator::value_type"); 726227825Stheraven 727227825Stheravenprivate: 728262801Sdim typedef __hash_value_type<key_type, mapped_type> __value_type; 729253159Stheraven typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 730253159Stheraven typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 731227825Stheraven typedef typename allocator_traits<allocator_type>::template 732227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 733227825Stheraven rebind_alloc<__value_type> 734227825Stheraven#else 735227825Stheraven rebind_alloc<__value_type>::other 736227825Stheraven#endif 737227825Stheraven __allocator_type; 738227825Stheraven 739227825Stheraven typedef __hash_table<__value_type, __hasher, 740227825Stheraven __key_equal, __allocator_type> __table; 741227825Stheraven 742227825Stheraven __table __table_; 743227825Stheraven 744227825Stheraven typedef typename __table::__node_pointer __node_pointer; 745227825Stheraven typedef typename __table::__node_const_pointer __node_const_pointer; 746227825Stheraven typedef typename __table::__node_traits __node_traits; 747227825Stheraven typedef typename __table::__node_allocator __node_allocator; 748227825Stheraven typedef typename __table::__node __node; 749232950Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 750232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 751227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 752227825Stheravenpublic: 753227825Stheraven typedef typename __alloc_traits::pointer pointer; 754227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 755227825Stheraven typedef typename __alloc_traits::size_type size_type; 756227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 757227825Stheraven 758227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 759227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 760227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 761227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 762227825Stheraven 763227825Stheraven _LIBCPP_INLINE_VISIBILITY 764227825Stheraven unordered_map() 765227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 766262801Sdim { 767262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 768262801Sdim __get_db()->__insert_c(this); 769262801Sdim#endif 770262801Sdim } 771227825Stheraven explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 772227825Stheraven const key_equal& __eql = key_equal()); 773227825Stheraven unordered_map(size_type __n, const hasher& __hf, 774227825Stheraven const key_equal& __eql, 775227825Stheraven const allocator_type& __a); 776227825Stheraven template <class _InputIterator> 777227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last); 778227825Stheraven template <class _InputIterator> 779227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 780227825Stheraven size_type __n, const hasher& __hf = hasher(), 781227825Stheraven const key_equal& __eql = key_equal()); 782227825Stheraven template <class _InputIterator> 783227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 784227825Stheraven size_type __n, const hasher& __hf, 785227825Stheraven const key_equal& __eql, 786227825Stheraven const allocator_type& __a); 787227825Stheraven explicit unordered_map(const allocator_type& __a); 788227825Stheraven unordered_map(const unordered_map& __u); 789227825Stheraven unordered_map(const unordered_map& __u, const allocator_type& __a); 790227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 791227825Stheraven unordered_map(unordered_map&& __u) 792227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 793227825Stheraven unordered_map(unordered_map&& __u, const allocator_type& __a); 794227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 795227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 796227825Stheraven unordered_map(initializer_list<value_type> __il); 797227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 798227825Stheraven const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 799227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 800227825Stheraven const hasher& __hf, const key_equal& __eql, 801227825Stheraven const allocator_type& __a); 802227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 803262801Sdim#if _LIBCPP_STD_VER > 11 804262801Sdim _LIBCPP_INLINE_VISIBILITY 805262801Sdim unordered_map(size_type __n, const allocator_type& __a) 806262801Sdim : unordered_map(__n, hasher(), key_equal(), __a) {} 807262801Sdim _LIBCPP_INLINE_VISIBILITY 808262801Sdim unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a) 809262801Sdim : unordered_map(__n, __hf, key_equal(), __a) {} 810262801Sdim template <class _InputIterator> 811262801Sdim _LIBCPP_INLINE_VISIBILITY 812262801Sdim unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 813262801Sdim : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} 814262801Sdim template <class _InputIterator> 815262801Sdim _LIBCPP_INLINE_VISIBILITY 816262801Sdim unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 817262801Sdim const allocator_type& __a) 818262801Sdim : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} 819262801Sdim _LIBCPP_INLINE_VISIBILITY 820262801Sdim unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 821262801Sdim : unordered_map(__il, __n, hasher(), key_equal(), __a) {} 822262801Sdim _LIBCPP_INLINE_VISIBILITY 823262801Sdim unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 824262801Sdim const allocator_type& __a) 825262801Sdim : unordered_map(__il, __n, __hf, key_equal(), __a) {} 826262801Sdim#endif 827227825Stheraven // ~unordered_map() = default; 828227825Stheraven _LIBCPP_INLINE_VISIBILITY 829227825Stheraven unordered_map& operator=(const unordered_map& __u) 830227825Stheraven { 831253159Stheraven#if __cplusplus >= 201103L 832227825Stheraven __table_ = __u.__table_; 833253159Stheraven#else 834263272Sdim if (this != &__u) { 835263272Sdim __table_.clear(); 836263272Sdim __table_.hash_function() = __u.__table_.hash_function(); 837263272Sdim __table_.key_eq() = __u.__table_.key_eq(); 838263272Sdim __table_.max_load_factor() = __u.__table_.max_load_factor(); 839263272Sdim __table_.__copy_assign_alloc(__u.__table_); 840263272Sdim insert(__u.begin(), __u.end()); 841263272Sdim } 842253159Stheraven#endif 843227825Stheraven return *this; 844227825Stheraven } 845227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 846227825Stheraven unordered_map& operator=(unordered_map&& __u) 847227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 848227825Stheraven#endif 849227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 850227825Stheraven unordered_map& operator=(initializer_list<value_type> __il); 851227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 852227825Stheraven 853227825Stheraven _LIBCPP_INLINE_VISIBILITY 854227825Stheraven allocator_type get_allocator() const _NOEXCEPT 855227825Stheraven {return allocator_type(__table_.__node_alloc());} 856227825Stheraven 857227825Stheraven _LIBCPP_INLINE_VISIBILITY 858227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 859227825Stheraven _LIBCPP_INLINE_VISIBILITY 860227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 861227825Stheraven _LIBCPP_INLINE_VISIBILITY 862227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 863227825Stheraven 864227825Stheraven _LIBCPP_INLINE_VISIBILITY 865227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 866227825Stheraven _LIBCPP_INLINE_VISIBILITY 867227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 868227825Stheraven _LIBCPP_INLINE_VISIBILITY 869227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 870227825Stheraven _LIBCPP_INLINE_VISIBILITY 871227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 872227825Stheraven _LIBCPP_INLINE_VISIBILITY 873227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 874227825Stheraven _LIBCPP_INLINE_VISIBILITY 875227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 876227825Stheraven 877227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 878227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 879227825Stheraven 880241903Sdim template <class... _Args> 881241903Sdim pair<iterator, bool> emplace(_Args&&... __args); 882227825Stheraven 883241903Sdim template <class... _Args> 884227825Stheraven _LIBCPP_INLINE_VISIBILITY 885262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 886262801Sdim iterator emplace_hint(const_iterator __p, _Args&&... __args) 887262801Sdim { 888262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 889262801Sdim "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" 890262801Sdim " referring to this unordered_map"); 891262801Sdim return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 892262801Sdim } 893262801Sdim#else 894241903Sdim iterator emplace_hint(const_iterator, _Args&&... __args) 895241903Sdim {return emplace(_VSTD::forward<_Args>(__args)...).first;} 896262801Sdim#endif 897227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 898227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 899227825Stheraven _LIBCPP_INLINE_VISIBILITY 900227825Stheraven pair<iterator, bool> insert(const value_type& __x) 901227825Stheraven {return __table_.__insert_unique(__x);} 902227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 903232950Stheraven template <class _Pp, 904232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 905227825Stheraven _LIBCPP_INLINE_VISIBILITY 906232950Stheraven pair<iterator, bool> insert(_Pp&& __x) 907232950Stheraven {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 908227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 909227825Stheraven _LIBCPP_INLINE_VISIBILITY 910262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 911262801Sdim iterator insert(const_iterator __p, const value_type& __x) 912262801Sdim { 913262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 914262801Sdim "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" 915262801Sdim " referring to this unordered_map"); 916262801Sdim return insert(__x).first; 917262801Sdim } 918262801Sdim#else 919227825Stheraven iterator insert(const_iterator, const value_type& __x) 920227825Stheraven {return insert(__x).first;} 921262801Sdim#endif 922227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 923232950Stheraven template <class _Pp, 924232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 925227825Stheraven _LIBCPP_INLINE_VISIBILITY 926262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 927262801Sdim iterator insert(const_iterator __p, _Pp&& __x) 928262801Sdim { 929262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 930262801Sdim "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" 931262801Sdim " referring to this unordered_map"); 932262801Sdim return insert(_VSTD::forward<_Pp>(__x)).first; 933262801Sdim } 934262801Sdim#else 935232950Stheraven iterator insert(const_iterator, _Pp&& __x) 936232950Stheraven {return insert(_VSTD::forward<_Pp>(__x)).first;} 937262801Sdim#endif 938227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 939227825Stheraven template <class _InputIterator> 940227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 941227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 942227825Stheraven _LIBCPP_INLINE_VISIBILITY 943227825Stheraven void insert(initializer_list<value_type> __il) 944227825Stheraven {insert(__il.begin(), __il.end());} 945227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 946227825Stheraven 947227825Stheraven _LIBCPP_INLINE_VISIBILITY 948227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 949227825Stheraven _LIBCPP_INLINE_VISIBILITY 950227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 951227825Stheraven _LIBCPP_INLINE_VISIBILITY 952227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 953227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 954227825Stheraven _LIBCPP_INLINE_VISIBILITY 955227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 956227825Stheraven 957227825Stheraven _LIBCPP_INLINE_VISIBILITY 958227825Stheraven void swap(unordered_map& __u) 959227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 960227825Stheraven {__table_.swap(__u.__table_);} 961227825Stheraven 962227825Stheraven _LIBCPP_INLINE_VISIBILITY 963227825Stheraven hasher hash_function() const 964227825Stheraven {return __table_.hash_function().hash_function();} 965227825Stheraven _LIBCPP_INLINE_VISIBILITY 966227825Stheraven key_equal key_eq() const 967227825Stheraven {return __table_.key_eq().key_eq();} 968227825Stheraven 969227825Stheraven _LIBCPP_INLINE_VISIBILITY 970227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 971227825Stheraven _LIBCPP_INLINE_VISIBILITY 972227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 973227825Stheraven _LIBCPP_INLINE_VISIBILITY 974227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 975227825Stheraven _LIBCPP_INLINE_VISIBILITY 976227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 977227825Stheraven {return __table_.__equal_range_unique(__k);} 978227825Stheraven _LIBCPP_INLINE_VISIBILITY 979227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 980227825Stheraven {return __table_.__equal_range_unique(__k);} 981227825Stheraven 982227825Stheraven mapped_type& operator[](const key_type& __k); 983227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 984227825Stheraven mapped_type& operator[](key_type&& __k); 985227825Stheraven#endif 986227825Stheraven 987227825Stheraven mapped_type& at(const key_type& __k); 988227825Stheraven const mapped_type& at(const key_type& __k) const; 989227825Stheraven 990227825Stheraven _LIBCPP_INLINE_VISIBILITY 991227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 992227825Stheraven _LIBCPP_INLINE_VISIBILITY 993227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 994227825Stheraven 995227825Stheraven _LIBCPP_INLINE_VISIBILITY 996227825Stheraven size_type bucket_size(size_type __n) const 997227825Stheraven {return __table_.bucket_size(__n);} 998227825Stheraven _LIBCPP_INLINE_VISIBILITY 999227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1000227825Stheraven 1001227825Stheraven _LIBCPP_INLINE_VISIBILITY 1002227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1003227825Stheraven _LIBCPP_INLINE_VISIBILITY 1004227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1005227825Stheraven _LIBCPP_INLINE_VISIBILITY 1006227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1007227825Stheraven _LIBCPP_INLINE_VISIBILITY 1008227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1009227825Stheraven _LIBCPP_INLINE_VISIBILITY 1010227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1011227825Stheraven _LIBCPP_INLINE_VISIBILITY 1012227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1013227825Stheraven 1014227825Stheraven _LIBCPP_INLINE_VISIBILITY 1015227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1016227825Stheraven _LIBCPP_INLINE_VISIBILITY 1017227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1018227825Stheraven _LIBCPP_INLINE_VISIBILITY 1019227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1020227825Stheraven _LIBCPP_INLINE_VISIBILITY 1021227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1022227825Stheraven _LIBCPP_INLINE_VISIBILITY 1023227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1024227825Stheraven 1025262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1026262801Sdim 1027262801Sdim bool __dereferenceable(const const_iterator* __i) const 1028262801Sdim {return __table_.__dereferenceable(&__i->__i_);} 1029262801Sdim bool __decrementable(const const_iterator* __i) const 1030262801Sdim {return __table_.__decrementable(&__i->__i_);} 1031262801Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1032262801Sdim {return __table_.__addable(&__i->__i_, __n);} 1033262801Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1034262801Sdim {return __table_.__addable(&__i->__i_, __n);} 1035262801Sdim 1036262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1037262801Sdim 1038227825Stheravenprivate: 1039227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1040241903Sdim __node_holder __construct_node(); 1041241903Sdim template <class _A0> 1042253159Stheraven __node_holder 1043241903Sdim __construct_node(_A0&& __a0); 1044253159Stheraven __node_holder __construct_node_with_key(key_type&& __k); 1045227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1046241903Sdim template <class _A0, class _A1, class ..._Args> 1047241903Sdim __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1048227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1049253159Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1050253159Stheraven __node_holder __construct_node_with_key(const key_type& __k); 1051227825Stheraven}; 1052227825Stheraven 1053227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1054227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1055227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1056227825Stheraven : __table_(__hf, __eql) 1057227825Stheraven{ 1058262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1059262801Sdim __get_db()->__insert_c(this); 1060262801Sdim#endif 1061227825Stheraven __table_.rehash(__n); 1062227825Stheraven} 1063227825Stheraven 1064227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1065227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1066227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1067227825Stheraven const allocator_type& __a) 1068227825Stheraven : __table_(__hf, __eql, __a) 1069227825Stheraven{ 1070262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1071262801Sdim __get_db()->__insert_c(this); 1072262801Sdim#endif 1073227825Stheraven __table_.rehash(__n); 1074227825Stheraven} 1075227825Stheraven 1076227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1077227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1078227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1079227825Stheraven const allocator_type& __a) 1080227825Stheraven : __table_(__a) 1081227825Stheraven{ 1082262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1083262801Sdim __get_db()->__insert_c(this); 1084262801Sdim#endif 1085227825Stheraven} 1086227825Stheraven 1087227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1088227825Stheraventemplate <class _InputIterator> 1089227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1090227825Stheraven _InputIterator __first, _InputIterator __last) 1091227825Stheraven{ 1092262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1093262801Sdim __get_db()->__insert_c(this); 1094262801Sdim#endif 1095227825Stheraven insert(__first, __last); 1096227825Stheraven} 1097227825Stheraven 1098227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1099227825Stheraventemplate <class _InputIterator> 1100227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1101227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1102227825Stheraven const hasher& __hf, const key_equal& __eql) 1103227825Stheraven : __table_(__hf, __eql) 1104227825Stheraven{ 1105262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1106262801Sdim __get_db()->__insert_c(this); 1107262801Sdim#endif 1108227825Stheraven __table_.rehash(__n); 1109227825Stheraven insert(__first, __last); 1110227825Stheraven} 1111227825Stheraven 1112227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1113227825Stheraventemplate <class _InputIterator> 1114227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1115227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1116227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1117227825Stheraven : __table_(__hf, __eql, __a) 1118227825Stheraven{ 1119262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1120262801Sdim __get_db()->__insert_c(this); 1121262801Sdim#endif 1122227825Stheraven __table_.rehash(__n); 1123227825Stheraven insert(__first, __last); 1124227825Stheraven} 1125227825Stheraven 1126227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1127227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1128227825Stheraven const unordered_map& __u) 1129227825Stheraven : __table_(__u.__table_) 1130227825Stheraven{ 1131262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1132262801Sdim __get_db()->__insert_c(this); 1133262801Sdim#endif 1134227825Stheraven __table_.rehash(__u.bucket_count()); 1135227825Stheraven insert(__u.begin(), __u.end()); 1136227825Stheraven} 1137227825Stheraven 1138227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1139227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1140227825Stheraven const unordered_map& __u, const allocator_type& __a) 1141227825Stheraven : __table_(__u.__table_, __a) 1142227825Stheraven{ 1143262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1144262801Sdim __get_db()->__insert_c(this); 1145262801Sdim#endif 1146227825Stheraven __table_.rehash(__u.bucket_count()); 1147227825Stheraven insert(__u.begin(), __u.end()); 1148227825Stheraven} 1149227825Stheraven 1150227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1151227825Stheraven 1152227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1153227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1154227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1155227825Stheraven unordered_map&& __u) 1156227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1157227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1158227825Stheraven{ 1159262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1160262801Sdim __get_db()->__insert_c(this); 1161262801Sdim __get_db()->swap(this, &__u); 1162262801Sdim#endif 1163227825Stheraven} 1164227825Stheraven 1165227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1166227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1167227825Stheraven unordered_map&& __u, const allocator_type& __a) 1168227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1169227825Stheraven{ 1170262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1171262801Sdim __get_db()->__insert_c(this); 1172262801Sdim#endif 1173227825Stheraven if (__a != __u.get_allocator()) 1174227825Stheraven { 1175227825Stheraven iterator __i = __u.begin(); 1176227825Stheraven while (__u.size() != 0) 1177227825Stheraven __table_.__insert_unique( 1178227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1179227825Stheraven ); 1180227825Stheraven } 1181262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1182262801Sdim else 1183262801Sdim __get_db()->swap(this, &__u); 1184262801Sdim#endif 1185227825Stheraven} 1186227825Stheraven 1187227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1188227825Stheraven 1189227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1190227825Stheraven 1191227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1192227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1193227825Stheraven initializer_list<value_type> __il) 1194227825Stheraven{ 1195262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1196262801Sdim __get_db()->__insert_c(this); 1197262801Sdim#endif 1198227825Stheraven insert(__il.begin(), __il.end()); 1199227825Stheraven} 1200227825Stheraven 1201227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1202227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1203227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1204227825Stheraven const key_equal& __eql) 1205227825Stheraven : __table_(__hf, __eql) 1206227825Stheraven{ 1207262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1208262801Sdim __get_db()->__insert_c(this); 1209262801Sdim#endif 1210227825Stheraven __table_.rehash(__n); 1211227825Stheraven insert(__il.begin(), __il.end()); 1212227825Stheraven} 1213227825Stheraven 1214227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1215227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1216227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1217227825Stheraven const key_equal& __eql, const allocator_type& __a) 1218227825Stheraven : __table_(__hf, __eql, __a) 1219227825Stheraven{ 1220262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1221262801Sdim __get_db()->__insert_c(this); 1222262801Sdim#endif 1223227825Stheraven __table_.rehash(__n); 1224227825Stheraven insert(__il.begin(), __il.end()); 1225227825Stheraven} 1226227825Stheraven 1227227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1228227825Stheraven 1229227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1230227825Stheraven 1231227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1232227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1233227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1234227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1235227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1236227825Stheraven{ 1237227825Stheraven __table_ = _VSTD::move(__u.__table_); 1238227825Stheraven return *this; 1239227825Stheraven} 1240227825Stheraven 1241227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1242227825Stheraven 1243227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1244227825Stheraven 1245227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1246227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1247227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1248227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1249227825Stheraven initializer_list<value_type> __il) 1250227825Stheraven{ 1251227825Stheraven __table_.__assign_unique(__il.begin(), __il.end()); 1252227825Stheraven return *this; 1253227825Stheraven} 1254227825Stheraven 1255227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1256227825Stheraven 1257227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1258227825Stheraven 1259227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1260227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1261241903Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1262227825Stheraven{ 1263227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1264232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1265241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1266227825Stheraven __h.get_deleter().__first_constructed = true; 1267227825Stheraven __h.get_deleter().__second_constructed = true; 1268227825Stheraven return __h; 1269227825Stheraven} 1270227825Stheraven 1271227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1272241903Sdimtemplate <class _A0> 1273253159Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1274227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1275227825Stheraven{ 1276227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1277232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1278227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1279227825Stheraven _VSTD::forward<_A0>(__a0)); 1280227825Stheraven __h.get_deleter().__first_constructed = true; 1281227825Stheraven __h.get_deleter().__second_constructed = true; 1282227825Stheraven return __h; 1283227825Stheraven} 1284227825Stheraven 1285241903Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1286253159Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1287253159Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k) 1288241903Sdim{ 1289241903Sdim __node_allocator& __na = __table_.__node_alloc(); 1290241903Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1291253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k)); 1292241903Sdim __h.get_deleter().__first_constructed = true; 1293253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1294241903Sdim __h.get_deleter().__second_constructed = true; 1295262801Sdim return __h; 1296241903Sdim} 1297241903Sdim 1298227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1299227825Stheraven 1300227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1301241903Sdimtemplate <class _A0, class _A1, class ..._Args> 1302241903Sdimtypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1303241903Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1304241903Sdim _A1&& __a1, 1305241903Sdim _Args&&... __args) 1306241903Sdim{ 1307241903Sdim __node_allocator& __na = __table_.__node_alloc(); 1308241903Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1309241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1310241903Sdim _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1311241903Sdim _VSTD::forward<_Args>(__args)...); 1312241903Sdim __h.get_deleter().__first_constructed = true; 1313241903Sdim __h.get_deleter().__second_constructed = true; 1314241903Sdim return __h; 1315241903Sdim} 1316241903Sdim 1317241903Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1318241903Sdimtemplate <class... _Args> 1319227825Stheravenpair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1320241903Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1321227825Stheraven{ 1322241903Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1323227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1324227825Stheraven if (__r.second) 1325227825Stheraven __h.release(); 1326227825Stheraven return __r; 1327227825Stheraven} 1328227825Stheraven 1329227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1330253159Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1331227825Stheraven 1332227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1333227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1334253159Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1335227825Stheraven{ 1336227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1337232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1338253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1339227825Stheraven __h.get_deleter().__first_constructed = true; 1340253159Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1341227825Stheraven __h.get_deleter().__second_constructed = true; 1342262801Sdim return _VSTD::move(__h); // explicitly moved for C++03 1343227825Stheraven} 1344227825Stheraven 1345227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1346227825Stheraventemplate <class _InputIterator> 1347227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1348227825Stheravenvoid 1349227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1350227825Stheraven _InputIterator __last) 1351227825Stheraven{ 1352227825Stheraven for (; __first != __last; ++__first) 1353227825Stheraven __table_.__insert_unique(*__first); 1354227825Stheraven} 1355227825Stheraven 1356227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1357227825Stheraven_Tp& 1358227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1359227825Stheraven{ 1360227825Stheraven iterator __i = find(__k); 1361227825Stheraven if (__i != end()) 1362227825Stheraven return __i->second; 1363253159Stheraven __node_holder __h = __construct_node_with_key(__k); 1364227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1365227825Stheraven __h.release(); 1366227825Stheraven return __r.first->second; 1367227825Stheraven} 1368227825Stheraven 1369227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1370227825Stheraven 1371227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1372227825Stheraven_Tp& 1373227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1374227825Stheraven{ 1375227825Stheraven iterator __i = find(__k); 1376227825Stheraven if (__i != end()) 1377227825Stheraven return __i->second; 1378253159Stheraven __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); 1379227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1380227825Stheraven __h.release(); 1381227825Stheraven return __r.first->second; 1382227825Stheraven} 1383227825Stheraven 1384227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1385227825Stheraven 1386227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1387227825Stheraven_Tp& 1388227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1389227825Stheraven{ 1390227825Stheraven iterator __i = find(__k); 1391227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1392227825Stheraven if (__i == end()) 1393227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1394227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1395227825Stheraven return __i->second; 1396227825Stheraven} 1397227825Stheraven 1398227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1399227825Stheravenconst _Tp& 1400227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1401227825Stheraven{ 1402227825Stheraven const_iterator __i = find(__k); 1403227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1404227825Stheraven if (__i == end()) 1405227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1406227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1407227825Stheraven return __i->second; 1408227825Stheraven} 1409227825Stheraven 1410227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1411227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1412227825Stheravenvoid 1413227825Stheravenswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1414227825Stheraven unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1415227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1416227825Stheraven{ 1417227825Stheraven __x.swap(__y); 1418227825Stheraven} 1419227825Stheraven 1420227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1421227825Stheravenbool 1422227825Stheravenoperator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1423227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1424227825Stheraven{ 1425227825Stheraven if (__x.size() != __y.size()) 1426227825Stheraven return false; 1427227825Stheraven typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1428227825Stheraven const_iterator; 1429227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1430227825Stheraven __i != __ex; ++__i) 1431227825Stheraven { 1432227825Stheraven const_iterator __j = __y.find(__i->first); 1433227825Stheraven if (__j == __ey || !(*__i == *__j)) 1434227825Stheraven return false; 1435227825Stheraven } 1436227825Stheraven return true; 1437227825Stheraven} 1438227825Stheraven 1439227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1440227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1441227825Stheravenbool 1442227825Stheravenoperator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1443227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1444227825Stheraven{ 1445227825Stheraven return !(__x == __y); 1446227825Stheraven} 1447227825Stheraven 1448227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1449227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 1450262801Sdimclass _LIBCPP_TYPE_VIS_ONLY unordered_multimap 1451227825Stheraven{ 1452227825Stheravenpublic: 1453227825Stheraven // types 1454227825Stheraven typedef _Key key_type; 1455227825Stheraven typedef _Tp mapped_type; 1456227825Stheraven typedef _Hash hasher; 1457227825Stheraven typedef _Pred key_equal; 1458227825Stheraven typedef _Alloc allocator_type; 1459227825Stheraven typedef pair<const key_type, mapped_type> value_type; 1460253159Stheraven typedef pair<key_type, mapped_type> __nc_value_type; 1461227825Stheraven typedef value_type& reference; 1462227825Stheraven typedef const value_type& const_reference; 1463262801Sdim static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1464262801Sdim "Invalid allocator::value_type"); 1465227825Stheraven 1466227825Stheravenprivate: 1467262801Sdim typedef __hash_value_type<key_type, mapped_type> __value_type; 1468253159Stheraven typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 1469253159Stheraven typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 1470227825Stheraven typedef typename allocator_traits<allocator_type>::template 1471227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1472227825Stheraven rebind_alloc<__value_type> 1473227825Stheraven#else 1474227825Stheraven rebind_alloc<__value_type>::other 1475227825Stheraven#endif 1476227825Stheraven __allocator_type; 1477227825Stheraven 1478227825Stheraven typedef __hash_table<__value_type, __hasher, 1479227825Stheraven __key_equal, __allocator_type> __table; 1480227825Stheraven 1481227825Stheraven __table __table_; 1482227825Stheraven 1483227825Stheraven typedef typename __table::__node_traits __node_traits; 1484227825Stheraven typedef typename __table::__node_allocator __node_allocator; 1485227825Stheraven typedef typename __table::__node __node; 1486232950Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 1487232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 1488227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 1489227825Stheravenpublic: 1490227825Stheraven typedef typename __alloc_traits::pointer pointer; 1491227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 1492227825Stheraven typedef typename __alloc_traits::size_type size_type; 1493227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 1494227825Stheraven 1495227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 1496227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1497227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1498227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1499227825Stheraven 1500227825Stheraven _LIBCPP_INLINE_VISIBILITY 1501227825Stheraven unordered_multimap() 1502227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1503262801Sdim { 1504262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1505262801Sdim __get_db()->__insert_c(this); 1506262801Sdim#endif 1507262801Sdim } 1508227825Stheraven explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1509227825Stheraven const key_equal& __eql = key_equal()); 1510227825Stheraven unordered_multimap(size_type __n, const hasher& __hf, 1511227825Stheraven const key_equal& __eql, 1512227825Stheraven const allocator_type& __a); 1513227825Stheraven template <class _InputIterator> 1514227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last); 1515227825Stheraven template <class _InputIterator> 1516227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1517227825Stheraven size_type __n, const hasher& __hf = hasher(), 1518227825Stheraven const key_equal& __eql = key_equal()); 1519227825Stheraven template <class _InputIterator> 1520227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1521227825Stheraven size_type __n, const hasher& __hf, 1522227825Stheraven const key_equal& __eql, 1523227825Stheraven const allocator_type& __a); 1524227825Stheraven explicit unordered_multimap(const allocator_type& __a); 1525227825Stheraven unordered_multimap(const unordered_multimap& __u); 1526227825Stheraven unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1527227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1528227825Stheraven unordered_multimap(unordered_multimap&& __u) 1529227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1530227825Stheraven unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1531227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1532227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1533227825Stheraven unordered_multimap(initializer_list<value_type> __il); 1534227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1535227825Stheraven const hasher& __hf = hasher(), 1536227825Stheraven const key_equal& __eql = key_equal()); 1537227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1538227825Stheraven const hasher& __hf, const key_equal& __eql, 1539227825Stheraven const allocator_type& __a); 1540227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1541262801Sdim#if _LIBCPP_STD_VER > 11 1542262801Sdim _LIBCPP_INLINE_VISIBILITY 1543262801Sdim unordered_multimap(size_type __n, const allocator_type& __a) 1544262801Sdim : unordered_multimap(__n, hasher(), key_equal(), __a) {} 1545262801Sdim _LIBCPP_INLINE_VISIBILITY 1546262801Sdim unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 1547262801Sdim : unordered_multimap(__n, __hf, key_equal(), __a) {} 1548262801Sdim template <class _InputIterator> 1549262801Sdim _LIBCPP_INLINE_VISIBILITY 1550262801Sdim unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1551262801Sdim : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 1552262801Sdim template <class _InputIterator> 1553262801Sdim _LIBCPP_INLINE_VISIBILITY 1554262801Sdim unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 1555262801Sdim const allocator_type& __a) 1556262801Sdim : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 1557262801Sdim _LIBCPP_INLINE_VISIBILITY 1558262801Sdim unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1559262801Sdim : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 1560262801Sdim _LIBCPP_INLINE_VISIBILITY 1561262801Sdim unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1562262801Sdim const allocator_type& __a) 1563262801Sdim : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 1564262801Sdim#endif 1565227825Stheraven // ~unordered_multimap() = default; 1566227825Stheraven _LIBCPP_INLINE_VISIBILITY 1567227825Stheraven unordered_multimap& operator=(const unordered_multimap& __u) 1568227825Stheraven { 1569253159Stheraven#if __cplusplus >= 201103L 1570227825Stheraven __table_ = __u.__table_; 1571253159Stheraven#else 1572263272Sdim if (this != &__u) { 1573263272Sdim __table_.clear(); 1574263272Sdim __table_.hash_function() = __u.__table_.hash_function(); 1575263272Sdim __table_.key_eq() = __u.__table_.key_eq(); 1576263272Sdim __table_.max_load_factor() = __u.__table_.max_load_factor(); 1577263272Sdim __table_.__copy_assign_alloc(__u.__table_); 1578263272Sdim insert(__u.begin(), __u.end()); 1579263272Sdim } 1580253159Stheraven#endif 1581227825Stheraven return *this; 1582227825Stheraven } 1583227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1584227825Stheraven unordered_multimap& operator=(unordered_multimap&& __u) 1585227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1586227825Stheraven#endif 1587227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1588227825Stheraven unordered_multimap& operator=(initializer_list<value_type> __il); 1589227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1590227825Stheraven 1591227825Stheraven _LIBCPP_INLINE_VISIBILITY 1592227825Stheraven allocator_type get_allocator() const _NOEXCEPT 1593227825Stheraven {return allocator_type(__table_.__node_alloc());} 1594227825Stheraven 1595227825Stheraven _LIBCPP_INLINE_VISIBILITY 1596227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1597227825Stheraven _LIBCPP_INLINE_VISIBILITY 1598227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 1599227825Stheraven _LIBCPP_INLINE_VISIBILITY 1600227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1601227825Stheraven 1602227825Stheraven _LIBCPP_INLINE_VISIBILITY 1603227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 1604227825Stheraven _LIBCPP_INLINE_VISIBILITY 1605227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 1606227825Stheraven _LIBCPP_INLINE_VISIBILITY 1607227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1608227825Stheraven _LIBCPP_INLINE_VISIBILITY 1609227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 1610227825Stheraven _LIBCPP_INLINE_VISIBILITY 1611227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1612227825Stheraven _LIBCPP_INLINE_VISIBILITY 1613227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 1614227825Stheraven 1615227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1616227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1617227825Stheraven 1618241903Sdim template <class... _Args> 1619241903Sdim iterator emplace(_Args&&... __args); 1620227825Stheraven 1621241903Sdim template <class... _Args> 1622241903Sdim iterator emplace_hint(const_iterator __p, _Args&&... __args); 1623227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1624227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1625227825Stheraven _LIBCPP_INLINE_VISIBILITY 1626227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1627227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1628232950Stheraven template <class _Pp, 1629232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1630227825Stheraven _LIBCPP_INLINE_VISIBILITY 1631232950Stheraven iterator insert(_Pp&& __x) 1632232950Stheraven {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1633227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1634227825Stheraven _LIBCPP_INLINE_VISIBILITY 1635227825Stheraven iterator insert(const_iterator __p, const value_type& __x) 1636227825Stheraven {return __table_.__insert_multi(__p.__i_, __x);} 1637227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1638232950Stheraven template <class _Pp, 1639232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1640227825Stheraven _LIBCPP_INLINE_VISIBILITY 1641232950Stheraven iterator insert(const_iterator __p, _Pp&& __x) 1642232950Stheraven {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1643227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1644227825Stheraven template <class _InputIterator> 1645227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 1646227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1647227825Stheraven _LIBCPP_INLINE_VISIBILITY 1648227825Stheraven void insert(initializer_list<value_type> __il) 1649227825Stheraven {insert(__il.begin(), __il.end());} 1650227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1651227825Stheraven 1652227825Stheraven _LIBCPP_INLINE_VISIBILITY 1653227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1654227825Stheraven _LIBCPP_INLINE_VISIBILITY 1655227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1656227825Stheraven _LIBCPP_INLINE_VISIBILITY 1657227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 1658227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 1659227825Stheraven _LIBCPP_INLINE_VISIBILITY 1660227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 1661227825Stheraven 1662227825Stheraven _LIBCPP_INLINE_VISIBILITY 1663227825Stheraven void swap(unordered_multimap& __u) 1664227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1665227825Stheraven {__table_.swap(__u.__table_);} 1666227825Stheraven 1667227825Stheraven _LIBCPP_INLINE_VISIBILITY 1668227825Stheraven hasher hash_function() const 1669227825Stheraven {return __table_.hash_function().hash_function();} 1670227825Stheraven _LIBCPP_INLINE_VISIBILITY 1671227825Stheraven key_equal key_eq() const 1672227825Stheraven {return __table_.key_eq().key_eq();} 1673227825Stheraven 1674227825Stheraven _LIBCPP_INLINE_VISIBILITY 1675227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 1676227825Stheraven _LIBCPP_INLINE_VISIBILITY 1677227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1678227825Stheraven _LIBCPP_INLINE_VISIBILITY 1679227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1680227825Stheraven _LIBCPP_INLINE_VISIBILITY 1681227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 1682227825Stheraven {return __table_.__equal_range_multi(__k);} 1683227825Stheraven _LIBCPP_INLINE_VISIBILITY 1684227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1685227825Stheraven {return __table_.__equal_range_multi(__k);} 1686227825Stheraven 1687227825Stheraven _LIBCPP_INLINE_VISIBILITY 1688227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1689227825Stheraven _LIBCPP_INLINE_VISIBILITY 1690227825Stheraven size_type max_bucket_count() const _NOEXCEPT 1691227825Stheraven {return __table_.max_bucket_count();} 1692227825Stheraven 1693227825Stheraven _LIBCPP_INLINE_VISIBILITY 1694227825Stheraven size_type bucket_size(size_type __n) const 1695227825Stheraven {return __table_.bucket_size(__n);} 1696227825Stheraven _LIBCPP_INLINE_VISIBILITY 1697227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1698227825Stheraven 1699227825Stheraven _LIBCPP_INLINE_VISIBILITY 1700227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1701227825Stheraven _LIBCPP_INLINE_VISIBILITY 1702227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1703227825Stheraven _LIBCPP_INLINE_VISIBILITY 1704227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1705227825Stheraven _LIBCPP_INLINE_VISIBILITY 1706227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1707227825Stheraven _LIBCPP_INLINE_VISIBILITY 1708227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1709227825Stheraven _LIBCPP_INLINE_VISIBILITY 1710227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1711227825Stheraven 1712227825Stheraven _LIBCPP_INLINE_VISIBILITY 1713227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1714227825Stheraven _LIBCPP_INLINE_VISIBILITY 1715227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1716227825Stheraven _LIBCPP_INLINE_VISIBILITY 1717227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1718227825Stheraven _LIBCPP_INLINE_VISIBILITY 1719227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1720227825Stheraven _LIBCPP_INLINE_VISIBILITY 1721227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1722227825Stheraven 1723262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1724262801Sdim 1725262801Sdim bool __dereferenceable(const const_iterator* __i) const 1726262801Sdim {return __table_.__dereferenceable(&__i->__i_);} 1727262801Sdim bool __decrementable(const const_iterator* __i) const 1728262801Sdim {return __table_.__decrementable(&__i->__i_);} 1729262801Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1730262801Sdim {return __table_.__addable(&__i->__i_, __n);} 1731262801Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1732262801Sdim {return __table_.__addable(&__i->__i_, __n);} 1733262801Sdim 1734262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1735262801Sdim 1736227825Stheravenprivate: 1737241903Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1738241903Sdim __node_holder __construct_node(); 1739241903Sdim template <class _A0> 1740253159Stheraven __node_holder 1741241903Sdim __construct_node(_A0&& __a0); 1742241903Sdim#ifndef _LIBCPP_HAS_NO_VARIADICS 1743241903Sdim template <class _A0, class _A1, class ..._Args> 1744241903Sdim __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1745241903Sdim#endif // _LIBCPP_HAS_NO_VARIADICS 1746241903Sdim#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1747227825Stheraven}; 1748227825Stheraven 1749227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1750227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1751227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1752227825Stheraven : __table_(__hf, __eql) 1753227825Stheraven{ 1754262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1755262801Sdim __get_db()->__insert_c(this); 1756262801Sdim#endif 1757227825Stheraven __table_.rehash(__n); 1758227825Stheraven} 1759227825Stheraven 1760227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1761227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1762227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1763227825Stheraven const allocator_type& __a) 1764227825Stheraven : __table_(__hf, __eql, __a) 1765227825Stheraven{ 1766262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1767262801Sdim __get_db()->__insert_c(this); 1768262801Sdim#endif 1769227825Stheraven __table_.rehash(__n); 1770227825Stheraven} 1771227825Stheraven 1772227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1773227825Stheraventemplate <class _InputIterator> 1774227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1775227825Stheraven _InputIterator __first, _InputIterator __last) 1776227825Stheraven{ 1777262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1778262801Sdim __get_db()->__insert_c(this); 1779262801Sdim#endif 1780227825Stheraven insert(__first, __last); 1781227825Stheraven} 1782227825Stheraven 1783227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1784227825Stheraventemplate <class _InputIterator> 1785227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1786227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1787227825Stheraven const hasher& __hf, const key_equal& __eql) 1788227825Stheraven : __table_(__hf, __eql) 1789227825Stheraven{ 1790262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1791262801Sdim __get_db()->__insert_c(this); 1792262801Sdim#endif 1793227825Stheraven __table_.rehash(__n); 1794227825Stheraven insert(__first, __last); 1795227825Stheraven} 1796227825Stheraven 1797227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1798227825Stheraventemplate <class _InputIterator> 1799227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1800227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1801227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1802227825Stheraven : __table_(__hf, __eql, __a) 1803227825Stheraven{ 1804262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1805262801Sdim __get_db()->__insert_c(this); 1806262801Sdim#endif 1807227825Stheraven __table_.rehash(__n); 1808227825Stheraven insert(__first, __last); 1809227825Stheraven} 1810227825Stheraven 1811227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1812227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1813227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1814227825Stheraven const allocator_type& __a) 1815227825Stheraven : __table_(__a) 1816227825Stheraven{ 1817262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1818262801Sdim __get_db()->__insert_c(this); 1819262801Sdim#endif 1820227825Stheraven} 1821227825Stheraven 1822227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1823227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1824227825Stheraven const unordered_multimap& __u) 1825227825Stheraven : __table_(__u.__table_) 1826227825Stheraven{ 1827262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1828262801Sdim __get_db()->__insert_c(this); 1829262801Sdim#endif 1830227825Stheraven __table_.rehash(__u.bucket_count()); 1831227825Stheraven insert(__u.begin(), __u.end()); 1832227825Stheraven} 1833227825Stheraven 1834227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1835227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1836227825Stheraven const unordered_multimap& __u, const allocator_type& __a) 1837227825Stheraven : __table_(__u.__table_, __a) 1838227825Stheraven{ 1839262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1840262801Sdim __get_db()->__insert_c(this); 1841262801Sdim#endif 1842227825Stheraven __table_.rehash(__u.bucket_count()); 1843227825Stheraven insert(__u.begin(), __u.end()); 1844227825Stheraven} 1845227825Stheraven 1846227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1847227825Stheraven 1848227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1849227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1850227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1851227825Stheraven unordered_multimap&& __u) 1852227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1853227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1854227825Stheraven{ 1855262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1856262801Sdim __get_db()->__insert_c(this); 1857262801Sdim __get_db()->swap(this, &__u); 1858262801Sdim#endif 1859227825Stheraven} 1860227825Stheraven 1861227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1862227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1863227825Stheraven unordered_multimap&& __u, const allocator_type& __a) 1864227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1865227825Stheraven{ 1866262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1867262801Sdim __get_db()->__insert_c(this); 1868262801Sdim#endif 1869227825Stheraven if (__a != __u.get_allocator()) 1870227825Stheraven { 1871227825Stheraven iterator __i = __u.begin(); 1872227825Stheraven while (__u.size() != 0) 1873262801Sdim { 1874227825Stheraven __table_.__insert_multi( 1875227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1876227825Stheraven ); 1877262801Sdim } 1878227825Stheraven } 1879262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1880262801Sdim else 1881262801Sdim __get_db()->swap(this, &__u); 1882262801Sdim#endif 1883227825Stheraven} 1884227825Stheraven 1885227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1886227825Stheraven 1887227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1888227825Stheraven 1889227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1890227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1891227825Stheraven initializer_list<value_type> __il) 1892227825Stheraven{ 1893262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1894262801Sdim __get_db()->__insert_c(this); 1895262801Sdim#endif 1896227825Stheraven insert(__il.begin(), __il.end()); 1897227825Stheraven} 1898227825Stheraven 1899227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1900227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1901227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1902227825Stheraven const key_equal& __eql) 1903227825Stheraven : __table_(__hf, __eql) 1904227825Stheraven{ 1905262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1906262801Sdim __get_db()->__insert_c(this); 1907262801Sdim#endif 1908227825Stheraven __table_.rehash(__n); 1909227825Stheraven insert(__il.begin(), __il.end()); 1910227825Stheraven} 1911227825Stheraven 1912227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1913227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1914227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1915227825Stheraven const key_equal& __eql, const allocator_type& __a) 1916227825Stheraven : __table_(__hf, __eql, __a) 1917227825Stheraven{ 1918262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1919262801Sdim __get_db()->__insert_c(this); 1920262801Sdim#endif 1921227825Stheraven __table_.rehash(__n); 1922227825Stheraven insert(__il.begin(), __il.end()); 1923227825Stheraven} 1924227825Stheraven 1925227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1926227825Stheraven 1927227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1928227825Stheraven 1929227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1930227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1931227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1932227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1933227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1934227825Stheraven{ 1935227825Stheraven __table_ = _VSTD::move(__u.__table_); 1936227825Stheraven return *this; 1937227825Stheraven} 1938227825Stheraven 1939227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1940227825Stheraven 1941227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1942227825Stheraven 1943227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1944227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1945227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1946227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1947227825Stheraven initializer_list<value_type> __il) 1948227825Stheraven{ 1949227825Stheraven __table_.__assign_multi(__il.begin(), __il.end()); 1950227825Stheraven return *this; 1951227825Stheraven} 1952227825Stheraven 1953227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1954227825Stheraven 1955227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1956227825Stheraven 1957227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1958227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1959241903Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1960227825Stheraven{ 1961227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1962232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1963241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1964227825Stheraven __h.get_deleter().__first_constructed = true; 1965227825Stheraven __h.get_deleter().__second_constructed = true; 1966227825Stheraven return __h; 1967227825Stheraven} 1968227825Stheraven 1969227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1970241903Sdimtemplate <class _A0> 1971253159Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1972227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1973227825Stheraven{ 1974227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1975232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1976227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1977227825Stheraven _VSTD::forward<_A0>(__a0)); 1978227825Stheraven __h.get_deleter().__first_constructed = true; 1979227825Stheraven __h.get_deleter().__second_constructed = true; 1980227825Stheraven return __h; 1981227825Stheraven} 1982227825Stheraven 1983227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1984227825Stheraven 1985227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1986241903Sdimtemplate <class _A0, class _A1, class ..._Args> 1987241903Sdimtypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1988241903Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 1989241903Sdim _A0&& __a0, _A1&& __a1, _Args&&... __args) 1990241903Sdim{ 1991241903Sdim __node_allocator& __na = __table_.__node_alloc(); 1992241903Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1993241903Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1994241903Sdim _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1995241903Sdim _VSTD::forward<_Args>(__args)...); 1996241903Sdim __h.get_deleter().__first_constructed = true; 1997241903Sdim __h.get_deleter().__second_constructed = true; 1998241903Sdim return __h; 1999241903Sdim} 2000241903Sdim 2001241903Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2002241903Sdimtemplate <class... _Args> 2003227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2004241903Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 2005227825Stheraven{ 2006241903Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2007227825Stheraven iterator __r = __table_.__node_insert_multi(__h.get()); 2008227825Stheraven __h.release(); 2009227825Stheraven return __r; 2010227825Stheraven} 2011227825Stheraven 2012227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2013241903Sdimtemplate <class... _Args> 2014227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2015227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 2016241903Sdim const_iterator __p, _Args&&... __args) 2017227825Stheraven{ 2018241903Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2019227825Stheraven iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 2020227825Stheraven __h.release(); 2021227825Stheraven return __r; 2022227825Stheraven} 2023227825Stheraven 2024227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 2025227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2026227825Stheraven 2027227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2028227825Stheraventemplate <class _InputIterator> 2029227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2030227825Stheravenvoid 2031227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 2032227825Stheraven _InputIterator __last) 2033227825Stheraven{ 2034227825Stheraven for (; __first != __last; ++__first) 2035227825Stheraven __table_.__insert_multi(*__first); 2036227825Stheraven} 2037227825Stheraven 2038227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2039227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2040227825Stheravenvoid 2041227825Stheravenswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2042227825Stheraven unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2043227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2044227825Stheraven{ 2045227825Stheraven __x.swap(__y); 2046227825Stheraven} 2047227825Stheraven 2048227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2049227825Stheravenbool 2050227825Stheravenoperator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2051227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2052227825Stheraven{ 2053227825Stheraven if (__x.size() != __y.size()) 2054227825Stheraven return false; 2055227825Stheraven typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 2056227825Stheraven const_iterator; 2057227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 2058227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 2059227825Stheraven { 2060227825Stheraven _EqRng __xeq = __x.equal_range(__i->first); 2061227825Stheraven _EqRng __yeq = __y.equal_range(__i->first); 2062227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 2063227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 2064227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2065227825Stheraven return false; 2066227825Stheraven __i = __xeq.second; 2067227825Stheraven } 2068227825Stheraven return true; 2069227825Stheraven} 2070227825Stheraven 2071227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2072227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2073227825Stheravenbool 2074227825Stheravenoperator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2075227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2076227825Stheraven{ 2077227825Stheraven return !(__x == __y); 2078227825Stheraven} 2079227825Stheraven 2080227825Stheraven_LIBCPP_END_NAMESPACE_STD 2081227825Stheraven 2082227825Stheraven#endif // _LIBCPP_UNORDERED_MAP 2083