This patch replaces uses of subscripts in heap algorithms, that where introduced
in r16-4100-gaaeca77a79a9a8 with dereference of advanced iterators.
The Cpp17RandomAccessIterator requirements, allows operator[] to return any
type that is convertible to reference, however user-provided comparators are
required only to accept result of dereferencing the iterator (i.e. reference
directly). This is visible, when comparator defines operator() for which
template arguments can be deduduced from reference (which will fail on proxy)
or that accepts types convertible from reference (see included tests).
For test we introduce a new proxy_random_access_iterator_wrapper iterator
in testsuite_iterators.h, that returns a proxy type from subscript operator.
This is separate type (instead of additional template argument and aliases),
as it used for test that work with C++98.
libstdc++-v3/ChangeLog:
* include/bits/stl_heap.h (std::__is_heap_until, std::__push_heap)
(std::__adjust_heap): Replace subscript with dereference of
advanced iterator.
* testsuite/util/testsuite_iterators.h (__gnu_test::subscript_proxy)
(__gnu_test::proxy_random_access_iterator_wrapper): Define.
* testsuite/25_algorithms/sort_heap/check_proxy_brackets.cc: New test.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Tomasz Kamiński <tkaminsk@redhat.com>
The logic of the null pointer check got reversed when converting the
std::stable_sort code for ranges::stable_sort.
libstdc++-v3/ChangeLog:
PR libstdc++/123180
* include/bits/ranges_algo.h (__stable_sort_fn::operator()): Fix
sense of null check. Replace typedef with alias-declaration.
* testsuite/25_algorithms/stable_sort/123180.cc: New test.
Reviewed-by: Patrick Palka <ppalka@redhat.com>
Copying narrow characters to a range of bool using std::copy cannot be
optimized to use std::memcpy. Assignment of an arbitrary integer to a
bool needs to convert all non-zero values to true, so is not a simple
memcpy-like or bit_cast-like operation. We currently get this wrong and
optimize it to memcpy, producing invalid bool values.
By making __memcpyable_integer<bool> false we disable memcpy
optimizations for heterogeneous std::copy and std::move calls where
either the source or destination type is bool. Copies where both types
are bool can still optimize to memcpy, because we don't check
__memcpyable_integer in that case.
This disables the memcpy optimization for bool as the source type,
which isn't actually necessary (the representation of bool in GCC is
0x00 or 0x01 and so copying bool to char is just a bit_cast). We don't
currently have a straightforward way to allow memcpy for bool to char
but disallow the inverse. This seems acceptable as using std::copy with
bool inputs and narrow character outputs is probably not common enough
for this to be an important optimization to do in the library code.
libstdc++-v3/ChangeLog:
PR libstdc++/122907
* include/bits/cpp_type_traits.h (__memcpyable_integer<bool>):
Define as false.
* testsuite/25_algorithms/copy/122907.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Patrick Palka <ppalka@redhat.com>
From the paper's abstract:
Change the iterator requirements for non-Ranges algorithms. For
forward iterators and above that are constant iterators, instead of
requiring that iterators meet certain Cpp17...Iterator requirements,
require that the iterators model certain iterator concepts. This makes
iterators from several standard views usable with non-Ranges
algorithms that require forward iterators or above, such as the
parallel overloads of most algorithms.
This patch narrowly implements P2408R5 in C++23 mode and C++20 mode
(as an extension). "Narrowly" because just as in the paper, we don't
attempt to relax the requirements of mutable iterators even though it's
possible in theory. Note that the PSTL algorithm requirements have
already been relaxed in r15-3650. And we don't bother touching the
deprecated parallel mode algorithms under ./include/parallel.
The main workhorse of this paper is a new helper
__iterator_concept_or_category that replaces eligible uses of
__iterator_category and iterator_traits::iterator_category. This new
helper considers both the iterator_concept and iterator_category of the
given iterator and returns the former if it's at least as strong as the
latter. It's implemented in terms of the __promotable_iterator concept
added in r16-2588 that made std::advance etc aware of C++20 iterators.
Note that this helper doesn't check the actual C++20 iterator concepts
(which check syntactic requirements along with iterator_concept if it's
defined) and instead just checks for, and fully trusts, the
iterator_concept defined by the iterator type. This is a slight
deviation from the paper but IMHO it's consistent with the existing
trusting of iterator_category and should be good enough in practice,
though it means C++20 iterators that don't define iterator_concept will
not be recognized as such by this helper even if they otherwise model
the std::foo_iterator concept. (An undefined iterator_concept
effectively defaults to random_access_iterator_tag.)
Most of the changes made here are effectively optimizations that don't
have a semantic impact, e.g. for std::reduce. I added tests for a
couple of algorithms where these changes are observable.
The new __iterator_concept_or_category helper can probably also be used
to fix PR100070 "Standard library container iterator-pair constructors
should check C++20 iterator concepts".
As a follow-up to this patch we should either remove the Boost-style
concept checks, or relax them accordingly. It seems we're leaning
towards removing them outright; see this thread:
https://gcc.gnu.org/pipermail/libstdc++/2025-May/061568.html
As suggested by Tomasz, this patch also introduces a _GLIBCXX_ITER_MOVE
wrapper around ranges::iter_move that also converts to the iterator's
value type (and is usable before C++20 as well).
PR libstdc++/113299
libstdc++-v3/ChangeLog:
* include/bits/deque.tcc (__copy_move_a1): Constrain with
__is_any_random_access_iter instead of __is_random_access_iter.
(__copy_move_backward_a1): Likewise.
(__equal_aux1): Likewise.
* include/bits/stl_algo.h (__search_n): Use
__iter_concept_or_category instead of __iterator_category
or iterator_traits::iterator_category.
(find_end): Likewise.
(__is_permutation): Likewise.
(for_each_n): Likewise.
(unique_copy): Likewise, for constant iterators.
(sample): Likewise, for constant iterators.
* include/bits/stl_algobase.h (__copy_move_a1): Adjust
deque-based forward declaration accordingly.
(__copy_move_backward_a1): Likewise.
(__equal_aux1): Likewise.
(__lexicographical_compare_impl): Use
__iter_concept_or_category instead of __iterator_category or
iterator_traits::iterator_category.
(__equal4): Likewise.
* include/bits/stl_iterator_base_funcs.h
(__iter_concept_or_category): New.
(__is_any_random_access_iter): New.
(_GLIBCXX_ITER_MOVE): New.
* include/bits/stl_uninitialized.h (uninitialized_copy_n):
Use __iterator_concept_or_category instead of
__iterator_category for the constant iterator __first.
(__uninitialized_copy_n_pair): Likewise.
* include/bits/version.def (algorithm_iterator_requirements):
Define.
* include/bits/version.h: Regenerate.
* include/std/algorithm: Provide the FTM
__cpp_lib_algorithm_iterator_requirements.
* include/std/memory: Likewise.
* include/std/numeric: Likewise. Include
<bits/stl_iterator_base_funcs.h>.
(reduce): Use __is_any_random_access_iter instead of
__is_random_access_iter.
(transform_reduce): Likewise.
(inclusive_scan): Use _GLIBCXX_ITER_MOVE instead of std::move.
* testsuite/25_algorithms/find_end/c++20_iter.cc: New test.
* testsuite/25_algorithms/sample/c++20_iter.cc: New test.
* testsuite/25_algorithms/search_n/c++20_iter.cc: New test.
* testsuite/25_algorithms/unique_copy/c++20_iter.cc: New test.
* testsuite/26_numerics/inclusive_scan/c++20_iter.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
These should be checking for equality, not performing assignments.
The tests for from_range on associative containers were actually
checking the wrong thing, but the bug in the is_equal function was
making the incorrect checks pass anyway, because all the values being
used were non-zero, so the result of lhs.id = rhs.id was true, but would
have been false if lhs.id == rhs.id had been used as intended.
libstdc++-v3/ChangeLog:
* testsuite/21_strings/basic_string/numeric_conversions/char/stoi.cc:
Fix assignment used instead of equality comparison.
* testsuite/21_strings/basic_string/numeric_conversions/char/stol.cc:
Likewise.
* testsuite/21_strings/basic_string/numeric_conversions/char/stoll.cc:
Likewise.
* testsuite/21_strings/basic_string/numeric_conversions/char/stoul.cc:
Likewise.
* testsuite/21_strings/basic_string/numeric_conversions/char/stoull.cc:
Likewise.
* testsuite/21_strings/basic_string/numeric_conversions/wchar_t/stoi.cc:
Likewise.
* testsuite/21_strings/basic_string/numeric_conversions/wchar_t/stol.cc:
Likewise.
* testsuite/21_strings/basic_string/numeric_conversions/wchar_t/stoll.cc:
Likewise.
* testsuite/21_strings/basic_string/numeric_conversions/wchar_t/stoul.cc:
Likewise.
* testsuite/21_strings/basic_string/numeric_conversions/wchar_t/stoull.cc:
Likewise.
* testsuite/23_containers/map/cons/from_range.cc: Fix is_equal
function and expected value of comparison functions after
construction.
* testsuite/23_containers/multimap/cons/from_range.cc: Likewise.
* testsuite/23_containers/multiset/cons/from_range.cc: Likewise.
* testsuite/23_containers/set/cons/from_range.cc: Likewise.
* testsuite/23_containers/unordered_map/cons/from_range.cc: Fix
is_equal functions.
* testsuite/23_containers/unordered_multimap/cons/from_range.cc:
Likewise.
* testsuite/23_containers/unordered_multiset/cons/from_range.cc:
Likewise.
* testsuite/23_containers/unordered_set/cons/from_range.cc:
Likewise.
* testsuite/25_algorithms/minmax/constrained.cc: Fix assignment
used instead of equality comparison.
* testsuite/27_io/manipulators/extended/get_time/wchar_t/1.cc:
Likewise.
ranges::shuffle has a two-at-a-time PRNG optimization (copied from
std::shuffle) that considers the PRNG width vs the size of the range.
But in C++20 a random access sentinel isn't always sized so we can't
unconditionally do __last - __first to obtain the size in constant
time.
We could instead use ranges::distance, but that'd take linear time for a
non-sized sentinel which makes the optimization less clear of a win. So
this patch instead makes us only consider this optimization for sized
ranges.
PR libstdc++/121917
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__shuffle_fn::operator()): Only
consider the two-at-a-time PRNG optimization if the range is
sized.
* testsuite/25_algorithms/shuffle/constrained.cc (test03): New
test.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Using std::move(*it) is incorrect for iterators that use proxy refs, we
should use ranges::iter_move(it) instead.
libstdc++-v3/ChangeLog:
PR libstdc++/121913
* include/bits/ranges_algo.h (__rotate_fn::operator()): Use
ranges::iter_move(it) instead of std::move(*it).
* testsuite/25_algorithms/rotate/121913.cc: New test.
Reviewed-by: Patrick Palka <ppalka@redhat.com>
Whenever we use operator+ or similar operators on random access
iterators we need to be careful to use the iterator's difference_type
rather than some other integer type. It's not guaranteed that an
expression with an arbitrary integer type, such as `it + 1u`, has the
same effects as `it + iter_difference_t<It>(1)`.
Some of our algorithms need changes to cast values to the correct type,
or to use std::next or ranges::next instead of `it + n`. Several tests
also need fixes where the arithmetic occurs directly in the test.
The __gnu_test::random_access_iterator_wrapper class template is
adjusted to have deleted operators that make programs ill-formed if the
argument to relevant operators is not the difference_type. This will
make it easier to avoid regressing in future.
libstdc++-v3/ChangeLog:
PR libstdc++/121890
* include/bits/ranges_algo.h (ranges::rotate, ranges::shuffle)
(__insertion_sort, __unguarded_partition_pivot, __introselect):
Use ranges::next to advance iterators. Use local variables in
rotate to avoid duplicate expressions.
(ranges::push_heap, ranges::pop_heap, ranges::partial_sort)
(ranges::partial_sort_copy): Use ranges::prev.
(__final_insertion_sort): Use iter_difference_t<Iter>
for operand of operator+ on iterator.
* include/bits/ranges_base.h (ranges::advance): Use iterator's
difference_type for all iterator arithmetic.
* include/bits/stl_algo.h (__search_n_aux, __rotate)
(__insertion_sort, __unguarded_partition_pivot, __introselect)
(__final_insertion_sort, for_each_n, random_shuffle): Likewise.
Use local variables in __rotate to avoid duplicate expressions.
* include/bits/stl_algobase.h (__fill_n_a, __lc_rai::__newlast1):
Likewise.
* include/bits/stl_heap.h (push_heap): Likewise.
(__is_heap_until): Add static_assert.
(__is_heap): Convert distance to difference_type.
* include/std/functional (boyer_moore_searcher::operator()): Use
iterator's difference_type for iterator arithmetic.
* testsuite/util/testsuite_iterators.h
(random_access_iterator_wrapper): Add deleted overloads of
operators that should be called with difference_type.
* testsuite/24_iterators/range_operations/advance.cc: Use
ranges::next.
* testsuite/25_algorithms/heap/constrained.cc: Use ranges::next
and ranges::prev.
* testsuite/25_algorithms/nth_element/58800.cc: Use std::next.
* testsuite/25_algorithms/nth_element/constrained.cc: Use
ptrdiff_t for loop variable.
* testsuite/25_algorithms/nth_element/random_test.cc: Use
iterator's difference_type instead of int.
* testsuite/25_algorithms/partial_sort/check_compare_by_value.cc:
Use std::next.
* testsuite/25_algorithms/partial_sort/constrained.cc: Use
ptrdiff_t for loop variable.
* testsuite/25_algorithms/partial_sort/random_test.cc: Use
iterator's difference_type instead of int.
* testsuite/25_algorithms/partial_sort_copy/constrained.cc:
Use ptrdiff_t for loop variable.
* testsuite/25_algorithms/partial_sort_copy/random_test.cc:
Use iterator's difference_type instead of int.
* testsuite/std/ranges/adaptors/drop.cc: Use ranges::next.
* testsuite/25_algorithms/fill_n/diff_type.cc: New test.
* testsuite/25_algorithms/lexicographical_compare/diff_type.cc:
New test.
Reviewed-by: Patrick Palka <ppalka@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
This patch adds the [[nodiscard]] attribute to the operator() of ranges
algorithm function objects if their std counterpart has it.
Furthermore, we [[nodiscard]] the operator() of the following ranges
algorithms that lack a std counterpart:
* find_last, find_last_if, find_last_if_not (to match other find
algorithms)
* contains, contains_subrange (to match find/any_of and search)
Finally, [[nodiscard]] is added to std::min and std::max overloads
that accept std::initializer_list. This appears to be an oversight,
as std::minmax is already marked, and other min overloads are as well.
The same applies to corresponding operator() overloads of ranges::min and
ranges::max.
PR libstdc++/121476
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__all_of_fn::operator()):
(__any_of_fn::operator(), __none_of_fn::operator())
(__find_first_of_fn::operator(), __count_fn::operator())
(__find_end_fn::operator(), __remove_if_fn::operator())
(__remove_fn::operator(), __unique_fn::operator())
(__is_sorted_until_fn::operator(), __is_sorted_fn::operator())
(__lower_bound_fn::operator(), __upper_bound_fn::operator())
(__equal_range_fn::operator(), __binary_search_fn::operator())
(__is_partitioned_fn::operator(), __partition_point_fn::operator())
(__minmax_fn::operator(), __min_element_fn::operator())
(__includes_fn::operator(), __max_fn::operator())
(__lexicographical_compare_fn::operator(), __clamp__fn::operator())
(__find_last_fn::operator(), __find_last_if_fn::operator())
(__find_last_if_not_fn::operator()): Add [[nodiscard]] attribute.
* include/bits/ranges_algobase.h (__equal_fn::operator()):
Add [[nodiscard]] attribute.
* include/bits/ranges_util.h (__find_fn::operator())
(__find_if_fn::operator(), __find_if_not_fn::operator())
(__mismatch_fn::operator(), __search_fn::operator())
(__min_fn::operator(), __adjacent_find_fn::operator()):
Add [[nodiscard]] attribute.
* include/bits/stl_algo.h (std::min(initializer_list<T>))
(std::min(initializer_list<T>, _Compare))
(std::max(initializer_list<T>))
(std::mmax(initializer_list<T>, _Compare)): Add _GLIBCXX_NODISCARD.
* testsuite/25_algorithms/min/constrained.cc: Silence nodiscard
warning.
* testsuite/25_algorithms/max/constrained.cc: Likewise.
* testsuite/25_algorithms/minmax/constrained.cc: Likewise.
* testsuite/25_algorithms/minmax_element/constrained.cc: Likewise.
The implementation is just a copy of std::shift_left/right with the
following changes:
- check bidirectional_iterator instead of iterator_category
- cope with __last being a distinct sentinel type
- for shift_left, return the subrange {__first, X} instead of X
- for shift_right, return the subrange {X, ranges::next(__first, __last)}
instead of X
- use the ranges:: versions of move_backward, move and iter_swap
- don't bother std::move'ing any iterators, it's unnecessary since all
iterators are forward, it's visually noisy, and in earlier versions
of this patch it introduced subtle use-after-move bugs
In passing also use the __glibcxx_shift macro to guard the
std::shift_left/right implementations.
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (shift_left, shift_right): Guard
with __glibcxx_shift >= 201806L.
(ranges::__shift_left_fn, ranges::shift_left): Define for C++23.
(ranges::__shift_right_fn, ranges::shift_right): Likewise.
* include/bits/version.def (shift): Update for C++23.
* include/bits/version.h: Regenerate.
* src/c++23/std.cc.in: Add ranges::shift_left/right.
* testsuite/25_algorithms/shift_left/constrained.cc: New test,
based off of 1.cc.
* testsuite/25_algorithms/shift_right/constrained.cc: New test,
based off of 1.cc.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
PR libstdc++/120789
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__remove_if_fn::operator()): Use
ranges::iter_move(iter) instead of std::move(*iter).
* testsuite/25_algorithms/remove_if/120789.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
PR libstdc++/120789
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__unique_fn::operator()): Use
ranges::iter_move(iter) instead of std::move(*iter).
* testsuite/25_algorithms/unique/120789.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
PR libstdc++/100795
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (shuffle_fn::operator()):
Reimplement directly, based on the stl_algo.h implementation.
* testsuite/25_algorithms/shuffle/constrained.cc (test02):
New test.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
PR libstdc++/100795
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__sample_fn::operator()):
Reimplement the forward_iterator branch directly, based
on the stl_algo.h implementation. Add explicit cast to
_Out's difference_type in the !forward_iterator branch.
* testsuite/25_algorithms/sample/constrained.cc (test02):
New test.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
PR libstdc++/100795
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__detail::__introselect): New,
based on the stl_algo.h implementation.
(nth_element_fn::operator()): Reimplement in terms of the above.
* testsuite/25_algorithms/nth_element/constrained.cc:
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
PR libstdc++/100795
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__detail::__find_if_not_n): New,
based on the stl_algo.h implementation.
(__detail::__stable_partition_adaptive): Likewise.
(__stable_partition_fn::operator()): Reimplement in terms of
the above.
* testsuite/25_algorithms/stable_partition/constrained.cc
(test03): New test.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
As with the previous patch, this patch reimplements ranges::inplace_merge
directly instead of incorrectly forwarding to std::inplace_merge. In
addition to the compatibility changes listed in the previous patch we
also:
- explicitly cast the difference type (which can be an integer class) to
ptrdiff_t when constructing a _Temporary_buffer
PR libstdc++/100795
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__detail::__move_merge_adaptive):
New, based on the stl_algo.h implementation.
(__detail::__move_merge_adaptive_backward): Likewise.
(__detail::__rotate_adaptive): Likewise.
(__detail::__merge_adaptive): Likewise.
(__detail::__merge_adaptive_resize): Likewise.
(__detail::__merge_without_buffer): Likewise.
(__inplace_merge_fn::operator()): Reimplement in terms of the
above.
* testsuite/25_algorithms/inplace_merge/constrained.cc (test03):
New test.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
As with the previous patch, this patch reimplements ranges::sort
directly instead of incorrectly forwarding to std::sort. In addition to
the compatibility changes listed in the previous patch we also:
- use ranges::iter_swap instead of std::iter_swap
- use ranges::move_backward instead of std::move_backward
- use __bit_width and __to_unsigned_like instead of __lg
PR libstdc++/100795
PR libstdc++/118209
libstdc++-v3/ChangeLog:
* include/bits/max_size_type.h (__bit_width): New explicit
specialization for __max_size_type.
* include/bits/ranges_algo.h (__detail::__move_median_to_first):
New, based on the stl_algo.h implementation.
(__detail::__unguarded_liner_insert): Likewise.
(__detail::__insertion_sort): Likewise.
(__detail::__sort_threshold): Likewise.
(__detail::__unguarded_insertion_sort): Likewise.
(__detail::__final_insertion_sort): Likewise.
(__detail::__unguarded_partition): Likewise.
(__detail::__unguarded_partition_pivot): Likewise.
(__detail::__heap_select): Likewise.
(__detail::__partial_sort): Likewise.
(__detail::__introsort_loop): Likewise.
(__sort_fn::operator()): Reimplement in terms of the above.
* testsuite/25_algorithms/sort/118209.cc: New test.
* testsuite/25_algorithms/sort/constrained.cc (test03): New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
ranges::push_heap, ranges::pop_heap, ranges::make_heap and
ranges::sort_heap are currently defined in terms of the corresponding
STL-style algorithms, but this is incorrect because the STL-style
algorithms rely on the legacy iterator system, and so misbehave when
passed a narrowly C++20 random access iterator. The other ranges heap
algos, ranges::is_heap and ranges::is_heap_until, are implemented
directly already and have no known issues.
This patch reimplements these ranges:: algos directly instead, based
closely on the legacy stl_heap.h implementation, with the following
changes for compatibility with the C++20 iterator system:
- handle non-common ranges by computing the corresponding end iterator
- use ranges::iter_move instead of std::move(*iter)
- use iter_value_t / iter_difference_t instead of iterator_traits
Besides these changes, the implementation of these algorithms is
intended to mirror the stl_heap.h implementations, for ease of
maintenance and review.
Note that we don't explicitly pass the projection function throughout,
instead we just create and pass a composite predicate via __make_comp_proj.
PR libstdc++/100795
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__detail::__push_heap): New,
based on the stl_heap.h implementation.
(__push_heap_fn::operator()): Reimplement in terms of the above.
(__detail::__adjust_heap): New, based on the stl_heap.h
implementation.
(__deatil::__pop_heap): Likewise.
(__pop_heap_fn::operator()): Reimplement in terms of the above.
(__make_heap_fn::operator()): Likewise.
(__sort_heap_fn::operator()): Likewise.
* testsuite/25_algorithms/heap/constrained.cc (test03): New
test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
This implements ranges::starts_with and ranges::ends_with from the C++23
paper P1659R3. The corresponding_S_impl member functions take optional
optional size parameters __n1 and __n2 of the two ranges, where -1 means
the corresponding size is not known.
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__starts_with_fn, starts_with):
Define.
(__ends_with_fn, ends_with): Define.
* include/bits/version.def (ranges_starts_ends_with): Define.
* include/bits/version.h: Regenerate.
* include/std/algorithm: Provide __cpp_lib_ranges_starts_ends_with.
* src/c++23/std.cc.in (ranges::starts_with): Export.
(ranges::ends_with): Export.
* testsuite/25_algorithms/ends_with/1.cc: New test.
* testsuite/25_algorithms/starts_with/1.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
The current overload set for __unique_copy handles three cases:
- The input range uses forward iterators, the output range does not.
This is the simplest case, and can just compare adjacent elements of
the input range.
- Neither the input range nor output range use forward iterators.
This requires a local variable copied from the input range and updated
by assigning each element to the local variable.
- The output range uses forward iterators.
For this case we compare the current element from the input range with
the element just written to the output range.
There are two problems with this implementation. Firstly, the third case
assumes that the value type of the output range can be compared to the
value type of the input range, which might not be possible at all, or
might be possible but give different results to comparing elements of
the input range. This is the problem identified in LWG 2439.
Secondly, the third case is used when both ranges use forward iterators,
even though the first case could (and should) be used. This means that
we compare elements from the output range instead of the input range,
with the problems described above (either not well-formed, or might give
the wrong results).
The cause of the second problem is that the overload for the first case
looks like:
OutputIterator
__unique_copy(ForwardIter, ForwardIter, OutputIterator, BinaryPred,
forward_iterator_tag, output_iterator_tag);
When the output range uses forward iterators this overload cannot be
used, because forward_iterator_tag does not inherit from
output_iterator_tag, so is not convertible to it.
To fix these problems we need to implement the resolution of LWG 2439 so
that the third case is only used when the value types of the two ranges
are the same. This ensures that the comparisons are well behaved. We
also need to ensure that the first case is used when both ranges use
forward iterators.
This change replaces a single step of tag dispatching to choose between
three overloads with two step of tag dispatching, choosing between two
overloads at each step. The first step dispatches based on the iterator
category of the input range, ignoring the category of the output range.
The second step only happens when the input range uses non-forward
iterators, and dispatches based on the category of the output range and
whether the value type of the two ranges is the same. So now the cases
that are handled are:
- The input range uses forward iterators.
- The output range uses non-forward iterators or a different value type.
- The output range uses forward iterators and has the same value type.
For the second case, the old code used __gnu_cxx::__ops::__iter_comp_val
to wrap the predicate in another level of indirection. That seems
unnecessary, as we can just use a pointer to the local variable instead
of an iterator referring to it.
During review of this patch, it was discovered that all known
implementations of std::unique_copy and ranges::unique_copy (except
cmcstl2) disagree with the specification. The standard (and the SGI STL
documentation) say that it uses pred(*i, *(i-1)) but everybody uses
pred(*(i-1), *i) instead, and apparently always has done. This patch
adjusts ranges::unique_copy to be consistent.
In the first __unique_copy overload, the local copy of the iterator is
changed to be the previous position not the next one, so that we use
++first as the "next" iterator, consistent with the logic used in the
other overloads. This makes it easier to compare them, because we aren't
using pred(*first, *next) in one and pred(something, *first) in the
others. Instead it's always pred(something, *first).
libstdc++-v3/ChangeLog:
PR libstdc++/120386
* include/bits/ranges_algo.h (__unique_copy_fn): Reorder
arguments for third case to match the first two cases.
* include/bits/stl_algo.h (__unique_copy): Replace three
overloads with two, depending only on the iterator category of
the input range. Dispatch to __unique_copy_1 for the
non-forward case.
(__unique_copy_1): New overloads for the case where the input
range uses non-forward iterators.
(unique_copy): Only pass the input range category to
__unique_copy.
* testsuite/25_algorithms/unique_copy/lwg2439.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
This looks to have been wrong since r0-125454-gea89b2482f97aa which
introduced the predefined_ops.h. Since that change, the binary predicate
passed to std::__unique_copy is _Iter_comp_iter, which takes arguments
of the iterator type, not the iterator's value type.
This removes the checks from the __unique_copy overloads and moves them
into the second overload of std::unique_copy, where we have the original
binary predicate, not the adapted one from predefined_ops.h.
The third __unique_copy overload currently checks that the predicate is
callable with the input range value type and the output range value
type. This change alters that, so that we only ever check that the
predicate can be called with two arguments of the same type. That is
intentional, because calling the predicate with different types is a bug
that will be fixed in a later commit (see PR libstdc++/120386).
libstdc++-v3/ChangeLog:
PR libstdc++/120384
* include/bits/stl_algo.h (__unique_copy): Remove all
_BinaryPredicateConcept concept checks.
(unique_copy): Check _BinaryPredicateConcept in overload that
takes a predicate.
* testsuite/25_algorithms/unique_copy/120384.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Now that the algorithms have been merged we can advertise full support
for P2562R1. This effectively reverts r15-8933-ga264c270fde292.
libstdc++-v3/ChangeLog:
PR libstdc++/119488
* include/bits/version.def (constexpr_algorithms): Bump
the feature-testing macro.
* include/bits/version.h: Regenerate.
* testsuite/25_algorithms/cpp_lib_constexpr.cc: Test the
bumped value for the feature-testing macro.
This completes the implementation of P2562R1 for C++26.
Unlike the other constexpr algorithms of the same family,
stable_partition does not have a constexpr-friendly version "ready to
use" during constant evaluation. In fact, it is not even available on
freestanding, because it always allocates a temporary memory buffer.
This commit implements the simplest possible strategy: during constant
evaluation allocate a buffer of length 1 on the stack, and use that as
a working area.
libstdc++-v3/ChangeLog:
* include/bits/algorithmfwd.h (stable_partition): Mark it
as constexpr for C++26.
* include/bits/ranges_algo.h (__stable_partition_fn): Likewise.
* include/bits/stl_algo.h (stable_partition): Mark it as
constexpr for C++26; during constant evaluation use a new
codepath where a temporary buffer of 1 element is used.
* testsuite/25_algorithms/headers/algorithm/synopsis.cc
(stable_partition): Add constexpr.
* testsuite/25_algorithms/stable_partition/constexpr.cc: New test.
This commit adds support for constexpr inplace_merge, added by P2562R1
for C++26. The implementation strategy is the same as for constexpr
stable_sort: use if consteval to detect if we're in constant evaluation,
and dispatch to a suitable path (same one as freestanding).
libstdc++-v3/ChangeLog:
* include/bits/algorithmfwd.h (inplace_merge): Mark it as
constexpr for C++26.
* include/bits/ranges_algo.h (__inplace_merge_fn): Likewise.
* include/bits/stl_algo.h (inplace_merge): Mark it as constexpr;
during constant evaluation, dispatch to the non-allocating
codepath.
* testsuite/25_algorithms/headers/algorithm/synopsis.cc
(inplace_merge): Add constexpr.
* testsuite/25_algorithms/inplace_merge/constexpr.cc: New test.
P2562R1 ("constexpr Stable Sorting") adds constexpr to stable_sort,
stable_partition and inplace_merge. However only the first is already
implemented in libstdc++, so we shouldn't bump the feature-testing
macro to the bumped C++26 value. This commit sets it to one less
than the final value.
Amends r15-7708-gff43f9853d3b10.
libstdc++-v3/ChangeLog:
* include/bits/version.def (constexpr_algorithms): Change
the value of the feature-testing macro.
* include/bits/version.h: Regenerate.
* testsuite/25_algorithms/cpp_lib_constexpr.cc: Amend the
check of the feature-testing macro.
My P3349R1 paper clarifies that we should be able to lower contiguous
iterators to pointers, without worrying about side effects of individual
increment or dereference operations.
We do need to advance the iterators, and we need to use std::to_address
on the result of advancing them. This ensures that iterators with error
detection get a chance to diagnose bugs. If we don't use std::to_address
on the advanced iterator, it would be possible for a memcpy on the
pointers to overflow a buffer. By performing the += or -= operations and
also using std::to_address, we give the iterator a chance to abort,
throw, or call a violation handler before the buffer overflow happens.
The new tests only check the std::copy* algorithms, because std::move
and std::move_backward use the same implementation details.
libstdc++-v3/ChangeLog:
* include/bits/stl_algobase.h (__nothrow_contiguous_iterator):
Remove.
(__memcpyable_iterators): Simplify.
(__copy_move_a2, __copy_n_a, __copy_move_backward_a2): Call
std::to_address on the iterators after advancing them.
* testsuite/25_algorithms/copy/contiguous.cc: New test.
* testsuite/25_algorithms/copy_backward/contiguous.cc: New test.
* testsuite/25_algorithms/copy_n/contiguous.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
The new test functions I added in r15-7765-g3866ca796d5281 are causing
those tests to FAIL on Solaris and arm-thumb due to the linker
complaining about undefined functions. The new test functions are not
called, so it shouldn't matter that they call undefined member
functions, but it does.
Move those functions to separate { dg-do compile } files so the linker
isn't used and won't complain.
libstdc++-v3/ChangeLog:
PR libstdc++/119110
* testsuite/25_algorithms/move/constrained.cc: Move test06
function to ...
* testsuite/25_algorithms/move/105609.cc: New test.
* testsuite/25_algorithms/move_backward/constrained.cc: Move
test04 function to ...
* testsuite/25_algorithms/move_backward/105609.cc: New test.
The ranges::move and ranges::move_backward algorithms are supposed to
use ranges::iter_move(iter) instead of std::move(*iter), which matters
for an iterator type with an iter_move overload findable by ADL.
Currently those algorithms use std::__assign_one which uses std::move,
so define a new ranges::__detail::__assign_one helper function that uses
ranges::iter_move.
libstdc++-v3/ChangeLog:
PR libstdc++/105609
* include/bits/ranges_algobase.h (__detail::__assign_one): New
helper function.
(__copy_or_move, __copy_or_move_backward): Use new function
instead of std::__assign_one.
* testsuite/25_algorithms/move/constrained.cc: Check that
ADL iter_move is used in preference to std::move.
* testsuite/25_algorithms/move_backward/constrained.cc:
Likewise.
stable_sort has been made constexpr in C++26. Apart from plastering a
few functions with constexpr, there's an implementation challenge, that
is: stable_sort takes different codepaths in case extra memory can be
allocated. Rather than doing some major refactorings, simply use the
non-allocating path during constant evaluation. That's the same codepath
used when extra memory could not be allocated, as well as by
freestanding.
libstdc++-v3/ChangeLog:
* include/bits/algorithmfwd.h (stable_sort): Add constexpr.
* include/bits/ranges_algo.h (__stable_sort_fn): Add constexpr
to the function call operators.
* include/bits/stl_algo.h (__stable_sort): Add constexpr.
During constant evaluation, always use the non-allocating path.
(stable_sort): Add constexpr.
(__inplace_stable_sort): Likewise.
(__merge_without_buffer): Likewise.
* include/bits/version.def (constexpr_algorithms): Bump value
for C++26.
* include/bits/version.h: Regnerate.
* testsuite/25_algorithms/cpp_lib_constexpr.cc: Test the bumped
feature-testing macro.
* testsuite/25_algorithms/headers/algorithm/synopsis.cc: Adapt
the test to constexpr stable_sort.
* testsuite/25_algorithms/stable_sort/constexpr.cc: New test.
Signed-off-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
The code was caching the result of `invoke(proj, *it)` in a local
`auto &&` variable. The problem is that this may create dangling
references, for instance in case `proj` is `std::identity` (the common
case) and `*it` produces a prvalue: lifetime extension does not
apply here due to the expressions involved.
Instead, store (and lifetime-extend) the result of `*it` in a separate
variable, then project that variable. While at it, also forward the
result of the projection to the predicate, so that the predicate can
act on the proper value category.
libstdc++-v3/ChangeLog:
PR libstdc++/118160
PR libstdc++/100249
* include/bits/ranges_algo.h (__is_permutation_fn): Avoid a
dangling reference by storing the result of the iterator
dereference and the result of the projection in two distinct
variables, in order to lifetime-extend each one.
Forward the projected value to the predicate.
* testsuite/25_algorithms/is_permutation/constrained.cc: Add a
test with a range returning prvalues. Test it in a constexpr
context, in order to rely on the compiler to catch UB.
Signed-off-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
As reported in PR118185, std::ranges::clamp does not correctly forward
the projected value to the comparator. Add the missing forward.
libstdc++-v3/ChangeLog:
PR libstdc++/118185
PR libstdc++/100249
* include/bits/ranges_algo.h (__clamp_fn): Correctly forward the
projected value to the comparator.
* testsuite/25_algorithms/clamp/118185.cc: New test.
Signed-off-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
Reviewed-by: Patrick Palka <ppalka@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Note, the PR raises another problem.
If on the same testcase the B b; line is removed, we silently synthetize
operator<=> which will crash at runtime due to returning without a return
statement. That is because the standard says that in that case
it should return static_cast<int>(std::strong_ordering::equal);
but I can't find anywhere wording which would say that if that isn't
valid, the function is deleted.
https://eel.is/c++draft/class.compare#class.spaceship-2.2
seems to talk just about cases where there are some members and their
comparison is invalid it is deleted, but here there are none and it
follows
https://eel.is/c++draft/class.compare#class.spaceship-3.sentence-2
So, we synthetize with tf_none, see the static_cast is invalid, don't
add error_mark_node statement silently, but as the function isn't deleted,
we just silently emit it.
Should the standard be amended to say that the operator should be deleted
even if it has no elements and the static cast from
https://eel.is/c++draft/class.compare#class.spaceship-3.sentence-2
On Fri, Jan 10, 2025 at 12:04:53PM -0500, Jason Merrill wrote:
> That seems pretty obviously what we want, and is what the other compilers
> implement.
This patch implements it then.
2025-01-15 Jakub Jelinek <jakub@redhat.com>
PR c++/118387
* method.cc (build_comparison_op): Set bad if
std::strong_ordering::equal doesn't convert to rettype.
* g++.dg/cpp2a/spaceship-err6.C: Expect another error.
* g++.dg/cpp2a/spaceship-synth17.C: Likewise.
* g++.dg/cpp2a/spaceship-synth-neg6.C: Likewise.
* g++.dg/cpp2a/spaceship-synth-neg7.C: New test.
* testsuite/25_algorithms/default_template_value.cc
(Input::operator<=>): Use auto as return type rather than bool.
Use a local reference for the (now possibly lifetime extended) result of
*__first so that we copy it only when necessary.
PR libstdc++/112349
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__min_fn::operator()): Turn local
object __tmp into a reference.
* include/bits/ranges_util.h (__max_fn::operator()): Likewise.
* testsuite/25_algorithms/max/constrained.cc (test04): New test.
* testsuite/25_algorithms/min/constrained.cc (test04): New test.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
In preparation for the deprecation of is_trivial (P3247R2).
Unfortunately I am unable to fully understand what aspect of triviality
seems to matter for these algorithms, so I just ported is_trivial to its
direct equivalent (trivially copyable + trivially default
constructible.)
libstdc++-v3/ChangeLog:
* include/pstl/algorithm_impl.h (__remove_elements): Port away
from is_trivial.
(__pattern_inplace_merge): Likewise.
* include/pstl/glue_memory_impl.h (uninitialized_copy): Likewise.
(uninitialized_copy_n): Likewise.
(uninitialized_move): Likewise.
(uninitialized_move_n): Likewise.
(uninitialized_default_construct): Likewise.
(uninitialized_default_construct_n): Likewise.
(uninitialized_value_construct): Likewise.
(uninitialized_value_construct_n): Likewise.
* testsuite/20_util/specialized_algorithms/pstl/uninitialized_construct.cc:
Likewise.
* testsuite/20_util/specialized_algorithms/pstl/uninitialized_copy_move.cc:
Likewise.
* testsuite/20_util/specialized_algorithms/pstl/uninitialized_fill_destroy.cc:
Likewise.
* testsuite/25_algorithms/pstl/alg_modifying_operations/partition.cc:
Likewise.
Signed-off-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
We already implement short-circuiting for random access iterators, but
we also need to do so for ranges::equal and ranges::is_permutation when
given sized ranges that are not random access ranges (e.g. std::list).
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__is_permutation_fn::operator()):
Short-circuit for sized ranges with different sizes, as per LWG
3560.
* include/bits/ranges_algobase.h (__equal_fn::operator()):
Likewise.
* include/bits/stl_algo.h (__is_permutation): Use if-constexpr
for random access iterator branches.
* include/bits/stl_algobase.h (__equal4): Likewise.
* testsuite/25_algorithms/equal/lwg3560.cc: New test.
* testsuite/25_algorithms/is_permutation/lwg3560.cc: New test.
Reviewed-by: Patrick Palka <ppalka@redhat.com>
The _GLIBCXX_NODISCARD macro only expands to [[__nodiscard__]] for C++17
and later, but all supported compilers will allow us to use that for
C++11 and C++14 too. Enable it for those older standards, to give
improved diagnostics for users of those older standards.
libstdc++-v3/ChangeLog:
* include/bits/c++config (_GLIBCXX_NODISCARD): Expand for C++11
and C++14.
* testsuite/22_locale/locale/cons/12438.cc: Adjust dg-warning to
expect nodiscard warnings for C++11 and C++14 as well.
* testsuite/22_locale/locale/operations/2.cc: Likewise.
* testsuite/25_algorithms/equal/debug/1_neg.cc: Likewise.
* testsuite/25_algorithms/equal/debug/2_neg.cc: Likewise.
* testsuite/25_algorithms/equal/debug/3_neg.cc: Likewise.
* testsuite/25_algorithms/find_first_of/concept_check_1.cc:
Likewise.
* testsuite/25_algorithms/is_permutation/2.cc: Likewise.
* testsuite/25_algorithms/lexicographical_compare/71545.cc:
Likewise.
* testsuite/25_algorithms/lower_bound/33613.cc: Likewise.
* testsuite/25_algorithms/lower_bound/debug/irreflexive.cc:
Likewise.
* testsuite/25_algorithms/lower_bound/debug/partitioned_neg.cc:
Likewise.
* testsuite/25_algorithms/lower_bound/debug/partitioned_pred_neg.cc: Likewise.
* testsuite/25_algorithms/minmax/3.cc: Likewise.
* testsuite/25_algorithms/search/78346.cc: Likewise.
* testsuite/25_algorithms/search_n/58358.cc: Likewise.
* testsuite/25_algorithms/unique/1.cc: Likewise.
* testsuite/25_algorithms/unique/11480.cc: Likewise.
* testsuite/25_algorithms/upper_bound/33613.cc: Likewise.
* testsuite/25_algorithms/upper_bound/debug/partitioned_neg.cc:
Likewise.
* testsuite/25_algorithms/upper_bound/debug/partitioned_pred_neg.cc: Likewise.
* testsuite/27_io/ios_base/types/fmtflags/bitmask_operators.cc:
Likewise.
* testsuite/27_io/ios_base/types/iostate/bitmask_operators.cc:
Likewise.
* testsuite/27_io/ios_base/types/openmode/bitmask_operators.cc:
Likewise.
* testsuite/ext/concept_checks.cc: Likewise.
* testsuite/ext/is_heap/47709.cc: Likewise.
* testsuite/ext/is_sorted/cxx0x.cc: Likewise.
This removes all the __copy_move class template specializations that
decide how to optimize std::copy and std::copy_n. We can inline those
optimizations into the algorithms, using if-constexpr (and macros for
C++98 compatibility) and remove the code dispatching to the various
class template specializations.
Doing this means we implement the optimization directly for std::copy_n
instead of deferring to std::copy, That avoids the unwanted consequence
of advancing the iterator in copy_n only to take the difference later to
get back to the length that we already had in copy_n originally (as
described in PR 115444).
With the new flattened implementations, we can also lower contiguous
iterators to pointers in std::copy/std::copy_n/std::copy_backwards, so
that they benefit from the same memmove optimizations as pointers.
There's a subtlety though: contiguous iterators can potentially throw
exceptions to exit the algorithm early. So we can only transform the
loop to memmove if dereferencing the iterator is noexcept. We don't
check that incrementing the iterator is noexcept because we advance the
contiguous iterators before using memmove, so that if incrementing would
throw, that happens first. I am writing a proposal (P3349R0) which would
make this unnecessary, so I hope we can drop the nothrow requirements
later.
This change also solves PR 114817 by checking is_trivially_assignable
before optimizing copy/copy_n etc. to memmove. It's not enough to check
that the types are trivially copyable (a precondition for using memmove
at all), we also need to check that the specific assignment that would
be performed by the algorithm is also trivial. Replacing a non-trivial
assignment with memmove would be observable, so not allowed.
libstdc++-v3/ChangeLog:
PR libstdc++/115444
PR libstdc++/114817
* include/bits/stl_algo.h (__copy_n): Remove generic overload
and overload for random access iterators.
(copy_n): Inline generic version of __copy_n here. Do not defer
to std::copy for random access iterators.
* include/bits/stl_algobase.h (__copy_move): Remove.
(__nothrow_contiguous_iterator, __memcpyable_iterators): New
concepts.
(__assign_one, _GLIBCXX_TO_ADDR, _GLIBCXX_ADVANCE): New helpers.
(__copy_move_a2): Inline __copy_move logic and conditional
memmove optimization into the most generic overload.
(__copy_n_a): Likewise.
(__copy_move_backward): Remove.
(__copy_move_backward_a2): Inline __copy_move_backward logic and
memmove optimization into the most generic overload.
* testsuite/20_util/specialized_algorithms/uninitialized_copy/114817.cc:
New test.
* testsuite/20_util/specialized_algorithms/uninitialized_copy_n/114817.cc:
New test.
* testsuite/25_algorithms/copy/114817.cc: New test.
* testsuite/25_algorithms/copy/115444.cc: New test.
* testsuite/25_algorithms/copy_n/114817.cc: New test.
Reviewed-by: Patrick Palka <ppalka@redhat.com>
Input iterators aren't required to be copyable.
libstdc++-v3/ChangeLog:
PR libstdc++/117094
* include/bits/ranges_algobase.h (__fill_fn): Use std::move for
iterator that might not be copyable.
* testsuite/25_algorithms/fill/constrained.cc: Check
non-copyable iterator with sized sentinel.
The result iterator needs to be decremented before writing to it.
Improve the PR 108846 tests for all of std::copy, std::copy_n,
std::copy_backward, and the std::ranges versions.
libstdc++-v3/ChangeLog:
PR libstdc++/117121
* include/bits/ranges_algobase.h (copy_backward): Decrement
output iterator before assigning one element through it.
* testsuite/25_algorithms/copy/108846.cc: Ensure the algorithm's
effects are correct for a single memcpyable element.
* testsuite/25_algorithms/copy_backward/108846.cc: Likewise.
* testsuite/25_algorithms/copy_n/108846.cc: Likewise.
This implements P2248R8 + P3217R0, both approved for C++26.
The changes are mostly mechanical; the struggle is to keep readability
with the pre-P2248 signatures.
* For containers, "classic STL" algorithms and their parallel versions,
introduce a macro and amend their declarations/definitions with it.
The macro either expands to the defaulted parameter or to nothing
in pre-C++26 modes.
* For range algorithms, we need to reorder their template parameters.
I've done so unconditionally, because users cannot rely on template
parameters of algorithms (this is explicitly authorized by
[algorithms.requirements]/15). The defaults are then hidden behind
another macro.
libstdc++-v3/ChangeLog:
* include/bits/iterator_concepts.h: Add projected_value_t.
* include/bits/algorithmfwd.h: Add the default template
parameter to the relevant forward declarations.
* include/pstl/glue_algorithm_defs.h: Likewise.
* include/bits/ranges_algo.h: Add the default template
parameter to range-based algorithms.
* include/bits/ranges_algobase.h: Likewise.
* include/bits/ranges_util.h: Likewise.
* include/bits/ranges_base.h: Add helper macros.
* include/bits/stl_iterator_base_types.h: Add helper macro.
* include/bits/version.def: Add the new feature-testing macro.
* include/bits/version.h: Regenerate.
* include/std/algorithm: Pull the feature-testing macro.
* include/std/ranges: Likewise.
* include/std/deque: Pull the feature-testing macro, add
the default for std::erase.
* include/std/forward_list: Likewise.
* include/std/list: Likewise.
* include/std/string: Likewise.
* include/std/vector: Likewise.
* testsuite/23_containers/default_template_value.cc: New test.
* testsuite/25_algorithms/default_template_value.cc: New test.
Signed-off-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
Co-authored-by: Jonathan Wakely <jwakely@redhat.com>
This is a step towards implementing the C++23 change P2408R5, "Ranges
iterators as inputs to non-Ranges algorithms". C++20 random access
iterators which do not meet the Cpp17RandomAccessIterator requirements
will now be recognized by the PSTL algorithms.
As noted by Patrick, P2408R5 only relaxes the requirements for
non-mutating algorithms, but this relaxes them for all parallel
algorithms. I believe that's OK. A call with a type which previously
didn't compile at all was undefined, so we're allowed to start accepting
those calls if the type satisfies std::random_access_iterator. However,
this also causes a change in behaviour for calls with arguments which
satisfy std::random_access_iterator and meet the Cpp17ForwardIterator
requirements but not the Cpp17RandomAccessIterator requirements. The
algorithms will dispatch to a different implementation now. I believe
that's also OK. The algorithms should give the same results whether
acting on forward iterators or random access iterators, just more
efficiently for the latter.
Additionally, we can optimize the C++17 implementation by using
std::__and_, and use std::__remove_cvref_t and std::__iter_category_t
for readability. This diverges from the upstream PSTL, but since libc++
is no longer using that upstream (so we're the only consumer of this
code) I think it's reasonable to use libstdc++ extensions in localized
places like this. Rebasing this small header on upstream should not be
difficult.
libstdc++-v3/ChangeLog:
PR libstdc++/110512
* include/pstl/execution_impl.h (__are_random_access_iterators):
Recognize C++20 random access iterators, and use more efficient
implementations.
* testsuite/25_algorithms/pstl/110512.cc: New test.
This commit ports the fixes already applied by r13-6372-g822a11a1e642e0
to the range-based versions of copy/move algorithms.
When doing so, a further bug (PR116471) was discovered in the
implementation of the range-based algorithms: although the algorithms
are already constrained by the indirectly_copyable/movable concepts,
there was a failing static_assert in the memmove path.
This static_assert checked that iterator's value type was assignable by
using the is_copy_assignable (move) type traits. However, this is a
problem, because the traits are too strict when checking for constness;
a type like
struct S { S& operator=(S &) = default; };
is trivially copyable (and thus could benefit of the memmove path),
but it does not satisfy is_copy_assignable because the operator takes
by non-const reference.
Now, the reason for the check to be there is because a type with
a deleted assignment operator like
struct E { E& operator=(const E&) = delete; };
is still trivially copyable, but not assignable. We don't want
algorithms like std::ranges::copy to compile because they end up
selecting the memmove path, "ignoring" the fact that E isn't even
copy assignable.
But the static_assert isn't needed here any longer: as noted before,
the ranges algorithms already have the appropriate constraints; and
even if they didn't, there's now a non-discarded codepath to deal with
ranges of length 1 where there is an explicit assignment operation.
Therefore, this commit removes it. (In fact, r13-6372-g822a11a1e642e0
removed the same static_assert from the non-ranges algorithms.)
libstdc++-v3/ChangeLog:
PR libstdc++/108846
PR libstdc++/116471
* include/bits/ranges_algobase.h (__assign_one): New helper
function.
(__copy_or_move): Remove a spurious static_assert; use
__assign_one for memcpyable ranges of length 1.
(__copy_or_move_backward): Likewise.
* testsuite/25_algorithms/copy/108846.cc: Extend to range-based
algorithms, and cover both memcpyable and non-memcpyable
cases.
* testsuite/25_algorithms/copy_backward/108846.cc: Likewise.
* testsuite/25_algorithms/copy_n/108846.cc: Likewise.
* testsuite/25_algorithms/move/108846.cc: Likewise.
* testsuite/25_algorithms/move_backward/108846.cc: Likewise.
Signed-off-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
When RAND_MAX is small and the number of elements being shuffled is
close to it, we get very uneven distributions in std::random_shuffle.
This uses a simple xorshift generator seeded by std::rand if we can't
rely on std::rand itself.
libstdc++-v3/ChangeLog:
PR libstdc++/88935
* include/bits/stl_algo.h (random_shuffle) [RAND_MAX < INT_MAX]:
Use xorshift instead of rand().
* testsuite/25_algorithms/random_shuffle/88935.cc: New test.
Co-authored-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Giovanni Bajo <rasky@develer.com>
libstdc++-v3/ChangeLog:
* testsuite/25_algorithms/contains/1.cc: Verify value of
__cpp_lib_ranges_contains.
* testsuite/25_algorithms/find_last/1.cc: Verify value of
__cpp_lib_ranges_find_last.
* testsuite/26_numerics/iota/2.cc: Verify value of
__cpp_lib_ranges_iota.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
