unordered_map revision 227825
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 328227825Stheraventemplate <class _Tp, class _Hash, bool = is_empty<_Hash>::value> 329227825Stheravenclass __unordered_map_hasher 330227825Stheraven : private _Hash 331227825Stheraven{ 332227825Stheravenpublic: 333227825Stheraven _LIBCPP_INLINE_VISIBILITY 334227825Stheraven __unordered_map_hasher() 335227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 336227825Stheraven : _Hash() {} 337227825Stheraven _LIBCPP_INLINE_VISIBILITY 338227825Stheraven __unordered_map_hasher(const _Hash& __h) 339227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 340227825Stheraven : _Hash(__h) {} 341227825Stheraven _LIBCPP_INLINE_VISIBILITY 342227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return *this;} 343227825Stheraven _LIBCPP_INLINE_VISIBILITY 344227825Stheraven size_t operator()(const _Tp& __x) const 345227825Stheraven {return static_cast<const _Hash&>(*this)(__x.first);} 346227825Stheraven _LIBCPP_INLINE_VISIBILITY 347227825Stheraven size_t operator()(const typename _Tp::first_type& __x) const 348227825Stheraven {return static_cast<const _Hash&>(*this)(__x);} 349227825Stheraven}; 350227825Stheraven 351227825Stheraventemplate <class _Tp, class _Hash> 352227825Stheravenclass __unordered_map_hasher<_Tp, _Hash, false> 353227825Stheraven{ 354227825Stheraven _Hash __hash_; 355227825Stheravenpublic: 356227825Stheraven _LIBCPP_INLINE_VISIBILITY 357227825Stheraven __unordered_map_hasher() 358227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 359227825Stheraven : __hash_() {} 360227825Stheraven _LIBCPP_INLINE_VISIBILITY 361227825Stheraven __unordered_map_hasher(const _Hash& __h) 362227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 363227825Stheraven : __hash_(__h) {} 364227825Stheraven _LIBCPP_INLINE_VISIBILITY 365227825Stheraven const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 366227825Stheraven _LIBCPP_INLINE_VISIBILITY 367227825Stheraven size_t operator()(const _Tp& __x) const 368227825Stheraven {return __hash_(__x.first);} 369227825Stheraven _LIBCPP_INLINE_VISIBILITY 370227825Stheraven size_t operator()(const typename _Tp::first_type& __x) const 371227825Stheraven {return __hash_(__x);} 372227825Stheraven}; 373227825Stheraven 374227825Stheraventemplate <class _Tp, class _Pred, bool = is_empty<_Pred>::value> 375227825Stheravenclass __unordered_map_equal 376227825Stheraven : private _Pred 377227825Stheraven{ 378227825Stheravenpublic: 379227825Stheraven _LIBCPP_INLINE_VISIBILITY 380227825Stheraven __unordered_map_equal() 381227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 382227825Stheraven : _Pred() {} 383227825Stheraven _LIBCPP_INLINE_VISIBILITY 384227825Stheraven __unordered_map_equal(const _Pred& __p) 385227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 386227825Stheraven : _Pred(__p) {} 387227825Stheraven _LIBCPP_INLINE_VISIBILITY 388227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return *this;} 389227825Stheraven _LIBCPP_INLINE_VISIBILITY 390227825Stheraven bool operator()(const _Tp& __x, const _Tp& __y) const 391227825Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 392227825Stheraven _LIBCPP_INLINE_VISIBILITY 393227825Stheraven bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 394227825Stheraven {return static_cast<const _Pred&>(*this)(__x, __y.first);} 395227825Stheraven _LIBCPP_INLINE_VISIBILITY 396227825Stheraven bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 397227825Stheraven {return static_cast<const _Pred&>(*this)(__x.first, __y);} 398227825Stheraven _LIBCPP_INLINE_VISIBILITY 399227825Stheraven bool operator()(const typename _Tp::first_type& __x, 400227825Stheraven const typename _Tp::first_type& __y) const 401227825Stheraven {return static_cast<const _Pred&>(*this)(__x, __y);} 402227825Stheraven}; 403227825Stheraven 404227825Stheraventemplate <class _Tp, class _Pred> 405227825Stheravenclass __unordered_map_equal<_Tp, _Pred, false> 406227825Stheraven{ 407227825Stheraven _Pred __pred_; 408227825Stheravenpublic: 409227825Stheraven _LIBCPP_INLINE_VISIBILITY 410227825Stheraven __unordered_map_equal() 411227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 412227825Stheraven : __pred_() {} 413227825Stheraven _LIBCPP_INLINE_VISIBILITY 414227825Stheraven __unordered_map_equal(const _Pred& __p) 415227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 416227825Stheraven : __pred_(__p) {} 417227825Stheraven _LIBCPP_INLINE_VISIBILITY 418227825Stheraven const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 419227825Stheraven _LIBCPP_INLINE_VISIBILITY 420227825Stheraven bool operator()(const _Tp& __x, const _Tp& __y) const 421227825Stheraven {return __pred_(__x.first, __y.first);} 422227825Stheraven _LIBCPP_INLINE_VISIBILITY 423227825Stheraven bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 424227825Stheraven {return __pred_(__x, __y.first);} 425227825Stheraven _LIBCPP_INLINE_VISIBILITY 426227825Stheraven bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 427227825Stheraven {return __pred_(__x.first, __y);} 428227825Stheraven _LIBCPP_INLINE_VISIBILITY 429227825Stheraven bool operator()(const typename _Tp::first_type& __x, 430227825Stheraven const typename _Tp::first_type& __y) const 431227825Stheraven {return __pred_(__x, __y);} 432227825Stheraven}; 433227825Stheraven 434227825Stheraventemplate <class _Alloc> 435227825Stheravenclass __hash_map_node_destructor 436227825Stheraven{ 437227825Stheraven typedef _Alloc allocator_type; 438227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 439227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 440227825Stheravenpublic: 441227825Stheraven typedef typename __alloc_traits::pointer pointer; 442227825Stheravenprivate: 443227825Stheraven typedef typename value_type::first_type first_type; 444227825Stheraven typedef typename value_type::second_type second_type; 445227825Stheraven 446227825Stheraven allocator_type& __na_; 447227825Stheraven 448227825Stheraven __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 449227825Stheraven 450227825Stheravenpublic: 451227825Stheraven bool __first_constructed; 452227825Stheraven bool __second_constructed; 453227825Stheraven 454227825Stheraven _LIBCPP_INLINE_VISIBILITY 455227825Stheraven explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 456227825Stheraven : __na_(__na), 457227825Stheraven __first_constructed(false), 458227825Stheraven __second_constructed(false) 459227825Stheraven {} 460227825Stheraven 461227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 462227825Stheraven _LIBCPP_INLINE_VISIBILITY 463227825Stheraven __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 464227825Stheraven _NOEXCEPT 465227825Stheraven : __na_(__x.__na_), 466227825Stheraven __first_constructed(__x.__value_constructed), 467227825Stheraven __second_constructed(__x.__value_constructed) 468227825Stheraven { 469227825Stheraven __x.__value_constructed = false; 470227825Stheraven } 471227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 472227825Stheraven _LIBCPP_INLINE_VISIBILITY 473227825Stheraven __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 474227825Stheraven : __na_(__x.__na_), 475227825Stheraven __first_constructed(__x.__value_constructed), 476227825Stheraven __second_constructed(__x.__value_constructed) 477227825Stheraven { 478227825Stheraven const_cast<bool&>(__x.__value_constructed) = false; 479227825Stheraven } 480227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 481227825Stheraven 482227825Stheraven _LIBCPP_INLINE_VISIBILITY 483227825Stheraven void operator()(pointer __p) _NOEXCEPT 484227825Stheraven { 485227825Stheraven if (__second_constructed) 486227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second)); 487227825Stheraven if (__first_constructed) 488227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); 489227825Stheraven if (__p) 490227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 491227825Stheraven } 492227825Stheraven}; 493227825Stheraven 494227825Stheraventemplate <class _HashIterator> 495227825Stheravenclass _LIBCPP_VISIBLE __hash_map_iterator 496227825Stheraven{ 497227825Stheraven _HashIterator __i_; 498227825Stheraven 499227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 500227825Stheraven typedef const typename _HashIterator::value_type::first_type key_type; 501227825Stheraven typedef typename _HashIterator::value_type::second_type mapped_type; 502227825Stheravenpublic: 503227825Stheraven typedef forward_iterator_tag iterator_category; 504227825Stheraven typedef pair<key_type, mapped_type> value_type; 505227825Stheraven typedef typename _HashIterator::difference_type difference_type; 506227825Stheraven typedef value_type& reference; 507227825Stheraven typedef typename __pointer_traits::template 508227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 509227825Stheraven rebind<value_type> 510227825Stheraven#else 511227825Stheraven rebind<value_type>::other 512227825Stheraven#endif 513227825Stheraven pointer; 514227825Stheraven 515227825Stheraven _LIBCPP_INLINE_VISIBILITY 516227825Stheraven __hash_map_iterator() _NOEXCEPT {} 517227825Stheraven 518227825Stheraven _LIBCPP_INLINE_VISIBILITY 519227825Stheraven __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 520227825Stheraven 521227825Stheraven _LIBCPP_INLINE_VISIBILITY 522227825Stheraven reference operator*() const {return *operator->();} 523227825Stheraven _LIBCPP_INLINE_VISIBILITY 524227825Stheraven pointer operator->() const {return (pointer)__i_.operator->();} 525227825Stheraven 526227825Stheraven _LIBCPP_INLINE_VISIBILITY 527227825Stheraven __hash_map_iterator& operator++() {++__i_; return *this;} 528227825Stheraven _LIBCPP_INLINE_VISIBILITY 529227825Stheraven __hash_map_iterator operator++(int) 530227825Stheraven { 531227825Stheraven __hash_map_iterator __t(*this); 532227825Stheraven ++(*this); 533227825Stheraven return __t; 534227825Stheraven } 535227825Stheraven 536227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 537227825Stheraven bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 538227825Stheraven {return __x.__i_ == __y.__i_;} 539227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 540227825Stheraven bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 541227825Stheraven {return __x.__i_ != __y.__i_;} 542227825Stheraven 543227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; 544227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; 545227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator; 546227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator; 547227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator; 548227825Stheraven}; 549227825Stheraven 550227825Stheraventemplate <class _HashIterator> 551227825Stheravenclass _LIBCPP_VISIBLE __hash_map_const_iterator 552227825Stheraven{ 553227825Stheraven _HashIterator __i_; 554227825Stheraven 555227825Stheraven typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 556227825Stheraven typedef const typename _HashIterator::value_type::first_type key_type; 557227825Stheraven typedef typename _HashIterator::value_type::second_type mapped_type; 558227825Stheravenpublic: 559227825Stheraven typedef forward_iterator_tag iterator_category; 560227825Stheraven typedef pair<key_type, mapped_type> value_type; 561227825Stheraven typedef typename _HashIterator::difference_type difference_type; 562227825Stheraven typedef const value_type& reference; 563227825Stheraven typedef typename __pointer_traits::template 564227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 565227825Stheraven rebind<const value_type> 566227825Stheraven#else 567227825Stheraven rebind<const value_type>::other 568227825Stheraven#endif 569227825Stheraven pointer; 570227825Stheraven 571227825Stheraven _LIBCPP_INLINE_VISIBILITY 572227825Stheraven __hash_map_const_iterator() _NOEXCEPT {} 573227825Stheraven 574227825Stheraven _LIBCPP_INLINE_VISIBILITY 575227825Stheraven __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 576227825Stheraven _LIBCPP_INLINE_VISIBILITY 577227825Stheraven __hash_map_const_iterator( 578227825Stheraven __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 579227825Stheraven _NOEXCEPT 580227825Stheraven : __i_(__i.__i_) {} 581227825Stheraven 582227825Stheraven _LIBCPP_INLINE_VISIBILITY 583227825Stheraven reference operator*() const {return *operator->();} 584227825Stheraven _LIBCPP_INLINE_VISIBILITY 585227825Stheraven pointer operator->() const {return (pointer)__i_.operator->();} 586227825Stheraven 587227825Stheraven _LIBCPP_INLINE_VISIBILITY 588227825Stheraven __hash_map_const_iterator& operator++() {++__i_; return *this;} 589227825Stheraven _LIBCPP_INLINE_VISIBILITY 590227825Stheraven __hash_map_const_iterator operator++(int) 591227825Stheraven { 592227825Stheraven __hash_map_const_iterator __t(*this); 593227825Stheraven ++(*this); 594227825Stheraven return __t; 595227825Stheraven } 596227825Stheraven 597227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 598227825Stheraven bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 599227825Stheraven {return __x.__i_ == __y.__i_;} 600227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 601227825Stheraven bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 602227825Stheraven {return __x.__i_ != __y.__i_;} 603227825Stheraven 604227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; 605227825Stheraven template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; 606227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator; 607227825Stheraven template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator; 608227825Stheraven}; 609227825Stheraven 610227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 611227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 612227825Stheravenclass _LIBCPP_VISIBLE unordered_map 613227825Stheraven{ 614227825Stheravenpublic: 615227825Stheraven // types 616227825Stheraven typedef _Key key_type; 617227825Stheraven typedef _Tp mapped_type; 618227825Stheraven typedef _Hash hasher; 619227825Stheraven typedef _Pred key_equal; 620227825Stheraven typedef _Alloc allocator_type; 621227825Stheraven typedef pair<const key_type, mapped_type> value_type; 622227825Stheraven typedef value_type& reference; 623227825Stheraven typedef const value_type& const_reference; 624227825Stheraven 625227825Stheravenprivate: 626227825Stheraven typedef pair<key_type, mapped_type> __value_type; 627227825Stheraven typedef __unordered_map_hasher<__value_type, hasher> __hasher; 628227825Stheraven typedef __unordered_map_equal<__value_type, key_equal> __key_equal; 629227825Stheraven typedef typename allocator_traits<allocator_type>::template 630227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 631227825Stheraven rebind_alloc<__value_type> 632227825Stheraven#else 633227825Stheraven rebind_alloc<__value_type>::other 634227825Stheraven#endif 635227825Stheraven __allocator_type; 636227825Stheraven 637227825Stheraven typedef __hash_table<__value_type, __hasher, 638227825Stheraven __key_equal, __allocator_type> __table; 639227825Stheraven 640227825Stheraven __table __table_; 641227825Stheraven 642227825Stheraven typedef typename __table::__node_pointer __node_pointer; 643227825Stheraven typedef typename __table::__node_const_pointer __node_const_pointer; 644227825Stheraven typedef typename __table::__node_traits __node_traits; 645227825Stheraven typedef typename __table::__node_allocator __node_allocator; 646227825Stheraven typedef typename __table::__node __node; 647227825Stheraven typedef __hash_map_node_destructor<__node_allocator> _D; 648227825Stheraven typedef unique_ptr<__node, _D> __node_holder; 649227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 650227825Stheravenpublic: 651227825Stheraven typedef typename __alloc_traits::pointer pointer; 652227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 653227825Stheraven typedef typename __alloc_traits::size_type size_type; 654227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 655227825Stheraven 656227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 657227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 658227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 659227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 660227825Stheraven 661227825Stheraven _LIBCPP_INLINE_VISIBILITY 662227825Stheraven unordered_map() 663227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 664227825Stheraven {} // = default; 665227825Stheraven explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 666227825Stheraven const key_equal& __eql = key_equal()); 667227825Stheraven unordered_map(size_type __n, const hasher& __hf, 668227825Stheraven const key_equal& __eql, 669227825Stheraven const allocator_type& __a); 670227825Stheraven template <class _InputIterator> 671227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last); 672227825Stheraven template <class _InputIterator> 673227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 674227825Stheraven size_type __n, const hasher& __hf = hasher(), 675227825Stheraven const key_equal& __eql = key_equal()); 676227825Stheraven template <class _InputIterator> 677227825Stheraven unordered_map(_InputIterator __first, _InputIterator __last, 678227825Stheraven size_type __n, const hasher& __hf, 679227825Stheraven const key_equal& __eql, 680227825Stheraven const allocator_type& __a); 681227825Stheraven explicit unordered_map(const allocator_type& __a); 682227825Stheraven unordered_map(const unordered_map& __u); 683227825Stheraven unordered_map(const unordered_map& __u, const allocator_type& __a); 684227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 685227825Stheraven unordered_map(unordered_map&& __u) 686227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 687227825Stheraven unordered_map(unordered_map&& __u, const allocator_type& __a); 688227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 689227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 690227825Stheraven unordered_map(initializer_list<value_type> __il); 691227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 692227825Stheraven const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 693227825Stheraven unordered_map(initializer_list<value_type> __il, size_type __n, 694227825Stheraven const hasher& __hf, const key_equal& __eql, 695227825Stheraven const allocator_type& __a); 696227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 697227825Stheraven // ~unordered_map() = default; 698227825Stheraven _LIBCPP_INLINE_VISIBILITY 699227825Stheraven unordered_map& operator=(const unordered_map& __u) 700227825Stheraven { 701227825Stheraven __table_ = __u.__table_; 702227825Stheraven return *this; 703227825Stheraven } 704227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 705227825Stheraven unordered_map& operator=(unordered_map&& __u) 706227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 707227825Stheraven#endif 708227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 709227825Stheraven unordered_map& operator=(initializer_list<value_type> __il); 710227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 711227825Stheraven 712227825Stheraven _LIBCPP_INLINE_VISIBILITY 713227825Stheraven allocator_type get_allocator() const _NOEXCEPT 714227825Stheraven {return allocator_type(__table_.__node_alloc());} 715227825Stheraven 716227825Stheraven _LIBCPP_INLINE_VISIBILITY 717227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 718227825Stheraven _LIBCPP_INLINE_VISIBILITY 719227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 720227825Stheraven _LIBCPP_INLINE_VISIBILITY 721227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 722227825Stheraven 723227825Stheraven _LIBCPP_INLINE_VISIBILITY 724227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 725227825Stheraven _LIBCPP_INLINE_VISIBILITY 726227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 727227825Stheraven _LIBCPP_INLINE_VISIBILITY 728227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 729227825Stheraven _LIBCPP_INLINE_VISIBILITY 730227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 731227825Stheraven _LIBCPP_INLINE_VISIBILITY 732227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 733227825Stheraven _LIBCPP_INLINE_VISIBILITY 734227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 735227825Stheraven 736227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 737227825Stheraven _LIBCPP_INLINE_VISIBILITY 738227825Stheraven pair<iterator, bool> emplace() 739227825Stheraven {return __table_.__emplace_unique();} 740227825Stheraven 741227825Stheraven template <class _A0, 742227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 743227825Stheraven _LIBCPP_INLINE_VISIBILITY 744227825Stheraven pair<iterator, bool> emplace(_A0&& __a0) 745227825Stheraven {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0));} 746227825Stheraven 747227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 748227825Stheraven 749227825Stheraven template <class _A0, class... _Args, 750227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 751227825Stheraven pair<iterator, bool> emplace(_A0&& __a0, _Args&&... __args); 752227825Stheraven 753227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 754227825Stheraven 755227825Stheraven _LIBCPP_INLINE_VISIBILITY 756227825Stheraven iterator emplace_hint(const_iterator) 757227825Stheraven {return __table_.__emplace_unique().first;} 758227825Stheraven 759227825Stheraven template <class _A0, 760227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 761227825Stheraven _LIBCPP_INLINE_VISIBILITY 762227825Stheraven iterator emplace_hint(const_iterator, _A0&& __a0) 763227825Stheraven {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0)).first;} 764227825Stheraven 765227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 766227825Stheraven 767227825Stheraven template <class _A0, class... _Args, 768227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 769227825Stheraven _LIBCPP_INLINE_VISIBILITY 770227825Stheraven iterator emplace_hint(const_iterator, _A0&& __a0, _Args&&... __args) 771227825Stheraven {return emplace(_VSTD::forward<_A0>(__a0), 772227825Stheraven _VSTD::forward<_Args>(__args)...).first;} 773227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 774227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 775227825Stheraven _LIBCPP_INLINE_VISIBILITY 776227825Stheraven pair<iterator, bool> insert(const value_type& __x) 777227825Stheraven {return __table_.__insert_unique(__x);} 778227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 779227825Stheraven template <class _P, 780227825Stheraven class = typename enable_if<is_constructible<value_type, _P>::value>::type> 781227825Stheraven _LIBCPP_INLINE_VISIBILITY 782227825Stheraven pair<iterator, bool> insert(_P&& __x) 783227825Stheraven {return __table_.__insert_unique(_VSTD::forward<_P>(__x));} 784227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 785227825Stheraven _LIBCPP_INLINE_VISIBILITY 786227825Stheraven iterator insert(const_iterator, const value_type& __x) 787227825Stheraven {return insert(__x).first;} 788227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 789227825Stheraven template <class _P, 790227825Stheraven class = typename enable_if<is_constructible<value_type, _P>::value>::type> 791227825Stheraven _LIBCPP_INLINE_VISIBILITY 792227825Stheraven iterator insert(const_iterator, _P&& __x) 793227825Stheraven {return insert(_VSTD::forward<_P>(__x)).first;} 794227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 795227825Stheraven template <class _InputIterator> 796227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 797227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 798227825Stheraven _LIBCPP_INLINE_VISIBILITY 799227825Stheraven void insert(initializer_list<value_type> __il) 800227825Stheraven {insert(__il.begin(), __il.end());} 801227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 802227825Stheraven 803227825Stheraven _LIBCPP_INLINE_VISIBILITY 804227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 805227825Stheraven _LIBCPP_INLINE_VISIBILITY 806227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 807227825Stheraven _LIBCPP_INLINE_VISIBILITY 808227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 809227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 810227825Stheraven _LIBCPP_INLINE_VISIBILITY 811227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 812227825Stheraven 813227825Stheraven _LIBCPP_INLINE_VISIBILITY 814227825Stheraven void swap(unordered_map& __u) 815227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 816227825Stheraven {__table_.swap(__u.__table_);} 817227825Stheraven 818227825Stheraven _LIBCPP_INLINE_VISIBILITY 819227825Stheraven hasher hash_function() const 820227825Stheraven {return __table_.hash_function().hash_function();} 821227825Stheraven _LIBCPP_INLINE_VISIBILITY 822227825Stheraven key_equal key_eq() const 823227825Stheraven {return __table_.key_eq().key_eq();} 824227825Stheraven 825227825Stheraven _LIBCPP_INLINE_VISIBILITY 826227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 827227825Stheraven _LIBCPP_INLINE_VISIBILITY 828227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 829227825Stheraven _LIBCPP_INLINE_VISIBILITY 830227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 831227825Stheraven _LIBCPP_INLINE_VISIBILITY 832227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 833227825Stheraven {return __table_.__equal_range_unique(__k);} 834227825Stheraven _LIBCPP_INLINE_VISIBILITY 835227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 836227825Stheraven {return __table_.__equal_range_unique(__k);} 837227825Stheraven 838227825Stheraven mapped_type& operator[](const key_type& __k); 839227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 840227825Stheraven mapped_type& operator[](key_type&& __k); 841227825Stheraven#endif 842227825Stheraven 843227825Stheraven mapped_type& at(const key_type& __k); 844227825Stheraven const mapped_type& at(const key_type& __k) const; 845227825Stheraven 846227825Stheraven _LIBCPP_INLINE_VISIBILITY 847227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 848227825Stheraven _LIBCPP_INLINE_VISIBILITY 849227825Stheraven size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 850227825Stheraven 851227825Stheraven _LIBCPP_INLINE_VISIBILITY 852227825Stheraven size_type bucket_size(size_type __n) const 853227825Stheraven {return __table_.bucket_size(__n);} 854227825Stheraven _LIBCPP_INLINE_VISIBILITY 855227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 856227825Stheraven 857227825Stheraven _LIBCPP_INLINE_VISIBILITY 858227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 859227825Stheraven _LIBCPP_INLINE_VISIBILITY 860227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 861227825Stheraven _LIBCPP_INLINE_VISIBILITY 862227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 863227825Stheraven _LIBCPP_INLINE_VISIBILITY 864227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 865227825Stheraven _LIBCPP_INLINE_VISIBILITY 866227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 867227825Stheraven _LIBCPP_INLINE_VISIBILITY 868227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 869227825Stheraven 870227825Stheraven _LIBCPP_INLINE_VISIBILITY 871227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 872227825Stheraven _LIBCPP_INLINE_VISIBILITY 873227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 874227825Stheraven _LIBCPP_INLINE_VISIBILITY 875227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 876227825Stheraven _LIBCPP_INLINE_VISIBILITY 877227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 878227825Stheraven _LIBCPP_INLINE_VISIBILITY 879227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 880227825Stheraven 881227825Stheravenprivate: 882227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 883227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 884227825Stheraven template <class _A0, class... _Args, 885227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 886227825Stheraven __node_holder __construct_node(_A0&& __a0, _Args&&... __args); 887227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 888227825Stheraven template <class _A0, 889227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 890227825Stheraven __node_holder __construct_node(_A0&& __a0); 891227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 892227825Stheraven __node_holder __construct_node(const key_type& __k); 893227825Stheraven#endif 894227825Stheraven}; 895227825Stheraven 896227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 897227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 898227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 899227825Stheraven : __table_(__hf, __eql) 900227825Stheraven{ 901227825Stheraven __table_.rehash(__n); 902227825Stheraven} 903227825Stheraven 904227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 905227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 906227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 907227825Stheraven const allocator_type& __a) 908227825Stheraven : __table_(__hf, __eql, __a) 909227825Stheraven{ 910227825Stheraven __table_.rehash(__n); 911227825Stheraven} 912227825Stheraven 913227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 914227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 915227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 916227825Stheraven const allocator_type& __a) 917227825Stheraven : __table_(__a) 918227825Stheraven{ 919227825Stheraven} 920227825Stheraven 921227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 922227825Stheraventemplate <class _InputIterator> 923227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 924227825Stheraven _InputIterator __first, _InputIterator __last) 925227825Stheraven{ 926227825Stheraven insert(__first, __last); 927227825Stheraven} 928227825Stheraven 929227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 930227825Stheraventemplate <class _InputIterator> 931227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 932227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 933227825Stheraven const hasher& __hf, const key_equal& __eql) 934227825Stheraven : __table_(__hf, __eql) 935227825Stheraven{ 936227825Stheraven __table_.rehash(__n); 937227825Stheraven insert(__first, __last); 938227825Stheraven} 939227825Stheraven 940227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 941227825Stheraventemplate <class _InputIterator> 942227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 943227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 944227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 945227825Stheraven : __table_(__hf, __eql, __a) 946227825Stheraven{ 947227825Stheraven __table_.rehash(__n); 948227825Stheraven insert(__first, __last); 949227825Stheraven} 950227825Stheraven 951227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 952227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 953227825Stheraven const unordered_map& __u) 954227825Stheraven : __table_(__u.__table_) 955227825Stheraven{ 956227825Stheraven __table_.rehash(__u.bucket_count()); 957227825Stheraven insert(__u.begin(), __u.end()); 958227825Stheraven} 959227825Stheraven 960227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 961227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 962227825Stheraven const unordered_map& __u, const allocator_type& __a) 963227825Stheraven : __table_(__u.__table_, __a) 964227825Stheraven{ 965227825Stheraven __table_.rehash(__u.bucket_count()); 966227825Stheraven insert(__u.begin(), __u.end()); 967227825Stheraven} 968227825Stheraven 969227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 970227825Stheraven 971227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 972227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 973227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 974227825Stheraven unordered_map&& __u) 975227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 976227825Stheraven : __table_(_VSTD::move(__u.__table_)) 977227825Stheraven{ 978227825Stheraven} 979227825Stheraven 980227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 981227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 982227825Stheraven unordered_map&& __u, const allocator_type& __a) 983227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 984227825Stheraven{ 985227825Stheraven if (__a != __u.get_allocator()) 986227825Stheraven { 987227825Stheraven iterator __i = __u.begin(); 988227825Stheraven while (__u.size() != 0) 989227825Stheraven __table_.__insert_unique( 990227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 991227825Stheraven ); 992227825Stheraven } 993227825Stheraven} 994227825Stheraven 995227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 996227825Stheraven 997227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 998227825Stheraven 999227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1000227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1001227825Stheraven initializer_list<value_type> __il) 1002227825Stheraven{ 1003227825Stheraven insert(__il.begin(), __il.end()); 1004227825Stheraven} 1005227825Stheraven 1006227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1007227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1008227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1009227825Stheraven const key_equal& __eql) 1010227825Stheraven : __table_(__hf, __eql) 1011227825Stheraven{ 1012227825Stheraven __table_.rehash(__n); 1013227825Stheraven insert(__il.begin(), __il.end()); 1014227825Stheraven} 1015227825Stheraven 1016227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1017227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1018227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1019227825Stheraven const key_equal& __eql, const allocator_type& __a) 1020227825Stheraven : __table_(__hf, __eql, __a) 1021227825Stheraven{ 1022227825Stheraven __table_.rehash(__n); 1023227825Stheraven insert(__il.begin(), __il.end()); 1024227825Stheraven} 1025227825Stheraven 1026227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1027227825Stheraven 1028227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1029227825Stheraven 1030227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1031227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1032227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1033227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1034227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1035227825Stheraven{ 1036227825Stheraven __table_ = _VSTD::move(__u.__table_); 1037227825Stheraven return *this; 1038227825Stheraven} 1039227825Stheraven 1040227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1041227825Stheraven 1042227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1043227825Stheraven 1044227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1045227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1046227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1047227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1048227825Stheraven initializer_list<value_type> __il) 1049227825Stheraven{ 1050227825Stheraven __table_.__assign_unique(__il.begin(), __il.end()); 1051227825Stheraven return *this; 1052227825Stheraven} 1053227825Stheraven 1054227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1055227825Stheraven 1056227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1057227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1058227825Stheraven 1059227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1060227825Stheraventemplate <class _A0, class... _Args, 1061227825Stheraven class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1062227825Stheraven > 1063227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1064227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1065227825Stheraven _Args&&... __args) 1066227825Stheraven{ 1067227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1068227825Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _D(__na)); 1069227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), 1070227825Stheraven _VSTD::forward<_A0>(__a0)); 1071227825Stheraven __h.get_deleter().__first_constructed = true; 1072227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second), 1073227825Stheraven _VSTD::forward<_Args>(__args)...); 1074227825Stheraven __h.get_deleter().__second_constructed = true; 1075227825Stheraven return __h; 1076227825Stheraven} 1077227825Stheraven 1078227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1079227825Stheraven 1080227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1081227825Stheraventemplate <class _A0, 1082227825Stheraven class // = typename enable_if<is_constructible<value_type, _A0>::value>::type 1083227825Stheraven > 1084227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1085227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1086227825Stheraven{ 1087227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1088227825Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _D(__na)); 1089227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1090227825Stheraven _VSTD::forward<_A0>(__a0)); 1091227825Stheraven __h.get_deleter().__first_constructed = true; 1092227825Stheraven __h.get_deleter().__second_constructed = true; 1093227825Stheraven return __h; 1094227825Stheraven} 1095227825Stheraven 1096227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1097227825Stheraven 1098227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1099227825Stheraventemplate <class _A0, class... _Args, 1100227825Stheraven class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1101227825Stheraven > 1102227825Stheravenpair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1103227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args) 1104227825Stheraven{ 1105227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0), 1106227825Stheraven _VSTD::forward<_Args>(__args)...); 1107227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1108227825Stheraven if (__r.second) 1109227825Stheraven __h.release(); 1110227825Stheraven return __r; 1111227825Stheraven} 1112227825Stheraven 1113227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1114227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1115227825Stheraven 1116227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1117227825Stheraventypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1118227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) 1119227825Stheraven{ 1120227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1121227825Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _D(__na)); 1122227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); 1123227825Stheraven __h.get_deleter().__first_constructed = true; 1124227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 1125227825Stheraven __h.get_deleter().__second_constructed = true; 1126227825Stheraven return _VSTD::move(__h); 1127227825Stheraven} 1128227825Stheraven 1129227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1130227825Stheraven 1131227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1132227825Stheraventemplate <class _InputIterator> 1133227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1134227825Stheravenvoid 1135227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1136227825Stheraven _InputIterator __last) 1137227825Stheraven{ 1138227825Stheraven for (; __first != __last; ++__first) 1139227825Stheraven __table_.__insert_unique(*__first); 1140227825Stheraven} 1141227825Stheraven 1142227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1143227825Stheraven_Tp& 1144227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1145227825Stheraven{ 1146227825Stheraven iterator __i = find(__k); 1147227825Stheraven if (__i != end()) 1148227825Stheraven return __i->second; 1149227825Stheraven __node_holder __h = __construct_node(__k); 1150227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1151227825Stheraven __h.release(); 1152227825Stheraven return __r.first->second; 1153227825Stheraven} 1154227825Stheraven 1155227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1156227825Stheraven 1157227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1158227825Stheraven_Tp& 1159227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1160227825Stheraven{ 1161227825Stheraven iterator __i = find(__k); 1162227825Stheraven if (__i != end()) 1163227825Stheraven return __i->second; 1164227825Stheraven __node_holder __h = __construct_node(_VSTD::move(__k)); 1165227825Stheraven pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1166227825Stheraven __h.release(); 1167227825Stheraven return __r.first->second; 1168227825Stheraven} 1169227825Stheraven 1170227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1171227825Stheraven 1172227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1173227825Stheraven_Tp& 1174227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1175227825Stheraven{ 1176227825Stheraven iterator __i = find(__k); 1177227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1178227825Stheraven if (__i == end()) 1179227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1180227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1181227825Stheraven return __i->second; 1182227825Stheraven} 1183227825Stheraven 1184227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1185227825Stheravenconst _Tp& 1186227825Stheravenunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1187227825Stheraven{ 1188227825Stheraven const_iterator __i = find(__k); 1189227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1190227825Stheraven if (__i == end()) 1191227825Stheraven throw out_of_range("unordered_map::at: key not found"); 1192227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1193227825Stheraven return __i->second; 1194227825Stheraven} 1195227825Stheraven 1196227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1197227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1198227825Stheravenvoid 1199227825Stheravenswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1200227825Stheraven unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1201227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1202227825Stheraven{ 1203227825Stheraven __x.swap(__y); 1204227825Stheraven} 1205227825Stheraven 1206227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1207227825Stheravenbool 1208227825Stheravenoperator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1209227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1210227825Stheraven{ 1211227825Stheraven if (__x.size() != __y.size()) 1212227825Stheraven return false; 1213227825Stheraven typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1214227825Stheraven const_iterator; 1215227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1216227825Stheraven __i != __ex; ++__i) 1217227825Stheraven { 1218227825Stheraven const_iterator __j = __y.find(__i->first); 1219227825Stheraven if (__j == __ey || !(*__i == *__j)) 1220227825Stheraven return false; 1221227825Stheraven } 1222227825Stheraven return true; 1223227825Stheraven} 1224227825Stheraven 1225227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1226227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1227227825Stheravenbool 1228227825Stheravenoperator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1229227825Stheraven const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1230227825Stheraven{ 1231227825Stheraven return !(__x == __y); 1232227825Stheraven} 1233227825Stheraven 1234227825Stheraventemplate <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1235227825Stheraven class _Alloc = allocator<pair<const _Key, _Tp> > > 1236227825Stheravenclass _LIBCPP_VISIBLE unordered_multimap 1237227825Stheraven{ 1238227825Stheravenpublic: 1239227825Stheraven // types 1240227825Stheraven typedef _Key key_type; 1241227825Stheraven typedef _Tp mapped_type; 1242227825Stheraven typedef _Hash hasher; 1243227825Stheraven typedef _Pred key_equal; 1244227825Stheraven typedef _Alloc allocator_type; 1245227825Stheraven typedef pair<const key_type, mapped_type> value_type; 1246227825Stheraven typedef value_type& reference; 1247227825Stheraven typedef const value_type& const_reference; 1248227825Stheraven 1249227825Stheravenprivate: 1250227825Stheraven typedef pair<key_type, mapped_type> __value_type; 1251227825Stheraven typedef __unordered_map_hasher<__value_type, hasher> __hasher; 1252227825Stheraven typedef __unordered_map_equal<__value_type, key_equal> __key_equal; 1253227825Stheraven typedef typename allocator_traits<allocator_type>::template 1254227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1255227825Stheraven rebind_alloc<__value_type> 1256227825Stheraven#else 1257227825Stheraven rebind_alloc<__value_type>::other 1258227825Stheraven#endif 1259227825Stheraven __allocator_type; 1260227825Stheraven 1261227825Stheraven typedef __hash_table<__value_type, __hasher, 1262227825Stheraven __key_equal, __allocator_type> __table; 1263227825Stheraven 1264227825Stheraven __table __table_; 1265227825Stheraven 1266227825Stheraven typedef typename __table::__node_traits __node_traits; 1267227825Stheraven typedef typename __table::__node_allocator __node_allocator; 1268227825Stheraven typedef typename __table::__node __node; 1269227825Stheraven typedef __hash_map_node_destructor<__node_allocator> _D; 1270227825Stheraven typedef unique_ptr<__node, _D> __node_holder; 1271227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 1272227825Stheravenpublic: 1273227825Stheraven typedef typename __alloc_traits::pointer pointer; 1274227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 1275227825Stheraven typedef typename __alloc_traits::size_type size_type; 1276227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 1277227825Stheraven 1278227825Stheraven typedef __hash_map_iterator<typename __table::iterator> iterator; 1279227825Stheraven typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1280227825Stheraven typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1281227825Stheraven typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1282227825Stheraven 1283227825Stheraven _LIBCPP_INLINE_VISIBILITY 1284227825Stheraven unordered_multimap() 1285227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1286227825Stheraven {} // = default; 1287227825Stheraven explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1288227825Stheraven const key_equal& __eql = key_equal()); 1289227825Stheraven unordered_multimap(size_type __n, const hasher& __hf, 1290227825Stheraven const key_equal& __eql, 1291227825Stheraven const allocator_type& __a); 1292227825Stheraven template <class _InputIterator> 1293227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last); 1294227825Stheraven template <class _InputIterator> 1295227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1296227825Stheraven size_type __n, const hasher& __hf = hasher(), 1297227825Stheraven const key_equal& __eql = key_equal()); 1298227825Stheraven template <class _InputIterator> 1299227825Stheraven unordered_multimap(_InputIterator __first, _InputIterator __last, 1300227825Stheraven size_type __n, const hasher& __hf, 1301227825Stheraven const key_equal& __eql, 1302227825Stheraven const allocator_type& __a); 1303227825Stheraven explicit unordered_multimap(const allocator_type& __a); 1304227825Stheraven unordered_multimap(const unordered_multimap& __u); 1305227825Stheraven unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1306227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1307227825Stheraven unordered_multimap(unordered_multimap&& __u) 1308227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1309227825Stheraven unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1310227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1311227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1312227825Stheraven unordered_multimap(initializer_list<value_type> __il); 1313227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1314227825Stheraven const hasher& __hf = hasher(), 1315227825Stheraven const key_equal& __eql = key_equal()); 1316227825Stheraven unordered_multimap(initializer_list<value_type> __il, size_type __n, 1317227825Stheraven const hasher& __hf, const key_equal& __eql, 1318227825Stheraven const allocator_type& __a); 1319227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1320227825Stheraven // ~unordered_multimap() = default; 1321227825Stheraven _LIBCPP_INLINE_VISIBILITY 1322227825Stheraven unordered_multimap& operator=(const unordered_multimap& __u) 1323227825Stheraven { 1324227825Stheraven __table_ = __u.__table_; 1325227825Stheraven return *this; 1326227825Stheraven } 1327227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1328227825Stheraven unordered_multimap& operator=(unordered_multimap&& __u) 1329227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1330227825Stheraven#endif 1331227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1332227825Stheraven unordered_multimap& operator=(initializer_list<value_type> __il); 1333227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1334227825Stheraven 1335227825Stheraven _LIBCPP_INLINE_VISIBILITY 1336227825Stheraven allocator_type get_allocator() const _NOEXCEPT 1337227825Stheraven {return allocator_type(__table_.__node_alloc());} 1338227825Stheraven 1339227825Stheraven _LIBCPP_INLINE_VISIBILITY 1340227825Stheraven bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1341227825Stheraven _LIBCPP_INLINE_VISIBILITY 1342227825Stheraven size_type size() const _NOEXCEPT {return __table_.size();} 1343227825Stheraven _LIBCPP_INLINE_VISIBILITY 1344227825Stheraven size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1345227825Stheraven 1346227825Stheraven _LIBCPP_INLINE_VISIBILITY 1347227825Stheraven iterator begin() _NOEXCEPT {return __table_.begin();} 1348227825Stheraven _LIBCPP_INLINE_VISIBILITY 1349227825Stheraven iterator end() _NOEXCEPT {return __table_.end();} 1350227825Stheraven _LIBCPP_INLINE_VISIBILITY 1351227825Stheraven const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1352227825Stheraven _LIBCPP_INLINE_VISIBILITY 1353227825Stheraven const_iterator end() const _NOEXCEPT {return __table_.end();} 1354227825Stheraven _LIBCPP_INLINE_VISIBILITY 1355227825Stheraven const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1356227825Stheraven _LIBCPP_INLINE_VISIBILITY 1357227825Stheraven const_iterator cend() const _NOEXCEPT {return __table_.end();} 1358227825Stheraven 1359227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1360227825Stheraven _LIBCPP_INLINE_VISIBILITY 1361227825Stheraven iterator emplace() 1362227825Stheraven {return __table_.__emplace_multi();} 1363227825Stheraven 1364227825Stheraven template <class _A0, 1365227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 1366227825Stheraven _LIBCPP_INLINE_VISIBILITY 1367227825Stheraven iterator emplace(_A0&& __a0) 1368227825Stheraven {return __table_.__emplace_multi(_VSTD::forward<_A0>(__a0));} 1369227825Stheraven 1370227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1371227825Stheraven 1372227825Stheraven template <class _A0, class... _Args, 1373227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 1374227825Stheraven iterator emplace(_A0&& __a0, _Args&&... __args); 1375227825Stheraven 1376227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1377227825Stheraven 1378227825Stheraven _LIBCPP_INLINE_VISIBILITY 1379227825Stheraven iterator emplace_hint(const_iterator __p) 1380227825Stheraven {return __table_.__emplace_hint_multi(__p.__i_);} 1381227825Stheraven 1382227825Stheraven template <class _A0, 1383227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 1384227825Stheraven _LIBCPP_INLINE_VISIBILITY 1385227825Stheraven iterator emplace_hint(const_iterator __p, _A0&& __a0) 1386227825Stheraven {return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_A0>(__a0));} 1387227825Stheraven 1388227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1389227825Stheraven 1390227825Stheraven template <class _A0, class... _Args, 1391227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 1392227825Stheraven iterator emplace_hint(const_iterator __p, _A0&& __a0, _Args&&... __args); 1393227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1394227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1395227825Stheraven _LIBCPP_INLINE_VISIBILITY 1396227825Stheraven iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1397227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1398227825Stheraven template <class _P, 1399227825Stheraven class = typename enable_if<is_constructible<value_type, _P>::value>::type> 1400227825Stheraven _LIBCPP_INLINE_VISIBILITY 1401227825Stheraven iterator insert(_P&& __x) 1402227825Stheraven {return __table_.__insert_multi(_VSTD::forward<_P>(__x));} 1403227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1404227825Stheraven _LIBCPP_INLINE_VISIBILITY 1405227825Stheraven iterator insert(const_iterator __p, const value_type& __x) 1406227825Stheraven {return __table_.__insert_multi(__p.__i_, __x);} 1407227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1408227825Stheraven template <class _P, 1409227825Stheraven class = typename enable_if<is_constructible<value_type, _P>::value>::type> 1410227825Stheraven _LIBCPP_INLINE_VISIBILITY 1411227825Stheraven iterator insert(const_iterator __p, _P&& __x) 1412227825Stheraven {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_P>(__x));} 1413227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1414227825Stheraven template <class _InputIterator> 1415227825Stheraven void insert(_InputIterator __first, _InputIterator __last); 1416227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1417227825Stheraven _LIBCPP_INLINE_VISIBILITY 1418227825Stheraven void insert(initializer_list<value_type> __il) 1419227825Stheraven {insert(__il.begin(), __il.end());} 1420227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1421227825Stheraven 1422227825Stheraven _LIBCPP_INLINE_VISIBILITY 1423227825Stheraven iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1424227825Stheraven _LIBCPP_INLINE_VISIBILITY 1425227825Stheraven size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1426227825Stheraven _LIBCPP_INLINE_VISIBILITY 1427227825Stheraven iterator erase(const_iterator __first, const_iterator __last) 1428227825Stheraven {return __table_.erase(__first.__i_, __last.__i_);} 1429227825Stheraven _LIBCPP_INLINE_VISIBILITY 1430227825Stheraven void clear() _NOEXCEPT {__table_.clear();} 1431227825Stheraven 1432227825Stheraven _LIBCPP_INLINE_VISIBILITY 1433227825Stheraven void swap(unordered_multimap& __u) 1434227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1435227825Stheraven {__table_.swap(__u.__table_);} 1436227825Stheraven 1437227825Stheraven _LIBCPP_INLINE_VISIBILITY 1438227825Stheraven hasher hash_function() const 1439227825Stheraven {return __table_.hash_function().hash_function();} 1440227825Stheraven _LIBCPP_INLINE_VISIBILITY 1441227825Stheraven key_equal key_eq() const 1442227825Stheraven {return __table_.key_eq().key_eq();} 1443227825Stheraven 1444227825Stheraven _LIBCPP_INLINE_VISIBILITY 1445227825Stheraven iterator find(const key_type& __k) {return __table_.find(__k);} 1446227825Stheraven _LIBCPP_INLINE_VISIBILITY 1447227825Stheraven const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1448227825Stheraven _LIBCPP_INLINE_VISIBILITY 1449227825Stheraven size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1450227825Stheraven _LIBCPP_INLINE_VISIBILITY 1451227825Stheraven pair<iterator, iterator> equal_range(const key_type& __k) 1452227825Stheraven {return __table_.__equal_range_multi(__k);} 1453227825Stheraven _LIBCPP_INLINE_VISIBILITY 1454227825Stheraven pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1455227825Stheraven {return __table_.__equal_range_multi(__k);} 1456227825Stheraven 1457227825Stheraven _LIBCPP_INLINE_VISIBILITY 1458227825Stheraven size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1459227825Stheraven _LIBCPP_INLINE_VISIBILITY 1460227825Stheraven size_type max_bucket_count() const _NOEXCEPT 1461227825Stheraven {return __table_.max_bucket_count();} 1462227825Stheraven 1463227825Stheraven _LIBCPP_INLINE_VISIBILITY 1464227825Stheraven size_type bucket_size(size_type __n) const 1465227825Stheraven {return __table_.bucket_size(__n);} 1466227825Stheraven _LIBCPP_INLINE_VISIBILITY 1467227825Stheraven size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1468227825Stheraven 1469227825Stheraven _LIBCPP_INLINE_VISIBILITY 1470227825Stheraven local_iterator begin(size_type __n) {return __table_.begin(__n);} 1471227825Stheraven _LIBCPP_INLINE_VISIBILITY 1472227825Stheraven local_iterator end(size_type __n) {return __table_.end(__n);} 1473227825Stheraven _LIBCPP_INLINE_VISIBILITY 1474227825Stheraven const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1475227825Stheraven _LIBCPP_INLINE_VISIBILITY 1476227825Stheraven const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1477227825Stheraven _LIBCPP_INLINE_VISIBILITY 1478227825Stheraven const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1479227825Stheraven _LIBCPP_INLINE_VISIBILITY 1480227825Stheraven const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1481227825Stheraven 1482227825Stheraven _LIBCPP_INLINE_VISIBILITY 1483227825Stheraven float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1484227825Stheraven _LIBCPP_INLINE_VISIBILITY 1485227825Stheraven float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1486227825Stheraven _LIBCPP_INLINE_VISIBILITY 1487227825Stheraven void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1488227825Stheraven _LIBCPP_INLINE_VISIBILITY 1489227825Stheraven void rehash(size_type __n) {__table_.rehash(__n);} 1490227825Stheraven _LIBCPP_INLINE_VISIBILITY 1491227825Stheraven void reserve(size_type __n) {__table_.reserve(__n);} 1492227825Stheraven 1493227825Stheravenprivate: 1494227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1495227825Stheraven template <class _A0, class... _Args, 1496227825Stheraven class = typename enable_if<is_constructible<key_type, _A0>::value>::type> 1497227825Stheraven __node_holder __construct_node(_A0&& __a0, _Args&&... __args); 1498227825Stheraven template <class _A0, 1499227825Stheraven class = typename enable_if<is_constructible<value_type, _A0>::value>::type> 1500227825Stheraven __node_holder __construct_node(_A0&& __a0); 1501227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1502227825Stheraven}; 1503227825Stheraven 1504227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1505227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1506227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql) 1507227825Stheraven : __table_(__hf, __eql) 1508227825Stheraven{ 1509227825Stheraven __table_.rehash(__n); 1510227825Stheraven} 1511227825Stheraven 1512227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1513227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1514227825Stheraven size_type __n, const hasher& __hf, const key_equal& __eql, 1515227825Stheraven const allocator_type& __a) 1516227825Stheraven : __table_(__hf, __eql, __a) 1517227825Stheraven{ 1518227825Stheraven __table_.rehash(__n); 1519227825Stheraven} 1520227825Stheraven 1521227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1522227825Stheraventemplate <class _InputIterator> 1523227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1524227825Stheraven _InputIterator __first, _InputIterator __last) 1525227825Stheraven{ 1526227825Stheraven insert(__first, __last); 1527227825Stheraven} 1528227825Stheraven 1529227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1530227825Stheraventemplate <class _InputIterator> 1531227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1532227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1533227825Stheraven const hasher& __hf, const key_equal& __eql) 1534227825Stheraven : __table_(__hf, __eql) 1535227825Stheraven{ 1536227825Stheraven __table_.rehash(__n); 1537227825Stheraven insert(__first, __last); 1538227825Stheraven} 1539227825Stheraven 1540227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1541227825Stheraventemplate <class _InputIterator> 1542227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1543227825Stheraven _InputIterator __first, _InputIterator __last, size_type __n, 1544227825Stheraven const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1545227825Stheraven : __table_(__hf, __eql, __a) 1546227825Stheraven{ 1547227825Stheraven __table_.rehash(__n); 1548227825Stheraven insert(__first, __last); 1549227825Stheraven} 1550227825Stheraven 1551227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1552227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1553227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1554227825Stheraven const allocator_type& __a) 1555227825Stheraven : __table_(__a) 1556227825Stheraven{ 1557227825Stheraven} 1558227825Stheraven 1559227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1560227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1561227825Stheraven const unordered_multimap& __u) 1562227825Stheraven : __table_(__u.__table_) 1563227825Stheraven{ 1564227825Stheraven __table_.rehash(__u.bucket_count()); 1565227825Stheraven insert(__u.begin(), __u.end()); 1566227825Stheraven} 1567227825Stheraven 1568227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1569227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1570227825Stheraven const unordered_multimap& __u, const allocator_type& __a) 1571227825Stheraven : __table_(__u.__table_, __a) 1572227825Stheraven{ 1573227825Stheraven __table_.rehash(__u.bucket_count()); 1574227825Stheraven insert(__u.begin(), __u.end()); 1575227825Stheraven} 1576227825Stheraven 1577227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1578227825Stheraven 1579227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1580227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1581227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1582227825Stheraven unordered_multimap&& __u) 1583227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1584227825Stheraven : __table_(_VSTD::move(__u.__table_)) 1585227825Stheraven{ 1586227825Stheraven} 1587227825Stheraven 1588227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1589227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1590227825Stheraven unordered_multimap&& __u, const allocator_type& __a) 1591227825Stheraven : __table_(_VSTD::move(__u.__table_), __a) 1592227825Stheraven{ 1593227825Stheraven if (__a != __u.get_allocator()) 1594227825Stheraven { 1595227825Stheraven iterator __i = __u.begin(); 1596227825Stheraven while (__u.size() != 0) 1597227825Stheraven{ 1598227825Stheraven __table_.__insert_multi( 1599227825Stheraven _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1600227825Stheraven ); 1601227825Stheraven} 1602227825Stheraven } 1603227825Stheraven} 1604227825Stheraven 1605227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1606227825Stheraven 1607227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1608227825Stheraven 1609227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1610227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1611227825Stheraven initializer_list<value_type> __il) 1612227825Stheraven{ 1613227825Stheraven insert(__il.begin(), __il.end()); 1614227825Stheraven} 1615227825Stheraven 1616227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1617227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1618227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1619227825Stheraven const key_equal& __eql) 1620227825Stheraven : __table_(__hf, __eql) 1621227825Stheraven{ 1622227825Stheraven __table_.rehash(__n); 1623227825Stheraven insert(__il.begin(), __il.end()); 1624227825Stheraven} 1625227825Stheraven 1626227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1627227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1628227825Stheraven initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1629227825Stheraven const key_equal& __eql, const allocator_type& __a) 1630227825Stheraven : __table_(__hf, __eql, __a) 1631227825Stheraven{ 1632227825Stheraven __table_.rehash(__n); 1633227825Stheraven insert(__il.begin(), __il.end()); 1634227825Stheraven} 1635227825Stheraven 1636227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1637227825Stheraven 1638227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1639227825Stheraven 1640227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1641227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1642227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1643227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1644227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1645227825Stheraven{ 1646227825Stheraven __table_ = _VSTD::move(__u.__table_); 1647227825Stheraven return *this; 1648227825Stheraven} 1649227825Stheraven 1650227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1651227825Stheraven 1652227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1653227825Stheraven 1654227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1655227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1656227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1657227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1658227825Stheraven initializer_list<value_type> __il) 1659227825Stheraven{ 1660227825Stheraven __table_.__assign_multi(__il.begin(), __il.end()); 1661227825Stheraven return *this; 1662227825Stheraven} 1663227825Stheraven 1664227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1665227825Stheraven 1666227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1667227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1668227825Stheraven 1669227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1670227825Stheraventemplate <class _A0, class... _Args, 1671227825Stheraven class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1672227825Stheraven > 1673227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1674227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 1675227825Stheraven _A0&& __a0, _Args&&... __args) 1676227825Stheraven{ 1677227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1678227825Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _D(__na)); 1679227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), 1680227825Stheraven _VSTD::forward<_A0>(__a0)); 1681227825Stheraven __h.get_deleter().__first_constructed = true; 1682227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second), 1683227825Stheraven _VSTD::forward<_Args>(__args)...); 1684227825Stheraven __h.get_deleter().__second_constructed = true; 1685227825Stheraven return __h; 1686227825Stheraven} 1687227825Stheraven 1688227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1689227825Stheraven 1690227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1691227825Stheraventemplate <class _A0, 1692227825Stheraven class // = typename enable_if<is_constructible<value_type, _A0>::value>::type 1693227825Stheraven > 1694227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1695227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1696227825Stheraven{ 1697227825Stheraven __node_allocator& __na = __table_.__node_alloc(); 1698227825Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _D(__na)); 1699227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1700227825Stheraven _VSTD::forward<_A0>(__a0)); 1701227825Stheraven __h.get_deleter().__first_constructed = true; 1702227825Stheraven __h.get_deleter().__second_constructed = true; 1703227825Stheraven return __h; 1704227825Stheraven} 1705227825Stheraven 1706227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1707227825Stheraven 1708227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1709227825Stheraventemplate <class _A0, class... _Args, 1710227825Stheraven class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1711227825Stheraven > 1712227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1713227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args) 1714227825Stheraven{ 1715227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0), 1716227825Stheraven _VSTD::forward<_Args>(__args)...); 1717227825Stheraven iterator __r = __table_.__node_insert_multi(__h.get()); 1718227825Stheraven __h.release(); 1719227825Stheraven return __r; 1720227825Stheraven} 1721227825Stheraven 1722227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1723227825Stheraventemplate <class _A0, class... _Args, 1724227825Stheraven class // = typename enable_if<is_constructible<key_type, _A0>::value>::type 1725227825Stheraven > 1726227825Stheraventypename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 1727227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 1728227825Stheraven const_iterator __p, _A0&& __a0, _Args&&... __args) 1729227825Stheraven{ 1730227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0), 1731227825Stheraven _VSTD::forward<_Args>(__args)...); 1732227825Stheraven iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 1733227825Stheraven __h.release(); 1734227825Stheraven return __r; 1735227825Stheraven} 1736227825Stheraven 1737227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1738227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1739227825Stheraven 1740227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1741227825Stheraventemplate <class _InputIterator> 1742227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1743227825Stheravenvoid 1744227825Stheravenunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1745227825Stheraven _InputIterator __last) 1746227825Stheraven{ 1747227825Stheraven for (; __first != __last; ++__first) 1748227825Stheraven __table_.__insert_multi(*__first); 1749227825Stheraven} 1750227825Stheraven 1751227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1752227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1753227825Stheravenvoid 1754227825Stheravenswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1755227825Stheraven unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1756227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1757227825Stheraven{ 1758227825Stheraven __x.swap(__y); 1759227825Stheraven} 1760227825Stheraven 1761227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1762227825Stheravenbool 1763227825Stheravenoperator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1764227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1765227825Stheraven{ 1766227825Stheraven if (__x.size() != __y.size()) 1767227825Stheraven return false; 1768227825Stheraven typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1769227825Stheraven const_iterator; 1770227825Stheraven typedef pair<const_iterator, const_iterator> _EqRng; 1771227825Stheraven for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 1772227825Stheraven { 1773227825Stheraven _EqRng __xeq = __x.equal_range(__i->first); 1774227825Stheraven _EqRng __yeq = __y.equal_range(__i->first); 1775227825Stheraven if (_VSTD::distance(__xeq.first, __xeq.second) != 1776227825Stheraven _VSTD::distance(__yeq.first, __yeq.second) || 1777227825Stheraven !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 1778227825Stheraven return false; 1779227825Stheraven __i = __xeq.second; 1780227825Stheraven } 1781227825Stheraven return true; 1782227825Stheraven} 1783227825Stheraven 1784227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1785227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1786227825Stheravenbool 1787227825Stheravenoperator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1788227825Stheraven const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1789227825Stheraven{ 1790227825Stheraven return !(__x == __y); 1791227825Stheraven} 1792227825Stheraven 1793227825Stheraven_LIBCPP_END_NAMESPACE_STD 1794227825Stheraven 1795227825Stheraven#endif // _LIBCPP_UNORDERED_MAP 1796