STL风格BST容器右值插入函数覆盖已有值的问题排查

Hey there, let's figure out why your rvalue insert is wiping out all existing nodes in your custom BST implementation. Looking at the code snippets you shared, the issue is almost certainly rooted in how your insert_unique function handles the new node and the tree's root pointer.

First, let's break down the likely cause #

Your truncated insert_unique code shows you're creating a node_holder_ for the new value, but then it looks like you're directly assigning the new node to root_ instead of traversing the BST to insert the node in the correct position. For example, if you're doing something like root_ = h_.release(); without checking if the tree is already non-empty, you're replacing the entire existing tree with just the new node—hence all prior values disappear.

How to fix this #

Let's walk through the key fixes you need to implement:

1. Implement proper BST insertion traversal
   Instead of overwriting root_ immediately, you need to traverse the tree to find the correct spot for the new node (following BST rules: left child for smaller values, right child for larger values). Here's a corrected version of insert_unique that follows this logic:

   template<typename Vp_>
   std::pair<iterator, bool> insert_unique(Vp_&& value) {
       // Perfect-forward the value to preserve its value category
       node_holder_ h = make_node_holder(std::forward<Vp_>(value));
       node_pointer_ new_node = h.get();
   
       // Case 1: Tree is empty, new node becomes root
       if (root_ == nullptr) {
           root_ = h.release();
           return {iterator(root_), true};
       }
   
       // Case 2: Tree has nodes—traverse to find insertion point
       node_pointer_ current = root_;
       node_pointer_ parent = nullptr;
       while (current != nullptr) {
           parent = current;
           if (value < current->value) {
               current = current->left;
           } else if (current->value < value) {
               current = current->right;
           } else {
               // Duplicate value—insert fails, return existing node
               return {iterator(current), false};
           }
       }
   
       // Attach new node to the parent's left or right
       if (value < parent->value) {
           parent->left = h.release();
       } else {
           parent->right = h.release();
       }
       return {iterator(new_node), true};
   }
   

2. Use perfect forwarding instead of fixed std::move
   Since insert_unique uses a universal reference (Vp_&&), use std::forward<Vp_>(value) instead of std::move—this ensures that both lvalues and rvalues are handled correctly when passing to make_node_holder.

3. Validate your node_holder behavior
   Make sure node_holder_'s release() method correctly transfers ownership of the node without leaking memory. If you were previously overwriting root_ without cleaning up the old tree, that would cause memory leaks—fixing the insertion logic avoids this entirely.

4. Align lvalue and rvalue insert paths
   Ensure your lvalue insert function uses the same insert_unique logic (or shares core insertion code) as the rvalue version. This way, both insertion types behave consistently, with no unexpected differences.

内容的提问来源于stack exchange，提问作者code_art