Add a flat_map container

base/containers/flat_tree_unittest.cc

Index: base/containers/flat_tree_unittest.cc
diff --git a/base/containers/flat_set_unittest.cc b/base/containers/flat_tree_unittest.cc
similarity index 67%
copy from base/containers/flat_set_unittest.cc
copy to base/containers/flat_tree_unittest.cc
index 1c7a46a026f3da16d366b234092b6482410551d6..1c952876a6b2efbbd4d11b9476d46488e9bc6d0c 100644
--- a/base/containers/flat_set_unittest.cc
+++ b/base/containers/flat_tree_unittest.cc
@@ -2,7 +2,7 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "base/containers/flat_set.h"
+#include "base/containers/flat_tree.h"
 
 // Following tests are ported and extended tests from libcpp for std::set.
 // They can be found here:
@@ -37,33 +37,15 @@
 #include <string>
 #include <vector>
 
+#include "base/containers/container_test_utils.h"
 #include "base/macros.h"
 #include "testing/gmock/include/gmock/gmock.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
-namespace {
-
-class MoveOnly {
- public:
-  explicit MoveOnly(int data = 1) : data_(data) {}
-  MoveOnly(MoveOnly&& other) : data_(other.data_) { other.data_ = 0; }
-  MoveOnly& operator=(MoveOnly&& other) {
-    data_ = other.data_;
-    other.data_ = 0;
-    return *this;
-  }
+namespace base {
+namespace internal {
 
-  friend bool operator<(const MoveOnly& lhs, const MoveOnly& rhs) {
-    return lhs.data_ < rhs.data_;
-  }
-
-  int data() const { return data_; }
-
- private:
-  int data_;
-
-  DISALLOW_COPY_AND_ASSIGN(MoveOnly);
-};
+namespace {
 
 template <class It>
 class InputIterator {
@@ -143,23 +125,31 @@ class NonDefaultConstructibleCompare {
   explicit NonDefaultConstructibleCompare(int) {}
 
   template <typename T>
-  bool operator()(const T& lhs, const T& rhs) {
+  bool operator()(const T& lhs, const T& rhs) const {
     return std::less<T>()(lhs, rhs);
   }
 };
 
-// Common test sets.
-using IntSet = base::flat_set<int>;
-using MoveOnlySet = base::flat_set<MoveOnly>;
-using EmplaceableSet = base::flat_set<Emplaceable>;
-using ReversedSet = base::flat_set<int, std::greater<int>>;
-
-// TODO(dyaroshev): replace less<int> with less<>, once we have it
-// crbug.com/682254.
-using SetWithLess = base::flat_set<int, std::less<int>>;
-
-using SetWithStrangeCompare =
-    base::flat_set<int, NonDefaultConstructibleCompare>;
+using ::base::internal::GetKeyFromValueIdentity;
+
+// Common test trees.
+using IntTree =
+    flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>;
+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;
 
@@ -168,16 +158,16 @@ using ::testing::ElementsAre;
 // ----------------------------------------------------------------------------
 // Class.
 
-// Check that base::flat_set and its iterators can be instantiated with an
+// Check that flat_tree and its iterators can be instantiated with an
 // incomplete type.
 
-TEST(FlatSet, IncompleteType) {
+TEST(FlatTree, IncompleteType) {
   struct A {
-    using Set = base::flat_set<A>;
+    using Tree = flat_tree<A, A, GetKeyFromValueIdentity<A>, std::less<A>>;
     int data;
-    Set set_with_incomplete_type;
-    Set::iterator it;
-    Set::const_iterator cit;
+    Tree set_with_incomplete_type;
+    Tree::iterator it;
+    Tree::const_iterator cit;
 
     // We do not declare operator< because clang complains that it's unused.
   };
@@ -185,19 +175,20 @@ TEST(FlatSet, IncompleteType) {
   A a;
 }
 
-TEST(FlatSet, Stability) {
+TEST(FlatTree, Stability) {
   using Pair = std::pair<int, int>;
 
   struct LessByFirst {
-    bool operator()(const Pair& lhs, const Pair& rhs) {
+    bool operator()(const Pair& lhs, const Pair& rhs) const {
       return lhs.first < rhs.first;
     }
   };
 
-  using Set = base::flat_set<Pair, LessByFirst>;
+  using Tree =
+      flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst>;
 
   // Constructors are not stable.
-  Set cont{{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}};
+  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(),
@@ -237,65 +228,65 @@ TEST(FlatSet, Stability) {
 // reverse_iterator
 // const_reverse_iterator
 
-TEST(FlatSet, Types) {
+TEST(FlatTree, Types) {
   // These are guaranteed to be portable.
-  static_assert((std::is_same<int, IntSet::key_type>::value), "");
-  static_assert((std::is_same<int, IntSet::value_type>::value), "");
-  static_assert((std::is_same<std::less<int>, IntSet::key_compare>::value), "");
-  static_assert((std::is_same<std::less<int>, IntSet::value_compare>::value),
+  static_assert((std::is_same<int, IntTree::key_type>::value), "");
+  static_assert((std::is_same<int, IntTree::value_type>::value), "");
+  static_assert((std::is_same<std::less<int>, IntTree::key_compare>::value),
+                "");
+  static_assert((std::is_same<int&, IntTree::reference>::value), "");
+  static_assert((std::is_same<const int&, IntTree::const_reference>::value),
                 "");
-  static_assert((std::is_same<int&, IntSet::reference>::value), "");
-  static_assert((std::is_same<const int&, IntSet::const_reference>::value), "");
-  static_assert((std::is_same<int*, IntSet::pointer>::value), "");
-  static_assert((std::is_same<const int*, IntSet::const_pointer>::value), "");
+  static_assert((std::is_same<int*, IntTree::pointer>::value), "");
+  static_assert((std::is_same<const int*, IntTree::const_pointer>::value), "");
 }
 
 // ----------------------------------------------------------------------------
 // Lifetime.
 
-// flat_set()
-// flat_set(const Compare& comp)
+// flat_tree()
+// flat_tree(const Compare& comp)
 
-TEST(FlatSet, DefaultConstructor) {
+TEST(FlatTree, DefaultConstructor) {
   {
-    IntSet cont;
+    IntTree cont;
     EXPECT_THAT(cont, ElementsAre());
   }
 
   {
-    SetWithStrangeCompare cont(NonDefaultConstructibleCompare(0));
+    TreeWithStrangeCompare cont(NonDefaultConstructibleCompare(0));
     EXPECT_THAT(cont, ElementsAre());
   }
 }
 
-// flat_set(InputIterator first,
+// flat_tree(InputIterator first,
 //          InputIterator last,
 //          const Compare& comp = Compare())
 
-TEST(FlatSet, RangeConstructor) {
+TEST(FlatTree, RangeConstructor) {
   {
-    IntSet::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
+    IntTree::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
 
-    IntSet cont(MakeInputIterator(std::begin(input_vals)),
-                MakeInputIterator(std::end(input_vals)));
+    IntTree cont(MakeInputIterator(std::begin(input_vals)),
+                 MakeInputIterator(std::end(input_vals)));
     EXPECT_THAT(cont, ElementsAre(1, 2, 3));
   }
   {
-    SetWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2,
-                                                      2, 3, 3, 3};
+    TreeWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2,
+                                                       2, 3, 3, 3};
 
-    SetWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)),
-                               MakeInputIterator(std::end(input_vals)),
-                               NonDefaultConstructibleCompare(0));
+    TreeWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)),
+                                MakeInputIterator(std::end(input_vals)),
+                                NonDefaultConstructibleCompare(0));
     EXPECT_THAT(cont, ElementsAre(1, 2, 3));
   }
 }
 
-// flat_set(const flat_set& x)
+// flat_tree(const flat_tree& x)
 
-TEST(FlatSet, CopyConstructor) {
-  IntSet original{1, 2, 3, 4};
-  IntSet copied(original);
+TEST(FlatTree, CopyConstructor) {
+  IntTree original{1, 2, 3, 4};
+  IntTree copied(original);
 
   EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
 
@@ -304,31 +295,31 @@ TEST(FlatSet, CopyConstructor) {
   EXPECT_EQ(original, copied);
 }
 
-// flat_set(flat_set&& x)
+// flat_tree(flat_tree&& x)
 
-TEST(FlatSet, MoveConstructor) {
+TEST(FlatTree, MoveConstructor) {
   int input_range[] = {1, 2, 3, 4};
 
-  MoveOnlySet original(std::begin(input_range), std::end(input_range));
-  MoveOnlySet moved(std::move(original));
+  MoveOnlyTree original(std::begin(input_range), std::end(input_range));
+  MoveOnlyTree moved(std::move(original));
 
-  EXPECT_EQ(1U, moved.count(MoveOnly(1)));
-  EXPECT_EQ(1U, moved.count(MoveOnly(2)));
-  EXPECT_EQ(1U, moved.count(MoveOnly(3)));
-  EXPECT_EQ(1U, moved.count(MoveOnly(4)));
+  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_set(std::initializer_list<value_type> ilist,
+//  flat_tree(std::initializer_list<value_type> ilist,
 //           const Compare& comp = Compare())
 
-TEST(FlatSet, InitializerListConstructor) {
+TEST(FlatTree, InitializerListConstructor) {
   {
-    IntSet cont{1, 2, 3, 4, 5, 6, 10, 8};
+    IntTree cont{1, 2, 3, 4, 5, 6, 10, 8};
     EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
   }
   {
-    SetWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8},
-                               NonDefaultConstructibleCompare(0));
+    TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8},
+                                NonDefaultConstructibleCompare(0));
     EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
   }
 }
@@ -336,11 +327,11 @@ TEST(FlatSet, InitializerListConstructor) {
 // ----------------------------------------------------------------------------
 // Assignments.
 
-// flat_set& operator=(const flat_set&)
+// flat_tree& operator=(const flat_tree&)
 
-TEST(FlatSet, CopyAssignable) {
-  IntSet original{1, 2, 3, 4};
-  IntSet copied;
+TEST(FlatTree, CopyAssignable) {
+  IntTree original{1, 2, 3, 4};
+  IntTree copied;
   copied = original;
 
   EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
@@ -348,25 +339,25 @@ TEST(FlatSet, CopyAssignable) {
   EXPECT_EQ(original, copied);
 }
 
-// flat_set& operator=(flat_set&&)
+// flat_tree& operator=(flat_tree&&)
 
-TEST(FlatSet, MoveAssignable) {
+TEST(FlatTree, MoveAssignable) {
   int input_range[] = {1, 2, 3, 4};
 
-  MoveOnlySet original(std::begin(input_range), std::end(input_range));
-  MoveOnlySet moved;
+  MoveOnlyTree original(std::begin(input_range), std::end(input_range));
+  MoveOnlyTree moved;
   moved = std::move(original);
 
-  EXPECT_EQ(1U, moved.count(MoveOnly(1)));
-  EXPECT_EQ(1U, moved.count(MoveOnly(2)));
-  EXPECT_EQ(1U, moved.count(MoveOnly(3)));
-  EXPECT_EQ(1U, moved.count(MoveOnly(4)));
+  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_set& operator=(std::initializer_list<value_type> ilist)
+// flat_tree& operator=(std::initializer_list<value_type> ilist)
 
-TEST(FlatSet, InitializerListAssignable) {
-  IntSet cont{0};
+TEST(FlatTree, InitializerListAssignable) {
+  IntTree cont{0};
   cont = {1, 2, 3, 4, 5, 6, 10, 8};
 
   EXPECT_EQ(0U, cont.count(0));
@@ -378,8 +369,8 @@ TEST(FlatSet, InitializerListAssignable) {
 
 // void reserve(size_type new_capacity)
 
-TEST(FlatSet, Reserve) {
-  IntSet cont{1, 2, 3};
+TEST(FlatTree, Reserve) {
+  IntTree cont{1, 2, 3};
 
   cont.reserve(5);
   EXPECT_LE(5U, cont.capacity());
@@ -387,8 +378,8 @@ TEST(FlatSet, Reserve) {
 
 // size_type capacity() const
 
-TEST(FlatSet, Capacity) {
-  IntSet cont{1, 2, 3};
+TEST(FlatTree, Capacity) {
+  IntTree cont{1, 2, 3};
 
   EXPECT_LE(cont.size(), cont.capacity());
   cont.reserve(5);
@@ -397,10 +388,10 @@ TEST(FlatSet, Capacity) {
 
 // void shrink_to_fit()
 
-TEST(FlatSet, ShrinkToFit) {
-  IntSet cont{1, 2, 3};
+TEST(FlatTree, ShrinkToFit) {
+  IntTree cont{1, 2, 3};
 
-  IntSet::size_type capacity_before = cont.capacity();
+  IntTree::size_type capacity_before = cont.capacity();
   cont.shrink_to_fit();
   EXPECT_GE(capacity_before, cont.capacity());
 }
@@ -410,16 +401,16 @@ TEST(FlatSet, ShrinkToFit) {
 
 // void clear()
 
-TEST(FlatSet, Clear) {
-  IntSet cont{1, 2, 3, 4, 5, 6, 7, 8};
+TEST(FlatTree, Clear) {
+  IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
   cont.clear();
   EXPECT_THAT(cont, ElementsAre());
 }
 
 // size_type size() const
 
-TEST(FlatSet, Size) {
-  IntSet cont;
+TEST(FlatTree, Size) {
+  IntTree cont;
 
   EXPECT_EQ(0U, cont.size());
   cont.insert(2);
@@ -438,8 +429,8 @@ TEST(FlatSet, Size) {
 
 // bool empty() const
 
-TEST(FlatSet, Empty) {
-  IntSet cont;
+TEST(FlatTree, Empty) {
+  IntTree cont;
 
   EXPECT_TRUE(cont.empty());
   cont.insert(1);
@@ -466,10 +457,10 @@ TEST(FlatSet, Empty) {
 // const_reverse_iterator crbegin() const
 // const_reverse_iterator crend() const
 
-TEST(FlatSet, Iterators) {
-  IntSet cont{1, 2, 3, 4, 5, 6, 7, 8};
+TEST(FlatTree, Iterators) {
+  IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
 
-  auto size = static_cast<IntSet::difference_type>(cont.size());
+  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()));
@@ -477,8 +468,8 @@ TEST(FlatSet, Iterators) {
   EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend()));
 
   {
-    IntSet::iterator it = cont.begin();
-    IntSet::const_iterator c_it = cont.cbegin();
+    IntTree::iterator it = cont.begin();
+    IntTree::const_iterator c_it = cont.cbegin();
     EXPECT_EQ(it, c_it);
     for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) {
       EXPECT_EQ(j, *it);
@@ -486,8 +477,8 @@ TEST(FlatSet, Iterators) {
     }
   }
   {
-    IntSet::reverse_iterator rit = cont.rbegin();
-    IntSet::const_reverse_iterator c_rit = cont.crbegin();
+    IntTree::reverse_iterator rit = cont.rbegin();
+    IntTree::const_reverse_iterator c_rit = cont.crbegin();
     EXPECT_EQ(rit, c_rit);
     for (int j = static_cast<int>(size); rit != cont.rend();
          ++rit, ++c_rit, --j) {
@@ -502,11 +493,11 @@ TEST(FlatSet, Iterators) {
 
 // pair<iterator, bool> insert(const value_type& val)
 
-TEST(FlatSet, InsertLValue) {
-  IntSet cont;
+TEST(FlatTree, InsertLValue) {
+  IntTree cont;
 
   int value = 2;
-  std::pair<IntSet::iterator, bool> result = cont.insert(value);
+  std::pair<IntTree::iterator, bool> result = cont.insert(value);
   EXPECT_TRUE(result.second);
   EXPECT_EQ(cont.begin(), result.first);
   EXPECT_EQ(1U, cont.size());
@@ -536,28 +527,28 @@ TEST(FlatSet, InsertLValue) {
 
 // pair<iterator, bool> insert(value_type&& val)
 
-TEST(FlatSet, InsertRValue) {
-  MoveOnlySet cont;
+TEST(FlatTree, InsertRValue) {
+  MoveOnlyTree cont;
 
-  std::pair<MoveOnlySet::iterator, bool> result = cont.insert(MoveOnly(2));
+  std::pair<MoveOnlyTree::iterator, bool> result = cont.insert(MoveOnlyInt(2));
   EXPECT_TRUE(result.second);
   EXPECT_EQ(cont.begin(), result.first);
   EXPECT_EQ(1U, cont.size());
   EXPECT_EQ(2, result.first->data());
 
-  result = cont.insert(MoveOnly(1));
+  result = cont.insert(MoveOnlyInt(1));
   EXPECT_TRUE(result.second);
   EXPECT_EQ(cont.begin(), result.first);
   EXPECT_EQ(2U, cont.size());
   EXPECT_EQ(1, result.first->data());
 
-  result = cont.insert(MoveOnly(3));
+  result = cont.insert(MoveOnlyInt(3));
   EXPECT_TRUE(result.second);
   EXPECT_EQ(std::prev(cont.end()), result.first);
   EXPECT_EQ(3U, cont.size());
   EXPECT_EQ(3, result.first->data());
 
-  result = cont.insert(MoveOnly(3));
+  result = cont.insert(MoveOnlyInt(3));
   EXPECT_FALSE(result.second);
   EXPECT_EQ(std::prev(cont.end()), result.first);
   EXPECT_EQ(3U, cont.size());
@@ -566,10 +557,10 @@ TEST(FlatSet, InsertRValue) {
 
 // iterator insert(const_iterator position_hint, const value_type& val)
 
-TEST(FlatSet, InsertPositionLValue) {
-  IntSet cont;
+TEST(FlatTree, InsertPositionLValue) {
+  IntTree cont;
 
-  IntSet::iterator result = cont.insert(cont.cend(), 2);
+  IntTree::iterator result = cont.insert(cont.cend(), 2);
   EXPECT_EQ(cont.begin(), result);
   EXPECT_EQ(1U, cont.size());
   EXPECT_EQ(2, *result);
@@ -592,25 +583,25 @@ TEST(FlatSet, InsertPositionLValue) {
 
 // iterator insert(const_iterator position_hint, value_type&& val)
 
-TEST(FlatSet, InsertPositionRValue) {
-  MoveOnlySet cont;
+TEST(FlatTree, InsertPositionRValue) {
+  MoveOnlyTree cont;
 
-  MoveOnlySet::iterator result = cont.insert(cont.cend(), MoveOnly(2));
+  MoveOnlyTree::iterator result = cont.insert(cont.cend(), MoveOnlyInt(2));
   EXPECT_EQ(cont.begin(), result);
   EXPECT_EQ(1U, cont.size());
   EXPECT_EQ(2, result->data());
 
-  result = cont.insert(cont.cend(), MoveOnly(1));
+  result = cont.insert(cont.cend(), MoveOnlyInt(1));
   EXPECT_EQ(cont.begin(), result);
   EXPECT_EQ(2U, cont.size());
   EXPECT_EQ(1, result->data());
 
-  result = cont.insert(cont.cend(), MoveOnly(3));
+  result = cont.insert(cont.cend(), MoveOnlyInt(3));
   EXPECT_EQ(std::prev(cont.end()), result);
   EXPECT_EQ(3U, cont.size());
   EXPECT_EQ(3, result->data());
 
-  result = cont.insert(cont.cend(), MoveOnly(3));
+  result = cont.insert(cont.cend(), MoveOnlyInt(3));
   EXPECT_EQ(std::prev(cont.end()), result);
   EXPECT_EQ(3U, cont.size());
   EXPECT_EQ(3, result->data());
@@ -619,11 +610,11 @@ TEST(FlatSet, InsertPositionRValue) {
 // template <class... Args>
 // pair<iterator, bool> emplace(Args&&... args)
 
-TEST(FlatSet, Emplace) {
+TEST(FlatTree, Emplace) {
   {
-    EmplaceableSet cont;
+    EmplaceableTree cont;
 
-    std::pair<EmplaceableSet::iterator, bool> result = cont.emplace();
+    std::pair<EmplaceableTree::iterator, bool> result = cont.emplace();
     EXPECT_TRUE(result.second);
     EXPECT_EQ(cont.begin(), result.first);
     EXPECT_EQ(1U, cont.size());
@@ -642,9 +633,9 @@ TEST(FlatSet, Emplace) {
     EXPECT_EQ(Emplaceable(2, 3.5), *result.first);
   }
   {
-    IntSet cont;
+    IntTree cont;
 
-    std::pair<IntSet::iterator, bool> result = cont.emplace(2);
+    std::pair<IntTree::iterator, bool> result = cont.emplace(2);
     EXPECT_TRUE(result.second);
     EXPECT_EQ(cont.begin(), result.first);
     EXPECT_EQ(1U, cont.size());
@@ -655,11 +646,11 @@ TEST(FlatSet, Emplace) {
 // template <class... Args>
 // iterator emplace_hint(const_iterator position_hint, Args&&... args)
 
-TEST(FlatSet, EmplacePosition) {
+TEST(FlatTree, EmplacePosition) {
   {
-    EmplaceableSet cont;
+    EmplaceableTree cont;
 
-    EmplaceableSet::iterator result = cont.emplace_hint(cont.cend());
+    EmplaceableTree::iterator result = cont.emplace_hint(cont.cend());
     EXPECT_EQ(cont.begin(), result);
     EXPECT_EQ(1U, cont.size());
     EXPECT_EQ(Emplaceable(), *cont.begin());
@@ -675,9 +666,9 @@ TEST(FlatSet, EmplacePosition) {
     EXPECT_EQ(Emplaceable(2, 3.5), *result);
   }
   {
-    IntSet cont;
+    IntTree cont;
 
-    IntSet::iterator result = cont.emplace_hint(cont.cend(), 2);
+    IntTree::iterator result = cont.emplace_hint(cont.cend(), 2);
     EXPECT_EQ(cont.begin(), result);
     EXPECT_EQ(1U, cont.size());
     EXPECT_EQ(2, *result);
@@ -689,10 +680,10 @@ TEST(FlatSet, EmplacePosition) {
 
 // iterator erase(const_iterator position_hint)
 
-TEST(FlatSet, ErasePosition) {
-  IntSet cont{1, 2, 3, 4, 5, 6, 7, 8};
+TEST(FlatTree, ErasePosition) {
+  IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
 
-  IntSet::iterator it = cont.erase(std::next(cont.cbegin(), 3));
+  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));
 
@@ -727,10 +718,10 @@ TEST(FlatSet, ErasePosition) {
 
 // iterator erase(const_iterator first, const_iterator last)
 
-TEST(FlatSet, EraseRange) {
-  IntSet cont{1, 2, 3, 4, 5, 6, 7, 8};
+TEST(FlatTree, EraseRange) {
+  IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
 
-  IntSet::iterator it =
+  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));
@@ -754,8 +745,8 @@ TEST(FlatSet, EraseRange) {
 
 // size_type erase(const key_type& key)
 
-TEST(FlatSet, EraseKey) {
-  IntSet cont{1, 2, 3, 4, 5, 6, 7, 8};
+TEST(FlatTree, EraseKey) {
+  IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
 
   EXPECT_EQ(0U, cont.erase(9));
   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8));
@@ -790,8 +781,8 @@ TEST(FlatSet, EraseKey) {
 
 // key_compare key_comp() const
 
-TEST(FlatSet, KeyComp) {
-  ReversedSet cont{1, 2, 3, 4, 5};
+TEST(FlatTree, KeyComp) {
+  ReversedTree cont{1, 2, 3, 4, 5};
 
   EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp()));
   int new_elements[] = {6, 7, 8, 9, 10};
@@ -802,8 +793,8 @@ TEST(FlatSet, KeyComp) {
 
 // value_compare value_comp() const
 
-TEST(FlatSet, ValueComp) {
-  ReversedSet cont{1, 2, 3, 4, 5};
+TEST(FlatTree, ValueComp) {
+  ReversedTree cont{1, 2, 3, 4, 5};
 
   EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp()));
   int new_elements[] = {6, 7, 8, 9, 10};
@@ -817,22 +808,9 @@ TEST(FlatSet, ValueComp) {
 
 // size_type count(const key_type& key) const
 
-TEST(FlatSet, Count) {
-  {
-    const IntSet cont{5, 6, 7, 8, 9, 10, 11, 12};
-
-    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));
-  }
+TEST(FlatTree, Count) {
   {
-    const SetWithLess cont{5, 6, 7, 8, 9, 10, 11, 12};
+    const IntTree cont{5, 6, 7, 8, 9, 10, 11, 12};
 
     EXPECT_EQ(1U, cont.count(5));
     EXPECT_EQ(1U, cont.count(6));
@@ -849,9 +827,9 @@ TEST(FlatSet, Count) {
 // iterator find(const key_type& key)
 // const_iterator find(const key_type& key) const
 
-TEST(FlatSet, Find) {
+TEST(FlatTree, Find) {
   {
-    IntSet cont{5, 6, 7, 8, 9, 10, 11, 12};
+    IntTree cont{5, 6, 7, 8, 9, 10, 11, 12};
 
     EXPECT_EQ(cont.begin(), cont.find(5));
     EXPECT_EQ(std::next(cont.begin()), cont.find(6));
@@ -864,20 +842,7 @@ TEST(FlatSet, Find) {
     EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
   }
   {
-    const IntSet cont{5, 6, 7, 8, 9, 10, 11, 12};
-
-    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));
-  }
-  {
-    SetWithLess cont{5, 6, 7, 8, 9, 10, 11, 12};
+    const IntTree cont{5, 6, 7, 8, 9, 10, 11, 12};
 
     EXPECT_EQ(cont.begin(), cont.find(5));
     EXPECT_EQ(std::next(cont.begin()), cont.find(6));
@@ -894,66 +859,11 @@ TEST(FlatSet, Find) {
 // pair<iterator, iterator> equal_range(const key_type& key)
 // pair<const_iterator, const_iterator> equal_range(const key_type& key) const
 
-TEST(FlatSet, EqualRange) {
+TEST(FlatTree, EqualRange) {
   {
-    IntSet cont{5, 7, 9, 11, 13, 15, 17, 19};
+    IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
 
-    std::pair<IntSet::iterator, IntSet::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);
-    EXPECT_EQ(std::next(cont.begin(), 3), result.second);
-    result = cont.equal_range(11);
-    EXPECT_EQ(std::next(cont.begin(), 3), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 4), result.second);
-    result = cont.equal_range(13);
-    EXPECT_EQ(std::next(cont.begin(), 4), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 5), result.second);
-    result = cont.equal_range(15);
-    EXPECT_EQ(std::next(cont.begin(), 5), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 6), result.second);
-    result = cont.equal_range(17);
-    EXPECT_EQ(std::next(cont.begin(), 6), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 7), result.second);
-    result = cont.equal_range(19);
-    EXPECT_EQ(std::next(cont.begin(), 7), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 8), result.second);
-    result = cont.equal_range(4);
-    EXPECT_EQ(std::next(cont.begin(), 0), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 0), result.second);
-    result = cont.equal_range(6);
-    EXPECT_EQ(std::next(cont.begin(), 1), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 1), result.second);
-    result = cont.equal_range(8);
-    EXPECT_EQ(std::next(cont.begin(), 2), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 2), result.second);
-    result = cont.equal_range(10);
-    EXPECT_EQ(std::next(cont.begin(), 3), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 3), result.second);
-    result = cont.equal_range(12);
-    EXPECT_EQ(std::next(cont.begin(), 4), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 4), result.second);
-    result = cont.equal_range(14);
-    EXPECT_EQ(std::next(cont.begin(), 5), result.first);
-    EXPECT_EQ(std::next(cont.begin(), 5), result.second);
-    result = cont.equal_range(16);
-    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 IntSet cont{5, 7, 9, 11, 13, 15, 17, 19};
-
-    std::pair<IntSet::const_iterator, IntSet::const_iterator> result =
+    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);
@@ -1007,9 +917,9 @@ TEST(FlatSet, EqualRange) {
     EXPECT_EQ(std::next(cont.begin(), 8), result.second);
   }
   {
-    SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19};
+    const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
 
-    std::pair<SetWithLess::iterator, SetWithLess::iterator> result =
+    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);
@@ -1067,30 +977,9 @@ TEST(FlatSet, EqualRange) {
 //       iterator lower_bound(const key_type& key);
 // const_iterator lower_bound(const key_type& key) const;
 
-TEST(FlatSet, LowerBound) {
-  {
-    IntSet cont{5, 7, 9, 11, 13, 15, 17, 19};
-
-    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));
-  }
+TEST(FlatTree, LowerBound) {
   {
-    const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19};
+    IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
 
     EXPECT_EQ(cont.begin(), cont.lower_bound(5));
     EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
@@ -1111,7 +1000,7 @@ TEST(FlatSet, LowerBound) {
     EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
   }
   {
-    SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19};
+    const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
 
     EXPECT_EQ(cont.begin(), cont.lower_bound(5));
     EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
@@ -1136,9 +1025,9 @@ TEST(FlatSet, LowerBound) {
 // iterator upper_bound(const key_type& key)
 // const_iterator upper_bound(const key_type& key) const
 
-TEST(FlatSet, UpperBound) {
+TEST(FlatTree, UpperBound) {
   {
-    IntSet cont{5, 7, 9, 11, 13, 15, 17, 19};
+    IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
 
     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
@@ -1159,28 +1048,7 @@ TEST(FlatSet, UpperBound) {
     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
   }
   {
-    const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19};
-
-    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));
-  }
-  {
-    SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19};
+    const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
 
     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
@@ -1205,12 +1073,12 @@ TEST(FlatSet, UpperBound) {
 // ----------------------------------------------------------------------------
 // General operations.
 
-// void swap(flat_set& other)
-// void swap(flat_set& lhs, flat_set& rhs)
+// void swap(flat_tree& other)
+// void swap(flat_tree& lhs, flat_tree& rhs)
 
-TEST(FlatSetOurs, Swap) {
-  IntSet x{1, 2, 3};
-  IntSet y{4};
+TEST(FlatTreeOurs, Swap) {
+  IntTree x{1, 2, 3};
+  IntTree y{4};
   swap(x, y);
   EXPECT_THAT(x, ElementsAre(4));
   EXPECT_THAT(y, ElementsAre(1, 2, 3));
@@ -1220,18 +1088,18 @@ TEST(FlatSetOurs, Swap) {
   EXPECT_THAT(y, ElementsAre(4));
 }
 
-// bool operator==(const flat_set& lhs, const flat_set& rhs)
-// bool operator!=(const flat_set& lhs, const flat_set& rhs)
-// bool operator<(const flat_set& lhs, const flat_set& rhs)
-// bool operator>(const flat_set& lhs, const flat_set& rhs)
-// bool operator<=(const flat_set& lhs, const flat_set& rhs)
-// bool operator>=(const flat_set& lhs, const flat_set& 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)
+// bool operator>=(const flat_tree& lhs, const flat_tree& rhs)
 
-TEST(FlatSet, Comparison) {
+TEST(FlatTree, Comparison) {
   // Provided comparator does not participate in comparison.
-  ReversedSet biggest{3};
-  ReversedSet smallest{1};
-  ReversedSet middle{1, 2};
+  ReversedTree biggest{3};
+  ReversedTree smallest{1};
+  ReversedTree middle{1, 2};
 
   EXPECT_EQ(biggest, biggest);
   EXPECT_NE(biggest, smallest);
@@ -1242,3 +1110,6 @@ TEST(FlatSet, Comparison) {
   EXPECT_GE(biggest, middle);
   EXPECT_GE(biggest, biggest);
 }
+
+}  // namespace internal
+}  // namespace base