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.
-// * 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.
+//   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 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
 //   contiguous memory and move them around, type is required to be movable.
 // * No tests for N3644.
 //   This proposal suggests that all default constructed iterators compare
 //   equal. Currently we use std::vector iterators and they don't implement
 //   this.
 // * No tests with min_allocator and no tests counting allocations.
 //   Flat sets currently don't support allocators.
 
 #include <forward_list>
 #include <iterator>
 #include <list>
 #include <string>
 #include <vector>
 
 #include "base/containers/container_test_utils.h"
+#include "base/functional.h"
 #include "base/macros.h"
 #include "testing/gmock/include/gmock/gmock.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace base {
 namespace internal {
 
 namespace {
 
 template <class It>
@@ skipping 62 matching lines @@
     return std::tie(lhs.int_, lhs.double_) < std::tie(rhs.int_, rhs.double_);
   }
 
  private:
   int int_;
   double double_;
 
   DISALLOW_COPY_AND_ASSIGN(Emplaceable);
 };
 
+struct TemplateConstructor {
+  template <typename T>
+  TemplateConstructor(const T&) {}
+
+  friend bool operator<(const TemplateConstructor&,
+                        const TemplateConstructor&) {
+    return false;
+  }
+};
+
 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>,
@@ 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 150 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}, KEEP_FIRST_OF_DUPES);
+  {
+    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));
+    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(), 0));
+    EXPECT_EQ(cont.begin(), it);
+    EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
 
-  it = cont.erase(std::next(cont.cbegin(), 5));
-  EXPECT_EQ(cont.end(), it);
-  EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7));
+    it = cont.erase(std::next(cont.cbegin(), 5));
+    EXPECT_EQ(cont.end(), it);
+    EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7));
 
-  it = cont.erase(std::next(cont.cbegin(), 1));
-  EXPECT_EQ(std::next(cont.begin()), it);
-  EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7));
+    it = cont.erase(std::next(cont.cbegin(), 1));
+    EXPECT_EQ(std::next(cont.begin()), it);
+    EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7));
 
-  it = cont.erase(std::next(cont.cbegin(), 2));
-  EXPECT_EQ(std::next(cont.begin(), 2), it);
-  EXPECT_THAT(cont, ElementsAre(2, 5, 7));
+    it = cont.erase(std::next(cont.cbegin(), 2));
+    EXPECT_EQ(std::next(cont.begin(), 2), it);
+    EXPECT_THAT(cont, ElementsAre(2, 5, 7));
 
-  it = cont.erase(std::next(cont.cbegin(), 2));
-  EXPECT_EQ(std::next(cont.begin(), 2), it);
-  EXPECT_THAT(cont, ElementsAre(2, 5));
+    it = cont.erase(std::next(cont.cbegin(), 2));
+    EXPECT_EQ(std::next(cont.begin(), 2), it);
+    EXPECT_THAT(cont, ElementsAre(2, 5));
 
-  it = cont.erase(std::next(cont.cbegin(), 0));
-  EXPECT_EQ(std::next(cont.begin(), 0), it);
-  EXPECT_THAT(cont, ElementsAre(5));
+    it = cont.erase(std::next(cont.cbegin(), 0));
+    EXPECT_EQ(std::next(cont.begin(), 0), it);
+    EXPECT_THAT(cont, ElementsAre(5));
 
-  it = cont.erase(cont.cbegin());
-  EXPECT_EQ(cont.begin(), it);
-  EXPECT_EQ(cont.end(), it);
+    it = cont.erase(cont.cbegin());
+    EXPECT_EQ(cont.begin(), it);
+    EXPECT_EQ(cont.end(), it);
+  }
+  //  This is LWG #2059.
+  //  There is a potential ambiguity between erase with an iterator and erase
+  //  with a key, if key has a templated constructor.
+  {
+    using T = TemplateConstructor;
+
+    flat_tree<T, T, GetKeyFromValueIdentity<T>, base::less> cont;
+    T v(0);
+
+    auto it = cont.find(v);
+    if (it != cont.end())
+      cont.erase(it);
+  }
 }
 
 // iterator erase(const_iterator first, const_iterator last)
 
 TEST(FlatTree, EraseRange) {
   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);
@@ skipping 75 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