Fix PR31166: std::inplace_merge seems to be unstable. Thanks to Jan Wilken Dörrie for the suggested fix.
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@311952 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/algorithm b/include/algorithm
index 4542275..31df79f 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -734,15 +734,15 @@
};
template <class _Predicate>
-class __negate
+class __invert // invert the sense of a comparison
{
private:
_Predicate __p_;
public:
- _LIBCPP_INLINE_VISIBILITY __negate() {}
+ _LIBCPP_INLINE_VISIBILITY __invert() {}
_LIBCPP_INLINE_VISIBILITY
- explicit __negate(_Predicate __p) : __p_(__p) {}
+ explicit __invert(_Predicate __p) : __p_(__p) {}
template <class _T1>
_LIBCPP_INLINE_VISIBILITY
@@ -750,7 +750,7 @@
template <class _T1, class _T2>
_LIBCPP_INLINE_VISIBILITY
- bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}
+ bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
};
#ifdef _LIBCPP_DEBUG
@@ -4567,7 +4567,7 @@
typedef reverse_iterator<value_type*> _Rv;
__half_inplace_merge(_Rv(__p), _Rv(__buff),
_RBi(__middle), _RBi(__first),
- _RBi(__last), __negate<_Compare>(__comp));
+ _RBi(__last), __invert<_Compare>(__comp));
}
}
diff --git a/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp b/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
index 369bccf..6fd8fd4 100644
--- a/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
+++ b/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
@@ -116,6 +116,25 @@
test<Iter>(1000);
}
+struct less_by_first {
+ template <typename Pair>
+ bool operator()(const Pair& lhs, const Pair& rhs) {
+ return std::less<typename Pair::first_type>()(lhs.first, rhs.first);
+ }
+};
+
+void test_PR31166 ()
+{
+ typedef std::pair<int, int> P;
+ typedef std::vector<P> V;
+ const V vec {{1, 0}, {2, 0}, {2, 1}, {2, 2}, {2, 3}};
+ for ( int i = 0; i < 5; ++i ) {
+ V res = vec;
+ std::inplace_merge(res.begin(), res.begin() + i, res.end(), less_by_first());
+ assert(res == vec);
+ }
+}
+
int main()
{
test<bidirectional_iterator<int*> >();
@@ -146,4 +165,6 @@
delete [] ia;
}
#endif // TEST_STD_VER >= 11
+
+ test_PR31166();
}