| // -*- C++ -*- |
| //===-------------------------- algorithm ---------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef _LIBCPP_ALGORITHM |
| #define _LIBCPP_ALGORITHM |
| |
| /* |
| algorithm synopsis |
| |
| #include <initializer_list> |
| |
| namespace std |
| { |
| |
| template <class InputIterator, class Predicate> |
| constexpr bool // constexpr in C++20 |
| all_of(InputIterator first, InputIterator last, Predicate pred); |
| |
| template <class InputIterator, class Predicate> |
| constexpr bool // constexpr in C++20 |
| any_of(InputIterator first, InputIterator last, Predicate pred); |
| |
| template <class InputIterator, class Predicate> |
| constexpr bool // constexpr in C++20 |
| none_of(InputIterator first, InputIterator last, Predicate pred); |
| |
| template <class InputIterator, class Function> |
| constexpr Function // constexpr in C++20 |
| for_each(InputIterator first, InputIterator last, Function f); |
| |
| template<class InputIterator, class Size, class Function> |
| constexpr InputIterator // constexpr in C++20 |
| for_each_n(InputIterator first, Size n, Function f); // C++17 |
| |
| template <class InputIterator, class T> |
| constexpr InputIterator // constexpr in C++20 |
| find(InputIterator first, InputIterator last, const T& value); |
| |
| template <class InputIterator, class Predicate> |
| constexpr InputIterator // constexpr in C++20 |
| find_if(InputIterator first, InputIterator last, Predicate pred); |
| |
| template<class InputIterator, class Predicate> |
| constexpr InputIterator // constexpr in C++20 |
| find_if_not(InputIterator first, InputIterator last, Predicate pred); |
| |
| template <class ForwardIterator1, class ForwardIterator2> |
| constexpr ForwardIterator1 // constexpr in C++20 |
| find_end(ForwardIterator1 first1, ForwardIterator1 last1, |
| ForwardIterator2 first2, ForwardIterator2 last2); |
| |
| template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> |
| constexpr ForwardIterator1 // constexpr in C++20 |
| find_end(ForwardIterator1 first1, ForwardIterator1 last1, |
| ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); |
| |
| template <class ForwardIterator1, class ForwardIterator2> |
| constexpr ForwardIterator1 // constexpr in C++20 |
| find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, |
| ForwardIterator2 first2, ForwardIterator2 last2); |
| |
| template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> |
| constexpr ForwardIterator1 // constexpr in C++20 |
| find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, |
| ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); |
| |
| template <class ForwardIterator> |
| constexpr ForwardIterator // constexpr in C++20 |
| adjacent_find(ForwardIterator first, ForwardIterator last); |
| |
| template <class ForwardIterator, class BinaryPredicate> |
| constexpr ForwardIterator // constexpr in C++20 |
| adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); |
| |
| template <class InputIterator, class T> |
| constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20 |
| count(InputIterator first, InputIterator last, const T& value); |
| |
| template <class InputIterator, class Predicate> |
| constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20 |
| count_if(InputIterator first, InputIterator last, Predicate pred); |
| |
| template <class InputIterator1, class InputIterator2> |
| constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 |
| mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); |
| |
| template <class InputIterator1, class InputIterator2> |
| constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 |
| mismatch(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2); // **C++14** |
| |
| template <class InputIterator1, class InputIterator2, class BinaryPredicate> |
| constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 |
| mismatch(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, BinaryPredicate pred); |
| |
| template <class InputIterator1, class InputIterator2, class BinaryPredicate> |
| constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 |
| mismatch(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, |
| BinaryPredicate pred); // **C++14** |
| |
| template <class InputIterator1, class InputIterator2> |
| constexpr bool // constexpr in C++20 |
| equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); |
| |
| template <class InputIterator1, class InputIterator2> |
| constexpr bool // constexpr in C++20 |
| equal(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2); // **C++14** |
| |
| template <class InputIterator1, class InputIterator2, class BinaryPredicate> |
| constexpr bool // constexpr in C++20 |
| equal(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, BinaryPredicate pred); |
| |
| template <class InputIterator1, class InputIterator2, class BinaryPredicate> |
| constexpr bool // constexpr in C++20 |
| equal(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, |
| BinaryPredicate pred); // **C++14** |
| |
| template<class ForwardIterator1, class ForwardIterator2> |
| constexpr bool // constexpr in C++20 |
| is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, |
| ForwardIterator2 first2); |
| |
| template<class ForwardIterator1, class ForwardIterator2> |
| constexpr bool // constexpr in C++20 |
| is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, |
| ForwardIterator2 first2, ForwardIterator2 last2); // **C++14** |
| |
| template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> |
| constexpr bool // constexpr in C++20 |
| is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, |
| ForwardIterator2 first2, BinaryPredicate pred); |
| |
| template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> |
| constexpr bool // constexpr in C++20 |
| is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, |
| ForwardIterator2 first2, ForwardIterator2 last2, |
| BinaryPredicate pred); // **C++14** |
| |
| template <class ForwardIterator1, class ForwardIterator2> |
| constexpr ForwardIterator1 // constexpr in C++20 |
| search(ForwardIterator1 first1, ForwardIterator1 last1, |
| ForwardIterator2 first2, ForwardIterator2 last2); |
| |
| template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> |
| constexpr ForwardIterator1 // constexpr in C++20 |
| search(ForwardIterator1 first1, ForwardIterator1 last1, |
| ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); |
| |
| template <class ForwardIterator, class Size, class T> |
| constexpr ForwardIterator // constexpr in C++20 |
| search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); |
| |
| template <class ForwardIterator, class Size, class T, class BinaryPredicate> |
| constexpr ForwardIterator // constexpr in C++20 |
| search_n(ForwardIterator first, ForwardIterator last, |
| Size count, const T& value, BinaryPredicate pred); |
| |
| template <class InputIterator, class OutputIterator> |
| constexpr OutputIterator // constexpr in C++20 |
| copy(InputIterator first, InputIterator last, OutputIterator result); |
| |
| template<class InputIterator, class OutputIterator, class Predicate> |
| constexpr OutputIterator // constexpr in C++20 |
| copy_if(InputIterator first, InputIterator last, |
| OutputIterator result, Predicate pred); |
| |
| template<class InputIterator, class Size, class OutputIterator> |
| constexpr OutputIterator // constexpr in C++20 |
| copy_n(InputIterator first, Size n, OutputIterator result); |
| |
| template <class BidirectionalIterator1, class BidirectionalIterator2> |
| constexpr BidirectionalIterator2 // constexpr in C++20 |
| copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, |
| BidirectionalIterator2 result); |
| |
| template <class ForwardIterator1, class ForwardIterator2> |
| constexpr ForwardIterator2 // constexpr in C++20 |
| swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); |
| |
| template <class ForwardIterator1, class ForwardIterator2> |
| constexpr void // constexpr in C++20 |
| iter_swap(ForwardIterator1 a, ForwardIterator2 b); |
| |
| template <class InputIterator, class OutputIterator, class UnaryOperation> |
| constexpr OutputIterator // constexpr in C++20 |
| transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> |
| constexpr OutputIterator // constexpr in C++20 |
| transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, |
| OutputIterator result, BinaryOperation binary_op); |
| |
| template <class ForwardIterator, class T> |
| constexpr void // constexpr in C++20 |
| replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); |
| |
| template <class ForwardIterator, class Predicate, class T> |
| constexpr void // constexpr in C++20 |
| replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value); |
| |
| template <class InputIterator, class OutputIterator, class T> |
| constexpr OutputIterator // constexpr in C++20 |
| replace_copy(InputIterator first, InputIterator last, OutputIterator result, |
| const T& old_value, const T& new_value); |
| |
| template <class InputIterator, class OutputIterator, class Predicate, class T> |
| constexpr OutputIterator // constexpr in C++20 |
| replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value); |
| |
| template <class ForwardIterator, class T> |
| constexpr void // constexpr in C++20 |
| fill(ForwardIterator first, ForwardIterator last, const T& value); |
| |
| template <class OutputIterator, class Size, class T> |
| constexpr OutputIterator // constexpr in C++20 |
| fill_n(OutputIterator first, Size n, const T& value); |
| |
| template <class ForwardIterator, class Generator> |
| constexpr void // constexpr in C++20 |
| generate(ForwardIterator first, ForwardIterator last, Generator gen); |
| |
| template <class OutputIterator, class Size, class Generator> |
| constexpr OutputIterator // constexpr in C++20 |
| generate_n(OutputIterator first, Size n, Generator gen); |
| |
| template <class ForwardIterator, class T> |
| constexpr ForwardIterator // constexpr in C++20 |
| remove(ForwardIterator first, ForwardIterator last, const T& value); |
| |
| template <class ForwardIterator, class Predicate> |
| constexpr ForwardIterator // constexpr in C++20 |
| remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); |
| |
| template <class InputIterator, class OutputIterator, class T> |
| constexpr OutputIterator // constexpr in C++20 |
| remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value); |
| |
| template <class InputIterator, class OutputIterator, class Predicate> |
| constexpr OutputIterator // constexpr in C++20 |
| remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); |
| |
| template <class ForwardIterator> |
| constexpr ForwardIterator // constexpr in C++20 |
| unique(ForwardIterator first, ForwardIterator last); |
| |
| template <class ForwardIterator, class BinaryPredicate> |
| constexpr ForwardIterator // constexpr in C++20 |
| unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); |
| |
| template <class InputIterator, class OutputIterator> |
| constexpr OutputIterator // constexpr in C++20 |
| unique_copy(InputIterator first, InputIterator last, OutputIterator result); |
| |
| template <class InputIterator, class OutputIterator, class BinaryPredicate> |
| constexpr OutputIterator // constexpr in C++20 |
| unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); |
| |
| template <class BidirectionalIterator> |
| constexpr void // constexpr in C++20 |
| reverse(BidirectionalIterator first, BidirectionalIterator last); |
| |
| template <class BidirectionalIterator, class OutputIterator> |
| constexpr OutputIterator // constexpr in C++20 |
| reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); |
| |
| template <class ForwardIterator> |
| constexpr ForwardIterator // constexpr in C++20 |
| rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); |
| |
| template <class ForwardIterator, class OutputIterator> |
| constexpr OutputIterator // constexpr in C++20 |
| rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); |
| |
| template <class RandomAccessIterator> |
| void |
| random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17 |
| |
| template <class RandomAccessIterator, class RandomNumberGenerator> |
| void |
| random_shuffle(RandomAccessIterator first, RandomAccessIterator last, |
| RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17 |
| |
| template<class PopulationIterator, class SampleIterator, |
| class Distance, class UniformRandomBitGenerator> |
| SampleIterator sample(PopulationIterator first, PopulationIterator last, |
| SampleIterator out, Distance n, |
| UniformRandomBitGenerator&& g); // C++17 |
| |
| template<class RandomAccessIterator, class UniformRandomNumberGenerator> |
| void shuffle(RandomAccessIterator first, RandomAccessIterator last, |
| UniformRandomNumberGenerator&& g); |
| |
| template<class ForwardIterator> |
| constexpr ForwardIterator |
| shift_left(ForwardIterator first, ForwardIterator last, |
| typename iterator_traits<ForwardIterator>::difference_type n); // C++20 |
| |
| template<class ForwardIterator> |
| constexpr ForwardIterator |
| shift_right(ForwardIterator first, ForwardIterator last, |
| typename iterator_traits<ForwardIterator>::difference_type n); // C++20 |
| |
| template <class InputIterator, class Predicate> |
| constexpr bool // constexpr in C++20 |
| is_partitioned(InputIterator first, InputIterator last, Predicate pred); |
| |
| template <class ForwardIterator, class Predicate> |
| constexpr ForwardIterator // constexpr in C++20 |
| partition(ForwardIterator first, ForwardIterator last, Predicate pred); |
| |
| template <class InputIterator, class OutputIterator1, |
| class OutputIterator2, class Predicate> |
| constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20 |
| partition_copy(InputIterator first, InputIterator last, |
| OutputIterator1 out_true, OutputIterator2 out_false, |
| Predicate pred); |
| |
| template <class ForwardIterator, class Predicate> |
| ForwardIterator |
| stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred); |
| |
| template<class ForwardIterator, class Predicate> |
| constexpr ForwardIterator // constexpr in C++20 |
| partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); |
| |
| template <class ForwardIterator> |
| constexpr bool // constexpr in C++20 |
| is_sorted(ForwardIterator first, ForwardIterator last); |
| |
| template <class ForwardIterator, class Compare> |
| constexpr bool // constexpr in C++20 |
| is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); |
| |
| template<class ForwardIterator> |
| constexpr ForwardIterator // constexpr in C++20 |
| is_sorted_until(ForwardIterator first, ForwardIterator last); |
| |
| template <class ForwardIterator, class Compare> |
| constexpr ForwardIterator // constexpr in C++20 |
| is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); |
| |
| template <class RandomAccessIterator> |
| void |
| sort(RandomAccessIterator first, RandomAccessIterator last); |
| |
| template <class RandomAccessIterator, class Compare> |
| void |
| sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
| |
| template <class RandomAccessIterator> |
| void |
| stable_sort(RandomAccessIterator first, RandomAccessIterator last); |
| |
| template <class RandomAccessIterator, class Compare> |
| void |
| stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
| |
| template <class RandomAccessIterator> |
| void |
| partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); |
| |
| template <class RandomAccessIterator, class Compare> |
| void |
| partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); |
| |
| template <class InputIterator, class RandomAccessIterator> |
| RandomAccessIterator |
| partial_sort_copy(InputIterator first, InputIterator last, |
| RandomAccessIterator result_first, RandomAccessIterator result_last); |
| |
| template <class InputIterator, class RandomAccessIterator, class Compare> |
| RandomAccessIterator |
| partial_sort_copy(InputIterator first, InputIterator last, |
| RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); |
| |
| template <class RandomAccessIterator> |
| void |
| nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); |
| |
| template <class RandomAccessIterator, class Compare> |
| void |
| nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); |
| |
| template <class ForwardIterator, class T> |
| constexpr ForwardIterator // constexpr in C++20 |
| lower_bound(ForwardIterator first, ForwardIterator last, const T& value); |
| |
| template <class ForwardIterator, class T, class Compare> |
| constexpr ForwardIterator // constexpr in C++20 |
| lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); |
| |
| template <class ForwardIterator, class T> |
| constexpr ForwardIterator // constexpr in C++20 |
| upper_bound(ForwardIterator first, ForwardIterator last, const T& value); |
| |
| template <class ForwardIterator, class T, class Compare> |
| constexpr ForwardIterator // constexpr in C++20 |
| upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); |
| |
| template <class ForwardIterator, class T> |
| constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20 |
| equal_range(ForwardIterator first, ForwardIterator last, const T& value); |
| |
| template <class ForwardIterator, class T, class Compare> |
| constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20 |
| equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); |
| |
| template <class ForwardIterator, class T> |
| constexpr bool // constexpr in C++20 |
| binary_search(ForwardIterator first, ForwardIterator last, const T& value); |
| |
| template <class ForwardIterator, class T, class Compare> |
| constexpr bool // constexpr in C++20 |
| binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator> |
| constexpr OutputIterator // constexpr in C++20 |
| merge(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, OutputIterator result); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> |
| constexpr OutputIterator // constexpr in C++20 |
| merge(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); |
| |
| template <class BidirectionalIterator> |
| void |
| inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); |
| |
| template <class BidirectionalIterator, class Compare> |
| void |
| inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); |
| |
| template <class InputIterator1, class InputIterator2> |
| constexpr bool // constexpr in C++20 |
| includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); |
| |
| template <class InputIterator1, class InputIterator2, class Compare> |
| constexpr bool // constexpr in C++20 |
| includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator> |
| constexpr OutputIterator // constexpr in C++20 |
| set_union(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, OutputIterator result); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> |
| constexpr OutputIterator // constexpr in C++20 |
| set_union(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator> |
| constexpr OutputIterator // constexpr in C++20 |
| set_intersection(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, OutputIterator result); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> |
| constexpr OutputIterator // constexpr in C++20 |
| set_intersection(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator> |
| constexpr OutputIterator // constexpr in C++20 |
| set_difference(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, OutputIterator result); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> |
| constexpr OutputIterator // constexpr in C++20 |
| set_difference(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator> |
| constexpr OutputIterator // constexpr in C++20 |
| set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, OutputIterator result); |
| |
| template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> |
| constexpr OutputIterator // constexpr in C++20 |
| set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); |
| |
| template <class RandomAccessIterator> |
| void |
| push_heap(RandomAccessIterator first, RandomAccessIterator last); |
| |
| template <class RandomAccessIterator, class Compare> |
| void |
| push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
| |
| template <class RandomAccessIterator> |
| void |
| pop_heap(RandomAccessIterator first, RandomAccessIterator last); |
| |
| template <class RandomAccessIterator, class Compare> |
| void |
| pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
| |
| template <class RandomAccessIterator> |
| void |
| make_heap(RandomAccessIterator first, RandomAccessIterator last); |
| |
| template <class RandomAccessIterator, class Compare> |
| void |
| make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
| |
| template <class RandomAccessIterator> |
| void |
| sort_heap(RandomAccessIterator first, RandomAccessIterator last); |
| |
| template <class RandomAccessIterator, class Compare> |
| void |
| sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
| |
| template <class RandomAccessIterator> |
| constexpr bool // constexpr in C++20 |
| is_heap(RandomAccessIterator first, RandomAccessiterator last); |
| |
| template <class RandomAccessIterator, class Compare> |
| constexpr bool // constexpr in C++20 |
| is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp); |
| |
| template <class RandomAccessIterator> |
| constexpr RandomAccessIterator // constexpr in C++20 |
| is_heap_until(RandomAccessIterator first, RandomAccessiterator last); |
| |
| template <class RandomAccessIterator, class Compare> |
| constexpr RandomAccessIterator // constexpr in C++20 |
| is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp); |
| |
| template <class ForwardIterator> |
| constexpr ForwardIterator // constexpr in C++14 |
| min_element(ForwardIterator first, ForwardIterator last); |
| |
| template <class ForwardIterator, class Compare> |
| constexpr ForwardIterator // constexpr in C++14 |
| min_element(ForwardIterator first, ForwardIterator last, Compare comp); |
| |
| template <class T> |
| constexpr const T& // constexpr in C++14 |
| min(const T& a, const T& b); |
| |
| template <class T, class Compare> |
| constexpr const T& // constexpr in C++14 |
| min(const T& a, const T& b, Compare comp); |
| |
| template<class T> |
| constexpr T // constexpr in C++14 |
| min(initializer_list<T> t); |
| |
| template<class T, class Compare> |
| constexpr T // constexpr in C++14 |
| min(initializer_list<T> t, Compare comp); |
| |
| template<class T> |
| constexpr const T& clamp(const T& v, const T& lo, const T& hi); // C++17 |
| |
| template<class T, class Compare> |
| constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17 |
| |
| template <class ForwardIterator> |
| constexpr ForwardIterator // constexpr in C++14 |
| max_element(ForwardIterator first, ForwardIterator last); |
| |
| template <class ForwardIterator, class Compare> |
| constexpr ForwardIterator // constexpr in C++14 |
| max_element(ForwardIterator first, ForwardIterator last, Compare comp); |
| |
| template <class T> |
| constexpr const T& // constexpr in C++14 |
| max(const T& a, const T& b); |
| |
| template <class T, class Compare> |
| constexpr const T& // constexpr in C++14 |
| max(const T& a, const T& b, Compare comp); |
| |
| template<class T> |
| constexpr T // constexpr in C++14 |
| max(initializer_list<T> t); |
| |
| template<class T, class Compare> |
| constexpr T // constexpr in C++14 |
| max(initializer_list<T> t, Compare comp); |
| |
| template<class ForwardIterator> |
| constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14 |
| minmax_element(ForwardIterator first, ForwardIterator last); |
| |
| template<class ForwardIterator, class Compare> |
| constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14 |
| minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); |
| |
| template<class T> |
| constexpr pair<const T&, const T&> // constexpr in C++14 |
| minmax(const T& a, const T& b); |
| |
| template<class T, class Compare> |
| constexpr pair<const T&, const T&> // constexpr in C++14 |
| minmax(const T& a, const T& b, Compare comp); |
| |
| template<class T> |
| constexpr pair<T, T> // constexpr in C++14 |
| minmax(initializer_list<T> t); |
| |
| template<class T, class Compare> |
| constexpr pair<T, T> // constexpr in C++14 |
| minmax(initializer_list<T> t, Compare comp); |
| |
| template <class InputIterator1, class InputIterator2> |
| constexpr bool // constexpr in C++20 |
| lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); |
| |
| template <class InputIterator1, class InputIterator2, class Compare> |
| constexpr bool // constexpr in C++20 |
| lexicographical_compare(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, InputIterator2 last2, Compare comp); |
| |
| template <class BidirectionalIterator> |
| constexpr bool // constexpr in C++20 |
| next_permutation(BidirectionalIterator first, BidirectionalIterator last); |
| |
| template <class BidirectionalIterator, class Compare> |
| constexpr bool // constexpr in C++20 |
| next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); |
| |
| template <class BidirectionalIterator> |
| constexpr bool // constexpr in C++20 |
| prev_permutation(BidirectionalIterator first, BidirectionalIterator last); |
| |
| template <class BidirectionalIterator, class Compare> |
| constexpr bool // constexpr in C++20 |
| prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); |
| |
| } // std |
| |
| */ |
| |
| #include <__config> |
| #include <initializer_list> |
| #include <type_traits> |
| #include <cstring> |
| #include <utility> // needed to provide swap_ranges. |
| #include <memory> |
| #include <functional> |
| #include <iterator> |
| #include <cstddef> |
| #include <bit> |
| #include <version> |
| |
| #include <__debug> |
| |
| #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
| #pragma GCC system_header |
| #endif |
| |
| _LIBCPP_PUSH_MACROS |
| #include <__undef_macros> |
| |
| |
| _LIBCPP_BEGIN_NAMESPACE_STD |
| |
| // I'd like to replace these with _VSTD::equal_to<void>, but can't because: |
| // * That only works with C++14 and later, and |
| // * We haven't included <functional> here. |
| template <class _T1, class _T2 = _T1> |
| struct __equal_to |
| { |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;} |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;} |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;} |
| }; |
| |
| template <class _T1> |
| struct __equal_to<_T1, _T1> |
| { |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} |
| }; |
| |
| template <class _T1> |
| struct __equal_to<const _T1, _T1> |
| { |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} |
| }; |
| |
| template <class _T1> |
| struct __equal_to<_T1, const _T1> |
| { |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} |
| }; |
| |
| template <class _T1, class _T2 = _T1> |
| struct __less |
| { |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} |
| |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} |
| |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} |
| |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;} |
| }; |
| |
| template <class _T1> |
| struct __less<_T1, _T1> |
| { |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} |
| }; |
| |
| template <class _T1> |
| struct __less<const _T1, _T1> |
| { |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} |
| }; |
| |
| template <class _T1> |
| struct __less<_T1, const _T1> |
| { |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} |
| }; |
| |
| template <class _Predicate> |
| class __invert // invert the sense of a comparison |
| { |
| private: |
| _Predicate __p_; |
| public: |
| _LIBCPP_INLINE_VISIBILITY __invert() {} |
| |
| _LIBCPP_INLINE_VISIBILITY |
| explicit __invert(_Predicate __p) : __p_(__p) {} |
| |
| template <class _T1> |
| _LIBCPP_INLINE_VISIBILITY |
| bool operator()(const _T1& __x) {return !__p_(__x);} |
| |
| template <class _T1, class _T2> |
| _LIBCPP_INLINE_VISIBILITY |
| bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);} |
| }; |
| |
| // Perform division by two quickly for positive integers (llvm.org/PR39129) |
| |
| template <typename _Integral> |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| typename enable_if |
| < |
| is_integral<_Integral>::value, |
| _Integral |
| >::type |
| __half_positive(_Integral __value) |
| { |
| return static_cast<_Integral>(static_cast<typename make_unsigned<_Integral>::type>(__value) / 2); |
| } |
| |
| template <typename _Tp> |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| typename enable_if |
| < |
| !is_integral<_Tp>::value, |
| _Tp |
| >::type |
| __half_positive(_Tp __value) |
| { |
| return __value / 2; |
| } |
| |
| #ifdef _LIBCPP_DEBUG |
| |
| template <class _Compare> |
| struct __debug_less |
| { |
| _Compare &__comp_; |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| __debug_less(_Compare& __c) : __comp_(__c) {} |
| |
| template <class _Tp, class _Up> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool operator()(const _Tp& __x, const _Up& __y) |
| { |
| bool __r = __comp_(__x, __y); |
| if (__r) |
| __do_compare_assert(0, __y, __x); |
| return __r; |
| } |
| |
| template <class _Tp, class _Up> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool operator()(_Tp& __x, _Up& __y) |
| { |
| bool __r = __comp_(__x, __y); |
| if (__r) |
| __do_compare_assert(0, __y, __x); |
| return __r; |
| } |
| |
| template <class _LHS, class _RHS> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| inline _LIBCPP_INLINE_VISIBILITY |
| decltype((void)_VSTD::declval<_Compare&>()( |
| _VSTD::declval<_LHS &>(), _VSTD::declval<_RHS &>())) |
| __do_compare_assert(int, _LHS & __l, _RHS & __r) { |
| _LIBCPP_ASSERT(!__comp_(__l, __r), |
| "Comparator does not induce a strict weak ordering"); |
| } |
| |
| template <class _LHS, class _RHS> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| inline _LIBCPP_INLINE_VISIBILITY |
| void __do_compare_assert(long, _LHS &, _RHS &) {} |
| }; |
| |
| #endif // _LIBCPP_DEBUG |
| |
| template <class _Comp> |
| struct __comp_ref_type { |
| // Pass the comparator by lvalue reference. Or in debug mode, using a |
| // debugging wrapper that stores a reference. |
| #ifndef _LIBCPP_DEBUG |
| typedef typename add_lvalue_reference<_Comp>::type type; |
| #else |
| typedef __debug_less<_Comp> type; |
| #endif |
| }; |
| |
| // all_of |
| |
| template <class _InputIterator, class _Predicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) |
| { |
| for (; __first != __last; ++__first) |
| if (!__pred(*__first)) |
| return false; |
| return true; |
| } |
| |
| // any_of |
| |
| template <class _InputIterator, class _Predicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) |
| { |
| for (; __first != __last; ++__first) |
| if (__pred(*__first)) |
| return true; |
| return false; |
| } |
| |
| // none_of |
| |
| template <class _InputIterator, class _Predicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) |
| { |
| for (; __first != __last; ++__first) |
| if (__pred(*__first)) |
| return false; |
| return true; |
| } |
| |
| // for_each |
| |
| template <class _InputIterator, class _Function> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _Function |
| for_each(_InputIterator __first, _InputIterator __last, _Function __f) |
| { |
| for (; __first != __last; ++__first) |
| __f(*__first); |
| return __f; |
| } |
| |
| #if _LIBCPP_STD_VER > 14 |
| // for_each_n |
| |
| template <class _InputIterator, class _Size, class _Function> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _InputIterator |
| for_each_n(_InputIterator __first, _Size __orig_n, _Function __f) |
| { |
| typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; |
| _IntegralSize __n = __orig_n; |
| while (__n > 0) |
| { |
| __f(*__first); |
| ++__first; |
| --__n; |
| } |
| return __first; |
| } |
| #endif |
| |
| // find |
| |
| template <class _InputIterator, class _Tp> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _InputIterator |
| find(_InputIterator __first, _InputIterator __last, const _Tp& __value_) |
| { |
| for (; __first != __last; ++__first) |
| if (*__first == __value_) |
| break; |
| return __first; |
| } |
| |
| // find_if |
| |
| template <class _InputIterator, class _Predicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _InputIterator |
| find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) |
| { |
| for (; __first != __last; ++__first) |
| if (__pred(*__first)) |
| break; |
| return __first; |
| } |
| |
| // find_if_not |
| |
| template<class _InputIterator, class _Predicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _InputIterator |
| find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred) |
| { |
| for (; __first != __last; ++__first) |
| if (!__pred(*__first)) |
| break; |
| return __first; |
| } |
| |
| // find_end |
| |
| template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 |
| __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, |
| forward_iterator_tag, forward_iterator_tag) |
| { |
| // modeled after search algorithm |
| _ForwardIterator1 __r = __last1; // __last1 is the "default" answer |
| if (__first2 == __last2) |
| return __r; |
| while (true) |
| { |
| while (true) |
| { |
| if (__first1 == __last1) // if source exhausted return last correct answer |
| return __r; // (or __last1 if never found) |
| if (__pred(*__first1, *__first2)) |
| break; |
| ++__first1; |
| } |
| // *__first1 matches *__first2, now match elements after here |
| _ForwardIterator1 __m1 = __first1; |
| _ForwardIterator2 __m2 = __first2; |
| while (true) |
| { |
| if (++__m2 == __last2) |
| { // Pattern exhaused, record answer and search for another one |
| __r = __first1; |
| ++__first1; |
| break; |
| } |
| if (++__m1 == __last1) // Source exhausted, return last answer |
| return __r; |
| if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first |
| { |
| ++__first1; |
| break; |
| } // else there is a match, check next elements |
| } |
| } |
| } |
| |
| template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 |
| __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, |
| _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred, |
| bidirectional_iterator_tag, bidirectional_iterator_tag) |
| { |
| // modeled after search algorithm (in reverse) |
| if (__first2 == __last2) |
| return __last1; // Everything matches an empty sequence |
| _BidirectionalIterator1 __l1 = __last1; |
| _BidirectionalIterator2 __l2 = __last2; |
| --__l2; |
| while (true) |
| { |
| // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks |
| while (true) |
| { |
| if (__first1 == __l1) // return __last1 if no element matches *__first2 |
| return __last1; |
| if (__pred(*--__l1, *__l2)) |
| break; |
| } |
| // *__l1 matches *__l2, now match elements before here |
| _BidirectionalIterator1 __m1 = __l1; |
| _BidirectionalIterator2 __m2 = __l2; |
| while (true) |
| { |
| if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) |
| return __m1; |
| if (__m1 == __first1) // Otherwise if source exhaused, pattern not found |
| return __last1; |
| if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 |
| { |
| break; |
| } // else there is a match, check next elements |
| } |
| } |
| } |
| |
| template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> |
| _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 |
| __find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, |
| _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, |
| random_access_iterator_tag, random_access_iterator_tag) |
| { |
| // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern |
| typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2; |
| if (__len2 == 0) |
| return __last1; |
| typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1; |
| if (__len1 < __len2) |
| return __last1; |
| const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here |
| _RandomAccessIterator1 __l1 = __last1; |
| _RandomAccessIterator2 __l2 = __last2; |
| --__l2; |
| while (true) |
| { |
| while (true) |
| { |
| if (__s == __l1) |
| return __last1; |
| if (__pred(*--__l1, *__l2)) |
| break; |
| } |
| _RandomAccessIterator1 __m1 = __l1; |
| _RandomAccessIterator2 __m2 = __l2; |
| while (true) |
| { |
| if (__m2 == __first2) |
| return __m1; |
| // no need to check range on __m1 because __s guarantees we have enough source |
| if (!__pred(*--__m1, *--__m2)) |
| { |
| break; |
| } |
| } |
| } |
| } |
| |
| template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator1 |
| find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) |
| { |
| return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type> |
| (__first1, __last1, __first2, __last2, __pred, |
| typename iterator_traits<_ForwardIterator1>::iterator_category(), |
| typename iterator_traits<_ForwardIterator2>::iterator_category()); |
| } |
| |
| template <class _ForwardIterator1, class _ForwardIterator2> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator1 |
| find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2) |
| { |
| typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; |
| typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; |
| return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); |
| } |
| |
| // find_first_of |
| |
| template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> |
| _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1 |
| __find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) |
| { |
| for (; __first1 != __last1; ++__first1) |
| for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) |
| if (__pred(*__first1, *__j)) |
| return __first1; |
| return __last1; |
| } |
| |
| |
| template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator1 |
| find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) |
| { |
| return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred); |
| } |
| |
| template <class _ForwardIterator1, class _ForwardIterator2> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator1 |
| find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2) |
| { |
| typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; |
| typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; |
| return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); |
| } |
| |
| // adjacent_find |
| |
| template <class _ForwardIterator, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator |
| adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) |
| { |
| if (__first != __last) |
| { |
| _ForwardIterator __i = __first; |
| while (++__i != __last) |
| { |
| if (__pred(*__first, *__i)) |
| return __first; |
| __first = __i; |
| } |
| } |
| return __last; |
| } |
| |
| template <class _ForwardIterator> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator |
| adjacent_find(_ForwardIterator __first, _ForwardIterator __last) |
| { |
| typedef typename iterator_traits<_ForwardIterator>::value_type __v; |
| return _VSTD::adjacent_find(__first, __last, __equal_to<__v>()); |
| } |
| |
| // count |
| |
| template <class _InputIterator, class _Tp> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| typename iterator_traits<_InputIterator>::difference_type |
| count(_InputIterator __first, _InputIterator __last, const _Tp& __value_) |
| { |
| typename iterator_traits<_InputIterator>::difference_type __r(0); |
| for (; __first != __last; ++__first) |
| if (*__first == __value_) |
| ++__r; |
| return __r; |
| } |
| |
| // count_if |
| |
| template <class _InputIterator, class _Predicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| typename iterator_traits<_InputIterator>::difference_type |
| count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) |
| { |
| typename iterator_traits<_InputIterator>::difference_type __r(0); |
| for (; __first != __last; ++__first) |
| if (__pred(*__first)) |
| ++__r; |
| return __r; |
| } |
| |
| // mismatch |
| |
| template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| pair<_InputIterator1, _InputIterator2> |
| mismatch(_InputIterator1 __first1, _InputIterator1 __last1, |
| _InputIterator2 __first2, _BinaryPredicate __pred) |
| { |
| for (; __first1 != __last1; ++__first1, (void) ++__first2) |
| if (!__pred(*__first1, *__first2)) |
| break; |
| return pair<_InputIterator1, _InputIterator2>(__first1, __first2); |
| } |
| |
| template <class _InputIterator1, class _InputIterator2> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| pair<_InputIterator1, _InputIterator2> |
| mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) |
| { |
| typedef typename iterator_traits<_InputIterator1>::value_type __v1; |
| typedef typename iterator_traits<_InputIterator2>::value_type __v2; |
| return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>()); |
| } |
| |
| #if _LIBCPP_STD_VER > 11 |
| template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| pair<_InputIterator1, _InputIterator2> |
| mismatch(_InputIterator1 __first1, _InputIterator1 __last1, |
| _InputIterator2 __first2, _InputIterator2 __last2, |
| _BinaryPredicate __pred) |
| { |
| for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) |
| if (!__pred(*__first1, *__first2)) |
| break; |
| return pair<_InputIterator1, _InputIterator2>(__first1, __first2); |
| } |
| |
| template <class _InputIterator1, class _InputIterator2> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| pair<_InputIterator1, _InputIterator2> |
| mismatch(_InputIterator1 __first1, _InputIterator1 __last1, |
| _InputIterator2 __first2, _InputIterator2 __last2) |
| { |
| typedef typename iterator_traits<_InputIterator1>::value_type __v1; |
| typedef typename iterator_traits<_InputIterator2>::value_type __v2; |
| return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); |
| } |
| #endif |
| |
| // equal |
| |
| template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) |
| { |
| for (; __first1 != __last1; ++__first1, (void) ++__first2) |
| if (!__pred(*__first1, *__first2)) |
| return false; |
| return true; |
| } |
| |
| template <class _InputIterator1, class _InputIterator2> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) |
| { |
| typedef typename iterator_traits<_InputIterator1>::value_type __v1; |
| typedef typename iterator_traits<_InputIterator2>::value_type __v2; |
| return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>()); |
| } |
| |
| #if _LIBCPP_STD_VER > 11 |
| template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| __equal(_InputIterator1 __first1, _InputIterator1 __last1, |
| _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred, |
| input_iterator_tag, input_iterator_tag ) |
| { |
| for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) |
| if (!__pred(*__first1, *__first2)) |
| return false; |
| return __first1 == __last1 && __first2 == __last2; |
| } |
| |
| template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, |
| _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, |
| random_access_iterator_tag, random_access_iterator_tag ) |
| { |
| if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) |
| return false; |
| return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2, |
| typename add_lvalue_reference<_BinaryPredicate>::type> |
| (__first1, __last1, __first2, __pred ); |
| } |
| |
| template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| equal(_InputIterator1 __first1, _InputIterator1 __last1, |
| _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred ) |
| { |
| return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type> |
| (__first1, __last1, __first2, __last2, __pred, |
| typename iterator_traits<_InputIterator1>::iterator_category(), |
| typename iterator_traits<_InputIterator2>::iterator_category()); |
| } |
| |
| template <class _InputIterator1, class _InputIterator2> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| equal(_InputIterator1 __first1, _InputIterator1 __last1, |
| _InputIterator2 __first2, _InputIterator2 __last2) |
| { |
| typedef typename iterator_traits<_InputIterator1>::value_type __v1; |
| typedef typename iterator_traits<_InputIterator2>::value_type __v2; |
| return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(), |
| typename iterator_traits<_InputIterator1>::iterator_category(), |
| typename iterator_traits<_InputIterator2>::iterator_category()); |
| } |
| #endif |
| |
| // is_permutation |
| |
| template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool |
| is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _BinaryPredicate __pred) |
| { |
| // shorten sequences as much as possible by lopping of any equal prefix |
| for (; __first1 != __last1; ++__first1, (void) ++__first2) |
| if (!__pred(*__first1, *__first2)) |
| break; |
| if (__first1 == __last1) |
| return true; |
| |
| // __first1 != __last1 && *__first1 != *__first2 |
| typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; |
| _D1 __l1 = _VSTD::distance(__first1, __last1); |
| if (__l1 == _D1(1)) |
| return false; |
| _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1); |
| // For each element in [f1, l1) see if there are the same number of |
| // equal elements in [f2, l2) |
| for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) |
| { |
| // Have we already counted the number of *__i in [f1, l1)? |
| _ForwardIterator1 __match = __first1; |
| for (; __match != __i; ++__match) |
| if (__pred(*__match, *__i)) |
| break; |
| if (__match == __i) { |
| // Count number of *__i in [f2, l2) |
| _D1 __c2 = 0; |
| for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) |
| if (__pred(*__i, *__j)) |
| ++__c2; |
| if (__c2 == 0) |
| return false; |
| // Count number of *__i in [__i, l1) (we can start with 1) |
| _D1 __c1 = 1; |
| for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) |
| if (__pred(*__i, *__j)) |
| ++__c1; |
| if (__c1 != __c2) |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| template<class _ForwardIterator1, class _ForwardIterator2> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2) |
| { |
| typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; |
| typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; |
| return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>()); |
| } |
| |
| #if _LIBCPP_STD_VER > 11 |
| template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 bool |
| __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2, |
| _BinaryPredicate __pred, |
| forward_iterator_tag, forward_iterator_tag ) |
| { |
| // shorten sequences as much as possible by lopping of any equal prefix |
| for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) |
| if (!__pred(*__first1, *__first2)) |
| break; |
| if (__first1 == __last1) |
| return __first2 == __last2; |
| else if (__first2 == __last2) |
| return false; |
| |
| typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; |
| _D1 __l1 = _VSTD::distance(__first1, __last1); |
| |
| typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2; |
| _D2 __l2 = _VSTD::distance(__first2, __last2); |
| if (__l1 != __l2) |
| return false; |
| |
| // For each element in [f1, l1) see if there are the same number of |
| // equal elements in [f2, l2) |
| for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) |
| { |
| // Have we already counted the number of *__i in [f1, l1)? |
| _ForwardIterator1 __match = __first1; |
| for (; __match != __i; ++__match) |
| if (__pred(*__match, *__i)) |
| break; |
| if (__match == __i) { |
| // Count number of *__i in [f2, l2) |
| _D1 __c2 = 0; |
| for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) |
| if (__pred(*__i, *__j)) |
| ++__c2; |
| if (__c2 == 0) |
| return false; |
| // Count number of *__i in [__i, l1) (we can start with 1) |
| _D1 __c1 = 1; |
| for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) |
| if (__pred(*__i, *__j)) |
| ++__c1; |
| if (__c1 != __c2) |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 bool |
| __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1, |
| _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2, |
| _BinaryPredicate __pred, |
| random_access_iterator_tag, random_access_iterator_tag ) |
| { |
| if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) |
| return false; |
| return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2, |
| typename add_lvalue_reference<_BinaryPredicate>::type> |
| (__first1, __last1, __first2, __pred ); |
| } |
| |
| template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2, |
| _BinaryPredicate __pred ) |
| { |
| return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type> |
| (__first1, __last1, __first2, __last2, __pred, |
| typename iterator_traits<_ForwardIterator1>::iterator_category(), |
| typename iterator_traits<_ForwardIterator2>::iterator_category()); |
| } |
| |
| template<class _ForwardIterator1, class _ForwardIterator2> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| bool |
| is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2) |
| { |
| typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; |
| typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; |
| return _VSTD::__is_permutation(__first1, __last1, __first2, __last2, |
| __equal_to<__v1, __v2>(), |
| typename iterator_traits<_ForwardIterator1>::iterator_category(), |
| typename iterator_traits<_ForwardIterator2>::iterator_category()); |
| } |
| #endif |
| |
| // search |
| // __search is in <functional> |
| |
| template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator1 |
| search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) |
| { |
| return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type> |
| (__first1, __last1, __first2, __last2, __pred, |
| typename iterator_traits<_ForwardIterator1>::iterator_category(), |
| typename iterator_traits<_ForwardIterator2>::iterator_category()) |
| .first; |
| } |
| |
| template <class _ForwardIterator1, class _ForwardIterator2> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator1 |
| search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2, _ForwardIterator2 __last2) |
| { |
| typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; |
| typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; |
| return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); |
| } |
| |
| |
| #if _LIBCPP_STD_VER > 14 |
| template <class _ForwardIterator, class _Searcher> |
| _LIBCPP_NODISCARD_EXT _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s) |
| { return __s(__f, __l).first; } |
| #endif |
| |
| // search_n |
| |
| template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator |
| __search_n(_ForwardIterator __first, _ForwardIterator __last, |
| _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag) |
| { |
| if (__count <= 0) |
| return __first; |
| while (true) |
| { |
| // Find first element in sequence that matchs __value_, with a mininum of loop checks |
| while (true) |
| { |
| if (__first == __last) // return __last if no element matches __value_ |
| return __last; |
| if (__pred(*__first, __value_)) |
| break; |
| ++__first; |
| } |
| // *__first matches __value_, now match elements after here |
| _ForwardIterator __m = __first; |
| _Size __c(0); |
| while (true) |
| { |
| if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) |
| return __first; |
| if (++__m == __last) // Otherwise if source exhaused, pattern not found |
| return __last; |
| if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first |
| { |
| __first = __m; |
| ++__first; |
| break; |
| } // else there is a match, check next elements |
| } |
| } |
| } |
| |
| template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator |
| __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last, |
| _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag) |
| { |
| if (__count <= 0) |
| return __first; |
| _Size __len = static_cast<_Size>(__last - __first); |
| if (__len < __count) |
| return __last; |
| const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here |
| while (true) |
| { |
| // Find first element in sequence that matchs __value_, with a mininum of loop checks |
| while (true) |
| { |
| if (__first >= __s) // return __last if no element matches __value_ |
| return __last; |
| if (__pred(*__first, __value_)) |
| break; |
| ++__first; |
| } |
| // *__first matches __value_, now match elements after here |
| _RandomAccessIterator __m = __first; |
| _Size __c(0); |
| while (true) |
| { |
| if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) |
| return __first; |
| ++__m; // no need to check range on __m because __s guarantees we have enough source |
| if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first |
| { |
| __first = __m; |
| ++__first; |
| break; |
| } // else there is a match, check next elements |
| } |
| } |
| } |
| |
| template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator |
| search_n(_ForwardIterator __first, _ForwardIterator __last, |
| _Size __count, const _Tp& __value_, _BinaryPredicate __pred) |
| { |
| return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type> |
| (__first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred, |
| typename iterator_traits<_ForwardIterator>::iterator_category()); |
| } |
| |
| template <class _ForwardIterator, class _Size, class _Tp> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator |
| search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) |
| { |
| typedef typename iterator_traits<_ForwardIterator>::value_type __v; |
| return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), |
| __value_, __equal_to<__v, _Tp>()); |
| } |
| |
| // copy |
| template <class _Iter> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| _Iter |
| __unwrap_iter(_Iter __i) |
| { |
| return __i; |
| } |
| |
| template <class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| typename enable_if |
| < |
| is_trivially_copy_assignable<_Tp>::value, |
| _Tp* |
| >::type |
| __unwrap_iter(move_iterator<_Tp*> __i) |
| { |
| return __i.base(); |
| } |
| |
| #if _LIBCPP_DEBUG_LEVEL < 2 |
| |
| template <class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| typename enable_if |
| < |
| is_trivially_copy_assignable<_Tp>::value, |
| _Tp* |
| >::type |
| __unwrap_iter(__wrap_iter<_Tp*> __i) |
| { |
| return __i.base(); |
| } |
| |
| template <class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| typename enable_if |
| < |
| is_trivially_copy_assignable<_Tp>::value, |
| const _Tp* |
| >::type |
| __unwrap_iter(__wrap_iter<const _Tp*> __i) |
| { |
| return __i.base(); |
| } |
| |
| #else |
| |
| template <class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| typename enable_if |
| < |
| is_trivially_copy_assignable<_Tp>::value, |
| __wrap_iter<_Tp*> |
| >::type |
| __unwrap_iter(__wrap_iter<_Tp*> __i) |
| { |
| return __i; |
| } |
| |
| #endif // _LIBCPP_DEBUG_LEVEL < 2 |
| |
| template <class _InputIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| __copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) |
| { |
| for (; __first != __last; ++__first, (void) ++__result) |
| *__result = *__first; |
| return __result; |
| } |
| |
| template <class _InputIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY |
| _OutputIterator |
| __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) |
| { |
| return _VSTD::__copy_constexpr(__first, __last, __result); |
| } |
| |
| template <class _Tp, class _Up> |
| inline _LIBCPP_INLINE_VISIBILITY |
| typename enable_if |
| < |
| is_same<typename remove_const<_Tp>::type, _Up>::value && |
| is_trivially_copy_assignable<_Up>::value, |
| _Up* |
| >::type |
| __copy(_Tp* __first, _Tp* __last, _Up* __result) |
| { |
| const size_t __n = static_cast<size_t>(__last - __first); |
| if (__n > 0) |
| _VSTD::memmove(__result, __first, __n * sizeof(_Up)); |
| return __result + __n; |
| } |
| |
| template <class _InputIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) |
| { |
| if (__libcpp_is_constant_evaluated()) { |
| return _VSTD::__copy_constexpr( |
| _VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); |
| } else { |
| return _VSTD::__copy( |
| _VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); |
| } |
| } |
| |
| // copy_backward |
| |
| template <class _BidirectionalIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| __copy_backward_constexpr(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) |
| { |
| while (__first != __last) |
| *--__result = *--__last; |
| return __result; |
| } |
| |
| template <class _BidirectionalIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY |
| _OutputIterator |
| __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) |
| { |
| return _VSTD::__copy_backward_constexpr(__first, __last, __result); |
| } |
| |
| template <class _Tp, class _Up> |
| inline _LIBCPP_INLINE_VISIBILITY |
| typename enable_if |
| < |
| is_same<typename remove_const<_Tp>::type, _Up>::value && |
| is_trivially_copy_assignable<_Up>::value, |
| _Up* |
| >::type |
| __copy_backward(_Tp* __first, _Tp* __last, _Up* __result) |
| { |
| const size_t __n = static_cast<size_t>(__last - __first); |
| if (__n > 0) |
| { |
| __result -= __n; |
| _VSTD::memmove(__result, __first, __n * sizeof(_Up)); |
| } |
| return __result; |
| } |
| |
| template <class _BidirectionalIterator1, class _BidirectionalIterator2> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _BidirectionalIterator2 |
| copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, |
| _BidirectionalIterator2 __result) |
| { |
| if (__libcpp_is_constant_evaluated()) { |
| return _VSTD::__copy_backward_constexpr(_VSTD::__unwrap_iter(__first), |
| _VSTD::__unwrap_iter(__last), |
| _VSTD::__unwrap_iter(__result)); |
| } else { |
| return _VSTD::__copy_backward(_VSTD::__unwrap_iter(__first), |
| _VSTD::__unwrap_iter(__last), |
| _VSTD::__unwrap_iter(__result)); |
| } |
| } |
| |
| // copy_if |
| |
| template<class _InputIterator, class _OutputIterator, class _Predicate> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| copy_if(_InputIterator __first, _InputIterator __last, |
| _OutputIterator __result, _Predicate __pred) |
| { |
| for (; __first != __last; ++__first) |
| { |
| if (__pred(*__first)) |
| { |
| *__result = *__first; |
| ++__result; |
| } |
| } |
| return __result; |
| } |
| |
| // copy_n |
| |
| template<class _InputIterator, class _Size, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| typename enable_if |
| < |
| __is_cpp17_input_iterator<_InputIterator>::value && |
| !__is_cpp17_random_access_iterator<_InputIterator>::value, |
| _OutputIterator |
| >::type |
| copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) |
| { |
| typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; |
| _IntegralSize __n = __orig_n; |
| if (__n > 0) |
| { |
| *__result = *__first; |
| ++__result; |
| for (--__n; __n > 0; --__n) |
| { |
| ++__first; |
| *__result = *__first; |
| ++__result; |
| } |
| } |
| return __result; |
| } |
| |
| template<class _InputIterator, class _Size, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| typename enable_if |
| < |
| __is_cpp17_random_access_iterator<_InputIterator>::value, |
| _OutputIterator |
| >::type |
| copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) |
| { |
| typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; |
| _IntegralSize __n = __orig_n; |
| return _VSTD::copy(__first, __first + __n, __result); |
| } |
| |
| // move |
| |
| // __move_constexpr exists so that __move doesn't call itself when delegating to the constexpr |
| // version of __move. |
| template <class _InputIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
| _OutputIterator |
| __move_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) |
| { |
| for (; __first != __last; ++__first, (void) ++__result) |
| *__result = _VSTD::move(*__first); |
| return __result; |
| } |
| |
| template <class _InputIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
| _OutputIterator |
| __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) |
| { |
| return _VSTD::__move_constexpr(__first, __last, __result); |
| } |
| |
| template <class _Tp, class _Up> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
| typename enable_if |
| < |
| is_same<typename remove_const<_Tp>::type, _Up>::value && |
| is_trivially_copy_assignable<_Up>::value, |
| _Up* |
| >::type |
| __move(_Tp* __first, _Tp* __last, _Up* __result) |
| { |
| if (__libcpp_is_constant_evaluated()) |
| return _VSTD::__move_constexpr(__first, __last, __result); |
| const size_t __n = static_cast<size_t>(__last - __first); |
| if (__n > 0) |
| _VSTD::memmove(__result, __first, __n * sizeof(_Up)); |
| return __result + __n; |
| } |
| |
| template <class _InputIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) |
| { |
| return _VSTD::__move(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); |
| } |
| |
| // move_backward |
| |
| // __move_backward_constexpr exists so that __move_backward doesn't call itself when delegating to |
| // the constexpr version of __move_backward. |
| template <class _InputIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
| _OutputIterator |
| __move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) |
| { |
| while (__first != __last) |
| *--__result = _VSTD::move(*--__last); |
| return __result; |
| } |
| |
| template <class _InputIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
| _OutputIterator |
| __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) |
| { |
| return _VSTD::__move_backward_constexpr(__first, __last, __result); |
| } |
| |
| template <class _Tp, class _Up> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 |
| typename enable_if |
| < |
| is_same<typename remove_const<_Tp>::type, _Up>::value && |
| is_trivially_copy_assignable<_Up>::value, |
| _Up* |
| >::type |
| __move_backward(_Tp* __first, _Tp* __last, _Up* __result) |
| { |
| if (__libcpp_is_constant_evaluated()) |
| return _VSTD::__move_backward_constexpr(__first, __last, __result); |
| const size_t __n = static_cast<size_t>(__last - __first); |
| if (__n > 0) |
| { |
| __result -= __n; |
| _VSTD::memmove(__result, __first, __n * sizeof(_Up)); |
| } |
| return __result; |
| } |
| |
| template <class _BidirectionalIterator1, class _BidirectionalIterator2> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _BidirectionalIterator2 |
| move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, |
| _BidirectionalIterator2 __result) |
| { |
| return _VSTD::__move_backward(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result)); |
| } |
| |
| // iter_swap |
| |
| // moved to <type_traits> for better swap / noexcept support |
| |
| // transform |
| |
| template <class _InputIterator, class _OutputIterator, class _UnaryOperation> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op) |
| { |
| for (; __first != __last; ++__first, (void) ++__result) |
| *__result = __op(*__first); |
| return __result; |
| } |
| |
| template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, |
| _OutputIterator __result, _BinaryOperation __binary_op) |
| { |
| for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result) |
| *__result = __binary_op(*__first1, *__first2); |
| return __result; |
| } |
| |
| // replace |
| |
| template <class _ForwardIterator, class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| void |
| replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value) |
| { |
| for (; __first != __last; ++__first) |
| if (*__first == __old_value) |
| *__first = __new_value; |
| } |
| |
| // replace_if |
| |
| template <class _ForwardIterator, class _Predicate, class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| void |
| replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value) |
| { |
| for (; __first != __last; ++__first) |
| if (__pred(*__first)) |
| *__first = __new_value; |
| } |
| |
| // replace_copy |
| |
| template <class _InputIterator, class _OutputIterator, class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, |
| const _Tp& __old_value, const _Tp& __new_value) |
| { |
| for (; __first != __last; ++__first, (void) ++__result) |
| if (*__first == __old_value) |
| *__result = __new_value; |
| else |
| *__result = *__first; |
| return __result; |
| } |
| |
| // replace_copy_if |
| |
| template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, |
| _Predicate __pred, const _Tp& __new_value) |
| { |
| for (; __first != __last; ++__first, (void) ++__result) |
| if (__pred(*__first)) |
| *__result = __new_value; |
| else |
| *__result = *__first; |
| return __result; |
| } |
| |
| // fill_n |
| |
| template <class _OutputIterator, class _Size, class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) |
| { |
| for (; __n > 0; ++__first, (void) --__n) |
| *__first = __value_; |
| return __first; |
| } |
| |
| template <class _OutputIterator, class _Size, class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) |
| { |
| return _VSTD::__fill_n(__first, _VSTD::__convert_to_integral(__n), __value_); |
| } |
| |
| // fill |
| |
| template <class _ForwardIterator, class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| void |
| __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag) |
| { |
| for (; __first != __last; ++__first) |
| *__first = __value_; |
| } |
| |
| template <class _RandomAccessIterator, class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| void |
| __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag) |
| { |
| _VSTD::fill_n(__first, __last - __first, __value_); |
| } |
| |
| template <class _ForwardIterator, class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| void |
| fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) |
| { |
| _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category()); |
| } |
| |
| // generate |
| |
| template <class _ForwardIterator, class _Generator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| void |
| generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen) |
| { |
| for (; __first != __last; ++__first) |
| *__first = __gen(); |
| } |
| |
| // generate_n |
| |
| template <class _OutputIterator, class _Size, class _Generator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen) |
| { |
| typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; |
| _IntegralSize __n = __orig_n; |
| for (; __n > 0; ++__first, (void) --__n) |
| *__first = __gen(); |
| return __first; |
| } |
| |
| // remove |
| |
| template <class _ForwardIterator, class _Tp> |
| _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator |
| remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) |
| { |
| __first = _VSTD::find(__first, __last, __value_); |
| if (__first != __last) |
| { |
| _ForwardIterator __i = __first; |
| while (++__i != __last) |
| { |
| if (!(*__i == __value_)) |
| { |
| *__first = _VSTD::move(*__i); |
| ++__first; |
| } |
| } |
| } |
| return __first; |
| } |
| |
| // remove_if |
| |
| template <class _ForwardIterator, class _Predicate> |
| _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator |
| remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) |
| { |
| __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type> |
| (__first, __last, __pred); |
| if (__first != __last) |
| { |
| _ForwardIterator __i = __first; |
| while (++__i != __last) |
| { |
| if (!__pred(*__i)) |
| { |
| *__first = _VSTD::move(*__i); |
| ++__first; |
| } |
| } |
| } |
| return __first; |
| } |
| |
| // remove_copy |
| |
| template <class _InputIterator, class _OutputIterator, class _Tp> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_) |
| { |
| for (; __first != __last; ++__first) |
| { |
| if (!(*__first == __value_)) |
| { |
| *__result = *__first; |
| ++__result; |
| } |
| } |
| return __result; |
| } |
| |
| // remove_copy_if |
| |
| template <class _InputIterator, class _OutputIterator, class _Predicate> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred) |
| { |
| for (; __first != __last; ++__first) |
| { |
| if (!__pred(*__first)) |
| { |
| *__result = *__first; |
| ++__result; |
| } |
| } |
| return __result; |
| } |
| |
| // unique |
| |
| template <class _ForwardIterator, class _BinaryPredicate> |
| _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator |
| unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) |
| { |
| __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type> |
| (__first, __last, __pred); |
| if (__first != __last) |
| { |
| // ... a a ? ... |
| // f i |
| _ForwardIterator __i = __first; |
| for (++__i; ++__i != __last;) |
| if (!__pred(*__first, *__i)) |
| *++__first = _VSTD::move(*__i); |
| ++__first; |
| } |
| return __first; |
| } |
| |
| template <class _ForwardIterator> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _ForwardIterator |
| unique(_ForwardIterator __first, _ForwardIterator __last) |
| { |
| typedef typename iterator_traits<_ForwardIterator>::value_type __v; |
| return _VSTD::unique(__first, __last, __equal_to<__v>()); |
| } |
| |
| // unique_copy |
| |
| template <class _BinaryPredicate, class _InputIterator, class _OutputIterator> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator |
| __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred, |
| input_iterator_tag, output_iterator_tag) |
| { |
| if (__first != __last) |
| { |
| typename iterator_traits<_InputIterator>::value_type __t(*__first); |
| *__result = __t; |
| ++__result; |
| while (++__first != __last) |
| { |
| if (!__pred(__t, *__first)) |
| { |
| __t = *__first; |
| *__result = __t; |
| ++__result; |
| } |
| } |
| } |
| return __result; |
| } |
| |
| template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator |
| __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred, |
| forward_iterator_tag, output_iterator_tag) |
| { |
| if (__first != __last) |
| { |
| _ForwardIterator __i = __first; |
| *__result = *__i; |
| ++__result; |
| while (++__first != __last) |
| { |
| if (!__pred(*__i, *__first)) |
| { |
| *__result = *__first; |
| ++__result; |
| __i = __first; |
| } |
| } |
| } |
| return __result; |
| } |
| |
| template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator> |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator |
| __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred, |
| input_iterator_tag, forward_iterator_tag) |
| { |
| if (__first != __last) |
| { |
| *__result = *__first; |
| while (++__first != __last) |
| if (!__pred(*__result, *__first)) |
| *++__result = *__first; |
| ++__result; |
| } |
| return __result; |
| } |
| |
| template <class _InputIterator, class _OutputIterator, class _BinaryPredicate> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred) |
| { |
| return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type> |
| (__first, __last, __result, __pred, |
| typename iterator_traits<_InputIterator>::iterator_category(), |
| typename iterator_traits<_OutputIterator>::iterator_category()); |
| } |
| |
| template <class _InputIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) |
| { |
| typedef typename iterator_traits<_InputIterator>::value_type __v; |
| return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>()); |
| } |
| |
| // reverse |
| |
| template <class _BidirectionalIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| void |
| __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag) |
| { |
| while (__first != __last) |
| { |
| if (__first == --__last) |
| break; |
| _VSTD::iter_swap(__first, __last); |
| ++__first; |
| } |
| } |
| |
| template <class _RandomAccessIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| void |
| __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag) |
| { |
| if (__first != __last) |
| for (; __first < --__last; ++__first) |
| _VSTD::iter_swap(__first, __last); |
| } |
| |
| template <class _BidirectionalIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| void |
| reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) |
| { |
| _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category()); |
| } |
| |
| // reverse_copy |
| |
| template <class _BidirectionalIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) |
| { |
| for (; __first != __last; ++__result) |
| *__result = *--__last; |
| return __result; |
| } |
| |
| // rotate |
| |
| template <class _ForwardIterator> |
| _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator |
| __rotate_left(_ForwardIterator __first, _ForwardIterator __last) |
| { |
| typedef typename iterator_traits<_ForwardIterator>::value_type value_type; |
| value_type __tmp = _VSTD::move(*__first); |
| _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first); |
| *__lm1 = _VSTD::move(__tmp); |
| return __lm1; |
| } |
| |
| template <class _BidirectionalIterator> |
| _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator |
| __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) |
| { |
| typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; |
| _BidirectionalIterator __lm1 = _VSTD::prev(__last); |
| value_type __tmp = _VSTD::move(*__lm1); |
| _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last); |
| *__first = _VSTD::move(__tmp); |
| return __fp1; |
| } |
| |
| template <class _ForwardIterator> |
| _LIBCPP_CONSTEXPR_AFTER_CXX14 _ForwardIterator |
| __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) |
| { |
| _ForwardIterator __i = __middle; |
| while (true) |
| { |
| swap(*__first, *__i); |
| ++__first; |
| if (++__i == __last) |
| break; |
| if (__first == __middle) |
| __middle = __i; |
| } |
| _ForwardIterator __r = __first; |
| if (__first != __middle) |
| { |
| __i = __middle; |
| while (true) |
| { |
| swap(*__first, *__i); |
| ++__first; |
| if (++__i == __last) |
| { |
| if (__first == __middle) |
| break; |
| __i = __middle; |
| } |
| else if (__first == __middle) |
| __middle = __i; |
| } |
| } |
| return __r; |
| } |
| |
| template<typename _Integral> |
| inline _LIBCPP_INLINE_VISIBILITY |
| _LIBCPP_CONSTEXPR_AFTER_CXX14 _Integral |
| __algo_gcd(_Integral __x, _Integral __y) |
| { |
| do |
| { |
| _Integral __t = __x % __y; |
| __x = __y; |
| __y = __t; |
| } while (__y); |
| return __x; |
| } |
| |
| template<typename _RandomAccessIterator> |
| _LIBCPP_CONSTEXPR_AFTER_CXX14 _RandomAccessIterator |
| __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) |
| { |
| typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; |
| typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; |
| |
| const difference_type __m1 = __middle - __first; |
| const difference_type __m2 = __last - __middle; |
| if (__m1 == __m2) |
| { |
| _VSTD::swap_ranges(__first, __middle, __middle); |
| return __middle; |
| } |
| const difference_type __g = _VSTD::__algo_gcd(__m1, __m2); |
| for (_RandomAccessIterator __p = __first + __g; __p != __first;) |
| { |
| value_type __t(_VSTD::move(*--__p)); |
| _RandomAccessIterator __p1 = __p; |
| _RandomAccessIterator __p2 = __p1 + __m1; |
| do |
| { |
| *__p1 = _VSTD::move(*__p2); |
| __p1 = __p2; |
| const difference_type __d = __last - __p2; |
| if (__m1 < __d) |
| __p2 += __m1; |
| else |
| __p2 = __first + (__m1 - __d); |
| } while (__p2 != __p); |
| *__p1 = _VSTD::move(__t); |
| } |
| return __first + __m2; |
| } |
| |
| template <class _ForwardIterator> |
| inline _LIBCPP_INLINE_VISIBILITY |
| _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator |
| __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, |
| _VSTD::forward_iterator_tag) |
| { |
| typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type; |
| if (_VSTD::is_trivially_move_assignable<value_type>::value) |
| { |
| if (_VSTD::next(__first) == __middle) |
| return _VSTD::__rotate_left(__first, __last); |
| } |
| return _VSTD::__rotate_forward(__first, __middle, __last); |
| } |
| |
| template <class _BidirectionalIterator> |
| inline _LIBCPP_INLINE_VISIBILITY |
| _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator |
| __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, |
| _VSTD::bidirectional_iterator_tag) |
| { |
| typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type; |
| if (_VSTD::is_trivially_move_assignable<value_type>::value) |
| { |
| if (_VSTD::next(__first) == __middle) |
| return _VSTD::__rotate_left(__first, __last); |
| if (_VSTD::next(__middle) == __last) |
| return _VSTD::__rotate_right(__first, __last); |
| } |
| return _VSTD::__rotate_forward(__first, __middle, __last); |
| } |
| |
| template <class _RandomAccessIterator> |
| inline _LIBCPP_INLINE_VISIBILITY |
| _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator |
| __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, |
| _VSTD::random_access_iterator_tag) |
| { |
| typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type; |
| if (_VSTD::is_trivially_move_assignable<value_type>::value) |
| { |
| if (_VSTD::next(__first) == __middle) |
| return _VSTD::__rotate_left(__first, __last); |
| if (_VSTD::next(__middle) == __last) |
| return _VSTD::__rotate_right(__first, __last); |
| return _VSTD::__rotate_gcd(__first, __middle, __last); |
| } |
| return _VSTD::__rotate_forward(__first, __middle, __last); |
| } |
| |
| template <class _ForwardIterator> |
| inline _LIBCPP_INLINE_VISIBILITY |
| _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator |
| rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) |
| { |
| if (__first == __middle) |
| return __last; |
| if (__middle == __last) |
| return __first; |
| return _VSTD::__rotate(__first, __middle, __last, |
| typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category()); |
| } |
| |
| // rotate_copy |
| |
| template <class _ForwardIterator, class _OutputIterator> |
| inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 |
| _OutputIterator |
| rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result) |
| { |
| return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result)); |
| } |
| |
| // min_element |
| |
| template <class _ForwardIterator, class _Compare> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| _ForwardIterator |
| min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) |
| { |
| static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, |
| "std::min_element requires a ForwardIterator"); |
| if (__first != __last) |
| { |
| _ForwardIterator __i = __first; |
| while (++__i != __last) |
| if (__comp(*__i, *__first)) |
| __first = __i; |
| } |
| return __first; |
| } |
| |
| template <class _ForwardIterator> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| _ForwardIterator |
| min_element(_ForwardIterator __first, _ForwardIterator __last) |
| { |
| return _VSTD::min_element(__first, __last, |
| __less<typename iterator_traits<_ForwardIterator>::value_type>()); |
| } |
| |
| // min |
| |
| template <class _Tp, class _Compare> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| const _Tp& |
| min(const _Tp& __a, const _Tp& __b, _Compare __comp) |
| { |
| return __comp(__b, __a) ? __b : __a; |
| } |
| |
| template <class _Tp> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| const _Tp& |
| min(const _Tp& __a, const _Tp& __b) |
| { |
| return _VSTD::min(__a, __b, __less<_Tp>()); |
| } |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| |
| template<class _Tp, class _Compare> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| _Tp |
| min(initializer_list<_Tp> __t, _Compare __comp) |
| { |
| return *_VSTD::min_element(__t.begin(), __t.end(), __comp); |
| } |
| |
| template<class _Tp> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| _Tp |
| min(initializer_list<_Tp> __t) |
| { |
| return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>()); |
| } |
| |
| #endif // _LIBCPP_CXX03_LANG |
| |
| // max_element |
| |
| template <class _ForwardIterator, class _Compare> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| _ForwardIterator |
| max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) |
| { |
| static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, |
| "std::max_element requires a ForwardIterator"); |
| if (__first != __last) |
| { |
| _ForwardIterator __i = __first; |
| while (++__i != __last) |
| if (__comp(*__first, *__i)) |
| __first = __i; |
| } |
| return __first; |
| } |
| |
| |
| template <class _ForwardIterator> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| _ForwardIterator |
| max_element(_ForwardIterator __first, _ForwardIterator __last) |
| { |
| return _VSTD::max_element(__first, __last, |
| __less<typename iterator_traits<_ForwardIterator>::value_type>()); |
| } |
| |
| // max |
| |
| template <class _Tp, class _Compare> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| const _Tp& |
| max(const _Tp& __a, const _Tp& __b, _Compare __comp) |
| { |
| return __comp(__a, __b) ? __b : __a; |
| } |
| |
| template <class _Tp> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| const _Tp& |
| max(const _Tp& __a, const _Tp& __b) |
| { |
| return _VSTD::max(__a, __b, __less<_Tp>()); |
| } |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| |
| template<class _Tp, class _Compare> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| _Tp |
| max(initializer_list<_Tp> __t, _Compare __comp) |
| { |
| return *_VSTD::max_element(__t.begin(), __t.end(), __comp); |
| } |
| |
| template<class _Tp> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| _Tp |
| max(initializer_list<_Tp> __t) |
| { |
| return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>()); |
| } |
| |
| #endif // _LIBCPP_CXX03_LANG |
| |
| #if _LIBCPP_STD_VER > 14 |
| // clamp |
| template<class _Tp, class _Compare> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| const _Tp& |
| clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp) |
| { |
| _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp"); |
| return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v; |
| |
| } |
| |
| template<class _Tp> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| const _Tp& |
| clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi) |
| { |
| return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>()); |
| } |
| #endif |
| |
| // minmax_element |
| |
| template <class _ForwardIterator, class _Compare> |
| _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| pair<_ForwardIterator, _ForwardIterator> |
| minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) |
| { |
| static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, |
| "std::minmax_element requires a ForwardIterator"); |
| pair<_ForwardIterator, _ForwardIterator> __result(__first, __first); |
| if (__first != __last) |
| { |
| if (++__first != __last) |
| { |
| if (__comp(*__first, *__result.first)) |
| __result.first = __first; |
| else |
| __result.second = __first; |
| while (++__first != __last) |
| { |
| _ForwardIterator __i = __first; |
| if (++__first == __last) |
| { |
| if (__comp(*__i, *__result.first)) |
| __result.first = __i; |
| else if (!__comp(*__i, *__result.second)) |
| __result.second = __i; |
| break; |
| } |
| else |
| { |
| if (__comp(*__first, *__i)) |
| { |
| if (__comp(*__first, *__result.first)) |
| __result.first = __first; |
| if (!__comp(*__i, *__result.second)) |
| __result.second = __i; |
| } |
| else |
| { |
| if (__comp(*__i, *__result.first)) |
| __result.first = __i; |
| if (!__comp(*__first, *__result.second)) |
| __result.second = __first; |
| } |
| } |
| } |
| } |
| } |
| return __result; |
| } |
| |
| template <class _ForwardIterator> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| pair<_ForwardIterator, _ForwardIterator> |
| minmax_element(_ForwardIterator __first, _ForwardIterator __last) |
| { |
| return _VSTD::minmax_element(__first, __last, |
| __less<typename iterator_traits<_ForwardIterator>::value_type>()); |
| } |
| |
| // minmax |
| |
| template<class _Tp, class _Compare> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| pair<const _Tp&, const _Tp&> |
| minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) |
| { |
| return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) : |
| pair<const _Tp&, const _Tp&>(__a, __b); |
| } |
| |
| template<class _Tp> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| pair<const _Tp&, const _Tp&> |
| minmax(const _Tp& __a, const _Tp& __b) |
| { |
| return _VSTD::minmax(__a, __b, __less<_Tp>()); |
| } |
| |
| #ifndef _LIBCPP_CXX03_LANG |
| |
| template<class _Tp, class _Compare> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| pair<_Tp, _Tp> |
| minmax(initializer_list<_Tp> __t, _Compare __comp) |
| { |
| typedef typename initializer_list<_Tp>::const_iterator _Iter; |
| _Iter __first = __t.begin(); |
| _Iter __last = __t.end(); |
| pair<_Tp, _Tp> __result(*__first, *__first); |
| |
| ++__first; |
| if (__t.size() % 2 == 0) |
| { |
| if (__comp(*__first, __result.first)) |
| __result.first = *__first; |
| else |
| __result.second = *__first; |
| ++__first; |
| } |
| |
| while (__first != __last) |
| { |
| _Tp __prev = *__first++; |
| if (__comp(*__first, __prev)) { |
| if ( __comp(*__first, __result.first)) __result.first = *__first; |
| if (!__comp(__prev, __result.second)) __result.second = __prev; |
| } |
| else { |
| if ( __comp(__prev, __result.first)) __result.first = __prev; |
| if (!__comp(*__first, __result.second)) __result.second = *__first; |
| } |
| |
| __first++; |
| } |
| return __result; |
| } |
| |
| template<class _Tp> |
| _LIBCPP_NODISCARD_EXT inline |
| _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| pair<_Tp, _Tp> |
| minmax(initializer_list<_Tp> __t) |
| { |
| return _VSTD::minmax(__t, __less<_Tp>()); |
| } |
| |
| #endif // _LIBCPP_CXX03_LANG |
| |
| // random_shuffle |
| |
| // __independent_bits_engine |
| |
| template <unsigned long long _Xp, size_t _Rp> |
| struct __log2_imp |
| { |
| static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp |
| : __log2_imp<_Xp, _Rp - 1>::value; |
| }; |
| |
| template <unsigned long long _Xp> |
| struct __log2_imp<_Xp, 0> |
| { |
| static const size_t value = 0; |
| }; |
| |
| template <size_t _Rp> |
| struct __log2_imp<0, _Rp> |
| { |
| static const size_t value = _Rp + 1; |
| }; |
| |
| template <class _UIntType, _UIntType _Xp> |
| struct __log2 |
| { |
| static const size_t value = __log2_imp<_Xp, |
| sizeof(_UIntType) * __CHAR_BIT__ - 1>::value; |
| }; |
| |
| template<class _Engine, class _UIntType> |
| class __independent_bits_engine |
| { |
| public: |
| // types |
| typedef _UIntType result_type; |
| |
| private: |
| typedef typename _Engine::result_type _Engine_result_type; |
| typedef typename conditional |
| < |
| sizeof(_Engine_result_type) <= sizeof(result_type), |
| result_type, |
| _Engine_result_type |
| >::type _Working_result_type; |
| |
| _Engine& __e_; |
| size_t __w_; |
| size_t __w0_; |
| size_t __n_; |
| size_t __n0_; |
| _Working_result_type __y0_; |
| _Working_result_type __y1_; |
| _Engine_result_type __mask0_; |
| _Engine_result_type __mask1_; |
| |
| #ifdef _LIBCPP_CXX03_LANG |
| static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min |
| + _Working_result_type(1); |
| #else |
| static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min() |
| + _Working_result_type(1); |
| #endif |
| static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value; |
| static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits; |
| static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits; |
| |
| public: |
| // constructors and seeding functions |
| __independent_bits_engine(_Engine& __e, size_t __w); |
| |
| // generating functions |
| result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());} |
| |
| private: |
| result_type __eval(false_type); |
| result_type __eval(true_type); |
| }; |
| |
| template<class _Engine, class _UIntType> |
| __independent_bits_engine<_Engine, _UIntType> |
| ::__independent_bits_engine(_Engine& __e, size_t __w) |
| : __e_(__e), |
| __w_(__w) |
| { |
| __n_ = __w_ / __m + (__w_ % __m != 0); |
| __w0_ = __w_ / __n_; |
| if (_Rp == 0) |
| __y0_ = _Rp; |
| else if (__w0_ < _WDt) |
| __y0_ = (_Rp >> __w0_) << __w0_; |
| else |
| __y0_ = 0; |
| if (_Rp - __y0_ > __y0_ / __n_) |
| { |
| ++__n_; |
| __w0_ = __w_ / __n_; |
| if (__w0_ < _WDt) |
| __y0_ = (_Rp >> __w0_) << __w0_; |
| else |
| __y0_ = 0; |
| } |
| __n0_ = __n_ - __w_ % __n_; |
| if (__w0_ < _WDt - 1) |
| __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1); |
| else |
| __y1_ = 0; |
| __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) : |
| _Engine_result_type(0); |
| __mask1_ = __w0_ < _EDt - 1 ? |
| _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) : |
| _Engine_result_type(~0); |
| } |
| |
| template<class _Engine, class _UIntType> |
| inline |
| _UIntType |
| __independent_bits_engine<_Engine, _UIntType>::__eval(false_type) |
| { |
| return static_cast<result_type>(__e_() & __mask0_); |
| } |
| |
| template<class _Engine, class _UIntType> |
| _UIntType |
| __independent_bits_engine<_Engine, _UIntType>::__eval(true_type) |
| { |
| const size_t _WRt = numeric_limits<result_type>::digits; |
| result_type _Sp = 0; |
| for (size_t __k = 0; __k < __n0_; ++__k) |
| { |
| _Engine_result_type __u; |
| do |
| { |
| __u = __e_() - _Engine::min(); |
| } while (__u >= __y0_); |
| if (__w0_ < _WRt) |
| _Sp <<= __w0_; |
| else |
| _Sp = 0; |
| _Sp += __u & __mask0_; |
| } |
| for (size_t __k = __n0_; __k < __n_; ++__k) |
| { |
| _Engine_result_type __u; |
| do |
| { |
| __u = __e_() - _Engine::min(); |
| } while (__u >= __y1_); |
| if (__w0_ < _WRt - 1) |
| _Sp <<= __w0_ + 1; |
| else |
| _Sp = 0; |
| _Sp += __u & __mask1_; |
| } |
| return _Sp; |
| } |
| |
| // uniform_int_distribution |
| |
| template<class _IntType = int> |
| class uniform_int_distribution |
| { |
| public: |
| // types |
| typedef _IntType result_type; |
| |
| class param_type |
| { |
| result_type __a_; |
| result_type __b_; |
| public: |
| typedef uniform_int_distribution distribution_type; |
| |
| explicit param_type(result_type __a = 0, |
| result_type __b = numeric_limits<result_type>::max()) |
| : __a_(__a), __b_(__b) {} |
| |
| result_type a() const {return __a_;} |
| result_type b() const {return __b_;} |
| |
| friend bool operator==(const param_type& __x, const param_type& __y) |
| {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;} |
| friend bool operator!=(const param_type& __x, const param_type& __y) |
| {return !(__x == __y);} |
| }; |
| |
| private: |
| param_type __p_; |
| |
| public: |
| // constructors and reset functions |
| #ifndef _LIBCPP_CXX03_LANG |
| uniform_int_distribution() : uniform_int_distribution(0) {} |
| explicit uniform_int_distribution( |
| result_type __a, result_type __b = numeric_limits<result_type>::max()) |
| : __p_(param_type(__a, __b)) {} |
| #else |
| explicit uniform_int_distribution( |
| result_type __a = 0, |
| result_type __b = numeric_limits<result_type>::max()) |
| : __p_(param_type(__a, __b)) {} |
| #endif |
| explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {} |
| void reset() {} |
| |
| // generating functions |
| template<class _URNG> result_type operator()(_URNG& __g) |
| {return (*this)(__g, __p_);} |
| template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p); |
| |
| // property functions |
| result_type a() const {return __p_.a();} |
| result_type b() const {return __p_.b();} |
| |
| param_type param() const {return __p_;} |
| void param(const param_type& __p) {__p_ = __p;} |
| |
| result_type min() const {return a();} |
| result_type max() const {return b();} |
| |
| friend bool operator==(const uniform_int_distribution& __x, |
| const uniform_int_distribution& __y) |
| {return __x.__p_ == __y.__p_;} |
| friend bool operator!=(const uniform_int_distribution& __x, |
| const uniform_int_distribution& __y) |
| {return !(__x == __y);} |
| }; |
| |
| template<class _IntType> |
| template<class _URNG> |
| typename uniform_int_distribution<_IntType>::result_type |
| uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p) |
| _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK |
| { |
| typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t), |
| uint32_t, uint64_t>::type _UIntType; |
| const _UIntType _Rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1); |
| if (_Rp == 1) |
| return __p.a(); |
| const size_t _Dt = numeric_limits<_UIntType>::digits; |
| typedef __independent_bits_engine<_URNG, _UIntType> _Eng; |
| if (_Rp == 0) |
| return static_cast<result_type>(_Eng(__g, _Dt)()); |
| size_t __w = _Dt - __libcpp_clz(_Rp) - 1; |
| if ((_Rp & (numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0) |
| ++__w; |
| _Eng __e( |
