[libc++] Adds missing forward_list merge tests.
During the review of D112660 it turned out the tests for
`std::forward_list::merge` are incomplete.
Adds tests for the rvalue reference overloads. The tests are extended to
better test the Effects [forward.list.ops]/25 and Remarks
[forward.list.ops]/27 of the function:
- x is empty after the merge.
- Pointers and references to the moved elements of x now refer to those
same elements but as members of *this.
- Iterators referring to the moved elements will continue to refer to
their elements, but they now behave as iterators into *this, not into x.
- The algorithm is stable.
Reviewed By: Quuxplusone, #libc, ldionne
Differential Revision: https://reviews.llvm.org/D113364
GitOrigin-RevId: 65fceaebc79112d755cdda4a58828fdd9318e45f
diff --git a/test/std/containers/sequences/forwardlist/forwardlist.ops/merge.pass.cpp b/test/std/containers/sequences/forwardlist/forwardlist.ops/merge.pass.cpp
deleted file mode 100644
index 95d21b0..0000000
--- a/test/std/containers/sequences/forwardlist/forwardlist.ops/merge.pass.cpp
+++ /dev/null
@@ -1,50 +0,0 @@
-//===----------------------------------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-// <forward_list>
-
-// void merge(forward_list&& x);
-
-#include <forward_list>
-#include <iterator>
-#include <cassert>
-
-#include "test_macros.h"
-#include "min_allocator.h"
-
-int main(int, char**)
-{
- {
- typedef int T;
- typedef std::forward_list<T> C;
- const T t1[] = {3, 5, 6, 7, 12, 13};
- const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
- const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
- C c1(std::begin(t1), std::end(t1));
- C c2(std::begin(t2), std::end(t2));
- c1.merge(c2);
- C c3(std::begin(t3), std::end(t3));
- assert(c1 == c3);
- }
-#if TEST_STD_VER >= 11
- {
- typedef int T;
- typedef std::forward_list<T, min_allocator<T>> C;
- const T t1[] = {3, 5, 6, 7, 12, 13};
- const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
- const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
- C c1(std::begin(t1), std::end(t1));
- C c2(std::begin(t2), std::end(t2));
- c1.merge(c2);
- C c3(std::begin(t3), std::end(t3));
- assert(c1 == c3);
- }
-#endif
-
- return 0;
-}
diff --git a/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_lvalue.pass.cpp b/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_lvalue.pass.cpp
new file mode 100644
index 0000000..cb30b03
--- /dev/null
+++ b/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_lvalue.pass.cpp
@@ -0,0 +1,113 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <forward_list>
+
+// void merge(forward_list& x);
+
+#include <forward_list>
+#include <iterator>
+#include <vector>
+#include <cassert>
+
+#include "test_macros.h"
+#include "min_allocator.h"
+
+#if TEST_STD_VER >= 11
+# include <functional>
+#endif
+
+/// Helper struct to test a stable sort.
+///
+/// relation comparison uses a.
+/// equality comparison uses a and b.
+struct value {
+ int a;
+ int b;
+
+ friend bool operator<(const value& lhs, const value& rhs) { return lhs.a < rhs.a; }
+ friend bool operator==(const value& lhs, const value& rhs) { return lhs.a == rhs.a && lhs.b == rhs.b; }
+};
+
+int main(int, char**) {
+ { // Basic merge operation.
+ typedef int T;
+ typedef std::forward_list<T> C;
+ const T t1[] = {3, 5, 6, 7, 12, 13};
+ const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
+ const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(c2);
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+ { // Pointers, references, and iterators should remain valid after merging.
+ typedef int T;
+ typedef std::forward_list<T> C;
+ typedef T* P;
+ typedef typename C::iterator I;
+ const T to[3] = {0, 1, 2};
+
+ C c2(std::begin(to), std::end(to));
+ I io[3] = {c2.begin(), ++c2.begin(), ++ ++c2.begin()};
+#if TEST_STD_VER >= 11
+ std::reference_wrapper<T> ro[3] = {*io[0], *io[1], *io[2]};
+#endif
+ P po[3] = {&*io[0], &*io[1], &*io[2]};
+
+ C c1;
+ c1.merge(c2);
+ assert(c2.empty());
+
+ for (size_t i = 0; i < 3; ++i) {
+ assert(to[i] == *io[i]);
+#if TEST_STD_VER >= 11
+ assert(to[i] == ro[i].get());
+#endif
+ assert(to[i] == *po[i]);
+ }
+ }
+ { // Sorting is stable.
+ typedef value T;
+ typedef std::forward_list<T> C;
+ const T t1[] = {{0, 0}, {2, 0}, {3, 0}};
+ const T t2[] = {{0, 1}, {1, 1}, {2, 1}, {4, 1}};
+ const T t3[] = {{0, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}, {3, 0}, {4, 1}};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(c2);
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+#if TEST_STD_VER >= 11
+ { // Test with a different allocator.
+ typedef int T;
+ typedef std::forward_list<T, min_allocator<T>> C;
+ const T t1[] = {3, 5, 6, 7, 12, 13};
+ const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
+ const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(c2);
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+#endif
+
+ return 0;
+}
diff --git a/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_lvalue_pred.pass.cpp b/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_lvalue_pred.pass.cpp
new file mode 100644
index 0000000..d8df4eb
--- /dev/null
+++ b/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_lvalue_pred.pass.cpp
@@ -0,0 +1,114 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <forward_list>
+
+// template <class Compare> void merge(forward_list& x, Compare comp);
+
+#include <forward_list>
+#include <iterator>
+#include <vector>
+#include <cassert>
+
+#include "test_macros.h"
+#include "min_allocator.h"
+
+#if TEST_STD_VER >= 11
+# include <functional>
+#endif
+
+/// Helper for testing a stable sort.
+///
+/// The relation operator uses \ref a.
+/// The equality operator uses \ref a and \ref b.
+struct value {
+ int a;
+ int b;
+
+ friend bool operator>(const value& lhs, const value& rhs) { return lhs.a > rhs.a; }
+ friend bool operator==(const value& lhs, const value& rhs) { return lhs.a == rhs.a && lhs.b == rhs.b; }
+};
+
+int main(int, char**) {
+ { // Basic merge operation.
+ typedef int T;
+ typedef std::forward_list<T> C;
+ const T t1[] = {13, 12, 7, 6, 5, 3};
+ const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
+ const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(c2, std::greater<T>());
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+ { // Pointers, references, and iterators should remain valid after merging.
+ typedef int T;
+ typedef std::forward_list<T> C;
+ typedef T* P;
+ typedef typename C::iterator I;
+ const T to[3] = {2, 1, 0};
+
+ C c2(std::begin(to), std::end(to));
+ I io[3] = {c2.begin(), ++c2.begin(), ++ ++c2.begin()};
+#if TEST_STD_VER >= 11
+ std::reference_wrapper<T> ro[3] = {*io[0], *io[1], *io[2]};
+#endif
+ P po[3] = {&*io[0], &*io[1], &*io[2]};
+
+ C c1;
+ c1.merge(c2, std::greater<T>());
+ assert(c2.empty());
+
+ for (size_t i = 0; i < 3; ++i) {
+ assert(to[i] == *io[i]);
+#if TEST_STD_VER >= 11
+ assert(to[i] == ro[i].get());
+#endif
+ assert(to[i] == *po[i]);
+ }
+ }
+ { // Sorting is stable.
+ typedef value T;
+ typedef std::forward_list<T> C;
+ const T t1[] = {{3, 0}, {2, 0}, {0, 0}};
+ const T t2[] = {{4, 1}, {2, 1}, {1, 1}, {0, 1}};
+ const T t3[] = {{4, 1}, {3, 0}, {2, 0}, {2, 1}, {1, 1}, {0, 0}, {0, 1}};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(c2, std::greater<T>());
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+
+#if TEST_STD_VER >= 11
+ { // Test with a different allocator.
+ typedef int T;
+ typedef std::forward_list<T, min_allocator<T>> C;
+ const T t1[] = {13, 12, 7, 6, 5, 3};
+ const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
+ const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(c2, std::greater<T>());
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+#endif
+
+ return 0;
+}
diff --git a/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_pred.pass.cpp b/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_pred.pass.cpp
deleted file mode 100644
index e625555..0000000
--- a/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_pred.pass.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-//===----------------------------------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-// <forward_list>
-
-// template <class Compare> void merge(forward_list&& x, Compare comp);
-
-#include <forward_list>
-#include <iterator>
-#include <functional>
-#include <cassert>
-
-#include "test_macros.h"
-#include "min_allocator.h"
-
-int main(int, char**)
-{
- {
- typedef int T;
- typedef std::forward_list<T> C;
- const T t1[] = {13, 12, 7, 6, 5, 3};
- const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
- const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
- C c1(std::begin(t1), std::end(t1));
- C c2(std::begin(t2), std::end(t2));
- c1.merge(c2, std::greater<T>());
- C c3(std::begin(t3), std::end(t3));
- assert(c1 == c3);
- }
-#if TEST_STD_VER >= 11
- {
- typedef int T;
- typedef std::forward_list<T, min_allocator<T>> C;
- const T t1[] = {13, 12, 7, 6, 5, 3};
- const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
- const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
- C c1(std::begin(t1), std::end(t1));
- C c2(std::begin(t2), std::end(t2));
- c1.merge(c2, std::greater<T>());
- C c3(std::begin(t3), std::end(t3));
- assert(c1 == c3);
- }
-#endif
-
- return 0;
-}
diff --git a/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_rvalue.pass.cpp b/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_rvalue.pass.cpp
new file mode 100644
index 0000000..f6db686
--- /dev/null
+++ b/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_rvalue.pass.cpp
@@ -0,0 +1,106 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03
+
+// <forward_list>
+
+// void merge(forward_list&& x);
+
+#include <forward_list>
+#include <functional>
+#include <iterator>
+#include <vector>
+#include <cassert>
+
+#include "test_macros.h"
+#include "min_allocator.h"
+
+/// Helper for testing a stable sort.
+///
+/// The relation operator uses \ref a.
+/// The equality operator uses \ref a and \ref b.
+struct value {
+ int a;
+ int b;
+
+ friend bool operator<(const value& lhs, const value& rhs) { return lhs.a < rhs.a; }
+ friend bool operator==(const value& lhs, const value& rhs) { return lhs.a == rhs.a && lhs.b == rhs.b; }
+};
+
+int main(int, char**) {
+ { // Basic merge operation.
+ typedef int T;
+ typedef std::forward_list<T> C;
+ const T t1[] = {3, 5, 6, 7, 12, 13};
+ const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
+ const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(std::move(c2));
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+ { // Pointers, references, and iterators should remain valid after merging.
+ typedef int T;
+ typedef std::forward_list<T> C;
+ typedef T* P;
+ typedef typename C::iterator I;
+ const T to[3] = {0, 1, 2};
+
+ C c2(std::begin(to), std::end(to));
+ I io[3] = {c2.begin(), ++c2.begin(), ++ ++c2.begin()};
+ std::reference_wrapper<T> ro[3] = {*io[0], *io[1], *io[2]};
+ P po[3] = {&*io[0], &*io[1], &*io[2]};
+
+ C c1;
+ c1.merge(std::move(c2));
+ assert(c2.empty());
+
+ for (size_t i = 0; i < 3; ++i) {
+ assert(to[i] == *io[i]);
+ assert(to[i] == ro[i].get());
+ assert(to[i] == *po[i]);
+ }
+ }
+ { // Sorting is stable.
+ typedef value T;
+ typedef std::forward_list<T> C;
+ const T t1[] = {{0, 0}, {2, 0}, {3, 0}};
+ const T t2[] = {{0, 1}, {1, 1}, {2, 1}, {4, 1}};
+ const T t3[] = {{0, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}, {3, 0}, {4, 1}};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(std::move(c2));
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+ { // Test with a different allocator.
+ typedef int T;
+ typedef std::forward_list<T, min_allocator<T>> C;
+ const T t1[] = {3, 5, 6, 7, 12, 13};
+ const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
+ const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(std::move(c2));
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+
+ return 0;
+}
diff --git a/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_rvalue_pred.pass.cpp b/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_rvalue_pred.pass.cpp
new file mode 100644
index 0000000..1b45946
--- /dev/null
+++ b/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_rvalue_pred.pass.cpp
@@ -0,0 +1,107 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03
+
+// <forward_list>
+
+// template <class Compare> void merge(forward_list&& x, Compare comp);
+
+#include <forward_list>
+#include <functional>
+#include <iterator>
+#include <vector>
+#include <cassert>
+
+#include "test_macros.h"
+#include "min_allocator.h"
+
+/// Helper for testing a stable sort.
+///
+/// The relation operator uses \ref a.
+/// The equality operator uses \ref a and \ref b.
+struct value {
+ int a;
+ int b;
+
+ friend bool operator>(const value& lhs, const value& rhs) { return lhs.a > rhs.a; }
+ friend bool operator==(const value& lhs, const value& rhs) { return lhs.a == rhs.a && lhs.b == rhs.b; }
+};
+
+int main(int, char**) {
+ { // Basic merge operation.
+ typedef int T;
+ typedef std::forward_list<T> C;
+ const T t1[] = {13, 12, 7, 6, 5, 3};
+ const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
+ const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(std::move(c2), std::greater<T>());
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+ { // Pointers, references, and iterators should remain valid after merging.
+ typedef int T;
+ typedef std::forward_list<T> C;
+ typedef T* P;
+ typedef typename C::iterator I;
+ const T to[3] = {2, 1, 0};
+
+ C c2(std::begin(to), std::end(to));
+ I io[3] = {c2.begin(), ++c2.begin(), ++ ++c2.begin()};
+ std::reference_wrapper<T> ro[3] = {*io[0], *io[1], *io[2]};
+ P po[3] = {&*io[0], &*io[1], &*io[2]};
+
+ C c1;
+ c1.merge(std::move(c2), std::greater<T>());
+ assert(c2.empty());
+
+ for (size_t i = 0; i < 3; ++i) {
+ assert(to[i] == *io[i]);
+ assert(to[i] == ro[i].get());
+ assert(to[i] == *po[i]);
+ }
+ }
+ { // Sorting is stable.
+ typedef value T;
+ typedef std::forward_list<T> C;
+ const T t1[] = {{3, 0}, {2, 0}, {0, 0}};
+ const T t2[] = {{4, 1}, {2, 1}, {1, 1}, {0, 1}};
+ const T t3[] = {{4, 1}, {3, 0}, {2, 0}, {2, 1}, {1, 1}, {0, 0}, {0, 1}};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(std::move(c2), std::greater<T>());
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+
+ { // Test with a different allocator.
+ typedef int T;
+ typedef std::forward_list<T, min_allocator<T>> C;
+ const T t1[] = {13, 12, 7, 6, 5, 3};
+ const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
+ const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
+
+ C c1(std::begin(t1), std::end(t1));
+ C c2(std::begin(t2), std::end(t2));
+ c1.merge(std::move(c2), std::greater<T>());
+ assert(c2.empty());
+
+ C c3(std::begin(t3), std::end(t3));
+ assert(c1 == c3);
+ }
+
+ return 0;
+}
