codekingpro/portable-devtools
114k
1// -*- C++ -*-2//===----------------------------- 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_MAP11#define _LIBCUDACXX_MAP12 13/*14 15 map synopsis16 17namespace std18{19 20template <class Key, class T, class Compare = less<Key>,21 class Allocator = allocator<pair<const Key, T>>>22class map23{24public:25 // types:26 typedef Key key_type;27 typedef T mapped_type;28 typedef pair<const key_type, mapped_type> value_type;29 typedef Compare key_compare;30 typedef Allocator allocator_type;31 typedef typename allocator_type::reference reference;32 typedef typename allocator_type::const_reference const_reference;33 typedef typename allocator_type::pointer pointer;34 typedef typename allocator_type::const_pointer const_pointer;35 typedef typename allocator_type::size_type size_type;36 typedef typename allocator_type::difference_type difference_type;37 38 typedef implementation-defined iterator;39 typedef implementation-defined const_iterator;40 typedef std::reverse_iterator<iterator> reverse_iterator;41 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;42 typedef unspecified node_type; // C++1743 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++1744 45 class value_compare46 : public __binary_function<value_type, value_type, bool>47 {48 friend class map;49 protected:50 key_compare comp;51 52 value_compare(key_compare c);53 public:54 bool operator()(const value_type& x, const value_type& y) const;55 };56 57 // construct/copy/destroy:58 map()59 noexcept(60 is_nothrow_default_constructible<allocator_type>::value &&61 is_nothrow_default_constructible<key_compare>::value &&62 is_nothrow_copy_constructible<key_compare>::value);63 explicit map(const key_compare& comp);64 map(const key_compare& comp, const allocator_type& a);65 template <class InputIterator>66 map(InputIterator first, InputIterator last,67 const key_compare& comp = key_compare());68 template <class InputIterator>69 map(InputIterator first, InputIterator last,70 const key_compare& comp, const allocator_type& a);71 map(const map& m);72 map(map&& m)73 noexcept(74 is_nothrow_move_constructible<allocator_type>::value &&75 is_nothrow_move_constructible<key_compare>::value);76 explicit map(const allocator_type& a);77 map(const map& m, const allocator_type& a);78 map(map&& m, const allocator_type& a);79 map(initializer_list<value_type> il, const key_compare& comp = key_compare());80 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);81 template <class InputIterator>82 map(InputIterator first, InputIterator last, const allocator_type& a)83 : map(first, last, Compare(), a) {} // C++1484 map(initializer_list<value_type> il, const allocator_type& a)85 : map(il, Compare(), a) {} // C++1486 ~map();87 88 map& operator=(const map& m);89 map& operator=(map&& m)90 noexcept(91 allocator_type::propagate_on_container_move_assignment::value &&92 is_nothrow_move_assignable<allocator_type>::value &&93 is_nothrow_move_assignable<key_compare>::value);94 map& operator=(initializer_list<value_type> il);95 96 // iterators:97 iterator begin() noexcept;98 const_iterator begin() const noexcept;99 iterator end() noexcept;100 const_iterator end() const noexcept;101 102 reverse_iterator rbegin() noexcept;103 const_reverse_iterator rbegin() const noexcept;104 reverse_iterator rend() noexcept;105 const_reverse_iterator rend() const noexcept;106 107 const_iterator cbegin() const noexcept;108 const_iterator cend() const noexcept;109 const_reverse_iterator crbegin() const noexcept;110 const_reverse_iterator crend() const noexcept;111 112 // capacity:113 bool empty() const noexcept;114 size_type size() const noexcept;115 size_type max_size() const noexcept;116 117 // element access:118 mapped_type& operator[](const key_type& k);119 mapped_type& operator[](key_type&& k);120 121 mapped_type& at(const key_type& k);122 const mapped_type& at(const key_type& k) const;123 124 // modifiers:125 template <class... Args>126 pair<iterator, bool> emplace(Args&&... args);127 template <class... Args>128 iterator emplace_hint(const_iterator position, Args&&... args);129 pair<iterator, bool> insert(const value_type& v);130 pair<iterator, bool> insert( value_type&& v); // C++17131 template <class P>132 pair<iterator, bool> insert(P&& p);133 iterator insert(const_iterator position, const value_type& v);134 iterator insert(const_iterator position, value_type&& v); // C++17135 template <class P>136 iterator insert(const_iterator position, P&& p);137 template <class InputIterator>138 void insert(InputIterator first, InputIterator last);139 void insert(initializer_list<value_type> il);140 141 node_type extract(const_iterator position); // C++17142 node_type extract(const key_type& x); // C++17143 insert_return_type insert(node_type&& nh); // C++17144 iterator insert(const_iterator hint, node_type&& nh); // C++17145 146 template <class... Args>147 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17148 template <class... Args>149 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17150 template <class... Args>151 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17152 template <class... Args>153 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17154 template <class M>155 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17156 template <class M>157 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17158 template <class M>159 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17160 template <class M>161 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17162 163 iterator erase(const_iterator position);164 iterator erase(iterator position); // C++14165 size_type erase(const key_type& k);166 iterator erase(const_iterator first, const_iterator last);167 void clear() noexcept;168 169 template<class C2>170 void merge(map<Key, T, C2, Allocator>& source); // C++17171 template<class C2>172 void merge(map<Key, T, C2, Allocator>&& source); // C++17173 template<class C2>174 void merge(multimap<Key, T, C2, Allocator>& source); // C++17175 template<class C2>176 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17177 178 void swap(map& m)179 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&180 is_nothrow_swappable<key_compare>::value); // C++17181 182 // observers:183 allocator_type get_allocator() const noexcept;184 key_compare key_comp() const;185 value_compare value_comp() const;186 187 // map operations:188 iterator find(const key_type& k);189 const_iterator find(const key_type& k) const;190 template<typename K>191 iterator find(const K& x); // C++14192 template<typename K>193 const_iterator find(const K& x) const; // C++14194 template<typename K>195 size_type count(const K& x) const; // C++14196 size_type count(const key_type& k) const;197 bool contains(const key_type& x) const; // C++20198 iterator lower_bound(const key_type& k);199 const_iterator lower_bound(const key_type& k) const;200 template<typename K>201 iterator lower_bound(const K& x); // C++14202 template<typename K>203 const_iterator lower_bound(const K& x) const; // C++14204 205 iterator upper_bound(const key_type& k);206 const_iterator upper_bound(const key_type& k) const;207 template<typename K>208 iterator upper_bound(const K& x); // C++14209 template<typename K>210 const_iterator upper_bound(const K& x) const; // C++14211 212 pair<iterator,iterator> equal_range(const key_type& k);213 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;214 template<typename K>215 pair<iterator,iterator> equal_range(const K& x); // C++14216 template<typename K>217 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14218};219 220template <class Key, class T, class Compare, class Allocator>221bool222operator==(const map<Key, T, Compare, Allocator>& x,223 const map<Key, T, Compare, Allocator>& y);224 225template <class Key, class T, class Compare, class Allocator>226bool227operator< (const map<Key, T, Compare, Allocator>& x,228 const map<Key, T, Compare, Allocator>& y);229 230template <class Key, class T, class Compare, class Allocator>231bool232operator!=(const map<Key, T, Compare, Allocator>& x,233 const map<Key, T, Compare, Allocator>& y);234 235template <class Key, class T, class Compare, class Allocator>236bool237operator> (const map<Key, T, Compare, Allocator>& x,238 const map<Key, T, Compare, Allocator>& y);239 240template <class Key, class T, class Compare, class Allocator>241bool242operator>=(const map<Key, T, Compare, Allocator>& x,243 const map<Key, T, Compare, Allocator>& y);244 245template <class Key, class T, class Compare, class Allocator>246bool247operator<=(const map<Key, T, Compare, Allocator>& x,248 const map<Key, T, Compare, Allocator>& y);249 250// specialized algorithms:251template <class Key, class T, class Compare, class Allocator>252void253swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)254 noexcept(noexcept(x.swap(y)));255 256template <class Key, class T, class Compare, class Allocator, class Predicate>257 void erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20258 259 260template <class Key, class T, class Compare = less<Key>,261 class Allocator = allocator<pair<const Key, T>>>262class multimap263{264public:265 // types:266 typedef Key key_type;267 typedef T mapped_type;268 typedef pair<const key_type,mapped_type> value_type;269 typedef Compare key_compare;270 typedef Allocator allocator_type;271 typedef typename allocator_type::reference reference;272 typedef typename allocator_type::const_reference const_reference;273 typedef typename allocator_type::size_type size_type;274 typedef typename allocator_type::difference_type difference_type;275 typedef typename allocator_type::pointer pointer;276 typedef typename allocator_type::const_pointer const_pointer;277 278 typedef implementation-defined iterator;279 typedef implementation-defined const_iterator;280 typedef std::reverse_iterator<iterator> reverse_iterator;281 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;282 typedef unspecified node_type; // C++17283 284 class value_compare285 : public __binary_function<value_type,value_type,bool>286 {287 friend class multimap;288 protected:289 key_compare comp;290 value_compare(key_compare c);291 public:292 bool operator()(const value_type& x, const value_type& y) const;293 };294 295 // construct/copy/destroy:296 multimap()297 noexcept(298 is_nothrow_default_constructible<allocator_type>::value &&299 is_nothrow_default_constructible<key_compare>::value &&300 is_nothrow_copy_constructible<key_compare>::value);301 explicit multimap(const key_compare& comp);302 multimap(const key_compare& comp, const allocator_type& a);303 template <class InputIterator>304 multimap(InputIterator first, InputIterator last, const key_compare& comp);305 template <class InputIterator>306 multimap(InputIterator first, InputIterator last, const key_compare& comp,307 const allocator_type& a);308 multimap(const multimap& m);309 multimap(multimap&& m)310 noexcept(311 is_nothrow_move_constructible<allocator_type>::value &&312 is_nothrow_move_constructible<key_compare>::value);313 explicit multimap(const allocator_type& a);314 multimap(const multimap& m, const allocator_type& a);315 multimap(multimap&& m, const allocator_type& a);316 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());317 multimap(initializer_list<value_type> il, const key_compare& comp,318 const allocator_type& a);319 template <class InputIterator>320 multimap(InputIterator first, InputIterator last, const allocator_type& a)321 : multimap(first, last, Compare(), a) {} // C++14322 multimap(initializer_list<value_type> il, const allocator_type& a)323 : multimap(il, Compare(), a) {} // C++14324 ~multimap();325 326 multimap& operator=(const multimap& m);327 multimap& operator=(multimap&& m)328 noexcept(329 allocator_type::propagate_on_container_move_assignment::value &&330 is_nothrow_move_assignable<allocator_type>::value &&331 is_nothrow_move_assignable<key_compare>::value);332 multimap& operator=(initializer_list<value_type> il);333 334 // iterators:335 iterator begin() noexcept;336 const_iterator begin() const noexcept;337 iterator end() noexcept;338 const_iterator end() const noexcept;339 340 reverse_iterator rbegin() noexcept;341 const_reverse_iterator rbegin() const noexcept;342 reverse_iterator rend() noexcept;343 const_reverse_iterator rend() const noexcept;344 345 const_iterator cbegin() const noexcept;346 const_iterator cend() const noexcept;347 const_reverse_iterator crbegin() const noexcept;348 const_reverse_iterator crend() const noexcept;349 350 // capacity:351 bool empty() const noexcept;352 size_type size() const noexcept;353 size_type max_size() const noexcept;354 355 // modifiers:356 template <class... Args>357 iterator emplace(Args&&... args);358 template <class... Args>359 iterator emplace_hint(const_iterator position, Args&&... args);360 iterator insert(const value_type& v);361 iterator insert( value_type&& v); // C++17362 template <class P>363 iterator insert(P&& p);364 iterator insert(const_iterator position, const value_type& v);365 iterator insert(const_iterator position, value_type&& v); // C++17366 template <class P>367 iterator insert(const_iterator position, P&& p);368 template <class InputIterator>369 void insert(InputIterator first, InputIterator last);370 void insert(initializer_list<value_type> il);371 372 node_type extract(const_iterator position); // C++17373 node_type extract(const key_type& x); // C++17374 iterator insert(node_type&& nh); // C++17375 iterator insert(const_iterator hint, node_type&& nh); // C++17376 377 iterator erase(const_iterator position);378 iterator erase(iterator position); // C++14379 size_type erase(const key_type& k);380 iterator erase(const_iterator first, const_iterator last);381 void clear() noexcept;382 383 template<class C2>384 void merge(multimap<Key, T, C2, Allocator>& source); // C++17385 template<class C2>386 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17387 template<class C2>388 void merge(map<Key, T, C2, Allocator>& source); // C++17389 template<class C2>390 void merge(map<Key, T, C2, Allocator>&& source); // C++17391 392 void swap(multimap& m)393 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&394 is_nothrow_swappable<key_compare>::value); // C++17395 396 // observers:397 allocator_type get_allocator() const noexcept;398 key_compare key_comp() const;399 value_compare value_comp() const;400 401 // map operations:402 iterator find(const key_type& k);403 const_iterator find(const key_type& k) const;404 template<typename K>405 iterator find(const K& x); // C++14406 template<typename K>407 const_iterator find(const K& x) const; // C++14408 template<typename K>409 size_type count(const K& x) const; // C++14410 size_type count(const key_type& k) const;411 bool contains(const key_type& x) const; // C++20412 iterator lower_bound(const key_type& k);413 const_iterator lower_bound(const key_type& k) const;414 template<typename K>415 iterator lower_bound(const K& x); // C++14416 template<typename K>417 const_iterator lower_bound(const K& x) const; // C++14418 419 iterator upper_bound(const key_type& k);420 const_iterator upper_bound(const key_type& k) const;421 template<typename K>422 iterator upper_bound(const K& x); // C++14423 template<typename K>424 const_iterator upper_bound(const K& x) const; // C++14425 426 pair<iterator,iterator> equal_range(const key_type& k);427 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;428 template<typename K>429 pair<iterator,iterator> equal_range(const K& x); // C++14430 template<typename K>431 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14432};433 434template <class Key, class T, class Compare, class Allocator>435bool436operator==(const multimap<Key, T, Compare, Allocator>& x,437 const multimap<Key, T, Compare, Allocator>& y);438 439template <class Key, class T, class Compare, class Allocator>440bool441operator< (const multimap<Key, T, Compare, Allocator>& x,442 const multimap<Key, T, Compare, Allocator>& y);443 444template <class Key, class T, class Compare, class Allocator>445bool446operator!=(const multimap<Key, T, Compare, Allocator>& x,447 const multimap<Key, T, Compare, Allocator>& y);448 449template <class Key, class T, class Compare, class Allocator>450bool451operator> (const multimap<Key, T, Compare, Allocator>& x,452 const multimap<Key, T, Compare, Allocator>& y);453 454template <class Key, class T, class Compare, class Allocator>455bool456operator>=(const multimap<Key, T, Compare, Allocator>& x,457 const multimap<Key, T, Compare, Allocator>& y);458 459template <class Key, class T, class Compare, class Allocator>460bool461operator<=(const multimap<Key, T, Compare, Allocator>& x,462 const multimap<Key, T, Compare, Allocator>& y);463 464// specialized algorithms:465template <class Key, class T, class Compare, class Allocator>466void467swap(multimap<Key, T, Compare, Allocator>& x,468 multimap<Key, T, Compare, Allocator>& y)469 noexcept(noexcept(x.swap(y)));470 471template <class Key, class T, class Compare, class Allocator, class Predicate>472 void erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20473 474} // std475 476*/477 478#include <__config>479#include <__tree>480#include <__node_handle>481#include <iterator>482#include <memory>483#include <utility>484#include <functional>485#include <initializer_list>486#include <type_traits>487#include <version>488 489#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)490# pragma GCC system_header491#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)492# pragma clang system_header493#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)494# pragma system_header495#endif // no system header496 497_LIBCUDACXX_BEGIN_NAMESPACE_STD498 499template <class _Key, class _CP, class _Compare,500 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>501class __map_value_compare502 : private _Compare503{504public:505 _LIBCUDACXX_INLINE_VISIBILITY506 __map_value_compare()507 noexcept(is_nothrow_default_constructible<_Compare>::value)508 : _Compare() {}509 _LIBCUDACXX_INLINE_VISIBILITY510 __map_value_compare(_Compare c)511 noexcept(is_nothrow_copy_constructible<_Compare>::value)512 : _Compare(c) {}513 _LIBCUDACXX_INLINE_VISIBILITY514 const _Compare& key_comp() const noexcept {return *this;}515 _LIBCUDACXX_INLINE_VISIBILITY516 bool operator()(const _CP& __x, const _CP& __y) const517 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);}518 _LIBCUDACXX_INLINE_VISIBILITY519 bool operator()(const _CP& __x, const _Key& __y) const520 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);}521 _LIBCUDACXX_INLINE_VISIBILITY522 bool operator()(const _Key& __x, const _CP& __y) const523 {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);}524 void swap(__map_value_compare&__y)525 noexcept(__is_nothrow_swappable<_Compare>::value)526 {527 using _CUDA_VSTD::swap;528 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));529 }530 531#if _LIBCUDACXX_STD_VER > 11532 template <typename _K2>533 _LIBCUDACXX_INLINE_VISIBILITY534 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type535 operator () ( const _K2& __x, const _CP& __y ) const536 {return static_cast<const _Compare&>(*this) (__x, __y.__get_value().first);}537 538 template <typename _K2>539 _LIBCUDACXX_INLINE_VISIBILITY540 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type541 operator () (const _CP& __x, const _K2& __y) const542 {return static_cast<const _Compare&>(*this) (__x.__get_value().first, __y);}543#endif544};545 546template <class _Key, class _CP, class _Compare>547class __map_value_compare<_Key, _CP, _Compare, false>548{549 _Compare comp;550 551public:552 _LIBCUDACXX_INLINE_VISIBILITY553 __map_value_compare()554 noexcept(is_nothrow_default_constructible<_Compare>::value)555 : comp() {}556 _LIBCUDACXX_INLINE_VISIBILITY557 __map_value_compare(_Compare c)558 noexcept(is_nothrow_copy_constructible<_Compare>::value)559 : comp(c) {}560 _LIBCUDACXX_INLINE_VISIBILITY561 const _Compare& key_comp() const noexcept {return comp;}562 563 _LIBCUDACXX_INLINE_VISIBILITY564 bool operator()(const _CP& __x, const _CP& __y) const565 {return comp(__x.__get_value().first, __y.__get_value().first);}566 _LIBCUDACXX_INLINE_VISIBILITY567 bool operator()(const _CP& __x, const _Key& __y) const568 {return comp(__x.__get_value().first, __y);}569 _LIBCUDACXX_INLINE_VISIBILITY570 bool operator()(const _Key& __x, const _CP& __y) const571 {return comp(__x, __y.__get_value().first);}572 void swap(__map_value_compare&__y)573 noexcept(__is_nothrow_swappable<_Compare>::value)574 {575 using _CUDA_VSTD::swap;576 swap(comp, __y.comp);577 }578 579#if _LIBCUDACXX_STD_VER > 11580 template <typename _K2>581 _LIBCUDACXX_INLINE_VISIBILITY582 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type583 operator () ( const _K2& __x, const _CP& __y ) const584 {return comp (__x, __y.__get_value().first);}585 586 template <typename _K2>587 _LIBCUDACXX_INLINE_VISIBILITY588 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type589 operator () (const _CP& __x, const _K2& __y) const590 {return comp (__x.__get_value().first, __y);}591#endif592};593 594template <class _Key, class _CP, class _Compare, bool __b>595inline _LIBCUDACXX_INLINE_VISIBILITY596void597swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,598 __map_value_compare<_Key, _CP, _Compare, __b>& __y)599 noexcept(noexcept(__x.swap(__y)))600{601 __x.swap(__y);602}603 604template <class _Allocator>605class __map_node_destructor606{607 typedef _Allocator allocator_type;608 typedef allocator_traits<allocator_type> __alloc_traits;609 610public:611 typedef typename __alloc_traits::pointer pointer;612 613private:614 allocator_type& __na_;615 616 __map_node_destructor& operator=(const __map_node_destructor&);617 618public:619 bool __first_constructed;620 bool __second_constructed;621 622 _LIBCUDACXX_INLINE_VISIBILITY623 explicit __map_node_destructor(allocator_type& __na) noexcept624 : __na_(__na),625 __first_constructed(false),626 __second_constructed(false)627 {}628 629 _LIBCUDACXX_INLINE_VISIBILITY630 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) noexcept631 : __na_(__x.__na_),632 __first_constructed(__x.__value_constructed),633 __second_constructed(__x.__value_constructed)634 {635 __x.__value_constructed = false;636 }637 638 _LIBCUDACXX_INLINE_VISIBILITY639 void operator()(pointer __p) noexcept640 {641 if (__second_constructed)642 __alloc_traits::destroy(__na_, _CUDA_VSTD::addressof(__p->__value_.__get_value().second));643 if (__first_constructed)644 __alloc_traits::destroy(__na_, _CUDA_VSTD::addressof(__p->__value_.__get_value().first));645 if (__p)646 __alloc_traits::deallocate(__na_, __p, 1);647 }648};649 650template <class _Key, class _Tp, class _Compare, class _Allocator>651 class map;652template <class _Key, class _Tp, class _Compare, class _Allocator>653 class multimap;654template <class _TreeIterator> class __map_const_iterator;655 656template <class _Key, class _Tp>657struct __value_type658{659 typedef _Key key_type;660 typedef _Tp mapped_type;661 typedef pair<const key_type, mapped_type> value_type;662 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;663 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;664 665private:666 value_type __cc;667 668public:669 _LIBCUDACXX_INLINE_VISIBILITY670 value_type& __get_value()671 {672#if _LIBCUDACXX_STD_VER > 14673 return *_CUDA_VSTD::launder(_CUDA_VSTD::addressof(__cc));674#else675 return __cc;676#endif677 }678 679 _LIBCUDACXX_INLINE_VISIBILITY680 const value_type& __get_value() const681 {682#if _LIBCUDACXX_STD_VER > 14683 return *_CUDA_VSTD::launder(_CUDA_VSTD::addressof(__cc));684#else685 return __cc;686#endif687 }688 689 _LIBCUDACXX_INLINE_VISIBILITY690 __nc_ref_pair_type __ref()691 {692 value_type& __v = __get_value();693 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);694 }695 696 _LIBCUDACXX_INLINE_VISIBILITY697 __nc_rref_pair_type __move()698 {699 value_type& __v = __get_value();700 return __nc_rref_pair_type(701 _CUDA_VSTD::move(const_cast<key_type&>(__v.first)),702 _CUDA_VSTD::move(__v.second));703 }704 705 _LIBCUDACXX_INLINE_VISIBILITY706 __value_type& operator=(const __value_type& __v)707 {708 __ref() = __v.__get_value();709 return *this;710 }711 712 _LIBCUDACXX_INLINE_VISIBILITY713 __value_type& operator=(__value_type&& __v)714 {715 __ref() = __v.__move();716 return *this;717 }718 719 template <class _ValueTp,720 class = typename enable_if<721 __is_same_uncvref<_ValueTp, value_type>::value722 >::type723 >724 _LIBCUDACXX_INLINE_VISIBILITY725 __value_type& operator=(_ValueTp&& __v)726 {727 __ref() = _CUDA_VSTD::forward<_ValueTp>(__v);728 return *this;729 }730 731private:732 __value_type() = delete;733 ~__value_type() = delete;734 __value_type(const __value_type& __v) = delete;735 __value_type(__value_type&& __v) = delete;736};737 738#else739 740template <class _Key, class _Tp>741struct __value_type742{743 typedef _Key key_type;744 typedef _Tp mapped_type;745 typedef pair<const key_type, mapped_type> value_type;746 747private:748 value_type __cc;749 750public:751 _LIBCUDACXX_INLINE_VISIBILITY752 value_type& __get_value() { return __cc; }753 _LIBCUDACXX_INLINE_VISIBILITY754 const value_type& __get_value() const { return __cc; }755 756private:757 __value_type();758 __value_type(__value_type const&);759 __value_type& operator=(__value_type const&);760 ~__value_type();761};762 763template <class _Tp>764struct __extract_key_value_types;765 766template <class _Key, class _Tp>767struct __extract_key_value_types<__value_type<_Key, _Tp> >768{769 typedef _Key const __key_type;770 typedef _Tp __mapped_type;771};772 773template <class _TreeIterator>774class _LIBCUDACXX_TEMPLATE_VIS __map_iterator775{776 typedef typename _TreeIterator::_NodeTypes _NodeTypes;777 typedef typename _TreeIterator::__pointer_traits __pointer_traits;778 779 _TreeIterator __i_;780 781public:782 typedef bidirectional_iterator_tag iterator_category;783 typedef typename _NodeTypes::__map_value_type value_type;784 typedef typename _TreeIterator::difference_type difference_type;785 typedef value_type& reference;786 typedef typename _NodeTypes::__map_value_type_pointer pointer;787 788 _LIBCUDACXX_INLINE_VISIBILITY789 __map_iterator() noexcept {}790 791 _LIBCUDACXX_INLINE_VISIBILITY792 __map_iterator(_TreeIterator __i) noexcept : __i_(__i) {}793 794 _LIBCUDACXX_INLINE_VISIBILITY795 reference operator*() const {return __i_->__get_value();}796 _LIBCUDACXX_INLINE_VISIBILITY797 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}798 799 _LIBCUDACXX_INLINE_VISIBILITY800 __map_iterator& operator++() {++__i_; return *this;}801 _LIBCUDACXX_INLINE_VISIBILITY802 __map_iterator operator++(int)803 {804 __map_iterator __t(*this);805 ++(*this);806 return __t;807 }808 809 _LIBCUDACXX_INLINE_VISIBILITY810 __map_iterator& operator--() {--__i_; return *this;}811 _LIBCUDACXX_INLINE_VISIBILITY812 __map_iterator operator--(int)813 {814 __map_iterator __t(*this);815 --(*this);816 return __t;817 }818 819 friend _LIBCUDACXX_INLINE_VISIBILITY820 bool operator==(const __map_iterator& __x, const __map_iterator& __y)821 {return __x.__i_ == __y.__i_;}822 friend823 _LIBCUDACXX_INLINE_VISIBILITY824 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)825 {return __x.__i_ != __y.__i_;}826 827 template <class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS map;828 template <class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS multimap;829 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __map_const_iterator;830};831 832template <class _TreeIterator>833class _LIBCUDACXX_TEMPLATE_VIS __map_const_iterator834{835 typedef typename _TreeIterator::_NodeTypes _NodeTypes;836 typedef typename _TreeIterator::__pointer_traits __pointer_traits;837 838 _TreeIterator __i_;839 840public:841 typedef bidirectional_iterator_tag iterator_category;842 typedef typename _NodeTypes::__map_value_type value_type;843 typedef typename _TreeIterator::difference_type difference_type;844 typedef const value_type& reference;845 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;846 847 _LIBCUDACXX_INLINE_VISIBILITY848 __map_const_iterator() noexcept {}849 850 _LIBCUDACXX_INLINE_VISIBILITY851 __map_const_iterator(_TreeIterator __i) noexcept : __i_(__i) {}852 _LIBCUDACXX_INLINE_VISIBILITY853 __map_const_iterator(__map_iterator<854 typename _TreeIterator::__non_const_iterator> __i) noexcept855 : __i_(__i.__i_) {}856 857 _LIBCUDACXX_INLINE_VISIBILITY858 reference operator*() const {return __i_->__get_value();}859 _LIBCUDACXX_INLINE_VISIBILITY860 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}861 862 _LIBCUDACXX_INLINE_VISIBILITY863 __map_const_iterator& operator++() {++__i_; return *this;}864 _LIBCUDACXX_INLINE_VISIBILITY865 __map_const_iterator operator++(int)866 {867 __map_const_iterator __t(*this);868 ++(*this);869 return __t;870 }871 872 _LIBCUDACXX_INLINE_VISIBILITY873 __map_const_iterator& operator--() {--__i_; return *this;}874 _LIBCUDACXX_INLINE_VISIBILITY875 __map_const_iterator operator--(int)876 {877 __map_const_iterator __t(*this);878 --(*this);879 return __t;880 }881 882 friend _LIBCUDACXX_INLINE_VISIBILITY883 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)884 {return __x.__i_ == __y.__i_;}885 friend _LIBCUDACXX_INLINE_VISIBILITY886 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)887 {return __x.__i_ != __y.__i_;}888 889 template <class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS map;890 template <class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS multimap;891 template <class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS __tree_const_iterator;892};893 894template <class _Key, class _Tp, class _Compare = less<_Key>,895 class _Allocator = allocator<pair<const _Key, _Tp> > >896class _LIBCUDACXX_TEMPLATE_VIS map897{898public:899 // types:900 typedef _Key key_type;901 typedef _Tp mapped_type;902 typedef pair<const key_type, mapped_type> value_type;903 typedef __type_identity_t<_Compare> key_compare;904 typedef __type_identity_t<_Allocator> allocator_type;905 typedef value_type& reference;906 typedef const value_type& const_reference;907 908 static_assert((is_same<typename allocator_type::value_type, value_type>::value),909 "Allocator::value_type must be same type as value_type");910 911 class _LIBCUDACXX_TEMPLATE_VIS value_compare912 : public __binary_function<value_type, value_type, bool>913 {914 friend class map;915 protected:916 key_compare comp;917 918 _LIBCUDACXX_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}919 public:920 _LIBCUDACXX_INLINE_VISIBILITY921 bool operator()(const value_type& __x, const value_type& __y) const922 {return comp(__x.first, __y.first);}923 };924 925private:926 927 typedef _CUDA_VSTD::__value_type<key_type, mapped_type> __value_type;928 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;929 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,930 __value_type>::type __allocator_type;931 typedef __tree<__value_type, __vc, __allocator_type> __base;932 typedef typename __base::__node_traits __node_traits;933 typedef allocator_traits<allocator_type> __alloc_traits;934 935 __base __tree_;936 937public:938 typedef typename __alloc_traits::pointer pointer;939 typedef typename __alloc_traits::const_pointer const_pointer;940 typedef typename __alloc_traits::size_type size_type;941 typedef typename __alloc_traits::difference_type difference_type;942 typedef __map_iterator<typename __base::iterator> iterator;943 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;944 typedef _CUDA_VSTD::reverse_iterator<iterator> reverse_iterator;945 typedef _CUDA_VSTD::reverse_iterator<const_iterator> const_reverse_iterator;946 947#if _LIBCUDACXX_STD_VER > 14948 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;949 typedef __insert_return_type<iterator, node_type> insert_return_type;950#endif951 952 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>953 friend class _LIBCUDACXX_TEMPLATE_VIS map;954 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>955 friend class _LIBCUDACXX_TEMPLATE_VIS multimap;956 957 _LIBCUDACXX_INLINE_VISIBILITY958 map()959 noexcept(960 is_nothrow_default_constructible<allocator_type>::value &&961 is_nothrow_default_constructible<key_compare>::value &&962 is_nothrow_copy_constructible<key_compare>::value)963 : __tree_(__vc(key_compare())) {}964 965 _LIBCUDACXX_INLINE_VISIBILITY966 explicit map(const key_compare& __comp)967 noexcept(968 is_nothrow_default_constructible<allocator_type>::value &&969 is_nothrow_copy_constructible<key_compare>::value)970 : __tree_(__vc(__comp)) {}971 972 _LIBCUDACXX_INLINE_VISIBILITY973 explicit map(const key_compare& __comp, const allocator_type& __a)974 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}975 976 template <class _InputIterator>977 _LIBCUDACXX_INLINE_VISIBILITY978 map(_InputIterator __f, _InputIterator __l,979 const key_compare& __comp = key_compare())980 : __tree_(__vc(__comp))981 {982 insert(__f, __l);983 }984 985 template <class _InputIterator>986 _LIBCUDACXX_INLINE_VISIBILITY987 map(_InputIterator __f, _InputIterator __l,988 const key_compare& __comp, const allocator_type& __a)989 : __tree_(__vc(__comp), typename __base::allocator_type(__a))990 {991 insert(__f, __l);992 }993 994#if _LIBCUDACXX_STD_VER > 11995 template <class _InputIterator>996 _LIBCUDACXX_INLINE_VISIBILITY997 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)998 : map(__f, __l, key_compare(), __a) {}999#endif1000 1001 _LIBCUDACXX_INLINE_VISIBILITY1002 map(const map& __m)1003 : __tree_(__m.__tree_)1004 {1005 insert(__m.begin(), __m.end());1006 }1007 1008 _LIBCUDACXX_INLINE_VISIBILITY1009 map& operator=(const map& __m)1010 {1011 __tree_ = __m.__tree_;1012 return *this;1013 }1014 1015 _LIBCUDACXX_INLINE_VISIBILITY1016 map(map&& __m)1017 noexcept(is_nothrow_move_constructible<__base>::value)1018 : __tree_(_CUDA_VSTD::move(__m.__tree_))1019 {1020 }1021 1022 map(map&& __m, const allocator_type& __a);1023 1024 _LIBCUDACXX_INLINE_VISIBILITY1025 map& operator=(map&& __m)1026 noexcept(is_nothrow_move_assignable<__base>::value)1027 {1028 __tree_ = _CUDA_VSTD::move(__m.__tree_);1029 return *this;1030 }1031 1032 _LIBCUDACXX_INLINE_VISIBILITY1033 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())1034 : __tree_(__vc(__comp))1035 {1036 insert(__il.begin(), __il.end());1037 }1038 1039 _LIBCUDACXX_INLINE_VISIBILITY1040 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)1041 : __tree_(__vc(__comp), typename __base::allocator_type(__a))1042 {1043 insert(__il.begin(), __il.end());1044 }1045 1046#if _LIBCUDACXX_STD_VER > 111047 _LIBCUDACXX_INLINE_VISIBILITY1048 map(initializer_list<value_type> __il, const allocator_type& __a)1049 : map(__il, key_compare(), __a) {}1050#endif1051 1052 _LIBCUDACXX_INLINE_VISIBILITY1053 map& operator=(initializer_list<value_type> __il)1054 {1055 __tree_.__assign_unique(__il.begin(), __il.end());1056 return *this;1057 }1058 1059 _LIBCUDACXX_INLINE_VISIBILITY1060 explicit map(const allocator_type& __a)1061 : __tree_(typename __base::allocator_type(__a))1062 {1063 }1064 1065 _LIBCUDACXX_INLINE_VISIBILITY1066 map(const map& __m, const allocator_type& __a)1067 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))1068 {1069 insert(__m.begin(), __m.end());1070 }1071 1072 _LIBCUDACXX_INLINE_VISIBILITY1073 ~map() {1074 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");1075 }1076 1077 _LIBCUDACXX_INLINE_VISIBILITY1078 iterator begin() noexcept {return __tree_.begin();}1079 _LIBCUDACXX_INLINE_VISIBILITY1080 const_iterator begin() const noexcept {return __tree_.begin();}1081 _LIBCUDACXX_INLINE_VISIBILITY1082 iterator end() noexcept {return __tree_.end();}1083 _LIBCUDACXX_INLINE_VISIBILITY1084 const_iterator end() const noexcept {return __tree_.end();}1085 1086 _LIBCUDACXX_INLINE_VISIBILITY1087 reverse_iterator rbegin() noexcept {return reverse_iterator(end());}1088 _LIBCUDACXX_INLINE_VISIBILITY1089 const_reverse_iterator rbegin() const noexcept1090 {return const_reverse_iterator(end());}1091 _LIBCUDACXX_INLINE_VISIBILITY1092 reverse_iterator rend() noexcept1093 {return reverse_iterator(begin());}1094 _LIBCUDACXX_INLINE_VISIBILITY1095 const_reverse_iterator rend() const noexcept1096 {return const_reverse_iterator(begin());}1097 1098 _LIBCUDACXX_INLINE_VISIBILITY1099 const_iterator cbegin() const noexcept {return begin();}1100 _LIBCUDACXX_INLINE_VISIBILITY1101 const_iterator cend() const noexcept {return end();}1102 _LIBCUDACXX_INLINE_VISIBILITY1103 const_reverse_iterator crbegin() const noexcept {return rbegin();}1104 _LIBCUDACXX_INLINE_VISIBILITY1105 const_reverse_iterator crend() const noexcept {return rend();}1106 1107 _LIBCUDACXX_NODISCARD_AFTER_CXX17 _LIBCUDACXX_INLINE_VISIBILITY1108 bool empty() const noexcept {return __tree_.size() == 0;}1109 _LIBCUDACXX_INLINE_VISIBILITY1110 size_type size() const noexcept {return __tree_.size();}1111 _LIBCUDACXX_INLINE_VISIBILITY1112 size_type max_size() const noexcept {return __tree_.max_size();}1113 1114 mapped_type& operator[](const key_type& __k);1115 mapped_type& operator[](key_type&& __k);1116 1117 mapped_type& at(const key_type& __k);1118 const mapped_type& at(const key_type& __k) const;1119 1120 _LIBCUDACXX_INLINE_VISIBILITY1121 allocator_type get_allocator() const noexcept {return allocator_type(__tree_.__alloc());}1122 _LIBCUDACXX_INLINE_VISIBILITY1123 key_compare key_comp() const {return __tree_.value_comp().key_comp();}1124 _LIBCUDACXX_INLINE_VISIBILITY1125 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}1126 1127 template <class ..._Args>1128 _LIBCUDACXX_INLINE_VISIBILITY1129 pair<iterator, bool> emplace(_Args&& ...__args) {1130 return __tree_.__emplace_unique(_CUDA_VSTD::forward<_Args>(__args)...);1131 }1132 1133 template <class ..._Args>1134 _LIBCUDACXX_INLINE_VISIBILITY1135 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {1136 return __tree_.__emplace_hint_unique(__p.__i_, _CUDA_VSTD::forward<_Args>(__args)...);1137 }1138 1139 template <class _Pp,1140 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>1141 _LIBCUDACXX_INLINE_VISIBILITY1142 pair<iterator, bool> insert(_Pp&& __p)1143 {return __tree_.__insert_unique(_CUDA_VSTD::forward<_Pp>(__p));}1144 1145 template <class _Pp,1146 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>1147 _LIBCUDACXX_INLINE_VISIBILITY1148 iterator insert(const_iterator __pos, _Pp&& __p)1149 {return __tree_.__insert_unique(__pos.__i_, _CUDA_VSTD::forward<_Pp>(__p));}1150 1151 _LIBCUDACXX_INLINE_VISIBILITY1152 pair<iterator, bool>1153 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}1154 1155 _LIBCUDACXX_INLINE_VISIBILITY1156 iterator1157 insert(const_iterator __p, const value_type& __v)1158 {return __tree_.__insert_unique(__p.__i_, __v);}1159 1160 _LIBCUDACXX_INLINE_VISIBILITY1161 pair<iterator, bool>1162 insert(value_type&& __v) {return __tree_.__insert_unique(_CUDA_VSTD::move(__v));}1163 1164 _LIBCUDACXX_INLINE_VISIBILITY1165 iterator insert(const_iterator __p, value_type&& __v)1166 {return __tree_.__insert_unique(__p.__i_, _CUDA_VSTD::move(__v));}1167 1168 _LIBCUDACXX_INLINE_VISIBILITY1169 void insert(initializer_list<value_type> __il)1170 {insert(__il.begin(), __il.end());}1171 1172 template <class _InputIterator>1173 _LIBCUDACXX_INLINE_VISIBILITY1174 void insert(_InputIterator __f, _InputIterator __l)1175 {1176 for (const_iterator __e = cend(); __f != __l; ++__f)1177 insert(__e.__i_, *__f);1178 }1179 1180#if _LIBCUDACXX_STD_VER > 141181 1182 template <class... _Args>1183 _LIBCUDACXX_INLINE_VISIBILITY1184 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)1185 {1186 return __tree_.__emplace_unique_key_args(__k,1187 _CUDA_VSTD::piecewise_construct,1188 _CUDA_VSTD::forward_as_tuple(__k),1189 _CUDA_VSTD::forward_as_tuple(_CUDA_VSTD::forward<_Args>(__args)...));1190 }1191 1192 template <class... _Args>1193 _LIBCUDACXX_INLINE_VISIBILITY1194 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)1195 {1196 return __tree_.__emplace_unique_key_args(__k,1197 _CUDA_VSTD::piecewise_construct,1198 _CUDA_VSTD::forward_as_tuple(_CUDA_VSTD::move(__k)),1199 _CUDA_VSTD::forward_as_tuple(_CUDA_VSTD::forward<_Args>(__args)...));1200 }