Confused by <bits/predefined_ops.h>
Jonathan Wakely
jwakely@redhat.com
Thu Jan 19 18:46:00 GMT 2017
On 19/01/17 08:32 +0000, Jonathan Wakely wrote:
>On 18/01/17 22:17 +0100, François Dumont wrote:
>>Hi
>>
>>Names of functions and struct in this file are surely not what I am
>>most proud of in libstdc++. I even think that I confess it when I
>>proposed the patch :-)
>>
>>As those elements are purely internal and we rarely need to be touch
>>I don't consider it as a big issue but if you want to rename
>>everything don't hesitate.
>>
>>Note that I also have this patch pending:
>>
>>https://gcc.gnu.org/ml/libstdc++/2015-10/msg00071.html
>>
>>But I can surely rework it on top of your changes unless you just
>>want me to forget it.
>
>It looks good, let's return to it in stage 1 for gcc 8.
>
>Any thoughts on the questions repeated below?
That patch provides one of the benefits of these predefined ops: we
can centralise where we do Debug Mode checks, to try and abort on
invalid orderings.
That's nice, but the cons of the predefined ops seem to outweigh the
pros quite heavily:
The code is much harder to understand (even with better names).
The code is considerably slower, because the __iter_comp_iter
functions make copies of the functors, and all the internal algorithms
(the ones with __ prefixes) make copies of the functors. Because the
code needs to work in C++98 we can't rely on rvalue references
everywhere, and because we're creating rvalues with the
__iter_comp_iter() functions we can't take lvalue reference arguments,
so we must make copies. This sucks. See PR 67085 and PR 70898. I've
improved things by adding _GLIBCXX_MOVE which helps because moves can
be faster than copies, but it would be even better to not do any moves
or copies. And sometimes the comparison function needs to be called in
a loop, so then we can't move it.
The attached patch rips out the predefined ops from <bits/stl_heap.h>
and makes the code more efficient, and IMHO simpler (we only have to
deal with functions that compare values, not some that compare
iterators and some that compare values and some that compare iterators
with values!)
This means the __is_heap and other internal functions can have a
_Compare& argument, and not copy anything.
All that's needed for this to work is a functor like std::less<void>.
What do we lose by making this change? i.e. reverting the predefined
ops changes to stl_heap.h?
The __heap_less function won't work with iterators that return proxies
or rvalues, but since heaps only work with RandomAccessIterators I
don't really care about that. We could solve it for C++11 and later
using forwarding references anyway, so only C++98 would not support
it.
We wouldn't be able to check the comparison objects aas easily in
Debug Mode. That's unfortunate, but normal mode must *not* get slower
in order to accomodate extra Debug Mode checks. That's not acceptable.
Anything else?
-------------- next part --------------
diff --git a/libstdc++-v3/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h
index c82ce77..81e2981 100644
--- a/libstdc++-v3/include/bits/stl_heap.h
+++ b/libstdc++-v3/include/bits/stl_heap.h
@@ -72,12 +72,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Compare>
_Distance
__is_heap_until(_RandomAccessIterator __first, _Distance __n,
- _Compare __comp)
+ _Compare& __comp)
{
_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;
@@ -85,24 +85,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __n;
}
+ struct __heap_less
+ {
+ template<typename _Tp, typename _Up>
+ bool operator()(_Tp& __lhs, _Up& __rhs) const
+ { return __lhs < __rhs; }
+ };
+
// __is_heap, a predicate testing whether or not a range is a heap.
// This function is an extension, not part of the C++ standard.
template<typename _RandomAccessIterator, typename _Distance>
inline bool
__is_heap(_RandomAccessIterator __first, _Distance __n)
{
- return std::__is_heap_until(__first, __n,
- __gnu_cxx::__ops::__iter_less_iter()) == __n;
+ __heap_less __comp;
+ return std::__is_heap_until(__first, __n, __comp) == __n;
}
template<typename _RandomAccessIterator, typename _Compare,
typename _Distance>
inline bool
- __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
- {
- return std::__is_heap_until(__first, __n,
- __gnu_cxx::__ops::__iter_comp_iter(__comp)) == __n;
- }
+ __is_heap(_RandomAccessIterator __first, _Compare& __comp, _Distance __n)
+ { return std::__is_heap_until(__first, __n, __comp) == __n; }
template<typename _RandomAccessIterator>
inline bool
@@ -112,7 +116,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _RandomAccessIterator, typename _Compare>
inline bool
__is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Compare __comp)
+ _Compare& __comp)
{ return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
@@ -123,10 +127,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
__push_heap(_RandomAccessIterator __first,
_Distance __holeIndex, _Distance __topIndex, _Tp __value,
- _Compare __comp)
+ _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;
@@ -162,10 +166,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive(__first, __last);
__glibcxx_requires_heap(__first, __last - 1);
+ __heap_less __comp;
_ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _GLIBCXX_MOVE(__value),
- __gnu_cxx::__ops::__iter_less_val());
+ _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
}
/**
@@ -199,24 +203,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _GLIBCXX_MOVE(__value),
- __gnu_cxx::__ops::
- __iter_comp_val(_GLIBCXX_MOVE(__comp)));
+ _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
}
template<typename _RandomAccessIterator, typename _Distance,
typename _Tp, typename _Compare>
void
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
- _Distance __len, _Tp __value, _Compare __comp)
+ _Distance __len, _Tp __value, _Compare& __comp)
{
const _Distance __topIndex = __holeIndex;
_Distance __secondChild = __holeIndex;
while (__secondChild < (__len - 1) / 2)
{
__secondChild = 2 * (__secondChild + 1);
- if (__comp(__first + __secondChild,
- __first + (__secondChild - 1)))
+ if (__comp(*(__first + __secondChild),
+ *(__first + (__secondChild - 1))))
__secondChild--;
*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
__holeIndex = __secondChild;
@@ -229,15 +231,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__holeIndex = __secondChild - 1;
}
std::__push_heap(__first, __holeIndex, __topIndex,
- _GLIBCXX_MOVE(__value),
- __gnu_cxx::__ops::
- __iter_comp_val(_GLIBCXX_MOVE(__comp)));
+ _GLIBCXX_MOVE(__value), __comp);
}
template<typename _RandomAccessIterator, typename _Compare>
inline void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _RandomAccessIterator __result, _Compare __comp)
+ _RandomAccessIterator __result, _Compare& __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
@@ -248,7 +248,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
*__result = _GLIBCXX_MOVE(*__first);
std::__adjust_heap(__first, _DistanceType(0),
_DistanceType(__last - __first),
- _GLIBCXX_MOVE(__value), _GLIBCXX_MOVE(__comp));
+ _GLIBCXX_MOVE(__value), __comp);
}
/**
@@ -276,11 +276,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive(__first, __last);
__glibcxx_requires_heap(__first, __last);
+ __heap_less __comp;
if (__last - __first > 1)
{
--__last;
- std::__pop_heap(__first, __last, __last,
- __gnu_cxx::__ops::__iter_less_iter());
+ std::__pop_heap(__first, __last, __last, __comp);
}
}
@@ -311,16 +311,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__last - __first > 1)
{
--__last;
- std::__pop_heap(__first, __last, __last,
- __gnu_cxx::__ops::
- __iter_comp_iter(_GLIBCXX_MOVE(__comp)));
+ std::__pop_heap(__first, __last, __last, __comp);
}
}
template<typename _RandomAccessIterator, typename _Compare>
void
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Compare __comp)
+ _Compare& __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
@@ -336,7 +334,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
_ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
- _GLIBCXX_MOVE(__comp));
+ __comp);
if (__parent == 0)
return;
__parent--;
@@ -363,8 +361,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
- std::__make_heap(__first, __last,
- __gnu_cxx::__ops::__iter_less_iter());
+ __heap_less __comp;
+ std::__make_heap(__first, __last, __comp);
}
/**
@@ -388,20 +386,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
- std::__make_heap(__first, __last,
- __gnu_cxx::__ops::
- __iter_comp_iter(_GLIBCXX_MOVE(__comp)));
+ std::__make_heap(__first, __last, __comp);
}
template<typename _RandomAccessIterator, typename _Compare>
void
__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Compare __comp)
+ _Compare& __comp)
{
while (__last - __first > 1)
{
--__last;
- std::__pop_heap(__first, __last, __last, _GLIBCXX_MOVE(__comp));
+ std::__pop_heap(__first, __last, __last, __comp);
}
}
@@ -426,8 +422,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive(__first, __last);
__glibcxx_requires_heap(__first, __last);
- std::__sort_heap(__first, __last,
- __gnu_cxx::__ops::__iter_less_iter());
+ __heap_less __comp;
+ std::__sort_heap(__first, __last, __comp);
}
/**
@@ -452,9 +448,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
__glibcxx_requires_heap_pred(__first, __last, __comp);
- std::__sort_heap(__first, __last,
- __gnu_cxx::__ops::
- __iter_comp_iter(_GLIBCXX_MOVE(__comp)));
+ std::__sort_heap(__first, __last, __comp);
}
#if __cplusplus >= 201103L
@@ -480,9 +474,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
+ __heap_less __comp;
return __first +
- std::__is_heap_until(__first, std::distance(__first, __last),
- __gnu_cxx::__ops::__iter_less_iter());
+ std::__is_heap_until(__first, std::distance(__first, __last), __comp);
}
/**
@@ -509,8 +503,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __first
+ std::__is_heap_until(__first, std::distance(__first, __last),
- __gnu_cxx::__ops::
- __iter_comp_iter(std::move(__comp)));
+ __comp);
}
/**
@@ -538,8 +531,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
- return std::is_heap_until(__first, __last, std::move(__comp))
- == __last;
+ // concept requirements
+ __glibcxx_function_requires(_RandomAccessIteratorConcept<
+ _RandomAccessIterator>)
+ __glibcxx_requires_valid_range(__first, __last);
+ __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
+
+ const auto __dist = std::distance(__first, __last);
+ return std::__is_heap_until(__first, __dist, __comp) == __dist;
}
#endif
More information about the Libstdc++
mailing list