unordered_map revision 232950
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===-------------------------- unordered_map -----------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP_UNORDERED_MAP 12227825Stheraven#define _LIBCPP_UNORDERED_MAP 13227825Stheraven 14227825Stheraven/* 15227825Stheraven 16227825Stheraven unordered_map synopsis 17227825Stheraven 18227825Stheraven#include <initializer_list> 19227825Stheraven 20227825Stheravennamespace std 21227825Stheraven{ 22227825Stheraven 23227825Stheraventemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 24227825Stheraven class Alloc = allocator<pair<const Key, T>>> 25227825Stheravenclass unordered_map 26227825Stheraven{ 27227825Stheravenpublic: 28227825Stheraven // types 29227825Stheraven typedef Key key_type; 30227825Stheraven typedef T mapped_type; 31227825Stheraven typedef Hash hasher; 32227825Stheraven typedef Pred key_equal; 33227825Stheraven typedef Alloc allocator_type; 34227825Stheraven typedef pair<const key_type, mapped_type> value_type; 35227825Stheraven typedef value_type& reference; 36227825Stheraven typedef const value_type& const_reference; 37227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 38227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 39227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 40227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 41227825Stheraven 42227825Stheraven typedef /unspecified/ iterator; 43227825Stheraven typedef /unspecified/ const_iterator; 44227825Stheraven typedef /unspecified/ local_iterator; 45227825Stheraven typedef /unspecified/ const_local_iterator; 46227825Stheraven 47227825Stheraven unordered_map() 48227825Stheraven noexcept( 49227825Stheraven is_nothrow_default_constructible<hasher>::value && 50227825Stheraven is_nothrow_default_constructible<key_equal>::value && 51227825Stheraven is_nothrow_default_constructible<allocator_type>::value); 52227825Stheraven explicit unordered_map(size_type n, const hasher& hf = hasher(), 53227825Stheraven const key_equal& eql = key_equal(), 54227825Stheraven const allocator_type& a = allocator_type()); 55227825Stheraven template <class InputIterator> 56227825Stheraven unordered_map(InputIterator f, InputIterator l, 57227825Stheraven size_type n = 0, const hasher& hf = hasher(), 58227825Stheraven const key_equal& eql = key_equal(), 59227825Stheraven const allocator_type& a = allocator_type()); 60227825Stheraven explicit unordered_map(const allocator_type&); 61227825Stheraven unordered_map(const unordered_map&); 62227825Stheraven unordered_map(const unordered_map&, const Allocator&); 63227825Stheraven unordered_map(unordered_map&&) 64227825Stheraven noexcept( 65227825Stheraven is_nothrow_move_constructible<hasher>::value && 66227825Stheraven is_nothrow_move_constructible<key_equal>::value && 67227825Stheraven is_nothrow_move_constructible<allocator_type>::value); 68227825Stheraven unordered_map(unordered_map&&, const Allocator&); 69227825Stheraven unordered_map(initializer_list<value_type>, size_type n = 0, 70227825Stheraven const hasher& hf = hasher(), const key_equal& eql = key_equal(), 71227825Stheraven const allocator_type& a = allocator_type()); 72227825Stheraven ~unordered_map(); 73227825Stheraven unordered_map& operator=(const unordered_map&); 74227825Stheraven unordered_map& operator=(unordered_map&&) 75227825Stheraven noexcept( 76227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 77227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 78227825Stheraven is_nothrow_move_assignable<hasher>::value && 79227825Stheraven is_nothrow_move_assignable<key_equal>::value); 80227825Stheraven unordered_map& operator=(initializer_list<value_type>); 81227825Stheraven 82227825Stheraven allocator_type get_allocator() const noexcept; 83227825Stheraven 84227825Stheraven bool empty() const noexcept; 85227825Stheraven size_type size() const noexcept; 86227825Stheraven size_type max_size() const noexcept; 87227825Stheraven 88227825Stheraven iterator begin() noexcept; 89227825Stheraven iterator end() noexcept; 90227825Stheraven const_iterator begin() const noexcept; 91227825Stheraven const_iterator end() const noexcept; 92227825Stheraven const_iterator cbegin() const noexcept; 93227825Stheraven const_iterator cend() const noexcept; 94227825Stheraven 95227825Stheraven template <class... Args> 96227825Stheraven pair<iterator, bool> emplace(Args&&... args); 97227825Stheraven template <class... Args> 98227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 99227825Stheraven pair<iterator, bool> insert(const value_type& obj); 100227825Stheraven template <class P> 101227825Stheraven pair<iterator, bool> insert(P&& obj); 102227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 103227825Stheraven template <class P> 104227825Stheraven iterator insert(const_iterator hint, P&& obj); 105227825Stheraven template <class InputIterator> 106227825Stheraven void insert(InputIterator first, InputIterator last); 107227825Stheraven void insert(initializer_list<value_type>); 108227825Stheraven 109227825Stheraven iterator erase(const_iterator position); 110227825Stheraven size_type erase(const key_type& k); 111227825Stheraven iterator erase(const_iterator first, const_iterator last); 112227825Stheraven void clear() noexcept; 113227825Stheraven 114227825Stheraven void swap(unordered_map&) 115227825Stheraven noexcept( 116227825Stheraven (!allocator_type::propagate_on_container_swap::value || 117227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 118227825Stheraven __is_nothrow_swappable<hasher>::value && 119227825Stheraven __is_nothrow_swappable<key_equal>::value); 120227825Stheraven 121227825Stheraven hasher hash_function() const; 122227825Stheraven key_equal key_eq() const; 123227825Stheraven 124227825Stheraven iterator find(const key_type& k); 125227825Stheraven const_iterator find(const key_type& k) const; 126227825Stheraven size_type count(const key_type& k) const; 127227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 128227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 129227825Stheraven 130227825Stheraven mapped_type& operator[](const key_type& k); 131227825Stheraven mapped_type& operator[](key_type&& k); 132227825Stheraven 133227825Stheraven mapped_type& at(const key_type& k); 134227825Stheraven const mapped_type& at(const key_type& k) const; 135227825Stheraven 136227825Stheraven size_type bucket_count() const noexcept; 137227825Stheraven size_type max_bucket_count() const noexcept; 138227825Stheraven 139227825Stheraven size_type bucket_size(size_type n) const; 140227825Stheraven size_type bucket(const key_type& k) const; 141227825Stheraven 142227825Stheraven local_iterator begin(size_type n); 143227825Stheraven local_iterator end(size_type n); 144227825Stheraven const_local_iterator begin(size_type n) const; 145227825Stheraven const_local_iterator end(size_type n) const; 146227825Stheraven const_local_iterator cbegin(size_type n) const; 147227825Stheraven const_local_iterator cend(size_type n) const; 148227825Stheraven 149227825Stheraven float load_factor() const noexcept; 150227825Stheraven float max_load_factor() const noexcept; 151227825Stheraven void max_load_factor(float z); 152227825Stheraven void rehash(size_type n); 153227825Stheraven void reserve(size_type n); 154227825Stheraven}; 155227825Stheraven 156227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 157227825Stheraven void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x, 158227825Stheraven unordered_map<Key, T, Hash, Pred, Alloc>& y) 159227825Stheraven noexcept(noexcept(x.swap(y))); 160227825Stheraven 161227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 162227825Stheraven bool 163227825Stheraven operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 164227825Stheraven const unordered_map<Key, T, Hash, Pred, Alloc>& y); 165227825Stheraven 166227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 167227825Stheraven bool 168227825Stheraven operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 169227825Stheraven const unordered_map<Key, T, Hash, Pred, Alloc>& y); 170227825Stheraven 171227825Stheraventemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 172227825Stheraven class Alloc = allocator<pair<const Key, T>>> 173227825Stheravenclass unordered_multimap 174227825Stheraven{ 175227825Stheravenpublic: 176227825Stheraven // types 177227825Stheraven typedef Key key_type; 178227825Stheraven typedef T mapped_type; 179227825Stheraven typedef Hash hasher; 180227825Stheraven typedef Pred key_equal; 181227825Stheraven typedef Alloc allocator_type; 182227825Stheraven typedef pair<const key_type, mapped_type> value_type; 183227825Stheraven typedef value_type& reference; 184227825Stheraven typedef const value_type& const_reference; 185227825Stheraven typedef typename allocator_traits<allocator_type>::pointer pointer; 186227825Stheraven typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 187227825Stheraven typedef typename allocator_traits<allocator_type>::size_type size_type; 188227825Stheraven typedef typename allocator_traits<allocator_type>::difference_type difference_type; 189227825Stheraven 190227825Stheraven typedef /unspecified/ iterator; 191227825Stheraven typedef /unspecified/ const_iterator; 192227825Stheraven typedef /unspecified/ local_iterator; 193227825Stheraven typedef /unspecified/ const_local_iterator; 194227825Stheraven 195227825Stheraven unordered_multimap() 196227825Stheraven noexcept( 197227825Stheraven is_nothrow_default_constructible<hasher>::value && 198227825Stheraven is_nothrow_default_constructible<key_equal>::value && 199227825Stheraven is_nothrow_default_constructible<allocator_type>::value); 200227825Stheraven explicit unordered_multimap(size_type n, const hasher& hf = hasher(), 201227825Stheraven const key_equal& eql = key_equal(), 202227825Stheraven const allocator_type& a = allocator_type()); 203227825Stheraven template <class InputIterator> 204227825Stheraven unordered_multimap(InputIterator f, InputIterator l, 205227825Stheraven size_type n = 0, const hasher& hf = hasher(), 206227825Stheraven const key_equal& eql = key_equal(), 207227825Stheraven const allocator_type& a = allocator_type()); 208227825Stheraven explicit unordered_multimap(const allocator_type&); 209227825Stheraven unordered_multimap(const unordered_multimap&); 210227825Stheraven unordered_multimap(const unordered_multimap&, const Allocator&); 211227825Stheraven unordered_multimap(unordered_multimap&&) 212227825Stheraven noexcept( 213227825Stheraven is_nothrow_move_constructible<hasher>::value && 214227825Stheraven is_nothrow_move_constructible<key_equal>::value && 215227825Stheraven is_nothrow_move_constructible<allocator_type>::value); 216227825Stheraven unordered_multimap(unordered_multimap&&, const Allocator&); 217227825Stheraven unordered_multimap(initializer_list<value_type>, size_type n = 0, 218227825Stheraven const hasher& hf = hasher(), const key_equal& eql = key_equal(), 219227825Stheraven const allocator_type& a = allocator_type()); 220227825Stheraven ~unordered_multimap(); 221227825Stheraven unordered_multimap& operator=(const unordered_multimap&); 222227825Stheraven unordered_multimap& operator=(unordered_multimap&&) 223227825Stheraven noexcept( 224227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 225227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 226227825Stheraven is_nothrow_move_assignable<hasher>::value && 227227825Stheraven is_nothrow_move_assignable<key_equal>::value); 228227825Stheraven unordered_multimap& operator=(initializer_list<value_type>); 229227825Stheraven 230227825Stheraven allocator_type get_allocator() const noexcept; 231227825Stheraven 232227825Stheraven bool empty() const noexcept; 233227825Stheraven size_type size() const noexcept; 234227825Stheraven size_type max_size() const noexcept; 235227825Stheraven 236227825Stheraven iterator begin() noexcept; 237227825Stheraven iterator end() noexcept; 238227825Stheraven const_iterator begin() const noexcept; 239227825Stheraven const_iterator end() const noexcept; 240227825Stheraven const_iterator cbegin() const noexcept; 241227825Stheraven const_iterator cend() const noexcept; 242227825Stheraven 243227825Stheraven template <class... Args> 244227825Stheraven iterator emplace(Args&&... args); 245227825Stheraven template <class... Args> 246227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 247227825Stheraven iterator insert(const value_type& obj); 248227825Stheraven template <class P> 249227825Stheraven iterator insert(P&& obj); 250227825Stheraven iterator insert(const_iterator hint, const value_type& obj); 251227825Stheraven template <class P> 252227825Stheraven iterator insert(const_iterator hint, P&& obj); 253227825Stheraven template <class InputIterator> 254227825Stheraven void insert(InputIterator first, InputIterator last); 255227825Stheraven void insert(initializer_list<value_type>); 256227825Stheraven 257227825Stheraven iterator erase(const_iterator position); 258227825Stheraven size_type erase(const key_type& k); 259227825Stheraven iterator erase(const_iterator first, const_iterator last); 260227825Stheraven void clear() noexcept; 261227825Stheraven 262227825Stheraven void swap(unordered_multimap&) 263227825Stheraven noexcept( 264227825Stheraven (!allocator_type::propagate_on_container_swap::value || 265227825Stheraven __is_nothrow_swappable<allocator_type>::value) && 266227825Stheraven __is_nothrow_swappable<hasher>::value && 267227825Stheraven __is_nothrow_swappable<key_equal>::value); 268227825Stheraven 269227825Stheraven hasher hash_function() const; 270227825Stheraven key_equal key_eq() const; 271227825Stheraven 272227825Stheraven iterator find(const key_type& k); 273227825Stheraven const_iterator find(const key_type& k) const; 274227825Stheraven size_type count(const key_type& k) const; 275227825Stheraven pair<iterator, iterator> equal_range(const key_type& k); 276227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 277227825Stheraven 278227825Stheraven size_type bucket_count() const noexcept; 279227825Stheraven size_type max_bucket_count() const noexcept; 280227825Stheraven 281227825Stheraven size_type bucket_size(size_type n) const; 282227825Stheraven size_type bucket(const key_type& k) const; 283227825Stheraven 284227825Stheraven local_iterator begin(size_type n); 285227825Stheraven local_iterator end(size_type n); 286227825Stheraven const_local_iterator begin(size_type n) const; 287227825Stheraven const_local_iterator end(size_type n) const; 288227825Stheraven const_local_iterator cbegin(size_type n) const; 289227825Stheraven const_local_iterator cend(size_type n) const; 290227825Stheraven 291227825Stheraven float load_factor() const noexcept; 292227825Stheraven float max_load_factor() const noexcept; 293227825Stheraven void max_load_factor(float z); 294227825Stheraven void rehash(size_type n); 295227825Stheraven void reserve(size_type n); 296227825Stheraven}; 297227825Stheraven 298227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 299227825Stheraven void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 300227825Stheraven unordered_multimap<Key, T, Hash, Pred, Alloc>& y) 301227825Stheraven noexcept(noexcept(x.swap(y))); 302227825Stheraven 303227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 304227825Stheraven bool 305227825Stheraven operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 306227825Stheraven const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 307227825Stheraven 308227825Stheraventemplate <class Key, class T, class Hash, class Pred, class Alloc> 309227825Stheraven bool 310227825Stheraven operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 311227825Stheraven const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 312227825Stheraven 313227825Stheraven} // std 314227825Stheraven 315227825Stheraven*/ 316227825Stheraven 317227825Stheraven#include <__config> 318227825Stheraven#include <__hash_table> 319227825Stheraven#include <functional> 320227825Stheraven#include <stdexcept> 321227825Stheraven 322227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 323227825Stheraven#pragma GCC system_header 324227825Stheraven#endif 325227825Stheraven 326227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 327227825Stheraven 328232950Stheraventemplate <class _Key, class _Tp, class _Hash, bool = is_empty<_Hash>::value 329232950Stheraven#if __has_feature(is_final) 330232950Stheraven && !__is_final(_Hash) 331232950Stheraven#endif 332232950Stheraven > 333227825Stheravenclass __unordered_map_hasher 334227825Stheraven : private _Hash 335227825Stheraven{ 336232950Stheraven typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; 337232950Stheraven typedef pair<const _Key, _Tp> _Cp; 338227825Stheravenpublic: 339227825Stheraven _LIBCPP_INLINE_VISIBILITY 340227825Stheraven __unordered_map_hasher() 341227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 342227825Stheraven : _Hash() {} 343227825Stheraven _LIBCPP_INLINE_VISIBILITY 344227825Stheraven __unordered_map_hasher(const _Hash& __h) 345227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 346227825Stheraven : _Hash(__h) {} 347227825Stheraven _LIBCPP_INLINE_VISIBILITY 348227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return *this;} 349227825Stheraven _LIBCPP_INLINE_VISIBILITY 350232950Stheraven size_t operator()(const _Pp& __x) const 351227825Stheraven {return static_cast<const _Hash&>(*this)(__x.first);} 352227825Stheraven _LIBCPP_INLINE_VISIBILITY 353232950Stheraven size_t operator()(const _Cp& __x) const 354232950Stheraven {return static_cast<const _Hash&>(*this)(__x.first);} 355232950Stheraven _LIBCPP_INLINE_VISIBILITY 356232950Stheraven size_t operator()(const _Key& __x) const 357227825Stheraven {return static_cast<const _Hash&>(*this)(__x);} 358227825Stheraven}; 359227825Stheraven 360232950Stheraventemplate <class _Key, class _Tp, class _Hash> 361232950Stheravenclass __unordered_map_hasher<_Key, _Tp, _Hash, false> 362227825Stheraven{ 363227825Stheraven _Hash __hash_; 364232950Stheraven 365232950Stheraven typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; 366232950Stheraven typedef pair<const _Key, _Tp> _Cp; 367227825Stheravenpublic: 368227825Stheraven _LIBCPP_INLINE_VISIBILITY 369227825Stheraven __unordered_map_hasher() 370227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 371227825Stheraven : __hash_() {} 372227825Stheraven _LIBCPP_INLINE_VISIBILITY 373227825Stheraven __unordered_map_hasher(const _Hash& __h) 374227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 375227825Stheraven : __hash_(__h) {} 376227825Stheraven _LIBCPP_INLINE_VISIBILITY 377227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 378227825Stheraven _LIBCPP_INLINE_VISIBILITY 379232950Stheraven size_t operator()(const _Pp& __x) const 380227825Stheraven {return __hash_(__x.first);} 381227825Stheraven _LIBCPP_INLINE_VISIBILITY 382232950Stheraven size_t operator()(const _Cp& __x) const 383232950Stheraven {return __hash_(__x.first);} 384232950Stheraven _LIBCPP_INLINE_VISIBILITY 385232950Stheraven size_t operator()(const _Key& __x) const 386227825Stheraven {return __hash_(__x);} 387227825Stheraven}; 388227825Stheraven 389232950Stheraventemplate <class _Key, class _Tp, class _Pred, bool = is_empty<_Pred>::value 390232950Stheraven#if __has_feature(is_final) 391232950Stheraven && !__is_final(_Pred) 392232950Stheraven#endif 393232950Stheraven > 394227825Stheravenclass __unordered_map_equal 395227825Stheraven : private _Pred 396227825Stheraven{ 397232950Stheraven typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; 398232950Stheraven typedef pair<const _Key, _Tp> _Cp; 399227825Stheravenpublic: 400227825Stheraven _LIBCPP_INLINE_VISIBILITY 401227825Stheraven __unordered_map_equal() 402227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 403227825Stheraven : _Pred() {} 404227825Stheraven _LIBCPP_INLINE_VISIBILITY 405227825Stheraven __unordered_map_equal(const _Pred& __p) 406227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 407227825Stheraven : _Pred(__p) {} 408227825Stheraven _LIBCPP_INLINE_VISIBILITY 409227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return *this;} 410227825Stheraven _LIBCPP_INLINE_VISIBILITY 411232950Stheraven bool operator()(const _Pp& __x, const _Pp& __y) const 412227825Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 413227825Stheraven _LIBCPP_INLINE_VISIBILITY 414232950Stheraven bool operator()(const _Pp& __x, const _Cp& __y) const 415232950Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 416227825Stheraven _LIBCPP_INLINE_VISIBILITY 417232950Stheraven bool operator()(const _Pp& __x, const _Key& __y) const 418227825Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y);} 419227825Stheraven _LIBCPP_INLINE_VISIBILITY 420232950Stheraven bool operator()(const _Cp& __x, const _Pp& __y) const 421232950Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 422232950Stheraven _LIBCPP_INLINE_VISIBILITY 423232950Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 424232950Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 425232950Stheraven _LIBCPP_INLINE_VISIBILITY 426232950Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 427232950Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y);} 428232950Stheraven _LIBCPP_INLINE_VISIBILITY 429232950Stheraven bool operator()(const _Key& __x, const _Pp& __y) const 430232950Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.first);} 431232950Stheraven _LIBCPP_INLINE_VISIBILITY 432232950Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 433232950Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.first);} 434232950Stheraven _LIBCPP_INLINE_VISIBILITY 435232950Stheraven bool operator()(const _Key& __x, const _Key& __y) const 436227825Stheraven {return static_cast<const _Pred&>(*this)(__x, __y);} 437227825Stheraven}; 438227825Stheraven 439232950Stheraventemplate <class _Key, class _Tp, class _Pred> 440232950Stheravenclass __unordered_map_equal<_Key, _Tp, _Pred, false> 441227825Stheraven{ 442227825Stheraven _Pred __pred_; 443232950Stheraven 444232950Stheraven typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; 445232950Stheraven typedef pair<const _Key, _Tp> _Cp; 446227825Stheravenpublic: 447227825Stheraven _LIBCPP_INLINE_VISIBILITY 448227825Stheraven __unordered_map_equal() 449227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 450227825Stheraven : __pred_() {} 451227825Stheraven _LIBCPP_INLINE_VISIBILITY 452227825Stheraven __unordered_map_equal(const _Pred& __p) 453227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 454227825Stheraven : __pred_(__p) {} 455227825Stheraven _LIBCPP_INLINE_VISIBILITY 456227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 457227825Stheraven _LIBCPP_INLINE_VISIBILITY 458232950Stheraven bool operator()(const _Pp& __x, const _Pp& __y) const 459227825Stheraven {return __pred_(__x.first, __y.first);} 460227825Stheraven _LIBCPP_INLINE_VISIBILITY 461232950Stheraven bool operator()(const _Pp& __x, const _Cp& __y) const 462232950Stheraven {return __pred_(__x.first, __y.first);} 463227825Stheraven _LIBCPP_INLINE_VISIBILITY 464232950Stheraven bool operator()(const _Pp& __x, const _Key& __y) const 465227825Stheraven {return __pred_(__x.first, __y);} 466227825Stheraven _LIBCPP_INLINE_VISIBILITY 467232950Stheraven bool operator()(const _Cp& __x, const _Pp& __y) const 468232950Stheraven {return __pred_(__x.first, __y.first);} 469232950Stheraven _LIBCPP_INLINE_VISIBILITY 470232950Stheraven bool operator()(const _Cp& __x, const _Cp& __y) const 471232950Stheraven {return __pred_(__x.first, __y.first);} 472232950Stheraven _LIBCPP_INLINE_VISIBILITY 473232950Stheraven bool operator()(const _Cp& __x, const _Key& __y) const 474232950Stheraven {return __pred_(__x.first, __y);} 475232950Stheraven _LIBCPP_INLINE_VISIBILITY 476232950Stheraven bool operator()(const _Key& __x, const _Pp& __y) const 477232950Stheraven {return __pred_(__x, __y.first);} 478232950Stheraven _LIBCPP_INLINE_VISIBILITY 479232950Stheraven bool operator()(const _Key& __x, const _Cp& __y) const 480232950Stheraven {return __pred_(__x, __y.first);} 481232950Stheraven _LIBCPP_INLINE_VISIBILITY 482232950Stheraven bool operator()(const _Key& __x, const _Key& __y) const 483227825Stheraven {return __pred_(__x, __y);} 484227825Stheraven}; 485227825Stheraven 486227825Stheraventemplate <class _Alloc> 487227825Stheravenclass __hash_map_node_destructor 488227825Stheraven{ 489227825Stheraven typedef _Alloc allocator_type; 490227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 491227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 492227825Stheravenpublic: 493227825Stheraven typedef typename __alloc_traits::pointer pointer; 494227825Stheravenprivate: 495227825Stheraven typedef typename value_type::first_type first_type; 496227825Stheraven typedef typename value_type::second_type second_type; 497227825Stheraven 498227825Stheraven allocator_type& __na_; 499227825Stheraven 500227825Stheraven __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 501227825Stheraven 502227825Stheravenpublic: 503227825Stheraven bool __first_constructed; 504227825Stheraven bool __second_constructed; 505227825Stheraven 506227825Stheraven _LIBCPP_INLINE_VISIBILITY 507227825Stheraven explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 508227825Stheraven : __na_(__na), 509227825Stheraven __first_constructed(false), 510227825Stheraven __second_constructed(false) 511227825Stheraven {} 512227825Stheraven 513227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 514227825Stheraven _LIBCPP_INLINE_VISIBILITY 515227825Stheraven __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 516227825Stheraven _NOEXCEPT 517227825Stheraven : __na_(__x.__na_), 518227825Stheraven __first_constructed(__x.__value_constructed), 519227825Stheraven __second_constructed(__x.__value_constructed) 520227825Stheraven { 521227825Stheraven __x.__value_constructed = false; 522227825Stheraven } 523227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 524227825Stheraven _LIBCPP_INLINE_VISIBILITY 525227825Stheraven __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 526227825Stheraven : __na_(__x.__na_), 527227825Stheraven __first_constructed(__x.__value_constructed), 528227825Stheraven __second_constructed(__x.__value_constructed) 529227825Stheraven { 530227825Stheraven const_cast<bool&>(__x.__value_constructed) = false; 531227825Stheraven } 532227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 533227825Stheraven 534227825Stheraven _LIBCPP_INLINE_VISIBILITY 535227825Stheraven void operator()(pointer __p) _NOEXCEPT 536227825Stheraven { 537227825Stheraven if (__second_constructed) 538227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second)); 539227825Stheraven if (__first_constructed) 540227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); 541227825Stheraven if (__p) 542227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 543227825Stheraven } 544227825Stheraven}; 545227825Stheraven 546227825Stheraventemplate <class _HashIterator> 547227825Stheravenclass _LIBCPP_VISIBLE __hash_map_iterator 548227825Stheraven{ 549227825Stheraven _HashIterator __i_; 550227825Stheraven 551227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 552227825Stheraven typedef const typename _HashIterator::value_type::first_type key_type; 553227825Stheraven typedef typename _HashIterator::value_type::second_type mapped_type; 554227825Stheravenpublic: 555227825Stheraven typedef forward_iterator_tag iterator_category; 556227825Stheraven typedef pair<key_type, mapped_type> value_type; 557227825Stheraven typedef typename _HashIterator::difference_type difference_type; 558227825Stheraven typedef value_type& reference; 559227825Stheraven typedef typename __pointer_traits::template 560227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 561227825Stheraven rebind<value_type> 562227825Stheraven#else 563227825Stheraven rebind<value_type>::other 564227825Stheraven#endif 565227825Stheraven pointer; 566227825Stheraven 567227825Stheraven _LIBCPP_INLINE_VISIBILITY 568227825Stheraven __hash_map_iterator() _NOEXCEPT {} 569227825Stheraven 570227825Stheraven _LIBCPP_INLINE_VISIBILITY 571227825Stheraven __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 572227825Stheraven 573227825Stheraven _LIBCPP_INLINE_VISIBILITY 574227825Stheraven reference operator*() const {return *operator->();} 575227825Stheraven _LIBCPP_INLINE_VISIBILITY 576227825Stheraven pointer operator->() const {return (pointer)__i_.operator->();} 577227825Stheraven 578227825Stheraven _LIBCPP_INLINE_VISIBILITY 579227825Stheraven __hash_map_iterator& operator++() {++__i_; return *this;} 580227825Stheraven _LIBCPP_INLINE_VISIBILITY 581227825Stheraven __hash_map_iterator operator++(int) 582227825Stheraven { 583227825Stheraven __hash_map_iterator __t(*this); 584227825Stheraven ++(*this); 585227825Stheraven return __t; 586227825Stheraven } 587227825Stheraven 588227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 589227825Stheraven bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 590227825Stheraven {return __x.__i_ == __y.__i_;} 591227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 592227825Stheraven bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 593227825Stheraven {return __x.__i_ != __y.__i_;} 594227825Stheraven 595227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; 596227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; 597227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator; 598227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator; 599227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator; 600227825Stheraven}; 601227825Stheraven 602227825Stheraventemplate <class _HashIterator> 603227825Stheravenclass _LIBCPP_VISIBLE __hash_map_const_iterator 604227825Stheraven{ 605227825Stheraven _HashIterator __i_; 606227825Stheraven 607227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 608227825Stheraven typedef const typename _HashIterator::value_type::first_type key_type; 609227825Stheraven typedef typename _HashIterator::value_type::second_type mapped_type; 610227825Stheravenpublic: 611227825Stheraven typedef forward_iterator_tag iterator_category; 612227825Stheraven typedef pair<key_type, mapped_type> value_type; 613227825Stheraven typedef typename _HashIterator::difference_type difference_type; 614227825Stheraven typedef const value_type& reference; 615227825Stheraven typedef typename __pointer_traits::template 616227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 617227825Stheraven rebind<const value_type> 618227825Stheraven#else 619227825Stheraven rebind<const value_type>::other 620227825Stheraven#endif 621227825Stheraven pointer; 622227825Stheraven 623227825Stheraven _LIBCPP_INLINE_VISIBILITY 624227825Stheraven __hash_map_const_iterator() _NOEXCEPT {} 625227825Stheraven 626227825Stheraven _LIBCPP_INLINE_VISIBILITY 627227825Stheraven __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 628227825Stheraven _LIBCPP_INLINE_VISIBILITY 629227825Stheraven __hash_map_const_iterator( 630227825Stheraven __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 631227825Stheraven _NOEXCEPT 632227825Stheraven : __i_(__i.__i_) {} 633227825Stheraven 634227825Stheraven _LIBCPP_INLINE_VISIBILITY 635227825Stheraven reference operator*() const {return *operator->();} 636227825Stheraven _LIBCPP_INLINE_VISIBILITY 637227825Stheraven pointer operator->() const {return (pointer)__i_.operator->();} 638227825Stheraven 639227825Stheraven _LIBCPP_INLINE_VISIBILITY 640227825Stheraven __hash_map_const_iterator& operator++() {++__i_; return *this;} 641227825Stheraven _LIBCPP_INLINE_VISIBILITY 642227825Stheraven __hash_map_const_iterator operator++(int) 643227825Stheraven { 644227825Stheraven __hash_map_const_iterator __t(*this); 645227825Stheraven ++(*this); 646227825Stheraven return __t; 647227825Stheraven } 648227825Stheraven 649227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 650227825Stheraven bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 651227825Stheraven {return __x.__i_ == __y.__i_;} 652227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 653227825Stheraven bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 654227825Stheraven {return __x.__i_ != __y.__i_;} 655227825Stheraven 656227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; 657227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; 658227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator; 659227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator; 660227825Stheraven}; 661227825Stheraven 662227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 663227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 664227825Stheravenclass _LIBCPP_VISIBLE unordered_map 665227825Stheraven{ 666227825Stheravenpublic: 667227825Stheraven // types 668227825Stheraven typedef _Key key_type; 669227825Stheraven typedef _Tp mapped_type; 670227825Stheraven typedef _Hash hasher; 671227825Stheraven typedef _Pred key_equal; 672227825Stheraven typedef _Alloc allocator_type; 673227825Stheraven typedef pair<const key_type, mapped_type> value_type; 674227825Stheraven typedef value_type& reference; 675227825Stheraven typedef const value_type& const_reference; 676227825Stheraven 677227825Stheravenprivate: 678227825Stheraven typedef pair<key_type, mapped_type> __value_type; 679232950Stheraven typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher; 680232950Stheraven typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal; 681227825Stheraven typedef typename allocator_traits<allocator_type>::template 682227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 683227825Stheraven rebind_alloc<__value_type> 684227825Stheraven#else 685227825Stheraven rebind_alloc<__value_type>::other 686227825Stheraven#endif 687227825Stheraven __allocator_type; 688227825Stheraven 689227825Stheraven typedef __hash_table<__value_type, __hasher, 690227825Stheraven __key_equal, __allocator_type> __table; 691227825Stheraven 692227825Stheraven __table __table_; 693227825Stheraven 694227825Stheraven typedef typename __table::__node_pointer __node_pointer; 695227825Stheraven typedef typename __table::__node_const_pointer __node_const_pointer; 696227825Stheraven typedef typename __table::__node_traits __node_traits; 697227825Stheraven typedef typename __table::__node_allocator __node_allocator; 698227825Stheraven typedef typename __table::__node __node; 699232950Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 700232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 701227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 702227825Stheravenpublic: 703227825Stheraven typedef typename __alloc_traits::pointer pointer; 704227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 705227825Stheraven typedef typename __alloc_traits::size_type size_type; 706227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 707227825Stheraven 708227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 709227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 710227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 711227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 712227825Stheraven 713227825Stheraven _LIBCPP_INLINE_VISIBILITY 714227825Stheraven unordered_map() 715227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 716227825Stheraven {} // = default; 717227825Stheraven explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 718227825Stheraven const key_equal& __eql = key_equal()); 719227825Stheraven unordered_map(size_type __n, const hasher& __hf, 720227825Stheraven const key_equal& __eql, 721227825Stheraven const allocator_type& __a); 722227825Stheraven template <class _InputIterator> 723227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last); 724227825Stheraven template <class _InputIterator> 725227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 726227825Stheraven size_type __n, const hasher& __hf = hasher(), 727227825Stheraven const key_equal& __eql = key_equal()); 728227825Stheraven template <class _InputIterator> 729227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 730227825Stheraven size_type __n, const hasher& __hf, 731227825Stheraven const key_equal& __eql, 732227825Stheraven const allocator_type& __a); 733227825Stheraven explicit unordered_map(const allocator_type& __a); 734227825Stheraven unordered_map(const unordered_map& __u); 735227825Stheraven unordered_map(const unordered_map& __u, const allocator_type& __a); 736227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 737227825Stheraven unordered_map(unordered_map&& __u) 738227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 739227825Stheraven unordered_map(unordered_map&& __u, const allocator_type& __a); 740227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 741227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 742227825Stheraven unordered_map(initializer_list<value_type> __il); 743227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 744227825Stheraven const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 745227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 746227825Stheraven const hasher& __hf, const key_equal& __eql, 747227825Stheraven const allocator_type& __a); 748227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 749227825Stheraven // ~unordered_map() = default; 750227825Stheraven _LIBCPP_INLINE_VISIBILITY 751227825Stheraven unordered_map& operator=(const unordered_map& __u) 752227825Stheraven { 753227825Stheraven __table_ = __u.__table_; 754227825Stheraven return *this; 755227825Stheraven } 756227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 757227825Stheraven unordered_map& operator=(unordered_map&& __u) 758227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 759227825Stheraven#endif 760227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 761227825Stheraven unordered_map& operator=(initializer_list<value_type> __il); 762227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 763227825Stheraven 764227825Stheraven _LIBCPP_INLINE_VISIBILITY 765227825Stheraven allocator_type get_allocator() const _NOEXCEPT 766227825Stheraven {return allocator_type(__table_.__node_alloc());} 767227825Stheraven 768227825Stheraven _LIBCPP_INLINE_VISIBILITY 769227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 770227825Stheraven _LIBCPP_INLINE_VISIBILITY 771227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 772227825Stheraven _LIBCPP_INLINE_VISIBILITY 773227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 774227825Stheraven 775227825Stheraven _LIBCPP_INLINE_VISIBILITY 776227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 777227825Stheraven _LIBCPP_INLINE_VISIBILITY 778227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 779227825Stheraven _LIBCPP_INLINE_VISIBILITY 780227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 781227825Stheraven _LIBCPP_INLINE_VISIBILITY 782227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 783227825Stheraven _LIBCPP_INLINE_VISIBILITY 784227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 785227825Stheraven _LIBCPP_INLINE_VISIBILITY 786227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 787227825Stheraven 788227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 789227825Stheraven _LIBCPP_INLINE_VISIBILITY 790227825Stheraven pair<iterator, bool> emplace() 791227825Stheraven {return __table_.__emplace_unique();} 792227825Stheraven 793227825Stheraven template <class _A0, 794227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 795227825Stheraven _LIBCPP_INLINE_VISIBILITY 796227825Stheraven pair<iterator, bool> emplace(_A0&& __a0) 797227825Stheraven {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0));} 798227825Stheraven 799227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 800227825Stheraven 801227825Stheraven template <class _A0, class... _Args, 802227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 803227825Stheraven pair<iterator, bool> emplace(_A0&& __a0, _Args&&... __args); 804227825Stheraven 805227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 806227825Stheraven 807227825Stheraven _LIBCPP_INLINE_VISIBILITY 808227825Stheraven iterator emplace_hint(const_iterator) 809227825Stheraven {return __table_.__emplace_unique().first;} 810227825Stheraven 811227825Stheraven template <class _A0, 812227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 813227825Stheraven _LIBCPP_INLINE_VISIBILITY 814227825Stheraven iterator emplace_hint(const_iterator, _A0&& __a0) 815227825Stheraven {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0)).first;} 816227825Stheraven 817227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 818227825Stheraven 819227825Stheraven template <class _A0, class... _Args, 820227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 821227825Stheraven _LIBCPP_INLINE_VISIBILITY 822227825Stheraven iterator emplace_hint(const_iterator, _A0&& __a0, _Args&&... __args) 823227825Stheraven {return emplace(_VSTD::forward<_A0>(__a0), 824227825Stheraven _VSTD::forward<_Args>(__args)...).first;} 825227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 826227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 827227825Stheraven _LIBCPP_INLINE_VISIBILITY 828227825Stheraven pair<iterator, bool> insert(const value_type& __x) 829227825Stheraven {return __table_.__insert_unique(__x);} 830227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 831232950Stheraven template <class _Pp, 832232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 833227825Stheraven _LIBCPP_INLINE_VISIBILITY 834232950Stheraven pair<iterator, bool> insert(_Pp&& __x) 835232950Stheraven {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 836227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 837227825Stheraven _LIBCPP_INLINE_VISIBILITY 838227825Stheraven iterator insert(const_iterator, const value_type& __x) 839227825Stheraven {return insert(__x).first;} 840227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 841232950Stheraven template <class _Pp, 842232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 843227825Stheraven _LIBCPP_INLINE_VISIBILITY 844232950Stheraven iterator insert(const_iterator, _Pp&& __x) 845232950Stheraven {return insert(_VSTD::forward<_Pp>(__x)).first;} 846227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 847227825Stheraven template <class _InputIterator> 848227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 849227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 850227825Stheraven _LIBCPP_INLINE_VISIBILITY 851227825Stheraven void insert(initializer_list<value_type> __il) 852227825Stheraven {insert(__il.begin(), __il.end());} 853227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 854227825Stheraven 855227825Stheraven _LIBCPP_INLINE_VISIBILITY 856227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 857227825Stheraven _LIBCPP_INLINE_VISIBILITY 858227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 859227825Stheraven _LIBCPP_INLINE_VISIBILITY 860227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 861227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 862227825Stheraven _LIBCPP_INLINE_VISIBILITY 863227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 864227825Stheraven 865227825Stheraven _LIBCPP_INLINE_VISIBILITY 866227825Stheraven void swap(unordered_map& __u) 867227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 868227825Stheraven {__table_.swap(__u.__table_);} 869227825Stheraven 870227825Stheraven _LIBCPP_INLINE_VISIBILITY 871227825Stheraven hasher hash_function() const 872227825Stheraven {return __table_.hash_function().hash_function();} 873227825Stheraven _LIBCPP_INLINE_VISIBILITY 874227825Stheraven key_equal key_eq() const 875227825Stheraven {return __table_.key_eq().key_eq();} 876227825Stheraven 877227825Stheraven _LIBCPP_INLINE_VISIBILITY 878227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 879227825Stheraven _LIBCPP_INLINE_VISIBILITY 880227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 881227825Stheraven _LIBCPP_INLINE_VISIBILITY 882227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 883227825Stheraven _LIBCPP_INLINE_VISIBILITY 884227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 885227825Stheraven {return __table_.__equal_range_unique(__k);} 886227825Stheraven _LIBCPP_INLINE_VISIBILITY 887227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 888227825Stheraven {return __table_.__equal_range_unique(__k);} 889227825Stheraven 890227825Stheraven mapped_type& operator[](const key_type& __k); 891227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 892227825Stheraven mapped_type& operator[](key_type&& __k); 893227825Stheraven#endif 894227825Stheraven 895227825Stheraven mapped_type& at(const key_type& __k); 896227825Stheraven const mapped_type& at(const key_type& __k) const; 897227825Stheraven 898227825Stheraven _LIBCPP_INLINE_VISIBILITY 899227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 900227825Stheraven _LIBCPP_INLINE_VISIBILITY 901227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 902227825Stheraven 903227825Stheraven _LIBCPP_INLINE_VISIBILITY 904227825Stheraven size_type bucket_size(size_type __n) const 905227825Stheraven {return __table_.bucket_size(__n);} 906227825Stheraven _LIBCPP_INLINE_VISIBILITY 907227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 908227825Stheraven 909227825Stheraven _LIBCPP_INLINE_VISIBILITY 910227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 911227825Stheraven _LIBCPP_INLINE_VISIBILITY 912227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 913227825Stheraven _LIBCPP_INLINE_VISIBILITY 914227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 915227825Stheraven _LIBCPP_INLINE_VISIBILITY 916227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 917227825Stheraven _LIBCPP_INLINE_VISIBILITY 918227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 919227825Stheraven _LIBCPP_INLINE_VISIBILITY 920227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 921227825Stheraven 922227825Stheraven _LIBCPP_INLINE_VISIBILITY 923227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 924227825Stheraven _LIBCPP_INLINE_VISIBILITY 925227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 926227825Stheraven _LIBCPP_INLINE_VISIBILITY 927227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 928227825Stheraven _LIBCPP_INLINE_VISIBILITY 929227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 930227825Stheraven _LIBCPP_INLINE_VISIBILITY 931227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 932227825Stheraven 933227825Stheravenprivate: 934227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 935227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 936227825Stheraven template <class _A0, class... _Args, 937227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 938227825Stheraven __node_holder __construct_node(_A0&& __a0, _Args&&... __args); 939227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 940227825Stheraven template <class _A0, 941227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 942227825Stheraven __node_holder __construct_node(_A0&& __a0); 943227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 944227825Stheraven __node_holder __construct_node(const key_type& __k); 945227825Stheraven#endif 946227825Stheraven}; 947227825Stheraven 948227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 949227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 950227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 951227825Stheraven : __table_(__hf, __eql) 952227825Stheraven{ 953227825Stheraven __table_.rehash(__n); 954227825Stheraven} 955227825Stheraven 956227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 957227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 958227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 959227825Stheraven const allocator_type& __a) 960227825Stheraven : __table_(__hf, __eql, __a) 961227825Stheraven{ 962227825Stheraven __table_.rehash(__n); 963227825Stheraven} 964227825Stheraven 965227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 966227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 967227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 968227825Stheraven const allocator_type& __a) 969227825Stheraven : __table_(__a) 970227825Stheraven{ 971227825Stheraven} 972227825Stheraven 973227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 974227825Stheraventemplate <class _InputIterator> 975227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 976227825Stheraven _InputIterator __first, _InputIterator __last) 977227825Stheraven{ 978227825Stheraven insert(__first, __last); 979227825Stheraven} 980227825Stheraven 981227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 982227825Stheraventemplate <class _InputIterator> 983227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 984227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 985227825Stheraven const hasher& __hf, const key_equal& __eql) 986227825Stheraven : __table_(__hf, __eql) 987227825Stheraven{ 988227825Stheraven __table_.rehash(__n); 989227825Stheraven insert(__first, __last); 990227825Stheraven} 991227825Stheraven 992227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 993227825Stheraventemplate <class _InputIterator> 994227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 995227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 996227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 997227825Stheraven : __table_(__hf, __eql, __a) 998227825Stheraven{ 999227825Stheraven __table_.rehash(__n); 1000227825Stheraven insert(__first, __last); 1001227825Stheraven} 1002227825Stheraven 1003227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1004227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1005227825Stheraven const unordered_map& __u) 1006227825Stheraven : __table_(__u.__table_) 1007227825Stheraven{ 1008227825Stheraven __table_.rehash(__u.bucket_count()); 1009227825Stheraven insert(__u.begin(), __u.end()); 1010227825Stheraven} 1011227825Stheraven 1012227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1013227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1014227825Stheraven const unordered_map& __u, const allocator_type& __a) 1015227825Stheraven : __table_(__u.__table_, __a) 1016227825Stheraven{ 1017227825Stheraven __table_.rehash(__u.bucket_count()); 1018227825Stheraven insert(__u.begin(), __u.end()); 1019227825Stheraven} 1020227825Stheraven 1021227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1022227825Stheraven 1023227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1024227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1025227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1026227825Stheraven unordered_map&& __u) 1027227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1028227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1029227825Stheraven{ 1030227825Stheraven} 1031227825Stheraven 1032227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1033227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1034227825Stheraven unordered_map&& __u, const allocator_type& __a) 1035227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1036227825Stheraven{ 1037227825Stheraven if (__a != __u.get_allocator()) 1038227825Stheraven { 1039227825Stheraven iterator __i = __u.begin(); 1040227825Stheraven while (__u.size() != 0) 1041227825Stheraven __table_.__insert_unique( 1042227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1043227825Stheraven ); 1044227825Stheraven } 1045227825Stheraven} 1046227825Stheraven 1047227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1048227825Stheraven 1049227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1050227825Stheraven 1051227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1052227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1053227825Stheraven initializer_list<value_type> __il) 1054227825Stheraven{ 1055227825Stheraven insert(__il.begin(), __il.end()); 1056227825Stheraven} 1057227825Stheraven 1058227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1059227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1060227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1061227825Stheraven const key_equal& __eql) 1062227825Stheraven : __table_(__hf, __eql) 1063227825Stheraven{ 1064227825Stheraven __table_.rehash(__n); 1065227825Stheraven insert(__il.begin(), __il.end()); 1066227825Stheraven} 1067227825Stheraven 1068227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1069227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1070227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1071227825Stheraven const key_equal& __eql, const allocator_type& __a) 1072227825Stheraven : __table_(__hf, __eql, __a) 1073227825Stheraven{ 1074227825Stheraven __table_.rehash(__n); 1075227825Stheraven insert(__il.begin(), __il.end()); 1076227825Stheraven} 1077227825Stheraven 1078227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1079227825Stheraven 1080227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1081227825Stheraven 1082227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1083227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1084227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1085227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1086227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1087227825Stheraven{ 1088227825Stheraven __table_ = _VSTD::move(__u.__table_); 1089227825Stheraven return *this; 1090227825Stheraven} 1091227825Stheraven 1092227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1093227825Stheraven 1094227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1095227825Stheraven 1096227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1097227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1098227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1099227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1100227825Stheraven initializer_list<value_type> __il) 1101227825Stheraven{ 1102227825Stheraven __table_.__assign_unique(__il.begin(), __il.end()); 1103227825Stheraven return *this; 1104227825Stheraven} 1105227825Stheraven 1106227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1107227825Stheraven 1108227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1109227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1110227825Stheraven 1111227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1112227825Stheraventemplate <class _A0, class... _Args, 1113227825Stheraven class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1114227825Stheraven > 1115227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1116227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1117227825Stheraven _Args&&... __args) 1118227825Stheraven{ 1119227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1120232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1121227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), 1122227825Stheraven _VSTD::forward<_A0>(__a0)); 1123227825Stheraven __h.get_deleter().__first_constructed = true; 1124227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second), 1125227825Stheraven _VSTD::forward<_Args>(__args)...); 1126227825Stheraven __h.get_deleter().__second_constructed = true; 1127227825Stheraven return __h; 1128227825Stheraven} 1129227825Stheraven 1130227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1131227825Stheraven 1132227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1133227825Stheraventemplate <class _A0, 1134227825Stheraven class // = typename enable_if<is_constructible<value_type, _A0>::value>::type 1135227825Stheraven > 1136227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1137227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1138227825Stheraven{ 1139227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1140232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1141227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1142227825Stheraven _VSTD::forward<_A0>(__a0)); 1143227825Stheraven __h.get_deleter().__first_constructed = true; 1144227825Stheraven __h.get_deleter().__second_constructed = true; 1145227825Stheraven return __h; 1146227825Stheraven} 1147227825Stheraven 1148227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1149227825Stheraven 1150227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1151227825Stheraventemplate <class _A0, class... _Args, 1152227825Stheraven class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1153227825Stheraven > 1154227825Stheravenpair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1155227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args) 1156227825Stheraven{ 1157227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0), 1158227825Stheraven _VSTD::forward<_Args>(__args)...); 1159227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1160227825Stheraven if (__r.second) 1161227825Stheraven __h.release(); 1162227825Stheraven return __r; 1163227825Stheraven} 1164227825Stheraven 1165227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1166227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1167227825Stheraven 1168227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1169227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1170227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) 1171227825Stheraven{ 1172227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1173232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1174227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); 1175227825Stheraven __h.get_deleter().__first_constructed = true; 1176227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1177227825Stheraven __h.get_deleter().__second_constructed = true; 1178227825Stheraven return _VSTD::move(__h); 1179227825Stheraven} 1180227825Stheraven 1181227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1182227825Stheraven 1183227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1184227825Stheraventemplate <class _InputIterator> 1185227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1186227825Stheravenvoid 1187227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1188227825Stheraven _InputIterator __last) 1189227825Stheraven{ 1190227825Stheraven for (; __first != __last; ++__first) 1191227825Stheraven __table_.__insert_unique(*__first); 1192227825Stheraven} 1193227825Stheraven 1194227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1195227825Stheraven_Tp& 1196227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1197227825Stheraven{ 1198227825Stheraven iterator __i = find(__k); 1199227825Stheraven if (__i != end()) 1200227825Stheraven return __i->second; 1201227825Stheraven __node_holder __h = __construct_node(__k); 1202227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1203227825Stheraven __h.release(); 1204227825Stheraven return __r.first->second; 1205227825Stheraven} 1206227825Stheraven 1207227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1208227825Stheraven 1209227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1210227825Stheraven_Tp& 1211227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1212227825Stheraven{ 1213227825Stheraven iterator __i = find(__k); 1214227825Stheraven if (__i != end()) 1215227825Stheraven return __i->second; 1216227825Stheraven __node_holder __h = __construct_node(_VSTD::move(__k)); 1217227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1218227825Stheraven __h.release(); 1219227825Stheraven return __r.first->second; 1220227825Stheraven} 1221227825Stheraven 1222227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1223227825Stheraven 1224227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1225227825Stheraven_Tp& 1226227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1227227825Stheraven{ 1228227825Stheraven iterator __i = find(__k); 1229227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1230227825Stheraven if (__i == end()) 1231227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1232227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1233227825Stheraven return __i->second; 1234227825Stheraven} 1235227825Stheraven 1236227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1237227825Stheravenconst _Tp& 1238227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1239227825Stheraven{ 1240227825Stheraven const_iterator __i = find(__k); 1241227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1242227825Stheraven if (__i == end()) 1243227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1244227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1245227825Stheraven return __i->second; 1246227825Stheraven} 1247227825Stheraven 1248227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1249227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1250227825Stheravenvoid 1251227825Stheravenswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1252227825Stheraven unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1253227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1254227825Stheraven{ 1255227825Stheraven __x.swap(__y); 1256227825Stheraven} 1257227825Stheraven 1258227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1259227825Stheravenbool 1260227825Stheravenoperator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1261227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1262227825Stheraven{ 1263227825Stheraven if (__x.size() != __y.size()) 1264227825Stheraven return false; 1265227825Stheraven typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1266227825Stheraven const_iterator; 1267227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1268227825Stheraven __i != __ex; ++__i) 1269227825Stheraven { 1270227825Stheraven const_iterator __j = __y.find(__i->first); 1271227825Stheraven if (__j == __ey || !(*__i == *__j)) 1272227825Stheraven return false; 1273227825Stheraven } 1274227825Stheraven return true; 1275227825Stheraven} 1276227825Stheraven 1277227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1278227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1279227825Stheravenbool 1280227825Stheravenoperator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1281227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1282227825Stheraven{ 1283227825Stheraven return !(__x == __y); 1284227825Stheraven} 1285227825Stheraven 1286227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1287227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 1288227825Stheravenclass _LIBCPP_VISIBLE unordered_multimap 1289227825Stheraven{ 1290227825Stheravenpublic: 1291227825Stheraven // types 1292227825Stheraven typedef _Key key_type; 1293227825Stheraven typedef _Tp mapped_type; 1294227825Stheraven typedef _Hash hasher; 1295227825Stheraven typedef _Pred key_equal; 1296227825Stheraven typedef _Alloc allocator_type; 1297227825Stheraven typedef pair<const key_type, mapped_type> value_type; 1298227825Stheraven typedef value_type& reference; 1299227825Stheraven typedef const value_type& const_reference; 1300227825Stheraven 1301227825Stheravenprivate: 1302227825Stheraven typedef pair<key_type, mapped_type> __value_type; 1303232950Stheraven typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher; 1304232950Stheraven typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal; 1305227825Stheraven typedef typename allocator_traits<allocator_type>::template 1306227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1307227825Stheraven rebind_alloc<__value_type> 1308227825Stheraven#else 1309227825Stheraven rebind_alloc<__value_type>::other 1310227825Stheraven#endif 1311227825Stheraven __allocator_type; 1312227825Stheraven 1313227825Stheraven typedef __hash_table<__value_type, __hasher, 1314227825Stheraven __key_equal, __allocator_type> __table; 1315227825Stheraven 1316227825Stheraven __table __table_; 1317227825Stheraven 1318227825Stheraven typedef typename __table::__node_traits __node_traits; 1319227825Stheraven typedef typename __table::__node_allocator __node_allocator; 1320227825Stheraven typedef typename __table::__node __node; 1321232950Stheraven typedef __hash_map_node_destructor<__node_allocator> _Dp; 1322232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 1323227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 1324227825Stheravenpublic: 1325227825Stheraven typedef typename __alloc_traits::pointer pointer; 1326227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 1327227825Stheraven typedef typename __alloc_traits::size_type size_type; 1328227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 1329227825Stheraven 1330227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 1331227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1332227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1333227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1334227825Stheraven 1335227825Stheraven _LIBCPP_INLINE_VISIBILITY 1336227825Stheraven unordered_multimap() 1337227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1338227825Stheraven {} // = default; 1339227825Stheraven explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1340227825Stheraven const key_equal& __eql = key_equal()); 1341227825Stheraven unordered_multimap(size_type __n, const hasher& __hf, 1342227825Stheraven const key_equal& __eql, 1343227825Stheraven const allocator_type& __a); 1344227825Stheraven template <class _InputIterator> 1345227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last); 1346227825Stheraven template <class _InputIterator> 1347227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1348227825Stheraven size_type __n, const hasher& __hf = hasher(), 1349227825Stheraven const key_equal& __eql = key_equal()); 1350227825Stheraven template <class _InputIterator> 1351227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1352227825Stheraven size_type __n, const hasher& __hf, 1353227825Stheraven const key_equal& __eql, 1354227825Stheraven const allocator_type& __a); 1355227825Stheraven explicit unordered_multimap(const allocator_type& __a); 1356227825Stheraven unordered_multimap(const unordered_multimap& __u); 1357227825Stheraven unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1358227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1359227825Stheraven unordered_multimap(unordered_multimap&& __u) 1360227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1361227825Stheraven unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1362227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1363227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1364227825Stheraven unordered_multimap(initializer_list<value_type> __il); 1365227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1366227825Stheraven const hasher& __hf = hasher(), 1367227825Stheraven const key_equal& __eql = key_equal()); 1368227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1369227825Stheraven const hasher& __hf, const key_equal& __eql, 1370227825Stheraven const allocator_type& __a); 1371227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1372227825Stheraven // ~unordered_multimap() = default; 1373227825Stheraven _LIBCPP_INLINE_VISIBILITY 1374227825Stheraven unordered_multimap& operator=(const unordered_multimap& __u) 1375227825Stheraven { 1376227825Stheraven __table_ = __u.__table_; 1377227825Stheraven return *this; 1378227825Stheraven } 1379227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1380227825Stheraven unordered_multimap& operator=(unordered_multimap&& __u) 1381227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1382227825Stheraven#endif 1383227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1384227825Stheraven unordered_multimap& operator=(initializer_list<value_type> __il); 1385227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1386227825Stheraven 1387227825Stheraven _LIBCPP_INLINE_VISIBILITY 1388227825Stheraven allocator_type get_allocator() const _NOEXCEPT 1389227825Stheraven {return allocator_type(__table_.__node_alloc());} 1390227825Stheraven 1391227825Stheraven _LIBCPP_INLINE_VISIBILITY 1392227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1393227825Stheraven _LIBCPP_INLINE_VISIBILITY 1394227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 1395227825Stheraven _LIBCPP_INLINE_VISIBILITY 1396227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1397227825Stheraven 1398227825Stheraven _LIBCPP_INLINE_VISIBILITY 1399227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 1400227825Stheraven _LIBCPP_INLINE_VISIBILITY 1401227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 1402227825Stheraven _LIBCPP_INLINE_VISIBILITY 1403227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1404227825Stheraven _LIBCPP_INLINE_VISIBILITY 1405227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 1406227825Stheraven _LIBCPP_INLINE_VISIBILITY 1407227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1408227825Stheraven _LIBCPP_INLINE_VISIBILITY 1409227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 1410227825Stheraven 1411227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1412227825Stheraven _LIBCPP_INLINE_VISIBILITY 1413227825Stheraven iterator emplace() 1414227825Stheraven {return __table_.__emplace_multi();} 1415227825Stheraven 1416227825Stheraven template <class _A0, 1417227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 1418227825Stheraven _LIBCPP_INLINE_VISIBILITY 1419227825Stheraven iterator emplace(_A0&& __a0) 1420227825Stheraven {return __table_.__emplace_multi(_VSTD::forward<_A0>(__a0));} 1421227825Stheraven 1422227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1423227825Stheraven 1424227825Stheraven template <class _A0, class... _Args, 1425227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 1426227825Stheraven iterator emplace(_A0&& __a0, _Args&&... __args); 1427227825Stheraven 1428227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1429227825Stheraven 1430227825Stheraven _LIBCPP_INLINE_VISIBILITY 1431227825Stheraven iterator emplace_hint(const_iterator __p) 1432227825Stheraven {return __table_.__emplace_hint_multi(__p.__i_);} 1433227825Stheraven 1434227825Stheraven template <class _A0, 1435227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 1436227825Stheraven _LIBCPP_INLINE_VISIBILITY 1437227825Stheraven iterator emplace_hint(const_iterator __p, _A0&& __a0) 1438227825Stheraven {return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_A0>(__a0));} 1439227825Stheraven 1440227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1441227825Stheraven 1442227825Stheraven template <class _A0, class... _Args, 1443227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 1444227825Stheraven iterator emplace_hint(const_iterator __p, _A0&& __a0, _Args&&... __args); 1445227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1446227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1447227825Stheraven _LIBCPP_INLINE_VISIBILITY 1448227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1449227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1450232950Stheraven template <class _Pp, 1451232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1452227825Stheraven _LIBCPP_INLINE_VISIBILITY 1453232950Stheraven iterator insert(_Pp&& __x) 1454232950Stheraven {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1455227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1456227825Stheraven _LIBCPP_INLINE_VISIBILITY 1457227825Stheraven iterator insert(const_iterator __p, const value_type& __x) 1458227825Stheraven {return __table_.__insert_multi(__p.__i_, __x);} 1459227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1460232950Stheraven template <class _Pp, 1461232950Stheraven class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1462227825Stheraven _LIBCPP_INLINE_VISIBILITY 1463232950Stheraven iterator insert(const_iterator __p, _Pp&& __x) 1464232950Stheraven {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1465227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1466227825Stheraven template <class _InputIterator> 1467227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 1468227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1469227825Stheraven _LIBCPP_INLINE_VISIBILITY 1470227825Stheraven void insert(initializer_list<value_type> __il) 1471227825Stheraven {insert(__il.begin(), __il.end());} 1472227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1473227825Stheraven 1474227825Stheraven _LIBCPP_INLINE_VISIBILITY 1475227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1476227825Stheraven _LIBCPP_INLINE_VISIBILITY 1477227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1478227825Stheraven _LIBCPP_INLINE_VISIBILITY 1479227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 1480227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 1481227825Stheraven _LIBCPP_INLINE_VISIBILITY 1482227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 1483227825Stheraven 1484227825Stheraven _LIBCPP_INLINE_VISIBILITY 1485227825Stheraven void swap(unordered_multimap& __u) 1486227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1487227825Stheraven {__table_.swap(__u.__table_);} 1488227825Stheraven 1489227825Stheraven _LIBCPP_INLINE_VISIBILITY 1490227825Stheraven hasher hash_function() const 1491227825Stheraven {return __table_.hash_function().hash_function();} 1492227825Stheraven _LIBCPP_INLINE_VISIBILITY 1493227825Stheraven key_equal key_eq() const 1494227825Stheraven {return __table_.key_eq().key_eq();} 1495227825Stheraven 1496227825Stheraven _LIBCPP_INLINE_VISIBILITY 1497227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 1498227825Stheraven _LIBCPP_INLINE_VISIBILITY 1499227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1500227825Stheraven _LIBCPP_INLINE_VISIBILITY 1501227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1502227825Stheraven _LIBCPP_INLINE_VISIBILITY 1503227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 1504227825Stheraven {return __table_.__equal_range_multi(__k);} 1505227825Stheraven _LIBCPP_INLINE_VISIBILITY 1506227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1507227825Stheraven {return __table_.__equal_range_multi(__k);} 1508227825Stheraven 1509227825Stheraven _LIBCPP_INLINE_VISIBILITY 1510227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1511227825Stheraven _LIBCPP_INLINE_VISIBILITY 1512227825Stheraven size_type max_bucket_count() const _NOEXCEPT 1513227825Stheraven {return __table_.max_bucket_count();} 1514227825Stheraven 1515227825Stheraven _LIBCPP_INLINE_VISIBILITY 1516227825Stheraven size_type bucket_size(size_type __n) const 1517227825Stheraven {return __table_.bucket_size(__n);} 1518227825Stheraven _LIBCPP_INLINE_VISIBILITY 1519227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1520227825Stheraven 1521227825Stheraven _LIBCPP_INLINE_VISIBILITY 1522227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1523227825Stheraven _LIBCPP_INLINE_VISIBILITY 1524227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1525227825Stheraven _LIBCPP_INLINE_VISIBILITY 1526227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1527227825Stheraven _LIBCPP_INLINE_VISIBILITY 1528227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1529227825Stheraven _LIBCPP_INLINE_VISIBILITY 1530227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1531227825Stheraven _LIBCPP_INLINE_VISIBILITY 1532227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1533227825Stheraven 1534227825Stheraven _LIBCPP_INLINE_VISIBILITY 1535227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1536227825Stheraven _LIBCPP_INLINE_VISIBILITY 1537227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1538227825Stheraven _LIBCPP_INLINE_VISIBILITY 1539227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1540227825Stheraven _LIBCPP_INLINE_VISIBILITY 1541227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1542227825Stheraven _LIBCPP_INLINE_VISIBILITY 1543227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1544227825Stheraven 1545227825Stheravenprivate: 1546227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1547227825Stheraven template <class _A0, class... _Args, 1548227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 1549227825Stheraven __node_holder __construct_node(_A0&& __a0, _Args&&... __args); 1550227825Stheraven template <class _A0, 1551227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 1552227825Stheraven __node_holder __construct_node(_A0&& __a0); 1553227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1554227825Stheraven}; 1555227825Stheraven 1556227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1557227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1558227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1559227825Stheraven : __table_(__hf, __eql) 1560227825Stheraven{ 1561227825Stheraven __table_.rehash(__n); 1562227825Stheraven} 1563227825Stheraven 1564227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1565227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1566227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1567227825Stheraven const allocator_type& __a) 1568227825Stheraven : __table_(__hf, __eql, __a) 1569227825Stheraven{ 1570227825Stheraven __table_.rehash(__n); 1571227825Stheraven} 1572227825Stheraven 1573227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1574227825Stheraventemplate <class _InputIterator> 1575227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1576227825Stheraven _InputIterator __first, _InputIterator __last) 1577227825Stheraven{ 1578227825Stheraven insert(__first, __last); 1579227825Stheraven} 1580227825Stheraven 1581227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1582227825Stheraventemplate <class _InputIterator> 1583227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1584227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1585227825Stheraven const hasher& __hf, const key_equal& __eql) 1586227825Stheraven : __table_(__hf, __eql) 1587227825Stheraven{ 1588227825Stheraven __table_.rehash(__n); 1589227825Stheraven insert(__first, __last); 1590227825Stheraven} 1591227825Stheraven 1592227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1593227825Stheraventemplate <class _InputIterator> 1594227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1595227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1596227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1597227825Stheraven : __table_(__hf, __eql, __a) 1598227825Stheraven{ 1599227825Stheraven __table_.rehash(__n); 1600227825Stheraven insert(__first, __last); 1601227825Stheraven} 1602227825Stheraven 1603227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1604227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1605227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1606227825Stheraven const allocator_type& __a) 1607227825Stheraven : __table_(__a) 1608227825Stheraven{ 1609227825Stheraven} 1610227825Stheraven 1611227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1612227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1613227825Stheraven const unordered_multimap& __u) 1614227825Stheraven : __table_(__u.__table_) 1615227825Stheraven{ 1616227825Stheraven __table_.rehash(__u.bucket_count()); 1617227825Stheraven insert(__u.begin(), __u.end()); 1618227825Stheraven} 1619227825Stheraven 1620227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1621227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1622227825Stheraven const unordered_multimap& __u, const allocator_type& __a) 1623227825Stheraven : __table_(__u.__table_, __a) 1624227825Stheraven{ 1625227825Stheraven __table_.rehash(__u.bucket_count()); 1626227825Stheraven insert(__u.begin(), __u.end()); 1627227825Stheraven} 1628227825Stheraven 1629227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1630227825Stheraven 1631227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1632227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1633227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1634227825Stheraven unordered_multimap&& __u) 1635227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1636227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1637227825Stheraven{ 1638227825Stheraven} 1639227825Stheraven 1640227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1641227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1642227825Stheraven unordered_multimap&& __u, const allocator_type& __a) 1643227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1644227825Stheraven{ 1645227825Stheraven if (__a != __u.get_allocator()) 1646227825Stheraven { 1647227825Stheraven iterator __i = __u.begin(); 1648227825Stheraven while (__u.size() != 0) 1649227825Stheraven{ 1650227825Stheraven __table_.__insert_multi( 1651227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1652227825Stheraven ); 1653227825Stheraven} 1654227825Stheraven } 1655227825Stheraven} 1656227825Stheraven 1657227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1658227825Stheraven 1659227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1660227825Stheraven 1661227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1662227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1663227825Stheraven initializer_list<value_type> __il) 1664227825Stheraven{ 1665227825Stheraven insert(__il.begin(), __il.end()); 1666227825Stheraven} 1667227825Stheraven 1668227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1669227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1670227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1671227825Stheraven const key_equal& __eql) 1672227825Stheraven : __table_(__hf, __eql) 1673227825Stheraven{ 1674227825Stheraven __table_.rehash(__n); 1675227825Stheraven insert(__il.begin(), __il.end()); 1676227825Stheraven} 1677227825Stheraven 1678227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1679227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1680227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1681227825Stheraven const key_equal& __eql, const allocator_type& __a) 1682227825Stheraven : __table_(__hf, __eql, __a) 1683227825Stheraven{ 1684227825Stheraven __table_.rehash(__n); 1685227825Stheraven insert(__il.begin(), __il.end()); 1686227825Stheraven} 1687227825Stheraven 1688227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1689227825Stheraven 1690227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1691227825Stheraven 1692227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1693227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1694227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1695227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1696227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1697227825Stheraven{ 1698227825Stheraven __table_ = _VSTD::move(__u.__table_); 1699227825Stheraven return *this; 1700227825Stheraven} 1701227825Stheraven 1702227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1703227825Stheraven 1704227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1705227825Stheraven 1706227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1707227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1708227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1709227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1710227825Stheraven initializer_list<value_type> __il) 1711227825Stheraven{ 1712227825Stheraven __table_.__assign_multi(__il.begin(), __il.end()); 1713227825Stheraven return *this; 1714227825Stheraven} 1715227825Stheraven 1716227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1717227825Stheraven 1718227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1719227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1720227825Stheraven 1721227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1722227825Stheraventemplate <class _A0, class... _Args, 1723227825Stheraven class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1724227825Stheraven > 1725227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1726227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 1727227825Stheraven _A0&& __a0, _Args&&... __args) 1728227825Stheraven{ 1729227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1730232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1731227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), 1732227825Stheraven _VSTD::forward<_A0>(__a0)); 1733227825Stheraven __h.get_deleter().__first_constructed = true; 1734227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second), 1735227825Stheraven _VSTD::forward<_Args>(__args)...); 1736227825Stheraven __h.get_deleter().__second_constructed = true; 1737227825Stheraven return __h; 1738227825Stheraven} 1739227825Stheraven 1740227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1741227825Stheraven 1742227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1743227825Stheraventemplate <class _A0, 1744227825Stheraven class // = typename enable_if<is_constructible<value_type, _A0>::value>::type 1745227825Stheraven > 1746227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1747227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1748227825Stheraven{ 1749227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1750232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1751227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1752227825Stheraven _VSTD::forward<_A0>(__a0)); 1753227825Stheraven __h.get_deleter().__first_constructed = true; 1754227825Stheraven __h.get_deleter().__second_constructed = true; 1755227825Stheraven return __h; 1756227825Stheraven} 1757227825Stheraven 1758227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1759227825Stheraven 1760227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1761227825Stheraventemplate <class _A0, class... _Args, 1762227825Stheraven class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1763227825Stheraven > 1764227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1765227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args) 1766227825Stheraven{ 1767227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0), 1768227825Stheraven _VSTD::forward<_Args>(__args)...); 1769227825Stheraven iterator __r = __table_.__node_insert_multi(__h.get()); 1770227825Stheraven __h.release(); 1771227825Stheraven return __r; 1772227825Stheraven} 1773227825Stheraven 1774227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1775227825Stheraventemplate <class _A0, class... _Args, 1776227825Stheraven class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1777227825Stheraven > 1778227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1779227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 1780227825Stheraven const_iterator __p, _A0&& __a0, _Args&&... __args) 1781227825Stheraven{ 1782227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0), 1783227825Stheraven _VSTD::forward<_Args>(__args)...); 1784227825Stheraven iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 1785227825Stheraven __h.release(); 1786227825Stheraven return __r; 1787227825Stheraven} 1788227825Stheraven 1789227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1790227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1791227825Stheraven 1792227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1793227825Stheraventemplate <class _InputIterator> 1794227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1795227825Stheravenvoid 1796227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1797227825Stheraven _InputIterator __last) 1798227825Stheraven{ 1799227825Stheraven for (; __first != __last; ++__first) 1800227825Stheraven __table_.__insert_multi(*__first); 1801227825Stheraven} 1802227825Stheraven 1803227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1804227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1805227825Stheravenvoid 1806227825Stheravenswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1807227825Stheraven unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1808227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1809227825Stheraven{ 1810227825Stheraven __x.swap(__y); 1811227825Stheraven} 1812227825Stheraven 1813227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1814227825Stheravenbool 1815227825Stheravenoperator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1816227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1817227825Stheraven{ 1818227825Stheraven if (__x.size() != __y.size()) 1819227825Stheraven return false; 1820227825Stheraven typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1821227825Stheraven const_iterator; 1822227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 1823227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1824227825Stheraven { 1825227825Stheraven _EqRng __xeq = __x.equal_range(__i->first); 1826227825Stheraven _EqRng __yeq = __y.equal_range(__i->first); 1827227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 1828227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 1829227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1830227825Stheraven return false; 1831227825Stheraven __i = __xeq.second; 1832227825Stheraven } 1833227825Stheraven return true; 1834227825Stheraven} 1835227825Stheraven 1836227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1837227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1838227825Stheravenbool 1839227825Stheravenoperator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1840227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1841227825Stheraven{ 1842227825Stheraven return !(__x == __y); 1843227825Stheraven} 1844227825Stheraven 1845227825Stheraven_LIBCPP_END_NAMESPACE_STD 1846227825Stheraven 1847227825Stheraven#endif // _LIBCPP_UNORDERED_MAP 1848