Allow for using b-tree with `value_type`s that can only be constructed by the allocator (ignoring copy/move constructors).

We were using `init_type`s for temp values that we would move into slots, but in this case, we need to have actual slots. We use node handles for managing slots outside of nodes.

Also, in btree::copy_or_move_values_in_order, pass the slots from the iterators rather than references to values. This allows for moving from map keys instead of copying for standard layout types.

In the test, fix a couple of ClangTidy warnings from missing includes and calling `new` instead of `make_unique`.

PiperOrigin-RevId: 452062967
Change-Id: I870e89ae1aa5b3cfa62ae6e75b73ffc3d52e731c

1 files changed, 23 insertions, 10 deletions

diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index cc2e1793..fc2f740a 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -166,9 +166,10 @@ class btree_container {
 
   // 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());
+    // Use Construct instead of Transfer because the rebalancing code will
+    // destroy the slot later.
+    auto node =
+        CommonAccess::Construct<node_type>(get_allocator(), position.slot());
     erase(position);
     return node;
   }
@@ -291,8 +292,11 @@ class btree_set_container : public btree_container<Tree> {
   }
   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));
+    // Use a node handle to manage a temp slot.
+    auto node = CommonAccess::Construct<node_type>(this->get_allocator(),
+                                                   std::forward<Args>(args)...);
+    auto *slot = CommonAccess::GetSlot(node);
+    return this->tree_.insert_unique(params_type::key(slot), slot);
   }
   iterator insert(const_iterator hint, const value_type &v) {
     return this->tree_
@@ -306,9 +310,12 @@ class btree_set_container : public btree_container<Tree> {
   }
   template <typename... Args>
   iterator emplace_hint(const_iterator hint, Args &&... args) {
-    init_type v(std::forward<Args>(args)...);
+    // Use a node handle to manage a temp slot.
+    auto node = CommonAccess::Construct<node_type>(this->get_allocator(),
+                                                   std::forward<Args>(args)...);
+    auto *slot = CommonAccess::GetSlot(node);
     return this->tree_
-        .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v))
+        .insert_hint_unique(iterator(hint), params_type::key(slot), slot)
         .first;
   }
   template <typename InputIterator>
@@ -598,12 +605,18 @@ class btree_multiset_container : public btree_container<Tree> {
   }
   template <typename... Args>
   iterator emplace(Args &&... args) {
-    return this->tree_.insert_multi(init_type(std::forward<Args>(args)...));
+    // Use a node handle to manage a temp slot.
+    auto node = CommonAccess::Construct<node_type>(this->get_allocator(),
+                                                   std::forward<Args>(args)...);
+    return this->tree_.insert_multi(CommonAccess::GetSlot(node));
   }
   template <typename... Args>
   iterator emplace_hint(const_iterator hint, Args &&... args) {
-    return this->tree_.insert_hint_multi(
-        iterator(hint), init_type(std::forward<Args>(args)...));
+    // Use a node handle to manage a temp slot.
+    auto node = CommonAccess::Construct<node_type>(this->get_allocator(),
+                                                   std::forward<Args>(args)...);
+    return this->tree_.insert_hint_multi(iterator(hint),
+                                         CommonAccess::GetSlot(node));
   }
   iterator insert(node_type &&node) {
     if (!node) return this->end();