How to reduce redundant code when adding new c++0x rvalue reference operator overloads

Question

I am adding new operator overloads to take advantage of c++0x rvalue references, and I feel like I'm producing a lot of redundant code.

I have a class, tree, that holds a tree of algebraic operations on double values. Here is an example use case:

tree x = 1.23;
tree y = 8.19;
tree z = (x + y)/67.31 - 3.15*y;
...
std::cout << z; // prints "(1.23 + 8.19)/67.31 - 3.15*8.19"

For each binary operation (like plus), each side can be either an lvalue tree, rvalue tree, or double. This results in 8 overloads for each binary operation:

// core rvalue overloads for plus:
tree operator +(const tree& a, const tree& b);
tree operator +(const tree& a, tree&&      b);
tree operator +(tree&&      a, const tree& b);
tree operator +(tree&&      a, tree&&      b);

// cast and forward cases:
tree operator +(const tree& a, double      b) { return a + tree(b); }
tree operator +(double      a, const tree& b) { return tree(a) + b; }
tree operator +(tree&&      a, double      b) { return std::move(a) + tree(b); }
tree operator +(double      a, tree&&      b) { return tree(a) + std::move(b); }

// 8 more overloads for minus

// 8 more overloads for multiply

// 8 more overloads for divide

// etc

which also has to be repeated in a way for each binary operation (minus, multiply, divide, etc).

As you can see, there are really only 4 functions I actually need to write; the other 4 can cast and forward to the core cases.

Do you have any suggestions for reducing the size of this code?

PS: The class is actually more complex than just a tree of doubles. Reducing copies does dramatically improve performance of my project. So, the rvalue overloads are worthwhile for me, even with the extra code. I have a suspicion that there might be a way to template away the "cast and forward" cases above, but I can't seem to think of anything.

Romanov

Answer 1

Just a quick late answer: If the class in question is moveable, the move is very cheap, and you would always move from all the arguments if you can, then passing the arguments by value might be an option:

tree operator +(tree      a, tree      b);

If tree is moveable and an rvalue ref is passed as the actual argument, then the arguments to the function will be initialized with tree's move constructor where possible, else the copy constructor. Then, the function can do whatever it wants with its arguments in the appropriate way (like, say, moving their internals around).

It does incur an extra move when passing an rvalue reference argument compared with the lots-of-overloads version, but I think it's generally better.

Also, IMO, tree && arguments should maybe accept lvalues via a temporary copy, but this is not what any compilers currently do, so it's not very useful.

Pesade

But I had to add +(double a, tree b) and (tree a, double a) versions. – Romanov

Answer 2

First, I don't see why operator+ would modify the arguments at all (isn't this a typical immutable binary tree implementation), so there'd be no difference between r-value and l-value reference. But let's assume that the subtrees have a pointer up to the parent or something like that.

From the usage example you showed, it looks like there's an implicit conversion from double to tree. In that case, your "cast and forward" cases aren't needed, the compiler will find the user-defined conversion.

Don't the non-move overloads end up making a new instance to go into the new tree? If so, I think you can write three of your remaining four cases as forwarders.

tree operator +(tree&& a, tree&& b); // core case
tree operator +(tree   a, tree   b) { return std::move(a) + std::move(b); }
tree operator +(tree   a, tree&& b) { return std::move(a) + std::move(b); }
tree operator +(tree&& a, tree   b) { return std::move(a) + std::move(b); }

Of course, you can use a macro to help generate the three (or seven) forwarding versions of each operator.

EDIT: if those calls are ambiguous or resolve to recursion, how about:

tree add_core(tree&& a, tree&& b);
tree operator +(tree&& a, tree&& b) { return add_core(std::move(a), std::move(b)); }
tree operator +(tree   a, tree   b) { return add_core(std::move(a), std::move(b)); }
tree operator +(tree   a, tree&& b) { return add_core(std::move(a), std::move(b)); }
tree operator +(tree&& a, tree   b) { return add_core(std::move(a), std::move(b)); }

EDIT: repro of the operator failure to use implicit conversions:

#include <iostream>

template<typename T>
class tree;

template<typename T> tree<T> add(tree<T> a, tree<T> b)
{
    std::cout << "added!" << std::endl << std::endl;
    return tree<T>();
}

template<typename T> tree<T> operator +(tree<T>   a, tree<T>   b) { return add(a, b); }

template<typename T>
class tree
{
public:
    tree() { }
    tree(const tree& t) { std::cout << "copy!" << std::endl; }
    tree(double val)    { std::cout << "double" << std::endl; }
    friend tree operator +<T>(tree a, tree b);
};

int main()
{
    tree<double>(1.0) + 2.0;
    return 0;
}

And version without templates where the implicit conversion works:

#include <iostream>

class tree
{
public:
    tree() { }
    tree(const tree& t) { std::cout << "copy!" << std::endl; }
    tree(double val)    { std::cout << "double" << std::endl; }
friend tree operator +(tree a, tree b);
};

tree add(tree a, tree b)
{
    std::cout << "added!" << std::endl << std::endl;
    return tree();
}

tree operator +(tree a, tree b) { return add(a, b); }

int main()
{
    tree(1.0) + 2.0;
    return 0;
}

Tiffin

making the double value constructor non-explicit might be a workable option... do the overloads you suggest produce a lot of unnecessary copies of l-values though? – Romanov

It depends on how you were planning to implement the non-move versions to begin with. I'm guessing you were going to need to make one copy of each non-move argument, and the forwarders I suggest do just that. Now, of course, copy constructing (during argument pass-by-value) followed by move is probably not quite as efficient as copy construction directly in the required place, but it shouldn't be much worse either. And once the compiler starts inlining it's hard to know if there is any difference at all. – Tiffin

Unfortunately, this elegant solution didn't work with VS 2010 RC. Depending on the usage case, the compiler complains about infinite recursion and ambiguous overloads. But I haven't tried gcc yet. – Romanov

RE: edit: That gets rid of infinite recursion, but VS10 complains error C2593: 'operator +' is ambiguous. Switching to const tree&'s fixes it, but then doubles wont bind. I'm starting to lose faith in the compiler here... – Romanov

Hmmm. Temporaries resulting from user-defined conversion definitely ought to bind to const references. You mentioned something about the conversion being explicit, which is the only thing I can think of to make the compiler correctly reject that. If you had accessible implicit converting constructors say so and I'll ask some of the VS2010 team members to explain why things work this way or confirm a bug. – Tiffin

@Ben Voigt: Hi Ben, I pasted a short test case, with the exact compile error in the comments: pastebin.com/6buJC2JP – Romanov

Your compile error is in template code. You completely neglected to mention templates in your original question, or any of the follow-on comments. I think you may have to provide the overloads which accept double if you are using templates, but you can still simply convert and then call the common implementation. Are you still having any problems with the r-value reference part of the code? – Tiffin

Answer 3

You're supposed to define them as member functions, so that you don't have to overload on lvalue or rvalue as the primary unit (which is unnecessary anyway) That is,

class Tree {
    Tree operator+ const (const Tree&);
    Tree operator+ const (Tree&&);
};

because the l or r valueness of the first is irrelevant. In addition, the compiler will automatically construct for you if that constructor is available. If tree constructs from double, then you can automatically use doubles here, and the double will be appropriately an rvalue. This is just two methods.

Electrograph

This actually works ok, except for the case with a double on the left hand side, e.g. 1.3 + tree(2.4), or am I missing something... – Romanov

It's common to declare operators as friend functions, that way you can overload on both operands freely, including on r-value vs l-value reference. – Tiffin

Writing double + tree is easy. friend operator+(double num, Tree&& ref) { return std::forward<Tree>(ref) + num; } That's good for both L and R values, thanks to std::forward. However, if Tree constructs from double, then this may not be necessary at all. You can declare as friend functions.. but I dislike it and only use that when it's impossible to use a member function. – Electrograph

Answer 4

I think the problem is that you have defined the operation with non const parameters. If you define

tree operator +(const tree& a, const tree& b);

There is no difference between r-value and l-value reference, so you don't need to define also

tree operator +(tree&&      a, const tree& b);

If in addition double is convertible to tree as tree x = 1.23; lets think, you don't need neither define

tree operator +(double      a, const tree& b){ return tree(a) + b; }

the compiler will do the work for you.

You will need to make the difference between rvalues and lvalues if the operator+ takes the tree parameter by value

tree operator +(tree a, tree b);

Yonne

"...There is no difference between r-value and l-value reference, so you don't need to define also ..." - I don't follow, could you elaborate? My understanding is the compiler will pick the closest overload, including the (rvalue,lvalue) case. – Romanov

@inverse: An r-value can bind to a const reference just fine. And since you only use const references, there is no real need for the r-value reference overloads. tree operator +(const tree& a, const tree& b); is capable of doing the work of tree operator +(tree&& a, const tree& b); just fine, unless you are doing something unexpected. – Kulun

"An r-value can bind to a const reference just fine." True, but then you lose the optimization of being able to take ownership of the internal structures instead of deep copying them. – Tiffin