Michael G. Kazakov b4d2b2f9a3 [libc++][pstl] Implementation of parallel std::lexicographical_compare() based on std::mismatch() (#212366) ... This PR adds an implementation of parallel `std::lexicographical_compare()` based on parallel `std::mismatch()`. The implementation is close to a one-liner: ```c++ auto __res = _Mismatch()(__policy, __first1, __last1, __first2, __last2, [&](_Ref1 __lhs, _Ref2 __rhs) { return !__comp(__lhs, __rhs) && !__comp(__rhs, __lhs); }); ``` Included tests check that: - Semantics of the iterator-only version is correct. - Semantics of the predicated version is correct. - The functions correctly SFINAE out when the first argument is not an execution policy. - The `noexcept` policy is followed. - The `nodiscard` policy is followed. - `static_assert` verifies iterators' categories. Part of #99938.		2026-07-31 09:06:38 +08:00
..
adjacent_find.h
all_of.h	[libc++] Forward std::all_of and std::none_of to std::any_of (#167670)	2025-11-24 11:09:40 +01:00
any_of.h	[libc++] Implement any_of in terms of find_if (#207274)	2026-07-23 09:38:21 -04:00
binary_search.h
clamp.h	[libc++] Consistently use version guards outside namespace macros (#181136)	2026-06-29 14:44:44 +02:00
comp.h	[libc++] Strip cv-refs in __desugars_to specialization for integral types (#208950)	2026-07-21 07:40:22 -04:00
comp_ref_type.h
copy.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
copy_backward.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
copy_if.h	[libc++] Use __in_out_result in the remaining appropriate algorithms (#198156)	2026-05-26 19:06:01 +02:00
copy_move_common.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
copy_n.h	[libc++] Treat negative counts in copy_n & friends as no-ops (#207086)	2026-07-15 13:24:03 -04:00
count.h	[libc++] Make the naming of the iterator_traits aliases consistent (#161661)	2025-10-07 14:42:11 +02:00
count_if.h
equal.h	[libc++] Add segmented iterator optimization to std::equal (#179242)	2026-02-24 10:23:15 +01:00
equal_range.h
fill.h	[libc++] Simplify most of the segmented iterator optimizations (#164797)	2025-11-07 08:27:55 +01:00
fill_n.h	[libc++] Introduce __specialized_algorithms (#167295)	2025-11-25 13:46:19 +01:00
find.h	[libc++] Forward find* algorithms to find_if (#179938)	2026-02-27 14:48:58 -08:00
find_end.h	[libc++] Add __find_end optimizations back (#171374)	2025-12-11 09:46:37 +01:00
find_first_of.h
find_if.h	[libc++] Forward find* algorithms to find_if (#179938)	2026-02-27 14:48:58 -08:00
find_if_not.h	[libc++] Forward find* algorithms to find_if (#179938)	2026-02-27 14:48:58 -08:00
find_segment_if.h	[libc++] Add segmented iterator optimization to std::equal (#179242)	2026-02-24 10:23:15 +01:00
for_each.h	[libcxx] Modify std::__for_each{, _n} to accept r-values in __f (#179451)	2026-02-04 23:15:21 +08:00
for_each_n.h	[libc++] Treat negative counts in copy_n & friends as no-ops (#207086)	2026-07-15 13:24:03 -04:00
for_each_n_segment.h
for_each_segment.h	[libc++] Merge the segmented iterator code for {copy,move}_backward (#165160)	2025-12-11 10:32:24 +01:00
generate.h	[libcxx] Optimize std::generate for segmented iterators (#163006)	2025-10-20 19:37:33 +08:00
generate_n.h	[libc++] Treat negative counts in copy_n & friends as no-ops (#207086)	2026-07-15 13:24:03 -04:00
half_positive.h
in_found_result.h
in_fun_result.h
in_in_out_result.h
in_in_result.h
in_out_out_result.h
in_out_result.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
includes.h
inplace_merge.h
is_heap.h
is_heap_until.h	[libc++] Optimize std::is_heap_until (#209141)	2026-07-16 16:46:46 +02:00
is_partitioned.h
is_permutation.h	[libc++] Make the naming of the iterator_traits aliases consistent (#161661)	2025-10-07 14:42:11 +02:00
is_sorted.h
is_sorted_until.h
iter_swap.h
iterator_operations.h	[libc++] Merge the implementations of ranges::copy_n and std::copy_n and fix vector::insert to assign (#157444)	2025-11-27 15:50:50 +01:00
lexicographical_compare.h	[libc++] Refactor __libcpp_is_trivially_equality_comparable to be a variable template (#173151)	2025-12-22 10:04:47 +01:00
lexicographical_compare_three_way.h	[libc++] Consistently use version guards outside namespace macros (#181136)	2026-06-29 14:44:44 +02:00
lower_bound.h	[libc++] Remove projection from __lower_bound_onesided (#206676)	2026-07-01 23:06:43 +02:00
make_heap.h	[libc++] Make the naming of the iterator_traits aliases consistent (#161661)	2025-10-07 14:42:11 +02:00
make_projected.h
max.h
max_element.h
merge.h
min.h
min_element.h
min_max_result.h
minmax.h
minmax_element.h
mismatch.h	[libc++] Refactor __libcpp_is_trivially_equality_comparable to be a variable template (#173151)	2025-12-22 10:04:47 +01:00
move.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
move_backward.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
next_permutation.h
none_of.h	[libc++] Forward std::all_of and std::none_of to std::any_of (#167670)	2025-11-24 11:09:40 +01:00
nth_element.h
out_value_result.h	[libc++] Consistently use version guards outside namespace macros (#181136)	2026-06-29 14:44:44 +02:00
partial_sort.h	[libc++] Improve the performance of std::make_heap a bit (#154092)	2025-09-08 12:00:04 +02:00
partial_sort_copy.h	[libc++] Use __in_out_result in the remaining appropriate algorithms (#198156)	2026-05-26 19:06:01 +02:00
partition.h
partition_copy.h
partition_point.h
pop_heap.h
prev_permutation.h
pstl.h	[libc++][pstl] Implementation of parallel std::lexicographical_compare() based on std::mismatch() (#212366)	2026-07-31 09:06:38 +08:00
push_heap.h
radix_sort.h	[libc++] Consistently use version guards outside namespace macros (#181136)	2026-06-29 14:44:44 +02:00
ranges_adjacent_find.h
ranges_all_of.h
ranges_any_of.h
ranges_binary_search.h
ranges_clamp.h
ranges_contains.h
ranges_contains_subrange.h
ranges_copy.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
ranges_copy_backward.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
ranges_copy_if.h	[libc++] Use __in_out_result in the remaining appropriate algorithms (#198156)	2026-05-26 19:06:01 +02:00
ranges_copy_n.h	[libc++] Consistently use version guards outside namespace macros (#181136)	2026-06-29 14:44:44 +02:00
ranges_count.h
ranges_count_if.h
ranges_ends_with.h
ranges_equal.h	[libc++] Fix use of static in constexpr (#175667)	2026-01-14 06:08:14 -08:00
ranges_equal_range.h
ranges_fill.h	[libc++] Optimize std::{,ranges}::{fill,fill_n} for segmented iterators (#132665)	2025-10-17 07:41:24 +08:00
ranges_fill_n.h
ranges_find.h
ranges_find_end.h
ranges_find_first_of.h
ranges_find_if.h	[libc++] Forward find* algorithms to find_if (#179938)	2026-02-27 14:48:58 -08:00
ranges_find_if_not.h	[libc++] Forward find* algorithms to find_if (#179938)	2026-02-27 14:48:58 -08:00
ranges_find_last.h
ranges_fold.h	[libc++] Implement ranges::fold_right_last (completes P2322R6) (#195580)	2026-05-11 18:35:15 +08:00
ranges_for_each.h	[libc++] Optimize {std,ranges}::for_each for iterating over __trees (#164405)	2025-12-12 09:05:51 +01:00
ranges_for_each_n.h	[libc++] Treat negative counts in copy_n & friends as no-ops (#207086)	2026-07-15 13:24:03 -04:00
ranges_generate.h
ranges_generate_n.h	[libcxx] Optimize rng::generate_n for segmented iterators (#165280)	2025-10-28 22:22:26 +08:00
ranges_includes.h
ranges_inplace_merge.h
ranges_is_heap.h
ranges_is_heap_until.h
ranges_is_partitioned.h
ranges_is_permutation.h
ranges_is_sorted.h
ranges_is_sorted_until.h
ranges_iterator_concept.h
ranges_lexicographical_compare.h
ranges_lower_bound.h
ranges_make_heap.h
ranges_max.h
ranges_max_element.h
ranges_merge.h
ranges_min.h
ranges_min_element.h
ranges_minmax.h
ranges_minmax_element.h
ranges_mismatch.h
ranges_move.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
ranges_move_backward.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
ranges_next_permutation.h
ranges_none_of.h
ranges_nth_element.h
ranges_partial_sort.h
ranges_partial_sort_copy.h	[libc++] Use __in_out_result in the remaining appropriate algorithms (#198156)	2026-05-26 19:06:01 +02:00
ranges_partition.h
ranges_partition_copy.h
ranges_partition_point.h
ranges_pop_heap.h
ranges_prev_permutation.h
ranges_push_heap.h
ranges_remove.h
ranges_remove_copy.h
ranges_remove_copy_if.h
ranges_remove_if.h	[libc++] Forward find* algorithms to find_if (#179938)	2026-02-27 14:48:58 -08:00
ranges_replace.h
ranges_replace_copy.h
ranges_replace_copy_if.h
ranges_replace_if.h
ranges_reverse.h
ranges_reverse_copy.h	[libc++] Use views::reverse to implement ranges::reverse_copy (#177123)	2026-02-04 20:58:16 +01:00
ranges_rotate.h
ranges_rotate_copy.h
ranges_sample.h
ranges_search.h
ranges_search_n.h	[libc++] Optimize search_n (#171389)	2026-01-08 11:26:08 +01:00
ranges_set_difference.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
ranges_set_intersection.h
ranges_set_symmetric_difference.h
ranges_set_union.h
ranges_shift_left.h	[libc++][ranges] implement ranges::shift_left (#83231)	2026-01-25 10:35:43 +00:00
ranges_shift_right.h	[libc++] Implement ranges::shift_right (#177847)	2026-02-14 17:34:44 +00:00
ranges_shuffle.h
ranges_sort.h
ranges_sort_heap.h
ranges_stable_partition.h
ranges_stable_sort.h
ranges_starts_with.h
ranges_swap_ranges.h	[libc++] Forward calls to ranges::swap_ranges to the 3-leg implementation if possible (#176762)	2026-01-27 16:25:41 +01:00
ranges_transform.h
ranges_unique.h
ranges_unique_copy.h	[libc++] Use __in_out_result in the remaining appropriate algorithms (#198156)	2026-05-26 19:06:01 +02:00
ranges_upper_bound.h
remove.h
remove_copy.h
remove_copy_if.h
remove_if.h
replace.h
replace_copy.h
replace_copy_if.h
replace_if.h
reverse.h
reverse_copy.h
rotate.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
rotate_copy.h
sample.h
search.h
search_n.h	[libc++] Optimize search_n (#171389)	2026-01-08 11:26:08 +01:00
set_difference.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
set_intersection.h	[libc++] Remove projection from __lower_bound_onesided (#206676)	2026-07-01 23:06:43 +02:00
set_symmetric_difference.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
set_union.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
shift_left.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
shift_right.h	[libc++] Introduce a private version of in_out_result and use it for copy/move algorithms (#198086)	2026-05-17 10:06:05 +02:00
shuffle.h	[libc++] Introduce implicit and explicit ABI annotations (#193045)	2026-05-08 12:21:31 +02:00
sift_down.h	[libc++] Make the naming of the iterator_traits aliases consistent (#161661)	2025-10-07 14:42:11 +02:00
simd_utils.h	[clang][X86] Emit AVX level mismatch psABI warnings on function definitions (#199091)	2026-07-07 11:16:56 -04:00
sort.h	[libc++] Introduce implicit and explicit ABI annotations (#193045)	2026-05-08 12:21:31 +02:00
sort_heap.h
specialized_algorithms.h	[libc++] Refactor swap_ranges to use __specialized_algorithm for the vector<bool>::iterator specialization (#173384)	2026-01-29 11:11:51 +01:00
stable_partition.h
stable_sort.h	[libc++] Make the naming of the iterator_traits aliases consistent (#161661)	2025-10-07 14:42:11 +02:00
swap_ranges.h	[libc++] Refactor swap_ranges to use __specialized_algorithm for the vector<bool>::iterator specialization (#173384)	2026-01-29 11:11:51 +01:00
three_way_comp_ref_type.h	[libc++] Consistently use version guards outside namespace macros (#181136)	2026-06-29 14:44:44 +02:00
transform.h
uniform_random_bit_generator_adaptor.h
unique.h
unique_copy.h	[libc++] Use __in_out_result in the remaining appropriate algorithms (#198156)	2026-05-26 19:06:01 +02:00
unwrap_iter.h	[libc++] Simplify __unwrap_iter a bit (#175153)	2026-01-13 17:01:02 +01:00
unwrap_range.h	[libc++] Fix module builds for <__algorithm/unwrap_range.h> (#179887)	2026-02-06 09:42:49 +08:00
upper_bound.h