On Wed, Jan 14, 2026 at 10:22 AM Jonathan Wakely <[email protected]> wrote:
> On Wed, 14 Jan 2026 at 09:09, Tomasz Kaminski <[email protected]> wrote: > > > > > > > > On Tue, Jan 13, 2026 at 5:22 PM Tomasz Kaminski <[email protected]> > wrote: > >> > >> > >> > >> On Tue, Jan 13, 2026 at 5:15 PM Jonathan Wakely <[email protected]> > wrote: > >>> > >>> On Tue, 13 Jan 2026 at 16:06, Tomasz Kamiński <[email protected]> > wrote: > >>> > > >>> > 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 template > operator() for > >>> > which arguments can be detected from reference (which will fail on > proxy) or > >>> > 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. > >>> > --- > >>> > In future we could replace random_access_iterator_wrapper with > >>> > proxy_random_access_iterator_wrapper so it is used in all test. > However, > >>> > we should think about contingous_iterator_wrapper, and this is much > >>> > larger change. > >>> > >>> Ah OK. I was hoping we would change the existing class template > >>> because that would mean the new proxy would be used by all the > >>> existing tests that use random_access_iterator_wrapper. I probably > >>> won't remember to use the new type when I write tests :-) > >> > >> I think we should do that in the future (soonish), after double checking > >> the contiguous iterator requirement, as I was not sure if it can return > a proxy, > >> I wanted to deliver the fix quickly, so limited scope of the changes. > > > > Unfortunately I think we need to keep both version of iterators, as > > proxy_random_access_iterator is Cpp17RandomAccessIterator but does not > > satisfy random_access_iterator concept ( > https://eel.is/c++draft/iterator.concept.random.access) > > due: > > { j[n] } -> same_as<iter_reference_t<I>>; > > > > This is interesting, as random_access_iterator allows using proxy as > reference > > (so in operator* and operator[]), but Cpp17RandomAccessIterator requires > T& > > on operator*, but allows subscript on operator[]. > > Ugh, such "fun". > > Could you add a comment to the new proxy_r_a_iterator_wrapper class > saying what you wrote above, so I don't forget and waste time trying > to merge them in future? :-) > Yes, that is a good idea. I will take a look into reducing duplication. > > > > > >>> > >>> But I hadn't realised that it wouldn't be a drop-in replacement, so I > >>> agree we should make it a separate type for now. > >>> > >>> > >>> > > >>> > Testing on x86_64-linux. The new file passed with C++98-26 and > >>> > with/without -m32 and local test pased. OK for trunk when all test > >>> > passes. > >>> > >>> Did you test with PCH enabled? I don't think the #undef in the new > >>> test will do anything if PCH is enabled (because the library headers > >>> will be included already). But we have that #undef in other tests for > >>> heap algos (since 2007) so I guess it either works, or it's harmless. > >> > >> Just started with a copy paste from another test, and haven't removed > it. > >>> > >>> > >>> OK for trunk when testing finishes - thanks for fixing it quickly. > >>> > >>> > > >>> > > >>> > libstdc++-v3/include/bits/stl_heap.h | 8 +- > >>> > .../sort_heap/check_proxy_brackets.cc | 67 ++++++ > >>> > .../testsuite/util/testsuite_iterators.h | 198 > ++++++++++++++++++ > >>> > 3 files changed, 269 insertions(+), 4 deletions(-) > >>> > create mode 100644 > libstdc++-v3/testsuite/25_algorithms/sort_heap/check_proxy_brackets.cc > >>> > > >>> > diff --git a/libstdc++-v3/include/bits/stl_heap.h > b/libstdc++-v3/include/bits/stl_heap.h > >>> > index c64553e2571..8c5c5df5266 100644 > >>> > --- a/libstdc++-v3/include/bits/stl_heap.h > >>> > +++ b/libstdc++-v3/include/bits/stl_heap.h > >>> > @@ -85,7 +85,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>> > _Distance __parent = 0; > >>> > for (_Distance __child = 1; __child < __n; ++__child) > >>> > { > >>> > - if (__comp(__first[__parent], __first[__child])) > >>> > + if (__comp(*(__first + __parent), *(__first + __child))) > >>> > return __child; > >>> > if ((__child & 1) == 0) > >>> > ++__parent; > >>> > @@ -143,7 +143,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>> > _Compare& __comp) > >>> > { > >>> > _Distance __parent = (__holeIndex - 1) / 2; > >>> > - while (__holeIndex > __topIndex && __comp(__first[__parent], > __value)) > >>> > + while (__holeIndex > __topIndex && __comp(*(__first + > __parent), __value)) > >>> > { > >>> > *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + > __parent)); > >>> > __holeIndex = __parent; > >>> > @@ -233,8 +233,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>> > while (__secondChild < (__len - 1) / 2) > >>> > { > >>> > __secondChild = 2 * (__secondChild + 1); > >>> > - if (__comp(__first[__secondChild], > >>> > - __first[__secondChild - 1])) > >>> > + if (__comp(*(__first + __secondChild), > >>> > + *(__first + _Distance(__secondChild - 1)))) > >>> > __secondChild--; > >>> > *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + > __secondChild)); > >>> > __holeIndex = __secondChild; > >>> > diff --git > a/libstdc++-v3/testsuite/25_algorithms/sort_heap/check_proxy_brackets.cc > b/libstdc++-v3/testsuite/25_algorithms/sort_heap/check_proxy_brackets.cc > >>> > new file mode 100644 > >>> > index 00000000000..c556c26dfa8 > >>> > --- /dev/null > >>> > +++ > b/libstdc++-v3/testsuite/25_algorithms/sort_heap/check_proxy_brackets.cc > >>> > @@ -0,0 +1,67 @@ > >>> > +// { dg-do run } > >>> > + > >>> > +#undef _GLIBCXX_CONCEPT_CHECKS > >>> > + > >>> > +#include <algorithm> > >>> > +#include <testsuite_hooks.h> > >>> > +#include <testsuite_iterators.h> > >>> > +#include <utility> > >>> > + > >>> > +using __gnu_test::test_container; > >>> > +using __gnu_test::proxy_random_access_iterator_wrapper; > >>> > + > >>> > +typedef std::pair<int, int> V; > >>> > +typedef test_container<V, proxy_random_access_iterator_wrapper> > Container; > >>> > + > >>> > +struct Deduced > >>> > +{ > >>> > + template<typename A, typename B> > >>> > + bool operator()(const std::pair<A, B>& lhs, > >>> > + const std::pair<A, B>& rhs) const > >>> > + { return lhs.first < rhs.first; } > >>> > +}; > >>> > + > >>> > +struct Conversion > >>> > +{ > >>> > + struct First > >>> > + { > >>> > + First(const V& p) : v(p.first) > >>> > + {} > >>> > + > >>> > + int v; > >>> > + }; > >>> > + > >>> > + bool operator()(First lhs, First rhs) const > >>> > + { return lhs.v < rhs.v; } > >>> > +}; > >>> > + > >>> > +template<typename Cmp> > >>> > +void > >>> > +test01(Cmp cmp) > >>> > +{ > >>> > + V s1[] = { V(0, 10), V(8, 18), V(6, 16), V(7, 17), V(9, 19), > >>> > + V(5, 15), V(4, 14), V(3, 13), V(2, 12), V(1, 11) }; > >>> > + const int N = sizeof(s1) / sizeof(V); > >>> > + Container con(s1, s1 + N); > >>> > + > >>> > + std::make_heap(con.begin(), con.end() - std::ptrdiff_t(2), cmp); > >>> > + std::push_heap(con.begin(), con.end() - std::ptrdiff_t(1), cmp); > >>> > + std::push_heap(con.begin(), con.end(), cmp); > >>> > +#if __cplusplus >= 201103L > >>> > + (void)std::is_heap_until(con.begin(), con.end(), cmp); > >>> > +#endif > >>> > + std::sort_heap(con.begin(), con.end(), cmp); > >>> > + for(int i = 0; i < N; ++i) > >>> > + { > >>> > + VERIFY( s1[i].first == i ); > >>> > + VERIFY( s1[i].second == 10 + i ); > >>> > + } > >>> > +} > >>> > + > >>> > +int > >>> > +main() > >>> > +{ > >>> > + test01(Deduced()); > >>> > + test01(Conversion()); > >>> > + return 0; > >>> > +} > >>> > diff --git a/libstdc++-v3/testsuite/util/testsuite_iterators.h > b/libstdc++-v3/testsuite/util/testsuite_iterators.h > >>> > index 95589b2626d..caede49e41b 100644 > >>> > --- a/libstdc++-v3/testsuite/util/testsuite_iterators.h > >>> > +++ b/libstdc++-v3/testsuite/util/testsuite_iterators.h > >>> > @@ -664,6 +664,204 @@ namespace __gnu_test > >>> > #endif > >>> > > >>> > > >>> > + template<typename T> > >>> > + struct subscript_proxy > >>> > + { > >>> > + _GLIBCXX_CONSTEXPR > >>> > + operator T&() const > >>> > + { return *ptr; } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + subscript_proxy& operator=(const T& val) > >>> > + { > >>> > + *ptr = val; > >>> > + return *this; > >>> > + } > >>> > + > >>> > + T* ptr; > >>> > + }; > >>> > + > >>> > + template<typename T> > >>> > + struct subscript_proxy<const T> > >>> > + { > >>> > + _GLIBCXX_CONSTEXPR > >>> > + operator const T&() const > >>> > + { return *ptr; } > >>> > + > >>> > + const T* ptr; > >>> > + }; > >>> > + > >>> > + /** > >>> > + * @brief random_access_iterator wrapper for pointer, > >>> > + * that returns proxy from subscript. > >>> > + * > >>> > + * This class takes a pointer and wraps it to provide exactly > >>> > + * the requirements of a random_access_iterator. It should not be > >>> > + * instantiated directly, but generated from a test_container > >>> > + */ > >>> > + template<class T> > >>> > + struct proxy_random_access_iterator_wrapper > >>> > + : public bidirectional_iterator_wrapper<T> > >>> > + { > >>> > + typedef BoundsContainer<T> ContainerType; > >>> > + typedef std::random_access_iterator_tag iterator_category; > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper(T* _ptr, ContainerType* > SharedInfo_in) > >>> > + : bidirectional_iterator_wrapper<T>(_ptr, SharedInfo_in) > >>> > + { } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper() > >>> > + : bidirectional_iterator_wrapper<T>() > >>> > + { } > >>> > + > >>> > +#if __cplusplus >= 201103L > >>> > + proxy_random_access_iterator_wrapper( > >>> > + const proxy_random_access_iterator_wrapper&) = default; > >>> > + > >>> > + proxy_random_access_iterator_wrapper& > >>> > + operator=(const proxy_random_access_iterator_wrapper&) = > default; > >>> > +#endif > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper& > >>> > + operator++() > >>> > + { > >>> > + ITERATOR_VERIFY(this->SharedInfo && this->ptr < > this->SharedInfo->last); > >>> > + this->ptr++; > >>> > + return *this; > >>> > + } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper > >>> > + operator++(int) > >>> > + { > >>> > + proxy_random_access_iterator_wrapper<T> tmp = *this; > >>> > + ++*this; > >>> > + return tmp; > >>> > + } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper& > >>> > + operator--() > >>> > + { > >>> > + ITERATOR_VERIFY(this->SharedInfo && this->ptr > > this->SharedInfo->first); > >>> > + this->ptr--; > >>> > + return *this; > >>> > + } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper > >>> > + operator--(int) > >>> > + { > >>> > + proxy_random_access_iterator_wrapper<T> tmp = *this; > >>> > + --*this; > >>> > + return tmp; > >>> > + } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper& > >>> > + operator+=(std::ptrdiff_t n) > >>> > + { > >>> > + if(n > 0) > >>> > + { > >>> > + ITERATOR_VERIFY(n <= this->SharedInfo->last - this->ptr); > >>> > + this->ptr += n; > >>> > + } > >>> > + else > >>> > + { > >>> > + ITERATOR_VERIFY(-n <= this->ptr - this->SharedInfo->first); > >>> > + this->ptr += n; > >>> > + } > >>> > + return *this; > >>> > + } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper& > >>> > + operator-=(std::ptrdiff_t n) > >>> > + { return *this += -n; } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper > >>> > + operator-(std::ptrdiff_t n) const > >>> > + { > >>> > + proxy_random_access_iterator_wrapper<T> tmp = *this; > >>> > + return tmp -= n; > >>> > + } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + std::ptrdiff_t > >>> > + operator-(const proxy_random_access_iterator_wrapper<T>& in) > const > >>> > + { > >>> > + ITERATOR_VERIFY(this->SharedInfo == in.SharedInfo); > >>> > + return this->ptr - in.ptr; > >>> > + } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + subscript_proxy<T> > >>> > + operator[](std::ptrdiff_t n) const > >>> > + { > >>> > + subscript_proxy<T> tmp = { *this + n }; > >>> > + return tmp; > >>> > + } > >>> > + > >>> > +#if __cplusplus >= 201103L > >>> > + // Ensure that the iterator's difference_type is always used. > >>> > + template<typename D> void operator+=(D) = delete; > >>> > + template<typename D> void operator-=(D) = delete; > >>> > + template<typename D> void operator[](D) const = delete; > >>> > + template<typename D> > >>> > + typename std::enable_if<std::is_integral<D>::value>::type > >>> > + operator-(D) const = delete; > >>> > +#endif > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + bool operator<(const proxy_random_access_iterator_wrapper<T>& > in) const > >>> > + { > >>> > + ITERATOR_VERIFY(this->SharedInfo == in.SharedInfo); > >>> > + return this->ptr < in.ptr; > >>> > + } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + bool operator>(const proxy_random_access_iterator_wrapper<T>& > in) const > >>> > + { > >>> > + return in < *this; > >>> > + } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + bool operator>=(const proxy_random_access_iterator_wrapper<T>& > in) const > >>> > + { > >>> > + return !(*this < in); > >>> > + } > >>> > + > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + bool operator<=(const proxy_random_access_iterator_wrapper<T>& > in) const > >>> > + { > >>> > + return !(*this > in); > >>> > + } > >>> > + }; > >>> > + > >>> > + template<typename T> > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper<T> > >>> > + operator+(proxy_random_access_iterator_wrapper<T> it, > std::ptrdiff_t n) > >>> > + { return it += n; } > >>> > + > >>> > + template<typename T> > >>> > + _GLIBCXX14_CONSTEXPR > >>> > + proxy_random_access_iterator_wrapper<T> > >>> > + operator+(std::ptrdiff_t n, > proxy_random_access_iterator_wrapper<T> it) > >>> > + { return it += n; } > >>> > + > >>> > +#if __cplusplus >= 201103L > >>> > + // Ensure that the iterator's difference_type is always used. > >>> > + template<typename T, typename D> > >>> > + void operator+(proxy_random_access_iterator_wrapper<T>, D) = > delete; > >>> > + template<typename T, typename D> > >>> > + void operator+(D, proxy_random_access_iterator_wrapper<T>) = > delete; > >>> > +#endif > >>> > + > >>> > /** > >>> > * @brief A container-type class for holding iterator wrappers > >>> > * test_container takes two parameters, a class T and an iterator > >>> > -- > >>> > 2.52.0 > >>> > > >>> > >
