This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Troubles with the rvalref changes to the *_heap functions
Hi again,
the below finally passes all my tests (heap/moveable.h is fixed wrt
those typos and extended). The basic idea is moving the __push_heap call
out of __adjust_heap. Maybe I can clean-up the code a bit more, but this
is version is algorithmically very safe (at least in the C++98 mode) and
should allow people to start playing with *_heap functions now only
requiring move-ability for the underlying ValueType. Tested
x86_64-linux. Will wait a bit more in case of comments or other
suggestions...
Paolo.
//////////////////
Index: include/bits/stl_heap.h
===================================================================
--- include/bits/stl_heap.h (revision 129230)
+++ include/bits/stl_heap.h (working copy)
@@ -62,6 +62,7 @@
#define _STL_HEAP_H 1
#include <debug/debug.h>
+#include <bits/stl_move.h>
_GLIBCXX_BEGIN_NAMESPACE(std)
@@ -121,11 +122,11 @@
_Distance __parent = (__holeIndex - 1) / 2;
while (__holeIndex > __topIndex && *(__first + __parent) < __value)
{
- *(__first + __holeIndex) = *(__first + __parent);
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
__holeIndex = __parent;
__parent = (__holeIndex - 1) / 2;
}
- *(__first + __holeIndex) = __value;
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
}
/**
@@ -153,8 +154,9 @@
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap(__first, __last - 1);
+ _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _ValueType(*(__last - 1)));
+ _DistanceType(0), _GLIBCXX_MOVE(__value));
}
template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
@@ -167,11 +169,11 @@
while (__holeIndex > __topIndex
&& __comp(*(__first + __parent), __value))
{
- *(__first + __holeIndex) = *(__first + __parent);
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
__holeIndex = __parent;
__parent = (__holeIndex - 1) / 2;
}
- *(__first + __holeIndex) = __value;
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
}
/**
@@ -201,44 +203,51 @@
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap_pred(__first, __last - 1, __comp);
+ _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _ValueType(*(__last - 1)), __comp);
+ _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
}
- template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
- void
+ template<typename _RandomAccessIterator, typename _Distance>
+ _Distance
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
- _Distance __len, _Tp __value)
+ _Distance __len)
{
- const _Distance __topIndex = __holeIndex;
_Distance __secondChild = __holeIndex;
while (__secondChild < (__len - 1) / 2)
{
__secondChild = 2 * (__secondChild + 1);
if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
__secondChild--;
- *(__first + __holeIndex) = *(__first + __secondChild);
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
__holeIndex = __secondChild;
}
if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
{
__secondChild = 2 * (__secondChild + 1);
- *(__first + __holeIndex) = *(__first + (__secondChild - 1));
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
+ + (__secondChild - 1)));
__holeIndex = __secondChild - 1;
}
- std::__push_heap(__first, __holeIndex, __topIndex, __value);
+ return __holeIndex;
}
- template<typename _RandomAccessIterator, typename _Tp>
- inline void
+ template<typename _RandomAccessIterator>
+ void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _RandomAccessIterator __result, _Tp __value)
+ _RandomAccessIterator __result)
{
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _Distance;
- *__result = *__first;
- std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
- __value);
+ _DistanceType;
+
+ _ValueType __value = _GLIBCXX_MOVE(*__result);
+ *__result = _GLIBCXX_MOVE(*__first);
+ _DistanceType __holeIndex = std::__adjust_heap(__first, _DistanceType(0),
+ _DistanceType(__last - __first));
+ std::__push_heap(__first, __holeIndex, _DistanceType(0),
+ _GLIBCXX_MOVE(__value));
}
/**
@@ -264,17 +273,15 @@
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap(__first, __last);
- std::__pop_heap(__first, __last - 1, __last - 1,
- _ValueType(*(__last - 1)));
+ std::__pop_heap(__first, __last - 1, __last - 1);
}
template<typename _RandomAccessIterator, typename _Distance,
- typename _Tp, typename _Compare>
- void
+ typename _Compare>
+ _Distance
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
- _Distance __len, _Tp __value, _Compare __comp)
+ _Distance __len, _Compare __comp)
{
- const _Distance __topIndex = __holeIndex;
_Distance __secondChild = __holeIndex;
while (__secondChild < (__len - 1) / 2)
{
@@ -282,28 +289,36 @@
if (__comp(*(__first + __secondChild),
*(__first + (__secondChild - 1))))
__secondChild--;
- *(__first + __holeIndex) = *(__first + __secondChild);
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
__holeIndex = __secondChild;
}
if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
{
__secondChild = 2 * (__secondChild + 1);
- *(__first + __holeIndex) = *(__first + (__secondChild - 1));
+ *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
+ + (__secondChild - 1)));
__holeIndex = __secondChild - 1;
}
- std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
+ return __holeIndex;
}
- template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
- inline void
+ template<typename _RandomAccessIterator, typename _Compare>
+ void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _RandomAccessIterator __result, _Tp __value, _Compare __comp)
+ _RandomAccessIterator __result, _Compare __comp)
{
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _Distance;
- *__result = *__first;
- std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
- __value, __comp);
+ _DistanceType;
+
+ _ValueType __value = _GLIBCXX_MOVE(*__result);
+ *__result = _GLIBCXX_MOVE(*__first);
+ _DistanceType __holeIndex = std::__adjust_heap(__first, _DistanceType(0),
+ _DistanceType(__last - __first),
+ __comp);
+ std::__push_heap(__first, __holeIndex, _DistanceType(0),
+ _GLIBCXX_MOVE(__value), __comp);
}
/**
@@ -322,17 +337,13 @@
pop_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap_pred(__first, __last, __comp);
- std::__pop_heap(__first, __last - 1, __last - 1,
- _ValueType(*(__last - 1)), __comp);
+ std::__pop_heap(__first, __last - 1, __last - 1, __comp);
}
/**
@@ -365,8 +376,11 @@
_DistanceType __parent = (__len - 2) / 2;
while (true)
{
- std::__adjust_heap(__first, __parent, __len,
- _ValueType(*(__first + __parent)));
+ _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
+ _DistanceType __holeIndex = std::__adjust_heap(__first, __parent,
+ __len);
+ std::__push_heap(__first, __holeIndex, __parent,
+ _GLIBCXX_MOVE(__value));
if (__parent == 0)
return;
__parent--;
@@ -405,8 +419,11 @@
_DistanceType __parent = (__len - 2) / 2;
while (true)
{
- std::__adjust_heap(__first, __parent, __len,
- _ValueType(*(__first + __parent)), __comp);
+ _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
+ _DistanceType __holeIndex = std::__adjust_heap(__first, __parent,
+ __len, __comp);
+ std::__push_heap(__first, __holeIndex, __parent,
+ _GLIBCXX_MOVE(__value), __comp);
if (__parent == 0)
return;
__parent--;
Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h (revision 129230)
+++ include/bits/stl_algo.h (working copy)
@@ -1628,13 +1628,10 @@
_RandomAccessIterator __middle,
_RandomAccessIterator __last)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
std::make_heap(__first, __middle);
for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
if (*__i < *__first)
- std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
+ std::__pop_heap(__first, __middle, __i);
}
/**
@@ -1648,13 +1645,10 @@
_RandomAccessIterator __middle,
_RandomAccessIterator __last, _Compare __comp)
{
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
-
std::make_heap(__first, __middle, __comp);
for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
if (__comp(*__i, *__first))
- std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
+ std::__pop_heap(__first, __middle, __i, __comp);
}
// partial_sort
@@ -1712,10 +1706,15 @@
while (__first != __last)
{
if (*__first < *__result_first)
- std::__adjust_heap(__result_first, _DistanceType(0),
- _DistanceType(__result_real_last
- - __result_first),
- _InputValueType(*__first));
+ {
+ _InputValueType __value = *__first;
+ _DistanceType __holeIndex = std::__adjust_heap(__result_first,
+ _DistanceType(0),
+ _DistanceType(__result_real_last
+ - __result_first));
+ std::__push_heap(__result_first, __holeIndex, _DistanceType(0),
+ __value);
+ }
++__first;
}
std::sort_heap(__result_first, __result_real_last);
@@ -1781,11 +1780,16 @@
while (__first != __last)
{
if (__comp(*__first, *__result_first))
- std::__adjust_heap(__result_first, _DistanceType(0),
- _DistanceType(__result_real_last
- - __result_first),
- _InputValueType(*__first),
- __comp);
+ {
+ _InputValueType __value = *__first;
+ _DistanceType __holeIndex = std::__adjust_heap(__result_first,
+ _DistanceType(0),
+ _DistanceType(__result_real_last
+ - __result_first),
+ __comp);
+ std::__push_heap(__result_first, __holeIndex, _DistanceType(0),
+ __value, __comp);
+ }
++__first;
}
std::sort_heap(__result_first, __result_real_last, __comp);
Index: testsuite/25_algorithms/heap/moveable.cc
===================================================================
--- testsuite/25_algorithms/heap/moveable.cc (revision 129231)
+++ testsuite/25_algorithms/heap/moveable.cc (working copy)
@@ -1,4 +1,3 @@
-// { dg-require-rvalref "" }
// { dg-options "-std=gnu++0x" }
// Copyright (C) 2005, 2007 Free Software Foundation, Inc.