Make flat containers stable, allow constructing from vector.

base/containers/flat_tree_unittest.cc

 // Copyright 2017 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/containers/flat_tree.h"
 
 // Following tests are ported and extended tests from libcpp for std::set.
 // They can be found here:
 // https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associative/set
 //
@@ skipping 112 matching lines @@
 class NonDefaultConstructibleCompare {
  public:
   explicit NonDefaultConstructibleCompare(int) {}
 
   template <typename T>
   bool operator()(const T& lhs, const T& rhs) const {
     return std::less<T>()(lhs, rhs);
   }
 };
 
+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
 // crbug.com/682254. This will make it different than IntTree.
 using IntTreeWithLess =
     flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>;
 using IntTree =
     flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>;
 using MoveOnlyTree = flat_tree<MoveOnlyInt,
                                MoveOnlyInt,
@@ skipping 31 matching lines @@
 
     // We do not declare operator< because clang complains that it's unused.
   };
 
   A a;
 }
 
 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<Pair>>;
+
+  // Constructors are stable.
+  Tree cont{{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}};
+
+  auto AllOfSecondsAreZero = [&cont] {
+    return std::all_of(cont.begin(), cont.end(),
+                       [](const Pair& elem) { return elem.second == 0; });
   };
 
-  using Tree =
-      flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst>;
-
-  // Constructors are not 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; });
-  };
+  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";
 }
 
 // ----------------------------------------------------------------------------
 // Types.
 
 // key_type
 // key_compare
 // value_type
 // value_compare
 // pointer
@@ skipping 81 matching lines @@
 
   MoveOnlyTree original(std::begin(input_range), std::end(input_range));
   MoveOnlyTree moved(std::move(original));
 
   EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
   EXPECT_EQ(1U, moved.count(MoveOnlyInt(2)));
   EXPECT_EQ(1U, moved.count(MoveOnlyInt(3)));
   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) {
   {
     IntTree cont{1, 2, 3, 4, 5, 6, 10, 8};
     EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
   }
   {
     TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8},
                                 NonDefaultConstructibleCompare(0));
@@ skipping 921 matching lines @@
   EraseIf(x, [](int elem) { return !(elem & 1); });
   EXPECT_THAT(x, ElementsAre(1, 3));
 
   x = {1, 2, 3, 4};
   EraseIf(x, [](int elem) { return elem & 1; });
   EXPECT_THAT(x, ElementsAre(2, 4));
 }
 
 }  // namespace internal
 }  // namespace base