[PATCH] libstdc++: Fix handling iterators with proxy subscript in heap algorithms.
Tomasz Kaminski
tkaminsk@redhat.com
Wed Jan 14 09:08:48 GMT 2026
On Tue, Jan 13, 2026 at 5:22 PM Tomasz Kaminski <tkaminsk@redhat.com> wrote:
>
>
> On Tue, Jan 13, 2026 at 5:15 PM Jonathan Wakely <jwakely@redhat.com>
> wrote:
>
>> On Tue, 13 Jan 2026 at 16:06, Tomasz Kamiński <tkaminsk@redhat.com>
>> 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 <https://eel.is/c++draft/concept.same#concept: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[].
>> 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
>> >
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260114/a851b6d2/attachment-0001.htm>
More information about the Libstdc++
mailing list