commit 6a5a08c54f2f62ac5dad94979df03686de6ad290
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Thu Jan 19 21:09:36 2017 +0000
PR67085 pass comparison functions by reference in heap algorithms
PR libstdc++/67085
* include/bits/predefined_ops.h (_Iter_less_val, _Val_less_iter): Add
converting constructors from _Iter_less_iter.
(_Iter_comp_val, _Val_comp_iter): Add converting constructors from
_Iter_comp_iter.
(__iter_comp_val(_Iter_comp_iter<C>): Use converting constructor.
(__val_comp_iter(_Iter_comp_iter<C>): Likewise.
* include/bits/stl_heap.h (__is_heap_until, __push_heap, __pop_heap)
(__make_heap, __sort_heap): Change _Compare parameters to references.
(__is_heap, push_heap, __adjust_heap, __pop_heap, pop_heap)
(__make_heap, make_heap, sort_heap, is_heap_until): Pass comparison
functions as lvalues.
(is_heap): Call __is_heap_until directly to avoid copying __comp.
* testsuite/23_containers/priority_queue/67085.cc: Adjust test to
count copies during construction with empty sequence.
@@ -50,6 +50,15 @@ namespace __ops
struct _Iter_less_val
{
+#if __cplusplus >= 201103L
+ constexpr _Iter_less_val() = default;
+#else
+ _Iter_less_val() { }
+#endif
+
+ explicit
+ _Iter_less_val(_Iter_less_iter) { }
+
template<typename _Iterator, typename _Value>
bool
operator()(_Iterator __it, _Value& __val) const
@@ -66,6 +75,15 @@ namespace __ops
struct _Val_less_iter
{
+#if __cplusplus >= 201103L
+ constexpr _Val_less_iter() = default;
+#else
+ _Val_less_iter() { }
+#endif
+
+ explicit
+ _Val_less_iter(_Iter_less_iter) { }
+
template<typename _Value, typename _Iterator>
bool
operator()(_Value& __val, _Iterator __it) const
@@ -141,6 +159,18 @@ namespace __ops
: _M_comp(_GLIBCXX_MOVE(__comp))
{ }
+ explicit
+ _Iter_comp_val(const _Iter_comp_iter<_Compare>& __comp)
+ : _M_comp(__comp._M_comp)
+ { }
+
+#if __cplusplus >= 201103L
+ explicit
+ _Iter_comp_val(_Iter_comp_iter<_Compare>&& __comp)
+ : _M_comp(std::move(__comp._M_comp))
+ { }
+#endif
+
template<typename _Iterator, typename _Value>
bool
operator()(_Iterator __it, _Value& __val)
@@ -155,7 +185,7 @@ namespace __ops
template<typename _Compare>
inline _Iter_comp_val<_Compare>
__iter_comp_val(_Iter_comp_iter<_Compare> __comp)
- { return _Iter_comp_val<_Compare>(_GLIBCXX_MOVE(__comp._M_comp)); }
+ { return _Iter_comp_val<_Compare>(_GLIBCXX_MOVE(__comp)); }
template<typename _Compare>
struct _Val_comp_iter
@@ -167,6 +197,18 @@ namespace __ops
: _M_comp(_GLIBCXX_MOVE(__comp))
{ }
+ explicit
+ _Val_comp_iter(const _Iter_comp_iter<_Compare>& __comp)
+ : _M_comp(__comp._M_comp)
+ { }
+
+#if __cplusplus >= 201103L
+ explicit
+ _Val_comp_iter(_Iter_comp_iter<_Compare>&& __comp)
+ : _M_comp(std::move(__comp._M_comp))
+ { }
+#endif
+
template<typename _Value, typename _Iterator>
bool
operator()(_Value& __val, _Iterator __it)
@@ -181,7 +223,7 @@ namespace __ops
template<typename _Compare>
inline _Val_comp_iter<_Compare>
__val_comp_iter(_Iter_comp_iter<_Compare> __comp)
- { return _Val_comp_iter<_Compare>(_GLIBCXX_MOVE(__comp._M_comp)); }
+ { return _Val_comp_iter<_Compare>(_GLIBCXX_MOVE(__comp)); }
template<typename _Value>
struct _Iter_equals_val
@@ -72,7 +72,7 @@ _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)
@@ -91,8 +91,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
inline bool
__is_heap(_RandomAccessIterator __first, _Distance __n)
{
- return std::__is_heap_until(__first, __n,
- __gnu_cxx::__ops::__iter_less_iter()) == __n;
+ __gnu_cxx::__ops::_Iter_less_iter __comp;
+ return std::__is_heap_until(__first, __n, __comp) == __n;
}
template<typename _RandomAccessIterator, typename _Compare,
@@ -100,8 +100,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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;
+ __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+ return std::__is_heap_until(__first, __n, __cmp) == __n;
}
template<typename _RandomAccessIterator>
@@ -126,7 +126,7 @@ _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))
@@ -165,10 +165,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive(__first, __last);
__glibcxx_requires_heap(__first, __last - 1);
+ __gnu_cxx::__ops::_Iter_less_val __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);
}
/**
@@ -200,11 +200,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
__glibcxx_requires_heap_pred(__first, __last - 1, __comp);
+ __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
+ __cmp(_GLIBCXX_MOVE(__comp));
_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), __cmp);
}
template<typename _RandomAccessIterator, typename _Distance,
@@ -231,16 +231,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
+ (__secondChild - 1)));
__holeIndex = __secondChild - 1;
}
- std::__push_heap(__first, __holeIndex, __topIndex,
- _GLIBCXX_MOVE(__value),
- __gnu_cxx::__ops::
- __iter_comp_val(_GLIBCXX_MOVE(__comp)));
+ __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
+ __cmp(_GLIBCXX_MOVE(__comp));
+ std::__push_heap(__first, __holeIndex, __topIndex,
+ _GLIBCXX_MOVE(__value), __cmp);
}
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;
@@ -251,7 +251,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);
}
/**
@@ -282,8 +282,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__last - __first > 1)
{
--__last;
- std::__pop_heap(__first, __last, __last,
- __gnu_cxx::__ops::__iter_less_iter());
+ __gnu_cxx::__ops::_Iter_less_iter __comp;
+ std::__pop_heap(__first, __last, __last, __comp);
}
}
@@ -313,17 +313,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__last - __first > 1)
{
+ using __gnu_cxx::__ops::_Iter_comp_iter;
+ _Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
--__last;
- std::__pop_heap(__first, __last, __last,
- __gnu_cxx::__ops::
- __iter_comp_iter(_GLIBCXX_MOVE(__comp)));
+ std::__pop_heap(__first, __last, __last, __cmp);
}
}
template<typename _RandomAccessIterator, typename _Compare>
void
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Compare __comp)
+ _Compare& __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
@@ -366,8 +366,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());
+ __gnu_cxx::__ops::_Iter_less_iter __comp;
+ std::__make_heap(__first, __last, __comp);
}
/**
@@ -391,15 +391,14 @@ _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)));
+ __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+ std::__make_heap(__first, __last, __cmp);
}
template<typename _RandomAccessIterator, typename _Compare>
void
__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Compare __comp)
+ _Compare& __comp)
{
while (__last - __first > 1)
{
@@ -429,8 +428,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());
+ __gnu_cxx::__ops::_Iter_less_iter __comp;
+ std::__sort_heap(__first, __last, __comp);
}
/**
@@ -455,9 +454,8 @@ _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)));
+ __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+ std::__sort_heap(__first, __last, __cmp);
}
#if __cplusplus >= 201103L
@@ -483,9 +481,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
+ __gnu_cxx::__ops::_Iter_less_iter __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);
}
/**
@@ -510,10 +508,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
+ __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
return __first
- + std::__is_heap_until(__first, std::distance(__first, __last),
- __gnu_cxx::__ops::
- __iter_comp_iter(std::move(__comp)));
+ + std::__is_heap_until(__first, std::distance(__first, __last), __cmp);
}
/**
@@ -541,8 +538,15 @@ _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);
+ __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+ return std::__is_heap_until(__first, __dist, __cmp) == __dist;
}
#endif
@@ -32,11 +32,11 @@ struct CopyCounter : std::less<int>
void
test01()
{
- int v[] = {1, 2, 3, 4};
- std::priority_queue<int, std::vector<int>, CopyCounter> q{v, v+4};
- VERIFY(count == 4);
+ int i;
+ std::priority_queue<int, std::vector<int>, CopyCounter> q{&i, &i};
+ VERIFY(count == 2);
q.push(1);
- VERIFY(count == 5);
+ VERIFY(count == 3);
}
int