codekingpro/portable-devtools
114k
1// -*- C++ -*-2//===-------------------------- algorithm ---------------------------------===//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_ALGORITHM11#define _LIBCUDACXX_ALGORITHM12 13/*14 algorithm synopsis15 16#include <initializer_list>17 18namespace std19{20 21template <class InputIterator, class Predicate>22 constexpr bool // constexpr in C++2023 all_of(InputIterator first, InputIterator last, Predicate pred);24 25template <class InputIterator, class Predicate>26 constexpr bool // constexpr in C++2027 any_of(InputIterator first, InputIterator last, Predicate pred);28 29template <class InputIterator, class Predicate>30 constexpr bool // constexpr in C++2031 none_of(InputIterator first, InputIterator last, Predicate pred);32 33template <class InputIterator, class Function>34 constexpr Function // constexpr in C++2035 for_each(InputIterator first, InputIterator last, Function f);36 37template<class InputIterator, class Size, class Function>38 constexpr InputIterator // constexpr in C++2039 for_each_n(InputIterator first, Size n, Function f); // C++1740 41template <class InputIterator, class T>42 constexpr InputIterator // constexpr in C++2043 find(InputIterator first, InputIterator last, const T& value);44 45template <class InputIterator, class Predicate>46 constexpr InputIterator // constexpr in C++2047 find_if(InputIterator first, InputIterator last, Predicate pred);48 49template<class InputIterator, class Predicate>50 InputIterator // constexpr in C++2051 find_if_not(InputIterator first, InputIterator last, Predicate pred);52 53template <class ForwardIterator1, class ForwardIterator2>54 ForwardIterator1 // constexpr in C++2055 find_end(ForwardIterator1 first1, ForwardIterator1 last1,56 ForwardIterator2 first2, ForwardIterator2 last2);57 58template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>59 ForwardIterator1 // constexpr in C++2060 find_end(ForwardIterator1 first1, ForwardIterator1 last1,61 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);62 63template <class ForwardIterator1, class ForwardIterator2>64 constexpr ForwardIterator1 // constexpr in C++2065 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,66 ForwardIterator2 first2, ForwardIterator2 last2);67 68template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>69 constexpr ForwardIterator1 // constexpr in C++2070 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,71 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);72 73template <class ForwardIterator>74 constexpr ForwardIterator // constexpr in C++2075 adjacent_find(ForwardIterator first, ForwardIterator last);76 77template <class ForwardIterator, class BinaryPredicate>78 constexpr ForwardIterator // constexpr in C++2079 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);80 81template <class InputIterator, class T>82 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++2083 count(InputIterator first, InputIterator last, const T& value);84 85template <class InputIterator, class Predicate>86 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++2087 count_if(InputIterator first, InputIterator last, Predicate pred);88 89template <class InputIterator1, class InputIterator2>90 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++2091 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);92 93template <class InputIterator1, class InputIterator2>94 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++2095 mismatch(InputIterator1 first1, InputIterator1 last1,96 InputIterator2 first2, InputIterator2 last2); // **C++14**97 98template <class InputIterator1, class InputIterator2, class BinaryPredicate>99 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20100 mismatch(InputIterator1 first1, InputIterator1 last1,101 InputIterator2 first2, BinaryPredicate pred);102 103template <class InputIterator1, class InputIterator2, class BinaryPredicate>104 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20105 mismatch(InputIterator1 first1, InputIterator1 last1,106 InputIterator2 first2, InputIterator2 last2,107 BinaryPredicate pred); // **C++14**108 109template <class InputIterator1, class InputIterator2>110 constexpr bool // constexpr in C++20111 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);112 113template <class InputIterator1, class InputIterator2>114 constexpr bool // constexpr in C++20115 equal(InputIterator1 first1, InputIterator1 last1,116 InputIterator2 first2, InputIterator2 last2); // **C++14**117 118template <class InputIterator1, class InputIterator2, class BinaryPredicate>119 constexpr bool // constexpr in C++20120 equal(InputIterator1 first1, InputIterator1 last1,121 InputIterator2 first2, BinaryPredicate pred);122 123template <class InputIterator1, class InputIterator2, class BinaryPredicate>124 constexpr bool // constexpr in C++20125 equal(InputIterator1 first1, InputIterator1 last1,126 InputIterator2 first2, InputIterator2 last2,127 BinaryPredicate pred); // **C++14**128 129template<class ForwardIterator1, class ForwardIterator2>130 constexpr bool // constexpr in C++20131 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,132 ForwardIterator2 first2);133 134template<class ForwardIterator1, class ForwardIterator2>135 constexpr bool // constexpr in C++20136 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,137 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**138 139template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>140 constexpr bool // constexpr in C++20141 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,142 ForwardIterator2 first2, BinaryPredicate pred);143 144template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>145 constexpr bool // constexpr in C++20146 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,147 ForwardIterator2 first2, ForwardIterator2 last2,148 BinaryPredicate pred); // **C++14**149 150template <class ForwardIterator1, class ForwardIterator2>151 constexpr ForwardIterator1 // constexpr in C++20152 search(ForwardIterator1 first1, ForwardIterator1 last1,153 ForwardIterator2 first2, ForwardIterator2 last2);154 155template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>156 constexpr ForwardIterator1 // constexpr in C++20157 search(ForwardIterator1 first1, ForwardIterator1 last1,158 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);159 160template <class ForwardIterator, class Size, class T>161 constexpr ForwardIterator // constexpr in C++20162 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);163 164template <class ForwardIterator, class Size, class T, class BinaryPredicate>165 constexpr ForwardIterator // constexpr in C++20166 search_n(ForwardIterator first, ForwardIterator last,167 Size count, const T& value, BinaryPredicate pred);168 169template <class InputIterator, class OutputIterator>170 OutputIterator171 copy(InputIterator first, InputIterator last, OutputIterator result);172 173template<class InputIterator, class OutputIterator, class Predicate>174 OutputIterator175 copy_if(InputIterator first, InputIterator last,176 OutputIterator result, Predicate pred);177 178template<class InputIterator, class Size, class OutputIterator>179 OutputIterator180 copy_n(InputIterator first, Size n, OutputIterator result);181 182template <class BidirectionalIterator1, class BidirectionalIterator2>183 BidirectionalIterator2184 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,185 BidirectionalIterator2 result);186 187template <class ForwardIterator1, class ForwardIterator2>188 ForwardIterator2189 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);190 191template <class ForwardIterator1, class ForwardIterator2>192 void193 iter_swap(ForwardIterator1 a, ForwardIterator2 b);194 195template <class InputIterator, class OutputIterator, class UnaryOperation>196 constexpr OutputIterator // constexpr in C++20197 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);198 199template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>200 constexpr OutputIterator // constexpr in C++20201 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,202 OutputIterator result, BinaryOperation binary_op);203 204template <class ForwardIterator, class T>205 constexpr void // constexpr in C++20206 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);207 208template <class ForwardIterator, class Predicate, class T>209 constexpr void // constexpr in C++20210 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);211 212template <class InputIterator, class OutputIterator, class T>213 constexpr OutputIterator // constexpr in C++20214 replace_copy(InputIterator first, InputIterator last, OutputIterator result,215 const T& old_value, const T& new_value);216 217template <class InputIterator, class OutputIterator, class Predicate, class T>218 constexpr OutputIterator // constexpr in C++20219 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);220 221template <class ForwardIterator, class T>222 constexpr void // constexpr in C++20223 fill(ForwardIterator first, ForwardIterator last, const T& value);224 225template <class OutputIterator, class Size, class T>226 constexpr OutputIterator // constexpr in C++20227 fill_n(OutputIterator first, Size n, const T& value);228 229template <class ForwardIterator, class Generator>230 constexpr void // constexpr in C++20231 generate(ForwardIterator first, ForwardIterator last, Generator gen);232 233template <class OutputIterator, class Size, class Generator>234 constexpr OutputIterator // constexpr in C++20235 generate_n(OutputIterator first, Size n, Generator gen);236 237template <class ForwardIterator, class T>238 constexpr ForwardIterator // constexpr in C++20239 remove(ForwardIterator first, ForwardIterator last, const T& value);240 241template <class ForwardIterator, class Predicate>242 constexpr ForwardIterator // constexpr in C++20243 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);244 245template <class InputIterator, class OutputIterator, class T>246 constexpr OutputIterator // constexpr in C++20247 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);248 249template <class InputIterator, class OutputIterator, class Predicate>250 constexpr OutputIterator // constexpr in C++20251 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);252 253template <class ForwardIterator>254 ForwardIterator255 unique(ForwardIterator first, ForwardIterator last);256 257template <class ForwardIterator, class BinaryPredicate>258 ForwardIterator259 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);260 261template <class InputIterator, class OutputIterator>262 OutputIterator263 unique_copy(InputIterator first, InputIterator last, OutputIterator result);264 265template <class InputIterator, class OutputIterator, class BinaryPredicate>266 OutputIterator267 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);268 269template <class BidirectionalIterator>270 void271 reverse(BidirectionalIterator first, BidirectionalIterator last);272 273template <class BidirectionalIterator, class OutputIterator>274 constexpr OutputIterator // constexpr in C++20275 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);276 277template <class ForwardIterator>278 ForwardIterator279 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);280 281template <class ForwardIterator, class OutputIterator>282 OutputIterator283 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);284 285template <class RandomAccessIterator>286 void287 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17288 289template <class RandomAccessIterator, class RandomNumberGenerator>290 void291 random_shuffle(RandomAccessIterator first, RandomAccessIterator last,292 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17293 294template<class PopulationIterator, class SampleIterator,295 class Distance, class UniformRandomBitGenerator>296 SampleIterator sample(PopulationIterator first, PopulationIterator last,297 SampleIterator out, Distance n,298 UniformRandomBitGenerator&& g); // C++17299 300template<class RandomAccessIterator, class UniformRandomNumberGenerator>301 void shuffle(RandomAccessIterator first, RandomAccessIterator last,302 UniformRandomNumberGenerator&& g);303 304template <class InputIterator, class Predicate>305 constexpr bool // constexpr in C++20306 is_partitioned(InputIterator first, InputIterator last, Predicate pred);307 308template <class ForwardIterator, class Predicate>309 ForwardIterator310 partition(ForwardIterator first, ForwardIterator last, Predicate pred);311 312template <class InputIterator, class OutputIterator1,313 class OutputIterator2, class Predicate>314 constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20315 partition_copy(InputIterator first, InputIterator last,316 OutputIterator1 out_true, OutputIterator2 out_false,317 Predicate pred);318 319template <class ForwardIterator, class Predicate>320 ForwardIterator321 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);322 323template<class ForwardIterator, class Predicate>324 constexpr ForwardIterator // constexpr in C++20325 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);326 327template <class ForwardIterator>328 constexpr bool // constexpr in C++20329 is_sorted(ForwardIterator first, ForwardIterator last);330 331template <class ForwardIterator, class Compare>332 bool333 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);334 335template<class ForwardIterator>336 constexpr ForwardIterator // constexpr in C++20337 is_sorted_until(ForwardIterator first, ForwardIterator last);338 339template <class ForwardIterator, class Compare>340 constexpr ForwardIterator // constexpr in C++20341 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);342 343template <class RandomAccessIterator>344 void345 sort(RandomAccessIterator first, RandomAccessIterator last);346 347template <class RandomAccessIterator, class Compare>348 void349 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);350 351template <class RandomAccessIterator>352 void353 stable_sort(RandomAccessIterator first, RandomAccessIterator last);354 355template <class RandomAccessIterator, class Compare>356 void357 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);358 359template <class RandomAccessIterator>360 void361 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);362 363template <class RandomAccessIterator, class Compare>364 void365 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);366 367template <class InputIterator, class RandomAccessIterator>368 RandomAccessIterator369 partial_sort_copy(InputIterator first, InputIterator last,370 RandomAccessIterator result_first, RandomAccessIterator result_last);371 372template <class InputIterator, class RandomAccessIterator, class Compare>373 RandomAccessIterator374 partial_sort_copy(InputIterator first, InputIterator last,375 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);376 377template <class RandomAccessIterator>378 void379 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);380 381template <class RandomAccessIterator, class Compare>382 void383 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);384 385template <class ForwardIterator, class T>386 constexpr ForwardIterator // constexpr in C++20387 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);388 389template <class ForwardIterator, class T, class Compare>390 constexpr ForwardIterator // constexpr in C++20391 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);392 393template <class ForwardIterator, class T>394 constexpr ForwardIterator // constexpr in C++20395 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);396 397template <class ForwardIterator, class T, class Compare>398 constexpr ForwardIterator // constexpr in C++20399 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);400 401template <class ForwardIterator, class T>402 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20403 equal_range(ForwardIterator first, ForwardIterator last, const T& value);404 405template <class ForwardIterator, class T, class Compare>406 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20407 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);408 409template <class ForwardIterator, class T>410 constexpr bool // constexpr in C++20411 binary_search(ForwardIterator first, ForwardIterator last, const T& value);412 413template <class ForwardIterator, class T, class Compare>414 constexpr bool // constexpr in C++20415 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);416 417template <class InputIterator1, class InputIterator2, class OutputIterator>418 OutputIterator419 merge(InputIterator1 first1, InputIterator1 last1,420 InputIterator2 first2, InputIterator2 last2, OutputIterator result);421 422template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>423 OutputIterator424 merge(InputIterator1 first1, InputIterator1 last1,425 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);426 427template <class BidirectionalIterator>428 void429 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);430 431template <class BidirectionalIterator, class Compare>432 void433 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);434 435template <class InputIterator1, class InputIterator2>436 constexpr bool // constexpr in C++20437 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);438 439template <class InputIterator1, class InputIterator2, class Compare>440 constexpr bool // constexpr in C++20441 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);442 443template <class InputIterator1, class InputIterator2, class OutputIterator>444 OutputIterator445 set_union(InputIterator1 first1, InputIterator1 last1,446 InputIterator2 first2, InputIterator2 last2, OutputIterator result);447 448template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>449 OutputIterator450 set_union(InputIterator1 first1, InputIterator1 last1,451 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);452 453template <class InputIterator1, class InputIterator2, class OutputIterator>454 constexpr OutputIterator // constexpr in C++20455 set_intersection(InputIterator1 first1, InputIterator1 last1,456 InputIterator2 first2, InputIterator2 last2, OutputIterator result);457 458template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>459 constexpr OutputIterator // constexpr in C++20460 set_intersection(InputIterator1 first1, InputIterator1 last1,461 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);462 463template <class InputIterator1, class InputIterator2, class OutputIterator>464 OutputIterator465 set_difference(InputIterator1 first1, InputIterator1 last1,466 InputIterator2 first2, InputIterator2 last2, OutputIterator result);467 468template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>469 OutputIterator470 set_difference(InputIterator1 first1, InputIterator1 last1,471 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);472 473template <class InputIterator1, class InputIterator2, class OutputIterator>474 OutputIterator475 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,476 InputIterator2 first2, InputIterator2 last2, OutputIterator result);477 478template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>479 OutputIterator480 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,481 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);482 483template <class RandomAccessIterator>484 void485 push_heap(RandomAccessIterator first, RandomAccessIterator last);486 487template <class RandomAccessIterator, class Compare>488 void489 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);490 491template <class RandomAccessIterator>492 void493 pop_heap(RandomAccessIterator first, RandomAccessIterator last);494 495template <class RandomAccessIterator, class Compare>496 void497 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);498 499template <class RandomAccessIterator>500 void501 make_heap(RandomAccessIterator first, RandomAccessIterator last);502 503template <class RandomAccessIterator, class Compare>504 void505 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);506 507template <class RandomAccessIterator>508 void509 sort_heap(RandomAccessIterator first, RandomAccessIterator last);510 511template <class RandomAccessIterator, class Compare>512 void513 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);514 515template <class RandomAccessIterator>516 constexpr bool // constexpr in C++20517 is_heap(RandomAccessIterator first, RandomAccessiterator last);518 519template <class RandomAccessIterator, class Compare>520 constexpr bool // constexpr in C++20521 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);522 523template <class RandomAccessIterator>524 constexpr RandomAccessIterator // constexpr in C++20525 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);526 527template <class RandomAccessIterator, class Compare>528 constexpr RandomAccessIterator // constexpr in C++20529 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);530 531template <class ForwardIterator>532 ForwardIterator533 min_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14534 535template <class ForwardIterator, class Compare>536 ForwardIterator537 min_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14538 539template <class T>540 const T&541 min(const T& a, const T& b); // constexpr in C++14542 543template <class T, class Compare>544 const T&545 min(const T& a, const T& b, Compare comp); // constexpr in C++14546 547template<class T>548 T549 min(::std::initializer_list<T> t); // constexpr in C++14550 551template<class T, class Compare>552 T553 min(::std::initializer_list<T> t, Compare comp); // constexpr in C++14554 555template<class T>556 constexpr const T& clamp( const T& v, const T& lo, const T& hi ); // C++17557 558template<class T, class Compare>559 constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp ); // C++17560 561template <class ForwardIterator>562 ForwardIterator563 max_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14564 565template <class ForwardIterator, class Compare>566 ForwardIterator567 max_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14568 569template <class T>570 const T&571 max(const T& a, const T& b); // constexpr in C++14572 573template <class T, class Compare>574 const T&575 max(const T& a, const T& b, Compare comp); // constexpr in C++14576 577template<class T>578 T579 max(::std::initializer_list<T> t); // constexpr in C++14580 581template<class T, class Compare>582 T583 max(::std::initializer_list<T> t, Compare comp); // constexpr in C++14584 585template<class ForwardIterator>586 pair<ForwardIterator, ForwardIterator>587 minmax_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14588 589template<class ForwardIterator, class Compare>590 pair<ForwardIterator, ForwardIterator>591 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14592 593template<class T>594 pair<const T&, const T&>595 minmax(const T& a, const T& b); // constexpr in C++14596 597template<class T, class Compare>598 pair<const T&, const T&>599 minmax(const T& a, const T& b, Compare comp); // constexpr in C++14600 601template<class T>602 pair<T, T>603 minmax(::std::initializer_list<T> t); // constexpr in C++14604 605template<class T, class Compare>606 pair<T, T>607 minmax(::std::initializer_list<T> t, Compare comp); // constexpr in C++14608 609template <class InputIterator1, class InputIterator2>610 constexpr bool // constexpr in C++20611 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);612 613template <class InputIterator1, class InputIterator2, class Compare>614 constexpr bool // constexpr in C++20615 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,616 InputIterator2 first2, InputIterator2 last2, Compare comp);617 618template <class BidirectionalIterator>619 bool620 next_permutation(BidirectionalIterator first, BidirectionalIterator last);621 622template <class BidirectionalIterator, class Compare>623 bool624 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);625 626template <class BidirectionalIterator>627 bool628 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);629 630template <class BidirectionalIterator, class Compare>631 bool632 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);633 634} // std635 636*/637#ifndef __cuda_std__638#include <__config>639#include <cstring>640#include <memory>641#endif // __cuda_std__642 643#include "__algorithm/swap_ranges.h"644#include "__assert" // all public C++ headers provide the assertion handler645#include "__debug"646#include "__iterator/distance.h"647#include "__iterator/iterator_traits.h"648#include "__iterator/move_iterator.h"649#include "__iterator/next.h"650#include "__iterator/prev.h"651#include "__iterator/reverse_iterator.h"652#include "__iterator/wrap_iter.h"653#include "__type_traits/common_type.h"654#include "__type_traits/enable_if.h"655#include "__type_traits/is_integral.h"656#include "__type_traits/is_same.h"657#include "__type_traits/is_trivially_copy_assignable.h"658#include "__type_traits/make_unsigned.h"659#include "__type_traits/remove_const.h"660#include "bit"661#include "cstddef"662#include "functional"663#include "initializer_list"664#include "type_traits"665#include "version"666 667#ifndef __cuda_std__668#include <__pragma_push>669#endif // __cuda_std__670 671#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)672# pragma GCC system_header673#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)674# pragma clang system_header675#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)676# pragma system_header677#endif // no system header678 679_LIBCUDACXX_BEGIN_NAMESPACE_STD680 681// I'd like to replace these with _CUDA_VSTD::equal_to<void>, but can't because:682// * That only works with C++14 and later, and683// * We haven't included <functional> here.684template <class _T1, class _T2 = _T1>685struct __equal_to686{687 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}688 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}689 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}690 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}691};692 693template <class _T1>694struct __equal_to<_T1, _T1>695{696 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11697 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}698};699 700template <class _T1>701struct __equal_to<const _T1, _T1>702{703 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11704 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}705};706 707template <class _T1>708struct __equal_to<_T1, const _T1>709{710 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11711 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}712};713 714template <class _T1, class _T2 = _T1>715struct __less716{717 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11718 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}719 720 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11721 bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}722 723 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11724 bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}725 726 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11727 bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}728};729 730template <class _T1>731struct __less<_T1, _T1>732{733 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11734 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}735};736 737template <class _T1>738struct __less<const _T1, _T1>739{740 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11741 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}742};743 744template <class _T1>745struct __less<_T1, const _T1>746{747 _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX11748 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}749};750 751#ifndef __cuda_std__752 753template <class _Predicate>754class __invert // invert the sense of a comparison755{756private:757 _Predicate __p_;758public:759 _LIBCUDACXX_INLINE_VISIBILITY __invert() {}760 761 _LIBCUDACXX_INLINE_VISIBILITY762 explicit __invert(_Predicate __p) : __p_(__p) {}763 764 template <class _T1>765 _LIBCUDACXX_INLINE_VISIBILITY766 bool operator()(const _T1& __x) {return !__p_(__x);}767 768 template <class _T1, class _T2>769 _LIBCUDACXX_INLINE_VISIBILITY770 bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}771};772 773// Perform division by two quickly for positive integers (llvm.org/PR39129)774 775template <typename _Integral>776_LIBCUDACXX_INLINE_VISIBILITY constexpr777__enable_if_t778<779 is_integral<_Integral>::value,780 _Integral781>782__half_positive(_Integral __value)783{784 return static_cast<_Integral>(static_cast<__make_unsigned_t<_Integral>>(__value) / 2);785}786 787template <typename _Tp>788_LIBCUDACXX_INLINE_VISIBILITY constexpr789__enable_if_t790<791 !is_integral<_Tp>::value,792 _Tp793>794__half_positive(_Tp __value)795{796 return __value / 2;797}798 799#ifdef _LIBCUDACXX_DEBUG800 801template <class _Compare>802struct __debug_less803{804 _Compare &__comp_;805 _LIBCUDACXX_CONSTEXPR_AFTER_CXX17806 __debug_less(_Compare& __c) : __comp_(__c) {}807 808 template <class _Tp, class _Up>809 _LIBCUDACXX_CONSTEXPR_AFTER_CXX17810 bool operator()(const _Tp& __x, const _Up& __y)811 {812 bool __r = __comp_(__x, __y);813 if (__r)814 __do_compare_assert(0, __y, __x);815 return __r;816 }817 818 template <class _Tp, class _Up>819 _LIBCUDACXX_CONSTEXPR_AFTER_CXX17820 bool operator()(_Tp& __x, _Up& __y)821 {822 bool __r = __comp_(__x, __y);823 if (__r)824 __do_compare_assert(0, __y, __x);825 return __r;826 }827 828 template <class _LHS, class _RHS>829 _LIBCUDACXX_CONSTEXPR_AFTER_CXX17830 inline _LIBCUDACXX_INLINE_VISIBILITY831 decltype((void)_CUDA_VSTD::declval<_Compare&>()(832 _CUDA_VSTD::declval<_LHS &>(), _CUDA_VSTD::declval<_RHS &>()))833 __do_compare_assert(int, _LHS & __l, _RHS & __r) {834 _LIBCUDACXX_ASSERT(!__comp_(__l, __r),835 "Comparator does not induce a strict weak ordering");836 }837 838 template <class _LHS, class _RHS>839 _LIBCUDACXX_CONSTEXPR_AFTER_CXX17840 inline _LIBCUDACXX_INLINE_VISIBILITY841 void __do_compare_assert(long, _LHS &, _RHS &) {}842};843 844#endif // _LIBCUDACXX_DEBUG845 846#endif // __cuda_std__847 848template <class _Comp>849struct __comp_ref_type {850 // Pass the comparator by lvalue reference. Or in debug mode, using a851 // debugging wrapper that stores a reference.852#ifndef _LIBCUDACXX_DEBUG853 typedef __add_lvalue_reference_t<_Comp> type;854#else855 typedef __debug_less<_Comp> type;856#endif857};858 859#ifndef __cuda_std__860// all_of861 862template <class _InputIterator, class _Predicate>863_LIBCUDACXX_NODISCARD_EXT inline864_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX17865bool866all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)867{868 for (; __first != __last; ++__first)869 if (!__pred(*__first))870 return false;871 return true;872}873 874// any_of875 876template <class _InputIterator, class _Predicate>877_LIBCUDACXX_NODISCARD_EXT inline878_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX17879bool880any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)881{882 for (; __first != __last; ++__first)883 if (__pred(*__first))884 return true;885 return false;886}887 888// none_of889 890template <class _InputIterator, class _Predicate>891_LIBCUDACXX_NODISCARD_EXT inline892_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX17893bool894none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)895{896 for (; __first != __last; ++__first)897 if (__pred(*__first))898 return false;899 return true;900}901 902// for_each903 904template <class _InputIterator, class _Function>905inline _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX17906_Function907for_each(_InputIterator __first, _InputIterator __last, _Function __f)908{909 for (; __first != __last; ++__first)910 __f(*__first);911 return __f;912}913 914#if _LIBCUDACXX_STD_VER > 14915// for_each_n916 917template <class _InputIterator, class _Size, class _Function>918inline _LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX17919_InputIterator920for_each_n(_InputIterator __first, _Size __orig_n, _Function __f)921{922 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;923 _IntegralSize __n = __orig_n;924 while (__n > 0)925 {926 __f(*__first);927 ++__first;928 --__n;929 }930 return __first;931}932#endif933 934// find935 936template <class _InputIterator, class _Tp>937_LIBCUDACXX_NODISCARD_EXT inline938_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX17939_InputIterator940find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)941{942 for (; __first != __last; ++__first)943 if (*__first == __value_)944 break;945 return __first;946}947 948// find_if949 950template <class _InputIterator, class _Predicate>951_LIBCUDACXX_NODISCARD_EXT inline952_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX17953_InputIterator954find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)955{956 for (; __first != __last; ++__first)957 if (__pred(*__first))958 break;959 return __first;960}961 962// find_if_not963 964template<class _InputIterator, class _Predicate>965_LIBCUDACXX_NODISCARD_EXT inline966_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX17967_InputIterator968find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)969{970 for (; __first != __last; ++__first)971 if (!__pred(*__first))972 break;973 return __first;974}975 976// find_end977 978template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>979_LIBCUDACXX_INLINE_VISIBILITY980_LIBCUDACXX_CONSTEXPR_AFTER_CXX17 _ForwardIterator1981__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,982 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,983 forward_iterator_tag, forward_iterator_tag)984{985 // modeled after search algorithm986 _ForwardIterator1 __r = __last1; // __last1 is the "default" answer987 if (__first2 == __last2)988 return __r;989 while (true)990 {991 while (true)992 {993 if (__first1 == __last1) // if source exhausted return last correct answer994 return __r; // (or __last1 if never found)995 if (__pred(*__first1, *__first2))996 break;997 ++__first1;998 }999 // *__first1 matches *__first2, now match elements after here1000 _ForwardIterator1 __m1 = __first1;1001 _ForwardIterator2 __m2 = __first2;1002 while (true)1003 {1004 if (++__m2 == __last2)1005 { // Pattern exhaused, record answer and search for another one1006 __r = __first1;1007 ++__first1;1008 break;1009 }1010 if (++__m1 == __last1) // Source exhausted, return last answer1011 return __r;1012 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first1013 {1014 ++__first1;1015 break;1016 } // else there is a match, check next elements1017 }1018 }1019}1020 1021template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>1022_LIBCUDACXX_INLINE_VISIBILITY1023_LIBCUDACXX_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator11024__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,1025 _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,1026 bidirectional_iterator_tag, bidirectional_iterator_tag)1027{1028 // modeled after search algorithm (in reverse)1029 if (__first2 == __last2)1030 return __last1; // Everything matches an empty sequence1031 _BidirectionalIterator1 __l1 = __last1;1032 _BidirectionalIterator2 __l2 = __last2;1033 --__l2;1034 while (true)1035 {1036 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks1037 while (true)1038 {1039 if (__first1 == __l1) // return __last1 if no element matches *__first21040 return __last1;1041 if (__pred(*--__l1, *__l2))1042 break;1043 }1044 // *__l1 matches *__l2, now match elements before here1045 _BidirectionalIterator1 __m1 = __l1;1046 _BidirectionalIterator2 __m2 = __l2;1047 while (true)1048 {1049 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)1050 return __m1;1051 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found1052 return __last1;1053 if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l11054 {1055 break;1056 } // else there is a match, check next elements1057 }1058 }1059}1060 1061template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>1062_LIBCUDACXX_INLINE_VISIBILITY1063_LIBCUDACXX_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator11064__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,1065 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,1066 random_access_iterator_tag, random_access_iterator_tag)1067{1068 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern1069 typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;1070 if (__len2 == 0)1071 return __last1;1072 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;1073 if (__len1 < __len2)1074 return __last1;1075 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here1076 _RandomAccessIterator1 __l1 = __last1;1077 _RandomAccessIterator2 __l2 = __last2;1078 --__l2;1079 while (true)1080 {1081 while (true)1082 {1083 if (__s == __l1)1084 return __last1;1085 if (__pred(*--__l1, *__l2))1086 break;1087 }1088 _RandomAccessIterator1 __m1 = __l1;1089 _RandomAccessIterator2 __m2 = __l2;1090 while (true)1091 {1092 if (__m2 == __first2)1093 return __m1;1094 // no need to check range on __m1 because __s guarantees we have enough source1095 if (!__pred(*--__m1, *--__m2))1096 {1097 break;1098 }1099 }1100 }1101}1102 1103template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>1104_LIBCUDACXX_NODISCARD_EXT inline1105_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX171106_ForwardIterator11107find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,1108 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)1109{1110 return _CUDA_VSTD::__find_end<__add_lvalue_reference_t<_BinaryPredicate>>1111 (__first1, __last1, __first2, __last2, __pred,1112 typename iterator_traits<_ForwardIterator1>::iterator_category(),1113 typename iterator_traits<_ForwardIterator2>::iterator_category());1114}1115 1116template <class _ForwardIterator1, class _ForwardIterator2>1117_LIBCUDACXX_NODISCARD_EXT inline1118_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX171119_ForwardIterator11120find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,1121 _ForwardIterator2 __first2, _ForwardIterator2 __last2)1122{1123 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;1124 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;1125 return _CUDA_VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());1126}1127 1128// find_first_of1129 1130template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>1131_LIBCUDACXX_INLINE_VISIBILITY1132_LIBCUDACXX_CONSTEXPR_AFTER_CXX11 _ForwardIterator11133__find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1,1134 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)1135{1136 for (; __first1 != __last1; ++__first1)1137 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)1138 if (__pred(*__first1, *__j))1139 return __first1;1140 return __last1;1141}1142 1143 1144template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>1145_LIBCUDACXX_NODISCARD_EXT inline1146_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX171147_ForwardIterator11148find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,1149 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)1150{1151 return _CUDA_VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);1152}1153 1154template <class _ForwardIterator1, class _ForwardIterator2>1155_LIBCUDACXX_NODISCARD_EXT inline1156_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX171157_ForwardIterator11158find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,1159 _ForwardIterator2 __first2, _ForwardIterator2 __last2)1160{1161 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;1162 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;1163 return _CUDA_VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());1164}1165 1166// adjacent_find1167 1168template <class _ForwardIterator, class _BinaryPredicate>1169_LIBCUDACXX_NODISCARD_EXT inline1170_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX171171_ForwardIterator1172adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)1173{1174 if (__first != __last)1175 {1176 _ForwardIterator __i = __first;1177 while (++__i != __last)1178 {1179 if (__pred(*__first, *__i))1180 return __first;1181 __first = __i;1182 }1183 }1184 return __last;1185}1186 1187template <class _ForwardIterator>1188_LIBCUDACXX_NODISCARD_EXT inline1189_LIBCUDACXX_INLINE_VISIBILITY _LIBCUDACXX_CONSTEXPR_AFTER_CXX171190_ForwardIterator1191adjacent_find(_ForwardIterator __first, _ForwardIterator __last)1192{1193 typedef typename iterator_traits<_ForwardIterator>::value_type __v;1194 return _CUDA_VSTD::adjacent_find(__first, __last, __equal_to<__v>());1195}1196 1197// count1198 1199template <class _InputIterator, class _Tp>1200_LIBCUDACXX_NODISCARD_EXT inline