Sign in to follow this  

using operators with polymorphism in C++

This topic is 2808 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a Vector class that represents a vector which can have any number of elements. It overloads the obvious operators like + and -. I'd like to try different implementations of the operators so I was thinking of making an abstract vector interface called IVec and deriving all of the vectors from that. But the problem is that if I'm working with pointers to the IVec class, then in order to use the operators I'll have to dereference all the pointers. For example, if BasicVec derives from IVec then I'd have to do something like this:
IVec* v1 = new BasicVec();
IVec *v2 = new BasicVec();
//initialize vectors
IVec* v3 = (*v1) + (*v2);


It doesn't look good to have to dereference the pointers just to use the + operator. This could be phrased as a more general question: How can operators be implemented in a polymorphic base class without having to dereference the pointers to the base class whenever the operators are used? Thanks

Share this post


Link to post
Share on other sites
The problem is that operators for pointers are already defined, and need to be compatible with C. Operators with pointers are pointer arithmetic.

Or, if a, b and c are all pointers to something, the following:
c = a + b;
is pointer arithmetic, and that cannot be changed, or it would break every code in existence.

Finally, there's the life time problem, since operators need to return something.

Quote:
How can operators be implemented in a polymorphic base class without having to dereference the pointers to the base class whenever the operators are used?


Don't overload operators. Avoid polymorphism as much as possible, especially for things like this. C++ prefers different approach.

Finally, since C++ doesn't have multiple dispatch, dealing with polymorphism this way gets really tedious really fast. Just use concrete types. There is really no reason to use operator-like operations on polymorphic classes.

If it is, then it can be expressed via pointer on RHS, while others remain concrete types (for delegate-like syntax or something).

Quote:
I have a Vector class that represents a vector which can have any number of elements.

This is simply the wrong way to approach the design. It may work in managed languages, but it doesn't in C or C++. Standard library offers complete, CS-proved methodology, where rather than exposing functionality via inheritance, they provide typed iterators.

But it's still simply too bulky solution vs. the simplicity of STL.

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
How can I use concrete types if I want to be able to easily change the implementation?

STL and <algorithm>. It's compile-time polymorphism.

If run-time polymorphism is needed, it can be implemented using at a different level of abstraction while using STL containers.

Share this post


Link to post
Share on other sites
I'm sorry, I don't understand. How can STL and <algorithm> help with a mathematical vector class? (I now see that I wasn't clear before, I'm trying to implement a mathematical vector, not a container class)
Can you explain what you mean when you say that STL and <algorithm> are compile time polymorphism?
Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
I now see that I wasn't clear before, I'm trying to implement a mathematical vector, not a container class
Thanks.


I think it would be easier to help if we knew a little more about what you want to do. What kind of vectors do want to have besides BasicVec? What kind of polymorphic behavior do you want?

Share this post


Link to post
Share on other sites
Quote:
Original post by jwezorek
...
I think it would be easier to help if we knew a little more about what you want to do. What kind of vectors do want to have besides BasicVec? What kind of polymorphic behavior do you want?


I want to experiment with both different ways to store the vector and with different ways to implement the various operators. For example, I'd like to try both the standard (basic) way of doing matrix algebra, and also more advanced techniques like meta-programming.
Thanks

Share this post


Link to post
Share on other sites
How do the different implementations of your BasicVec differ? Are they different dimensions of a vector? Then you most probably want a compile time error anyway if you use two different vectors in an equation.


IVec* v2d = new My2DVector(5,5);
IVec* v3d = new My3DVector(2,2,2);
IVec* v = (*v2d) + (*v3d); // I bet you would like to get this caught by the compiler


If that's your design, you should go for templates (or better, have a closer look into the STL to reuse code).

If you only have different implementations for the same mathematical vector (say... one in polar coordinates, an other in carthesian) but both versions could be used together in any equation, then your design is not the worst to start with.

In this case, I recommend you put your implementation into a common (and concrete) Vector class. (That's the "adding one indirection solves many problems in computer science" - thingie ;)


class MathVector
{
IVec* impl;
MathVector(double x, double y, double z) : impl(new CarthesianVec(x,y,z) {}
...
};
MathVector operator+(const MathVector& rhs, const MathVector& lhs)
{
...
}


You should consider making the member "impl" a shared pointer (std::tr1::shared_ptr) so you don't have to implement copy constructor and
assignment operator of MathVector.

Ciao, Imi.

Share this post


Link to post
Share on other sites
Quote:
Original post by imi
How do the different implementations of your BasicVec differ? Are they different dimensions of a vector? Then you most probably want a compile time error anyway if you use two different vectors in an equation.


IVec* v2d = new My2DVector(5,5);
IVec* v3d = new My3DVector(2,2,2);
IVec* v = (*v2d) + (*v3d); // I bet you would like to get this caught by the compiler


If that's your design, you should go for templates (or better, have a closer look into the STL to reuse code).

The different implementations would differ mainly in the way the vector is stored, and in the way the operators are implemented.
How would I use templates to create the vectors? Would I have one templated vector class which is initialized with storage and operator options?
Thanks

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Or, if a, b and c are all pointers to something, the following:
c = a + b;
is pointer arithmetic

No. Pointer arithmetic is one of the following:

pointer + ptrdiff_t
pointer - ptrdiff_t
pointer - pointer

Adding two pointers does not make any sense whatsoever.

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
But the problem is that if I'm working with pointers to the IVec class, then in order to use the operators I'll have to dereference all the pointers.


Then don't work with pointers. Work with references instead (i.e. just write the values, and have your overloads accept and return references where appropriate, following the usual conventions). References were actually added to the language more or less specifically to support operator overloading. They allow you to get 'virtual' behaviour for function calls (including operator overloads), too.

However, keep in mind that C++ does not have multiple dispatch built in. In 'x + y', only the exact derived type of x will matter for looking up the implementation, unless you explicitly re-dispatch, e.g.


IVec IVec::operator+(const IVec& rhs) {
return rhs.addedToBase(*this);
}
// Similarly for each derived type, naming a different helper

IVec IVec::addedTo(const IVec& lhs) {
// protected virtual; does the work
// SImilarly for each derived type, accepting a parameter of that type
}


But honestly, all of this is kind of moot, because operator overloads generally belong to simple mathematical types, and simple mathematical types have no reason for any polymorphic behaviour.

Share this post


Link to post
Share on other sites
Quote:

You should consider making the member "impl" a shared pointer (std::tr1::shared_ptr) so you don't have to implement copy constructor and
assignment operator of MathVector.

That is dangerous. Leaving aside the fact that I wouldn't bother using any kind of runtime polymorphism for this, using a shared_ptr<> in the implementation means that Vector instances no longer act like simple mathmatical types, which can canuse unexpected and bizarre behaviour. I really wouldn't expect vector types to alias one another, its quite a violation of the principle of least surprise.

Something more appropriate for such use cases might be mr_edd's value_ptr<>.

Share this post


Link to post
Share on other sites
Thanks for all the helpful replies. It seems like I shouldn't be using polymorphism for basic types. Maybe it'd be better to use templates? I could make a class with a signature like:
template<class Storage, class Math> Vector;
and then to create a vector you'd pass a "Storage" class that has getter and setter functions, and a "Math" class that uses the storage class to do the math.
Is that a good idea? Is there a better way to use templates?
Thanks

Share this post


Link to post
Share on other sites
Why do you need more than one kind of Vector at all? Or at worst, more than a few small sizes? Are you writing some kind of quantum-mechanics simulator or something? Nearly all practical applications don't have to worry about more than 3 dimensions of space, i.e. 3-element vectors or 4x4 matrices (due to homogeneous coordinates). Maybe you'd want a 4-element vector to represent a row or column of a 4x4 matrix, but that's about it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Why do you need more than one kind of Vector at all? Or at worst, more than a few small sizes? Are you writing some kind of quantum-mechanics simulator or something? Nearly all practical applications don't have to worry about more than 3 dimensions of space, i.e. 3-element vectors or 4x4 matrices (due to homogeneous coordinates). Maybe you'd want a 4-element vector to represent a row or column of a 4x4 matrix, but that's about it.


I'm writing a rigid body simulator which solves large systems of equations.
In these equations, the system state and forces are represented by one long column vector. They have to be calculated together since they all influence each-other. In addition, my integrator also takes one column vector containing the states of all the bodies and one containing all of the derivatives.

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l

I'm writing a rigid body simulator which solves large systems of equations.
No physics or linear algebra ever needed or profited from use of polymorphism.

Quote:
In these equations, the system state and forces are represented by one long column vector.
Which is what std::vector is used for.

Quote:
They have to be calculated together since they all influence each-other. In addition, my integrator also takes one column vector containing the states of all the bodies and one containing all of the derivatives.
Which is also what std::vector is used for. The storage at least. Contents do not need to be polymorphic.

As a matter of fact, since the 1960s, all that was ever needed for solving these problems on computers was tape, or later an array.

Share this post


Link to post
Share on other sites
linear algebra is based on the concept of polymorphism. vector spaces are written over fields, an extremely abstract concept. really all of linear algebra has been generalized to where all you have to do is have objects that satisfy a few requirements and you slip them in there.

abstract algebra
vector spaces in linear algebra.

for instance, you can use continuous real valued functions as your vectors. from a linear algebra point of view, they are the same.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Which is what std::vector is used for.

But what if I want to apply various operators to my vectors? Don't I have to write a new class to do that?

Share this post


Link to post
Share on other sites

For a more advanced vector implementation using templates you can look at the eigen vector library http://eigen.tuxfamily.org/index.php?title=Main_Page

For large matrices the overhead for one virtual call is probably negelable. So if you need to be able to change storage and math at runtime, it is doable. But if you intend to implement operators using virtual methods it will add considerable overhead.

For a nice implementation I would do as imi suggests buy using a concrete wrapper which keeps track of a pointer.

If you need to do operators between different kinds of storage/math vectors then you need to look at the double dispatch pattern as Zahlman suggests.

If you dont need to be able to change implementation at runtime, then it will probably be better to manage without virtuals.


typedef SparseMatrix EquationMatrix;

Vector vector(n);
EquationMatrix sparseEquations(n, n);

// ...

Vector resultVector = solve(sparseEquations, vector);


Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l

But what if I want to apply various operators to my vectors? Don't I have to write a new class to do that?


An operation on a matrix creates a matrix. The dimensions of the result and inputs may differ, but they are still all matrices.

Multiplication of two matrices is always done the same, using same algorithm. So is addition and every other operation. There is no polymorphic behavior.

A matrix is defined as such:
class Matrix {
int m,n;
vector<double> elements; // m*n elements
};
The handful of operators that need to be implemented then all look the same:
Matrix operator*(Matrix & a, Matrix & b) {
// verify dimensions of a and b
Matrix result; // set dimensions of the resulting matrix
// compute elements of the result
return result;
};


The more interesting computations (transpose, cross, solve) do not have adequate operator equivalents, so they end up being plain old member functions:
Matrix m;
Matrix n = m.transpose();
Matrix o = n.cross(m).transpose();
// and so on



Note that since this type of calculations is very important, it has been studied for the last 50 years, and there exist robust and well tested libraries (LAPACK et al.), some with hardware acceleration.

Share this post


Link to post
Share on other sites
Quote:
Original post by ibebrett
linear algebra is based on the concept of polymorphism...


But the kind of polymorphism you are talking about here is compile-time polymorphism. You can have a vector in third-order-polynomial-function space, but you don't normally have vectors in second-order-polynomial-function-cross-integer space. And even if you do, when you take, say, a dot product of vectors, they come from the same space, and you know what space they're from ahead of time.

Quote:
Original post by daniel_i_l
Quote:
Original post by Antheus
Which is what std::vector is used for.

But what if I want to apply various operators to my vectors? Don't I have to write a new class to do that?


No, you just write operator overloads as free (non-member) functions, and implement them using the public interface of the vector.

Quote:
Original post by Antheus
A matrix is defined as such:


Or you can use boost::multi_array.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Or you can use boost::multi_array.


If you're going to use boost for matrices, you might as well use boost::numeric::ublas::matrix<>

Share this post


Link to post
Share on other sites

This topic is 2808 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this