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