C++ operator + and * non-const overloading

Question

I have the following tricky problem: I have implemented a (rather complicated) class which represents mathematical functions in a multiwavelet basis. Since operations like +, - and * are quite natural in this context, I have implemented overloaded operators for this class:

FunctionTree<D> operator+(FunctionTree<D> &inpTree);
FunctionTree<D> operator-(FunctionTree<D> &inpTree);
FunctionTree<D> operator*(FunctionTree<D> &inpTree);

There operators work finer in simple, non-chained operations, and even in some cases when chaining the operators. Statements like

FunctionTree<3> y = a * b + c;
FunctionTree<3> z = a * b + b;

compile and seemingly work fine. The first line is actually ok, but the second line causes valgrind to tell you grim stories about memory being freed inside already freed regions and uninitialized variables being accessed. Furthermore, a statement like

FunctionTree<D> y = a + b * c;

will not even compile, because I have not defined (an ambiguous operator taking an actual object, not a reference, as argument). Of course the solution is clear: All arguments, and methods ought to be made const, and perhaps even return a const object or reference. Unfortunately this is not possible, since NONE of the objects involved are constant during the operations! This may sound strange, but this is an unavoidable consequence of the mathematics involved. I can fake it, using const_cast, but the code is still wrong!

Is there a way to solve this problem? The only solution I have currently is to make the return objects const, thus effectively disabling the operator chaining.

Regards, .jonas.

Answer 1

You can use proxies instead of real values, and proxies can be constant, as they are not going to be changed. Below is a small example of how it might look like. Be aware that all the temporaries are still going to be created in that example but if you want to be smart, you can just save the operations, not the actual results of operations, and calculate only when someone wants to finally get result or a part of it. It might even speed up your code enormously as it helped APL

Also, you might want to make most of the members private.

#include <memory>
#include <iostream>

struct FunctionTreeProxy;
struct FunctionTree;

struct FunctionTreeProxy {
    mutable std::auto_ptr<FunctionTree> ft;

    explicit FunctionTreeProxy(FunctionTree * _ft): ft(_ft) {}
    FunctionTreeProxy(FunctionTreeProxy const & rhs): ft(rhs.ft) {}

    FunctionTreeProxy operator+(FunctionTree & rhs);
    FunctionTreeProxy operator*(FunctionTree & rhs);
    FunctionTreeProxy operator+(FunctionTreeProxy const & rhs);
    FunctionTreeProxy operator*(FunctionTreeProxy const & rhs);
};

struct FunctionTree {
    int i;
    FunctionTree(int _i): i(_i) {}
    FunctionTree(FunctionTreeProxy const & rhs): i(rhs.ft->i) {}

    FunctionTree * add(FunctionTree & rhs) {
        return new FunctionTree(i + rhs.i);
    }

    FunctionTree * mult(FunctionTree & rhs) {
        return new FunctionTree(i * rhs.i);
    }

    FunctionTreeProxy operator+(FunctionTree & rhs) {
        return FunctionTreeProxy(add(rhs));
    }

    FunctionTreeProxy operator*(FunctionTree & rhs) {
        return FunctionTreeProxy(mult(rhs));
    }

    FunctionTreeProxy operator+(FunctionTreeProxy const & rhs) {
        return FunctionTreeProxy(add(*rhs.ft));
    }

    FunctionTreeProxy operator*(FunctionTreeProxy const & rhs) {
        return FunctionTreeProxy(mult(*rhs.ft));
    }
};

FunctionTreeProxy FunctionTreeProxy::operator+(FunctionTree & rhs) {
    return FunctionTreeProxy(ft.get()->add(rhs));
}

FunctionTreeProxy FunctionTreeProxy::operator*(FunctionTree & rhs) {
    return FunctionTreeProxy(ft.get()->mult(rhs));
}

FunctionTreeProxy FunctionTreeProxy::operator+(FunctionTreeProxy const & rhs) {
    return FunctionTreeProxy(ft.get()->add(*rhs.ft));
}

FunctionTreeProxy FunctionTreeProxy::operator*(FunctionTreeProxy const & rhs) {
    return FunctionTreeProxy(ft.get()->mult(*rhs.ft));
}

int main(int argc, char* argv[])
{
    FunctionTree a(1), b(2), c(3);

    FunctionTree z = a + b * c;

    std::cout << z.i << std::endl;

    return 0;
}

Answer 2

If your objects are 1GB (I guess that's memory they allocate on the heap, not their actual sizeof size), you probably shouldn't be supporting these operators on them. The problem is that your examples of operator chaining more or less presume immutable objects as its basic model of "what's going on", and create lots of temporaries to serve as intermediate results. You can't count on the compiler to be able to re-use the space efficiently. But you also can't copy 1GB objects willy-nilly.

Instead, you should only support the various assigning operators. Then your client instead of writing:

y = a * b + c;

which is liable to create enormous temporaries, should instead write:

// y = a * b + c
y = a;
y *= b;
y += c;

That way the user can keep a lid on things. It's easily seen that no temporaries are created, and you won't accidentally write a simple line of code that requires 18GB to run. If you want to do:

y = a * b + c * d;

then your code must explicitly note that a temporary result is required here (assuming you can't trash any of a, b, c, d):

// y = a * b + c * d
y = a;
y *= b;
{
   FunctionTree x = c;
   x *= d;
   y += x;
}

but if the caller happens to know that for example c isn't needed after this, you can explicitly do:

// y = a * b + c * d  [c is trashed]
c *= d;
y = a;
y *= b;
y += c;

In theory the compiler might be up to working all this stuff out for itself based on big expression with the chained operators, and data-flow analysis to show that c is unused. Good compilers with lots of optimisation switched on are good at this for integer arithmetic, so the machinery is there. In practice I wouldn't count on it. If the compiler cannot prove that the constructor and destructor of FunctionTree have no observable side-effects, then its ability to skip them is limited to the specific cases of legal "copy elision" in the standard.

Or you could look at the C interface to GMP to see how this is done without operator overloading at all. All the functions there take an "out parameter", which the result is written to. So for example if x is a huge multiple precision integer, that you want to multiply by 10, you choose whether to write:

mpz_mul_ui(x, x, 10); // modifies x in place, uses less memory

or:

mpz_t y;
mpz_init(y);
mpz_mul_ui(y, x, 10); // leaves x alone, result occupies as much memory again.

Answer 3

There is no simple solution to this problem. Your binary operators are (correctly) producing nameless temporary objects - such objects cannot be bound to non-const reference parameters.

One possible way round this is to forgo the chaining of operators - for a class X:

X a;
X b;
X c = a * b;
X d;
X e  = c + d;

Another (rather horrible) solution is to make the the data members of the class mutable - that way they would be logically const but physically alterable. You would then make your parameters be const references. Like I said, this is horrible and may cause other problems.

Answer 4

"...NONE of the objects involved are constant during the operations! This may sound strange..." No it doesn't sound strange, it sounds wrong. If your operators modify the objects in a way that is observable from the outside, then that's an abuse of operator overloading. If the objects are modified, because results are cached, make the cache mutable, so functions modifying the cache can still be declared const.

Answer 5

Pass the arguments by value rather than by reference?

EDIT: You may want to use += -= *= instead.