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