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