Improving flat containers interface.

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
 //
 // Not ported tests:
 // * No tests with PrivateConstructor and std::less<> changed to std::less<T>
 //   These tests have to do with C++14 std::less<>
 //   http://en.cppreference.com/w/cpp/utility/functional/less_void
 //   and add support for templated versions of lookup functions.
-//   Current implementation of flat containers doesn't support it.
+//   Because we use same implementation, we figured that it's OK just to check
+//   compilation and this is what we do in flat_set_unittest/flat_map_unittest.
 // * No tests with TemplateConstructor.
 //   Library working group issue: LWG #2059
 //   http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2059
 //   There is an ambiguity between erase with an iterator and erase with a key,
 //   if key has a templated constructor. We have to fix this.
 // * No tests for max_size()
 //   Has to do with allocator support.
 // * No tests with DefaultOnly.
 //   Standard containers allocate each element in the separate node on the heap
 //   and then manipulate these nodes. Flat containers store their elements in
@@ skipping 105 matching lines @@
 };
 
 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>,
@@ skipping 594 matching lines @@
   EXPECT_EQ(std::prev(cont.end()), result);
   EXPECT_EQ(3U, cont.size());
   EXPECT_EQ(3, result->data());
 }
 
 // template <class InputIterator>
 //   void insert(InputIterator first, InputIterator last);
 
 TEST(FlatTree, InsertIterIter) {
   struct GetKeyFromIntIntPair {
-    int operator()(const std::pair<int, int>& p) const { return p.first; }
+    const int& operator()(const std::pair<int, int>& p) const {
+      return p.first;
+    }
   };
 
   using IntIntMap =
       flat_tree<int, IntPair, GetKeyFromIntIntPair, std::less<int>>;
 
   {
     IntIntMap cont;
     IntPair int_pairs[] = {{3, 1}, {1, 1}, {4, 1}, {2, 1}};
     cont.insert(std::begin(int_pairs), std::end(int_pairs),
                 KEEP_FIRST_OF_DUPES);
@@ skipping 278 matching lines @@
             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}, 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},
-                               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}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(cont.begin(), cont.find(5));
@@ skipping 12 matching lines @@
     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}, 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}, KEEP_FIRST_OF_DUPES);
 
     std::pair<IntTree::iterator, IntTree::iterator> result =
@@ skipping 98 matching lines @@
     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);
   }
-  {
-    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);
-    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);
-  }
 }
 
 //       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}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(cont.begin(), cont.lower_bound(5));
@@ skipping 28 matching lines @@
     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}, 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}, KEEP_FIRST_OF_DUPES);
 
     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
@@ skipping 28 matching lines @@
     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}, 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}, KEEP_FIRST_OF_DUPES);
@@ skipping 39 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