codekingpro/portable-devtools
115k
1// -*- C++ -*-2//===-------------------------- unordered_map -----------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCUDACXX_UNORDERED_MAP11#define _LIBCUDACXX_UNORDERED_MAP12 13/*14 15 unordered_map synopsis16 17#include <initializer_list>18 19namespace std20{21 22template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,23 class Alloc = allocator<pair<const Key, T>>>24class unordered_map25{26public:27 // types28 typedef Key key_type;29 typedef T mapped_type;30 typedef Hash hasher;31 typedef Pred key_equal;32 typedef Alloc allocator_type;33 typedef pair<const key_type, mapped_type> value_type;34 typedef value_type& reference;35 typedef const value_type& const_reference;36 typedef typename allocator_traits<allocator_type>::pointer pointer;37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;38 typedef typename allocator_traits<allocator_type>::size_type size_type;39 typedef typename allocator_traits<allocator_type>::difference_type difference_type;40 41 typedef /unspecified/ iterator;42 typedef /unspecified/ const_iterator;43 typedef /unspecified/ local_iterator;44 typedef /unspecified/ const_local_iterator;45 46 typedef unspecified node_type; // C++1747 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++1748 49 unordered_map()50 noexcept(51 is_nothrow_default_constructible<hasher>::value &&52 is_nothrow_default_constructible<key_equal>::value &&53 is_nothrow_default_constructible<allocator_type>::value);54 explicit unordered_map(size_type n, const hasher& hf = hasher(),55 const key_equal& eql = key_equal(),56 const allocator_type& a = allocator_type());57 template <class InputIterator>58 unordered_map(InputIterator f, InputIterator l,59 size_type n = 0, const hasher& hf = hasher(),60 const key_equal& eql = key_equal(),61 const allocator_type& a = allocator_type());62 explicit unordered_map(const allocator_type&);63 unordered_map(const unordered_map&);64 unordered_map(const unordered_map&, const Allocator&);65 unordered_map(unordered_map&&)66 noexcept(67 is_nothrow_move_constructible<hasher>::value &&68 is_nothrow_move_constructible<key_equal>::value &&69 is_nothrow_move_constructible<allocator_type>::value);70 unordered_map(unordered_map&&, const Allocator&);71 unordered_map(initializer_list<value_type>, size_type n = 0,72 const hasher& hf = hasher(), const key_equal& eql = key_equal(),73 const allocator_type& a = allocator_type());74 unordered_map(size_type n, const allocator_type& a)75 : unordered_map(n, hasher(), key_equal(), a) {} // C++1476 unordered_map(size_type n, const hasher& hf, const allocator_type& a)77 : unordered_map(n, hf, key_equal(), a) {} // C++1478 template <class InputIterator>79 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)80 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++1481 template <class InputIterator>82 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,83 const allocator_type& a)84 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++1485 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)86 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++1487 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,88 const allocator_type& a)89 : unordered_map(il, n, hf, key_equal(), a) {} // C++1490 ~unordered_map();91 unordered_map& operator=(const unordered_map&);92 unordered_map& operator=(unordered_map&&)93 noexcept(94 allocator_type::propagate_on_container_move_assignment::value &&95 is_nothrow_move_assignable<allocator_type>::value &&96 is_nothrow_move_assignable<hasher>::value &&97 is_nothrow_move_assignable<key_equal>::value);98 unordered_map& operator=(initializer_list<value_type>);99 100 allocator_type get_allocator() const noexcept;101 102 bool empty() const noexcept;103 size_type size() const noexcept;104 size_type max_size() const noexcept;105 106 iterator begin() noexcept;107 iterator end() noexcept;108 const_iterator begin() const noexcept;109 const_iterator end() const noexcept;110 const_iterator cbegin() const noexcept;111 const_iterator cend() const noexcept;112 113 template <class... Args>114 pair<iterator, bool> emplace(Args&&... args);115 template <class... Args>116 iterator emplace_hint(const_iterator position, Args&&... args);117 pair<iterator, bool> insert(const value_type& obj);118 template <class P>119 pair<iterator, bool> insert(P&& obj);120 iterator insert(const_iterator hint, const value_type& obj);121 template <class P>122 iterator insert(const_iterator hint, P&& obj);123 template <class InputIterator>124 void insert(InputIterator first, InputIterator last);125 void insert(initializer_list<value_type>);126 127 node_type extract(const_iterator position); // C++17128 node_type extract(const key_type& x); // C++17129 insert_return_type insert(node_type&& nh); // C++17130 iterator insert(const_iterator hint, node_type&& nh); // C++17131 132 template <class... Args>133 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17134 template <class... Args>135 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17136 template <class... Args>137 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17138 template <class... Args>139 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17140 template <class M>141 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17142 template <class M>143 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17144 template <class M>145 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17146 template <class M>147 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17148 149 iterator erase(const_iterator position);150 iterator erase(iterator position); // C++14151 size_type erase(const key_type& k);152 iterator erase(const_iterator first, const_iterator last);153 void clear() noexcept;154 155 template<class H2, class P2>156 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17157 template<class H2, class P2>158 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17159 template<class H2, class P2>160 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17161 template<class H2, class P2>162 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17163 164 void swap(unordered_map&)165 noexcept(166 (!allocator_type::propagate_on_container_swap::value ||167 __is_nothrow_swappable<allocator_type>::value) &&168 __is_nothrow_swappable<hasher>::value &&169 __is_nothrow_swappable<key_equal>::value);170 171 hasher hash_function() const;172 key_equal key_eq() const;173 174 iterator find(const key_type& k);175 const_iterator find(const key_type& k) const;176 size_type count(const key_type& k) const;177 bool contains(const key_type& k) const; // C++20178 pair<iterator, iterator> equal_range(const key_type& k);179 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;180 181 mapped_type& operator[](const key_type& k);182 mapped_type& operator[](key_type&& k);183 184 mapped_type& at(const key_type& k);185 const mapped_type& at(const key_type& k) const;186 187 size_type bucket_count() const noexcept;188 size_type max_bucket_count() const noexcept;189 190 size_type bucket_size(size_type n) const;191 size_type bucket(const key_type& k) const;192 193 local_iterator begin(size_type n);194 local_iterator end(size_type n);195 const_local_iterator begin(size_type n) const;196 const_local_iterator end(size_type n) const;197 const_local_iterator cbegin(size_type n) const;198 const_local_iterator cend(size_type n) const;199 200 float load_factor() const noexcept;201 float max_load_factor() const noexcept;202 void max_load_factor(float z);203 void rehash(size_type n);204 void reserve(size_type n);205};206 207template <class Key, class T, class Hash, class Pred, class Alloc>208 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,209 unordered_map<Key, T, Hash, Pred, Alloc>& y)210 noexcept(noexcept(x.swap(y)));211 212template <class Key, class T, class Hash, class Pred, class Alloc>213 bool214 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,215 const unordered_map<Key, T, Hash, Pred, Alloc>& y);216 217template <class Key, class T, class Hash, class Pred, class Alloc>218 bool219 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,220 const unordered_map<Key, T, Hash, Pred, Alloc>& y);221 222template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,223 class Alloc = allocator<pair<const Key, T>>>224class unordered_multimap225{226public:227 // types228 typedef Key key_type;229 typedef T mapped_type;230 typedef Hash hasher;231 typedef Pred key_equal;232 typedef Alloc allocator_type;233 typedef pair<const key_type, mapped_type> value_type;234 typedef value_type& reference;235 typedef const value_type& const_reference;236 typedef typename allocator_traits<allocator_type>::pointer pointer;237 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;238 typedef typename allocator_traits<allocator_type>::size_type size_type;239 typedef typename allocator_traits<allocator_type>::difference_type difference_type;240 241 typedef /unspecified/ iterator;242 typedef /unspecified/ const_iterator;243 typedef /unspecified/ local_iterator;244 typedef /unspecified/ const_local_iterator;245 246 typedef unspecified node_type; // C++17247 248 unordered_multimap()249 noexcept(250 is_nothrow_default_constructible<hasher>::value &&251 is_nothrow_default_constructible<key_equal>::value &&252 is_nothrow_default_constructible<allocator_type>::value);253 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),254 const key_equal& eql = key_equal(),255 const allocator_type& a = allocator_type());256 template <class InputIterator>257 unordered_multimap(InputIterator f, InputIterator l,258 size_type n = 0, const hasher& hf = hasher(),259 const key_equal& eql = key_equal(),260 const allocator_type& a = allocator_type());261 explicit unordered_multimap(const allocator_type&);262 unordered_multimap(const unordered_multimap&);263 unordered_multimap(const unordered_multimap&, const Allocator&);264 unordered_multimap(unordered_multimap&&)265 noexcept(266 is_nothrow_move_constructible<hasher>::value &&267 is_nothrow_move_constructible<key_equal>::value &&268 is_nothrow_move_constructible<allocator_type>::value);269 unordered_multimap(unordered_multimap&&, const Allocator&);270 unordered_multimap(initializer_list<value_type>, size_type n = 0,271 const hasher& hf = hasher(), const key_equal& eql = key_equal(),272 const allocator_type& a = allocator_type());273 unordered_multimap(size_type n, const allocator_type& a)274 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14275 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)276 : unordered_multimap(n, hf, key_equal(), a) {} // C++14277 template <class InputIterator>278 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)279 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14280 template <class InputIterator>281 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,282 const allocator_type& a)283 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14284 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)285 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14286 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,287 const allocator_type& a)288 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14289 ~unordered_multimap();290 unordered_multimap& operator=(const unordered_multimap&);291 unordered_multimap& operator=(unordered_multimap&&)292 noexcept(293 allocator_type::propagate_on_container_move_assignment::value &&294 is_nothrow_move_assignable<allocator_type>::value &&295 is_nothrow_move_assignable<hasher>::value &&296 is_nothrow_move_assignable<key_equal>::value);297 unordered_multimap& operator=(initializer_list<value_type>);298 299 allocator_type get_allocator() const noexcept;300 301 bool empty() const noexcept;302 size_type size() const noexcept;303 size_type max_size() const noexcept;304 305 iterator begin() noexcept;306 iterator end() noexcept;307 const_iterator begin() const noexcept;308 const_iterator end() const noexcept;309 const_iterator cbegin() const noexcept;310 const_iterator cend() const noexcept;311 312 template <class... Args>313 iterator emplace(Args&&... args);314 template <class... Args>315 iterator emplace_hint(const_iterator position, Args&&... args);316 iterator insert(const value_type& obj);317 template <class P>318 iterator insert(P&& obj);319 iterator insert(const_iterator hint, const value_type& obj);320 template <class P>321 iterator insert(const_iterator hint, P&& obj);322 template <class InputIterator>323 void insert(InputIterator first, InputIterator last);324 void insert(initializer_list<value_type>);325 326 node_type extract(const_iterator position); // C++17327 node_type extract(const key_type& x); // C++17328 iterator insert(node_type&& nh); // C++17329 iterator insert(const_iterator hint, node_type&& nh); // C++17330 331 iterator erase(const_iterator position);332 iterator erase(iterator position); // C++14333 size_type erase(const key_type& k);334 iterator erase(const_iterator first, const_iterator last);335 void clear() noexcept;336 337 template<class H2, class P2>338 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17339 template<class H2, class P2>340 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17341 template<class H2, class P2>342 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17343 template<class H2, class P2>344 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17345 346 void swap(unordered_multimap&)347 noexcept(348 (!allocator_type::propagate_on_container_swap::value ||349 __is_nothrow_swappable<allocator_type>::value) &&350 __is_nothrow_swappable<hasher>::value &&351 __is_nothrow_swappable<key_equal>::value);352 353 hasher hash_function() const;354 key_equal key_eq() const;355 356 iterator find(const key_type& k);357 const_iterator find(const key_type& k) const;358 size_type count(const key_type& k) const;359 bool contains(const key_type& k) const; // C++20360 pair<iterator, iterator> equal_range(const key_type& k);361 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;362 363 size_type bucket_count() const noexcept;364 size_type max_bucket_count() const noexcept;365 366 size_type bucket_size(size_type n) const;367 size_type bucket(const key_type& k) const;368 369 local_iterator begin(size_type n);370 local_iterator end(size_type n);371 const_local_iterator begin(size_type n) const;372 const_local_iterator end(size_type n) const;373 const_local_iterator cbegin(size_type n) const;374 const_local_iterator cend(size_type n) const;375 376 float load_factor() const noexcept;377 float max_load_factor() const noexcept;378 void max_load_factor(float z);379 void rehash(size_type n);380 void reserve(size_type n);381};382 383template <class Key, class T, class Hash, class Pred, class Alloc>384 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,385 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)386 noexcept(noexcept(x.swap(y)));387 388template <class K, class T, class H, class P, class A, class Predicate>389 void erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20390 391template <class K, class T, class H, class P, class A, class Predicate>392 void erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20393 394template <class Key, class T, class Hash, class Pred, class Alloc>395 bool396 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,397 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);398 399template <class Key, class T, class Hash, class Pred, class Alloc>400 bool401 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,402 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);403 404} // std405 406*/407 408#include <__config>409#include <__hash_table>410#include <__node_handle>411#include <functional>412#include <stdexcept>413#include <tuple>414#include <version>415 416#include <__debug>417 418#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)419# pragma GCC system_header420#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)421# pragma clang system_header422#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)423# pragma system_header424#endif // no system header425 426_LIBCUDACXX_BEGIN_NAMESPACE_STD427 428template <class _Key, class _Cp, class _Hash,429 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>430class __unordered_map_hasher431 : private _Hash432{433public:434 _LIBCUDACXX_INLINE_VISIBILITY435 __unordered_map_hasher()436 noexcept(is_nothrow_default_constructible<_Hash>::value)437 : _Hash() {}438 _LIBCUDACXX_INLINE_VISIBILITY439 __unordered_map_hasher(const _Hash& __h)440 noexcept(is_nothrow_copy_constructible<_Hash>::value)441 : _Hash(__h) {}442 _LIBCUDACXX_INLINE_VISIBILITY443 const _Hash& hash_function() const noexcept {return *this;}444 _LIBCUDACXX_INLINE_VISIBILITY445 size_t operator()(const _Cp& __x) const446 {return static_cast<const _Hash&>(*this)(__x.__get_value().first);}447 _LIBCUDACXX_INLINE_VISIBILITY448 size_t operator()(const _Key& __x) const449 {return static_cast<const _Hash&>(*this)(__x);}450 void swap(__unordered_map_hasher&__y)451 noexcept(__is_nothrow_swappable<_Hash>::value)452 {453 using _CUDA_VSTD::swap;454 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));455 }456};457 458template <class _Key, class _Cp, class _Hash>459class __unordered_map_hasher<_Key, _Cp, _Hash, false>460{461 _Hash __hash_;462public:463 _LIBCUDACXX_INLINE_VISIBILITY464 __unordered_map_hasher()465 noexcept(is_nothrow_default_constructible<_Hash>::value)466 : __hash_() {}467 _LIBCUDACXX_INLINE_VISIBILITY468 __unordered_map_hasher(const _Hash& __h)469 noexcept(is_nothrow_copy_constructible<_Hash>::value)470 : __hash_(__h) {}471 _LIBCUDACXX_INLINE_VISIBILITY472 const _Hash& hash_function() const noexcept {return __hash_;}473 _LIBCUDACXX_INLINE_VISIBILITY474 size_t operator()(const _Cp& __x) const475 {return __hash_(__x.__get_value().first);}476 _LIBCUDACXX_INLINE_VISIBILITY477 size_t operator()(const _Key& __x) const478 {return __hash_(__x);}479 void swap(__unordered_map_hasher&__y)480 noexcept(__is_nothrow_swappable<_Hash>::value)481 {482 using _CUDA_VSTD::swap;483 swap(__hash_, __y.__hash_);484 }485};486 487template <class _Key, class _Cp, class _Hash, bool __b>488inline _LIBCUDACXX_INLINE_VISIBILITY489void490swap(__unordered_map_hasher<_Key, _Cp, _Hash, __b>& __x,491 __unordered_map_hasher<_Key, _Cp, _Hash, __b>& __y)492 noexcept(noexcept(__x.swap(__y)))493{494 __x.swap(__y);495}496 497template <class _Key, class _Cp, class _Pred,498 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value>499class __unordered_map_equal500 : private _Pred501{502public:503 _LIBCUDACXX_INLINE_VISIBILITY504 __unordered_map_equal()505 noexcept(is_nothrow_default_constructible<_Pred>::value)506 : _Pred() {}507 _LIBCUDACXX_INLINE_VISIBILITY508 __unordered_map_equal(const _Pred& __p)509 noexcept(is_nothrow_copy_constructible<_Pred>::value)510 : _Pred(__p) {}511 _LIBCUDACXX_INLINE_VISIBILITY512 const _Pred& key_eq() const noexcept {return *this;}513 _LIBCUDACXX_INLINE_VISIBILITY514 bool operator()(const _Cp& __x, const _Cp& __y) const515 {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);}516 _LIBCUDACXX_INLINE_VISIBILITY517 bool operator()(const _Cp& __x, const _Key& __y) const518 {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);}519 _LIBCUDACXX_INLINE_VISIBILITY520 bool operator()(const _Key& __x, const _Cp& __y) const521 {return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);}522 void swap(__unordered_map_equal&__y)523 noexcept(__is_nothrow_swappable<_Pred>::value)524 {525 using _CUDA_VSTD::swap;526 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));527 }528};529 530template <class _Key, class _Cp, class _Pred>531class __unordered_map_equal<_Key, _Cp, _Pred, false>532{533 _Pred __pred_;534public:535 _LIBCUDACXX_INLINE_VISIBILITY536 __unordered_map_equal()537 noexcept(is_nothrow_default_constructible<_Pred>::value)538 : __pred_() {}539 _LIBCUDACXX_INLINE_VISIBILITY540 __unordered_map_equal(const _Pred& __p)541 noexcept(is_nothrow_copy_constructible<_Pred>::value)542 : __pred_(__p) {}543 _LIBCUDACXX_INLINE_VISIBILITY544 const _Pred& key_eq() const noexcept {return __pred_;}545 _LIBCUDACXX_INLINE_VISIBILITY546 bool operator()(const _Cp& __x, const _Cp& __y) const547 {return __pred_(__x.__get_value().first, __y.__get_value().first);}548 _LIBCUDACXX_INLINE_VISIBILITY549 bool operator()(const _Cp& __x, const _Key& __y) const550 {return __pred_(__x.__get_value().first, __y);}551 _LIBCUDACXX_INLINE_VISIBILITY552 bool operator()(const _Key& __x, const _Cp& __y) const553 {return __pred_(__x, __y.__get_value().first);}554 void swap(__unordered_map_equal&__y)555 noexcept(__is_nothrow_swappable<_Pred>::value)556 {557 using _CUDA_VSTD::swap;558 swap(__pred_, __y.__pred_);559 }560};561 562template <class _Key, class _Cp, class _Pred, bool __b>563inline _LIBCUDACXX_INLINE_VISIBILITY564void565swap(__unordered_map_equal<_Key, _Cp, _Pred, __b>& __x,566 __unordered_map_equal<_Key, _Cp, _Pred, __b>& __y)567 noexcept(noexcept(__x.swap(__y)))568{569 __x.swap(__y);570}571 572template <class _Alloc>573class __hash_map_node_destructor574{575 typedef _Alloc allocator_type;576 typedef allocator_traits<allocator_type> __alloc_traits;577 578public:579 580 typedef typename __alloc_traits::pointer pointer;581private:582 583 allocator_type& __na_;584 585 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);586 587public:588 bool __first_constructed;589 bool __second_constructed;590 591 _LIBCUDACXX_INLINE_VISIBILITY592 explicit __hash_map_node_destructor(allocator_type& __na) noexcept593 : __na_(__na),594 __first_constructed(false),595 __second_constructed(false)596 {}597 598 _LIBCUDACXX_INLINE_VISIBILITY599 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)600 noexcept601 : __na_(__x.__na_),602 __first_constructed(__x.__value_constructed),603 __second_constructed(__x.__value_constructed)604 {605 __x.__value_constructed = false;606 }607 608 _LIBCUDACXX_INLINE_VISIBILITY609 void operator()(pointer __p) noexcept610 {611 if (__second_constructed)612 __alloc_traits::destroy(__na_, _CUDA_VSTD::addressof(__p->__value_.__get_value().second));613 if (__first_constructed)614 __alloc_traits::destroy(__na_, _CUDA_VSTD::addressof(__p->__value_.__get_value().first));615 if (__p)616 __alloc_traits::deallocate(__na_, __p, 1);617 }618};619 620template <class _Key, class _Tp>621struct __hash_value_type622{623 typedef _Key key_type;624 typedef _Tp mapped_type;625 typedef pair<const key_type, mapped_type> value_type;626 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;627 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;628 629private:630 value_type __cc;631 632public:633 _LIBCUDACXX_INLINE_VISIBILITY634 value_type& __get_value()635 {636#if _LIBCUDACXX_STD_VER > 14637 return *_CUDA_VSTD::launder(_CUDA_VSTD::addressof(__cc));638#else639 return __cc;640#endif641 }642 643 _LIBCUDACXX_INLINE_VISIBILITY644 const value_type& __get_value() const645 {646#if _LIBCUDACXX_STD_VER > 14647 return *_CUDA_VSTD::launder(_CUDA_VSTD::addressof(__cc));648#else649 return __cc;650#endif651 }652 653 _LIBCUDACXX_INLINE_VISIBILITY654 __nc_ref_pair_type __ref()655 {656 value_type& __v = __get_value();657 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);658 }659 660 _LIBCUDACXX_INLINE_VISIBILITY661 __nc_rref_pair_type __move()662 {663 value_type& __v = __get_value();664 return __nc_rref_pair_type(665 _CUDA_VSTD::move(const_cast<key_type&>(__v.first)),666 _CUDA_VSTD::move(__v.second));667 }668 669 _LIBCUDACXX_INLINE_VISIBILITY670 __hash_value_type& operator=(const __hash_value_type& __v)671 {672 __ref() = __v.__get_value();673 return *this;674 }675 676 _LIBCUDACXX_INLINE_VISIBILITY677 __hash_value_type& operator=(__hash_value_type&& __v)678 {679 __ref() = __v.__move();680 return *this;681 }682 683 template <class _ValueTp,684 class = typename enable_if<685 __is_same_uncvref<_ValueTp, value_type>::value686 >::type687 >688 _LIBCUDACXX_INLINE_VISIBILITY689 __hash_value_type& operator=(_ValueTp&& __v)690 {691 __ref() = _CUDA_VSTD::forward<_ValueTp>(__v);692 return *this;693 }694 695private:696 __hash_value_type(const __hash_value_type& __v) = delete;697 __hash_value_type(__hash_value_type&& __v) = delete;698 template <class ..._Args>699 explicit __hash_value_type(_Args&& ...__args) = delete;700 701 ~__hash_value_type() = delete;702};703 704template <class _HashIterator>705class _LIBCUDACXX_TEMPLATE_VIS __hash_map_iterator706{707 _HashIterator __i_;708 709 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;710 711public:712 typedef forward_iterator_tag iterator_category;713 typedef typename _NodeTypes::__map_value_type value_type;714 typedef typename _NodeTypes::difference_type difference_type;715 typedef value_type& reference;716 typedef typename _NodeTypes::__map_value_type_pointer pointer;717 718 _LIBCUDACXX_INLINE_VISIBILITY719 __hash_map_iterator() noexcept {}720 721 _LIBCUDACXX_INLINE_VISIBILITY722 __hash_map_iterator(_HashIterator __i) noexcept : __i_(__i) {}723 724 _LIBCUDACXX_INLINE_VISIBILITY725 reference operator*() const {return __i_->__get_value();}726 _LIBCUDACXX_INLINE_VISIBILITY727 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}728 729 _LIBCUDACXX_INLINE_VISIBILITY730 __hash_map_iterator& operator++() {++__i_; return *this;}731 _LIBCUDACXX_INLINE_VISIBILITY732 __hash_map_iterator operator++(int)733 {734 __hash_map_iterator __t(*this);735 ++(*this);736 return __t;737 }738 739 friend _LIBCUDACXX_INLINE_VISIBILITY740 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)741 {return __x.__i_ == __y.__i_;}742 friend _LIBCUDACXX_INLINE_VISIBILITY743 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)744 {return __x.__i_ != __y.__i_;}745 746 template <class, class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS unordered_map;747 template <class, class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS unordered_multimap;748 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_const_iterator;749 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_const_local_iterator;750 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_map_const_iterator;751};752 753template <class _HashIterator>754class _LIBCUDACXX_TEMPLATE_VIS __hash_map_const_iterator755{756 _HashIterator __i_;757 758 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;759 760public:761 typedef forward_iterator_tag iterator_category;762 typedef typename _NodeTypes::__map_value_type value_type;763 typedef typename _NodeTypes::difference_type difference_type;764 typedef const value_type& reference;765 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;766 767 _LIBCUDACXX_INLINE_VISIBILITY768 __hash_map_const_iterator() noexcept {}769 770 _LIBCUDACXX_INLINE_VISIBILITY771 __hash_map_const_iterator(_HashIterator __i) noexcept : __i_(__i) {}772 _LIBCUDACXX_INLINE_VISIBILITY773 __hash_map_const_iterator(774 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)775 noexcept776 : __i_(__i.__i_) {}777 778 _LIBCUDACXX_INLINE_VISIBILITY779 reference operator*() const {return __i_->__get_value();}780 _LIBCUDACXX_INLINE_VISIBILITY781 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}782 783 _LIBCUDACXX_INLINE_VISIBILITY784 __hash_map_const_iterator& operator++() {++__i_; return *this;}785 _LIBCUDACXX_INLINE_VISIBILITY786 __hash_map_const_iterator operator++(int)787 {788 __hash_map_const_iterator __t(*this);789 ++(*this);790 return __t;791 }792 793 friend _LIBCUDACXX_INLINE_VISIBILITY794 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)795 {return __x.__i_ == __y.__i_;}796 friend _LIBCUDACXX_INLINE_VISIBILITY797 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)798 {return __x.__i_ != __y.__i_;}799 800 template <class, class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS unordered_map;801 template <class, class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS unordered_multimap;802 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_const_iterator;803 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __hash_const_local_iterator;804};805 806template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>807class unordered_multimap;808 809template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,810 class _Alloc = allocator<pair<const _Key, _Tp> > >811class _LIBCUDACXX_TEMPLATE_VIS unordered_map812{813public:814 // types815 typedef _Key key_type;816 typedef _Tp mapped_type;817 typedef __type_identity_t<_Hash> hasher;818 typedef __type_identity_t<_Pred> key_equal;819 typedef __type_identity_t<_Alloc> allocator_type;820 typedef pair<const key_type, mapped_type> value_type;821 typedef value_type& reference;822 typedef const value_type& const_reference;823 static_assert((is_same<value_type, typename allocator_type::value_type>::value),824 "Invalid allocator::value_type");825 826private:827 typedef __hash_value_type<key_type, mapped_type> __value_type;828 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;829 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;830 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,831 __value_type>::type __allocator_type;832 833 typedef __hash_table<__value_type, __hasher,834 __key_equal, __allocator_type> __table;835 836 __table __table_;837 838 typedef typename __table::_NodeTypes _NodeTypes;839 typedef typename __table::__node_pointer __node_pointer;840 typedef typename __table::__node_const_pointer __node_const_pointer;841 typedef typename __table::__node_traits __node_traits;842 typedef typename __table::__node_allocator __node_allocator;843 typedef typename __table::__node __node;844 typedef __hash_map_node_destructor<__node_allocator> _Dp;845 typedef unique_ptr<__node, _Dp> __node_holder;846 typedef allocator_traits<allocator_type> __alloc_traits;847 848 static_assert((is_same<typename __table::__container_value_type, value_type>::value), "");849 static_assert((is_same<typename __table::__node_value_type, __value_type>::value), "");850public:851 typedef typename __alloc_traits::pointer pointer;852 typedef typename __alloc_traits::const_pointer const_pointer;853 typedef typename __table::size_type size_type;854 typedef typename __table::difference_type difference_type;855 856 typedef __hash_map_iterator<typename __table::iterator> iterator;857 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;858 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;859 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;860 861#if _LIBCUDACXX_STD_VER > 14862 typedef __map_node_handle<__node, allocator_type> node_type;863 typedef __insert_return_type<iterator, node_type> insert_return_type;864#endif865 866 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>867 friend class _LIBCUDACXX_TEMPLATE_VIS unordered_map;868 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>869 friend class _LIBCUDACXX_TEMPLATE_VIS unordered_multimap;870 871 _LIBCUDACXX_INLINE_VISIBILITY872 unordered_map()873 noexcept(is_nothrow_default_constructible<__table>::value)874 {875#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE876 __get_db()->__insert_c(this);877#endif878 }879 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),880 const key_equal& __eql = key_equal());881 unordered_map(size_type __n, const hasher& __hf,882 const key_equal& __eql,883 const allocator_type& __a);884 template <class _InputIterator>885 unordered_map(_InputIterator __first, _InputIterator __last);886 template <class _InputIterator>887 unordered_map(_InputIterator __first, _InputIterator __last,888 size_type __n, const hasher& __hf = hasher(),889 const key_equal& __eql = key_equal());890 template <class _InputIterator>891 unordered_map(_InputIterator __first, _InputIterator __last,892 size_type __n, const hasher& __hf,893 const key_equal& __eql,894 const allocator_type& __a);895 _LIBCUDACXX_INLINE_VISIBILITY896 explicit unordered_map(const allocator_type& __a);897 unordered_map(const unordered_map& __u);898 unordered_map(const unordered_map& __u, const allocator_type& __a);899 _LIBCUDACXX_INLINE_VISIBILITY900 unordered_map(unordered_map&& __u)901 noexcept(is_nothrow_move_constructible<__table>::value);902 unordered_map(unordered_map&& __u, const allocator_type& __a);903 unordered_map(initializer_list<value_type> __il);904 unordered_map(initializer_list<value_type> __il, size_type __n,905 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());906 unordered_map(initializer_list<value_type> __il, size_type __n,907 const hasher& __hf, const key_equal& __eql,908 const allocator_type& __a);909#if _LIBCUDACXX_STD_VER > 11910 _LIBCUDACXX_INLINE_VISIBILITY911 unordered_map(size_type __n, const allocator_type& __a)912 : unordered_map(__n, hasher(), key_equal(), __a) {}913 _LIBCUDACXX_INLINE_VISIBILITY914 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)915 : unordered_map(__n, __hf, key_equal(), __a) {}916 template <class _InputIterator>917 _LIBCUDACXX_INLINE_VISIBILITY918 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)919 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}920 template <class _InputIterator>921 _LIBCUDACXX_INLINE_VISIBILITY922 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,923 const allocator_type& __a)924 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}925 _LIBCUDACXX_INLINE_VISIBILITY926 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)927 : unordered_map(__il, __n, hasher(), key_equal(), __a) {}928 _LIBCUDACXX_INLINE_VISIBILITY929 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,930 const allocator_type& __a)931 : unordered_map(__il, __n, __hf, key_equal(), __a) {}932#endif933 _LIBCUDACXX_INLINE_VISIBILITY934 ~unordered_map() {935 static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");936 }937 938 _LIBCUDACXX_INLINE_VISIBILITY939 unordered_map& operator=(const unordered_map& __u)940 {941 __table_ = __u.__table_;942 return *this;943 }944 _LIBCUDACXX_INLINE_VISIBILITY945 unordered_map& operator=(unordered_map&& __u)946 noexcept(is_nothrow_move_assignable<__table>::value);947 _LIBCUDACXX_INLINE_VISIBILITY948 unordered_map& operator=(initializer_list<value_type> __il);949 950 _LIBCUDACXX_INLINE_VISIBILITY951 allocator_type get_allocator() const noexcept952 {return allocator_type(__table_.__node_alloc());}953 954 _LIBCUDACXX_NODISCARD_AFTER_CXX17 _LIBCUDACXX_INLINE_VISIBILITY955 bool empty() const noexcept {return __table_.size() == 0;}956 _LIBCUDACXX_INLINE_VISIBILITY957 size_type size() const noexcept {return __table_.size();}958 _LIBCUDACXX_INLINE_VISIBILITY959 size_type max_size() const noexcept {return __table_.max_size();}960 961 _LIBCUDACXX_INLINE_VISIBILITY962 iterator begin() noexcept {return __table_.begin();}963 _LIBCUDACXX_INLINE_VISIBILITY964 iterator end() noexcept {return __table_.end();}965 _LIBCUDACXX_INLINE_VISIBILITY966 const_iterator begin() const noexcept {return __table_.begin();}967 _LIBCUDACXX_INLINE_VISIBILITY968 const_iterator end() const noexcept {return __table_.end();}969 _LIBCUDACXX_INLINE_VISIBILITY970 const_iterator cbegin() const noexcept {return __table_.begin();}971 _LIBCUDACXX_INLINE_VISIBILITY972 const_iterator cend() const noexcept {return __table_.end();}973 974 _LIBCUDACXX_INLINE_VISIBILITY975 pair<iterator, bool> insert(const value_type& __x)976 {return __table_.__insert_unique(__x);}977 978 iterator insert(const_iterator __p, const value_type& __x) {979#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE980 _LIBCUDACXX_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,981 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"982 " referring to this unordered_map");983#else984 ((void)__p);985#endif986 return insert(__x).first;987 }988 989 template <class _InputIterator>990 _LIBCUDACXX_INLINE_VISIBILITY991 void insert(_InputIterator __first, _InputIterator __last);992 993 _LIBCUDACXX_INLINE_VISIBILITY994 void insert(initializer_list<value_type> __il)995 {insert(__il.begin(), __il.end());}996 997 _LIBCUDACXX_INLINE_VISIBILITY998 pair<iterator, bool> insert(value_type&& __x)999 {return __table_.__insert_unique(_CUDA_VSTD::move(__x));}1000 1001 iterator insert(const_iterator __p, value_type&& __x) {1002#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1003 _LIBCUDACXX_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,1004 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"1005 " referring to this unordered_map");1006#else1007 ((void)__p);1008#endif1009 return __table_.__insert_unique(_CUDA_VSTD::move(__x)).first;1010 }1011 1012 template <class _Pp,1013 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>1014 _LIBCUDACXX_INLINE_VISIBILITY1015 pair<iterator, bool> insert(_Pp&& __x)1016 {return __table_.__insert_unique(_CUDA_VSTD::forward<_Pp>(__x));}1017 1018 template <class _Pp,1019 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>1020 _LIBCUDACXX_INLINE_VISIBILITY1021 iterator insert(const_iterator __p, _Pp&& __x)1022 {1023#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1024 _LIBCUDACXX_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,1025 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"1026 " referring to this unordered_map");1027#else1028 ((void)__p);1029#endif1030 return insert(_CUDA_VSTD::forward<_Pp>(__x)).first;1031 }1032 1033 template <class... _Args>1034 _LIBCUDACXX_INLINE_VISIBILITY1035 pair<iterator, bool> emplace(_Args&&... __args) {1036 return __table_.__emplace_unique(_CUDA_VSTD::forward<_Args>(__args)...);1037 }1038 1039 template <class... _Args>1040 _LIBCUDACXX_INLINE_VISIBILITY1041 iterator emplace_hint(const_iterator __p, _Args&&... __args) {1042#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1043 _LIBCUDACXX_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,1044 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"1045 " referring to this unordered_map");1046#else1047 ((void)__p);1048#endif1049 return __table_.__emplace_unique(_CUDA_VSTD::forward<_Args>(__args)...).first;1050 }1051 1052#if _LIBCUDACXX_STD_VER > 141053 template <class... _Args>1054 _LIBCUDACXX_INLINE_VISIBILITY1055 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)1056 {1057 return __table_.__emplace_unique_key_args(__k, _CUDA_VSTD::piecewise_construct,1058 _CUDA_VSTD::forward_as_tuple(__k),1059 _CUDA_VSTD::forward_as_tuple(_CUDA_VSTD::forward<_Args>(__args)...));1060 }1061 1062 template <class... _Args>1063 _LIBCUDACXX_INLINE_VISIBILITY1064 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)1065 {1066 return __table_.__emplace_unique_key_args(__k, _CUDA_VSTD::piecewise_construct,1067 _CUDA_VSTD::forward_as_tuple(_CUDA_VSTD::move(__k)),1068 _CUDA_VSTD::forward_as_tuple(_CUDA_VSTD::forward<_Args>(__args)...));1069 }1070 1071 template <class... _Args>1072 _LIBCUDACXX_INLINE_VISIBILITY1073 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)1074 {1075#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1076 _LIBCUDACXX_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,1077 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"1078 " referring to this unordered_map");1079#else1080 ((void)__h);1081#endif1082 return try_emplace(__k, _CUDA_VSTD::forward<_Args>(__args)...).first;1083 }1084 1085 template <class... _Args>1086 _LIBCUDACXX_INLINE_VISIBILITY1087 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)1088 {1089#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1090 _LIBCUDACXX_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,1091 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"1092 " referring to this unordered_map");1093#else1094 ((void)__h);1095#endif1096 return try_emplace(_CUDA_VSTD::move(__k), _CUDA_VSTD::forward<_Args>(__args)...).first;1097 }1098 1099 template <class _Vp>1100 _LIBCUDACXX_INLINE_VISIBILITY1101 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)1102 {1103 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,1104 __k, _CUDA_VSTD::forward<_Vp>(__v));1105 if (!__res.second) {1106 __res.first->second = _CUDA_VSTD::forward<_Vp>(__v);1107 }1108 return __res;1109 }1110 1111 template <class _Vp>1112 _LIBCUDACXX_INLINE_VISIBILITY1113 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)1114 {1115 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,1116 _CUDA_VSTD::move(__k), _CUDA_VSTD::forward<_Vp>(__v));1117 if (!__res.second) {1118 __res.first->second = _CUDA_VSTD::forward<_Vp>(__v);1119 }1120 return __res;1121 }1122 1123 template <class _Vp>1124 _LIBCUDACXX_INLINE_VISIBILITY1125 iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v)1126 {1127 // FIXME: Add debug mode checking for the iterator input1128 return insert_or_assign(__k, _CUDA_VSTD::forward<_Vp>(__v)).first;1129 }1130 1131 template <class _Vp>1132 _LIBCUDACXX_INLINE_VISIBILITY1133 iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v)1134 {1135 // FIXME: Add debug mode checking for the iterator input1136 return insert_or_assign(_CUDA_VSTD::move(__k), _CUDA_VSTD::forward<_Vp>(__v)).first;1137 }1138#endif // _LIBCUDACXX_STD_VER > 141139 1140 _LIBCUDACXX_INLINE_VISIBILITY1141 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}1142 _LIBCUDACXX_INLINE_VISIBILITY1143 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}1144 _LIBCUDACXX_INLINE_VISIBILITY1145 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}1146 _LIBCUDACXX_INLINE_VISIBILITY1147 iterator erase(const_iterator __first, const_iterator __last)1148 {return __table_.erase(__first.__i_, __last.__i_);}1149 _LIBCUDACXX_INLINE_VISIBILITY1150 void clear() noexcept {__table_.clear();}1151 1152#if _LIBCUDACXX_STD_VER > 141153 _LIBCUDACXX_INLINE_VISIBILITY1154 insert_return_type insert(node_type&& __nh)1155 {1156 _LIBCUDACXX_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),1157 "node_type with incompatible allocator passed to unordered_map::insert()");1158 return __table_.template __node_handle_insert_unique<1159 node_type, insert_return_type>(_CUDA_VSTD::move(__nh));1160 }1161 _LIBCUDACXX_INLINE_VISIBILITY1162 iterator insert(const_iterator __hint, node_type&& __nh)1163 {1164 _LIBCUDACXX_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),1165 "node_type with incompatible allocator passed to unordered_map::insert()");1166 return __table_.template __node_handle_insert_unique<node_type>(1167 __hint.__i_, _CUDA_VSTD::move(__nh));1168 }1169 _LIBCUDACXX_INLINE_VISIBILITY1170 node_type extract(key_type const& __key)1171 {1172 return __table_.template __node_handle_extract<node_type>(__key);1173 }1174 _LIBCUDACXX_INLINE_VISIBILITY1175 node_type extract(const_iterator __it)1176 {1177 return __table_.template __node_handle_extract<node_type>(1178 __it.__i_);1179 }1180 1181 template <class _H2, class _P2>1182 _LIBCUDACXX_INLINE_VISIBILITY1183 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source)1184 {1185 _LIBCUDACXX_ASSERT(__source.get_allocator() == get_allocator(),1186 "merging container with incompatible allocator");1187 return __table_.__node_handle_merge_unique(__source.__table_);1188 }1189 template <class _H2, class _P2>1190 _LIBCUDACXX_INLINE_VISIBILITY1191 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)1192 {1193 _LIBCUDACXX_ASSERT(__source.get_allocator() == get_allocator(),1194 "merging container with incompatible allocator");1195 return __table_.__node_handle_merge_unique(__source.__table_);1196 }1197 template <class _H2, class _P2>1198 _LIBCUDACXX_INLINE_VISIBILITY1199 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source)1200 {