Add range insertion for base::flat_tree

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 13 matching lines @@
 // * 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.
-// * No tests for range insertion. Flat sets currently do not support this
-//   functionality.
 
 #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 base {
@@ skipping 685 matching lines @@
   EXPECT_EQ(std::prev(cont.end()), result);
   EXPECT_EQ(3U, cont.size());
   EXPECT_EQ(3, result->data());
 
   result = cont.insert(cont.cend(), MoveOnlyInt(3));
   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; }
+  };
+
+  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));
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1)));
+  }
+
+  {
+    IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs));
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1)));
+  }
+
+  {
+    IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}, {7, 2}, {6, 2},
+                           {8, 2}, {5, 2}, {5, 3}, {6, 3}, {7, 3}, {8, 3}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs));
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1), IntPair(5, 2), IntPair(6, 2),
+                                  IntPair(7, 2), IntPair(8, 2)));
+  }

[dyaroshev, 2017/05/09 09:32:46]

An empty range check is important.

Maybe we want to generate some inputs and check against those? Doesn't seem that
hard.

[jdoerrie, 2017/05/09 17:03:30]

Done.

+}
+
 // template <class... Args>
 // pair<iterator, bool> emplace(Args&&... args)
 
 TEST(FlatTree, Emplace) {
   {
     EmplaceableTree cont;
 
     std::pair<EmplaceableTree::iterator, bool> result = cont.emplace();
     EXPECT_TRUE(result.second);
     EXPECT_EQ(cont.begin(), result.first);
@@ skipping 625 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