[PATCH] libstdc++: Teach std::distance and std::advance about C++20 iterators [PR102181]
Tomasz Kaminski
tkaminsk@redhat.com
Mon Jul 28 15:04:54 GMT 2025
Pushed to v16.
On Fri, Jul 25, 2025 at 4:08 PM Patrick Palka <ppalka@redhat.com> wrote:
> On Fri, 18 Jul 2025, Jonathan Wakely wrote:
>
> > When the C++98 std::distance and std::advance functions (and C++11
> > std::next and std::prev) are used with C++20 iterators there can be
> > unexpected results, ranging from compilation failure to decreased
> > performance to undefined behaviour.
> >
> > An iterator which satisfies std::input_iterator but does not meet the
> > Cpp17InputIterator requirements might have std::output_iterator_tag for
> > its std::iterator_traits<I>::iterator_category, which means it currently
> > cannot be used with std::advance at all. However, the implementation of
> > std::advance for a Cpp17InputIterator doesn't do anything that isn't
> > valid for iterator types satsifying C++20 std::input_iterator.
> >
> > Similarly, a type satisfying C++20 std::bidirectional_iterator might be
> > usable with std::prev, if it weren't for the fact that its C++17
> > iterator_category is std::input_iterator_tag.
> >
> > Finally, a type satisfying C++20 std::random_access_iterator might use a
> > slower implementation for std::distance or std::advance if its C++17
> > iterator_category is not std::random_access_iterator_tag.
> >
> > This commit adds a __promotable_iterator concept to detect C++20
> > iterators which explicitly define an iterator_concept member, and which
> > either have no iterator_category, or their iterator_category is weaker
> > than their iterator_concept. This is used by std::distance and
> > std::advance to detect iterators which should dispatch based on their
> > iterator_concept instead of their iterator_category. This means that
> > those functions just work and do the right thing for C++20 iterators
> > which would otherwise fail to compile or have suboptimal performance.
> >
> > This is related to LWG 3197, which considers making it undefined to use
> > std::prev with types which do not meet the Cpp17BidirectionalIterator
> > requirements. I think making it work, as in this commit, is a better
> > solution than banning it (or rejecting it at compile-time as libc++
> > does).
> >
> > libstdc++-v3/ChangeLog:
> >
> > PR libstdc++/102181
> > * include/bits/stl_iterator_base_funcs.h (distance, advance):
> > Check C++20 iterator concepts and handle appropriately.
> > (__detail::__iter_category_converts_to_concept): New concept.
> > (__detail::__promotable_iterator): New concept.
> > * testsuite/24_iterators/operations/cxx20_iterators.cc: New
> > test.
>
> LGTM too
>
> > ---
> >
> > This is something I've been experimenting with to try and remove some of
> > the differences between C++17 iterators and C++20 iterators. It would be
> > really nice if the basic utilities for working with old iterators
> > (std::next, std::distance, etc.) were usable with C++20 iterators.
> >
> > I'm not going to commit this now, because I'm about to be offline for a
> > while. Please take a look, think about whether this works and is safe,
> > and whether it seems like a direction we should pursue.
> >
> > The reason for the __promotable_iterator concept (rather than just
> > checking the C++20 category and dispatching based on that alone) is that
> > some C++17 iterators appear to satisfy the C++20 concepts BUT THEY LIE,
> > e.g. see https://gcc.gnu.org/gcc-15/porting_to.html#cxx20-iterators
> >
> > Iterator adaptors and facades which provide all operators, but which
> > define iterator_category as std::forward_iterator_tag, might satisfy the
> > std::random_access_iterator concept. But if you try to actually use
> > those operators, they fail outside the immediate context. So we need to
> > trust what the iterator tells us: if it has an iterator_category, do not
> > assume we can ignore it. So __promotable_iterator only considers
> > iterators which explicitly define iterator_concept, because those are
> > definitely claiming to be C++20 iterators.
> >
> > If you think this is useful and safe, feel free to push it on my behalf.
> > It passes the testsuite (at least now that _Utf_iterator has the missing
> > bidirectional operations, it failed ext/unicode/view.cc until then).
> >
> > .../include/bits/stl_iterator_base_funcs.h | 68 ++++++++++++++++++-
> > .../operations/cxx20_iterators.cc | 60 ++++++++++++++++
> > 2 files changed, 125 insertions(+), 3 deletions(-)
> > create mode 100644
> libstdc++-v3/testsuite/24_iterators/operations/cxx20_iterators.cc
> >
> > diff --git a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> > index 637159fffc83..f78e5356d090 100644
> > --- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> > +++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> > @@ -130,6 +130,28 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> > __distance(_OutputIterator, _OutputIterator, output_iterator_tag) =
> delete;
> > #endif
> >
> > +#ifdef __glibcxx_concepts
> > +namespace __detail
> > +{
> > + // Satisfied if ITER_TRAITS(Iter)::iterator_category is valid and is
> > + // at least as strong as ITER_TRAITS(Iter)::iterator_concept.
> > + template<typename _Iter>
> > + concept __iter_category_converts_to_concept
> > + = convertible_to<typename __iter_traits<_Iter>::iterator_category,
> > + typename __iter_traits<_Iter>::iterator_concept>;
> > +
> > + // Satisfied if the type is a C++20 iterator that defines
> iterator_concept,
> > + // and its iterator_concept is stronger than its iterator_category
> (if any).
> > + // Used by std::distance and std::advance to detect iterators which
> should
> > + // dispatch based on their C++20 concept not their C++17 category.
> > + template<typename _Iter>
> > + concept __promotable_iterator
> > + = input_iterator<_Iter>
> > + && requires { typename __iter_traits<_Iter>::iterator_concept; }
> > + && ! __iter_category_converts_to_concept<_Iter>;
> > +} // namespace __detail
> > +#endif
> > +
> > /**
> > * @brief A generalization of pointer arithmetic.
> > * @param __first An input iterator.
> > @@ -149,6 +171,24 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> > typename iterator_traits<_InputIterator>::difference_type
> > distance(_InputIterator __first, _InputIterator __last)
> > {
> > +#ifdef __glibcxx_concepts
> > + // A type which satisfies the C++20 random_access_iterator
> concept might
> > + // have input_iterator_tag as its iterator_category type, which
> would
> > + // mean we select the O(n) __distance. Or a C++20
> std::input_iterator
> > + // that is not a Cpp17InputIterator might have
> output_iterator_tag as
> > + // its iterator_category type and then calling __distance with
> > + // std::__iterator_category(__first) would be ill-formed.
> > + // So for C++20 iterator types we can just choose to do the right
> thing.
> > + if constexpr (__detail::__promotable_iterator<_InputIterator>)
> > + {
> > + if constexpr (random_access_iterator<_InputIterator>)
> > + return __last - __first;
> > + else
> > + return std::__distance(std::move(__first), std::move(__last),
> > + input_iterator_tag());
> > + }
> > + else // assume it meets the Cpp17InputIterator requirements:
> > +#endif
> > // concept requirements -- taken care of in __distance
> > return std::__distance(__first, __last,
> > std::__iterator_category(__first));
> > @@ -221,9 +261,31 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> > inline _GLIBCXX17_CONSTEXPR void
> > advance(_InputIterator& __i, _Distance __n)
> > {
> > - // concept requirements -- taken care of in __advance
> > - typename iterator_traits<_InputIterator>::difference_type __d =
> __n;
> > - std::__advance(__i, __d, std::__iterator_category(__i));
> > +#ifdef __glibcxx_concepts
> > + // A type which satisfies the C++20 bidirectional_iterator
> concept might
> > + // have input_iterator_tag as its iterator_category type, which
> would
> > + // mean we select the __advance overload which cannot move
> backwards.
> > + // A C++20 random_access_iterator we might select the O(n)
> __advance
> > + // if it doesn't meet the Cpp17RandomAccessIterator requirements.
> > + // So for C++20 iterator types we can just choose to do the right
> thing.
> > + if constexpr (__detail::__promotable_iterator<_InputIterator>
> > + && ranges::__detail::__is_integer_like<_Distance>)
> > + {
> > + auto __d = static_cast<iter_difference_t<_InputIterator>>(__n);
> > + if constexpr (random_access_iterator<_InputIterator>)
> > + std::__advance(__i, __d, random_access_iterator_tag());
> > + else if constexpr (bidirectional_iterator<_InputIterator>)
> > + std::__advance(__i, __d, bidirectional_iterator_tag());
> > + else
> > + std::__advance(__i, __d, input_iterator_tag());
> > + }
> > + else // assume it meets the Cpp17InputIterator requirements:
> > +#endif
> > + {
> > + // concept requirements -- taken care of in __advance
> > + typename iterator_traits<_InputIterator>::difference_type __d =
> __n;
> > + std::__advance(__i, __d, std::__iterator_category(__i));
> > + }
> > }
> >
> > #if __cplusplus >= 201103L
> > diff --git
> a/libstdc++-v3/testsuite/24_iterators/operations/cxx20_iterators.cc
> b/libstdc++-v3/testsuite/24_iterators/operations/cxx20_iterators.cc
> > new file mode 100644
> > index 000000000000..b613c3793b1a
> > --- /dev/null
> > +++ b/libstdc++-v3/testsuite/24_iterators/operations/cxx20_iterators.cc
> > @@ -0,0 +1,60 @@
> > +// { dg-do run { target c++20 } }
> > +
> > +#include <ranges>
> > +#include <testsuite_iterators.h>
> > +#include <testsuite_hooks.h>
> > +
> > +// Bug 102181 std::advance and std::views::iota<std::int64_t> don't work
> > +void
> > +test_pr102181()
> > +{
> > +#ifdef __SIZEOF_INT128__
> > + using type = unsigned __int128;
> > +#else
> > + using type = unsigned long;
> > +#endif
> > + auto v = std::ranges::iota_view(type(0), type(10));
> > + auto b = v.begin();
> > + VERIFY( std::distance(b, std::next(b)) == 1 );
> > + std::advance(b, std::iter_difference_t<decltype(b)>(1));
> > + VERIFY( *b == 1 );
> > + VERIFY( std::distance(b, v.end()) == 9 );
> > +}
> > +
> > +//
> https://stackoverflow.com/questions/68100775/rangesviewtransform-produces-an-inputiterator-preventing-the-use-of-stdpre
> > +void
> > +test_transform_view_iterator()
> > +{
> > + int a[] = {0, 1, 2, 3};
> > + __gnu_test::random_access_container<int> rr(a);
> > + auto rx = std::ranges::views::transform(rr, std::identity{});
> > + auto re = rx.end();
> > + VERIFY( *std::prev(re) == 3 );
> > + VERIFY( std::distance(rx.begin(), re) == 4 );
> > +
> > + __gnu_test::bidirectional_container<int> br(a);
> > + auto bx = std::ranges::views::transform(br, std::identity{});
> > + auto be = bx.end();
> > + VERIFY( *std::prev(be) == 3 );
> > + VERIFY( std::distance(bx.begin(), be) == 4 );
> > +
> > + __gnu_test::forward_container<int> fr(a);
> > + auto fx = std::ranges::views::transform(br, std::identity{});
> > + auto fb = fx.begin();
> > + VERIFY( *std::next(fb) == 1 );
> > + VERIFY( std::distance(fb, fx.end()) == 4 );
> > +
> > + __gnu_test::test_input_range<int> ir(a);
> > + auto ix = std::ranges::views::transform(ir, std::identity{});
> > + auto ii = ix.begin();
> > + std::advance(ii, 1);
> > + VERIFY( *ii == 1 );
> > + // N.B. cannot use std::distance or std::next here because there is no
> > + // iterator_traits<decltype(ii)>::difference_type for this iterator.
> > +}
> > +
> > +int main()
> > +{
> > + test_pr102181();
> > + test_transform_view_iterator();
> > +}
> > --
> > 2.50.1
> >
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20250728/99d18adb/attachment-0001.htm>
More information about the Libstdc++
mailing list