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()

Drop the const in the second overload, just Comparable&& x. You can't move from a const object. And yes, it should be std::move(x) - a named object can never bind to an rvalue reference. — Igor Tandetnik
– Igor Tandetnik, Commented Dec 17, 2016 at 16:47

skypjack · Accepted Answer · 2016-12-17 23:13:44Z

2

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.

answered Dec 17, 2016 at 23:13

skypjack

50.9k19 gold badges108 silver badges203 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Edgar Rokjān Over a year ago

Can we leave only the rewritten version of the second insert function changing std::move to std::forward everywhere inside it?

skypjack Over a year ago

@EdgarRokyan It could make sense, of course. I didn't change the OP's code for I don't know what's the actual problem.

Collectives™ on Stack Overflow

Function overloading for rvalue

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related