unordered_map revision 288943
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()); 72261272Sdim unordered_map(size_type n, const allocator_type& a) 73261272Sdim : unordered_map(n, hasher(), key_equal(), a) {} // C++14 74261272Sdim unordered_map(size_type n, const hasher& hf, const allocator_type& a) 75261272Sdim : unordered_map(n, hf, key_equal(), a) {} // C++14 76261272Sdim template <class InputIterator> 77261272Sdim unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 78261272Sdim : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14 79261272Sdim template <class InputIterator> 80261272Sdim unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, 81261272Sdim const allocator_type& a) 82261272Sdim : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14 83261272Sdim unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a) 84261272Sdim : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 85261272Sdim unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf, 86261272Sdim const allocator_type& a) 87261272Sdim : 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 125288943Sdim template <class... Args> 126288943Sdim pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17 127288943Sdim template <class... Args> 128288943Sdim pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17 129288943Sdim template <class... Args> 130288943Sdim iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17 131288943Sdim template <class... Args> 132288943Sdim iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17 133288943Sdim template <class M> 134288943Sdim pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17 135288943Sdim template <class M> 136288943Sdim pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17 137288943Sdim template <class M> 138288943Sdim iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17 139288943Sdim template <class M> 140288943Sdim iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17 141288943Sdim 142227825Stheraven iterator erase(const_iterator position); 143288943Sdim iterator erase(iterator position); // C++14 144227825Stheraven size_type erase(const key_type& k); 145227825Stheraven iterator erase(const_iterator first, const_iterator last); 146227825Stheraven void clear() noexcept; 147227825Stheraven 148227825Stheraven void swap(unordered_map&) 149227825Stheraven noexcept( 150227825Stheraven (!allocator_type::propagate_on_container_swap::value || 151227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 152227825Stheraven __is_nothrow_swappable<hasher>::value && 153227825Stheraven __is_nothrow_swappable<key_equal>::value); 154227825Stheraven 155227825Stheraven hasher hash_function() const; 156227825Stheraven key_equal key_eq() const; 157227825Stheraven 158227825Stheraven iterator find(const key_type& k); 159227825Stheraven const_iterator find(const key_type& k) const; 160227825Stheraven size_type count(const key_type& k) const; 161227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 162227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 163227825Stheraven 164227825Stheraven mapped_type& operator[](const key_type& k); 165227825Stheraven mapped_type& operator[](key_type&& k); 166227825Stheraven 167227825Stheraven mapped_type& at(const key_type& k); 168227825Stheraven const mapped_type& at(const key_type& k) const; 169227825Stheraven 170227825Stheraven size_type bucket_count() const noexcept; 171227825Stheraven size_type max_bucket_count() const noexcept; 172227825Stheraven 173227825Stheraven size_type bucket_size(size_type n) const; 174227825Stheraven size_type bucket(const key_type& k) const; 175227825Stheraven 176227825Stheraven local_iterator begin(size_type n); 177227825Stheraven local_iterator end(size_type n); 178227825Stheraven const_local_iterator begin(size_type n) const; 179227825Stheraven const_local_iterator end(size_type n) const; 180227825Stheraven const_local_iterator cbegin(size_type n) const; 181227825Stheraven const_local_iterator cend(size_type n) const; 182227825Stheraven 183227825Stheraven float load_factor() const noexcept; 184227825Stheraven float max_load_factor() const noexcept; 185227825Stheraven void max_load_factor(float z); 186227825Stheraven void rehash(size_type n); 187227825Stheraven void reserve(size_type n); 188227825Stheraven}; 189227825Stheraven 190227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 191227825Stheraven void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x, 192227825Stheraven unordered_map<Key, T, Hash, Pred, Alloc>& y) 193227825Stheraven noexcept(noexcept(x.swap(y))); 194227825Stheraven 195227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 196227825Stheraven bool 197227825Stheraven operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 198227825Stheraven const unordered_map<Key, T, Hash, Pred, Alloc>& y); 199227825Stheraven 200227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 201227825Stheraven bool 202227825Stheraven operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 203227825Stheraven const unordered_map<Key, T, Hash, Pred, Alloc>& y); 204227825Stheraven 205227825Stheraventemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 206227825Stheraven class Alloc = allocator<pair<const Key, T>>> 207227825Stheravenclass unordered_multimap 208227825Stheraven{ 209227825Stheravenpublic: 210227825Stheraven // types 211227825Stheraven typedef Key key_type; 212227825Stheraven typedef T mapped_type; 213227825Stheraven typedef Hash hasher; 214227825Stheraven typedef Pred key_equal; 215227825Stheraven typedef Alloc allocator_type; 216227825Stheraven typedef pair<const key_type, mapped_type> value_type; 217227825Stheraven typedef value_type& reference; 218227825Stheraven typedef const value_type& const_reference; 219227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 220227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 221227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 222227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 223227825Stheraven 224227825Stheraven typedef /unspecified/ iterator; 225227825Stheraven typedef /unspecified/ const_iterator; 226227825Stheraven typedef /unspecified/ local_iterator; 227227825Stheraven typedef /unspecified/ const_local_iterator; 228227825Stheraven 229227825Stheraven unordered_multimap() 230227825Stheraven noexcept( 231227825Stheraven is_nothrow_default_constructible<hasher>::value && 232227825Stheraven is_nothrow_default_constructible<key_equal>::value && 233227825Stheraven is_nothrow_default_constructible<allocator_type>::value); 234227825Stheraven explicit unordered_multimap(size_type n, const hasher& hf = hasher(), 235227825Stheraven const key_equal& eql = key_equal(), 236227825Stheraven const allocator_type& a = allocator_type()); 237227825Stheraven template <class InputIterator> 238227825Stheraven unordered_multimap(InputIterator f, InputIterator l, 239227825Stheraven size_type n = 0, const hasher& hf = hasher(), 240227825Stheraven const key_equal& eql = key_equal(), 241227825Stheraven const allocator_type& a = allocator_type()); 242227825Stheraven explicit unordered_multimap(const allocator_type&); 243227825Stheraven unordered_multimap(const unordered_multimap&); 244227825Stheraven unordered_multimap(const unordered_multimap&, const Allocator&); 245227825Stheraven unordered_multimap(unordered_multimap&&) 246227825Stheraven noexcept( 247227825Stheraven is_nothrow_move_constructible<hasher>::value && 248227825Stheraven is_nothrow_move_constructible<key_equal>::value && 249227825Stheraven is_nothrow_move_constructible<allocator_type>::value); 250227825Stheraven unordered_multimap(unordered_multimap&&, const Allocator&); 251227825Stheraven unordered_multimap(initializer_list<value_type>, size_type n = 0, 252227825Stheraven const hasher& hf = hasher(), const key_equal& eql = key_equal(), 253227825Stheraven const allocator_type& a = allocator_type()); 254261272Sdim unordered_multimap(size_type n, const allocator_type& a) 255261272Sdim : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14 256261272Sdim unordered_multimap(size_type n, const hasher& hf, const allocator_type& a) 257261272Sdim : unordered_multimap(n, hf, key_equal(), a) {} // C++14 258261272Sdim template <class InputIterator> 259261272Sdim unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 260261272Sdim : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14 261261272Sdim template <class InputIterator> 262261272Sdim unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, 263261272Sdim const allocator_type& a) 264261272Sdim : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14 265261272Sdim unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a) 266261272Sdim : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 267261272Sdim unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf, 268261272Sdim const allocator_type& a) 269261272Sdim : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14 270227825Stheraven ~unordered_multimap(); 271227825Stheraven unordered_multimap& operator=(const unordered_multimap&); 272227825Stheraven unordered_multimap& operator=(unordered_multimap&&) 273227825Stheraven noexcept( 274227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 275227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 276227825Stheraven is_nothrow_move_assignable<hasher>::value && 277227825Stheraven is_nothrow_move_assignable<key_equal>::value); 278227825Stheraven unordered_multimap& operator=(initializer_list<value_type>); 279227825Stheraven 280227825Stheraven allocator_type get_allocator() const noexcept; 281227825Stheraven 282227825Stheraven bool empty() const noexcept; 283227825Stheraven size_type size() const noexcept; 284227825Stheraven size_type max_size() const noexcept; 285227825Stheraven 286227825Stheraven iterator begin() noexcept; 287227825Stheraven iterator end() noexcept; 288227825Stheraven const_iterator begin() const noexcept; 289227825Stheraven const_iterator end() const noexcept; 290227825Stheraven const_iterator cbegin() const noexcept; 291227825Stheraven const_iterator cend() const noexcept; 292227825Stheraven 293227825Stheraven template <class... Args> 294227825Stheraven iterator emplace(Args&&... args); 295227825Stheraven template <class... Args> 296227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 297227825Stheraven iterator insert(const value_type& obj); 298227825Stheraven template <class P> 299227825Stheraven iterator insert(P&& obj); 300227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 301227825Stheraven template <class P> 302227825Stheraven iterator insert(const_iterator hint, P&& obj); 303227825Stheraven template <class InputIterator> 304227825Stheraven void insert(InputIterator first, InputIterator last); 305227825Stheraven void insert(initializer_list<value_type>); 306227825Stheraven 307227825Stheraven iterator erase(const_iterator position); 308288943Sdim iterator erase(iterator position); // C++14 309227825Stheraven size_type erase(const key_type& k); 310227825Stheraven iterator erase(const_iterator first, const_iterator last); 311227825Stheraven void clear() noexcept; 312227825Stheraven 313227825Stheraven void swap(unordered_multimap&) 314227825Stheraven noexcept( 315227825Stheraven (!allocator_type::propagate_on_container_swap::value || 316227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 317227825Stheraven __is_nothrow_swappable<hasher>::value && 318227825Stheraven __is_nothrow_swappable<key_equal>::value); 319227825Stheraven 320227825Stheraven hasher hash_function() const; 321227825Stheraven key_equal key_eq() const; 322227825Stheraven 323227825Stheraven iterator find(const key_type& k); 324227825Stheraven const_iterator find(const key_type& k) const; 325227825Stheraven size_type count(const key_type& k) const; 326227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 327227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 328227825Stheraven 329227825Stheraven size_type bucket_count() const noexcept; 330227825Stheraven size_type max_bucket_count() const noexcept; 331227825Stheraven 332227825Stheraven size_type bucket_size(size_type n) const; 333227825Stheraven size_type bucket(const key_type& k) const; 334227825Stheraven 335227825Stheraven local_iterator begin(size_type n); 336227825Stheraven local_iterator end(size_type n); 337227825Stheraven const_local_iterator begin(size_type n) const; 338227825Stheraven const_local_iterator end(size_type n) const; 339227825Stheraven const_local_iterator cbegin(size_type n) const; 340227825Stheraven const_local_iterator cend(size_type n) const; 341227825Stheraven 342227825Stheraven float load_factor() const noexcept; 343227825Stheraven float max_load_factor() const noexcept; 344227825Stheraven void max_load_factor(float z); 345227825Stheraven void rehash(size_type n); 346227825Stheraven void reserve(size_type n); 347227825Stheraven}; 348227825Stheraven 349227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 350227825Stheraven void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 351227825Stheraven unordered_multimap<Key, T, Hash, Pred, Alloc>& y) 352227825Stheraven noexcept(noexcept(x.swap(y))); 353227825Stheraven 354227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 355227825Stheraven bool 356227825Stheraven operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 357227825Stheraven const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 358227825Stheraven 359227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 360227825Stheraven bool 361227825Stheraven operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 362227825Stheraven const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 363227825Stheraven 364227825Stheraven} // std 365227825Stheraven 366227825Stheraven*/ 367227825Stheraven 368227825Stheraven#include <__config> 369227825Stheraven#include <__hash_table> 370227825Stheraven#include <functional> 371227825Stheraven#include <stdexcept> 372227825Stheraven 373276792Sdim#include <__debug> 374276792Sdim 375227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 376227825Stheraven#pragma GCC system_header 377227825Stheraven#endif 378227825Stheraven 379227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 380227825Stheraven 381288943Sdimtemplate <class _Key, class _Cp, class _Hash, 382288943Sdim bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value 383232924Stheraven > 384227825Stheravenclass __unordered_map_hasher 385227825Stheraven : private _Hash 386227825Stheraven{ 387227825Stheravenpublic: 388227825Stheraven _LIBCPP_INLINE_VISIBILITY 389227825Stheraven __unordered_map_hasher() 390227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 391227825Stheraven : _Hash() {} 392227825Stheraven _LIBCPP_INLINE_VISIBILITY 393227825Stheraven __unordered_map_hasher(const _Hash& __h) 394227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 395227825Stheraven : _Hash(__h) {} 396227825Stheraven _LIBCPP_INLINE_VISIBILITY 397227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return *this;} 398227825Stheraven _LIBCPP_INLINE_VISIBILITY 399232924Stheraven size_t operator()(const _Cp& __x) const 400253146Stheraven {return static_cast<const _Hash&>(*this)(__x.__cc.first);} 401232924Stheraven _LIBCPP_INLINE_VISIBILITY 402232924Stheraven size_t operator()(const _Key& __x) const 403227825Stheraven {return static_cast<const _Hash&>(*this)(__x);} 404288943Sdim void swap(__unordered_map_hasher&__y) 405288943Sdim _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) 406288943Sdim { 407288943Sdim using _VSTD::swap; 408288943Sdim swap(static_cast<const _Hash&>(*this), static_cast<const _Hash&>(__y)); 409288943Sdim } 410227825Stheraven}; 411227825Stheraven 412253146Stheraventemplate <class _Key, class _Cp, class _Hash> 413253146Stheravenclass __unordered_map_hasher<_Key, _Cp, _Hash, false> 414227825Stheraven{ 415227825Stheraven _Hash __hash_; 416232924Stheraven 417227825Stheravenpublic: 418227825Stheraven _LIBCPP_INLINE_VISIBILITY 419227825Stheraven __unordered_map_hasher() 420227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 421227825Stheraven : __hash_() {} 422227825Stheraven _LIBCPP_INLINE_VISIBILITY 423227825Stheraven __unordered_map_hasher(const _Hash& __h) 424227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 425227825Stheraven : __hash_(__h) {} 426227825Stheraven _LIBCPP_INLINE_VISIBILITY 427227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 428227825Stheraven _LIBCPP_INLINE_VISIBILITY 429232924Stheraven size_t operator()(const _Cp& __x) const 430253146Stheraven {return __hash_(__x.__cc.first);} 431232924Stheraven _LIBCPP_INLINE_VISIBILITY 432232924Stheraven size_t operator()(const _Key& __x) const 433227825Stheraven {return __hash_(__x);} 434288943Sdim void swap(__unordered_map_hasher&__y) 435288943Sdim _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) 436288943Sdim { 437288943Sdim using _VSTD::swap; 438288943Sdim swap(__hash_, __y.__hash_); 439288943Sdim } 440227825Stheraven}; 441227825Stheraven 442288943Sdimtemplate <class _Key, class _Cp, class _Hash, bool __b> 443288943Sdiminline _LIBCPP_INLINE_VISIBILITY 444288943Sdimvoid 445288943Sdimswap(__unordered_map_hasher<_Key, _Cp, _Hash, __b>& __x, 446288943Sdim __unordered_map_hasher<_Key, _Cp, _Hash, __b>& __y) 447288943Sdim _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 448288943Sdim{ 449288943Sdim __x.swap(__y); 450288943Sdim} 451288943Sdim 452288943Sdimtemplate <class _Key, class _Cp, class _Pred, 453288943Sdim bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value 454232924Stheraven > 455227825Stheravenclass __unordered_map_equal 456227825Stheraven : private _Pred 457227825Stheraven{ 458227825Stheravenpublic: 459227825Stheraven _LIBCPP_INLINE_VISIBILITY 460227825Stheraven __unordered_map_equal() 461227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 462227825Stheraven : _Pred() {} 463227825Stheraven _LIBCPP_INLINE_VISIBILITY 464227825Stheraven __unordered_map_equal(const _Pred& __p) 465227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 466227825Stheraven : _Pred(__p) {} 467227825Stheraven _LIBCPP_INLINE_VISIBILITY 468227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return *this;} 469227825Stheraven _LIBCPP_INLINE_VISIBILITY 470232924Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 471253146Stheraven {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);} 472232924Stheraven _LIBCPP_INLINE_VISIBILITY 473232924Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 474253146Stheraven {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);} 475232924Stheraven _LIBCPP_INLINE_VISIBILITY 476232924Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 477253146Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);} 478288943Sdim void swap(__unordered_map_equal&__y) 479288943Sdim _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) 480288943Sdim { 481288943Sdim using _VSTD::swap; 482288943Sdim swap(static_cast<const _Pred&>(*this), static_cast<const _Pred&>(__y)); 483288943Sdim } 484227825Stheraven}; 485227825Stheraven 486253146Stheraventemplate <class _Key, class _Cp, class _Pred> 487253146Stheravenclass __unordered_map_equal<_Key, _Cp, _Pred, false> 488227825Stheraven{ 489227825Stheraven _Pred __pred_; 490232924Stheraven 491227825Stheravenpublic: 492227825Stheraven _LIBCPP_INLINE_VISIBILITY 493227825Stheraven __unordered_map_equal() 494227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 495227825Stheraven : __pred_() {} 496227825Stheraven _LIBCPP_INLINE_VISIBILITY 497227825Stheraven __unordered_map_equal(const _Pred& __p) 498227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 499227825Stheraven : __pred_(__p) {} 500227825Stheraven _LIBCPP_INLINE_VISIBILITY 501227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 502227825Stheraven _LIBCPP_INLINE_VISIBILITY 503232924Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 504253146Stheraven {return __pred_(__x.__cc.first, __y.__cc.first);} 505232924Stheraven _LIBCPP_INLINE_VISIBILITY 506232924Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 507253146Stheraven {return __pred_(__x.__cc.first, __y);} 508232924Stheraven _LIBCPP_INLINE_VISIBILITY 509232924Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 510253146Stheraven {return __pred_(__x, __y.__cc.first);} 511288943Sdim void swap(__unordered_map_equal&__y) 512288943Sdim _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) 513288943Sdim { 514288943Sdim using _VSTD::swap; 515288943Sdim swap(__pred_, __y.__pred_); 516288943Sdim } 517227825Stheraven}; 518227825Stheraven 519288943Sdimtemplate <class _Key, class _Cp, class _Pred, bool __b> 520288943Sdiminline _LIBCPP_INLINE_VISIBILITY 521288943Sdimvoid 522288943Sdimswap(__unordered_map_equal<_Key, _Cp, _Pred, __b>& __x, 523288943Sdim __unordered_map_equal<_Key, _Cp, _Pred, __b>& __y) 524288943Sdim _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 525288943Sdim{ 526288943Sdim __x.swap(__y); 527288943Sdim} 528288943Sdim 529227825Stheraventemplate <class _Alloc> 530227825Stheravenclass __hash_map_node_destructor 531227825Stheraven{ 532227825Stheraven typedef _Alloc allocator_type; 533227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 534227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 535227825Stheravenpublic: 536227825Stheraven typedef typename __alloc_traits::pointer pointer; 537227825Stheravenprivate: 538253146Stheraven typedef typename value_type::value_type::first_type first_type; 539253146Stheraven typedef typename value_type::value_type::second_type second_type; 540227825Stheraven 541227825Stheraven allocator_type& __na_; 542227825Stheraven 543227825Stheraven __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 544227825Stheraven 545227825Stheravenpublic: 546227825Stheraven bool __first_constructed; 547227825Stheraven bool __second_constructed; 548227825Stheraven 549227825Stheraven _LIBCPP_INLINE_VISIBILITY 550227825Stheraven explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 551227825Stheraven : __na_(__na), 552227825Stheraven __first_constructed(false), 553227825Stheraven __second_constructed(false) 554227825Stheraven {} 555227825Stheraven 556227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 557227825Stheraven _LIBCPP_INLINE_VISIBILITY 558227825Stheraven __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 559227825Stheraven _NOEXCEPT 560227825Stheraven : __na_(__x.__na_), 561227825Stheraven __first_constructed(__x.__value_constructed), 562227825Stheraven __second_constructed(__x.__value_constructed) 563227825Stheraven { 564227825Stheraven __x.__value_constructed = false; 565227825Stheraven } 566227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 567227825Stheraven _LIBCPP_INLINE_VISIBILITY 568227825Stheraven __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 569227825Stheraven : __na_(__x.__na_), 570227825Stheraven __first_constructed(__x.__value_constructed), 571227825Stheraven __second_constructed(__x.__value_constructed) 572227825Stheraven { 573227825Stheraven const_cast<bool&>(__x.__value_constructed) = false; 574227825Stheraven } 575227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 576227825Stheraven 577227825Stheraven _LIBCPP_INLINE_VISIBILITY 578227825Stheraven void operator()(pointer __p) _NOEXCEPT 579227825Stheraven { 580227825Stheraven if (__second_constructed) 581253146Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second)); 582227825Stheraven if (__first_constructed) 583253146Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first)); 584227825Stheraven if (__p) 585227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 586227825Stheraven } 587227825Stheraven}; 588227825Stheraven 589261272Sdim#if __cplusplus >= 201103L 590261272Sdim 591261272Sdimtemplate <class _Key, class _Tp> 592261272Sdimunion __hash_value_type 593261272Sdim{ 594261272Sdim typedef _Key key_type; 595261272Sdim typedef _Tp mapped_type; 596261272Sdim typedef pair<const key_type, mapped_type> value_type; 597261272Sdim typedef pair<key_type, mapped_type> __nc_value_type; 598261272Sdim 599261272Sdim value_type __cc; 600261272Sdim __nc_value_type __nc; 601261272Sdim 602261272Sdim template <class ..._Args> 603261272Sdim _LIBCPP_INLINE_VISIBILITY 604261272Sdim __hash_value_type(_Args&& ...__args) 605261272Sdim : __cc(std::forward<_Args>(__args)...) {} 606261272Sdim 607261272Sdim _LIBCPP_INLINE_VISIBILITY 608261272Sdim __hash_value_type(const __hash_value_type& __v) 609261272Sdim : __cc(__v.__cc) {} 610261272Sdim 611261272Sdim _LIBCPP_INLINE_VISIBILITY 612261272Sdim __hash_value_type(__hash_value_type&& __v) 613288943Sdim : __nc(_VSTD::move(__v.__nc)) {} 614261272Sdim 615261272Sdim _LIBCPP_INLINE_VISIBILITY 616261272Sdim __hash_value_type& operator=(const __hash_value_type& __v) 617261272Sdim {__nc = __v.__cc; return *this;} 618261272Sdim 619261272Sdim _LIBCPP_INLINE_VISIBILITY 620261272Sdim __hash_value_type& operator=(__hash_value_type&& __v) 621288943Sdim {__nc = _VSTD::move(__v.__nc); return *this;} 622261272Sdim 623261272Sdim _LIBCPP_INLINE_VISIBILITY 624261272Sdim ~__hash_value_type() {__cc.~value_type();} 625261272Sdim}; 626261272Sdim 627261272Sdim#else 628261272Sdim 629261272Sdimtemplate <class _Key, class _Tp> 630261272Sdimstruct __hash_value_type 631261272Sdim{ 632261272Sdim typedef _Key key_type; 633261272Sdim typedef _Tp mapped_type; 634261272Sdim typedef pair<const key_type, mapped_type> value_type; 635261272Sdim 636261272Sdim value_type __cc; 637261272Sdim 638261272Sdim _LIBCPP_INLINE_VISIBILITY 639261272Sdim __hash_value_type() {} 640261272Sdim 641261272Sdim template <class _A0> 642261272Sdim _LIBCPP_INLINE_VISIBILITY 643261272Sdim __hash_value_type(const _A0& __a0) 644261272Sdim : __cc(__a0) {} 645261272Sdim 646261272Sdim template <class _A0, class _A1> 647261272Sdim _LIBCPP_INLINE_VISIBILITY 648261272Sdim __hash_value_type(const _A0& __a0, const _A1& __a1) 649261272Sdim : __cc(__a0, __a1) {} 650261272Sdim}; 651261272Sdim 652261272Sdim#endif 653261272Sdim 654227825Stheraventemplate <class _HashIterator> 655261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator 656227825Stheraven{ 657227825Stheraven _HashIterator __i_; 658227825Stheraven 659227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 660253146Stheraven typedef const typename _HashIterator::value_type::value_type::first_type key_type; 661253146Stheraven typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 662227825Stheravenpublic: 663227825Stheraven typedef forward_iterator_tag iterator_category; 664227825Stheraven typedef pair<key_type, mapped_type> value_type; 665227825Stheraven typedef typename _HashIterator::difference_type difference_type; 666227825Stheraven typedef value_type& reference; 667227825Stheraven typedef typename __pointer_traits::template 668227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 669227825Stheraven rebind<value_type> 670227825Stheraven#else 671227825Stheraven rebind<value_type>::other 672227825Stheraven#endif 673227825Stheraven pointer; 674227825Stheraven 675227825Stheraven _LIBCPP_INLINE_VISIBILITY 676227825Stheraven __hash_map_iterator() _NOEXCEPT {} 677227825Stheraven 678227825Stheraven _LIBCPP_INLINE_VISIBILITY 679227825Stheraven __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 680227825Stheraven 681227825Stheraven _LIBCPP_INLINE_VISIBILITY 682253146Stheraven reference operator*() const {return __i_->__cc;} 683227825Stheraven _LIBCPP_INLINE_VISIBILITY 684253146Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 685227825Stheraven 686227825Stheraven _LIBCPP_INLINE_VISIBILITY 687227825Stheraven __hash_map_iterator& operator++() {++__i_; return *this;} 688227825Stheraven _LIBCPP_INLINE_VISIBILITY 689227825Stheraven __hash_map_iterator operator++(int) 690227825Stheraven { 691227825Stheraven __hash_map_iterator __t(*this); 692227825Stheraven ++(*this); 693227825Stheraven return __t; 694227825Stheraven } 695227825Stheraven 696227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 697227825Stheraven bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 698227825Stheraven {return __x.__i_ == __y.__i_;} 699227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 700227825Stheraven bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 701227825Stheraven {return __x.__i_ != __y.__i_;} 702227825Stheraven 703261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 704261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 705261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 706261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 707261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 708227825Stheraven}; 709227825Stheraven 710227825Stheraventemplate <class _HashIterator> 711261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator 712227825Stheraven{ 713227825Stheraven _HashIterator __i_; 714227825Stheraven 715227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 716253146Stheraven typedef const typename _HashIterator::value_type::value_type::first_type key_type; 717253146Stheraven typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 718227825Stheravenpublic: 719227825Stheraven typedef forward_iterator_tag iterator_category; 720227825Stheraven typedef pair<key_type, mapped_type> value_type; 721227825Stheraven typedef typename _HashIterator::difference_type difference_type; 722227825Stheraven typedef const value_type& reference; 723227825Stheraven typedef typename __pointer_traits::template 724227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 725227825Stheraven rebind<const value_type> 726227825Stheraven#else 727227825Stheraven rebind<const value_type>::other 728227825Stheraven#endif 729227825Stheraven pointer; 730227825Stheraven 731227825Stheraven _LIBCPP_INLINE_VISIBILITY 732227825Stheraven __hash_map_const_iterator() _NOEXCEPT {} 733227825Stheraven 734227825Stheraven _LIBCPP_INLINE_VISIBILITY 735227825Stheraven __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 736227825Stheraven _LIBCPP_INLINE_VISIBILITY 737227825Stheraven __hash_map_const_iterator( 738227825Stheraven __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 739227825Stheraven _NOEXCEPT 740227825Stheraven : __i_(__i.__i_) {} 741227825Stheraven 742227825Stheraven _LIBCPP_INLINE_VISIBILITY 743253146Stheraven reference operator*() const {return __i_->__cc;} 744227825Stheraven _LIBCPP_INLINE_VISIBILITY 745253146Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 746227825Stheraven 747227825Stheraven _LIBCPP_INLINE_VISIBILITY 748227825Stheraven __hash_map_const_iterator& operator++() {++__i_; return *this;} 749227825Stheraven _LIBCPP_INLINE_VISIBILITY 750227825Stheraven __hash_map_const_iterator operator++(int) 751227825Stheraven { 752227825Stheraven __hash_map_const_iterator __t(*this); 753227825Stheraven ++(*this); 754227825Stheraven return __t; 755227825Stheraven } 756227825Stheraven 757227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 758227825Stheraven bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 759227825Stheraven {return __x.__i_ == __y.__i_;} 760227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 761227825Stheraven bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 762227825Stheraven {return __x.__i_ != __y.__i_;} 763227825Stheraven 764261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 765261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 766261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 767261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 768227825Stheraven}; 769227825Stheraven 770227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 771227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 772261272Sdimclass _LIBCPP_TYPE_VIS_ONLY unordered_map 773227825Stheraven{ 774227825Stheravenpublic: 775227825Stheraven // types 776227825Stheraven typedef _Key key_type; 777227825Stheraven typedef _Tp mapped_type; 778227825Stheraven typedef _Hash hasher; 779227825Stheraven typedef _Pred key_equal; 780227825Stheraven typedef _Alloc allocator_type; 781227825Stheraven typedef pair<const key_type, mapped_type> value_type; 782253146Stheraven typedef pair<key_type, mapped_type> __nc_value_type; 783227825Stheraven typedef value_type& reference; 784227825Stheraven typedef const value_type& const_reference; 785261272Sdim static_assert((is_same<value_type, typename allocator_type::value_type>::value), 786261272Sdim "Invalid allocator::value_type"); 787227825Stheraven 788227825Stheravenprivate: 789261272Sdim typedef __hash_value_type<key_type, mapped_type> __value_type; 790253146Stheraven typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 791253146Stheraven typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 792288943Sdim typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 793288943Sdim __value_type>::type __allocator_type; 794227825Stheraven 795227825Stheraven typedef __hash_table<__value_type, __hasher, 796227825Stheraven __key_equal, __allocator_type> __table; 797227825Stheraven 798227825Stheraven __table __table_; 799227825Stheraven 800227825Stheraven typedef typename __table::__node_pointer __node_pointer; 801227825Stheraven typedef typename __table::__node_const_pointer __node_const_pointer; 802227825Stheraven typedef typename __table::__node_traits __node_traits; 803227825Stheraven typedef typename __table::__node_allocator __node_allocator; 804227825Stheraven typedef typename __table::__node __node; 805232924Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 806232924Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 807227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 808227825Stheravenpublic: 809227825Stheraven typedef typename __alloc_traits::pointer pointer; 810227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 811227825Stheraven typedef typename __alloc_traits::size_type size_type; 812227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 813227825Stheraven 814227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 815227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 816227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 817227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 818227825Stheraven 819227825Stheraven _LIBCPP_INLINE_VISIBILITY 820227825Stheraven unordered_map() 821227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 822261272Sdim { 823261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 824261272Sdim __get_db()->__insert_c(this); 825261272Sdim#endif 826261272Sdim } 827227825Stheraven explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 828227825Stheraven const key_equal& __eql = key_equal()); 829227825Stheraven unordered_map(size_type __n, const hasher& __hf, 830227825Stheraven const key_equal& __eql, 831227825Stheraven const allocator_type& __a); 832227825Stheraven template <class _InputIterator> 833227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last); 834227825Stheraven template <class _InputIterator> 835227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 836227825Stheraven size_type __n, const hasher& __hf = hasher(), 837227825Stheraven const key_equal& __eql = key_equal()); 838227825Stheraven template <class _InputIterator> 839227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 840227825Stheraven size_type __n, const hasher& __hf, 841227825Stheraven const key_equal& __eql, 842227825Stheraven const allocator_type& __a); 843227825Stheraven explicit unordered_map(const allocator_type& __a); 844227825Stheraven unordered_map(const unordered_map& __u); 845227825Stheraven unordered_map(const unordered_map& __u, const allocator_type& __a); 846227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 847227825Stheraven unordered_map(unordered_map&& __u) 848227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 849227825Stheraven unordered_map(unordered_map&& __u, const allocator_type& __a); 850227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 851227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 852227825Stheraven unordered_map(initializer_list<value_type> __il); 853227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 854227825Stheraven const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 855227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 856227825Stheraven const hasher& __hf, const key_equal& __eql, 857227825Stheraven const allocator_type& __a); 858227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 859261272Sdim#if _LIBCPP_STD_VER > 11 860261272Sdim _LIBCPP_INLINE_VISIBILITY 861261272Sdim unordered_map(size_type __n, const allocator_type& __a) 862261272Sdim : unordered_map(__n, hasher(), key_equal(), __a) {} 863261272Sdim _LIBCPP_INLINE_VISIBILITY 864261272Sdim unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a) 865261272Sdim : unordered_map(__n, __hf, key_equal(), __a) {} 866261272Sdim template <class _InputIterator> 867261272Sdim _LIBCPP_INLINE_VISIBILITY 868261272Sdim unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 869261272Sdim : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} 870261272Sdim template <class _InputIterator> 871261272Sdim _LIBCPP_INLINE_VISIBILITY 872261272Sdim unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 873261272Sdim const allocator_type& __a) 874261272Sdim : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} 875261272Sdim _LIBCPP_INLINE_VISIBILITY 876261272Sdim unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 877261272Sdim : unordered_map(__il, __n, hasher(), key_equal(), __a) {} 878261272Sdim _LIBCPP_INLINE_VISIBILITY 879261272Sdim unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 880261272Sdim const allocator_type& __a) 881261272Sdim : unordered_map(__il, __n, __hf, key_equal(), __a) {} 882261272Sdim#endif 883227825Stheraven // ~unordered_map() = default; 884227825Stheraven _LIBCPP_INLINE_VISIBILITY 885227825Stheraven unordered_map& operator=(const unordered_map& __u) 886227825Stheraven { 887253146Stheraven#if __cplusplus >= 201103L 888227825Stheraven __table_ = __u.__table_; 889253146Stheraven#else 890276792Sdim if (this != &__u) { 891276792Sdim __table_.clear(); 892276792Sdim __table_.hash_function() = __u.__table_.hash_function(); 893276792Sdim __table_.key_eq() = __u.__table_.key_eq(); 894276792Sdim __table_.max_load_factor() = __u.__table_.max_load_factor(); 895276792Sdim __table_.__copy_assign_alloc(__u.__table_); 896276792Sdim insert(__u.begin(), __u.end()); 897276792Sdim } 898253146Stheraven#endif 899227825Stheraven return *this; 900227825Stheraven } 901227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 902227825Stheraven unordered_map& operator=(unordered_map&& __u) 903227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 904227825Stheraven#endif 905227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 906227825Stheraven unordered_map& operator=(initializer_list<value_type> __il); 907227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 908227825Stheraven 909227825Stheraven _LIBCPP_INLINE_VISIBILITY 910227825Stheraven allocator_type get_allocator() const _NOEXCEPT 911227825Stheraven {return allocator_type(__table_.__node_alloc());} 912227825Stheraven 913227825Stheraven _LIBCPP_INLINE_VISIBILITY 914227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 915227825Stheraven _LIBCPP_INLINE_VISIBILITY 916227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 917227825Stheraven _LIBCPP_INLINE_VISIBILITY 918227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 919227825Stheraven 920227825Stheraven _LIBCPP_INLINE_VISIBILITY 921227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 922227825Stheraven _LIBCPP_INLINE_VISIBILITY 923227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 924227825Stheraven _LIBCPP_INLINE_VISIBILITY 925227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 926227825Stheraven _LIBCPP_INLINE_VISIBILITY 927227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 928227825Stheraven _LIBCPP_INLINE_VISIBILITY 929227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 930227825Stheraven _LIBCPP_INLINE_VISIBILITY 931227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 932227825Stheraven 933227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 934227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 935227825Stheraven 936241900Sdim template <class... _Args> 937241900Sdim pair<iterator, bool> emplace(_Args&&... __args); 938227825Stheraven 939241900Sdim template <class... _Args> 940227825Stheraven _LIBCPP_INLINE_VISIBILITY 941261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 942261272Sdim iterator emplace_hint(const_iterator __p, _Args&&... __args) 943261272Sdim { 944261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 945261272Sdim "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" 946261272Sdim " referring to this unordered_map"); 947261272Sdim return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 948261272Sdim } 949261272Sdim#else 950241900Sdim iterator emplace_hint(const_iterator, _Args&&... __args) 951241900Sdim {return emplace(_VSTD::forward<_Args>(__args)...).first;} 952261272Sdim#endif 953227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 954227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 955227825Stheraven _LIBCPP_INLINE_VISIBILITY 956227825Stheraven pair<iterator, bool> insert(const value_type& __x) 957227825Stheraven {return __table_.__insert_unique(__x);} 958227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 959232924Stheraven template <class _Pp, 960232924Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 961227825Stheraven _LIBCPP_INLINE_VISIBILITY 962232924Stheraven pair<iterator, bool> insert(_Pp&& __x) 963232924Stheraven {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 964227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 965227825Stheraven _LIBCPP_INLINE_VISIBILITY 966261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 967261272Sdim iterator insert(const_iterator __p, const value_type& __x) 968261272Sdim { 969261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 970261272Sdim "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" 971261272Sdim " referring to this unordered_map"); 972261272Sdim return insert(__x).first; 973261272Sdim } 974261272Sdim#else 975227825Stheraven iterator insert(const_iterator, const value_type& __x) 976227825Stheraven {return insert(__x).first;} 977261272Sdim#endif 978227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 979232924Stheraven template <class _Pp, 980232924Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 981227825Stheraven _LIBCPP_INLINE_VISIBILITY 982261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 983261272Sdim iterator insert(const_iterator __p, _Pp&& __x) 984261272Sdim { 985261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 986261272Sdim "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" 987261272Sdim " referring to this unordered_map"); 988261272Sdim return insert(_VSTD::forward<_Pp>(__x)).first; 989261272Sdim } 990261272Sdim#else 991232924Stheraven iterator insert(const_iterator, _Pp&& __x) 992232924Stheraven {return insert(_VSTD::forward<_Pp>(__x)).first;} 993261272Sdim#endif 994227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 995227825Stheraven template <class _InputIterator> 996227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 997227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 998227825Stheraven _LIBCPP_INLINE_VISIBILITY 999227825Stheraven void insert(initializer_list<value_type> __il) 1000227825Stheraven {insert(__il.begin(), __il.end());} 1001227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1002227825Stheraven 1003288943Sdim#if _LIBCPP_STD_VER > 14 1004288943Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1005288943Sdim#ifndef _LIBCPP_HAS_NO_VARIADICS 1006288943Sdim template <class... _Args> 1007288943Sdim _LIBCPP_INLINE_VISIBILITY 1008288943Sdim pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) 1009288943Sdim { 1010288943Sdim iterator __p = __table_.find(__k); 1011288943Sdim if ( __p != end()) 1012288943Sdim return _VSTD::make_pair(__p, false); 1013288943Sdim else 1014288943Sdim return _VSTD::make_pair( 1015288943Sdim emplace_hint(__p, 1016288943Sdim _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), 1017288943Sdim _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)), 1018288943Sdim true); 1019288943Sdim } 1020288943Sdim 1021288943Sdim template <class... _Args> 1022288943Sdim _LIBCPP_INLINE_VISIBILITY 1023288943Sdim pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) 1024288943Sdim { 1025288943Sdim iterator __p = __table_.find(__k); 1026288943Sdim if ( __p != end()) 1027288943Sdim return _VSTD::make_pair(__p, false); 1028288943Sdim else 1029288943Sdim return _VSTD::make_pair( 1030288943Sdim emplace_hint(__p, 1031288943Sdim _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 1032288943Sdim _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)), 1033288943Sdim true); 1034288943Sdim } 1035288943Sdim 1036288943Sdim template <class... _Args> 1037288943Sdim _LIBCPP_INLINE_VISIBILITY 1038288943Sdim iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) 1039288943Sdim { 1040288943Sdim iterator __p = __table_.find(__k); 1041288943Sdim if ( __p != end()) 1042288943Sdim return __p; 1043288943Sdim else 1044288943Sdim return emplace_hint(__h, 1045288943Sdim _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), 1046288943Sdim _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1047288943Sdim } 1048288943Sdim 1049288943Sdim template <class... _Args> 1050288943Sdim _LIBCPP_INLINE_VISIBILITY 1051288943Sdim iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) 1052288943Sdim { 1053288943Sdim iterator __p = __table_.find(__k); 1054288943Sdim if ( __p != end()) 1055288943Sdim return __p; 1056288943Sdim else 1057288943Sdim return emplace_hint(__h, 1058288943Sdim _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), 1059288943Sdim _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1060288943Sdim } 1061288943Sdim 1062288943Sdim template <class _Vp> 1063288943Sdim _LIBCPP_INLINE_VISIBILITY 1064288943Sdim pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) 1065288943Sdim { 1066288943Sdim iterator __p = __table_.find(__k); 1067288943Sdim if ( __p != end()) 1068288943Sdim { 1069288943Sdim __p->second = _VSTD::move(__v); 1070288943Sdim return _VSTD::make_pair(__p, false); 1071288943Sdim } 1072288943Sdim return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true); 1073288943Sdim } 1074288943Sdim 1075288943Sdim template <class _Vp> 1076288943Sdim _LIBCPP_INLINE_VISIBILITY 1077288943Sdim pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) 1078288943Sdim { 1079288943Sdim iterator __p = __table_.find(__k); 1080288943Sdim if ( __p != end()) 1081288943Sdim { 1082288943Sdim __p->second = _VSTD::move(__v); 1083288943Sdim return _VSTD::make_pair(__p, false); 1084288943Sdim } 1085288943Sdim return _VSTD::make_pair(emplace_hint(__p, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v)), true); 1086288943Sdim } 1087288943Sdim 1088288943Sdim template <class _Vp> 1089288943Sdim _LIBCPP_INLINE_VISIBILITY 1090288943Sdim iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) 1091288943Sdim { 1092288943Sdim iterator __p = __table_.find(__k); 1093288943Sdim if ( __p != end()) 1094288943Sdim { 1095288943Sdim __p->second = _VSTD::move(__v); 1096288943Sdim return __p; 1097288943Sdim } 1098288943Sdim return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v)); 1099288943Sdim } 1100288943Sdim 1101288943Sdim template <class _Vp> 1102288943Sdim _LIBCPP_INLINE_VISIBILITY 1103288943Sdim iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) 1104288943Sdim { 1105288943Sdim iterator __p = __table_.find(__k); 1106288943Sdim if ( __p != end()) 1107288943Sdim { 1108288943Sdim __p->second = _VSTD::move(__v); 1109288943Sdim return __p; 1110288943Sdim } 1111288943Sdim return emplace_hint(__h, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v)); 1112288943Sdim } 1113288943Sdim#endif 1114288943Sdim#endif 1115288943Sdim#endif 1116288943Sdim 1117227825Stheraven _LIBCPP_INLINE_VISIBILITY 1118227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1119227825Stheraven _LIBCPP_INLINE_VISIBILITY 1120288943Sdim iterator erase(iterator __p) {return __table_.erase(__p.__i_);} 1121288943Sdim _LIBCPP_INLINE_VISIBILITY 1122227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 1123227825Stheraven _LIBCPP_INLINE_VISIBILITY 1124227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 1125227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 1126227825Stheraven _LIBCPP_INLINE_VISIBILITY 1127227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 1128227825Stheraven 1129227825Stheraven _LIBCPP_INLINE_VISIBILITY 1130227825Stheraven void swap(unordered_map& __u) 1131227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1132227825Stheraven {__table_.swap(__u.__table_);} 1133227825Stheraven 1134227825Stheraven _LIBCPP_INLINE_VISIBILITY 1135227825Stheraven hasher hash_function() const 1136227825Stheraven {return __table_.hash_function().hash_function();} 1137227825Stheraven _LIBCPP_INLINE_VISIBILITY 1138227825Stheraven key_equal key_eq() const 1139227825Stheraven {return __table_.key_eq().key_eq();} 1140227825Stheraven 1141227825Stheraven _LIBCPP_INLINE_VISIBILITY 1142227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 1143227825Stheraven _LIBCPP_INLINE_VISIBILITY 1144227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1145227825Stheraven _LIBCPP_INLINE_VISIBILITY 1146227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 1147227825Stheraven _LIBCPP_INLINE_VISIBILITY 1148227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 1149227825Stheraven {return __table_.__equal_range_unique(__k);} 1150227825Stheraven _LIBCPP_INLINE_VISIBILITY 1151227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1152227825Stheraven {return __table_.__equal_range_unique(__k);} 1153227825Stheraven 1154227825Stheraven mapped_type& operator[](const key_type& __k); 1155227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1156227825Stheraven mapped_type& operator[](key_type&& __k); 1157227825Stheraven#endif 1158227825Stheraven 1159227825Stheraven mapped_type& at(const key_type& __k); 1160227825Stheraven const mapped_type& at(const key_type& __k) const; 1161227825Stheraven 1162227825Stheraven _LIBCPP_INLINE_VISIBILITY 1163227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1164227825Stheraven _LIBCPP_INLINE_VISIBILITY 1165227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 1166227825Stheraven 1167227825Stheraven _LIBCPP_INLINE_VISIBILITY 1168227825Stheraven size_type bucket_size(size_type __n) const 1169227825Stheraven {return __table_.bucket_size(__n);} 1170227825Stheraven _LIBCPP_INLINE_VISIBILITY 1171227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1172227825Stheraven 1173227825Stheraven _LIBCPP_INLINE_VISIBILITY 1174227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1175227825Stheraven _LIBCPP_INLINE_VISIBILITY 1176227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1177227825Stheraven _LIBCPP_INLINE_VISIBILITY 1178227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1179227825Stheraven _LIBCPP_INLINE_VISIBILITY 1180227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1181227825Stheraven _LIBCPP_INLINE_VISIBILITY 1182227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1183227825Stheraven _LIBCPP_INLINE_VISIBILITY 1184227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1185227825Stheraven 1186227825Stheraven _LIBCPP_INLINE_VISIBILITY 1187227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1188227825Stheraven _LIBCPP_INLINE_VISIBILITY 1189227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1190227825Stheraven _LIBCPP_INLINE_VISIBILITY 1191227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1192227825Stheraven _LIBCPP_INLINE_VISIBILITY 1193227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1194227825Stheraven _LIBCPP_INLINE_VISIBILITY 1195227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1196227825Stheraven 1197261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1198261272Sdim 1199261272Sdim bool __dereferenceable(const const_iterator* __i) const 1200261272Sdim {return __table_.__dereferenceable(&__i->__i_);} 1201261272Sdim bool __decrementable(const const_iterator* __i) const 1202261272Sdim {return __table_.__decrementable(&__i->__i_);} 1203261272Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1204261272Sdim {return __table_.__addable(&__i->__i_, __n);} 1205261272Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1206261272Sdim {return __table_.__addable(&__i->__i_, __n);} 1207261272Sdim 1208261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1209261272Sdim 1210227825Stheravenprivate: 1211227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1212241900Sdim __node_holder __construct_node(); 1213241900Sdim template <class _A0> 1214253146Stheraven __node_holder 1215241900Sdim __construct_node(_A0&& __a0); 1216253146Stheraven __node_holder __construct_node_with_key(key_type&& __k); 1217227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1218241900Sdim template <class _A0, class _A1, class ..._Args> 1219241900Sdim __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1220227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1221253146Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1222253146Stheraven __node_holder __construct_node_with_key(const key_type& __k); 1223227825Stheraven}; 1224227825Stheraven 1225227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1226227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1227227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1228227825Stheraven : __table_(__hf, __eql) 1229227825Stheraven{ 1230261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1231261272Sdim __get_db()->__insert_c(this); 1232261272Sdim#endif 1233227825Stheraven __table_.rehash(__n); 1234227825Stheraven} 1235227825Stheraven 1236227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1237227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1238227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1239227825Stheraven const allocator_type& __a) 1240227825Stheraven : __table_(__hf, __eql, __a) 1241227825Stheraven{ 1242261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1243261272Sdim __get_db()->__insert_c(this); 1244261272Sdim#endif 1245227825Stheraven __table_.rehash(__n); 1246227825Stheraven} 1247227825Stheraven 1248227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1249227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1250227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1251227825Stheraven const allocator_type& __a) 1252227825Stheraven : __table_(__a) 1253227825Stheraven{ 1254261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1255261272Sdim __get_db()->__insert_c(this); 1256261272Sdim#endif 1257227825Stheraven} 1258227825Stheraven 1259227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1260227825Stheraventemplate <class _InputIterator> 1261227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1262227825Stheraven _InputIterator __first, _InputIterator __last) 1263227825Stheraven{ 1264261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1265261272Sdim __get_db()->__insert_c(this); 1266261272Sdim#endif 1267227825Stheraven insert(__first, __last); 1268227825Stheraven} 1269227825Stheraven 1270227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1271227825Stheraventemplate <class _InputIterator> 1272227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1273227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1274227825Stheraven const hasher& __hf, const key_equal& __eql) 1275227825Stheraven : __table_(__hf, __eql) 1276227825Stheraven{ 1277261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1278261272Sdim __get_db()->__insert_c(this); 1279261272Sdim#endif 1280227825Stheraven __table_.rehash(__n); 1281227825Stheraven insert(__first, __last); 1282227825Stheraven} 1283227825Stheraven 1284227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1285227825Stheraventemplate <class _InputIterator> 1286227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1287227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1288227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1289227825Stheraven : __table_(__hf, __eql, __a) 1290227825Stheraven{ 1291261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1292261272Sdim __get_db()->__insert_c(this); 1293261272Sdim#endif 1294227825Stheraven __table_.rehash(__n); 1295227825Stheraven insert(__first, __last); 1296227825Stheraven} 1297227825Stheraven 1298227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1299227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1300227825Stheraven const unordered_map& __u) 1301227825Stheraven : __table_(__u.__table_) 1302227825Stheraven{ 1303261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1304261272Sdim __get_db()->__insert_c(this); 1305261272Sdim#endif 1306227825Stheraven __table_.rehash(__u.bucket_count()); 1307227825Stheraven insert(__u.begin(), __u.end()); 1308227825Stheraven} 1309227825Stheraven 1310227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1311227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1312227825Stheraven const unordered_map& __u, const allocator_type& __a) 1313227825Stheraven : __table_(__u.__table_, __a) 1314227825Stheraven{ 1315261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1316261272Sdim __get_db()->__insert_c(this); 1317261272Sdim#endif 1318227825Stheraven __table_.rehash(__u.bucket_count()); 1319227825Stheraven insert(__u.begin(), __u.end()); 1320227825Stheraven} 1321227825Stheraven 1322227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1323227825Stheraven 1324227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1325227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1326227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1327227825Stheraven unordered_map&& __u) 1328227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1329227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1330227825Stheraven{ 1331261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1332261272Sdim __get_db()->__insert_c(this); 1333261272Sdim __get_db()->swap(this, &__u); 1334261272Sdim#endif 1335227825Stheraven} 1336227825Stheraven 1337227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1338227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1339227825Stheraven unordered_map&& __u, const allocator_type& __a) 1340227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1341227825Stheraven{ 1342261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1343261272Sdim __get_db()->__insert_c(this); 1344261272Sdim#endif 1345227825Stheraven if (__a != __u.get_allocator()) 1346227825Stheraven { 1347227825Stheraven iterator __i = __u.begin(); 1348227825Stheraven while (__u.size() != 0) 1349227825Stheraven __table_.__insert_unique( 1350227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1351227825Stheraven ); 1352227825Stheraven } 1353261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1354261272Sdim else 1355261272Sdim __get_db()->swap(this, &__u); 1356261272Sdim#endif 1357227825Stheraven} 1358227825Stheraven 1359227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1360227825Stheraven 1361227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1362227825Stheraven 1363227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1364227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1365227825Stheraven initializer_list<value_type> __il) 1366227825Stheraven{ 1367261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1368261272Sdim __get_db()->__insert_c(this); 1369261272Sdim#endif 1370227825Stheraven insert(__il.begin(), __il.end()); 1371227825Stheraven} 1372227825Stheraven 1373227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1374227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1375227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1376227825Stheraven const key_equal& __eql) 1377227825Stheraven : __table_(__hf, __eql) 1378227825Stheraven{ 1379261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1380261272Sdim __get_db()->__insert_c(this); 1381261272Sdim#endif 1382227825Stheraven __table_.rehash(__n); 1383227825Stheraven insert(__il.begin(), __il.end()); 1384227825Stheraven} 1385227825Stheraven 1386227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1387227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1388227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1389227825Stheraven const key_equal& __eql, const allocator_type& __a) 1390227825Stheraven : __table_(__hf, __eql, __a) 1391227825Stheraven{ 1392261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1393261272Sdim __get_db()->__insert_c(this); 1394261272Sdim#endif 1395227825Stheraven __table_.rehash(__n); 1396227825Stheraven insert(__il.begin(), __il.end()); 1397227825Stheraven} 1398227825Stheraven 1399227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1400227825Stheraven 1401227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1402227825Stheraven 1403227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1404227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1405227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1406227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1407227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1408227825Stheraven{ 1409227825Stheraven __table_ = _VSTD::move(__u.__table_); 1410227825Stheraven return *this; 1411227825Stheraven} 1412227825Stheraven 1413227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1414227825Stheraven 1415227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1416227825Stheraven 1417227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1418227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1419227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1420227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1421227825Stheraven initializer_list<value_type> __il) 1422227825Stheraven{ 1423227825Stheraven __table_.__assign_unique(__il.begin(), __il.end()); 1424227825Stheraven return *this; 1425227825Stheraven} 1426227825Stheraven 1427227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1428227825Stheraven 1429227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1430227825Stheraven 1431227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1432227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1433241900Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1434227825Stheraven{ 1435227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1436232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1437241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1438227825Stheraven __h.get_deleter().__first_constructed = true; 1439227825Stheraven __h.get_deleter().__second_constructed = true; 1440227825Stheraven return __h; 1441227825Stheraven} 1442227825Stheraven 1443227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1444241900Sdimtemplate <class _A0> 1445253146Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1446227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1447227825Stheraven{ 1448227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1449232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1450227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1451227825Stheraven _VSTD::forward<_A0>(__a0)); 1452227825Stheraven __h.get_deleter().__first_constructed = true; 1453227825Stheraven __h.get_deleter().__second_constructed = true; 1454227825Stheraven return __h; 1455227825Stheraven} 1456227825Stheraven 1457241900Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1458253146Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1459253146Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k) 1460241900Sdim{ 1461241900Sdim __node_allocator& __na = __table_.__node_alloc(); 1462241900Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1463253146Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k)); 1464241900Sdim __h.get_deleter().__first_constructed = true; 1465253146Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1466241900Sdim __h.get_deleter().__second_constructed = true; 1467261272Sdim return __h; 1468241900Sdim} 1469241900Sdim 1470227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1471227825Stheraven 1472227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1473241900Sdimtemplate <class _A0, class _A1, class ..._Args> 1474241900Sdimtypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1475241900Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1476241900Sdim _A1&& __a1, 1477241900Sdim _Args&&... __args) 1478241900Sdim{ 1479241900Sdim __node_allocator& __na = __table_.__node_alloc(); 1480241900Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1481241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1482241900Sdim _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1483241900Sdim _VSTD::forward<_Args>(__args)...); 1484241900Sdim __h.get_deleter().__first_constructed = true; 1485241900Sdim __h.get_deleter().__second_constructed = true; 1486241900Sdim return __h; 1487241900Sdim} 1488241900Sdim 1489241900Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1490241900Sdimtemplate <class... _Args> 1491227825Stheravenpair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1492241900Sdimunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1493227825Stheraven{ 1494241900Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1495227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1496227825Stheraven if (__r.second) 1497227825Stheraven __h.release(); 1498227825Stheraven return __r; 1499227825Stheraven} 1500227825Stheraven 1501227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1502253146Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1503227825Stheraven 1504227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1505227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1506253146Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1507227825Stheraven{ 1508227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1509232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1510253146Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1511227825Stheraven __h.get_deleter().__first_constructed = true; 1512253146Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1513227825Stheraven __h.get_deleter().__second_constructed = true; 1514261272Sdim return _VSTD::move(__h); // explicitly moved for C++03 1515227825Stheraven} 1516227825Stheraven 1517227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1518227825Stheraventemplate <class _InputIterator> 1519227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1520227825Stheravenvoid 1521227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1522227825Stheraven _InputIterator __last) 1523227825Stheraven{ 1524227825Stheraven for (; __first != __last; ++__first) 1525227825Stheraven __table_.__insert_unique(*__first); 1526227825Stheraven} 1527227825Stheraven 1528227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1529227825Stheraven_Tp& 1530227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1531227825Stheraven{ 1532227825Stheraven iterator __i = find(__k); 1533227825Stheraven if (__i != end()) 1534227825Stheraven return __i->second; 1535253146Stheraven __node_holder __h = __construct_node_with_key(__k); 1536227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1537227825Stheraven __h.release(); 1538227825Stheraven return __r.first->second; 1539227825Stheraven} 1540227825Stheraven 1541227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1542227825Stheraven 1543227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1544227825Stheraven_Tp& 1545227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1546227825Stheraven{ 1547227825Stheraven iterator __i = find(__k); 1548227825Stheraven if (__i != end()) 1549227825Stheraven return __i->second; 1550253146Stheraven __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); 1551227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1552227825Stheraven __h.release(); 1553227825Stheraven return __r.first->second; 1554227825Stheraven} 1555227825Stheraven 1556227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1557227825Stheraven 1558227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1559227825Stheraven_Tp& 1560227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1561227825Stheraven{ 1562227825Stheraven iterator __i = find(__k); 1563227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1564227825Stheraven if (__i == end()) 1565227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1566227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1567227825Stheraven return __i->second; 1568227825Stheraven} 1569227825Stheraven 1570227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1571227825Stheravenconst _Tp& 1572227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1573227825Stheraven{ 1574227825Stheraven const_iterator __i = find(__k); 1575227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1576227825Stheraven if (__i == end()) 1577227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1578227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1579227825Stheraven return __i->second; 1580227825Stheraven} 1581227825Stheraven 1582227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1583227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1584227825Stheravenvoid 1585227825Stheravenswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1586227825Stheraven unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1587227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1588227825Stheraven{ 1589227825Stheraven __x.swap(__y); 1590227825Stheraven} 1591227825Stheraven 1592227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1593227825Stheravenbool 1594227825Stheravenoperator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1595227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1596227825Stheraven{ 1597227825Stheraven if (__x.size() != __y.size()) 1598227825Stheraven return false; 1599227825Stheraven typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1600227825Stheraven const_iterator; 1601227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1602227825Stheraven __i != __ex; ++__i) 1603227825Stheraven { 1604227825Stheraven const_iterator __j = __y.find(__i->first); 1605227825Stheraven if (__j == __ey || !(*__i == *__j)) 1606227825Stheraven return false; 1607227825Stheraven } 1608227825Stheraven return true; 1609227825Stheraven} 1610227825Stheraven 1611227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1612227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1613227825Stheravenbool 1614227825Stheravenoperator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1615227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1616227825Stheraven{ 1617227825Stheraven return !(__x == __y); 1618227825Stheraven} 1619227825Stheraven 1620227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1621227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 1622261272Sdimclass _LIBCPP_TYPE_VIS_ONLY unordered_multimap 1623227825Stheraven{ 1624227825Stheravenpublic: 1625227825Stheraven // types 1626227825Stheraven typedef _Key key_type; 1627227825Stheraven typedef _Tp mapped_type; 1628227825Stheraven typedef _Hash hasher; 1629227825Stheraven typedef _Pred key_equal; 1630227825Stheraven typedef _Alloc allocator_type; 1631227825Stheraven typedef pair<const key_type, mapped_type> value_type; 1632253146Stheraven typedef pair<key_type, mapped_type> __nc_value_type; 1633227825Stheraven typedef value_type& reference; 1634227825Stheraven typedef const value_type& const_reference; 1635261272Sdim static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1636261272Sdim "Invalid allocator::value_type"); 1637227825Stheraven 1638227825Stheravenprivate: 1639261272Sdim typedef __hash_value_type<key_type, mapped_type> __value_type; 1640253146Stheraven typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 1641253146Stheraven typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 1642288943Sdim typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1643288943Sdim __value_type>::type __allocator_type; 1644227825Stheraven 1645227825Stheraven typedef __hash_table<__value_type, __hasher, 1646227825Stheraven __key_equal, __allocator_type> __table; 1647227825Stheraven 1648227825Stheraven __table __table_; 1649227825Stheraven 1650227825Stheraven typedef typename __table::__node_traits __node_traits; 1651227825Stheraven typedef typename __table::__node_allocator __node_allocator; 1652227825Stheraven typedef typename __table::__node __node; 1653232924Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 1654232924Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 1655227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 1656227825Stheravenpublic: 1657227825Stheraven typedef typename __alloc_traits::pointer pointer; 1658227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 1659227825Stheraven typedef typename __alloc_traits::size_type size_type; 1660227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 1661227825Stheraven 1662227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 1663227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1664227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1665227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1666227825Stheraven 1667227825Stheraven _LIBCPP_INLINE_VISIBILITY 1668227825Stheraven unordered_multimap() 1669227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1670261272Sdim { 1671261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1672261272Sdim __get_db()->__insert_c(this); 1673261272Sdim#endif 1674261272Sdim } 1675227825Stheraven explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1676227825Stheraven const key_equal& __eql = key_equal()); 1677227825Stheraven unordered_multimap(size_type __n, const hasher& __hf, 1678227825Stheraven const key_equal& __eql, 1679227825Stheraven const allocator_type& __a); 1680227825Stheraven template <class _InputIterator> 1681227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last); 1682227825Stheraven template <class _InputIterator> 1683227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1684227825Stheraven size_type __n, const hasher& __hf = hasher(), 1685227825Stheraven const key_equal& __eql = key_equal()); 1686227825Stheraven template <class _InputIterator> 1687227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1688227825Stheraven size_type __n, const hasher& __hf, 1689227825Stheraven const key_equal& __eql, 1690227825Stheraven const allocator_type& __a); 1691227825Stheraven explicit unordered_multimap(const allocator_type& __a); 1692227825Stheraven unordered_multimap(const unordered_multimap& __u); 1693227825Stheraven unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1694227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1695227825Stheraven unordered_multimap(unordered_multimap&& __u) 1696227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1697227825Stheraven unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1698227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1699227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1700227825Stheraven unordered_multimap(initializer_list<value_type> __il); 1701227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1702227825Stheraven const hasher& __hf = hasher(), 1703227825Stheraven const key_equal& __eql = key_equal()); 1704227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1705227825Stheraven const hasher& __hf, const key_equal& __eql, 1706227825Stheraven const allocator_type& __a); 1707227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1708261272Sdim#if _LIBCPP_STD_VER > 11 1709261272Sdim _LIBCPP_INLINE_VISIBILITY 1710261272Sdim unordered_multimap(size_type __n, const allocator_type& __a) 1711261272Sdim : unordered_multimap(__n, hasher(), key_equal(), __a) {} 1712261272Sdim _LIBCPP_INLINE_VISIBILITY 1713261272Sdim unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 1714261272Sdim : unordered_multimap(__n, __hf, key_equal(), __a) {} 1715261272Sdim template <class _InputIterator> 1716261272Sdim _LIBCPP_INLINE_VISIBILITY 1717261272Sdim unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1718261272Sdim : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 1719261272Sdim template <class _InputIterator> 1720261272Sdim _LIBCPP_INLINE_VISIBILITY 1721261272Sdim unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 1722261272Sdim const allocator_type& __a) 1723261272Sdim : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 1724261272Sdim _LIBCPP_INLINE_VISIBILITY 1725261272Sdim unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1726261272Sdim : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 1727261272Sdim _LIBCPP_INLINE_VISIBILITY 1728261272Sdim unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1729261272Sdim const allocator_type& __a) 1730261272Sdim : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 1731261272Sdim#endif 1732227825Stheraven // ~unordered_multimap() = default; 1733227825Stheraven _LIBCPP_INLINE_VISIBILITY 1734227825Stheraven unordered_multimap& operator=(const unordered_multimap& __u) 1735227825Stheraven { 1736253146Stheraven#if __cplusplus >= 201103L 1737227825Stheraven __table_ = __u.__table_; 1738253146Stheraven#else 1739276792Sdim if (this != &__u) { 1740276792Sdim __table_.clear(); 1741276792Sdim __table_.hash_function() = __u.__table_.hash_function(); 1742276792Sdim __table_.key_eq() = __u.__table_.key_eq(); 1743276792Sdim __table_.max_load_factor() = __u.__table_.max_load_factor(); 1744276792Sdim __table_.__copy_assign_alloc(__u.__table_); 1745276792Sdim insert(__u.begin(), __u.end()); 1746276792Sdim } 1747253146Stheraven#endif 1748227825Stheraven return *this; 1749227825Stheraven } 1750227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1751227825Stheraven unordered_multimap& operator=(unordered_multimap&& __u) 1752227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1753227825Stheraven#endif 1754227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1755227825Stheraven unordered_multimap& operator=(initializer_list<value_type> __il); 1756227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1757227825Stheraven 1758227825Stheraven _LIBCPP_INLINE_VISIBILITY 1759227825Stheraven allocator_type get_allocator() const _NOEXCEPT 1760227825Stheraven {return allocator_type(__table_.__node_alloc());} 1761227825Stheraven 1762227825Stheraven _LIBCPP_INLINE_VISIBILITY 1763227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1764227825Stheraven _LIBCPP_INLINE_VISIBILITY 1765227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 1766227825Stheraven _LIBCPP_INLINE_VISIBILITY 1767227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1768227825Stheraven 1769227825Stheraven _LIBCPP_INLINE_VISIBILITY 1770227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 1771227825Stheraven _LIBCPP_INLINE_VISIBILITY 1772227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 1773227825Stheraven _LIBCPP_INLINE_VISIBILITY 1774227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1775227825Stheraven _LIBCPP_INLINE_VISIBILITY 1776227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 1777227825Stheraven _LIBCPP_INLINE_VISIBILITY 1778227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1779227825Stheraven _LIBCPP_INLINE_VISIBILITY 1780227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 1781227825Stheraven 1782227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1783227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1784227825Stheraven 1785241900Sdim template <class... _Args> 1786241900Sdim iterator emplace(_Args&&... __args); 1787227825Stheraven 1788241900Sdim template <class... _Args> 1789241900Sdim iterator emplace_hint(const_iterator __p, _Args&&... __args); 1790227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1791227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1792227825Stheraven _LIBCPP_INLINE_VISIBILITY 1793227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1794227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1795232924Stheraven template <class _Pp, 1796232924Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1797227825Stheraven _LIBCPP_INLINE_VISIBILITY 1798232924Stheraven iterator insert(_Pp&& __x) 1799232924Stheraven {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1800227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1801227825Stheraven _LIBCPP_INLINE_VISIBILITY 1802227825Stheraven iterator insert(const_iterator __p, const value_type& __x) 1803227825Stheraven {return __table_.__insert_multi(__p.__i_, __x);} 1804227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1805232924Stheraven template <class _Pp, 1806232924Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1807227825Stheraven _LIBCPP_INLINE_VISIBILITY 1808232924Stheraven iterator insert(const_iterator __p, _Pp&& __x) 1809232924Stheraven {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1810227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1811227825Stheraven template <class _InputIterator> 1812227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 1813227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1814227825Stheraven _LIBCPP_INLINE_VISIBILITY 1815227825Stheraven void insert(initializer_list<value_type> __il) 1816227825Stheraven {insert(__il.begin(), __il.end());} 1817227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1818227825Stheraven 1819227825Stheraven _LIBCPP_INLINE_VISIBILITY 1820227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1821227825Stheraven _LIBCPP_INLINE_VISIBILITY 1822288943Sdim iterator erase(iterator __p) {return __table_.erase(__p.__i_);} 1823288943Sdim _LIBCPP_INLINE_VISIBILITY 1824227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1825227825Stheraven _LIBCPP_INLINE_VISIBILITY 1826227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 1827227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 1828227825Stheraven _LIBCPP_INLINE_VISIBILITY 1829227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 1830227825Stheraven 1831227825Stheraven _LIBCPP_INLINE_VISIBILITY 1832227825Stheraven void swap(unordered_multimap& __u) 1833227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1834227825Stheraven {__table_.swap(__u.__table_);} 1835227825Stheraven 1836227825Stheraven _LIBCPP_INLINE_VISIBILITY 1837227825Stheraven hasher hash_function() const 1838227825Stheraven {return __table_.hash_function().hash_function();} 1839227825Stheraven _LIBCPP_INLINE_VISIBILITY 1840227825Stheraven key_equal key_eq() const 1841227825Stheraven {return __table_.key_eq().key_eq();} 1842227825Stheraven 1843227825Stheraven _LIBCPP_INLINE_VISIBILITY 1844227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 1845227825Stheraven _LIBCPP_INLINE_VISIBILITY 1846227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1847227825Stheraven _LIBCPP_INLINE_VISIBILITY 1848227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1849227825Stheraven _LIBCPP_INLINE_VISIBILITY 1850227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 1851227825Stheraven {return __table_.__equal_range_multi(__k);} 1852227825Stheraven _LIBCPP_INLINE_VISIBILITY 1853227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1854227825Stheraven {return __table_.__equal_range_multi(__k);} 1855227825Stheraven 1856227825Stheraven _LIBCPP_INLINE_VISIBILITY 1857227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1858227825Stheraven _LIBCPP_INLINE_VISIBILITY 1859227825Stheraven size_type max_bucket_count() const _NOEXCEPT 1860227825Stheraven {return __table_.max_bucket_count();} 1861227825Stheraven 1862227825Stheraven _LIBCPP_INLINE_VISIBILITY 1863227825Stheraven size_type bucket_size(size_type __n) const 1864227825Stheraven {return __table_.bucket_size(__n);} 1865227825Stheraven _LIBCPP_INLINE_VISIBILITY 1866227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1867227825Stheraven 1868227825Stheraven _LIBCPP_INLINE_VISIBILITY 1869227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1870227825Stheraven _LIBCPP_INLINE_VISIBILITY 1871227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1872227825Stheraven _LIBCPP_INLINE_VISIBILITY 1873227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1874227825Stheraven _LIBCPP_INLINE_VISIBILITY 1875227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1876227825Stheraven _LIBCPP_INLINE_VISIBILITY 1877227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1878227825Stheraven _LIBCPP_INLINE_VISIBILITY 1879227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1880227825Stheraven 1881227825Stheraven _LIBCPP_INLINE_VISIBILITY 1882227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1883227825Stheraven _LIBCPP_INLINE_VISIBILITY 1884227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1885227825Stheraven _LIBCPP_INLINE_VISIBILITY 1886227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1887227825Stheraven _LIBCPP_INLINE_VISIBILITY 1888227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1889227825Stheraven _LIBCPP_INLINE_VISIBILITY 1890227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1891227825Stheraven 1892261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1893261272Sdim 1894261272Sdim bool __dereferenceable(const const_iterator* __i) const 1895261272Sdim {return __table_.__dereferenceable(&__i->__i_);} 1896261272Sdim bool __decrementable(const const_iterator* __i) const 1897261272Sdim {return __table_.__decrementable(&__i->__i_);} 1898261272Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1899261272Sdim {return __table_.__addable(&__i->__i_, __n);} 1900261272Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1901261272Sdim {return __table_.__addable(&__i->__i_, __n);} 1902261272Sdim 1903261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1904261272Sdim 1905227825Stheravenprivate: 1906241900Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1907241900Sdim __node_holder __construct_node(); 1908241900Sdim template <class _A0> 1909253146Stheraven __node_holder 1910241900Sdim __construct_node(_A0&& __a0); 1911241900Sdim#ifndef _LIBCPP_HAS_NO_VARIADICS 1912241900Sdim template <class _A0, class _A1, class ..._Args> 1913241900Sdim __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1914241900Sdim#endif // _LIBCPP_HAS_NO_VARIADICS 1915241900Sdim#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1916227825Stheraven}; 1917227825Stheraven 1918227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1919227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1920227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1921227825Stheraven : __table_(__hf, __eql) 1922227825Stheraven{ 1923261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1924261272Sdim __get_db()->__insert_c(this); 1925261272Sdim#endif 1926227825Stheraven __table_.rehash(__n); 1927227825Stheraven} 1928227825Stheraven 1929227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1930227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1931227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1932227825Stheraven const allocator_type& __a) 1933227825Stheraven : __table_(__hf, __eql, __a) 1934227825Stheraven{ 1935261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1936261272Sdim __get_db()->__insert_c(this); 1937261272Sdim#endif 1938227825Stheraven __table_.rehash(__n); 1939227825Stheraven} 1940227825Stheraven 1941227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1942227825Stheraventemplate <class _InputIterator> 1943227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1944227825Stheraven _InputIterator __first, _InputIterator __last) 1945227825Stheraven{ 1946261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1947261272Sdim __get_db()->__insert_c(this); 1948261272Sdim#endif 1949227825Stheraven insert(__first, __last); 1950227825Stheraven} 1951227825Stheraven 1952227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1953227825Stheraventemplate <class _InputIterator> 1954227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1955227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1956227825Stheraven const hasher& __hf, const key_equal& __eql) 1957227825Stheraven : __table_(__hf, __eql) 1958227825Stheraven{ 1959261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1960261272Sdim __get_db()->__insert_c(this); 1961261272Sdim#endif 1962227825Stheraven __table_.rehash(__n); 1963227825Stheraven insert(__first, __last); 1964227825Stheraven} 1965227825Stheraven 1966227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1967227825Stheraventemplate <class _InputIterator> 1968227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1969227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1970227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1971227825Stheraven : __table_(__hf, __eql, __a) 1972227825Stheraven{ 1973261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1974261272Sdim __get_db()->__insert_c(this); 1975261272Sdim#endif 1976227825Stheraven __table_.rehash(__n); 1977227825Stheraven insert(__first, __last); 1978227825Stheraven} 1979227825Stheraven 1980227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1981227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1982227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1983227825Stheraven const allocator_type& __a) 1984227825Stheraven : __table_(__a) 1985227825Stheraven{ 1986261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1987261272Sdim __get_db()->__insert_c(this); 1988261272Sdim#endif 1989227825Stheraven} 1990227825Stheraven 1991227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1992227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1993227825Stheraven const unordered_multimap& __u) 1994227825Stheraven : __table_(__u.__table_) 1995227825Stheraven{ 1996261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1997261272Sdim __get_db()->__insert_c(this); 1998261272Sdim#endif 1999227825Stheraven __table_.rehash(__u.bucket_count()); 2000227825Stheraven insert(__u.begin(), __u.end()); 2001227825Stheraven} 2002227825Stheraven 2003227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2004227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2005227825Stheraven const unordered_multimap& __u, const allocator_type& __a) 2006227825Stheraven : __table_(__u.__table_, __a) 2007227825Stheraven{ 2008261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2009261272Sdim __get_db()->__insert_c(this); 2010261272Sdim#endif 2011227825Stheraven __table_.rehash(__u.bucket_count()); 2012227825Stheraven insert(__u.begin(), __u.end()); 2013227825Stheraven} 2014227825Stheraven 2015227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2016227825Stheraven 2017227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2018227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2019227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2020227825Stheraven unordered_multimap&& __u) 2021227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 2022227825Stheraven : __table_(_VSTD::move(__u.__table_)) 2023227825Stheraven{ 2024261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2025261272Sdim __get_db()->__insert_c(this); 2026261272Sdim __get_db()->swap(this, &__u); 2027261272Sdim#endif 2028227825Stheraven} 2029227825Stheraven 2030227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2031227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2032227825Stheraven unordered_multimap&& __u, const allocator_type& __a) 2033227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 2034227825Stheraven{ 2035261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2036261272Sdim __get_db()->__insert_c(this); 2037261272Sdim#endif 2038227825Stheraven if (__a != __u.get_allocator()) 2039227825Stheraven { 2040227825Stheraven iterator __i = __u.begin(); 2041227825Stheraven while (__u.size() != 0) 2042261272Sdim { 2043227825Stheraven __table_.__insert_multi( 2044227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 2045227825Stheraven ); 2046261272Sdim } 2047227825Stheraven } 2048261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2049261272Sdim else 2050261272Sdim __get_db()->swap(this, &__u); 2051261272Sdim#endif 2052227825Stheraven} 2053227825Stheraven 2054227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2055227825Stheraven 2056227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2057227825Stheraven 2058227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2059227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2060227825Stheraven initializer_list<value_type> __il) 2061227825Stheraven{ 2062261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2063261272Sdim __get_db()->__insert_c(this); 2064261272Sdim#endif 2065227825Stheraven insert(__il.begin(), __il.end()); 2066227825Stheraven} 2067227825Stheraven 2068227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2069227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2070227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 2071227825Stheraven const key_equal& __eql) 2072227825Stheraven : __table_(__hf, __eql) 2073227825Stheraven{ 2074261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2075261272Sdim __get_db()->__insert_c(this); 2076261272Sdim#endif 2077227825Stheraven __table_.rehash(__n); 2078227825Stheraven insert(__il.begin(), __il.end()); 2079227825Stheraven} 2080227825Stheraven 2081227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2082227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2083227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 2084227825Stheraven const key_equal& __eql, const allocator_type& __a) 2085227825Stheraven : __table_(__hf, __eql, __a) 2086227825Stheraven{ 2087261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2088261272Sdim __get_db()->__insert_c(this); 2089261272Sdim#endif 2090227825Stheraven __table_.rehash(__n); 2091227825Stheraven insert(__il.begin(), __il.end()); 2092227825Stheraven} 2093227825Stheraven 2094227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2095227825Stheraven 2096227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2097227825Stheraven 2098227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2099227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2100227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2101227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 2102227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 2103227825Stheraven{ 2104227825Stheraven __table_ = _VSTD::move(__u.__table_); 2105227825Stheraven return *this; 2106227825Stheraven} 2107227825Stheraven 2108227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2109227825Stheraven 2110227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2111227825Stheraven 2112227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2113227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2114227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2115227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 2116227825Stheraven initializer_list<value_type> __il) 2117227825Stheraven{ 2118227825Stheraven __table_.__assign_multi(__il.begin(), __il.end()); 2119227825Stheraven return *this; 2120227825Stheraven} 2121227825Stheraven 2122227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2123227825Stheraven 2124227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2125227825Stheraven 2126227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2127227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 2128241900Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 2129227825Stheraven{ 2130227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 2131232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2132241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 2133227825Stheraven __h.get_deleter().__first_constructed = true; 2134227825Stheraven __h.get_deleter().__second_constructed = true; 2135227825Stheraven return __h; 2136227825Stheraven} 2137227825Stheraven 2138227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2139241900Sdimtemplate <class _A0> 2140253146Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 2141227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 2142227825Stheraven{ 2143227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 2144232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2145227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 2146227825Stheraven _VSTD::forward<_A0>(__a0)); 2147227825Stheraven __h.get_deleter().__first_constructed = true; 2148227825Stheraven __h.get_deleter().__second_constructed = true; 2149227825Stheraven return __h; 2150227825Stheraven} 2151227825Stheraven 2152227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 2153227825Stheraven 2154227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2155241900Sdimtemplate <class _A0, class _A1, class ..._Args> 2156241900Sdimtypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 2157241900Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 2158241900Sdim _A0&& __a0, _A1&& __a1, _Args&&... __args) 2159241900Sdim{ 2160241900Sdim __node_allocator& __na = __table_.__node_alloc(); 2161241900Sdim __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2162241900Sdim __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 2163241900Sdim _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 2164241900Sdim _VSTD::forward<_Args>(__args)...); 2165241900Sdim __h.get_deleter().__first_constructed = true; 2166241900Sdim __h.get_deleter().__second_constructed = true; 2167241900Sdim return __h; 2168241900Sdim} 2169241900Sdim 2170241900Sdimtemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2171241900Sdimtemplate <class... _Args> 2172227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2173241900Sdimunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 2174227825Stheraven{ 2175241900Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2176227825Stheraven iterator __r = __table_.__node_insert_multi(__h.get()); 2177227825Stheraven __h.release(); 2178227825Stheraven return __r; 2179227825Stheraven} 2180227825Stheraven 2181227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2182241900Sdimtemplate <class... _Args> 2183227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2184227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 2185241900Sdim const_iterator __p, _Args&&... __args) 2186227825Stheraven{ 2187241900Sdim __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2188227825Stheraven iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 2189227825Stheraven __h.release(); 2190227825Stheraven return __r; 2191227825Stheraven} 2192227825Stheraven 2193227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 2194227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2195227825Stheraven 2196227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2197227825Stheraventemplate <class _InputIterator> 2198227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2199227825Stheravenvoid 2200227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 2201227825Stheraven _InputIterator __last) 2202227825Stheraven{ 2203227825Stheraven for (; __first != __last; ++__first) 2204227825Stheraven __table_.__insert_multi(*__first); 2205227825Stheraven} 2206227825Stheraven 2207227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2208227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2209227825Stheravenvoid 2210227825Stheravenswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2211227825Stheraven unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2212227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2213227825Stheraven{ 2214227825Stheraven __x.swap(__y); 2215227825Stheraven} 2216227825Stheraven 2217227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2218227825Stheravenbool 2219227825Stheravenoperator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2220227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2221227825Stheraven{ 2222227825Stheraven if (__x.size() != __y.size()) 2223227825Stheraven return false; 2224227825Stheraven typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 2225227825Stheraven const_iterator; 2226227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 2227227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 2228227825Stheraven { 2229227825Stheraven _EqRng __xeq = __x.equal_range(__i->first); 2230227825Stheraven _EqRng __yeq = __y.equal_range(__i->first); 2231227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 2232227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 2233227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2234227825Stheraven return false; 2235227825Stheraven __i = __xeq.second; 2236227825Stheraven } 2237227825Stheraven return true; 2238227825Stheraven} 2239227825Stheraven 2240227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2241227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2242227825Stheravenbool 2243227825Stheravenoperator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2244227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2245227825Stheraven{ 2246227825Stheraven return !(__x == __y); 2247227825Stheraven} 2248227825Stheraven 2249227825Stheraven_LIBCPP_END_NAMESPACE_STD 2250227825Stheraven 2251227825Stheraven#endif // _LIBCPP_UNORDERED_MAP 2252