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