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 IntPair = std::pair<int, int>;
+using IntPairTree = flat_tree<IntPair,
+                              IntPair,
+                              GetKeyFromValueIdentity<IntPair>,
+                              LessByFirst<IntPair>>;
 using MoveOnlyTree = flat_tree<MoveOnlyInt,
                                MoveOnlyInt,
                                GetKeyFromValueIdentity<MoveOnlyInt>,
                                std::less<MoveOnlyInt>>;
 using EmplaceableTree = flat_tree<Emplaceable,
                                   Emplaceable,
                                   GetKeyFromValueIdentity<Emplaceable>,
                                   std::less<Emplaceable>>;
 using ReversedTree =
     flat_tree<int, int, GetKeyFromValueIdentity<int>, std::greater<int>>;
 
 using TreeWithStrangeCompare = flat_tree<int,
                                          int,
                                          GetKeyFromValueIdentity<int>,
                                          NonDefaultConstructibleCompare>;
 
 using ::testing::ElementsAre;
 
 }  // namespace
 
+TEST(FlatTree, LastUnique) {
+  using Pair = std::pair<int, int>;
+  using Vect = std::vector<Pair>;
+
+  auto cmp = [](const Pair& lhs, const Pair& rhs) {
+    return lhs.first == rhs.first;
+  };
+
+  // Empty case.
+  Vect empty;
+  EXPECT_EQ(empty.end(), LastUnique(empty.begin(), empty.end(), cmp));
+
+  // Single element.
+  Vect one;
+  one.push_back(Pair(1, 1));
+  EXPECT_EQ(one.end(), LastUnique(one.begin(), one.end(), cmp));
+  ASSERT_EQ(1u, one.size());
+  EXPECT_THAT(one, ElementsAre(Pair(1, 1)));
+
+  // Two elements, already unique.
+  Vect two_u;
+  two_u.push_back(Pair(1, 1));
+  two_u.push_back(Pair(2, 2));
+  EXPECT_EQ(two_u.end(), LastUnique(two_u.begin(), two_u.end(), cmp));
+  EXPECT_THAT(two_u, ElementsAre(Pair(1, 1), Pair(2, 2)));
+
+  // Two elements, dupes.
+  Vect two_d;
+  two_d.push_back(Pair(1, 1));
+  two_d.push_back(Pair(1, 2));
+  auto last = LastUnique(two_d.begin(), two_d.end(), cmp);
+  EXPECT_EQ(two_d.begin() + 1, last);
+  two_d.erase(last, two_d.end());
+  EXPECT_THAT(two_d, ElementsAre(Pair(1, 2)));
+
+  // Non-dupes, dupes, non-dupes.
+  Vect ndn;
+  ndn.push_back(Pair(1, 1));
+  ndn.push_back(Pair(2, 1));
+  ndn.push_back(Pair(2, 2));
+  ndn.push_back(Pair(2, 3));
+  ndn.push_back(Pair(3, 1));
+  last = LastUnique(ndn.begin(), ndn.end(), cmp);
+  EXPECT_EQ(ndn.begin() + 3, last);
+  ndn.erase(last, ndn.end());
+  EXPECT_THAT(ndn, ElementsAre(Pair(1, 1), Pair(2, 3), Pair(3, 1)));
+
+  // Dupes, non-dupes, dupes.
+  Vect dnd;
+  dnd.push_back(Pair(1, 1));
+  dnd.push_back(Pair(1, 2));
+  dnd.push_back(Pair(1, 3));
+  dnd.push_back(Pair(2, 1));
+  dnd.push_back(Pair(3, 1));
+  dnd.push_back(Pair(3, 2));
+  dnd.push_back(Pair(3, 3));
+  last = LastUnique(dnd.begin(), dnd.end(), cmp);
+  EXPECT_EQ(dnd.begin() + 3, last);
+  dnd.erase(last, dnd.end());
+  EXPECT_THAT(dnd, ElementsAre(Pair(1, 3), Pair(2, 1), Pair(3, 3)));
+}
+
 // ----------------------------------------------------------------------------
 // Class.
 
 // Check that flat_tree and its iterators can be instantiated with an
 // incomplete type.
 
 TEST(FlatTree, IncompleteType) {
   struct A {
     using Tree = flat_tree<A, A, GetKeyFromValueIdentity<A>, std::less<A>>;
     int data;
     Tree set_with_incomplete_type;
     Tree::iterator it;
     Tree::const_iterator cit;
 
     // 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}},
+            KEEP_FIRST_OF_DUPES);
+
+  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 32 matching lines @@
     EXPECT_THAT(cont, ElementsAre());
   }
 
   {
     TreeWithStrangeCompare cont(NonDefaultConstructibleCompare(0));
     EXPECT_THAT(cont, ElementsAre());
   }
 }
 
 // flat_tree(InputIterator first,
-//          InputIterator last,
-//          const Compare& comp = Compare())
+//           InputIterator last,
+//           FlatContainerDupes dupe_handling,
+//           const Compare& comp = Compare())
 
 TEST(FlatTree, RangeConstructor) {
   {
-    IntTree::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
+    IntPair input_vals[] = {{1, 1}, {1, 2}, {2, 1}, {2, 2}, {1, 3},
+                            {2, 3}, {3, 1}, {3, 2}, {3, 3}};
 
-    IntTree cont(MakeInputIterator(std::begin(input_vals)),
-                 MakeInputIterator(std::end(input_vals)));
-    EXPECT_THAT(cont, ElementsAre(1, 2, 3));
+    IntPairTree first_of(MakeInputIterator(std::begin(input_vals)),
+                         MakeInputIterator(std::end(input_vals)),
+                         KEEP_FIRST_OF_DUPES);
+    EXPECT_THAT(first_of,
+                ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1)));
+
+    IntPairTree last_of(MakeInputIterator(std::begin(input_vals)),
+                        MakeInputIterator(std::end(input_vals)),
+                        KEEP_LAST_OF_DUPES);
+    EXPECT_THAT(last_of,
+                ElementsAre(IntPair(1, 3), IntPair(2, 3), IntPair(3, 3)));
   }
   {
     TreeWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2,
                                                        2, 3, 3, 3};
 
     TreeWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)),
                                 MakeInputIterator(std::end(input_vals)),
+                                KEEP_FIRST_OF_DUPES,
                                 NonDefaultConstructibleCompare(0));
     EXPECT_THAT(cont, ElementsAre(1, 2, 3));
   }
 }
 
 // flat_tree(const flat_tree& x)
 
 TEST(FlatTree, CopyConstructor) {
-  IntTree original{1, 2, 3, 4};
+  IntTree original({1, 2, 3, 4}, KEEP_FIRST_OF_DUPES);
   IntTree copied(original);
 
   EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
 
   EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
   EXPECT_THAT(original, ElementsAre(1, 2, 3, 4));
   EXPECT_EQ(original, copied);
 }
 
 // flat_tree(flat_tree&& x)
 
 TEST(FlatTree, MoveConstructor) {
   int input_range[] = {1, 2, 3, 4};
 
-  MoveOnlyTree original(std::begin(input_range), std::end(input_range));
+  MoveOnlyTree original(std::begin(input_range), std::end(input_range),
+                        KEEP_FIRST_OF_DUPES);
   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>, FlatContainerDupes dupe_handling)
+
+TEST(FlatTree, VectorConstructor) {
+  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), KEEP_FIRST_OF_DUPES);
+
+  // 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());
+
+  // Test KEEP_LAST_OF_DUPES with a simple vector constructor.
+  std::vector<IntPair> int_storage{{1, 1}, {1, 2}, {2, 1}};
+  IntPairTree int_tree(std::move(int_storage), KEEP_LAST_OF_DUPES);
+  EXPECT_THAT(int_tree, ElementsAre(IntPair(1, 2), IntPair(2, 1)));
+}
+
+// flat_tree(std::initializer_list<value_type> ilist,
+//           FlatContainerDupes dupe_handling,
 //           const Compare& comp = Compare())
 
 TEST(FlatTree, InitializerListConstructor) {
   {
-    IntTree cont{1, 2, 3, 4, 5, 6, 10, 8};
+    IntTree cont({1, 2, 3, 4, 5, 6, 10, 8}, KEEP_FIRST_OF_DUPES);
     EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
   }
   {
-    TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8},
+    IntTree cont({1, 2, 3, 4, 5, 6, 10, 8}, KEEP_FIRST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
+  }
+  {
+    TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8}, KEEP_FIRST_OF_DUPES,
                                 NonDefaultConstructibleCompare(0));
     EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
   }
+  {
+    IntPairTree first_of({{1, 1}, {2, 1}, {1, 2}}, KEEP_FIRST_OF_DUPES);
+    EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
+  }
+  {
+    IntPairTree last_of({{1, 1}, {2, 1}, {1, 2}}, KEEP_LAST_OF_DUPES);
+    EXPECT_THAT(last_of, ElementsAre(IntPair(1, 2), IntPair(2, 1)));
+  }
 }
 
 // ----------------------------------------------------------------------------
 // Assignments.
 
 // flat_tree& operator=(const flat_tree&)
 
 TEST(FlatTree, CopyAssignable) {
-  IntTree original{1, 2, 3, 4};
+  IntTree original({1, 2, 3, 4}, KEEP_FIRST_OF_DUPES);
   IntTree copied;
   copied = original;
 
   EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
   EXPECT_THAT(original, ElementsAre(1, 2, 3, 4));
   EXPECT_EQ(original, copied);
 }
 
 // flat_tree& operator=(flat_tree&&)
 
 TEST(FlatTree, MoveAssignable) {
   int input_range[] = {1, 2, 3, 4};
 
-  MoveOnlyTree original(std::begin(input_range), std::end(input_range));
+  MoveOnlyTree original(std::begin(input_range), std::end(input_range),
+                        KEEP_FIRST_OF_DUPES);
   MoveOnlyTree moved;
   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& operator=(std::initializer_list<value_type> ilist)
 
 TEST(FlatTree, InitializerListAssignable) {
-  IntTree cont{0};
+  IntTree cont({0}, KEEP_FIRST_OF_DUPES);
   cont = {1, 2, 3, 4, 5, 6, 10, 8};
 
   EXPECT_EQ(0U, cont.count(0));
   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
 }
 
 // --------------------------------------------------------------------------
 // Memory management.
 
 // void reserve(size_type new_capacity)
 
 TEST(FlatTree, Reserve) {
-  IntTree cont{1, 2, 3};
+  IntTree cont({1, 2, 3}, KEEP_FIRST_OF_DUPES);
 
   cont.reserve(5);
   EXPECT_LE(5U, cont.capacity());
 }
 
 // size_type capacity() const
 
 TEST(FlatTree, Capacity) {
-  IntTree cont{1, 2, 3};
+  IntTree cont({1, 2, 3}, KEEP_FIRST_OF_DUPES);
 
   EXPECT_LE(cont.size(), cont.capacity());
   cont.reserve(5);
   EXPECT_LE(cont.size(), cont.capacity());
 }
 
 // void shrink_to_fit()
 
 TEST(FlatTree, ShrinkToFit) {
-  IntTree cont{1, 2, 3};
+  IntTree cont({1, 2, 3}, KEEP_FIRST_OF_DUPES);
 
   IntTree::size_type capacity_before = cont.capacity();
   cont.shrink_to_fit();
   EXPECT_GE(capacity_before, cont.capacity());
 }
 
 // ----------------------------------------------------------------------------
 // Size management.
 
 // void clear()
 
 TEST(FlatTree, Clear) {
-  IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
+  IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
   cont.clear();
   EXPECT_THAT(cont, ElementsAre());
 }
 
 // size_type size() const
 
 TEST(FlatTree, Size) {
   IntTree cont;
 
   EXPECT_EQ(0U, cont.size());
@@ skipping 35 matching lines @@
 // const_reverse_iterator rbegin() const
 // reverse_iterator rend()
 // const_reverse_iterator rend() const
 //
 // const_iterator cbegin() const
 // const_iterator cend() const
 // const_reverse_iterator crbegin() const
 // const_reverse_iterator crend() const
 
 TEST(FlatTree, Iterators) {
-  IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
+  IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
 
   auto size = static_cast<IntTree::difference_type>(cont.size());
 
   EXPECT_EQ(size, std::distance(cont.begin(), cont.end()));
   EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend()));
   EXPECT_EQ(size, std::distance(cont.rbegin(), cont.rend()));
   EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend()));
 
   {
     IntTree::iterator it = cont.begin();
@@ skipping 202 matching lines @@
     EXPECT_EQ(2, *result);
   }
 }
 
 // ----------------------------------------------------------------------------
 // Erase operations.
 
 // iterator erase(const_iterator position_hint)
 
 TEST(FlatTree, ErasePosition) {
-  IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
+  IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
 
   IntTree::iterator it = cont.erase(std::next(cont.cbegin(), 3));
   EXPECT_EQ(std::next(cont.begin(), 3), it);
   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
 
   it = cont.erase(std::next(cont.cbegin(), 0));
   EXPECT_EQ(cont.begin(), it);
   EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
 
   it = cont.erase(std::next(cont.cbegin(), 5));
@@ skipping 17 matching lines @@
   EXPECT_THAT(cont, ElementsAre(5));
 
   it = cont.erase(cont.cbegin());
   EXPECT_EQ(cont.begin(), it);
   EXPECT_EQ(cont.end(), it);
 }
 
 // iterator erase(const_iterator first, const_iterator last)
 
 TEST(FlatTree, EraseRange) {
-  IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
+  IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
 
   IntTree::iterator it =
       cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5));
   EXPECT_EQ(std::next(cont.begin(), 5), it);
   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8));
 
   it = cont.erase(std::next(cont.cbegin(), 3), std::next(cont.cbegin(), 4));
   EXPECT_EQ(std::next(cont.begin(), 3), it);
   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
 
   it = cont.erase(std::next(cont.cbegin(), 2), std::next(cont.cbegin(), 5));
   EXPECT_EQ(std::next(cont.begin(), 2), it);
   EXPECT_THAT(cont, ElementsAre(1, 2, 7, 8));
 
   it = cont.erase(std::next(cont.cbegin(), 0), std::next(cont.cbegin(), 2));
   EXPECT_EQ(std::next(cont.begin(), 0), it);
   EXPECT_THAT(cont, ElementsAre(7, 8));
 
   it = cont.erase(cont.cbegin(), cont.cend());
   EXPECT_EQ(cont.begin(), it);
   EXPECT_EQ(cont.end(), it);
 }
 
 // size_type erase(const key_type& key)
 
 TEST(FlatTree, EraseKey) {
-  IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
+  IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
 
   EXPECT_EQ(0U, cont.erase(9));
   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8));
 
   EXPECT_EQ(1U, cont.erase(4));
   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
 
   EXPECT_EQ(1U, cont.erase(1));
   EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
 
@@ skipping 15 matching lines @@
   EXPECT_EQ(1U, cont.erase(5));
   EXPECT_THAT(cont, ElementsAre());
 }
 
 // ----------------------------------------------------------------------------
 // Comparators.
 
 // key_compare key_comp() const
 
 TEST(FlatTree, KeyComp) {
-  ReversedTree cont{1, 2, 3, 4, 5};
+  ReversedTree cont({1, 2, 3, 4, 5}, KEEP_FIRST_OF_DUPES);
 
   EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp()));
   int new_elements[] = {6, 7, 8, 9, 10};
   std::copy(std::begin(new_elements), std::end(new_elements),
             std::inserter(cont, cont.end()));
   EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp()));
 }
 
 // value_compare value_comp() const
 
 TEST(FlatTree, ValueComp) {
-  ReversedTree cont{1, 2, 3, 4, 5};
+  ReversedTree cont({1, 2, 3, 4, 5}, KEEP_FIRST_OF_DUPES);
 
   EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp()));
   int new_elements[] = {6, 7, 8, 9, 10};
   std::copy(std::begin(new_elements), std::end(new_elements),
             std::inserter(cont, cont.end()));
   EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp()));
 }
 
 // ----------------------------------------------------------------------------
 // Search operations.
 
 // size_type count(const key_type& key) const
 
 TEST(FlatTree, Count) {
   {
-    const IntTree cont{5, 6, 7, 8, 9, 10, 11, 12};
+    const IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(1U, cont.count(5));
     EXPECT_EQ(1U, cont.count(6));
     EXPECT_EQ(1U, cont.count(7));
     EXPECT_EQ(1U, cont.count(8));
     EXPECT_EQ(1U, cont.count(9));
     EXPECT_EQ(1U, cont.count(10));
     EXPECT_EQ(1U, cont.count(11));
     EXPECT_EQ(1U, cont.count(12));
     EXPECT_EQ(0U, cont.count(4));
   }
   {
-    const IntTreeWithLess cont{5, 6, 7, 8, 9, 10, 11, 12};
+    const IntTreeWithLess cont({5, 6, 7, 8, 9, 10, 11, 12},
+                               KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(1U, cont.count(5));
     EXPECT_EQ(1U, cont.count(6));
     EXPECT_EQ(1U, cont.count(7));
     EXPECT_EQ(1U, cont.count(8));
     EXPECT_EQ(1U, cont.count(9));
     EXPECT_EQ(1U, cont.count(10));
     EXPECT_EQ(1U, cont.count(11));
     EXPECT_EQ(1U, cont.count(12));
     EXPECT_EQ(0U, cont.count(4));
   }
 }
 
 // iterator find(const key_type& key)
 // const_iterator find(const key_type& key) const
 
 TEST(FlatTree, Find) {
   {
-    IntTree cont{5, 6, 7, 8, 9, 10, 11, 12};
+    IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(cont.begin(), cont.find(5));
     EXPECT_EQ(std::next(cont.begin()), cont.find(6));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
   }
   {
-    const IntTree cont{5, 6, 7, 8, 9, 10, 11, 12};
+    const IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(cont.begin(), cont.find(5));
     EXPECT_EQ(std::next(cont.begin()), cont.find(6));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
   }
   {
-    IntTreeWithLess cont{5, 6, 7, 8, 9, 10, 11, 12};
+    IntTreeWithLess cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(cont.begin(), cont.find(5));
     EXPECT_EQ(std::next(cont.begin()), cont.find(6));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
   }
 }
 
 // pair<iterator, iterator> equal_range(const key_type& key)
 // pair<const_iterator, const_iterator> equal_range(const key_type& key) const
 
 TEST(FlatTree, EqualRange) {
   {
-    IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+    IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
 
     std::pair<IntTree::iterator, IntTree::iterator> result =
         cont.equal_range(5);
     EXPECT_EQ(std::next(cont.begin(), 0), result.first);
     EXPECT_EQ(std::next(cont.begin(), 1), result.second);
     result = cont.equal_range(7);
     EXPECT_EQ(std::next(cont.begin(), 1), result.first);
     EXPECT_EQ(std::next(cont.begin(), 2), result.second);
     result = cont.equal_range(9);
     EXPECT_EQ(std::next(cont.begin(), 2), result.first);
@@ skipping 35 matching lines @@
     EXPECT_EQ(std::next(cont.begin(), 6), result.first);
     EXPECT_EQ(std::next(cont.begin(), 6), result.second);
     result = cont.equal_range(18);
     EXPECT_EQ(std::next(cont.begin(), 7), result.first);
     EXPECT_EQ(std::next(cont.begin(), 7), result.second);
     result = cont.equal_range(20);
     EXPECT_EQ(std::next(cont.begin(), 8), result.first);
     EXPECT_EQ(std::next(cont.begin(), 8), result.second);
   }
   {
-    const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+    const IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
 
     std::pair<IntTree::const_iterator, IntTree::const_iterator> result =
         cont.equal_range(5);
     EXPECT_EQ(std::next(cont.begin(), 0), result.first);
     EXPECT_EQ(std::next(cont.begin(), 1), result.second);
     result = cont.equal_range(7);
     EXPECT_EQ(std::next(cont.begin(), 1), result.first);
     EXPECT_EQ(std::next(cont.begin(), 2), result.second);
     result = cont.equal_range(9);
     EXPECT_EQ(std::next(cont.begin(), 2), result.first);
@@ skipping 35 matching lines @@
     EXPECT_EQ(std::next(cont.begin(), 6), result.first);
     EXPECT_EQ(std::next(cont.begin(), 6), result.second);
     result = cont.equal_range(18);
     EXPECT_EQ(std::next(cont.begin(), 7), result.first);
     EXPECT_EQ(std::next(cont.begin(), 7), result.second);
     result = cont.equal_range(20);
     EXPECT_EQ(std::next(cont.begin(), 8), result.first);
     EXPECT_EQ(std::next(cont.begin(), 8), result.second);
   }
   {
-    IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19};
+    IntTreeWithLess cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
 
     std::pair<IntTree::iterator, IntTree::iterator> result =
         cont.equal_range(5);
     EXPECT_EQ(std::next(cont.begin(), 0), result.first);
     EXPECT_EQ(std::next(cont.begin(), 1), result.second);
     result = cont.equal_range(7);
     EXPECT_EQ(std::next(cont.begin(), 1), result.first);
     EXPECT_EQ(std::next(cont.begin(), 2), result.second);
     result = cont.equal_range(9);
     EXPECT_EQ(std::next(cont.begin(), 2), result.first);
@@ skipping 41 matching lines @@
     EXPECT_EQ(std::next(cont.begin(), 8), result.first);
     EXPECT_EQ(std::next(cont.begin(), 8), result.second);
   }
 }
 
 //       iterator lower_bound(const key_type& key);
 // const_iterator lower_bound(const key_type& key) const;
 
 TEST(FlatTree, LowerBound) {
   {
-    IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+    IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(cont.begin(), cont.lower_bound(5));
     EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19));
     EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
     EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
   }
   {
-    const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+    const IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(cont.begin(), cont.lower_bound(5));
     EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19));
     EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
     EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
   }
   {
-    IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19};
+    IntTreeWithLess cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(cont.begin(), cont.lower_bound(5));
     EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19));
     EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
     EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
   }
 }
 
 // iterator upper_bound(const key_type& key)
 // const_iterator upper_bound(const key_type& key) const
 
 TEST(FlatTree, UpperBound) {
   {
-    IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+    IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19));
     EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
   }
   {
-    const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+    const IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19));
     EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
   }
   {
-    IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19};
+    IntTreeWithLess cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19));
     EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
     EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
     EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
     EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
     EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
     EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
   }
 }
 
 // ----------------------------------------------------------------------------
 // General operations.
 
 // void swap(flat_tree& other)
 // void swap(flat_tree& lhs, flat_tree& rhs)
 
 TEST(FlatTreeOurs, Swap) {
-  IntTree x{1, 2, 3};
-  IntTree y{4};
+  IntTree x({1, 2, 3}, KEEP_FIRST_OF_DUPES);
+  IntTree y({4}, KEEP_FIRST_OF_DUPES);
   swap(x, y);
   EXPECT_THAT(x, ElementsAre(4));
   EXPECT_THAT(y, ElementsAre(1, 2, 3));
 
   y.swap(x);
   EXPECT_THAT(x, ElementsAre(1, 2, 3));
   EXPECT_THAT(y, ElementsAre(4));
 }
 
 // bool operator==(const flat_tree& lhs, const flat_tree& rhs)
 // bool operator!=(const flat_tree& lhs, const flat_tree& rhs)
 // bool operator<(const flat_tree& lhs, const flat_tree& rhs)
 // bool operator>(const flat_tree& lhs, const flat_tree& rhs)
 // bool operator<=(const flat_tree& lhs, const flat_tree& rhs)
 // bool operator>=(const flat_tree& lhs, const flat_tree& rhs)
 
 TEST(FlatTree, Comparison) {
   // Provided comparator does not participate in comparison.
-  ReversedTree biggest{3};
-  ReversedTree smallest{1};
-  ReversedTree middle{1, 2};
+  ReversedTree biggest({3}, KEEP_FIRST_OF_DUPES);
+  ReversedTree smallest({1}, KEEP_FIRST_OF_DUPES);
+  ReversedTree middle({1, 2}, KEEP_FIRST_OF_DUPES);
 
   EXPECT_EQ(biggest, biggest);
   EXPECT_NE(biggest, smallest);
   EXPECT_LT(smallest, middle);
   EXPECT_LE(smallest, middle);
   EXPECT_LE(middle, middle);
   EXPECT_GT(biggest, middle);
   EXPECT_GE(biggest, middle);
   EXPECT_GE(biggest, biggest);
 }
 
 TEST(FlatSet, EraseIf) {
   IntTree x;
   EraseIf(x, [](int) { return false; });
   EXPECT_THAT(x, ElementsAre());
 
   x = {1, 2, 3};
   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