jdoerrie created this revision.
This change fixes std::inplace_merge to be stable for all inputs and adds
corresponding tests.
Fixes Bug 31166: https://bugs.llvm.org//show_bug.cgi?id=31166
https://reviews.llvm.org/D32788
Files:
include/algorithm
test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
Index: test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
===================================================================
--- test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
+++ test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
@@ -32,6 +32,14 @@
{return *x < *y;}
};
+struct first_only
+{
+ bool operator()(const std::pair<int, int>& x, const std::pair<int, int>& y)
+ {
+ return x.first < y.first;
+ }
+};
+
struct S {
S() : i_(0) {}
S(int i) : i_(i) {}
@@ -85,6 +93,23 @@
delete [] ia;
}
+void
+test_two(unsigned N, unsigned M)
+{
+ typedef std::pair<int, int> P;
+ std::vector<P> v(N);
+ unsigned mod = std::max(M, N - M);
+ for (unsigned i = 0; i < N; ++i)
+ {
+ v[i] = P(i % mod, i >= M);
+ }
+
+ std::stable_sort(v.begin(), v.begin() + M, first_only());
+ std::stable_sort(v.begin() + M, v.end(), first_only());
+ std::inplace_merge(v.begin(), v.begin() + M, v.end(), first_only());
+ assert(std::is_sorted(v.begin(), v.end()));
+}
+
template <class Iter>
void
test(unsigned N)
@@ -94,6 +119,12 @@
test_one<Iter>(N, N/2);
test_one<Iter>(N, 3*N/4);
test_one<Iter>(N, N);
+
+ test_two(N, 0);
+ test_two(N, N/4);
+ test_two(N, N/2);
+ test_two(N, 3*N/4);
+ test_two(N, N);
}
template <class Iter>
@@ -110,6 +141,18 @@
test_one<Iter>(3, 1);
test_one<Iter>(3, 2);
test_one<Iter>(3, 3);
+
+ test_two(0, 0);
+ test_two(1, 0);
+ test_two(1, 1);
+ test_two(2, 0);
+ test_two(2, 1);
+ test_two(2, 2);
+ test_two(3, 0);
+ test_two(3, 1);
+ test_two(3, 2);
+ test_two(3, 3);
+
test<Iter>(4);
test<Iter>(20);
test<Iter>(100);
Index: include/algorithm
===================================================================
--- include/algorithm
+++ include/algorithm
@@ -745,7 +745,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
Index: test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
===================================================================
--- test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
+++ test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
@@ -32,6 +32,14 @@
{return *x < *y;}
};
+struct first_only
+{
+ bool operator()(const std::pair<int, int>& x, const std::pair<int, int>& y)
+ {
+ return x.first < y.first;
+ }
+};
+
struct S {
S() : i_(0) {}
S(int i) : i_(i) {}
@@ -85,6 +93,23 @@
delete [] ia;
}
+void
+test_two(unsigned N, unsigned M)
+{
+ typedef std::pair<int, int> P;
+ std::vector<P> v(N);
+ unsigned mod = std::max(M, N - M);
+ for (unsigned i = 0; i < N; ++i)
+ {
+ v[i] = P(i % mod, i >= M);
+ }
+
+ std::stable_sort(v.begin(), v.begin() + M, first_only());
+ std::stable_sort(v.begin() + M, v.end(), first_only());
+ std::inplace_merge(v.begin(), v.begin() + M, v.end(), first_only());
+ assert(std::is_sorted(v.begin(), v.end()));
+}
+
template <class Iter>
void
test(unsigned N)
@@ -94,6 +119,12 @@
test_one<Iter>(N, N/2);
test_one<Iter>(N, 3*N/4);
test_one<Iter>(N, N);
+
+ test_two(N, 0);
+ test_two(N, N/4);
+ test_two(N, N/2);
+ test_two(N, 3*N/4);
+ test_two(N, N);
}
template <class Iter>
@@ -110,6 +141,18 @@
test_one<Iter>(3, 1);
test_one<Iter>(3, 2);
test_one<Iter>(3, 3);
+
+ test_two(0, 0);
+ test_two(1, 0);
+ test_two(1, 1);
+ test_two(2, 0);
+ test_two(2, 1);
+ test_two(2, 2);
+ test_two(3, 0);
+ test_two(3, 1);
+ test_two(3, 2);
+ test_two(3, 3);
+
test<Iter>(4);
test<Iter>(20);
test<Iter>(100);
Index: include/algorithm
===================================================================
--- include/algorithm
+++ include/algorithm
@@ -745,7 +745,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
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
