Creation of LTS branch "lts_2020_02_25"20200225

  - 0033c9ea91a52ade7c6b725aa2ef3cbe15463421 Fix build on FreeBSD/powerpc (#616) by kgotlinux <60880393+kgotlinux@users.noreply.github.com>
  - 0d5ce2797eb695aee7e019e25323251ef6ffc277 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - b69c7d880caddfc25bf348dbcfe9d45fdd8bc6e6 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 2a5633fc077a58528cdbfe78720f3f6bfdc6044d Merge "Export of internal Abseil changes" by Xiaoyi Zhang <zhangxy@google.com>
  - f9b3d6e493c1b6ab3dbdab71c5f8fa849db4abaf Add RISCV support to GetProgramCounter() (#621) by Khem Raj <raj.khem@gmail.com>
  - 0232c87f21c26718aa3eb2d86678070f3b498a4e Add missing ABSL_HAVE_VDSO_SUPPORT conditional (#622) by Sinan Kaya <41809318+franksinankaya@users.noreply.github.com>
  - 3c814105108680997d0821077694f663693b5382 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - c44657f55692eddf5504156645d1f4ec7b3acabd Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 98eb410c93ad059f9bba1bf43f5bb916fc92a5ea Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - bf78e977309c4cb946914b456404141ddac1c302 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - d95d1567165d449e4c213ea31a15cbb112a9865f Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 24713a7036a81498334807fa5c7ad3cb7c643711 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 72382c21fefed981b4b8a2a1b82e2d231c2c2e39 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 08a7e7bf972c8451855a5022f2faf3d3655db015 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 36bcd9599b3f48c99357ba61cf33584889306d6a Fix pointer format specifier in documentation (#614) by Andre Nguyen <andre-nguyen@users.noreply.github.com>
  - 0f86336b6939ea673cc1cbe29189286cae67d63a Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - c512f118dde6ffd51cb7d8ac8804bbaf4d266c3a Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 37dd2562ec830d547a1524bb306be313ac3f2556 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 44427702614d7b86b064ba06a390f5eb2f85dbf6 fix: Add support for more ARM processors detection (#608) by Andre Nguyen <andre-nguyen@users.noreply.github.com>
  - 159bf2bf6d1cc8087e02468d071e94d1177d1bae Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - a2e6adecc294dc4cd98cc285a9134ce58e0f2ad0 Use https links. (#586) by nlewycky <nicholas@mxc.ca>
  - 564001ae506a17c51fa1223684a78f05f91d3d91 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - b3aaac8a37c467a1125c794196caa90d0957bdc3 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 63ee2f8877915a3565c29707dba8fe4d7822596a Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - a048203a881f11f4b7b8df5fb563aec85522f8db Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 1de0166368e2ae67347f92099d6dca3ab3a4a496 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - ad904b6cd3906ddf79878003d92b7bc08d7786ae Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 29235139149790f5afc430c11cec8f1eb1677607 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - bf86cfe165ef7d70dfe68f0b8fc0c018bc79a577 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 12bc53e0318d80569270a5b26ccbc62b52022b89 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 1e39f8626a4dadec1f56920b999dd4c3cfae333e Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 77f87009a34c745255bd84d8f2647040d831a2b3 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - d659fe54b35ab9b8e35c72e50a4b8814167d5a84 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - a4b757b5d42694306a9de853cee0a5fba9c7bbe9 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 0514227d2547793b23e209809276375e41c76617 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 7f4fe64af80fe3c84db8ea938276c3690573c45e Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 16d9fd58a51c6083234e2e9f8f50e49ed5ed02e4 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - bcaae6009c0833b73c6fa7bdd972921d8081a724 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 8ba96a8244bbe334d09542e92d566673a65c1f78 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 2103fd9acdf58279f739860bff3f8c9f4b845605 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 3df7b52a6ada51a72a23796b844549a7b282f1b8 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - fa8c75182fbfdeddb2485fc0d53baeda3f40b7a3 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 85092b4b648ca729c6263c4a302a41dfff28705e Fix Conan builds (#400) by Adrian Ostrowski <adr.ostrowski@gmail.com>
  - e96ae2203b80d5ae2e0b7abe0c77b722b224b16d Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 20de2db748ca0471cfb61cb53e813dd12938c12b Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 846e5dbedac123d12455adcfe6f53c8b5dcbfeef Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 8207907f4f7fbaeeaa2b7340c76875e06fd345ba Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 078b89b3c046d230ef3ad39494e5852184eb528b Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 19b021cb3ff23048dfbe236a4e611925d8930831 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - ecc0033b54847f6c9ee37dbb0be8aa17e5b6d37b Always enable proper symbolize implementation on Windows ... by Loo Rong Jie <loorongjie@gmail.com>
  - 2796d500aea5a31d26b8b24a33fab7a1c8fa2f32 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - e4c8d0eb8ef4acb5d7a4252b3b87feb391ef7e41 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - a15364ce4d88534ae2295127e5d8e32aefb6b446 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - ab3552a18964e7063c8324f45b3896a6a20b08a8 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - e9f9000c7c80993cb589d011616b7a8016e42f4a Fix ABSL_WAITER_MODE detection for mingw (#342) by Joe Sylve <Joe.Sylve@gmail.com>
  - abea769b551f7a100f540967cb95debdb0080df8 Fix ABSL_HAVE_ALARM check on mingw (#341) by Joe Sylve <Joe.Sylve@gmail.com>
  - 25597bdfc148e91e27678ec30efa52f4fc8c164f Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - aad33fefaa8f744d71ce747a53717b835bdf8e84 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 8fe7214fe2d7a45ecc4d85f6a524c6b1532426de Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - debac94cfb5a0fa75d1d97c399682bd1c72e3191 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 882b3501a31eb0e4ae4213afb91a0e43feda7d5f Fix spelling errors (#384) by Sungmann Cho <55860394+chosungmann@users.noreply.github.com>
  - 502efe6d7841bff82b1aeef5500491fe9a48c635 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - ccdd1d57b6386ebc26fb0c7d99b604672437c124 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - ddf8e52a2918dd0ccec75d3e2426125fa3926724 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 6ec136281086b71da32b5fb068bd6e46b78a5c79 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - ac78ffc3bc0a8b295cab9a03817760fd460df2a1 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 5374c56e5196320681993869e3126b51edac2a43 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 97c1664b4bbab5f78fac2b151ab02656268fb34b Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 325fd7b042ff4ec34f7dd32e602cd81ad0e24b22 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 83c1d65c90a92aa49632b9ac5a793214bb0768bc Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - eb6b7bd23bc0815bfd784e1a74021ce166765280 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 9ddac555b7861dc178d0dbe758a1cfbed718784b Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 1948f6f967e34db9793cfa8b4bcbaf370d039fd8 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - a0d1e098c2f99694fa399b175a7ccf920762030e Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 2d2d7fbc283315b676159716376e739d3d23ed94 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 0302d1e5fa4fcdd1763b7d1bb3212943b1ae911d supppress unused variable warning for gcc (#372) by Martin <pizzard@users.noreply.github.com>
  - 262d74ba81b1fc4d71f459555cde8ecb39786d68 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - f0afae0d49af3e15a7169e019634d7719143d94d Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 0e7afdcbd24c7e5b7cab4e0217d8886f1525b520 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 9a41ffdd3a0ccbcdd29c4e3886b28e06f2cd9c66 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 36910d3d7e9fccadd6603f232d0c4f54dcd47c7e [bazel] Add fixes for --incompatible_load_cc_rules_from_b... by Yannic <contact@yannic-bonenberger.com>
  - aae8143cf9aa611f70d7ea9b95b8b8b383b2271a Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - d9aa92d7fb324314f9df487ac23d32a25650b742 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 321ab5303023c86cd15d9ddc5740fb4b4fde32e1 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 4ef574064e75b86f115549e9eb4c7e806781b3ab Export of internal Abseil changes by Abseil Team <absl-team@google.com>

GitOrigin-RevId: 0033c9ea91a52ade7c6b725aa2ef3cbe15463421
Change-Id: I8a2b70063cb3ab40c6943a6db0fe40cae71ed8d7

1 files changed, 672 insertions, 0 deletions

diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
new file mode 100644
index 00000000..f2e4c3a5
--- /dev/null
+++ b/absl/container/internal/btree_container.h
@@ -0,0 +1,672 @@
+// Copyright 2018 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef ABSL_CONTAINER_INTERNAL_BTREE_CONTAINER_H_
+#define ABSL_CONTAINER_INTERNAL_BTREE_CONTAINER_H_
+
+#include <algorithm>
+#include <initializer_list>
+#include <iterator>
+#include <utility>
+
+#include "absl/base/internal/throw_delegate.h"
+#include "absl/container/internal/btree.h"  // IWYU pragma: export
+#include "absl/container/internal/common.h"
+#include "absl/meta/type_traits.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace container_internal {
+
+// A common base class for btree_set, btree_map, btree_multiset, and
+// btree_multimap.
+template <typename Tree>
+class btree_container {
+  using params_type = typename Tree::params_type;
+
+ protected:
+  // Alias used for heterogeneous lookup functions.
+  // `key_arg<K>` evaluates to `K` when the functors are transparent and to
+  // `key_type` otherwise. It permits template argument deduction on `K` for the
+  // transparent case.
+  template <class K>
+  using key_arg =
+      typename KeyArg<IsTransparent<typename Tree::key_compare>::value>::
+          template type<K, typename Tree::key_type>;
+
+ public:
+  using key_type = typename Tree::key_type;
+  using value_type = typename Tree::value_type;
+  using size_type = typename Tree::size_type;
+  using difference_type = typename Tree::difference_type;
+  using key_compare = typename Tree::key_compare;
+  using value_compare = typename Tree::value_compare;
+  using allocator_type = typename Tree::allocator_type;
+  using reference = typename Tree::reference;
+  using const_reference = typename Tree::const_reference;
+  using pointer = typename Tree::pointer;
+  using const_pointer = typename Tree::const_pointer;
+  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 node_type = typename Tree::node_handle_type;
+
+  // Constructors/assignments.
+  btree_container() : tree_(key_compare(), allocator_type()) {}
+  explicit btree_container(const key_compare &comp,
+                           const allocator_type &alloc = allocator_type())
+      : tree_(comp, alloc) {}
+  btree_container(const btree_container &x) = default;
+  btree_container(btree_container &&x) noexcept = default;
+  btree_container &operator=(const btree_container &x) = default;
+  btree_container &operator=(btree_container &&x) noexcept(
+      std::is_nothrow_move_assignable<Tree>::value) = default;
+
+  // Iterator routines.
+  iterator begin() { return tree_.begin(); }
+  const_iterator begin() const { return tree_.begin(); }
+  const_iterator cbegin() const { return tree_.begin(); }
+  iterator end() { return tree_.end(); }
+  const_iterator end() const { return tree_.end(); }
+  const_iterator cend() const { return tree_.end(); }
+  reverse_iterator rbegin() { return tree_.rbegin(); }
+  const_reverse_iterator rbegin() const { return tree_.rbegin(); }
+  const_reverse_iterator crbegin() const { return tree_.rbegin(); }
+  reverse_iterator rend() { return tree_.rend(); }
+  const_reverse_iterator rend() const { return tree_.rend(); }
+  const_reverse_iterator crend() const { return tree_.rend(); }
+
+  // Lookup routines.
+  template <typename K = key_type>
+  iterator find(const key_arg<K> &key) {
+    return tree_.find(key);
+  }
+  template <typename K = key_type>
+  const_iterator find(const key_arg<K> &key) const {
+    return tree_.find(key);
+  }
+  template <typename K = key_type>
+  bool contains(const key_arg<K> &key) const {
+    return find(key) != end();
+  }
+  template <typename K = key_type>
+  iterator lower_bound(const key_arg<K> &key) {
+    return tree_.lower_bound(key);
+  }
+  template <typename K = key_type>
+  const_iterator lower_bound(const key_arg<K> &key) const {
+    return tree_.lower_bound(key);
+  }
+  template <typename K = key_type>
+  iterator upper_bound(const key_arg<K> &key) {
+    return tree_.upper_bound(key);
+  }
+  template <typename K = key_type>
+  const_iterator upper_bound(const key_arg<K> &key) const {
+    return tree_.upper_bound(key);
+  }
+  template <typename K = key_type>
+  std::pair<iterator, iterator> equal_range(const key_arg<K> &key) {
+    return tree_.equal_range(key);
+  }
+  template <typename K = key_type>
+  std::pair<const_iterator, const_iterator> equal_range(
+      const key_arg<K> &key) const {
+    return tree_.equal_range(key);
+  }
+
+  // Deletion routines. Note that there is also a deletion routine that is
+  // specific to btree_set_container/btree_multiset_container.
+
+  // Erase the specified iterator from the btree. The iterator must be valid
+  // (i.e. not equal to end()).  Return an iterator pointing to the node after
+  // the one that was erased (or end() if none exists).
+  iterator erase(const_iterator iter) { return tree_.erase(iterator(iter)); }
+  iterator erase(iterator iter) { return tree_.erase(iter); }
+  iterator erase(const_iterator first, const_iterator last) {
+    return tree_.erase_range(iterator(first), iterator(last)).second;
+  }
+
+  // Extract routines.
+  node_type extract(iterator position) {
+    // Use Move instead of Transfer, because the rebalancing code expects to
+    // have a valid object to scribble metadata bits on top of.
+    auto node = CommonAccess::Move<node_type>(get_allocator(), position.slot());
+    erase(position);
+    return node;
+  }
+  node_type extract(const_iterator position) {
+    return extract(iterator(position));
+  }
+
+ public:
+  // Utility routines.
+  void clear() { tree_.clear(); }
+  void swap(btree_container &x) { tree_.swap(x.tree_); }
+  void verify() const { tree_.verify(); }
+
+  // Size routines.
+  size_type size() const { return tree_.size(); }
+  size_type max_size() const { return tree_.max_size(); }
+  bool empty() const { return tree_.empty(); }
+
+  friend bool operator==(const btree_container &x, const btree_container &y) {
+    if (x.size() != y.size()) return false;
+    return std::equal(x.begin(), x.end(), y.begin());
+  }
+
+  friend bool operator!=(const btree_container &x, const btree_container &y) {
+    return !(x == y);
+  }
+
+  friend bool operator<(const btree_container &x, const btree_container &y) {
+    return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
+  }
+
+  friend bool operator>(const btree_container &x, const btree_container &y) {
+    return y < x;
+  }
+
+  friend bool operator<=(const btree_container &x, const btree_container &y) {
+    return !(y < x);
+  }
+
+  friend bool operator>=(const btree_container &x, const btree_container &y) {
+    return !(x < y);
+  }
+
+  // The allocator used by the btree.
+  allocator_type get_allocator() const { return tree_.get_allocator(); }
+
+  // The key comparator used by the btree.
+  key_compare key_comp() const { return tree_.key_comp(); }
+  value_compare value_comp() const { return tree_.value_comp(); }
+
+  // Support absl::Hash.
+  template <typename State>
+  friend State AbslHashValue(State h, const btree_container &b) {
+    for (const auto &v : b) {
+      h = State::combine(std::move(h), v);
+    }
+    return State::combine(std::move(h), b.size());
+  }
+
+ protected:
+  Tree tree_;
+};
+
+// A common base class for btree_set and btree_map.
+template <typename Tree>
+class btree_set_container : public btree_container<Tree> {
+  using super_type = btree_container<Tree>;
+  using params_type = typename Tree::params_type;
+  using init_type = typename params_type::init_type;
+  using is_key_compare_to = typename params_type::is_key_compare_to;
+  friend class BtreeNodePeer;
+
+ protected:
+  template <class K>
+  using key_arg = typename super_type::template key_arg<K>;
+
+ public:
+  using key_type = typename Tree::key_type;
+  using value_type = typename Tree::value_type;
+  using size_type = typename Tree::size_type;
+  using key_compare = typename Tree::key_compare;
+  using allocator_type = typename Tree::allocator_type;
+  using iterator = typename Tree::iterator;
+  using const_iterator = typename Tree::const_iterator;
+  using node_type = typename super_type::node_type;
+  using insert_return_type = InsertReturnType<iterator, node_type>;
+
+  // Inherit constructors.
+  using super_type::super_type;
+  btree_set_container() {}
+
+  // Range constructor.
+  template <class InputIterator>
+  btree_set_container(InputIterator b, InputIterator e,
+                      const key_compare &comp = key_compare(),
+                      const allocator_type &alloc = allocator_type())
+      : super_type(comp, alloc) {
+    insert(b, e);
+  }
+
+  // Initializer list constructor.
+  btree_set_container(std::initializer_list<init_type> init,
+                      const key_compare &comp = key_compare(),
+                      const allocator_type &alloc = allocator_type())
+      : btree_set_container(init.begin(), init.end(), comp, alloc) {}
+
+  // Lookup routines.
+  template <typename K = key_type>
+  size_type count(const key_arg<K> &key) const {
+    return this->tree_.count_unique(key);
+  }
+
+  // Insertion routines.
+  std::pair<iterator, bool> insert(const value_type &x) {
+    return this->tree_.insert_unique(params_type::key(x), x);
+  }
+  std::pair<iterator, bool> insert(value_type &&x) {
+    return this->tree_.insert_unique(params_type::key(x), std::move(x));
+  }
+  template <typename... Args>
+  std::pair<iterator, bool> emplace(Args &&... args) {
+    init_type v(std::forward<Args>(args)...);
+    return this->tree_.insert_unique(params_type::key(v), std::move(v));
+  }
+  iterator insert(const_iterator position, const value_type &x) {
+    return this->tree_
+        .insert_hint_unique(iterator(position), params_type::key(x), x)
+        .first;
+  }
+  iterator insert(const_iterator position, value_type &&x) {
+    return this->tree_
+        .insert_hint_unique(iterator(position), params_type::key(x),
+                            std::move(x))
+        .first;
+  }
+  template <typename... Args>
+  iterator emplace_hint(const_iterator position, Args &&... args) {
+    init_type v(std::forward<Args>(args)...);
+    return this->tree_
+        .insert_hint_unique(iterator(position), params_type::key(v),
+                            std::move(v))
+        .first;
+  }
+  template <typename InputIterator>
+  void insert(InputIterator b, InputIterator e) {
+    this->tree_.insert_iterator_unique(b, e);
+  }
+  void insert(std::initializer_list<init_type> init) {
+    this->tree_.insert_iterator_unique(init.begin(), init.end());
+  }
+  insert_return_type insert(node_type &&node) {
+    if (!node) return {this->end(), false, node_type()};
+    std::pair<iterator, bool> res =
+        this->tree_.insert_unique(params_type::key(CommonAccess::GetSlot(node)),
+                                  CommonAccess::GetSlot(node));
+    if (res.second) {
+      CommonAccess::Destroy(&node);
+      return {res.first, true, node_type()};
+    } else {
+      return {res.first, false, std::move(node)};
+    }
+  }
+  iterator insert(const_iterator hint, node_type &&node) {
+    if (!node) return this->end();
+    std::pair<iterator, bool> res = this->tree_.insert_hint_unique(
+        iterator(hint), params_type::key(CommonAccess::GetSlot(node)),
+        CommonAccess::GetSlot(node));
+    if (res.second) CommonAccess::Destroy(&node);
+    return res.first;
+  }
+
+  // Deletion routines.
+  template <typename K = key_type>
+  size_type erase(const key_arg<K> &key) {
+    return this->tree_.erase_unique(key);
+  }
+  using super_type::erase;
+
+  // Node extraction routines.
+  template <typename K = key_type>
+  node_type extract(const key_arg<K> &key) {
+    auto it = this->find(key);
+    return it == this->end() ? node_type() : extract(it);
+  }
+  using super_type::extract;
+
+  // Merge routines.
+  // Moves elements from `src` into `this`. If the element already exists in
+  // `this`, it is left unmodified in `src`.
+  template <
+      typename T,
+      typename absl::enable_if_t<
+          absl::conjunction<
+              std::is_same<value_type, typename T::value_type>,
+              std::is_same<allocator_type, typename T::allocator_type>,
+              std::is_same<typename params_type::is_map_container,
+                           typename T::params_type::is_map_container>>::value,
+          int> = 0>
+  void merge(btree_container<T> &src) {  // NOLINT
+    for (auto src_it = src.begin(); src_it != src.end();) {
+      if (insert(std::move(*src_it)).second) {
+        src_it = src.erase(src_it);
+      } else {
+        ++src_it;
+      }
+    }
+  }
+
+  template <
+      typename T,
+      typename absl::enable_if_t<
+          absl::conjunction<
+              std::is_same<value_type, typename T::value_type>,
+              std::is_same<allocator_type, typename T::allocator_type>,
+              std::is_same<typename params_type::is_map_container,
+                           typename T::params_type::is_map_container>>::value,
+          int> = 0>
+  void merge(btree_container<T> &&src) {
+    merge(src);
+  }
+};
+
+// Base class for btree_map.
+template <typename Tree>
+class btree_map_container : public btree_set_container<Tree> {
+  using super_type = btree_set_container<Tree>;
+  using params_type = typename Tree::params_type;
+
+ private:
+  template <class K>
+  using key_arg = typename super_type::template key_arg<K>;
+
+ public:
+  using key_type = typename Tree::key_type;
+  using mapped_type = typename params_type::mapped_type;
+  using value_type = typename Tree::value_type;
+  using key_compare = typename Tree::key_compare;
+  using allocator_type = typename Tree::allocator_type;
+  using iterator = typename Tree::iterator;
+  using const_iterator = typename Tree::const_iterator;
+
+  // Inherit constructors.
+  using super_type::super_type;
+  btree_map_container() {}
+
+  // Insertion routines.
+  // Note: the nullptr template arguments and extra `const M&` overloads allow
+  // for supporting bitfield arguments.
+  // Note: when we call `std::forward<M>(obj)` twice, it's safe because
+  // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when
+  // `ret.second` is false.
+  template <class M>
+  std::pair<iterator, bool> insert_or_assign(const key_type &k, const M &obj) {
+    const std::pair<iterator, bool> ret = this->tree_.insert_unique(k, k, obj);
+    if (!ret.second) ret.first->second = obj;
+    return ret;
+  }
+  template <class M, key_type * = nullptr>
+  std::pair<iterator, bool> insert_or_assign(key_type &&k, const M &obj) {
+    const std::pair<iterator, bool> ret =
+        this->tree_.insert_unique(k, std::move(k), obj);
+    if (!ret.second) ret.first->second = obj;
+    return ret;
+  }
+  template <class M, M * = nullptr>
+  std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj) {
+    const std::pair<iterator, bool> ret =
+        this->tree_.insert_unique(k, k, std::forward<M>(obj));
+    if (!ret.second) ret.first->second = std::forward<M>(obj);
+    return ret;
+  }
+  template <class M, key_type * = nullptr, M * = nullptr>
+  std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj) {
+    const std::pair<iterator, bool> ret =
+        this->tree_.insert_unique(k, std::move(k), std::forward<M>(obj));
+    if (!ret.second) ret.first->second = std::forward<M>(obj);
+    return ret;
+  }
+  template <class M>
+  iterator insert_or_assign(const_iterator position, const key_type &k,
+                            const M &obj) {
+    const std::pair<iterator, bool> ret =
+        this->tree_.insert_hint_unique(iterator(position), k, k, obj);
+    if (!ret.second) ret.first->second = obj;
+    return ret.first;
+  }
+  template <class M, key_type * = nullptr>
+  iterator insert_or_assign(const_iterator position, key_type &&k,
+                            const M &obj) {
+    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
+        iterator(position), k, std::move(k), obj);
+    if (!ret.second) ret.first->second = obj;
+    return ret.first;
+  }
+  template <class M, M * = nullptr>
+  iterator insert_or_assign(const_iterator position, const key_type &k,
+                            M &&obj) {
+    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
+        iterator(position), k, k, std::forward<M>(obj));
+    if (!ret.second) ret.first->second = std::forward<M>(obj);
+    return ret.first;
+  }
+  template <class M, key_type * = nullptr, M * = nullptr>
+  iterator insert_or_assign(const_iterator position, key_type &&k, M &&obj) {
+    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
+        iterator(position), k, std::move(k), std::forward<M>(obj));
+    if (!ret.second) ret.first->second = std::forward<M>(obj);
+    return ret.first;
+  }
+  template <typename... Args>
+  std::pair<iterator, bool> try_emplace(const key_type &k, Args &&... args) {
+    return this->tree_.insert_unique(
+        k, std::piecewise_construct, std::forward_as_tuple(k),
+        std::forward_as_tuple(std::forward<Args>(args)...));
+  }
+  template <typename... Args>
+  std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args) {
+    // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k`
+    // and then using `k` unsequenced. This is safe because the move is into a
+    // forwarding reference and insert_unique guarantees that `key` is never
+    // referenced after consuming `args`.
+    const key_type &key_ref = k;
+    return this->tree_.insert_unique(
+        key_ref, std::piecewise_construct, std::forward_as_tuple(std::move(k)),
+        std::forward_as_tuple(std::forward<Args>(args)...));
+  }
+  template <typename... Args>
+  iterator try_emplace(const_iterator hint, const key_type &k,
+                       Args &&... args) {
+    return this->tree_
+        .insert_hint_unique(iterator(hint), k, std::piecewise_construct,
+                            std::forward_as_tuple(k),
+                            std::forward_as_tuple(std::forward<Args>(args)...))
+        .first;
+  }
+  template <typename... Args>
+  iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args) {
+    // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k`
+    // and then using `k` unsequenced. This is safe because the move is into a
+    // forwarding reference and insert_hint_unique guarantees that `key` is
+    // never referenced after consuming `args`.
+    const key_type &key_ref = k;
+    return this->tree_
+        .insert_hint_unique(iterator(hint), key_ref, std::piecewise_construct,
+                            std::forward_as_tuple(std::move(k)),
+                            std::forward_as_tuple(std::forward<Args>(args)...))
+        .first;
+  }
+  mapped_type &operator[](const key_type &k) {
+    return try_emplace(k).first->second;
+  }
+  mapped_type &operator[](key_type &&k) {
+    return try_emplace(std::move(k)).first->second;
+  }
+
+  template <typename K = key_type>
+  mapped_type &at(const key_arg<K> &key) {
+    auto it = this->find(key);
+    if (it == this->end())
+      base_internal::ThrowStdOutOfRange("absl::btree_map::at");
+    return it->second;
+  }
+  template <typename K = key_type>
+  const mapped_type &at(const key_arg<K> &key) const {
+    auto it = this->find(key);
+    if (it == this->end())
+      base_internal::ThrowStdOutOfRange("absl::btree_map::at");
+    return it->second;
+  }
+};
+
+// A common base class for btree_multiset and btree_multimap.
+template <typename Tree>
+class btree_multiset_container : public btree_container<Tree> {
+  using super_type = btree_container<Tree>;
+  using params_type = typename Tree::params_type;
+  using init_type = typename params_type::init_type;
+  using is_key_compare_to = typename params_type::is_key_compare_to;
+
+  template <class K>
+  using key_arg = typename super_type::template key_arg<K>;
+
+ public:
+  using key_type = typename Tree::key_type;
+  using value_type = typename Tree::value_type;
+  using size_type = typename Tree::size_type;
+  using key_compare = typename Tree::key_compare;
+  using allocator_type = typename Tree::allocator_type;
+  using iterator = typename Tree::iterator;
+  using const_iterator = typename Tree::const_iterator;
+  using node_type = typename super_type::node_type;
+
+  // Inherit constructors.
+  using super_type::super_type;
+  btree_multiset_container() {}
+
+  // Range constructor.
+  template <class InputIterator>
+  btree_multiset_container(InputIterator b, InputIterator e,
+                           const key_compare &comp = key_compare(),
+                           const allocator_type &alloc = allocator_type())
+      : super_type(comp, alloc) {
+    insert(b, e);
+  }
+
+  // Initializer list constructor.
+  btree_multiset_container(std::initializer_list<init_type> init,
+                           const key_compare &comp = key_compare(),
+                           const allocator_type &alloc = allocator_type())
+      : btree_multiset_container(init.begin(), init.end(), comp, alloc) {}
+
+  // Lookup routines.
+  template <typename K = key_type>
+  size_type count(const key_arg<K> &key) const {
+    return this->tree_.count_multi(key);
+  }
+
+  // Insertion routines.
+  iterator insert(const value_type &x) { return this->tree_.insert_multi(x); }
+  iterator insert(value_type &&x) {
+    return this->tree_.insert_multi(std::move(x));
+  }
+  iterator insert(const_iterator position, const value_type &x) {
+    return this->tree_.insert_hint_multi(iterator(position), x);
+  }
+  iterator insert(const_iterator position, value_type &&x) {
+    return this->tree_.insert_hint_multi(iterator(position), std::move(x));
+  }
+  template <typename InputIterator>
+  void insert(InputIterator b, InputIterator e) {
+    this->tree_.insert_iterator_multi(b, e);
+  }
+  void insert(std::initializer_list<init_type> init) {
+    this->tree_.insert_iterator_multi(init.begin(), init.end());
+  }
+  template <typename... Args>
+  iterator emplace(Args &&... args) {
+    return this->tree_.insert_multi(init_type(std::forward<Args>(args)...));
+  }
+  template <typename... Args>
+  iterator emplace_hint(const_iterator position, Args &&... args) {
+    return this->tree_.insert_hint_multi(
+        iterator(position), init_type(std::forward<Args>(args)...));
+  }
+  iterator insert(node_type &&node) {
+    if (!node) return this->end();
+    iterator res =
+        this->tree_.insert_multi(params_type::key(CommonAccess::GetSlot(node)),
+                                 CommonAccess::GetSlot(node));
+    CommonAccess::Destroy(&node);
+    return res;
+  }
+  iterator insert(const_iterator hint, node_type &&node) {
+    if (!node) return this->end();
+    iterator res = this->tree_.insert_hint_multi(
+        iterator(hint),
+        std::move(params_type::element(CommonAccess::GetSlot(node))));
+    CommonAccess::Destroy(&node);
+    return res;
+  }
+
+  // Deletion routines.
+  template <typename K = key_type>
+  size_type erase(const key_arg<K> &key) {
+    return this->tree_.erase_multi(key);
+  }
+  using super_type::erase;
+
+  // Node extraction routines.
+  template <typename K = key_type>
+  node_type extract(const key_arg<K> &key) {
+    auto it = this->find(key);
+    return it == this->end() ? node_type() : extract(it);
+  }
+  using super_type::extract;
+
+  // Merge routines.
+  // Moves all elements from `src` into `this`.
+  template <
+      typename T,
+      typename absl::enable_if_t<
+          absl::conjunction<
+              std::is_same<value_type, typename T::value_type>,
+              std::is_same<allocator_type, typename T::allocator_type>,
+              std::is_same<typename params_type::is_map_container,
+                           typename T::params_type::is_map_container>>::value,
+          int> = 0>
+  void merge(btree_container<T> &src) {  // NOLINT
+    insert(std::make_move_iterator(src.begin()),
+           std::make_move_iterator(src.end()));
+    src.clear();
+  }
+
+  template <
+      typename T,
+      typename absl::enable_if_t<
+          absl::conjunction<
+              std::is_same<value_type, typename T::value_type>,
+              std::is_same<allocator_type, typename T::allocator_type>,
+              std::is_same<typename params_type::is_map_container,
+                           typename T::params_type::is_map_container>>::value,
+          int> = 0>
+  void merge(btree_container<T> &&src) {
+    merge(src);
+  }
+};
+
+// A base class for btree_multimap.
+template <typename Tree>
+class btree_multimap_container : public btree_multiset_container<Tree> {
+  using super_type = btree_multiset_container<Tree>;
+  using params_type = typename Tree::params_type;
+
+ public:
+  using mapped_type = typename params_type::mapped_type;
+
+  // Inherit constructors.
+  using super_type::super_type;
+  btree_multimap_container() {}
+};
+
+}  // namespace container_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
+
+#endif  // ABSL_CONTAINER_INTERNAL_BTREE_CONTAINER_H_