diff --git a/rtc_base/BUILD.gn b/rtc_base/BUILD.gn
index 7ea069a..8dc89fa 100644
--- a/rtc_base/BUILD.gn
+++ b/rtc_base/BUILD.gn
@@ -1399,6 +1399,7 @@
         "../test:fileutils",
         "../test:test_main",
         "../test:test_support",
+        "containers:unittests",
         "memory:unittests",
         "synchronization:mutex",
         "task_utils:to_queued_task",
diff --git a/rtc_base/containers/BUILD.gn b/rtc_base/containers/BUILD.gn
new file mode 100644
index 0000000..f303e70
--- /dev/null
+++ b/rtc_base/containers/BUILD.gn
@@ -0,0 +1,59 @@
+# 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.
+
+import("../../webrtc.gni")
+
+rtc_library("flat_containers_internal") {
+  sources = [
+    "as_const.h",
+    "flat_tree.cc",
+    "flat_tree.h",
+    "identity.h",
+    "invoke.h",
+    "move_only_int.h",
+    "not_fn.h",
+    "void_t.h",
+  ]
+  deps = [
+    "..:checks",
+    "../system:no_unique_address",
+  ]
+  absl_deps = [ "//third_party/abseil-cpp/absl/algorithm:container" ]
+  visibility = [ ":*" ]
+}
+
+rtc_source_set("flat_set") {
+  sources = [ "flat_set.h" ]
+  deps = [ ":flat_containers_internal" ]
+}
+
+rtc_source_set("flat_map") {
+  sources = [ "flat_map.h" ]
+  deps = [
+    ":flat_containers_internal",
+    "..:checks",
+  ]
+}
+
+rtc_library("unittests") {
+  testonly = true
+  sources = [
+    "flat_map_unittest.cc",
+    "flat_set_unittest.cc",
+    "flat_tree_unittest.cc",
+  ]
+  deps = [
+    ":flat_containers_internal",
+    ":flat_map",
+    ":flat_set",
+    "../../test:test_support",
+    "//testing/gmock:gmock",
+    "//testing/gtest:gtest",
+  ]
+  absl_deps = [ "//third_party/abseil-cpp/absl/algorithm:container" ]
+}
diff --git a/rtc_base/containers/as_const.h b/rtc_base/containers/as_const.h
new file mode 100644
index 0000000..a41b3bc
--- /dev/null
+++ b/rtc_base/containers/as_const.h
@@ -0,0 +1,32 @@
+/*
+ *  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.
+
+#ifndef RTC_BASE_CONTAINERS_AS_CONST_H_
+#define RTC_BASE_CONTAINERS_AS_CONST_H_
+
+#include <type_traits>
+
+namespace webrtc {
+
+// C++14 implementation of C++17's std::as_const():
+// https://en.cppreference.com/w/cpp/utility/as_const
+template <typename T>
+constexpr std::add_const_t<T>& as_const(T& t) noexcept {
+  return t;
+}
+
+template <typename T>
+void as_const(const T&& t) = delete;
+
+}  // namespace webrtc
+
+#endif  // RTC_BASE_CONTAINERS_AS_CONST_H_
diff --git a/rtc_base/containers/flat_map.h b/rtc_base/containers/flat_map.h
new file mode 100644
index 0000000..9fa8056
--- /dev/null
+++ b/rtc_base/containers/flat_map.h
@@ -0,0 +1,364 @@
+/*
+ *  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.
+
+#ifndef RTC_BASE_CONTAINERS_FLAT_MAP_H_
+#define RTC_BASE_CONTAINERS_FLAT_MAP_H_
+
+#include <functional>
+#include <tuple>
+#include <utility>
+#include <vector>
+
+#include "rtc_base/checks.h"
+#include "rtc_base/containers/flat_tree.h"
+
+namespace webrtc {
+
+namespace flat_containers_internal {
+
+// An implementation of the flat_tree GetKeyFromValue template parameter that
+// extracts the key as the first element of a pair.
+struct GetFirst {
+  template <class Key, class Mapped>
+  constexpr const Key& operator()(const std::pair<Key, Mapped>& p) const {
+    return p.first;
+  }
+};
+
+}  // namespace flat_containers_internal
+
+// flat_map is a container with a std::map-like interface that stores its
+// contents in a sorted container, by default a vector.
+//
+// Its implementation mostly tracks the corresponding standardization proposal
+// https://wg21.link/P0429, except that the storage of keys and values is not
+// split.
+//
+// PROS
+//
+//  - Good memory locality.
+//  - Low overhead, especially for smaller maps.
+//  - Performance is good for more workloads than you might expect (see
+//    //base/containers/README.md in Chromium repository)
+//  - Supports C++14 map interface.
+//
+// CONS
+//
+//  - Inserts and removals are O(n).
+//
+// IMPORTANT NOTES
+//
+//  - Iterators are invalidated across mutations. This means that the following
+//    line of code has undefined behavior since adding a new element could
+//    resize the container, invalidating all iterators:
+//      container["new element"] = it.second;
+//  - If possible, construct a flat_map in one operation by inserting into
+//    a container and moving that container into the flat_map constructor.
+//
+// QUICK REFERENCE
+//
+// Most of the core functionality is inherited from flat_tree. Please see
+// flat_tree.h for more details for most of these functions. As a quick
+// reference, the functions available are:
+//
+// Constructors (inputs need not be sorted):
+//   flat_map(const flat_map&);
+//   flat_map(flat_map&&);
+//   flat_map(InputIterator first, InputIterator last,
+//            const Compare& compare = Compare());
+//   flat_map(const container_type& items,
+//            const Compare& compare = Compare());
+//   flat_map(container_type&& items,
+//            const Compare& compare = Compare()); // Re-use storage.
+//   flat_map(std::initializer_list<value_type> ilist,
+//            const Compare& comp = Compare());
+//
+// Constructors (inputs need to be sorted):
+//   flat_map(sorted_unique_t,
+//            InputIterator first, InputIterator last,
+//            const Compare& compare = Compare());
+//   flat_map(sorted_unique_t,
+//            const container_type& items,
+//            const Compare& compare = Compare());
+//   flat_map(sorted_unique_t,
+//            container_type&& items,
+//            const Compare& compare = Compare());  // Re-use storage.
+//   flat_map(sorted_unique_t,
+//            std::initializer_list<value_type> ilist,
+//            const Compare& comp = Compare());
+//
+// Assignment functions:
+//   flat_map& operator=(const flat_map&);
+//   flat_map& operator=(flat_map&&);
+//   flat_map& operator=(initializer_list<value_type>);
+//
+// Memory management functions:
+//   void   reserve(size_t);
+//   size_t capacity() const;
+//   void   shrink_to_fit();
+//
+// Size management functions:
+//   void   clear();
+//   size_t size() const;
+//   size_t max_size() const;
+//   bool   empty() const;
+//
+// Iterator functions:
+//   iterator               begin();
+//   const_iterator         begin() const;
+//   const_iterator         cbegin() const;
+//   iterator               end();
+//   const_iterator         end() const;
+//   const_iterator         cend() const;
+//   reverse_iterator       rbegin();
+//   const reverse_iterator rbegin() const;
+//   const_reverse_iterator crbegin() const;
+//   reverse_iterator       rend();
+//   const_reverse_iterator rend() const;
+//   const_reverse_iterator crend() const;
+//
+// Insert and accessor functions:
+//   mapped_type&         operator[](const key_type&);
+//   mapped_type&         operator[](key_type&&);
+//   mapped_type&         at(const K&);
+//   const mapped_type&   at(const K&) const;
+//   pair<iterator, bool> insert(const value_type&);
+//   pair<iterator, bool> insert(value_type&&);
+//   iterator             insert(const_iterator hint, const value_type&);
+//   iterator             insert(const_iterator hint, value_type&&);
+//   void                 insert(InputIterator first, InputIterator last);
+//   pair<iterator, bool> insert_or_assign(K&&, M&&);
+//   iterator             insert_or_assign(const_iterator hint, K&&, M&&);
+//   pair<iterator, bool> emplace(Args&&...);
+//   iterator             emplace_hint(const_iterator, Args&&...);
+//   pair<iterator, bool> try_emplace(K&&, Args&&...);
+//   iterator             try_emplace(const_iterator hint, K&&, Args&&...);
+
+// Underlying type functions:
+//   container_type       extract() &&;
+//   void                 replace(container_type&&);
+//
+// Erase functions:
+//   iterator erase(iterator);
+//   iterator erase(const_iterator);
+//   iterator erase(const_iterator first, const_iterator& last);
+//   template <class K> size_t erase(const K& key);
+//
+// Comparators (see std::map documentation).
+//   key_compare   key_comp() const;
+//   value_compare value_comp() const;
+//
+// Search functions:
+//   template <typename K> size_t                   count(const K&) const;
+//   template <typename K> iterator                 find(const K&);
+//   template <typename K> const_iterator           find(const K&) const;
+//   template <typename K> bool                     contains(const K&) const;
+//   template <typename K> pair<iterator, iterator> equal_range(const K&);
+//   template <typename K> iterator                 lower_bound(const K&);
+//   template <typename K> const_iterator           lower_bound(const K&) const;
+//   template <typename K> iterator                 upper_bound(const K&);
+//   template <typename K> const_iterator           upper_bound(const K&) const;
+//
+// General functions:
+//   void swap(flat_map&);
+//
+// Non-member operators:
+//   bool operator==(const flat_map&, const flat_map);
+//   bool operator!=(const flat_map&, const flat_map);
+//   bool operator<(const flat_map&, const flat_map);
+//   bool operator>(const flat_map&, const flat_map);
+//   bool operator>=(const flat_map&, const flat_map);
+//   bool operator<=(const flat_map&, const flat_map);
+//
+template <class Key,
+          class Mapped,
+          class Compare = std::less<>,
+          class Container = std::vector<std::pair<Key, Mapped>>>
+class flat_map : public ::webrtc::flat_containers_internal::flat_tree<
+                     Key,
+                     flat_containers_internal::GetFirst,
+                     Compare,
+                     Container> {
+ private:
+  using tree = typename ::webrtc::flat_containers_internal::
+      flat_tree<Key, flat_containers_internal::GetFirst, Compare, Container>;
+
+ public:
+  using key_type = typename tree::key_type;
+  using mapped_type = Mapped;
+  using value_type = typename tree::value_type;
+  using reference = typename Container::reference;
+  using const_reference = typename Container::const_reference;
+  using size_type = typename Container::size_type;
+  using difference_type = typename Container::difference_type;
+  using iterator = typename tree::iterator;
+  using const_iterator = typename tree::const_iterator;
+  using reverse_iterator = typename tree::reverse_iterator;
+  using const_reverse_iterator = typename tree::const_reverse_iterator;
+  using container_type = typename tree::container_type;
+
+  // --------------------------------------------------------------------------
+  // Lifetime and assignments.
+  //
+  // Note: we explicitly bring operator= in because otherwise
+  //   flat_map<...> x;
+  //   x = {...};
+  // Would first create a flat_map and then move assign it. This most likely
+  // would be optimized away but still affects our debug builds.
+
+  using tree::tree;
+  using tree::operator=;
+
+  // Out-of-bound calls to at() will CHECK.
+  template <class K>
+  mapped_type& at(const K& key);
+  template <class K>
+  const mapped_type& at(const K& key) const;
+
+  // --------------------------------------------------------------------------
+  // Map-specific insert operations.
+  //
+  // Normal insert() functions are inherited from flat_tree.
+  //
+  // Assume that every operation invalidates iterators and references.
+  // Insertion of one element can take O(size).
+
+  mapped_type& operator[](const key_type& key);
+  mapped_type& operator[](key_type&& key);
+
+  template <class K, class M>
+  std::pair<iterator, bool> insert_or_assign(K&& key, M&& obj);
+  template <class K, class M>
+  iterator insert_or_assign(const_iterator hint, K&& key, M&& obj);
+
+  template <class K, class... Args>
+  std::enable_if_t<std::is_constructible<key_type, K&&>::value,
+                   std::pair<iterator, bool>>
+  try_emplace(K&& key, Args&&... args);
+
+  template <class K, class... Args>
+  std::enable_if_t<std::is_constructible<key_type, K&&>::value, iterator>
+  try_emplace(const_iterator hint, K&& key, Args&&... args);
+
+  // --------------------------------------------------------------------------
+  // General operations.
+  //
+  // Assume that swap invalidates iterators and references.
+
+  void swap(flat_map& other) noexcept;
+
+  friend void swap(flat_map& lhs, flat_map& rhs) noexcept { lhs.swap(rhs); }
+};
+
+// ----------------------------------------------------------------------------
+// Lookups.
+
+template <class Key, class Mapped, class Compare, class Container>
+template <class K>
+auto flat_map<Key, Mapped, Compare, Container>::at(const K& key)
+    -> mapped_type& {
+  iterator found = tree::find(key);
+  RTC_CHECK(found != tree::end());
+  return found->second;
+}
+
+template <class Key, class Mapped, class Compare, class Container>
+template <class K>
+auto flat_map<Key, Mapped, Compare, Container>::at(const K& key) const
+    -> const mapped_type& {
+  const_iterator found = tree::find(key);
+  RTC_CHECK(found != tree::cend());
+  return found->second;
+}
+
+// ----------------------------------------------------------------------------
+// Insert operations.
+
+template <class Key, class Mapped, class Compare, class Container>
+auto flat_map<Key, Mapped, Compare, Container>::operator[](const key_type& key)
+    -> mapped_type& {
+  iterator found = tree::lower_bound(key);
+  if (found == tree::end() || tree::key_comp()(key, found->first))
+    found = tree::unsafe_emplace(found, key, mapped_type());
+  return found->second;
+}
+
+template <class Key, class Mapped, class Compare, class Container>
+auto flat_map<Key, Mapped, Compare, Container>::operator[](key_type&& key)
+    -> mapped_type& {
+  iterator found = tree::lower_bound(key);
+  if (found == tree::end() || tree::key_comp()(key, found->first))
+    found = tree::unsafe_emplace(found, std::move(key), mapped_type());
+  return found->second;
+}
+
+template <class Key, class Mapped, class Compare, class Container>
+template <class K, class M>
+auto flat_map<Key, Mapped, Compare, Container>::insert_or_assign(K&& key,
+                                                                 M&& obj)
+    -> std::pair<iterator, bool> {
+  auto result =
+      tree::emplace_key_args(key, std::forward<K>(key), std::forward<M>(obj));
+  if (!result.second)
+    result.first->second = std::forward<M>(obj);
+  return result;
+}
+
+template <class Key, class Mapped, class Compare, class Container>
+template <class K, class M>
+auto flat_map<Key, Mapped, Compare, Container>::insert_or_assign(
+    const_iterator hint,
+    K&& key,
+    M&& obj) -> iterator {
+  auto result = tree::emplace_hint_key_args(hint, key, std::forward<K>(key),
+                                            std::forward<M>(obj));
+  if (!result.second)
+    result.first->second = std::forward<M>(obj);
+  return result.first;
+}
+
+template <class Key, class Mapped, class Compare, class Container>
+template <class K, class... Args>
+auto flat_map<Key, Mapped, Compare, Container>::try_emplace(K&& key,
+                                                            Args&&... args)
+    -> std::enable_if_t<std::is_constructible<key_type, K&&>::value,
+                        std::pair<iterator, bool>> {
+  return tree::emplace_key_args(
+      key, std::piecewise_construct,
+      std::forward_as_tuple(std::forward<K>(key)),
+      std::forward_as_tuple(std::forward<Args>(args)...));
+}
+
+template <class Key, class Mapped, class Compare, class Container>
+template <class K, class... Args>
+auto flat_map<Key, Mapped, Compare, Container>::try_emplace(const_iterator hint,
+                                                            K&& key,
+                                                            Args&&... args)
+    -> std::enable_if_t<std::is_constructible<key_type, K&&>::value, iterator> {
+  return tree::emplace_hint_key_args(
+             hint, key, std::piecewise_construct,
+             std::forward_as_tuple(std::forward<K>(key)),
+             std::forward_as_tuple(std::forward<Args>(args)...))
+      .first;
+}
+
+// ----------------------------------------------------------------------------
+// General operations.
+
+template <class Key, class Mapped, class Compare, class Container>
+void flat_map<Key, Mapped, Compare, Container>::swap(flat_map& other) noexcept {
+  tree::swap(other);
+}
+
+}  // namespace webrtc
+
+#endif  // RTC_BASE_CONTAINERS_FLAT_MAP_H_
diff --git a/rtc_base/containers/flat_map_unittest.cc b/rtc_base/containers/flat_map_unittest.cc
new file mode 100644
index 0000000..3ece2ff
--- /dev/null
+++ b/rtc_base/containers/flat_map_unittest.cc
@@ -0,0 +1,433 @@
+/*
+ *  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());
+}
+
+}  // namespace
+}  // namespace webrtc
diff --git a/rtc_base/containers/flat_set.h b/rtc_base/containers/flat_set.h
new file mode 100644
index 0000000..5c43179
--- /dev/null
+++ b/rtc_base/containers/flat_set.h
@@ -0,0 +1,166 @@
+/*
+ *  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.
+
+#ifndef RTC_BASE_CONTAINERS_FLAT_SET_H_
+#define RTC_BASE_CONTAINERS_FLAT_SET_H_
+
+#include <functional>
+#include <vector>
+
+#include "rtc_base/containers/flat_tree.h"
+#include "rtc_base/containers/identity.h"
+
+namespace webrtc {
+
+// flat_set is a container with a std::set-like interface that stores its
+// contents in a sorted container, by default a vector.
+//
+// Its implementation mostly tracks the corresponding standardization proposal
+// https://wg21.link/P1222.
+//
+//
+// PROS
+//
+//  - Good memory locality.
+//  - Low overhead, especially for smaller sets.
+//  - Performance is good for more workloads than you might expect (see
+//    //base/containers/README.md in Chromium repository)
+//  - Supports C++14 set interface.
+//
+// CONS
+//
+//  - Inserts and removals are O(n).
+//
+// IMPORTANT NOTES
+//
+//  - Iterators are invalidated across mutations.
+//  - If possible, construct a flat_set in one operation by inserting into
+//    a container and moving that container into the flat_set constructor.
+//  - For multiple removals use base::EraseIf() which is O(n) rather than
+//    O(n * removed_items).
+//
+// QUICK REFERENCE
+//
+// Most of the core functionality is inherited from flat_tree. Please see
+// flat_tree.h for more details for most of these functions. As a quick
+// reference, the functions available are:
+//
+// Constructors (inputs need not be sorted):
+//   flat_set(const flat_set&);
+//   flat_set(flat_set&&);
+//   flat_set(InputIterator first, InputIterator last,
+//            const Compare& compare = Compare());
+//   flat_set(const container_type& items,
+//            const Compare& compare = Compare());
+//   flat_set(container_type&& items,
+//            const Compare& compare = Compare());  // Re-use storage.
+//   flat_set(std::initializer_list<value_type> ilist,
+//            const Compare& comp = Compare());
+//
+// Constructors (inputs need to be sorted):
+//   flat_set(sorted_unique_t,
+//            InputIterator first, InputIterator last,
+//            const Compare& compare = Compare());
+//   flat_set(sorted_unique_t,
+//            const container_type& items,
+//            const Compare& compare = Compare());
+//   flat_set(sorted_unique_t,
+//            container_type&& items,
+//            const Compare& compare = Compare());  // Re-use storage.
+//   flat_set(sorted_unique_t,
+//            std::initializer_list<value_type> ilist,
+//            const Compare& comp = Compare());
+//
+// Assignment functions:
+//   flat_set& operator=(const flat_set&);
+//   flat_set& operator=(flat_set&&);
+//   flat_set& operator=(initializer_list<Key>);
+//
+// Memory management functions:
+//   void   reserve(size_t);
+//   size_t capacity() const;
+//   void   shrink_to_fit();
+//
+// Size management functions:
+//   void   clear();
+//   size_t size() const;
+//   size_t max_size() const;
+//   bool   empty() const;
+//
+// Iterator functions:
+//   iterator               begin();
+//   const_iterator         begin() const;
+//   const_iterator         cbegin() const;
+//   iterator               end();
+//   const_iterator         end() const;
+//   const_iterator         cend() const;
+//   reverse_iterator       rbegin();
+//   const reverse_iterator rbegin() const;
+//   const_reverse_iterator crbegin() const;
+//   reverse_iterator       rend();
+//   const_reverse_iterator rend() const;
+//   const_reverse_iterator crend() const;
+//
+// Insert and accessor functions:
+//   pair<iterator, bool> insert(const key_type&);
+//   pair<iterator, bool> insert(key_type&&);
+//   void                 insert(InputIterator first, InputIterator last);
+//   iterator             insert(const_iterator hint, const key_type&);
+//   iterator             insert(const_iterator hint, key_type&&);
+//   pair<iterator, bool> emplace(Args&&...);
+//   iterator             emplace_hint(const_iterator, Args&&...);
+//
+// Underlying type functions:
+//   container_type       extract() &&;
+//   void                 replace(container_type&&);
+//
+// Erase functions:
+//   iterator erase(iterator);
+//   iterator erase(const_iterator);
+//   iterator erase(const_iterator first, const_iterator& last);
+//   template <typename K> size_t erase(const K& key);
+//
+// Comparators (see std::set documentation).
+//   key_compare   key_comp() const;
+//   value_compare value_comp() const;
+//
+// Search functions:
+//   template <typename K> size_t                   count(const K&) const;
+//   template <typename K> iterator                 find(const K&);
+//   template <typename K> const_iterator           find(const K&) const;
+//   template <typename K> bool                     contains(const K&) const;
+//   template <typename K> pair<iterator, iterator> equal_range(K&);
+//   template <typename K> iterator                 lower_bound(const K&);
+//   template <typename K> const_iterator           lower_bound(const K&) const;
+//   template <typename K> iterator                 upper_bound(const K&);
+//   template <typename K> const_iterator           upper_bound(const K&) const;
+//
+// General functions:
+//   void swap(flat_set&);
+//
+// Non-member operators:
+//   bool operator==(const flat_set&, const flat_set);
+//   bool operator!=(const flat_set&, const flat_set);
+//   bool operator<(const flat_set&, const flat_set);
+//   bool operator>(const flat_set&, const flat_set);
+//   bool operator>=(const flat_set&, const flat_set);
+//   bool operator<=(const flat_set&, const flat_set);
+//
+template <class Key,
+          class Compare = std::less<>,
+          class Container = std::vector<Key>>
+using flat_set = typename ::webrtc::flat_containers_internal::
+    flat_tree<Key, webrtc::identity, Compare, Container>;
+
+}  // namespace webrtc
+
+#endif  // RTC_BASE_CONTAINERS_FLAT_SET_H_
diff --git a/rtc_base/containers/flat_set_unittest.cc b/rtc_base/containers/flat_set_unittest.cc
new file mode 100644
index 0000000..831afed
--- /dev/null
+++ b/rtc_base/containers/flat_set_unittest.cc
@@ -0,0 +1,129 @@
+/*
+ *  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_set.h"
+
+#include <algorithm>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "rtc_base/containers/move_only_int.h"
+#include "test/gmock.h"
+#include "test/gtest.h"
+
+// A flat_set 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 {
+
+TEST(FlatSet, IncompleteType) {
+  struct A {
+    using Set = flat_set<A>;
+    int data;
+    Set set_with_incomplete_type;
+    Set::iterator it;
+    Set::const_iterator cit;
+
+    // We do not declare operator< because clang complains that it's unused.
+  };
+
+  A a;
+}
+
+TEST(FlatSet, RangeConstructor) {
+  flat_set<int>::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
+
+  flat_set<int> cont(std::begin(input_vals), std::end(input_vals));
+  EXPECT_THAT(cont, ElementsAre(1, 2, 3));
+}
+
+TEST(FlatSet, MoveConstructor) {
+  int input_range[] = {1, 2, 3, 4};
+
+  flat_set<MoveOnlyInt> original(std::begin(input_range),
+                                 std::end(input_range));
+  flat_set<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(FlatSet, InitializerListConstructor) {
+  flat_set<int> cont({1, 2, 3, 4, 5, 6, 10, 8});
+  EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
+}
+
+TEST(FlatSet, InsertFindSize) {
+  flat_set<int> s;
+  s.insert(1);
+  s.insert(1);
+  s.insert(2);
+
+  EXPECT_EQ(2u, s.size());
+  EXPECT_EQ(1, *s.find(1));
+  EXPECT_EQ(2, *s.find(2));
+  EXPECT_EQ(s.end(), s.find(7));
+}
+
+TEST(FlatSet, CopySwap) {
+  flat_set<int> original;
+  original.insert(1);
+  original.insert(2);
+  EXPECT_THAT(original, ElementsAre(1, 2));
+
+  flat_set<int> copy(original);
+  EXPECT_THAT(copy, ElementsAre(1, 2));
+
+  copy.erase(copy.begin());
+  copy.insert(10);
+  EXPECT_THAT(copy, ElementsAre(2, 10));
+
+  original.swap(copy);
+  EXPECT_THAT(original, ElementsAre(2, 10));
+  EXPECT_THAT(copy, ElementsAre(1, 2));
+}
+
+TEST(FlatSet, UsingTransparentCompare) {
+  using ExplicitInt = webrtc::MoveOnlyInt;
+  flat_set<ExplicitInt> s;
+  const auto& s1 = s;
+  int x = 0;
+
+  // Check if we can use lookup functions without converting to key_type.
+  // Correctness is checked in flat_tree tests.
+  s.count(x);
+  s1.count(x);
+  s.find(x);
+  s1.find(x);
+  s.equal_range(x);
+  s1.equal_range(x);
+  s.lower_bound(x);
+  s1.lower_bound(x);
+  s.upper_bound(x);
+  s1.upper_bound(x);
+  s.erase(x);
+
+  // Check if we broke overload resolution.
+  s.emplace(0);
+  s.emplace(1);
+  s.erase(s.begin());
+  s.erase(s.cbegin());
+}
+}  // namespace
+}  // namespace webrtc
diff --git a/rtc_base/containers/flat_tree.cc b/rtc_base/containers/flat_tree.cc
new file mode 100644
index 0000000..9e86db1
--- /dev/null
+++ b/rtc_base/containers/flat_tree.cc
@@ -0,0 +1,19 @@
+/*
+ *  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_tree.h"
+
+namespace webrtc {
+
+sorted_unique_t sorted_unique;
+
+}  // namespace webrtc
diff --git a/rtc_base/containers/flat_tree.h b/rtc_base/containers/flat_tree.h
new file mode 100644
index 0000000..046eef1
--- /dev/null
+++ b/rtc_base/containers/flat_tree.h
@@ -0,0 +1,1102 @@
+/*
+ *  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.
+
+#ifndef RTC_BASE_CONTAINERS_FLAT_TREE_H_
+#define RTC_BASE_CONTAINERS_FLAT_TREE_H_
+
+#include <algorithm>
+#include <iterator>
+#include <type_traits>
+#include <utility>
+#include <vector>
+
+#include "absl/algorithm/container.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/containers/as_const.h"
+#include "rtc_base/containers/not_fn.h"
+#include "rtc_base/containers/void_t.h"
+#include "rtc_base/system/no_unique_address.h"
+
+namespace webrtc {
+// Tag type that allows skipping the sort_and_unique step when constructing a
+// flat_tree in case the underlying container is already sorted and has no
+// duplicate elements.
+struct sorted_unique_t {
+  constexpr sorted_unique_t() = default;
+};
+extern sorted_unique_t sorted_unique;
+
+namespace flat_containers_internal {
+
+// Helper functions used in RTC_DCHECKs below to make sure that inputs tagged
+// with sorted_unique are indeed sorted and unique.
+template <typename Range, typename Comp>
+constexpr bool is_sorted_and_unique(const Range& range, Comp comp) {
+  // Being unique implies that there are no adjacent elements that
+  // compare equal. So this checks that each element is strictly less
+  // than the element after it.
+  return absl::c_adjacent_find(range, webrtc::not_fn(comp)) == std::end(range);
+}
+
+// This is a convenience trait inheriting from std::true_type if Iterator is at
+// least a ForwardIterator and thus supports multiple passes over a range.
+template <class Iterator>
+using is_multipass =
+    std::is_base_of<std::forward_iterator_tag,
+                    typename std::iterator_traits<Iterator>::iterator_category>;
+
+// Uses SFINAE to detect whether type has is_transparent member.
+template <typename T, typename = void>
+struct IsTransparentCompare : std::false_type {};
+template <typename T>
+struct IsTransparentCompare<T, void_t<typename T::is_transparent>>
+    : std::true_type {};
+
+// Helper inspired by C++20's std::to_array to convert a C-style array to a
+// std::array. As opposed to the C++20 version this implementation does not
+// provide an overload for rvalues and does not strip cv qualifers from the
+// returned std::array::value_type. The returned value_type needs to be
+// specified explicitly, allowing the construction of std::arrays with const
+// elements.
+//
+// Reference: https://en.cppreference.com/w/cpp/container/array/to_array
+template <typename U, typename T, size_t N, size_t... I>
+constexpr std::array<U, N> ToArrayImpl(const T (&data)[N],
+                                       std::index_sequence<I...>) {
+  return {{data[I]...}};
+}
+
+template <typename U, typename T, size_t N>
+constexpr std::array<U, N> ToArray(const T (&data)[N]) {
+  return ToArrayImpl<U>(data, std::make_index_sequence<N>());
+}
+
+// std::pair's operator= is not constexpr prior to C++20. Thus we need this
+// small helper to invoke operator= on the .first and .second member explicitly.
+template <typename T>
+constexpr void Assign(T& lhs, T&& rhs) {
+  lhs = std::move(rhs);
+}
+
+template <typename T, typename U>
+constexpr void Assign(std::pair<T, U>& lhs, std::pair<T, U>&& rhs) {
+  Assign(lhs.first, std::move(rhs.first));
+  Assign(lhs.second, std::move(rhs.second));
+}
+
+// constexpr swap implementation. std::swap is not constexpr prior to C++20.
+template <typename T>
+constexpr void Swap(T& lhs, T& rhs) {
+  T tmp = std::move(lhs);
+  Assign(lhs, std::move(rhs));
+  Assign(rhs, std::move(tmp));
+}
+
+// constexpr prev implementation. std::prev is not constexpr prior to C++17.
+template <typename BidirIt>
+constexpr BidirIt Prev(BidirIt it) {
+  return --it;
+}
+
+// constexpr next implementation. std::next is not constexpr prior to C++17.
+template <typename InputIt>
+constexpr InputIt Next(InputIt it) {
+  return ++it;
+}
+
+// constexpr sort implementation. std::sort is not constexpr prior to C++20.
+// While insertion sort has a quadratic worst case complexity, it was chosen
+// because it has linear complexity for nearly sorted data, is stable, and
+// simple to implement.
+template <typename BidirIt, typename Compare>
+constexpr void InsertionSort(BidirIt first, BidirIt last, const Compare& comp) {
+  if (first == last)
+    return;
+
+  for (auto it = Next(first); it != last; ++it) {
+    for (auto curr = it; curr != first && comp(*curr, *Prev(curr)); --curr)
+      Swap(*curr, *Prev(curr));
+  }
+}
+
+// Implementation -------------------------------------------------------------
+
+// Implementation for the sorted associative flat_set and flat_map using a
+// sorted vector as the backing store. Do not use directly.
+//
+// The use of "value" in this is like std::map uses, meaning it's the thing
+// contained (in the case of map it's a <Kay, Mapped> pair). The Key is how
+// things are looked up. In the case of a set, Key == Value. In the case of
+// a map, the Key is a component of a Value.
+//
+// The helper class GetKeyFromValue provides the means to extract a key from a
+// value for comparison purposes. It should implement:
+//   const Key& operator()(const Value&).
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+class flat_tree {
+ public:
+  // --------------------------------------------------------------------------
+  // Types.
+  //
+  using key_type = Key;
+  using key_compare = KeyCompare;
+  using value_type = typename Container::value_type;
+
+  // Wraps the templated key comparison to compare values.
+  struct value_compare {
+    constexpr bool operator()(const value_type& left,
+                              const value_type& right) const {
+      GetKeyFromValue extractor;
+      return comp(extractor(left), extractor(right));
+    }
+
+    RTC_NO_UNIQUE_ADDRESS key_compare comp;
+  };
+
+  using pointer = typename Container::pointer;
+  using const_pointer = typename Container::const_pointer;
+  using reference = typename Container::reference;
+  using const_reference = typename Container::const_reference;
+  using size_type = typename Container::size_type;
+  using difference_type = typename Container::difference_type;
+  using iterator = typename Container::iterator;
+  using const_iterator = typename Container::const_iterator;
+  using reverse_iterator = typename Container::reverse_iterator;
+  using const_reverse_iterator = typename Container::const_reverse_iterator;
+  using container_type = Container;
+
+  // --------------------------------------------------------------------------
+  // Lifetime.
+  //
+  // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity
+  // and take O(N * log(N)) + O(N) if extra memory is available (N is a range
+  // length).
+  //
+  // Assume that move constructors invalidate iterators and references.
+  //
+  // The constructors that take ranges, lists, and vectors do not require that
+  // the input be sorted.
+  //
+  // When passing the webrtc::sorted_unique tag as the first argument no sort
+  // and unique step takes places. This is useful if the underlying container
+  // already has the required properties.
+
+  flat_tree() = default;
+  flat_tree(const flat_tree&) = default;
+  flat_tree(flat_tree&&) = default;
+
+  explicit flat_tree(const key_compare& comp);
+
+  template <class InputIterator>
+  flat_tree(InputIterator first,
+            InputIterator last,
+            const key_compare& comp = key_compare());
+
+  flat_tree(const container_type& items,
+            const key_compare& comp = key_compare());
+
+  explicit flat_tree(container_type&& items,
+                     const key_compare& comp = key_compare());
+
+  flat_tree(std::initializer_list<value_type> ilist,
+            const key_compare& comp = key_compare());
+
+  template <class InputIterator>
+  flat_tree(sorted_unique_t,
+            InputIterator first,
+            InputIterator last,
+            const key_compare& comp = key_compare());
+
+  flat_tree(sorted_unique_t,
+            const container_type& items,
+            const key_compare& comp = key_compare());
+
+  constexpr flat_tree(sorted_unique_t,
+                      container_type&& items,
+                      const key_compare& comp = key_compare());
+
+  flat_tree(sorted_unique_t,
+            std::initializer_list<value_type> ilist,
+            const key_compare& comp = key_compare());
+
+  ~flat_tree() = default;
+
+  // --------------------------------------------------------------------------
+  // Assignments.
+  //
+  // Assume that move assignment invalidates iterators and references.
+
+  flat_tree& operator=(const flat_tree&) = default;
+  flat_tree& operator=(flat_tree&&) = default;
+  // Takes the first if there are duplicates in the initializer list.
+  flat_tree& operator=(std::initializer_list<value_type> ilist);
+
+  // --------------------------------------------------------------------------
+  // Memory management.
+  //
+  // Beware that shrink_to_fit() simply forwards the request to the
+  // container_type and its implementation is free to optimize otherwise and
+  // leave capacity() to be greater that its size.
+  //
+  // reserve() and shrink_to_fit() invalidate iterators and references.
+
+  void reserve(size_type new_capacity);
+  size_type capacity() const;
+  void shrink_to_fit();
+
+  // --------------------------------------------------------------------------
+  // Size management.
+  //
+  // clear() leaves the capacity() of the flat_tree unchanged.
+
+  void clear();
+
+  constexpr size_type size() const;
+  constexpr size_type max_size() const;
+  constexpr bool empty() const;
+
+  // --------------------------------------------------------------------------
+  // Iterators.
+  //
+  // Iterators follow the ordering defined by the key comparator used in
+  // construction of the flat_tree.
+
+  iterator begin();
+  constexpr const_iterator begin() const;
+  const_iterator cbegin() const;
+
+  iterator end();
+  constexpr const_iterator end() const;
+  const_iterator cend() const;
+
+  reverse_iterator rbegin();
+  const_reverse_iterator rbegin() const;
+  const_reverse_iterator crbegin() const;
+
+  reverse_iterator rend();
+  const_reverse_iterator rend() const;
+  const_reverse_iterator crend() const;
+
+  // --------------------------------------------------------------------------
+  // Insert operations.
+  //
+  // Assume that every operation invalidates iterators and references.
+  // Insertion of one element can take O(size). Capacity of flat_tree grows in
+  // an implementation-defined manner.
+  //
+  // NOTE: Prefer to build a new flat_tree from a std::vector (or similar)
+  // instead of calling insert() repeatedly.
+
+  std::pair<iterator, bool> insert(const value_type& val);
+  std::pair<iterator, bool> insert(value_type&& val);
+
+  iterator insert(const_iterator position_hint, const value_type& x);
+  iterator insert(const_iterator position_hint, value_type&& x);
+
+  // This method inserts the values from the range [first, last) into the
+  // current tree.
+  template <class InputIterator>
+  void insert(InputIterator first, InputIterator last);
+
+  template <class... Args>
+  std::pair<iterator, bool> emplace(Args&&... args);
+
+  template <class... Args>
+  iterator emplace_hint(const_iterator position_hint, Args&&... args);
+
+  // --------------------------------------------------------------------------
+  // Underlying type operations.
+  //
+  // Assume that either operation invalidates iterators and references.
+
+  // Extracts the container_type and returns it to the caller. Ensures that
+  // `this` is `empty()` afterwards.
+  container_type extract() &&;
+
+  // Replaces the container_type with `body`. Expects that `body` is sorted
+  // and has no repeated elements with regard to value_comp().
+  void replace(container_type&& body);
+
+  // --------------------------------------------------------------------------
+  // Erase operations.
+  //
+  // Assume that every operation invalidates iterators and references.
+  //
+  // erase(position), erase(first, last) can take O(size).
+  // erase(key) may take O(size) + O(log(size)).
+  //
+  // Prefer webrtc::EraseIf() or some other variation on erase(remove(), end())
+  // idiom when deleting multiple non-consecutive elements.
+
+  iterator erase(iterator position);
+  // Artificially templatized to break ambiguity if `iterator` and
+  // `const_iterator` are the same type.
+  template <typename DummyT = void>
+  iterator erase(const_iterator position);
+  iterator erase(const_iterator first, const_iterator last);
+  template <typename K>
+  size_type erase(const K& key);
+
+  // --------------------------------------------------------------------------
+  // Comparators.
+
+  constexpr key_compare key_comp() const;
+  constexpr value_compare value_comp() const;
+
+  // --------------------------------------------------------------------------
+  // Search operations.
+  //
+  // Search operations have O(log(size)) complexity.
+
+  template <typename K>
+  size_type count(const K& key) const;
+
+  template <typename K>
+  iterator find(const K& key);
+
+  template <typename K>
+  const_iterator find(const K& key) const;
+
+  template <typename K>
+  bool contains(const K& key) const;
+
+  template <typename K>
+  std::pair<iterator, iterator> equal_range(const K& key);
+
+  template <typename K>
+  std::pair<const_iterator, const_iterator> equal_range(const K& key) const;
+
+  template <typename K>
+  iterator lower_bound(const K& key);
+
+  template <typename K>
+  const_iterator lower_bound(const K& key) const;
+
+  template <typename K>
+  iterator upper_bound(const K& key);
+
+  template <typename K>
+  const_iterator upper_bound(const K& key) const;
+
+  // --------------------------------------------------------------------------
+  // General operations.
+  //
+  // Assume that swap invalidates iterators and references.
+  //
+  // Implementation note: currently we use operator==() and operator<() on
+  // std::vector, because they have the same contract we need, so we use them
+  // directly for brevity and in case it is more optimal than calling equal()
+  // and lexicograhpical_compare(). If the underlying container type is changed,
+  // this code may need to be modified.
+
+  void swap(flat_tree& other) noexcept;
+
+  friend bool operator==(const flat_tree& lhs, const flat_tree& rhs) {
+    return lhs.body_ == rhs.body_;
+  }
+
+  friend bool operator!=(const flat_tree& lhs, const flat_tree& rhs) {
+    return !(lhs == rhs);
+  }
+
+  friend bool operator<(const flat_tree& lhs, const flat_tree& rhs) {
+    return lhs.body_ < rhs.body_;
+  }
+
+  friend bool operator>(const flat_tree& lhs, const flat_tree& rhs) {
+    return rhs < lhs;
+  }
+
+  friend bool operator>=(const flat_tree& lhs, const flat_tree& rhs) {
+    return !(lhs < rhs);
+  }
+
+  friend bool operator<=(const flat_tree& lhs, const flat_tree& rhs) {
+    return !(lhs > rhs);
+  }
+
+  friend void swap(flat_tree& lhs, flat_tree& rhs) noexcept { lhs.swap(rhs); }
+
+ protected:
+  // Emplaces a new item into the tree that is known not to be in it. This
+  // is for implementing map operator[].
+  template <class... Args>
+  iterator unsafe_emplace(const_iterator position, Args&&... args);
+
+  // Attempts to emplace a new element with key |key|. Only if |key| is not yet
+  // present, construct value_type from |args| and insert it. Returns an
+  // iterator to the element with key |key| and a bool indicating whether an
+  // insertion happened.
+  template <class K, class... Args>
+  std::pair<iterator, bool> emplace_key_args(const K& key, Args&&... args);
+
+  // Similar to |emplace_key_args|, but checks |hint| first as a possible
+  // insertion position.
+  template <class K, class... Args>
+  std::pair<iterator, bool> emplace_hint_key_args(const_iterator hint,
+                                                  const K& key,
+                                                  Args&&... args);
+
+ private:
+  // Helper class for e.g. lower_bound that can compare a value on the left
+  // to a key on the right.
+  struct KeyValueCompare {
+    // The key comparison object must outlive this class.
+    explicit KeyValueCompare(const key_compare& comp) : comp_(comp) {}
+
+    template <typename T, typename U>
+    bool operator()(const T& lhs, const U& rhs) const {
+      return comp_(extract_if_value_type(lhs), extract_if_value_type(rhs));
+    }
+
+   private:
+    const key_type& extract_if_value_type(const value_type& v) const {
+      GetKeyFromValue extractor;
+      return extractor(v);
+    }
+
+    template <typename K>
+    const K& extract_if_value_type(const K& k) const {
+      return k;
+    }
+
+    const key_compare& comp_;
+  };
+
+  iterator const_cast_it(const_iterator c_it) {
+    auto distance = std::distance(cbegin(), c_it);
+    return std::next(begin(), distance);
+  }
+
+  // This method is inspired by both std::map::insert(P&&) and
+  // std::map::insert_or_assign(const K&, V&&). It inserts val if an equivalent
+  // element is not present yet, otherwise it overwrites. It returns an iterator
+  // to the modified element and a flag indicating whether insertion or
+  // assignment happened.
+  template <class V>
+  std::pair<iterator, bool> insert_or_assign(V&& val) {
+    auto position = lower_bound(GetKeyFromValue()(val));
+
+    if (position == end() || value_comp()(val, *position))
+      return {body_.emplace(position, std::forward<V>(val)), true};
+
+    *position = std::forward<V>(val);
+    return {position, false};
+  }
+
+  // This method is similar to insert_or_assign, with the following differences:
+  // - Instead of searching [begin(), end()) it only searches [first, last).
+  // - In case no equivalent element is found, val is appended to the end of the
+  //   underlying body and an iterator to the next bigger element in [first,
+  //   last) is returned.
+  template <class V>
+  std::pair<iterator, bool> append_or_assign(iterator first,
+                                             iterator last,
+                                             V&& val) {
+    auto position = std::lower_bound(first, last, val, value_comp());
+
+    if (position == last || value_comp()(val, *position)) {
+      // emplace_back might invalidate position, which is why distance needs to
+      // be cached.
+      const difference_type distance = std::distance(begin(), position);
+      body_.emplace_back(std::forward<V>(val));
+      return {std::next(begin(), distance), true};
+    }
+
+    *position = std::forward<V>(val);
+    return {position, false};
+  }
+
+  // This method is similar to insert, with the following differences:
+  // - Instead of searching [begin(), end()) it only searches [first, last).
+  // - In case no equivalent element is found, val is appended to the end of the
+  //   underlying body and an iterator to the next bigger element in [first,
+  //   last) is returned.
+  template <class V>
+  std::pair<iterator, bool> append_unique(iterator first,
+                                          iterator last,
+                                          V&& val) {
+    auto position = std::lower_bound(first, last, val, value_comp());
+
+    if (position == last || value_comp()(val, *position)) {
+      // emplace_back might invalidate position, which is why distance needs to
+      // be cached.
+      const difference_type distance = std::distance(begin(), position);
+      body_.emplace_back(std::forward<V>(val));
+      return {std::next(begin(), distance), true};
+    }
+
+    return {position, false};
+  }
+
+  void sort_and_unique(iterator first, iterator last) {
+    // Preserve stability for the unique code below.
+    std::stable_sort(first, last, value_comp());
+
+    // lhs is already <= rhs due to sort, therefore !(lhs < rhs) <=> lhs == rhs.
+    auto equal_comp = webrtc::not_fn(value_comp());
+    erase(std::unique(first, last, equal_comp), last);
+  }
+
+  void sort_and_unique() { sort_and_unique(begin(), end()); }
+
+  // To support comparators that may not be possible to default-construct, we
+  // have to store an instance of Compare. Since Compare commonly is stateless,
+  // we use the RTC_NO_UNIQUE_ADDRESS attribute to save space.
+  RTC_NO_UNIQUE_ADDRESS key_compare comp_;
+  // Declare after |key_compare_comp_| to workaround GCC ICE. For details
+  // see https://crbug.com/1156268
+  container_type body_;
+
+  // If the compare is not transparent we want to construct key_type once.
+  template <typename K>
+  using KeyTypeOrK = typename std::
+      conditional<IsTransparentCompare<key_compare>::value, K, key_type>::type;
+};
+
+// ----------------------------------------------------------------------------
+// Lifetime.
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
+    const KeyCompare& comp)
+    : comp_(comp) {}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <class InputIterator>
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
+    InputIterator first,
+    InputIterator last,
+    const KeyCompare& comp)
+    : comp_(comp), body_(first, last) {
+  sort_and_unique();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
+    const container_type& items,
+    const KeyCompare& comp)
+    : comp_(comp), body_(items) {
+  sort_and_unique();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
+    container_type&& items,
+    const KeyCompare& comp)
+    : comp_(comp), body_(std::move(items)) {
+  sort_and_unique();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
+    std::initializer_list<value_type> ilist,
+    const KeyCompare& comp)
+    : flat_tree(std::begin(ilist), std::end(ilist), comp) {}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <class InputIterator>
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
+    sorted_unique_t,
+    InputIterator first,
+    InputIterator last,
+    const KeyCompare& comp)
+    : comp_(comp), body_(first, last) {
+  RTC_DCHECK(is_sorted_and_unique(*this, value_comp()));
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
+    sorted_unique_t,
+    const container_type& items,
+    const KeyCompare& comp)
+    : comp_(comp), body_(items) {
+  RTC_DCHECK(is_sorted_and_unique(*this, value_comp()));
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+constexpr flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
+    sorted_unique_t,
+    container_type&& items,
+    const KeyCompare& comp)
+    : comp_(comp), body_(std::move(items)) {
+  RTC_DCHECK(is_sorted_and_unique(*this, value_comp()));
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
+    sorted_unique_t,
+    std::initializer_list<value_type> ilist,
+    const KeyCompare& comp)
+    : flat_tree(sorted_unique, std::begin(ilist), std::end(ilist), comp) {}
+
+// ----------------------------------------------------------------------------
+// Assignments.
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::operator=(
+    std::initializer_list<value_type> ilist) -> flat_tree& {
+  body_ = ilist;
+  sort_and_unique();
+  return *this;
+}
+
+// ----------------------------------------------------------------------------
+// Memory management.
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::reserve(
+    size_type new_capacity) {
+  body_.reserve(new_capacity);
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::capacity() const
+    -> size_type {
+  return body_.capacity();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::shrink_to_fit() {
+  body_.shrink_to_fit();
+}
+
+// ----------------------------------------------------------------------------
+// Size management.
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::clear() {
+  body_.clear();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::size()
+    const -> size_type {
+  return body_.size();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+constexpr auto
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::max_size() const
+    -> size_type {
+  return body_.max_size();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+constexpr bool flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::empty()
+    const {
+  return body_.empty();
+}
+
+// ----------------------------------------------------------------------------
+// Iterators.
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::begin()
+    -> iterator {
+  return body_.begin();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::begin()
+    const -> const_iterator {
+  return std::begin(body_);
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::cbegin() const
+    -> const_iterator {
+  return body_.cbegin();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::end() -> iterator {
+  return body_.end();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::end()
+    const -> const_iterator {
+  return std::end(body_);
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::cend() const
+    -> const_iterator {
+  return body_.cend();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rbegin()
+    -> reverse_iterator {
+  return body_.rbegin();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rbegin() const
+    -> const_reverse_iterator {
+  return body_.rbegin();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::crbegin() const
+    -> const_reverse_iterator {
+  return body_.crbegin();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rend()
+    -> reverse_iterator {
+  return body_.rend();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rend() const
+    -> const_reverse_iterator {
+  return body_.rend();
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::crend() const
+    -> const_reverse_iterator {
+  return body_.crend();
+}
+
+// ----------------------------------------------------------------------------
+// Insert operations.
+//
+// Currently we use position_hint the same way as eastl or boost:
+// https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set.h#L493
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
+    const value_type& val) -> std::pair<iterator, bool> {
+  return emplace_key_args(GetKeyFromValue()(val), val);
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
+    value_type&& val) -> std::pair<iterator, bool> {
+  return emplace_key_args(GetKeyFromValue()(val), std::move(val));
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
+    const_iterator position_hint,
+    const value_type& val) -> iterator {
+  return emplace_hint_key_args(position_hint, GetKeyFromValue()(val), val)
+      .first;
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
+    const_iterator position_hint,
+    value_type&& val) -> iterator {
+  return emplace_hint_key_args(position_hint, GetKeyFromValue()(val),
+                               std::move(val))
+      .first;
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <class InputIterator>
+void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
+    InputIterator first,
+    InputIterator last) {
+  if (first == last)
+    return;
+
+  // Dispatch to single element insert if the input range contains a single
+  // element.
+  if (is_multipass<InputIterator>() && std::next(first) == last) {
+    insert(end(), *first);
+    return;
+  }
+
+  // Provide a convenience lambda to obtain an iterator pointing past the last
+  // old element. This needs to be dymanic due to possible re-allocations.
+  auto middle = [this, size = size()] { return std::next(begin(), size); };
+
+  // For batch updates initialize the first insertion point.
+  difference_type pos_first_new = size();
+
+  // Loop over the input range while appending new values and overwriting
+  // existing ones, if applicable. Keep track of the first insertion point.
+  for (; first != last; ++first) {
+    std::pair<iterator, bool> result = append_unique(begin(), middle(), *first);
+    if (result.second) {
+      pos_first_new =
+          std::min(pos_first_new, std::distance(begin(), result.first));
+    }
+  }
+
+  // The new elements might be unordered and contain duplicates, so post-process
+  // the just inserted elements and merge them with the rest, inserting them at
+  // the previously found spot.
+  sort_and_unique(middle(), end());
+  std::inplace_merge(std::next(begin(), pos_first_new), middle(), end(),
+                     value_comp());
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <class... Args>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace(
+    Args&&... args) -> std::pair<iterator, bool> {
+  return insert(value_type(std::forward<Args>(args)...));
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <class... Args>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace_hint(
+    const_iterator position_hint,
+    Args&&... args) -> iterator {
+  return insert(position_hint, value_type(std::forward<Args>(args)...));
+}
+
+// ----------------------------------------------------------------------------
+// Underlying type operations.
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::
+    extract() && -> container_type {
+  return std::exchange(body_, container_type());
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::replace(
+    container_type&& body) {
+  // Ensure that `body` is sorted and has no repeated elements according to
+  // `value_comp()`.
+  RTC_DCHECK(is_sorted_and_unique(body, value_comp()));
+  body_ = std::move(body);
+}
+
+// ----------------------------------------------------------------------------
+// Erase operations.
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(
+    iterator position) -> iterator {
+  RTC_CHECK(position != body_.end());
+  return body_.erase(position);
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename DummyT>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(
+    const_iterator position) -> iterator {
+  RTC_CHECK(position != body_.end());
+  return body_.erase(position);
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(const K& val)
+    -> size_type {
+  auto eq_range = equal_range(val);
+  auto res = std::distance(eq_range.first, eq_range.second);
+  erase(eq_range.first, eq_range.second);
+  return res;
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(
+    const_iterator first,
+    const_iterator last) -> iterator {
+  return body_.erase(first, last);
+}
+
+// ----------------------------------------------------------------------------
+// Comparators.
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+constexpr auto
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::key_comp() const
+    -> key_compare {
+  return comp_;
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+constexpr auto
+flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::value_comp() const
+    -> value_compare {
+  return value_compare{comp_};
+}
+
+// ----------------------------------------------------------------------------
+// Search operations.
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::count(
+    const K& key) const -> size_type {
+  auto eq_range = equal_range(key);
+  return std::distance(eq_range.first, eq_range.second);
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(const K& key)
+    -> iterator {
+  return const_cast_it(webrtc::as_const(*this).find(key));
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(
+    const K& key) const -> const_iterator {
+  auto eq_range = equal_range(key);
+  return (eq_range.first == eq_range.second) ? end() : eq_range.first;
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+bool flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::contains(
+    const K& key) const {
+  auto lower = lower_bound(key);
+  return lower != end() && !comp_(key, GetKeyFromValue()(*lower));
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range(
+    const K& key) -> std::pair<iterator, iterator> {
+  auto res = webrtc::as_const(*this).equal_range(key);
+  return {const_cast_it(res.first), const_cast_it(res.second)};
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range(
+    const K& key) const -> std::pair<const_iterator, const_iterator> {
+  auto lower = lower_bound(key);
+
+  KeyValueCompare comp(comp_);
+  if (lower == end() || comp(key, *lower))
+    return {lower, lower};
+
+  return {lower, std::next(lower)};
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::lower_bound(
+    const K& key) -> iterator {
+  return const_cast_it(webrtc::as_const(*this).lower_bound(key));
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::lower_bound(
+    const K& key) const -> const_iterator {
+  static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value,
+                "Requested type cannot be bound to the container's key_type "
+                "which is required for a non-transparent compare.");
+
+  const KeyTypeOrK<K>& key_ref = key;
+
+  KeyValueCompare comp(comp_);
+  return absl::c_lower_bound(*this, key_ref, comp);
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::upper_bound(
+    const K& key) -> iterator {
+  return const_cast_it(webrtc::as_const(*this).upper_bound(key));
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <typename K>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::upper_bound(
+    const K& key) const -> const_iterator {
+  static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value,
+                "Requested type cannot be bound to the container's key_type "
+                "which is required for a non-transparent compare.");
+
+  const KeyTypeOrK<K>& key_ref = key;
+
+  KeyValueCompare comp(comp_);
+  return absl::c_upper_bound(*this, key_ref, comp);
+}
+
+// ----------------------------------------------------------------------------
+// General operations.
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::swap(
+    flat_tree& other) noexcept {
+  std::swap(*this, other);
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <class... Args>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::unsafe_emplace(
+    const_iterator position,
+    Args&&... args) -> iterator {
+  return body_.emplace(position, std::forward<Args>(args)...);
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <class K, class... Args>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace_key_args(
+    const K& key,
+    Args&&... args) -> std::pair<iterator, bool> {
+  auto lower = lower_bound(key);
+  if (lower == end() || comp_(key, GetKeyFromValue()(*lower)))
+    return {unsafe_emplace(lower, std::forward<Args>(args)...), true};
+  return {lower, false};
+}
+
+template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
+template <class K, class... Args>
+auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::
+    emplace_hint_key_args(const_iterator hint, const K& key, Args&&... args)
+        -> std::pair<iterator, bool> {
+  KeyValueCompare comp(comp_);
+  if ((hint == begin() || comp(*std::prev(hint), key))) {
+    if (hint == end() || comp(key, *hint)) {
+      // *(hint - 1) < key < *hint => key did not exist and hint is correct.
+      return {unsafe_emplace(hint, std::forward<Args>(args)...), true};
+    }
+    if (!comp(*hint, key)) {
+      // key == *hint => no-op, return correct hint.
+      return {const_cast_it(hint), false};
+    }
+  }
+  // hint was not helpful, dispatch to hintless version.
+  return emplace_key_args(key, std::forward<Args>(args)...);
+}
+
+}  // namespace flat_containers_internal
+
+// ----------------------------------------------------------------------------
+// Free functions.
+
+// Erases all elements that match predicate. It has O(size) complexity.
+template <class Key,
+          class GetKeyFromValue,
+          class KeyCompare,
+          class Container,
+          typename Predicate>
+size_t EraseIf(
+    webrtc::flat_containers_internal::
+        flat_tree<Key, GetKeyFromValue, KeyCompare, Container>& container,
+    Predicate pred) {
+  auto it = std::remove_if(container.begin(), container.end(), pred);
+  size_t removed = std::distance(it, container.end());
+  container.erase(it, container.end());
+  return removed;
+}
+
+}  // namespace webrtc
+
+#endif  // RTC_BASE_CONTAINERS_FLAT_TREE_H_
diff --git a/rtc_base/containers/flat_tree_unittest.cc b/rtc_base/containers/flat_tree_unittest.cc
new file mode 100644
index 0000000..9bb803d
--- /dev/null
+++ b/rtc_base/containers/flat_tree_unittest.cc
@@ -0,0 +1,1484 @@
+/*
+ *  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_tree.h"
+
+// Following tests are ported and extended tests from libcpp for std::set.
+// They can be found here:
+// https://github.com/llvm/llvm-project/tree/main/libcxx/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.
+//   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 <array>
+#include <deque>
+#include <forward_list>
+#include <functional>
+#include <iterator>
+#include <list>
+#include <string>
+#include <vector>
+
+#include "rtc_base/containers/identity.h"
+#include "rtc_base/containers/move_only_int.h"
+#include "test/gmock.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace flat_containers_internal {
+namespace {
+
+template <class It>
+class InputIterator {
+ public:
+  using iterator_category = std::input_iterator_tag;
+  using value_type = typename std::iterator_traits<It>::value_type;
+  using difference_type = typename std::iterator_traits<It>::difference_type;
+  using pointer = It;
+  using reference = typename std::iterator_traits<It>::reference;
+
+  InputIterator() : it_() {}
+  explicit InputIterator(It it) : it_(it) {}
+
+  reference operator*() const { return *it_; }
+  pointer operator->() const { return it_; }
+
+  InputIterator& operator++() {
+    ++it_;
+    return *this;
+  }
+  InputIterator operator++(int) {
+    InputIterator tmp(*this);
+    ++(*this);
+    return tmp;
+  }
+
+  friend bool operator==(const InputIterator& lhs, const InputIterator& rhs) {
+    return lhs.it_ == rhs.it_;
+  }
+  friend bool operator!=(const InputIterator& lhs, const InputIterator& rhs) {
+    return !(lhs == rhs);
+  }
+
+ private:
+  It it_;
+};
+
+template <typename It>
+InputIterator<It> MakeInputIterator(It it) {
+  return InputIterator<It>(it);
+}
+
+class Emplaceable {
+ public:
+  Emplaceable() : Emplaceable(0, 0.0) {}
+  Emplaceable(int i, double d) : int_(i), double_(d) {}
+  Emplaceable(Emplaceable&& other) : int_(other.int_), double_(other.double_) {
+    other.int_ = 0;
+    other.double_ = 0.0;
+  }
+  Emplaceable(const Emplaceable&) = delete;
+  Emplaceable& operator=(const Emplaceable&) = delete;
+
+  Emplaceable& operator=(Emplaceable&& other) {
+    int_ = other.int_;
+    other.int_ = 0;
+    double_ = other.double_;
+    other.double_ = 0.0;
+    return *this;
+  }
+
+  friend bool operator==(const Emplaceable& lhs, const Emplaceable& rhs) {
+    return std::tie(lhs.int_, lhs.double_) == std::tie(rhs.int_, rhs.double_);
+  }
+
+  friend bool operator<(const Emplaceable& lhs, const Emplaceable& rhs) {
+    return std::tie(lhs.int_, lhs.double_) < std::tie(rhs.int_, rhs.double_);
+  }
+
+ private:
+  int int_;
+  double double_;
+};
+
+struct TemplateConstructor {
+  template <typename T>
+  explicit 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.
+template <typename ContainerT>
+using TypedTree = flat_tree<typename ContainerT::value_type,
+                            identity,
+                            std::less<>,
+                            ContainerT>;
+using IntTree = TypedTree<std::vector<int>>;
+using IntPair = std::pair<int, int>;
+using IntPairTree =
+    flat_tree<IntPair, identity, LessByFirst<IntPair>, std::vector<IntPair>>;
+using MoveOnlyTree =
+    flat_tree<MoveOnlyInt, identity, std::less<>, std::vector<MoveOnlyInt>>;
+using EmplaceableTree =
+    flat_tree<Emplaceable, identity, std::less<>, std::vector<Emplaceable>>;
+using ReversedTree =
+    flat_tree<int, identity, std::greater<int>, std::vector<int>>;
+
+using TreeWithStrangeCompare =
+    flat_tree<int, identity, NonDefaultConstructibleCompare, std::vector<int>>;
+
+using ::testing::ElementsAre;
+using ::testing::IsEmpty;
+
+template <typename T>
+class FlatTreeTest : public testing::Test {};
+TYPED_TEST_SUITE_P(FlatTreeTest);
+
+TEST(FlatTree, IsMultipass) {
+  static_assert(!is_multipass<std::istream_iterator<int>>(),
+                "InputIterator is not multipass");
+  static_assert(!is_multipass<std::ostream_iterator<int>>(),
+                "OutputIterator is not multipass");
+
+  static_assert(is_multipass<std::forward_list<int>::iterator>(),
+                "ForwardIterator is multipass");
+  static_assert(is_multipass<std::list<int>::iterator>(),
+                "BidirectionalIterator is multipass");
+  static_assert(is_multipass<std::vector<int>::iterator>(),
+                "RandomAccessIterator is multipass");
+}
+
+// Tests that the compiler generated move operators propagrate noexcept
+// specifiers.
+TEST(FlatTree, NoExcept) {
+  struct MoveThrows {
+    MoveThrows(MoveThrows&&) noexcept(false) {}
+    MoveThrows& operator=(MoveThrows&&) noexcept(false) { return *this; }
+  };
+
+  using MoveThrowsTree =
+      flat_tree<MoveThrows, identity, std::less<>, std::array<MoveThrows, 1>>;
+
+  static_assert(std::is_nothrow_move_constructible<IntTree>::value,
+                "Error: IntTree is not nothrow move constructible");
+  static_assert(std::is_nothrow_move_assignable<IntTree>::value,
+                "Error: IntTree is not nothrow move assignable");
+
+  static_assert(!std::is_nothrow_move_constructible<MoveThrowsTree>::value,
+                "Error: MoveThrowsTree is nothrow move constructible");
+  static_assert(!std::is_nothrow_move_assignable<MoveThrowsTree>::value,
+                "Error: MoveThrowsTree is nothrow move assignable");
+}
+
+// ----------------------------------------------------------------------------
+// Class.
+
+// Check that flat_tree and its iterators can be instantiated with an
+// incomplete type.
+
+TEST(FlatTree, IncompleteType) {
+  struct A {
+    using Tree = flat_tree<A, identity, std::less<A>, std::vector<A>>;
+    int data;
+    Tree set_with_incomplete_type;
+    Tree::iterator it;
+    Tree::const_iterator cit;
+
+    // We do not declare operator< because clang complains that it's unused.
+  };
+
+  A a;
+}
+
+TEST(FlatTree, Stability) {
+  using Pair = std::pair<int, int>;
+
+  using Tree = flat_tree<Pair, identity, LessByFirst<Pair>, std::vector<Pair>>;
+
+  // Constructors are stable.
+  Tree cont({{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}});
+
+  auto AllOfSecondsAreZero = [&cont] {
+    return absl::c_all_of(cont,
+                          [](const Pair& elem) { return elem.second == 0; });
+  };
+
+  EXPECT_TRUE(AllOfSecondsAreZero()) << "constructor should be stable";
+
+  // Should not replace existing.
+  cont.insert(Pair(0, 2));
+  cont.insert(Pair(1, 2));
+  cont.insert(Pair(2, 2));
+
+  EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
+
+  cont.insert(Pair(3, 0));
+  cont.insert(Pair(3, 2));
+
+  EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
+}
+
+// ----------------------------------------------------------------------------
+// Types.
+
+// key_type
+// key_compare
+// value_type
+// value_compare
+// pointer
+// const_pointer
+// reference
+// const_reference
+// size_type
+// difference_type
+// iterator
+// const_iterator
+// reverse_iterator
+// const_reverse_iterator
+
+TEST(FlatTree, Types) {
+  // These are guaranteed to be portable.
+  static_assert((std::is_same<int, IntTree::key_type>::value), "");
+  static_assert((std::is_same<int, IntTree::value_type>::value), "");
+  static_assert((std::is_same<std::less<>, IntTree::key_compare>::value), "");
+  static_assert((std::is_same<int&, IntTree::reference>::value), "");
+  static_assert((std::is_same<const int&, IntTree::const_reference>::value),
+                "");
+  static_assert((std::is_same<int*, IntTree::pointer>::value), "");
+  static_assert((std::is_same<const int*, IntTree::const_pointer>::value), "");
+}
+
+// ----------------------------------------------------------------------------
+// Lifetime.
+
+// flat_tree()
+// flat_tree(const Compare& comp)
+
+TYPED_TEST_P(FlatTreeTest, DefaultConstructor) {
+  {
+    TypedTree<TypeParam> cont;
+    EXPECT_THAT(cont, ElementsAre());
+  }
+
+  {
+    TreeWithStrangeCompare cont(NonDefaultConstructibleCompare(0));
+    EXPECT_THAT(cont, ElementsAre());
+  }
+}
+
+// flat_tree(const flat_tree& x)
+
+TYPED_TEST_P(FlatTreeTest, CopyConstructor) {
+  TypedTree<TypeParam> original({1, 2, 3, 4});
+  TypedTree<TypeParam> copied(original);
+
+  EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
+
+  EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
+  EXPECT_THAT(original, ElementsAre(1, 2, 3, 4));
+  EXPECT_EQ(original, copied);
+}
+
+// flat_tree(flat_tree&& x)
+
+TEST(FlatTree, MoveConstructor) {
+  int input_range[] = {1, 2, 3, 4};
+
+  MoveOnlyTree original(std::begin(input_range), std::end(input_range));
+  MoveOnlyTree 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)));
+}
+
+// flat_tree(InputIterator first,
+//           InputIterator last,
+//           const Compare& comp = Compare())
+
+TEST(FlatTree, RangeConstructor) {
+  {
+    IntPair input_vals[] = {{1, 1}, {1, 2}, {2, 1}, {2, 2}, {1, 3},
+                            {2, 3}, {3, 1}, {3, 2}, {3, 3}};
+
+    IntPairTree first_of(MakeInputIterator(std::begin(input_vals)),
+                         MakeInputIterator(std::end(input_vals)));
+    EXPECT_THAT(first_of,
+                ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1)));
+  }
+  {
+    TreeWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2,
+                                                       2, 3, 3, 3};
+
+    TreeWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)),
+                                MakeInputIterator(std::end(input_vals)),
+                                NonDefaultConstructibleCompare(0));
+    EXPECT_THAT(cont, ElementsAre(1, 2, 3));
+  }
+}
+
+// flat_tree(const container_type&)
+
+TYPED_TEST_P(FlatTreeTest, ContainerCopyConstructor) {
+  TypeParam items = {1, 2, 3, 4};
+  TypedTree<TypeParam> tree(items);
+
+  EXPECT_THAT(tree, ElementsAre(1, 2, 3, 4));
+  EXPECT_THAT(items, ElementsAre(1, 2, 3, 4));
+}
+
+// flat_tree(container_type&&)
+
+TEST(FlatTree, ContainerMoveConstructor) {
+  using Pair = std::pair<int, MoveOnlyInt>;
+
+  // Construct an unsorted vector with a duplicate item in it. Sorted by the
+  // first item, the second allows us to test for stability. Using a move
+  // only type to ensure the vector is not copied.
+  std::vector<Pair> storage;
+  storage.push_back(Pair(2, MoveOnlyInt(0)));
+  storage.push_back(Pair(1, MoveOnlyInt(0)));
+  storage.push_back(Pair(2, MoveOnlyInt(1)));
+
+  using Tree = flat_tree<Pair, identity, LessByFirst<Pair>, std::vector<Pair>>;
+  Tree tree(std::move(storage));
+
+  // The list should be two items long, with only the first "2" saved.
+  ASSERT_EQ(2u, tree.size());
+  const Pair& zeroth = *tree.begin();
+  ASSERT_EQ(1, zeroth.first);
+  ASSERT_EQ(0, zeroth.second.data());
+
+  const Pair& first = *(tree.begin() + 1);
+  ASSERT_EQ(2, first.first);
+  ASSERT_EQ(0, first.second.data());
+}
+
+// flat_tree(std::initializer_list<value_type> ilist,
+//           const Compare& comp = Compare())
+
+TYPED_TEST_P(FlatTreeTest, InitializerListConstructor) {
+  {
+    TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 10, 8});
+    EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
+  }
+  {
+    TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 10, 8});
+    EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
+  }
+  {
+    TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8},
+                                NonDefaultConstructibleCompare(0));
+    EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
+  }
+  {
+    IntPairTree first_of({{1, 1}, {2, 1}, {1, 2}});
+    EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
+  }
+}
+
+// flat_tree(sorted_unique_t,
+//           InputIterator first,
+//           InputIterator last,
+//           const Compare& comp = Compare())
+
+TEST(FlatTree, SortedUniqueRangeConstructor) {
+  {
+    IntPair input_vals[] = {{1, 1}, {2, 1}, {3, 1}};
+
+    IntPairTree first_of(sorted_unique,
+                         MakeInputIterator(std::begin(input_vals)),
+                         MakeInputIterator(std::end(input_vals)));
+    EXPECT_THAT(first_of,
+                ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1)));
+  }
+  {
+    TreeWithStrangeCompare::value_type input_vals[] = {1, 2, 3};
+
+    TreeWithStrangeCompare cont(sorted_unique,
+                                MakeInputIterator(std::begin(input_vals)),
+                                MakeInputIterator(std::end(input_vals)),
+                                NonDefaultConstructibleCompare(0));
+    EXPECT_THAT(cont, ElementsAre(1, 2, 3));
+  }
+}
+
+// flat_tree(sorted_unique_t, const container_type&)
+
+TYPED_TEST_P(FlatTreeTest, SortedUniqueContainerCopyConstructor) {
+  TypeParam items = {1, 2, 3, 4};
+  TypedTree<TypeParam> tree(sorted_unique, items);
+
+  EXPECT_THAT(tree, ElementsAre(1, 2, 3, 4));
+  EXPECT_THAT(items, ElementsAre(1, 2, 3, 4));
+}
+
+// flat_tree(sorted_unique_t, std::vector<value_type>&&)
+
+TEST(FlatTree, SortedUniqueVectorMoveConstructor) {
+  using Pair = std::pair<int, MoveOnlyInt>;
+
+  std::vector<Pair> storage;
+  storage.push_back(Pair(1, MoveOnlyInt(0)));
+  storage.push_back(Pair(2, MoveOnlyInt(0)));
+
+  using Tree = flat_tree<Pair, identity, LessByFirst<Pair>, std::vector<Pair>>;
+  Tree tree(sorted_unique, std::move(storage));
+
+  ASSERT_EQ(2u, tree.size());
+  const Pair& zeroth = *tree.begin();
+  ASSERT_EQ(1, zeroth.first);
+  ASSERT_EQ(0, zeroth.second.data());
+
+  const Pair& first = *(tree.begin() + 1);
+  ASSERT_EQ(2, first.first);
+  ASSERT_EQ(0, first.second.data());
+}
+
+// flat_tree(sorted_unique_t,
+//           std::initializer_list<value_type> ilist,
+//           const Compare& comp = Compare())
+
+TYPED_TEST_P(FlatTreeTest, SortedUniqueInitializerListConstructor) {
+  {
+    TypedTree<TypeParam> cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10});
+    EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
+  }
+  {
+    TypedTree<TypeParam> cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10});
+    EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
+  }
+  {
+    TreeWithStrangeCompare cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10},
+                                NonDefaultConstructibleCompare(0));
+    EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
+  }
+  {
+    IntPairTree first_of(sorted_unique, {{1, 1}, {2, 1}});
+    EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
+  }
+}
+
+// ----------------------------------------------------------------------------
+// Assignments.
+
+// flat_tree& operator=(const flat_tree&)
+
+TYPED_TEST_P(FlatTreeTest, CopyAssignable) {
+  TypedTree<TypeParam> original({1, 2, 3, 4});
+  TypedTree<TypeParam> copied;
+  copied = original;
+
+  EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
+  EXPECT_THAT(original, ElementsAre(1, 2, 3, 4));
+  EXPECT_EQ(original, copied);
+}
+
+// flat_tree& operator=(flat_tree&&)
+
+TEST(FlatTree, MoveAssignable) {
+  int input_range[] = {1, 2, 3, 4};
+
+  MoveOnlyTree original(std::begin(input_range), std::end(input_range));
+  MoveOnlyTree moved;
+  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)));
+}
+
+// flat_tree& operator=(std::initializer_list<value_type> ilist)
+
+TYPED_TEST_P(FlatTreeTest, InitializerListAssignable) {
+  TypedTree<TypeParam> cont({0});
+  cont = {1, 2, 3, 4, 5, 6, 10, 8};
+
+  EXPECT_EQ(0U, cont.count(0));
+  EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
+}
+
+// --------------------------------------------------------------------------
+// Memory management.
+
+// void reserve(size_type new_capacity)
+
+TEST(FlatTreeTest, Reserve) {
+  IntTree cont({1, 2, 3});
+
+  cont.reserve(5);
+  EXPECT_LE(5U, cont.capacity());
+}
+
+// size_type capacity() const
+
+TEST(FlatTreeTest, Capacity) {
+  IntTree cont({1, 2, 3});
+
+  EXPECT_LE(cont.size(), cont.capacity());
+  cont.reserve(5);
+  EXPECT_LE(cont.size(), cont.capacity());
+}
+
+// void shrink_to_fit()
+
+TEST(FlatTreeTest, ShrinkToFit) {
+  IntTree cont({1, 2, 3});
+
+  IntTree::size_type capacity_before = cont.capacity();
+  cont.shrink_to_fit();
+  EXPECT_GE(capacity_before, cont.capacity());
+}
+
+// ----------------------------------------------------------------------------
+// Size management.
+
+// void clear()
+
+TYPED_TEST_P(FlatTreeTest, Clear) {
+  TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
+  cont.clear();
+  EXPECT_THAT(cont, ElementsAre());
+}
+
+// size_type size() const
+
+TYPED_TEST_P(FlatTreeTest, Size) {
+  TypedTree<TypeParam> cont;
+
+  EXPECT_EQ(0U, cont.size());
+  cont.insert(2);
+  EXPECT_EQ(1U, cont.size());
+  cont.insert(1);
+  EXPECT_EQ(2U, cont.size());
+  cont.insert(3);
+  EXPECT_EQ(3U, cont.size());
+  cont.erase(cont.begin());
+  EXPECT_EQ(2U, cont.size());
+  cont.erase(cont.begin());
+  EXPECT_EQ(1U, cont.size());
+  cont.erase(cont.begin());
+  EXPECT_EQ(0U, cont.size());
+}
+
+// bool empty() const
+
+TYPED_TEST_P(FlatTreeTest, Empty) {
+  TypedTree<TypeParam> cont;
+
+  EXPECT_TRUE(cont.empty());
+  cont.insert(1);
+  EXPECT_FALSE(cont.empty());
+  cont.clear();
+  EXPECT_TRUE(cont.empty());
+}
+
+// ----------------------------------------------------------------------------
+// Iterators.
+
+// iterator begin()
+// const_iterator begin() const
+// iterator end()
+// const_iterator end() const
+//
+// reverse_iterator rbegin()
+// const_reverse_iterator rbegin() const
+// reverse_iterator rend()
+// const_reverse_iterator rend() const
+//
+// const_iterator cbegin() const
+// const_iterator cend() const
+// const_reverse_iterator crbegin() const
+// const_reverse_iterator crend() const
+
+TYPED_TEST_P(FlatTreeTest, Iterators) {
+  TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
+
+  auto size =
+      static_cast<typename TypedTree<TypeParam>::difference_type>(cont.size());
+
+  EXPECT_EQ(size, std::distance(cont.begin(), cont.end()));
+  EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend()));
+  EXPECT_EQ(size, std::distance(cont.rbegin(), cont.rend()));
+  EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend()));
+
+  {
+    auto it = cont.begin();
+    auto c_it = cont.cbegin();
+    EXPECT_EQ(it, c_it);
+    for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) {
+      EXPECT_EQ(j, *it);
+      EXPECT_EQ(j, *c_it);
+    }
+  }
+  {
+    auto rit = cont.rbegin();
+    auto c_rit = cont.crbegin();
+    EXPECT_EQ(rit, c_rit);
+    for (int j = static_cast<int>(size); rit != cont.rend();
+         ++rit, ++c_rit, --j) {
+      EXPECT_EQ(j, *rit);
+      EXPECT_EQ(j, *c_rit);
+    }
+  }
+}
+
+// ----------------------------------------------------------------------------
+// Insert operations.
+
+// pair<iterator, bool> insert(const value_type& val)
+
+TYPED_TEST_P(FlatTreeTest, InsertLValue) {
+  TypedTree<TypeParam> cont;
+
+  int value = 2;
+  std::pair<typename TypedTree<TypeParam>::iterator, bool> result =
+      cont.insert(value);
+  EXPECT_TRUE(result.second);
+  EXPECT_EQ(cont.begin(), result.first);
+  EXPECT_EQ(1U, cont.size());
+  EXPECT_EQ(2, *result.first);
+
+  value = 1;
+  result = cont.insert(value);
+  EXPECT_TRUE(result.second);
+  EXPECT_EQ(cont.begin(), result.first);
+  EXPECT_EQ(2U, cont.size());
+  EXPECT_EQ(1, *result.first);
+
+  value = 3;
+  result = cont.insert(value);
+  EXPECT_TRUE(result.second);
+  EXPECT_EQ(std::prev(cont.end()), result.first);
+  EXPECT_EQ(3U, cont.size());
+  EXPECT_EQ(3, *result.first);
+
+  value = 3;
+  result = cont.insert(value);
+  EXPECT_FALSE(result.second);
+  EXPECT_EQ(std::prev(cont.end()), result.first);
+  EXPECT_EQ(3U, cont.size());
+  EXPECT_EQ(3, *result.first);
+}
+
+// pair<iterator, bool> insert(value_type&& val)
+
+TEST(FlatTree, InsertRValue) {
+  MoveOnlyTree cont;
+
+  std::pair<MoveOnlyTree::iterator, bool> result = cont.insert(MoveOnlyInt(2));
+  EXPECT_TRUE(result.second);
+  EXPECT_EQ(cont.begin(), result.first);
+  EXPECT_EQ(1U, cont.size());
+  EXPECT_EQ(2, result.first->data());
+
+  result = cont.insert(MoveOnlyInt(1));
+  EXPECT_TRUE(result.second);
+  EXPECT_EQ(cont.begin(), result.first);
+  EXPECT_EQ(2U, cont.size());
+  EXPECT_EQ(1, result.first->data());
+
+  result = cont.insert(MoveOnlyInt(3));
+  EXPECT_TRUE(result.second);
+  EXPECT_EQ(std::prev(cont.end()), result.first);
+  EXPECT_EQ(3U, cont.size());
+  EXPECT_EQ(3, result.first->data());
+
+  result = cont.insert(MoveOnlyInt(3));
+  EXPECT_FALSE(result.second);
+  EXPECT_EQ(std::prev(cont.end()), result.first);
+  EXPECT_EQ(3U, cont.size());
+  EXPECT_EQ(3, result.first->data());
+}
+
+// iterator insert(const_iterator position_hint, const value_type& val)
+
+TYPED_TEST_P(FlatTreeTest, InsertPositionLValue) {
+  TypedTree<TypeParam> cont;
+
+  auto result = cont.insert(cont.cend(), 2);
+  EXPECT_EQ(cont.begin(), result);
+  EXPECT_EQ(1U, cont.size());
+  EXPECT_EQ(2, *result);
+
+  result = cont.insert(cont.cend(), 1);
+  EXPECT_EQ(cont.begin(), result);
+  EXPECT_EQ(2U, cont.size());
+  EXPECT_EQ(1, *result);
+
+  result = cont.insert(cont.cend(), 3);
+  EXPECT_EQ(std::prev(cont.end()), result);
+  EXPECT_EQ(3U, cont.size());
+  EXPECT_EQ(3, *result);
+
+  result = cont.insert(cont.cend(), 3);
+  EXPECT_EQ(std::prev(cont.end()), result);
+  EXPECT_EQ(3U, cont.size());
+  EXPECT_EQ(3, *result);
+}
+
+// iterator insert(const_iterator position_hint, value_type&& val)
+
+TEST(FlatTree, InsertPositionRValue) {
+  MoveOnlyTree cont;
+
+  auto result = cont.insert(cont.cend(), MoveOnlyInt(2));
+  EXPECT_EQ(cont.begin(), result);
+  EXPECT_EQ(1U, cont.size());
+  EXPECT_EQ(2, result->data());
+
+  result = cont.insert(cont.cend(), MoveOnlyInt(1));
+  EXPECT_EQ(cont.begin(), result);
+  EXPECT_EQ(2U, cont.size());
+  EXPECT_EQ(1, 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());
+
+  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 {
+    const int& operator()(const std::pair<int, int>& p) const {
+      return p.first;
+    }
+  };
+
+  using IntIntMap = flat_tree<int, GetKeyFromIntIntPair, std::less<int>,
+                              std::vector<IntPair>>;
+
+  {
+    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)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
+    std::vector<IntPair> int_pairs;
+    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)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
+    IntPair int_pairs[] = {{1, 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)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
+    IntPair int_pairs[] = {{5, 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(5, 1)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {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)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {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)));
+  }
+}
+
+// template <class... Args>
+// pair<iterator, bool> emplace(Args&&... args)
+
+TYPED_TEST_P(FlatTreeTest, Emplace) {
+  {
+    EmplaceableTree cont;
+
+    std::pair<EmplaceableTree::iterator, bool> result = cont.emplace();
+    EXPECT_TRUE(result.second);
+    EXPECT_EQ(cont.begin(), result.first);
+    EXPECT_EQ(1U, cont.size());
+    EXPECT_EQ(Emplaceable(), *cont.begin());
+
+    result = cont.emplace(2, 3.5);
+    EXPECT_TRUE(result.second);
+    EXPECT_EQ(std::next(cont.begin()), result.first);
+    EXPECT_EQ(2U, cont.size());
+    EXPECT_EQ(Emplaceable(2, 3.5), *result.first);
+
+    result = cont.emplace(2, 3.5);
+    EXPECT_FALSE(result.second);
+    EXPECT_EQ(std::next(cont.begin()), result.first);
+    EXPECT_EQ(2U, cont.size());
+    EXPECT_EQ(Emplaceable(2, 3.5), *result.first);
+  }
+  {
+    TypedTree<TypeParam> cont;
+
+    std::pair<typename TypedTree<TypeParam>::iterator, bool> result =
+        cont.emplace(2);
+    EXPECT_TRUE(result.second);
+    EXPECT_EQ(cont.begin(), result.first);
+    EXPECT_EQ(1U, cont.size());
+    EXPECT_EQ(2, *result.first);
+  }
+}
+
+// template <class... Args>
+// iterator emplace_hint(const_iterator position_hint, Args&&... args)
+
+TYPED_TEST_P(FlatTreeTest, EmplacePosition) {
+  {
+    EmplaceableTree cont;
+
+    auto result = cont.emplace_hint(cont.cend());
+    EXPECT_EQ(cont.begin(), result);
+    EXPECT_EQ(1U, cont.size());
+    EXPECT_EQ(Emplaceable(), *cont.begin());
+
+    result = cont.emplace_hint(cont.cend(), 2, 3.5);
+    EXPECT_EQ(std::next(cont.begin()), result);
+    EXPECT_EQ(2U, cont.size());
+    EXPECT_EQ(Emplaceable(2, 3.5), *result);
+
+    result = cont.emplace_hint(cont.cbegin(), 2, 3.5);
+    EXPECT_EQ(std::next(cont.begin()), result);
+    EXPECT_EQ(2U, cont.size());
+    EXPECT_EQ(Emplaceable(2, 3.5), *result);
+  }
+  {
+    TypedTree<TypeParam> cont;
+
+    auto result = cont.emplace_hint(cont.cend(), 2);
+    EXPECT_EQ(cont.begin(), result);
+    EXPECT_EQ(1U, cont.size());
+    EXPECT_EQ(2, *result);
+  }
+}
+
+// ----------------------------------------------------------------------------
+// Underlying type operations.
+
+// underlying_type extract() &&
+TYPED_TEST_P(FlatTreeTest, Extract) {
+  TypedTree<TypeParam> cont;
+  cont.emplace(3);
+  cont.emplace(1);
+  cont.emplace(2);
+  cont.emplace(4);
+
+  TypeParam body = std::move(cont).extract();
+  EXPECT_THAT(cont, IsEmpty());
+  EXPECT_THAT(body, ElementsAre(1, 2, 3, 4));
+}
+
+// replace(underlying_type&&)
+TYPED_TEST_P(FlatTreeTest, Replace) {
+  TypeParam body = {1, 2, 3, 4};
+  TypedTree<TypeParam> cont;
+  cont.replace(std::move(body));
+
+  EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4));
+}
+
+// ----------------------------------------------------------------------------
+// Erase operations.
+
+// iterator erase(const_iterator position_hint)
+
+TYPED_TEST_P(FlatTreeTest, ErasePosition) {
+  {
+    TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
+
+    auto 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(), 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(), 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(), 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);
+  }
+  //  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, identity, std::less<>, std::vector<T>> cont;
+    T v(0);
+
+    auto it = cont.find(v);
+    if (it != cont.end())
+      cont.erase(it);
+  }
+}
+
+// iterator erase(const_iterator first, const_iterator last)
+
+TYPED_TEST_P(FlatTreeTest, EraseRange) {
+  TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
+
+  auto it =
+      cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5));
+  EXPECT_EQ(std::next(cont.begin(), 5), it);
+  EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8));
+
+  it = cont.erase(std::next(cont.cbegin(), 3), std::next(cont.cbegin(), 4));
+  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(), 2), std::next(cont.cbegin(), 5));
+  EXPECT_EQ(std::next(cont.begin(), 2), it);
+  EXPECT_THAT(cont, ElementsAre(1, 2, 7, 8));
+
+  it = cont.erase(std::next(cont.cbegin(), 0), std::next(cont.cbegin(), 2));
+  EXPECT_EQ(std::next(cont.begin(), 0), it);
+  EXPECT_THAT(cont, ElementsAre(7, 8));
+
+  it = cont.erase(cont.cbegin(), cont.cend());
+  EXPECT_EQ(cont.begin(), it);
+  EXPECT_EQ(cont.end(), it);
+}
+
+// size_type erase(const key_type& key)
+
+TYPED_TEST_P(FlatTreeTest, EraseKey) {
+  TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
+
+  EXPECT_EQ(0U, cont.erase(9));
+  EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8));
+
+  EXPECT_EQ(1U, cont.erase(4));
+  EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
+
+  EXPECT_EQ(1U, cont.erase(1));
+  EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
+
+  EXPECT_EQ(1U, cont.erase(8));
+  EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7));
+
+  EXPECT_EQ(1U, cont.erase(3));
+  EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7));
+
+  EXPECT_EQ(1U, cont.erase(6));
+  EXPECT_THAT(cont, ElementsAre(2, 5, 7));
+
+  EXPECT_EQ(1U, cont.erase(7));
+  EXPECT_THAT(cont, ElementsAre(2, 5));
+
+  EXPECT_EQ(1U, cont.erase(2));
+  EXPECT_THAT(cont, ElementsAre(5));
+
+  EXPECT_EQ(1U, cont.erase(5));
+  EXPECT_THAT(cont, ElementsAre());
+}
+
+TYPED_TEST_P(FlatTreeTest, EraseEndDeath) {
+  {
+    TypedTree<TypeParam> tree;
+    ASSERT_DEATH_IF_SUPPORTED(tree.erase(tree.cend()), "");
+  }
+
+  {
+    TypedTree<TypeParam> tree = {1, 2, 3, 4};
+    ASSERT_DEATH_IF_SUPPORTED(tree.erase(tree.find(5)), "");
+  }
+}
+
+// ----------------------------------------------------------------------------
+// Comparators.
+
+// key_compare key_comp() const
+
+TEST(FlatTree, KeyComp) {
+  ReversedTree cont({1, 2, 3, 4, 5});
+
+  EXPECT_TRUE(absl::c_is_sorted(cont, cont.key_comp()));
+  int new_elements[] = {6, 7, 8, 9, 10};
+  std::copy(std::begin(new_elements), std::end(new_elements),
+            std::inserter(cont, cont.end()));
+  EXPECT_TRUE(absl::c_is_sorted(cont, cont.key_comp()));
+}
+
+// value_compare value_comp() const
+
+TEST(FlatTree, ValueComp) {
+  ReversedTree cont({1, 2, 3, 4, 5});
+
+  EXPECT_TRUE(absl::c_is_sorted(cont, cont.value_comp()));
+  int new_elements[] = {6, 7, 8, 9, 10};
+  std::copy(std::begin(new_elements), std::end(new_elements),
+            std::inserter(cont, cont.end()));
+  EXPECT_TRUE(absl::c_is_sorted(cont, cont.value_comp()));
+}
+
+// ----------------------------------------------------------------------------
+// Search operations.
+
+// size_type count(const key_type& key) const
+
+TYPED_TEST_P(FlatTreeTest, Count) {
+  const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12});
+
+  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
+
+TYPED_TEST_P(FlatTreeTest, Find) {
+  {
+    TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12});
+
+    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));
+  }
+  {
+    const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12});
+
+    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));
+  }
+}
+
+// bool contains(const key_type& key) const
+
+TYPED_TEST_P(FlatTreeTest, Contains) {
+  const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12});
+
+  EXPECT_TRUE(cont.contains(5));
+  EXPECT_TRUE(cont.contains(6));
+  EXPECT_TRUE(cont.contains(7));
+  EXPECT_TRUE(cont.contains(8));
+  EXPECT_TRUE(cont.contains(9));
+  EXPECT_TRUE(cont.contains(10));
+  EXPECT_TRUE(cont.contains(11));
+  EXPECT_TRUE(cont.contains(12));
+  EXPECT_FALSE(cont.contains(4));
+}
+
+// pair<iterator, iterator> equal_range(const key_type& key)
+// pair<const_iterator, const_iterator> equal_range(const key_type& key) const
+
+TYPED_TEST_P(FlatTreeTest, EqualRange) {
+  {
+    TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
+
+    std::pair<typename TypedTree<TypeParam>::iterator,
+              typename TypedTree<TypeParam>::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);
+  }
+  {
+    const TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
+
+    std::pair<typename TypedTree<TypeParam>::const_iterator,
+              typename TypedTree<TypeParam>::const_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;
+
+TYPED_TEST_P(FlatTreeTest, LowerBound) {
+  {
+    TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
+
+    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));
+  }
+  {
+    const TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
+
+    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
+
+TYPED_TEST_P(FlatTreeTest, UpperBound) {
+  {
+    TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
+
+    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));
+  }
+  {
+    const TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
+
+    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)
+
+TYPED_TEST_P(FlatTreeTest, Swap) {
+  TypedTree<TypeParam> x({1, 2, 3});
+  TypedTree<TypeParam> y({4});
+  swap(x, y);
+  EXPECT_THAT(x, ElementsAre(4));
+  EXPECT_THAT(y, ElementsAre(1, 2, 3));
+
+  y.swap(x);
+  EXPECT_THAT(x, ElementsAre(1, 2, 3));
+  EXPECT_THAT(y, ElementsAre(4));
+}
+
+// bool operator==(const flat_tree& lhs, const flat_tree& rhs)
+// bool operator!=(const flat_tree& lhs, const flat_tree& rhs)
+// bool operator<(const flat_tree& lhs, const flat_tree& rhs)
+// bool operator>(const flat_tree& lhs, const flat_tree& rhs)
+// bool operator<=(const flat_tree& lhs, const flat_tree& rhs)
+// bool operator>=(const flat_tree& lhs, const flat_tree& rhs)
+
+TEST(FlatTree, Comparison) {
+  // Provided comparator does not participate in comparison.
+  ReversedTree biggest({3});
+  ReversedTree smallest({1});
+  ReversedTree middle({1, 2});
+
+  EXPECT_EQ(biggest, biggest);
+  EXPECT_NE(biggest, smallest);
+  EXPECT_LT(smallest, middle);
+  EXPECT_LE(smallest, middle);
+  EXPECT_LE(middle, middle);
+  EXPECT_GT(biggest, middle);
+  EXPECT_GE(biggest, middle);
+  EXPECT_GE(biggest, biggest);
+}
+
+TYPED_TEST_P(FlatTreeTest, SupportsEraseIf) {
+  TypedTree<TypeParam> x;
+  EXPECT_EQ(0u, EraseIf(x, [](int) { return false; }));
+  EXPECT_THAT(x, ElementsAre());
+
+  x = {1, 2, 3};
+  EXPECT_EQ(1u, EraseIf(x, [](int elem) { return !(elem & 1); }));
+  EXPECT_THAT(x, ElementsAre(1, 3));
+
+  x = {1, 2, 3, 4};
+  EXPECT_EQ(2u, EraseIf(x, [](int elem) { return elem & 1; }));
+  EXPECT_THAT(x, ElementsAre(2, 4));
+}
+
+REGISTER_TYPED_TEST_SUITE_P(FlatTreeTest,
+                            DefaultConstructor,
+                            CopyConstructor,
+                            ContainerCopyConstructor,
+                            InitializerListConstructor,
+                            SortedUniqueContainerCopyConstructor,
+                            SortedUniqueInitializerListConstructor,
+                            CopyAssignable,
+                            InitializerListAssignable,
+                            Clear,
+                            Size,
+                            Empty,
+                            Iterators,
+                            InsertLValue,
+                            InsertPositionLValue,
+                            Emplace,
+                            EmplacePosition,
+                            Extract,
+                            Replace,
+                            ErasePosition,
+                            EraseRange,
+                            EraseKey,
+                            EraseEndDeath,
+                            Count,
+                            Find,
+                            Contains,
+                            EqualRange,
+                            LowerBound,
+                            UpperBound,
+                            Swap,
+                            SupportsEraseIf);
+
+using IntSequenceContainers =
+    ::testing::Types<std::deque<int>, std::vector<int>>;
+INSTANTIATE_TYPED_TEST_SUITE_P(My, FlatTreeTest, IntSequenceContainers);
+
+}  // namespace
+}  // namespace flat_containers_internal
+}  // namespace webrtc
diff --git a/rtc_base/containers/identity.h b/rtc_base/containers/identity.h
new file mode 100644
index 0000000..2959293
--- /dev/null
+++ b/rtc_base/containers/identity.h
@@ -0,0 +1,36 @@
+/*
+ *  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.
+
+#ifndef RTC_BASE_CONTAINERS_IDENTITY_H_
+#define RTC_BASE_CONTAINERS_IDENTITY_H_
+
+#include <utility>
+
+namespace webrtc {
+
+// Implementation of C++20's std::identity.
+//
+// Reference:
+// - https://en.cppreference.com/w/cpp/utility/functional/identity
+// - https://wg21.link/func.identity
+struct identity {
+  template <typename T>
+  constexpr T&& operator()(T&& t) const noexcept {
+    return std::forward<T>(t);
+  }
+
+  using is_transparent = void;
+};
+
+}  // namespace webrtc
+
+#endif  // RTC_BASE_CONTAINERS_IDENTITY_H_
diff --git a/rtc_base/containers/invoke.h b/rtc_base/containers/invoke.h
new file mode 100644
index 0000000..5d17a70
--- /dev/null
+++ b/rtc_base/containers/invoke.h
@@ -0,0 +1,162 @@
+/*
+ *  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.
+
+#ifndef RTC_BASE_CONTAINERS_INVOKE_H_
+#define RTC_BASE_CONTAINERS_INVOKE_H_
+
+#include <type_traits>
+#include <utility>
+
+namespace webrtc {
+
+namespace invoke_internal {
+
+// Helper struct and alias to deduce the class type from a member function
+// pointer or member object pointer.
+template <typename DecayedF>
+struct member_pointer_class {};
+
+template <typename ReturnT, typename ClassT>
+struct member_pointer_class<ReturnT ClassT::*> {
+  using type = ClassT;
+};
+
+template <typename DecayedF>
+using member_pointer_class_t = typename member_pointer_class<DecayedF>::type;
+
+// Utility struct to detect specializations of std::reference_wrapper.
+template <typename T>
+struct is_reference_wrapper : std::false_type {};
+
+template <typename T>
+struct is_reference_wrapper<std::reference_wrapper<T>> : std::true_type {};
+
+// Small helpers used below in invoke_internal::invoke to make the SFINAE more
+// concise.
+template <typename F>
+const bool& IsMemFunPtr =
+    std::is_member_function_pointer<std::decay_t<F>>::value;
+
+template <typename F>
+const bool& IsMemObjPtr = std::is_member_object_pointer<std::decay_t<F>>::value;
+
+template <typename F,
+          typename T,
+          typename MemPtrClass = member_pointer_class_t<std::decay_t<F>>>
+const bool& IsMemPtrToBaseOf =
+    std::is_base_of<MemPtrClass, std::decay_t<T>>::value;
+
+template <typename T>
+const bool& IsRefWrapper = is_reference_wrapper<std::decay_t<T>>::value;
+
+template <bool B>
+using EnableIf = std::enable_if_t<B, bool>;
+
+// Invokes a member function pointer on a reference to an object of a suitable
+// type. Covers bullet 1 of the INVOKE definition.
+//
+// Reference: https://wg21.link/func.require#1.1
+template <typename F,
+          typename T1,
+          typename... Args,
+          EnableIf<IsMemFunPtr<F> && IsMemPtrToBaseOf<F, T1>> = true>
+constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1, Args&&... args) {
+  return (std::forward<T1>(t1).*f)(std::forward<Args>(args)...);
+}
+
+// Invokes a member function pointer on a std::reference_wrapper to an object of
+// a suitable type. Covers bullet 2 of the INVOKE definition.
+//
+// Reference: https://wg21.link/func.require#1.2
+template <typename F,
+          typename T1,
+          typename... Args,
+          EnableIf<IsMemFunPtr<F> && IsRefWrapper<T1>> = true>
+constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1, Args&&... args) {
+  return (t1.get().*f)(std::forward<Args>(args)...);
+}
+
+// Invokes a member function pointer on a pointer-like type to an object of a
+// suitable type. Covers bullet 3 of the INVOKE definition.
+//
+// Reference: https://wg21.link/func.require#1.3
+template <typename F,
+          typename T1,
+          typename... Args,
+          EnableIf<IsMemFunPtr<F> && !IsMemPtrToBaseOf<F, T1> &&
+                   !IsRefWrapper<T1>> = true>
+constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1, Args&&... args) {
+  return ((*std::forward<T1>(t1)).*f)(std::forward<Args>(args)...);
+}
+
+// Invokes a member object pointer on a reference to an object of a suitable
+// type. Covers bullet 4 of the INVOKE definition.
+//
+// Reference: https://wg21.link/func.require#1.4
+template <typename F,
+          typename T1,
+          EnableIf<IsMemObjPtr<F> && IsMemPtrToBaseOf<F, T1>> = true>
+constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1) {
+  return std::forward<T1>(t1).*f;
+}
+
+// Invokes a member object pointer on a std::reference_wrapper to an object of
+// a suitable type. Covers bullet 5 of the INVOKE definition.
+//
+// Reference: https://wg21.link/func.require#1.5
+template <typename F,
+          typename T1,
+          EnableIf<IsMemObjPtr<F> && IsRefWrapper<T1>> = true>
+constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1) {
+  return t1.get().*f;
+}
+
+// Invokes a member object pointer on a pointer-like type to an object of a
+// suitable type. Covers bullet 6 of the INVOKE definition.
+//
+// Reference: https://wg21.link/func.require#1.6
+template <typename F,
+          typename T1,
+          EnableIf<IsMemObjPtr<F> && !IsMemPtrToBaseOf<F, T1> &&
+                   !IsRefWrapper<T1>> = true>
+constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1) {
+  return (*std::forward<T1>(t1)).*f;
+}
+
+// Invokes a regular function or function object. Covers bullet 7 of the INVOKE
+// definition.
+//
+// Reference: https://wg21.link/func.require#1.7
+template <typename F, typename... Args>
+constexpr decltype(auto) InvokeImpl(F&& f, Args&&... args) {
+  return std::forward<F>(f)(std::forward<Args>(args)...);
+}
+
+}  // namespace invoke_internal
+
+// Implementation of C++17's std::invoke. This is not based on implementation
+// referenced in original std::invoke proposal, but rather a manual
+// implementation, so that it can be constexpr.
+//
+// References:
+// - https://wg21.link/n4169#implementability
+// - https://en.cppreference.com/w/cpp/utility/functional/invoke
+// - https://wg21.link/func.invoke
+template <typename F, typename... Args>
+constexpr decltype(auto) invoke(F&& f, Args&&... args) {
+  return invoke_internal::InvokeImpl(std::forward<F>(f),
+                                     std::forward<Args>(args)...);
+}
+
+}  // namespace webrtc
+
+#endif  // RTC_BASE_CONTAINERS_INVOKE_H_
diff --git a/rtc_base/containers/move_only_int.h b/rtc_base/containers/move_only_int.h
new file mode 100644
index 0000000..8f745aa
--- /dev/null
+++ b/rtc_base/containers/move_only_int.h
@@ -0,0 +1,74 @@
+/*
+ *  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.
+
+#ifndef RTC_BASE_CONTAINERS_MOVE_ONLY_INT_H_
+#define RTC_BASE_CONTAINERS_MOVE_ONLY_INT_H_
+
+namespace webrtc {
+
+// A move-only class that holds an integer. This is designed for testing
+// containers. See also CopyOnlyInt.
+class MoveOnlyInt {
+ public:
+  explicit MoveOnlyInt(int data = 1) : data_(data) {}
+  MoveOnlyInt(const MoveOnlyInt& other) = delete;
+  MoveOnlyInt& operator=(const MoveOnlyInt& other) = delete;
+  MoveOnlyInt(MoveOnlyInt&& other) : data_(other.data_) { other.data_ = 0; }
+  ~MoveOnlyInt() { data_ = 0; }
+
+  MoveOnlyInt& operator=(MoveOnlyInt&& other) {
+    data_ = other.data_;
+    other.data_ = 0;
+    return *this;
+  }
+
+  friend bool operator==(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) {
+    return lhs.data_ == rhs.data_;
+  }
+
+  friend bool operator!=(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) {
+    return !operator==(lhs, rhs);
+  }
+
+  friend bool operator<(const MoveOnlyInt& lhs, int rhs) {
+    return lhs.data_ < rhs;
+  }
+
+  friend bool operator<(int lhs, const MoveOnlyInt& rhs) {
+    return lhs < rhs.data_;
+  }
+
+  friend bool operator<(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) {
+    return lhs.data_ < rhs.data_;
+  }
+
+  friend bool operator>(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) {
+    return rhs < lhs;
+  }
+
+  friend bool operator<=(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) {
+    return !(rhs < lhs);
+  }
+
+  friend bool operator>=(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) {
+    return !(lhs < rhs);
+  }
+
+  int data() const { return data_; }
+
+ private:
+  volatile int data_;
+};
+
+}  // namespace webrtc
+
+#endif  // RTC_BASE_CONTAINERS_MOVE_ONLY_INT_H_
diff --git a/rtc_base/containers/not_fn.h b/rtc_base/containers/not_fn.h
new file mode 100644
index 0000000..39cfd27
--- /dev/null
+++ b/rtc_base/containers/not_fn.h
@@ -0,0 +1,64 @@
+/*
+ *  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.
+
+#ifndef RTC_BASE_CONTAINERS_NOT_FN_H_
+#define RTC_BASE_CONTAINERS_NOT_FN_H_
+
+#include <type_traits>
+#include <utility>
+
+#include "rtc_base/containers/invoke.h"
+
+namespace webrtc {
+
+namespace not_fn_internal {
+
+template <typename F>
+struct NotFnImpl {
+  F f;
+
+  template <typename... Args>
+  constexpr decltype(auto) operator()(Args&&... args) & noexcept {
+    return !webrtc::invoke(f, std::forward<Args>(args)...);
+  }
+
+  template <typename... Args>
+  constexpr decltype(auto) operator()(Args&&... args) const& noexcept {
+    return !webrtc::invoke(f, std::forward<Args>(args)...);
+  }
+
+  template <typename... Args>
+  constexpr decltype(auto) operator()(Args&&... args) && noexcept {
+    return !webrtc::invoke(std::move(f), std::forward<Args>(args)...);
+  }
+
+  template <typename... Args>
+  constexpr decltype(auto) operator()(Args&&... args) const&& noexcept {
+    return !webrtc::invoke(std::move(f), std::forward<Args>(args)...);
+  }
+};
+
+}  // namespace not_fn_internal
+
+// Implementation of C++17's std::not_fn.
+//
+// Reference:
+// - https://en.cppreference.com/w/cpp/utility/functional/not_fn
+// - https://wg21.link/func.not.fn
+template <typename F>
+constexpr not_fn_internal::NotFnImpl<std::decay_t<F>> not_fn(F&& f) {
+  return {std::forward<F>(f)};
+}
+
+}  // namespace webrtc
+
+#endif  // RTC_BASE_CONTAINERS_NOT_FN_H_
diff --git a/rtc_base/containers/void_t.h b/rtc_base/containers/void_t.h
new file mode 100644
index 0000000..62c57d4
--- /dev/null
+++ b/rtc_base/containers/void_t.h
@@ -0,0 +1,36 @@
+/*
+ *  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.
+
+#ifndef RTC_BASE_CONTAINERS_VOID_T_H_
+#define RTC_BASE_CONTAINERS_VOID_T_H_
+
+namespace webrtc {
+namespace void_t_internal {
+// Implementation detail of webrtc::void_t below.
+template <typename...>
+struct make_void {
+  using type = void;
+};
+
+}  // namespace void_t_internal
+
+// webrtc::void_t is an implementation of std::void_t from C++17.
+//
+// We use |webrtc::void_t_internal::make_void| as a helper struct to avoid a
+// C++14 defect:
+//   http://en.cppreference.com/w/cpp/types/void_t
+//   http://open-std.org/JTC1/SC22/WG21/docs/cwg_defects.html#1558
+template <typename... Ts>
+using void_t = typename ::webrtc::void_t_internal::make_void<Ts...>::type;
+}  // namespace webrtc
+
+#endif  // RTC_BASE_CONTAINERS_VOID_T_H_