views:

684

answers:

5

I'm writing this question with reference to this one which I wrote yesterday. After a little documentation, it seems clear to me that what I wanted to do (and what I believed to be possible) is nearly impossible if not impossible at all. There are several ways to implement it, and since I'm not an experienced programmer, I ask you which choice would you take. I explain again my problem, but now I have some solutions to explore.

What I need

I have a Matrix class, and I want to implement multiplication between matrices so that the class usage is very intuitive:

Matrix a(5,2);
a(4,1) = 6 ;
a(3,1) = 9.4 ;           
...                   // And so on ...

Matrix b(2,9);
b(0,2) = 3;
...                   // And so on ...

// After a while
Matrix i = a * b;

What I had yesterday

At the moment I overloaded the two operators operator* and operator= and until yesterday night the were defined in this way:

Matrix& operator*(Matrix& m);
Matrix& operator=(Matrix& m);

The operator* instantiates a new Matrix object (Matrix return = new Matrix(...)) on the heap, set the values and then just:

return *result;

What I have today

After the discussion I decided to implement it in a "different way" to avoid the user to be bothered bother by pointers of any type and to keep the usage unchanged. The "different way" is to pass the returning value of operator* by value:

Matrix operator*(Matrix& m);
Matrix& operator=(Matrix& m);

The operator* instantiates return on the stack, set the values and then return the object.

There is a problem with this approach: it doesn't work. The operator= expects a Matrix& and operator* returns a Matrix. Moreover this approach doesn't look so good to me for another reason: I'm dealing with matrices, that can be very large and the aims of this library were to be 1) good enough for my project 2) fast, so probably passing by value should not be an option.

Which solutions I have explored

Well, following the suggestions in the previous discussion I read some stuff about smart pointers, they look great but I can't still figure out how to solve my problem with them. They deal with memory freeing and pointer copying, but I'm basicly using references, so they don't look the right choice for me. But I may be wrong.

Maybe the only solution is to pass by value, maybe I can't get both efficiency and a good interface. But again, you're the expert, and I would like to know your opinion.

+9  A: 

The problem you are having is that the expression a * b creates a temporary object, and in C++, a temporary is not allowed to bind to a non-constant reference, which is what your Matrix& operator=(Matrix& m) takes. If you change it to:

Matrix& operator=(Matrix const& m);

The code should now compile. As well as the obvious benefit of producing compilable code :), adding the const also communicates to your callers that you will not be modifying the argument m, which may be helpful information.

You should also do the same for your operator*():

Matrix operator*(Matrix const& m) const;

[EDIT: The additional const at the end indicates that the method promises not to alter *this, the object on the left-hand side of the multiplication, either. This is necessary to cope with expressions such as a * b * c -- the subexpression a * b creates a temporary and won't bind without the const at the end. Thanks to Greg Rogers for pointing this out in the comments.]

P.S. The reason why C++ does not allow a temporary to bind to a non-constant reference is because temporaries exist (as the name suggests) for only a very short time, and in most cases, it would be a mistake to attempt to modify them.

j_random_hacker
I agree with this -- make as much use of const as possible, and then rely on things like RVO (return value optimization) to avoid as much extraneous copies as possible.Of course, if you need better performance, you could take a look at copy-on-write semantics as mentioned by peterchen.
Sumudu Fernando
second snippet should be Matrix operator*(Matrix const actually if you are going to implement it as a member operator with const correctness.
Greg Rogers
You're right Greg. I've edited the post to reflect this.
j_random_hacker
+9  A: 

You should really read Effective C++ by Scott Meyers, it has great topics on that. As already said, the best signatures for operator= and operator* are

Matrix& operator=(Matrix const& m);
Matrix operator*(Matrix const& m) const;

but I have to say you should implement multiplication code in

Matrix& operator*=(Matrix const& m);

and just reuse it in operator*

Matrix operator*(Matrix const &m) {
    return Matrix(*this) *= m;
}

that way user could multiply without creating new matrices when she wants to. Of course for this code to work you also should have copy constructor :)

vava
+1, both good suggestions. (Although actually, unless the OP is doing dynamic memory allocation inside Matrix, it's better to have *neither* an operator=() nor a copy ctor and just use the defaults.) Just a little thing, I think you need a "*" before "this" in your last code snippet.
j_random_hacker
Thanks for the correction, it was stupid of me.
vava
Sumudu Fernando
I agree that it's nicer to have a *= first, but how would you define that for a matrix, without making a copy (remember, each value is used several times)
roe
Good point roe, hadn't thought of that... :)
j_random_hacker
A: 

Yes, your suggestion are both good, and I admit that I didn't know the temporary object issue with non-const references. But my Matrix class also contains facilities to get the LU factorization (Gaussian Elimination):

const Matrix& get_inverse();
const Matrix& get_l();
const Matrix& get_u();
const Matrix& get_p();

Are all but const since they all call (if necessary):

void lupp();

That updates the cached L, U and P. The same stands for get_inverse() that call lupp() and also sets Matrix* Matrix::inverse. This causes problem with the:

Matrix& operator=(Matrix const& m);
Matrix operator*(Matrix const& m);

technique.

tunnuz
Do you call any of those 4 methods inside your operator=() or operator*()? If not, then you'll have no problems -- just declaring a parameter const does not make the argument passed to it const if it was not already!
j_random_hacker
If you do call any of those methods from either operator=() or operator*(), then, since you say L, U and P are "cached" values, it's probably safe to declare them mutable, meaning they can be modified even in a const object. That is what the mutable keyword was designed for.
j_random_hacker
Just don't call them on "m", "this" is not const. Or mark the cache as mutable.
vava
+3  A: 

Note: Start with Vadims suggestions. The following discussion is moot if we talk about very small matrices only, e.g. if you limit yourself to 3x3 or 4x4 matrices. Also I hope I am not trying to cram to much ideas down on you :)

As a matrix is potentially a heavy object, you should definitely avoid the deep copies. Smart pointers are one utility to implement that, but they don't solve your problem out of the box.

In your scenario, there are two common approaches. In both cases, any copy (like a=b), only copies a reference, and increments the reference counter (that's what smart pointers can do for you).

With Copy On Write, the deep copy is delayed until a modification is made. e.g. calling a member function like void Matrix.TransFormMe() on b would see that the actual data is referenced by two objects (a and b), and create a deep copy before doing the transformation.

The net effect is that your matrix class acts like a "normal" object, but the number of deep copies actually made is reduced dramatically.

The other approach are Immutable Objects where the API itself never modifies an existing object - any modification creates a new object. So instead of a void TransformMe()' member transforming the contained matrix, Matrix contains only a Matrix GetTransformed()`member, returning a copy of the data.

Which method is better depends on the actual data. In MFC, CString is copy-on-write, in .NET a String is immutable. Immutable classes often need a builder class (like StringBuilder) that avoids the copies of many sequential modifications. Copy-On-Write objects need careful design so that in the API it is clear which member modify the internal members, and which return a copy.

For matrices, since there are many algorithms that can modify the matrix in-place (i.e. the algorithm itself does not need the copy), copy-on-write might be the better solution.

I've once tried to build a copy-on-write pointer on top of boost smart pointers, but I haven't touched it to figure out threading issues etc. Pseudocode would look like this:

class CowPtr<T>
{
     refcounting_ptr<T> m_actualData;
   public:
     void MakeUnique()
     {
        if (m_actualData.refcount() > 1)
           m_actualData = m_actualData.DeepCopy();
     }
     // ...remaining smart pointer interface...
}

class MatrixData // not visible to user
{
  std::vector<...> myActualMatrixData;
}

class Matrix
{
  CowPtr<MatrixData> m_ptr; // the simple reference that will be copied on assignment

  double operator()(int row, int col)  const
  {  // a non-modifying member. 
     return m_ptr->GetElement(row, col);
  }

  void Transform()
  {
    m_ptr.MakeUnique(); // we are going to modify the data, so make sure 
                        // we don't modify other references to the same MatrixData
    m_ptr->Transform();
  }
}
peterchen
I'm using plain C++ under UNIX. Once I get my library compiling and working with the passing by value mechanism I will think about optimizations. Thank you for the suggestion.
tunnuz
+3  A: 

… Are all but const since they all call (if necessary):

void lupp();

That updates the cached L, U and P. The same stands for get_inverse() that call lupp() and also sets Matrix* Matrix::inverse. This causes problem with the:

Matrix& operator=(Matrix const& m);
Matrix operator*(Matrix const& m);

technique.

Please explain how that causes problems. It should't, usually. Additionally, if you use member variables to cache temporary results, make them mutable. Then you can modify them even in const objects.

Konrad Rudolph
This suggestion was very useful! I'm trying to solve some problems, but I think this is the right way.
tunnuz