[gcc r16-6749] libstdc++: Fix handling iterators with proxy subscript in heap algorithms.
Tomasz Kaminski
tkaminsk@gcc.gnu.org
Tue Jan 13 18:15:34 GMT 2026
https://gcc.gnu.org/g:76ad28b11266606fcc1571d0ef92d3f2ef402bfb
commit r16-6749-g76ad28b11266606fcc1571d0ef92d3f2ef402bfb
Author: Tomasz Kamiński <tkaminsk@redhat.com>
Date: Tue Jan 13 16:29:42 2026 +0100
libstdc++: Fix handling iterators with proxy subscript in heap algorithms.
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 operator() for which
template arguments can be deduduced from reference (which will fail on proxy)
or that accepts 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.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Tomasz Kamiński <tkaminsk@redhat.com>
Diff:
---
libstdc++-v3/include/bits/stl_heap.h | 8 +-
.../sort_heap/check_proxy_brackets.cc | 67 +++++++
libstdc++-v3/testsuite/util/testsuite_iterators.h | 198 +++++++++++++++++++++
3 files changed, 269 insertions(+), 4 deletions(-)
diff --git a/libstdc++-v3/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h
index c64553e25718..8c5c5df5266d 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 000000000000..c556c26dfa8d
--- /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 95589b2626d2..caede49e41b5 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
More information about the Libstdc++-cvs
mailing list