Add a flat_map container

base/containers/flat_map_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_map.h"
+
+#include <string>
+#include <vector>
+
+#include "base/macros.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+// A flat_map is basically a interface to flat_tree. So several basic
+// operations are tested to make sure things are set up properly, but the bulk
+// of the tests are in flat_tree_unittests.cc.
+
+using ::testing::ElementsAre;
+
+namespace base {
+
+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;
+  }
+
+  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
+
+TEST(FlatMap, IncompleteType) {
+  struct A {
+    using Map = flat_map<A, A>;
+    int data;
+    Map set_with_incomplete_type;
+    Map::iterator it;
+    Map::const_iterator cit;
+
+    // We do not declare operator< because clang complains that it's unused.
+  };
+
+  A a;
+}
+
+TEST(FlatMap, RangeConstructor) {
+  flat_map<int, int>::value_type input_vals[] = {
+      {1, 1}, {1, 1}, {1, 1}, {2, 2}, {2, 2}, {2, 2}, {3, 3}, {3, 3}, {3, 3}};
+
+  flat_map<int, int> cont(std::begin(input_vals), std::end(input_vals));
+  EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2),
+                                std::make_pair(3, 3)));
+}
+
+TEST(FlatMap, MoveConstructor) {
+  std::pair<int, int> input_range[] = {{1, 1}, {2, 2}, {3, 3}, {4, 4}};
+
+  flat_map<MoveOnly, MoveOnly> original(std::begin(input_range),
+                                        std::end(input_range));
+  flat_map<MoveOnly, MoveOnly> 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)));
+}
+
+TEST(FlatMap, InitializerListConstructor) {
+  flat_map<int, int> cont{{1, 1}, {2, 2}, {3, 3},   {4, 4},
+                          {5, 5}, {6, 6}, {10, 10}, {8, 8}};
+  EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2),
+                                std::make_pair(3, 3), std::make_pair(4, 4),
+                                std::make_pair(5, 5), std::make_pair(6, 6),
+                                std::make_pair(8, 8), std::make_pair(10, 10)));
+}
+
+TEST(FlatMap, InsertFindSize) {
+  base::flat_map<int, int> s;
+  s.insert(std::make_pair(1, 1));
+  s.insert(std::make_pair(1, 1));
+  s.insert(std::make_pair(2, 2));
+
+  EXPECT_EQ(2u, s.size());
+  EXPECT_EQ(std::make_pair(1, 1), *s.find(1));
+  EXPECT_EQ(std::make_pair(2, 2), *s.find(2));
+  EXPECT_EQ(s.end(), s.find(7));
+}
+
+TEST(FlatMap, CopySwap) {
+  base::flat_map<int, int> original;
+  original.insert({1, 1});
+  original.insert({2, 2});
+  EXPECT_THAT(original,
+              ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
+
+  base::flat_map<int, int> copy(original);
+  EXPECT_THAT(copy, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
+
+  copy.erase(copy.begin());
+  copy.insert({10, 10});
+  EXPECT_THAT(copy, ElementsAre(std::make_pair(2, 2), std::make_pair(10, 10)));
+
+  original.swap(copy);
+  EXPECT_THAT(original,
+              ElementsAre(std::make_pair(2, 2), std::make_pair(10, 10)));
+  EXPECT_THAT(copy, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
+}
+
+// operator[](const Key&)
+TEST(FlatMap, SubscriptConstKey) {
+  base::flat_map<std::string, int> m;
+
+  // Default construct elements that don't exist yet.
+  int& s = m["a"];
+  EXPECT_EQ(0, s);
+  EXPECT_EQ(1u, m.size());
+
+  // The returned mapped reference should refer into the map.
+  s = 22;
+  EXPECT_EQ(22, m["a"]);
+
+  // Overwrite existing elements.
+  m["a"] = 44;
+  EXPECT_EQ(44, m["a"]);
+}
+
+// operator[](Key&&)
+TEST(FlatMap, SubscriptMoveOnlyKey) {
+  base::flat_map<MoveOnly, int> m;
+
+  // Default construct elements that don't exist yet.
+  int& s = m[MoveOnly(1)];
+  EXPECT_EQ(0, s);
+  EXPECT_EQ(1u, m.size());
+
+  // The returned mapped reference should refer into the map.
+  s = 22;
+  EXPECT_EQ(22, m[MoveOnly(1)]);
+
+  // Overwrite existing elements.
+  m[MoveOnly(1)] = 44;
+  EXPECT_EQ(44, m[MoveOnly(1)]);
+}
+
+}  // namespace base