Function overloading for rvalue

Question

I am implementing an insert function for a binary search tree class, there are two versions for the function, one that is called with an lvalue item (the item to be inserted to the tree) and one with an rvalue where I am using std::move.

The first:

template <typename Comparable>
void BinarySearchTree<Comparable>::insert(const Comparable &x, BinaryNode* &t)
{
    if (t == nullptr)
        t = new BinaryNode(x, nullptr, nullptr);

    if (x < t->element)
        insert(x, t->left);
    if (x > t->element)
        insert(x, t->right);
}

The second:

template <typename Comparable>
void BinarySearchTree<Comparable>::insert(Comparable &&x, BinaryNode* &t)
{
    if (t == nullptr)
        t = new BinaryNode(std::move(x), nullptr, nullptr);

    if (x < t->element)
        insert(x, t->left); // should this be insert(std::move(x), t->left)?
    if (x > t->element)
        insert(x, t->right); // also here?
}

Should the recursive call of insert in the second function be called with x or std::move(x)?

My guess is that it should be x as it's already an rvalue and no need for move(), however, the guide implementation I am using used std::move()

Answer 1

First of all, consider what the standard says for those objects that can be moved:

[...] moved-from objects shall be placed in a valid but unspecified state.

You cannot expect that it applies also to all the user defined types, but it's a common pattern.
Let's suppose it's the case for a Comparable and analyze your second function:

template <typename Comparable>
void BinarySearchTree<Comparable>::insert(Comparable &&x, BinaryNode* &t)
{
    if (t == nullptr)
        t = new BinaryNode(std::move(x), nullptr, nullptr);

    if (x < t->element)
        insert(x, t->left); // should this be insert(std::move(x), t->left)?
    if (x > t->element)
        insert(x, t->right); // also here?
}

If t equals to nullptr, you move x in t.
After that operation, it could happen that x is in a valid but unspecified state.
It means that x < t->element as well as x > t->element have an undefined behavior.
In other terms, you should not use an object once you have moved it out. Similarly, you should not move twice the same object.

Should the recursive call of insert in the second function be called with x or std::move(x)?

You can simply rewrite it as it follows:

template <typename Comparable>
void BinarySearchTree<Comparable>::insert(Comparable &&x, BinaryNode* &t)
{
    if (t == nullptr) {
        t = new BinaryNode(std::move(x), nullptr, nullptr);
    } else if (x < t->element) {
        insert(std::move(x), t->left);
    } else if (x > t->element) {
        insert(std::move(x), t->right);
    }
}

Move a Comparable only once.