Make flat containers stable, allow constructing from vector.

base/containers/flat_tree_unittest.cc

Index: base/containers/flat_tree_unittest.cc
diff --git a/base/containers/flat_tree_unittest.cc b/base/containers/flat_tree_unittest.cc
index 91a853c736ca6df5547383ca25826cff2d28a1a0..825f6feb38415807504fb796a35c7f804d86e1cf 100644
--- a/base/containers/flat_tree_unittest.cc
+++ b/base/containers/flat_tree_unittest.cc
@@ -130,6 +130,13 @@ class NonDefaultConstructibleCompare {
   }
 };
 
+template <class PairType>
+struct LessByFirst {
+  bool operator()(const PairType& lhs, const PairType& rhs) const {
+    return lhs.first < rhs.first;
+  }
+};
+
 // Common test trees.
 
 // TODO(dyaroshev): replace less<int> with less<>, once we have it
@@ -181,36 +188,30 @@ TEST(FlatTree, IncompleteType) {
 TEST(FlatTree, Stability) {
   using Pair = std::pair<int, int>;
 
-  struct LessByFirst {
-    bool operator()(const Pair& lhs, const Pair& rhs) const {
-      return lhs.first < rhs.first;
-    }
-  };
-
   using Tree =
-      flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst>;
+      flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst<Pair>>;
 
-  // Constructors are not stable.
+  // Constructors are stable.
   Tree cont{{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}};
 
-  auto NoneOfSecondsAreTwo = [&cont] {
-    return std::none_of(cont.begin(), cont.end(),
-                        [](const Pair& elem) { return elem.second == 2; });
+  auto AllOfSecondsAreZero = [&cont] {
+    return std::all_of(cont.begin(), cont.end(),
+                       [](const Pair& elem) { return elem.second == 0; });
   };
 
+  EXPECT_TRUE(AllOfSecondsAreZero()) << "constructor should be stable";
+
   // Should not replace existing.
   cont.insert(Pair(0, 2));
   cont.insert(Pair(1, 2));
   cont.insert(Pair(2, 2));
 
-  EXPECT_TRUE(NoneOfSecondsAreTwo())
-      << "insert should be stable with respect to constructor";
+  EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
 
   cont.insert(Pair(3, 0));
   cont.insert(Pair(3, 2));
 
-  EXPECT_TRUE(NoneOfSecondsAreTwo())
-      << "insert should be stable with respect to previous insert";
+  EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
 }
 
 // ----------------------------------------------------------------------------
@@ -312,7 +313,35 @@ TEST(FlatTree, MoveConstructor) {
   EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
 }
 
-//  flat_tree(std::initializer_list<value_type> ilist,
+// flat_tree(std::vector<value_type>&&)
+
+TEST(FlatTree, MoveVectorConstructor) {
+  using Pair = std::pair<int, MoveOnlyInt>;
+
+  // Construct an unsorted vector with a duplicate item in it. Sorted by the
+  // first item, the second allows us to test for stability. Using a move
+  // only type to ensure the vector is not copied.
+  std::vector<Pair> storage;
+  storage.push_back(Pair(2, MoveOnlyInt(0)));
+  storage.push_back(Pair(1, MoveOnlyInt(0)));
+  storage.push_back(Pair(2, MoveOnlyInt(1)));
+
+  using Tree =
+      flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst<Pair>>;
+  Tree tree(std::move(storage));
+
+  // The list should be two items long, with only the first "2" saved.
+  ASSERT_EQ(2u, tree.size());
+  const Pair& zeroth = *tree.begin();
+  ASSERT_EQ(1, zeroth.first);
+  ASSERT_EQ(0, zeroth.second.data());
+
+  const Pair& first = *(tree.begin() + 1);
+  ASSERT_EQ(2, first.first);
+  ASSERT_EQ(0, first.second.data());
+}
+
+// flat_tree(std::initializer_list<value_type> ilist,
 //           const Compare& comp = Compare())
 
 TEST(FlatTree, InitializerListConstructor) {