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? :-)
>
>>>
>>> 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
>>> >
>>>
