rtc_base/containers/flat_map_unittest.cc - src - Git at Google

 /*
  *  Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */

 // This implementation is borrowed from Chromium.

 #include "rtc_base/containers/flat_map.h"

 #include <algorithm>
 #include <string>
 #include <vector>

 #include "rtc_base/containers/move_only_int.h"
 #include "test/gmock.h"
 #include "test/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 webrtc {

 namespace {

 struct Unsortable {
   int value;
 };

 bool operator==(const Unsortable& lhs, const Unsortable& rhs) {
   return lhs.value == rhs.value;
 }

 bool operator<(const Unsortable& lhs, const Unsortable& rhs) = delete;
 bool operator<=(const Unsortable& lhs, const Unsortable& rhs) = delete;
 bool operator>(const Unsortable& lhs, const Unsortable& rhs) = delete;
 bool operator>=(const Unsortable& lhs, const Unsortable& rhs) = delete;

 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, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}};

   flat_map<int, int> first(std::begin(input_vals), std::end(input_vals));
   EXPECT_THAT(first, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 1),
                                  std::make_pair(3, 1)));
 }

 TEST(FlatMap, MoveConstructor) {
   using pair = std::pair<MoveOnlyInt, MoveOnlyInt>;

   flat_map<MoveOnlyInt, MoveOnlyInt> original;
   original.insert(pair(MoveOnlyInt(1), MoveOnlyInt(1)));
   original.insert(pair(MoveOnlyInt(2), MoveOnlyInt(2)));
   original.insert(pair(MoveOnlyInt(3), MoveOnlyInt(3)));
   original.insert(pair(MoveOnlyInt(4), MoveOnlyInt(4)));

   flat_map<MoveOnlyInt, MoveOnlyInt> moved(std::move(original));

   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)));
 }

 TEST(FlatMap, VectorConstructor) {
   using IntPair = std::pair<int, int>;
   using IntMap = flat_map<int, int>;
   std::vector<IntPair> vect{{1, 1}, {1, 2}, {2, 1}};
   IntMap map(std::move(vect));
   EXPECT_THAT(map, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
 }

 TEST(FlatMap, InitializerListConstructor) {
   flat_map<int, int> cont(
       {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {1, 2}, {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(8, 8),
                                 std::make_pair(10, 10)));
 }

 TEST(FlatMap, SortedRangeConstructor) {
   using PairType = std::pair<int, Unsortable>;
   using MapType = flat_map<int, Unsortable>;
   MapType::value_type input_vals[] = {{1, {1}}, {2, {1}}, {3, {1}}};
   MapType map(sorted_unique, std::begin(input_vals), std::end(input_vals));
   EXPECT_THAT(
       map, ElementsAre(PairType(1, {1}), PairType(2, {1}), PairType(3, {1})));
 }

 TEST(FlatMap, SortedCopyFromVectorConstructor) {
   using PairType = std::pair<int, Unsortable>;
   using MapType = flat_map<int, Unsortable>;
   std::vector<PairType> vect{{1, {1}}, {2, {1}}};
   MapType map(sorted_unique, vect);
   EXPECT_THAT(map, ElementsAre(PairType(1, {1}), PairType(2, {1})));
 }

 TEST(FlatMap, SortedMoveFromVectorConstructor) {
   using PairType = std::pair<int, Unsortable>;
   using MapType = flat_map<int, Unsortable>;
   std::vector<PairType> vect{{1, {1}}, {2, {1}}};
   MapType map(sorted_unique, std::move(vect));
   EXPECT_THAT(map, ElementsAre(PairType(1, {1}), PairType(2, {1})));
 }

 TEST(FlatMap, SortedInitializerListConstructor) {
   using PairType = std::pair<int, Unsortable>;
   flat_map<int, Unsortable> map(
       sorted_unique,
       {{1, {1}}, {2, {2}}, {3, {3}}, {4, {4}}, {5, {5}}, {8, {8}}, {10, {10}}});
   EXPECT_THAT(map,
               ElementsAre(PairType(1, {1}), PairType(2, {2}), PairType(3, {3}),
                           PairType(4, {4}), PairType(5, {5}), PairType(8, {8}),
                           PairType(10, {10})));
 }

 TEST(FlatMap, InitializerListAssignment) {
   flat_map<int, int> cont;
   cont = {{1, 1}, {2, 2}};
   EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
 }

 TEST(FlatMap, InsertFindSize) {
   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) {
   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)));

   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) {
   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) {
   flat_map<MoveOnlyInt, int> m;

   // Default construct elements that don't exist yet.
   int& s = m[MoveOnlyInt(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[MoveOnlyInt(1)]);

   // Overwrite existing elements.
   m[MoveOnlyInt(1)] = 44;
   EXPECT_EQ(44, m[MoveOnlyInt(1)]);
 }

 // Mapped& at(const Key&)
 // const Mapped& at(const Key&) const
 TEST(FlatMap, AtFunction) {
   flat_map<int, std::string> m = {{1, "a"}, {2, "b"}};

   // Basic Usage.
   EXPECT_EQ("a", m.at(1));
   EXPECT_EQ("b", m.at(2));

   // Const reference works.
   const std::string& const_ref = webrtc::as_const(m).at(1);
   EXPECT_EQ("a", const_ref);

   // Reference works, can operate on the string.
   m.at(1)[0] = 'x';
   EXPECT_EQ("x", m.at(1));

   // Out-of-bounds will CHECK.
   EXPECT_DEATH_IF_SUPPORTED(m.at(-1), "");
   EXPECT_DEATH_IF_SUPPORTED({ m.at(-1)[0] = 'z'; }, "");

   // Heterogeneous look-up works.
   flat_map<std::string, int> m2 = {{"a", 1}, {"b", 2}};
   EXPECT_EQ(1, m2.at(absl::string_view("a")));
   EXPECT_EQ(2, webrtc::as_const(m2).at(absl::string_view("b")));
 }

 // insert_or_assign(K&&, M&&)
 TEST(FlatMap, InsertOrAssignMoveOnlyKey) {
   flat_map<MoveOnlyInt, MoveOnlyInt> m;

   // Initial insertion should return an iterator to the element and set the
   // second pair member to |true|. The inserted key and value should be moved
   // from.
   MoveOnlyInt key(1);
   MoveOnlyInt val(22);
   auto result = m.insert_or_assign(std::move(key), std::move(val));
   EXPECT_EQ(1, result.first->first.data());
   EXPECT_EQ(22, result.first->second.data());
   EXPECT_TRUE(result.second);
   EXPECT_EQ(1u, m.size());
   EXPECT_EQ(0, key.data());  // moved from
   EXPECT_EQ(0, val.data());  // moved from

   // Second call with same key should result in an assignment, overwriting the
   // old value. Assignment should be indicated by setting the second pair member
   // to |false|. Only the inserted value should be moved from, the key should be
   // left intact.
   key = MoveOnlyInt(1);
   val = MoveOnlyInt(44);
   result = m.insert_or_assign(std::move(key), std::move(val));
   EXPECT_EQ(1, result.first->first.data());
   EXPECT_EQ(44, result.first->second.data());
   EXPECT_FALSE(result.second);
   EXPECT_EQ(1u, m.size());
   EXPECT_EQ(1, key.data());  // not moved from
   EXPECT_EQ(0, val.data());  // moved from

   // Check that random insertion results in sorted range.
   flat_map<MoveOnlyInt, int> map;
   for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
     map.insert_or_assign(MoveOnlyInt(i), i);
     EXPECT_TRUE(absl::c_is_sorted(map));
   }
 }

 // insert_or_assign(const_iterator hint, K&&, M&&)
 TEST(FlatMap, InsertOrAssignMoveOnlyKeyWithHint) {
   flat_map<MoveOnlyInt, MoveOnlyInt> m;

   // Initial insertion should return an iterator to the element. The inserted
   // key and value should be moved from.
   MoveOnlyInt key(1);
   MoveOnlyInt val(22);
   auto result = m.insert_or_assign(m.end(), std::move(key), std::move(val));
   EXPECT_EQ(1, result->first.data());
   EXPECT_EQ(22, result->second.data());
   EXPECT_EQ(1u, m.size());
   EXPECT_EQ(0, key.data());  // moved from
   EXPECT_EQ(0, val.data());  // moved from

   // Second call with same key should result in an assignment, overwriting the
   // old value. Only the inserted value should be moved from, the key should be
   // left intact.
   key = MoveOnlyInt(1);
   val = MoveOnlyInt(44);
   result = m.insert_or_assign(m.end(), std::move(key), std::move(val));
   EXPECT_EQ(1, result->first.data());
   EXPECT_EQ(44, result->second.data());
   EXPECT_EQ(1u, m.size());
   EXPECT_EQ(1, key.data());  // not moved from
   EXPECT_EQ(0, val.data());  // moved from

   // Check that random insertion results in sorted range.
   flat_map<MoveOnlyInt, int> map;
   for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
     map.insert_or_assign(map.end(), MoveOnlyInt(i), i);
     EXPECT_TRUE(absl::c_is_sorted(map));
   }
 }

 // try_emplace(K&&, Args&&...)
 TEST(FlatMap, TryEmplaceMoveOnlyKey) {
   flat_map<MoveOnlyInt, std::pair<MoveOnlyInt, MoveOnlyInt>> m;

   // Trying to emplace into an empty map should succeed. Insertion should return
   // an iterator to the element and set the second pair member to |true|. The
   // inserted key and value should be moved from.
   MoveOnlyInt key(1);
   MoveOnlyInt val1(22);
   MoveOnlyInt val2(44);
   // Test piecewise construction of mapped_type.
   auto result = m.try_emplace(std::move(key), std::move(val1), std::move(val2));
   EXPECT_EQ(1, result.first->first.data());
   EXPECT_EQ(22, result.first->second.first.data());
   EXPECT_EQ(44, result.first->second.second.data());
   EXPECT_TRUE(result.second);
   EXPECT_EQ(1u, m.size());
   EXPECT_EQ(0, key.data());   // moved from
   EXPECT_EQ(0, val1.data());  // moved from
   EXPECT_EQ(0, val2.data());  // moved from

   // Second call with same key should result in a no-op, returning an iterator
   // to the existing element and returning false as the second pair member.
   // Key and values that were attempted to be inserted should be left intact.
   key = MoveOnlyInt(1);
   auto paired_val = std::make_pair(MoveOnlyInt(33), MoveOnlyInt(55));
   // Test construction of mapped_type from pair.
   result = m.try_emplace(std::move(key), std::move(paired_val));
   EXPECT_EQ(1, result.first->first.data());
   EXPECT_EQ(22, result.first->second.first.data());
   EXPECT_EQ(44, result.first->second.second.data());
   EXPECT_FALSE(result.second);
   EXPECT_EQ(1u, m.size());
   EXPECT_EQ(1, key.data());                 // not moved from
   EXPECT_EQ(33, paired_val.first.data());   // not moved from
   EXPECT_EQ(55, paired_val.second.data());  // not moved from

   // Check that random insertion results in sorted range.
   flat_map<MoveOnlyInt, int> map;
   for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
     map.try_emplace(MoveOnlyInt(i), i);
     EXPECT_TRUE(absl::c_is_sorted(map));
   }
 }

 // try_emplace(const_iterator hint, K&&, Args&&...)
 TEST(FlatMap, TryEmplaceMoveOnlyKeyWithHint) {
   flat_map<MoveOnlyInt, std::pair<MoveOnlyInt, MoveOnlyInt>> m;

   // Trying to emplace into an empty map should succeed. Insertion should return
   // an iterator to the element. The inserted key and value should be moved
   // from.
   MoveOnlyInt key(1);
   MoveOnlyInt val1(22);
   MoveOnlyInt val2(44);
   // Test piecewise construction of mapped_type.
   auto result =
       m.try_emplace(m.end(), std::move(key), std::move(val1), std::move(val2));
   EXPECT_EQ(1, result->first.data());
   EXPECT_EQ(22, result->second.first.data());
   EXPECT_EQ(44, result->second.second.data());
   EXPECT_EQ(1u, m.size());
   EXPECT_EQ(0, key.data());   // moved from
   EXPECT_EQ(0, val1.data());  // moved from
   EXPECT_EQ(0, val2.data());  // moved from

   // Second call with same key should result in a no-op, returning an iterator
   // to the existing element. Key and values that were attempted to be inserted
   // should be left intact.
   key = MoveOnlyInt(1);
   val1 = MoveOnlyInt(33);
   val2 = MoveOnlyInt(55);
   auto paired_val = std::make_pair(MoveOnlyInt(33), MoveOnlyInt(55));
   // Test construction of mapped_type from pair.
   result = m.try_emplace(m.end(), std::move(key), std::move(paired_val));
   EXPECT_EQ(1, result->first.data());
   EXPECT_EQ(22, result->second.first.data());
   EXPECT_EQ(44, result->second.second.data());
   EXPECT_EQ(1u, m.size());
   EXPECT_EQ(1, key.data());                 // not moved from
   EXPECT_EQ(33, paired_val.first.data());   // not moved from
   EXPECT_EQ(55, paired_val.second.data());  // not moved from

   // Check that random insertion results in sorted range.
   flat_map<MoveOnlyInt, int> map;
   for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
     map.try_emplace(map.end(), MoveOnlyInt(i), i);
     EXPECT_TRUE(absl::c_is_sorted(map));
   }
 }

 TEST(FlatMap, UsingTransparentCompare) {
   using ExplicitInt = MoveOnlyInt;
   flat_map<ExplicitInt, int> m;
   const auto& m1 = m;
   int x = 0;

   // Check if we can use lookup functions without converting to key_type.
   // Correctness is checked in flat_tree tests.
   m.count(x);
   m1.count(x);
   m.find(x);
   m1.find(x);
   m.equal_range(x);
   m1.equal_range(x);
   m.lower_bound(x);
   m1.lower_bound(x);
   m.upper_bound(x);
   m1.upper_bound(x);
   m.erase(x);

   // Check if we broke overload resolution.
   m.emplace(ExplicitInt(0), 0);
   m.emplace(ExplicitInt(1), 0);
   m.erase(m.begin());
   m.erase(m.cbegin());
 }

 TEST(FlatMap, SupportsEraseIf) {
   flat_map<MoveOnlyInt, MoveOnlyInt> m;
   m.insert(std::make_pair(MoveOnlyInt(1), MoveOnlyInt(1)));
   m.insert(std::make_pair(MoveOnlyInt(2), MoveOnlyInt(2)));
   m.insert(std::make_pair(MoveOnlyInt(3), MoveOnlyInt(3)));
   m.insert(std::make_pair(MoveOnlyInt(4), MoveOnlyInt(4)));
   m.insert(std::make_pair(MoveOnlyInt(5), MoveOnlyInt(5)));

   EraseIf(m, [to_be_removed = MoveOnlyInt(2)](
                  const std::pair<MoveOnlyInt, MoveOnlyInt>& e) {
     return e.first == to_be_removed;
   });

   EXPECT_EQ(m.size(), 4u);
   ASSERT_TRUE(m.find(MoveOnlyInt(1)) != m.end());
   ASSERT_FALSE(m.find(MoveOnlyInt(2)) != m.end());
   ASSERT_TRUE(m.find(MoveOnlyInt(3)) != m.end());
   ASSERT_TRUE(m.find(MoveOnlyInt(4)) != m.end());
   ASSERT_TRUE(m.find(MoveOnlyInt(5)) != m.end());
 }

 }  // namespace
 }  // namespace webrtc
	/*
	* Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
	*
	* Use of this source code is governed by a BSD-style license
	* that can be found in the LICENSE file in the root of the source
	* tree. An additional intellectual property rights grant can be found
	* in the file PATENTS. All contributing project authors may
	* be found in the AUTHORS file in the root of the source tree.
	*/

	// This implementation is borrowed from Chromium.

	#include "rtc_base/containers/flat_map.h"

	#include <algorithm>
	#include <string>
	#include <vector>

	#include "rtc_base/containers/move_only_int.h"
	#include "test/gmock.h"
	#include "test/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 webrtc {

	namespace {

	struct Unsortable {
	int value;
	};

	bool operator==(const Unsortable& lhs, const Unsortable& rhs) {
	return lhs.value == rhs.value;
	}

	bool operator<(const Unsortable& lhs, const Unsortable& rhs) = delete;
	bool operator<=(const Unsortable& lhs, const Unsortable& rhs) = delete;
	bool operator>(const Unsortable& lhs, const Unsortable& rhs) = delete;
	bool operator>=(const Unsortable& lhs, const Unsortable& rhs) = delete;

	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, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}};

	flat_map<int, int> first(std::begin(input_vals), std::end(input_vals));
	EXPECT_THAT(first, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 1),
	std::make_pair(3, 1)));
	}

	TEST(FlatMap, MoveConstructor) {
	using pair = std::pair<MoveOnlyInt, MoveOnlyInt>;

	flat_map<MoveOnlyInt, MoveOnlyInt> original;
	original.insert(pair(MoveOnlyInt(1), MoveOnlyInt(1)));
	original.insert(pair(MoveOnlyInt(2), MoveOnlyInt(2)));
	original.insert(pair(MoveOnlyInt(3), MoveOnlyInt(3)));
	original.insert(pair(MoveOnlyInt(4), MoveOnlyInt(4)));

	flat_map<MoveOnlyInt, MoveOnlyInt> moved(std::move(original));

	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)));
	}

	TEST(FlatMap, VectorConstructor) {
	using IntPair = std::pair<int, int>;
	using IntMap = flat_map<int, int>;
	std::vector<IntPair> vect{{1, 1}, {1, 2}, {2, 1}};
	IntMap map(std::move(vect));
	EXPECT_THAT(map, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
	}

	TEST(FlatMap, InitializerListConstructor) {
	flat_map<int, int> cont(
	{{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {1, 2}, {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(8, 8),
	std::make_pair(10, 10)));
	}

	TEST(FlatMap, SortedRangeConstructor) {
	using PairType = std::pair<int, Unsortable>;
	using MapType = flat_map<int, Unsortable>;
	MapType::value_type input_vals[] = {{1, {1}}, {2, {1}}, {3, {1}}};
	MapType map(sorted_unique, std::begin(input_vals), std::end(input_vals));
	EXPECT_THAT(
	map, ElementsAre(PairType(1, {1}), PairType(2, {1}), PairType(3, {1})));
	}

	TEST(FlatMap, SortedCopyFromVectorConstructor) {
	using PairType = std::pair<int, Unsortable>;
	using MapType = flat_map<int, Unsortable>;
	std::vector<PairType> vect{{1, {1}}, {2, {1}}};
	MapType map(sorted_unique, vect);
	EXPECT_THAT(map, ElementsAre(PairType(1, {1}), PairType(2, {1})));
	}

	TEST(FlatMap, SortedMoveFromVectorConstructor) {
	using PairType = std::pair<int, Unsortable>;
	using MapType = flat_map<int, Unsortable>;
	std::vector<PairType> vect{{1, {1}}, {2, {1}}};
	MapType map(sorted_unique, std::move(vect));
	EXPECT_THAT(map, ElementsAre(PairType(1, {1}), PairType(2, {1})));
	}

	TEST(FlatMap, SortedInitializerListConstructor) {
	using PairType = std::pair<int, Unsortable>;
	flat_map<int, Unsortable> map(
	sorted_unique,
	{{1, {1}}, {2, {2}}, {3, {3}}, {4, {4}}, {5, {5}}, {8, {8}}, {10, {10}}});
	EXPECT_THAT(map,
	ElementsAre(PairType(1, {1}), PairType(2, {2}), PairType(3, {3}),
	PairType(4, {4}), PairType(5, {5}), PairType(8, {8}),
	PairType(10, {10})));
	}

	TEST(FlatMap, InitializerListAssignment) {
	flat_map<int, int> cont;
	cont = {{1, 1}, {2, 2}};
	EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
	}

	TEST(FlatMap, InsertFindSize) {
	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) {
	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)));

	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) {
	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) {
	flat_map<MoveOnlyInt, int> m;

	// Default construct elements that don't exist yet.
	int& s = m[MoveOnlyInt(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[MoveOnlyInt(1)]);

	// Overwrite existing elements.
	m[MoveOnlyInt(1)] = 44;
	EXPECT_EQ(44, m[MoveOnlyInt(1)]);
	}

	// Mapped& at(const Key&)
	// const Mapped& at(const Key&) const
	TEST(FlatMap, AtFunction) {
	flat_map<int, std::string> m = {{1, "a"}, {2, "b"}};

	// Basic Usage.
	EXPECT_EQ("a", m.at(1));
	EXPECT_EQ("b", m.at(2));

	// Const reference works.
	const std::string& const_ref = webrtc::as_const(m).at(1);
	EXPECT_EQ("a", const_ref);

	// Reference works, can operate on the string.
	m.at(1)[0] = 'x';
	EXPECT_EQ("x", m.at(1));

	// Out-of-bounds will CHECK.
	EXPECT_DEATH_IF_SUPPORTED(m.at(-1), "");
	EXPECT_DEATH_IF_SUPPORTED({ m.at(-1)[0] = 'z'; }, "");

	// Heterogeneous look-up works.
	flat_map<std::string, int> m2 = {{"a", 1}, {"b", 2}};
	EXPECT_EQ(1, m2.at(absl::string_view("a")));
	EXPECT_EQ(2, webrtc::as_const(m2).at(absl::string_view("b")));
	}

	// insert_or_assign(K&&, M&&)
	TEST(FlatMap, InsertOrAssignMoveOnlyKey) {
	flat_map<MoveOnlyInt, MoveOnlyInt> m;

	// Initial insertion should return an iterator to the element and set the
	// second pair member to \|true\|. The inserted key and value should be moved
	// from.
	MoveOnlyInt key(1);
	MoveOnlyInt val(22);
	auto result = m.insert_or_assign(std::move(key), std::move(val));
	EXPECT_EQ(1, result.first->first.data());
	EXPECT_EQ(22, result.first->second.data());
	EXPECT_TRUE(result.second);
	EXPECT_EQ(1u, m.size());
	EXPECT_EQ(0, key.data()); // moved from
	EXPECT_EQ(0, val.data()); // moved from

	// Second call with same key should result in an assignment, overwriting the
	// old value. Assignment should be indicated by setting the second pair member
	// to \|false\|. Only the inserted value should be moved from, the key should be
	// left intact.
	key = MoveOnlyInt(1);
	val = MoveOnlyInt(44);
	result = m.insert_or_assign(std::move(key), std::move(val));
	EXPECT_EQ(1, result.first->first.data());
	EXPECT_EQ(44, result.first->second.data());
	EXPECT_FALSE(result.second);
	EXPECT_EQ(1u, m.size());
	EXPECT_EQ(1, key.data()); // not moved from
	EXPECT_EQ(0, val.data()); // moved from

	// Check that random insertion results in sorted range.
	flat_map<MoveOnlyInt, int> map;
	for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
	map.insert_or_assign(MoveOnlyInt(i), i);
	EXPECT_TRUE(absl::c_is_sorted(map));
	}
	}

	// insert_or_assign(const_iterator hint, K&&, M&&)
	TEST(FlatMap, InsertOrAssignMoveOnlyKeyWithHint) {
	flat_map<MoveOnlyInt, MoveOnlyInt> m;

	// Initial insertion should return an iterator to the element. The inserted
	// key and value should be moved from.
	MoveOnlyInt key(1);
	MoveOnlyInt val(22);
	auto result = m.insert_or_assign(m.end(), std::move(key), std::move(val));
	EXPECT_EQ(1, result->first.data());
	EXPECT_EQ(22, result->second.data());
	EXPECT_EQ(1u, m.size());
	EXPECT_EQ(0, key.data()); // moved from
	EXPECT_EQ(0, val.data()); // moved from

	// Second call with same key should result in an assignment, overwriting the
	// old value. Only the inserted value should be moved from, the key should be
	// left intact.
	key = MoveOnlyInt(1);
	val = MoveOnlyInt(44);
	result = m.insert_or_assign(m.end(), std::move(key), std::move(val));
	EXPECT_EQ(1, result->first.data());
	EXPECT_EQ(44, result->second.data());
	EXPECT_EQ(1u, m.size());
	EXPECT_EQ(1, key.data()); // not moved from
	EXPECT_EQ(0, val.data()); // moved from

	// Check that random insertion results in sorted range.
	flat_map<MoveOnlyInt, int> map;
	for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
	map.insert_or_assign(map.end(), MoveOnlyInt(i), i);
	EXPECT_TRUE(absl::c_is_sorted(map));
	}
	}

	// try_emplace(K&&, Args&&...)
	TEST(FlatMap, TryEmplaceMoveOnlyKey) {
	flat_map<MoveOnlyInt, std::pair<MoveOnlyInt, MoveOnlyInt>> m;

	// Trying to emplace into an empty map should succeed. Insertion should return
	// an iterator to the element and set the second pair member to \|true\|. The
	// inserted key and value should be moved from.
	MoveOnlyInt key(1);
	MoveOnlyInt val1(22);
	MoveOnlyInt val2(44);
	// Test piecewise construction of mapped_type.
	auto result = m.try_emplace(std::move(key), std::move(val1), std::move(val2));
	EXPECT_EQ(1, result.first->first.data());
	EXPECT_EQ(22, result.first->second.first.data());
	EXPECT_EQ(44, result.first->second.second.data());
	EXPECT_TRUE(result.second);
	EXPECT_EQ(1u, m.size());
	EXPECT_EQ(0, key.data()); // moved from
	EXPECT_EQ(0, val1.data()); // moved from
	EXPECT_EQ(0, val2.data()); // moved from

	// Second call with same key should result in a no-op, returning an iterator
	// to the existing element and returning false as the second pair member.
	// Key and values that were attempted to be inserted should be left intact.
	key = MoveOnlyInt(1);
	auto paired_val = std::make_pair(MoveOnlyInt(33), MoveOnlyInt(55));
	// Test construction of mapped_type from pair.
	result = m.try_emplace(std::move(key), std::move(paired_val));
	EXPECT_EQ(1, result.first->first.data());
	EXPECT_EQ(22, result.first->second.first.data());
	EXPECT_EQ(44, result.first->second.second.data());
	EXPECT_FALSE(result.second);
	EXPECT_EQ(1u, m.size());
	EXPECT_EQ(1, key.data()); // not moved from
	EXPECT_EQ(33, paired_val.first.data()); // not moved from
	EXPECT_EQ(55, paired_val.second.data()); // not moved from

	// Check that random insertion results in sorted range.
	flat_map<MoveOnlyInt, int> map;
	for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
	map.try_emplace(MoveOnlyInt(i), i);
	EXPECT_TRUE(absl::c_is_sorted(map));
	}
	}

	// try_emplace(const_iterator hint, K&&, Args&&...)
	TEST(FlatMap, TryEmplaceMoveOnlyKeyWithHint) {
	flat_map<MoveOnlyInt, std::pair<MoveOnlyInt, MoveOnlyInt>> m;

	// Trying to emplace into an empty map should succeed. Insertion should return
	// an iterator to the element. The inserted key and value should be moved
	// from.
	MoveOnlyInt key(1);
	MoveOnlyInt val1(22);
	MoveOnlyInt val2(44);
	// Test piecewise construction of mapped_type.
	auto result =
	m.try_emplace(m.end(), std::move(key), std::move(val1), std::move(val2));
	EXPECT_EQ(1, result->first.data());
	EXPECT_EQ(22, result->second.first.data());
	EXPECT_EQ(44, result->second.second.data());
	EXPECT_EQ(1u, m.size());
	EXPECT_EQ(0, key.data()); // moved from
	EXPECT_EQ(0, val1.data()); // moved from
	EXPECT_EQ(0, val2.data()); // moved from

	// Second call with same key should result in a no-op, returning an iterator
	// to the existing element. Key and values that were attempted to be inserted
	// should be left intact.
	key = MoveOnlyInt(1);
	val1 = MoveOnlyInt(33);
	val2 = MoveOnlyInt(55);
	auto paired_val = std::make_pair(MoveOnlyInt(33), MoveOnlyInt(55));
	// Test construction of mapped_type from pair.
	result = m.try_emplace(m.end(), std::move(key), std::move(paired_val));
	EXPECT_EQ(1, result->first.data());
	EXPECT_EQ(22, result->second.first.data());
	EXPECT_EQ(44, result->second.second.data());
	EXPECT_EQ(1u, m.size());
	EXPECT_EQ(1, key.data()); // not moved from
	EXPECT_EQ(33, paired_val.first.data()); // not moved from
	EXPECT_EQ(55, paired_val.second.data()); // not moved from

	// Check that random insertion results in sorted range.
	flat_map<MoveOnlyInt, int> map;
	for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
	map.try_emplace(map.end(), MoveOnlyInt(i), i);
	EXPECT_TRUE(absl::c_is_sorted(map));
	}
	}

	TEST(FlatMap, UsingTransparentCompare) {
	using ExplicitInt = MoveOnlyInt;
	flat_map<ExplicitInt, int> m;
	const auto& m1 = m;
	int x = 0;

	// Check if we can use lookup functions without converting to key_type.
	// Correctness is checked in flat_tree tests.
	m.count(x);
	m1.count(x);
	m.find(x);
	m1.find(x);
	m.equal_range(x);
	m1.equal_range(x);
	m.lower_bound(x);
	m1.lower_bound(x);
	m.upper_bound(x);
	m1.upper_bound(x);
	m.erase(x);

	// Check if we broke overload resolution.
	m.emplace(ExplicitInt(0), 0);
	m.emplace(ExplicitInt(1), 0);
	m.erase(m.begin());
	m.erase(m.cbegin());
	}

	TEST(FlatMap, SupportsEraseIf) {
	flat_map<MoveOnlyInt, MoveOnlyInt> m;
	m.insert(std::make_pair(MoveOnlyInt(1), MoveOnlyInt(1)));
	m.insert(std::make_pair(MoveOnlyInt(2), MoveOnlyInt(2)));
	m.insert(std::make_pair(MoveOnlyInt(3), MoveOnlyInt(3)));
	m.insert(std::make_pair(MoveOnlyInt(4), MoveOnlyInt(4)));
	m.insert(std::make_pair(MoveOnlyInt(5), MoveOnlyInt(5)));

	EraseIf(m, [to_be_removed = MoveOnlyInt(2)](
	const std::pair<MoveOnlyInt, MoveOnlyInt>& e) {
	return e.first == to_be_removed;
	});

	EXPECT_EQ(m.size(), 4u);
	ASSERT_TRUE(m.find(MoveOnlyInt(1)) != m.end());
	ASSERT_FALSE(m.find(MoveOnlyInt(2)) != m.end());
	ASSERT_TRUE(m.find(MoveOnlyInt(3)) != m.end());
	ASSERT_TRUE(m.find(MoveOnlyInt(4)) != m.end());
	ASSERT_TRUE(m.find(MoveOnlyInt(5)) != m.end());
	}

	} // namespace
	} // namespace webrtc