[RESOLVED] Forward declarations and covariate return types

[cooperised]

Hi,

I'm having difficulty finding a way to implement part of a matrix library I'm writing. Here's a distilled version of the code, to demonstrate the problem:

class Vector {
public:
  virtual Vector *getTranspose() = 0;
}

class RowVector : public Vector {
public:
  virtual ColumnVector *getTranspose();
}

class ColumnVector : public Vector {
public:
  virtual RowVector *getTranspose();
}

The problem, as you can probably see, is one of forward declaration. I want to override the getTranspose() method of Vector to return a pointer to a RowVector or ColumnVector as appropriate using covariate return types, which is perfectly legal. But the ColumnVector and RowVector classes need to be aware of each other.

Clearly, if I were not dealing with covariate return types, I could just insert a forward declaration of ColumnVector at the top somewhere. But for the above snippet to compile, the compiler needs to be aware not only that ColumnVector exists, but that it inherits from Vector - and I can't find a way to declare this fact, because ': public Vector' is part of the definition of ColumnVector, not its declaration.

Any ideas? Am I missing something? I feel sure that I must be, because I'd be able to implement this interface without any problems in a whole bunch of other OO languages...

Cheers
cooperised

[TheCPUWizard]

Vector.h

class Vector {
public:
  virtual Vector *getTranspose() = 0;
}

RowVector.h

#include "vector.h"
class ColumnVector;
class RowVector : public Vector {
public:
  virtual ColumnVector *getTranspose();
}

ColumnVector.h

#include "vector.h"
class RowVector;
class ColumnVector : public Vector {
public:
  virtual RowVector *getTranspose();
}

WHERE is the problem?

[treuss]

WHERE is the problem?

ColumnVector.h:5: error: invalid covariant return type for `virtual RowVector* ColumnVector::getTranspose()'.

Just as the OP describes the problem: A forward declaration does not give the compiler sufficient information to see that the class is in fact a valid covariant return type.

[cooperised]

@TheCPUWizard,

Thanks for your prompt response. But try compiling your example and you will see the problem. The following (for example) is not sufficient:

#include "vector.h"
class ColumnVector;
class RowVector : public Vector {
public:
  virtual ColumnVector *getTranspose();
}

Compilation will fail because getTranspose() overrides a superclass method, and so its return type must be a subtype of the return type declared by the superclass method, ie. a subtype of Vector. Since the compiler doesn't know from the simple forward declaration that ColumnVector inherits from Vector, it will complain that the return type is not appropriate (error: invalid covariant return type for 'virtual RowVector* ColumnVector::getTranspose()').

Does this make it any clearer?

Thanks
cooperised

[TheCPUWizard]

Missed that.

One approach is to actually use a template

[cooperised]

Missed that.

Hehe, don't worry, it's nearing the end of the working day (or at least, it is here)!

One approach is to actually use a template

That looks interesting, thanks. Would you mind posting a quick example of how to use the technique in my context? It would really help me to understand what's going on. I'm (relatively) new to C++, but not to C or to many other languages (both procedural and OO) so you don't need to include masses of extra information, but a code snippet based on my original post, plus a very quick description of how the technique allows me to postpone the full declaration of the derived classes, would be extremely helpful.

Thanks,
cooperised

[TheCPUWizard]

Best right now I can do is a simple explanation (not by a C++ environment to get the details for yous specifics.

Remeber that minimal (but critical) processing is done when encountering a template. SO:

template<typename A, typename B>
class Foo
{
      A F(B x) { return x; }
};

will definately compile. But when we go to instanciate it:

Foo<int, double> f;

ADDITIONAL procssing will be done, and an errror generated because you can not implicitly cast double to int.

One thing that IS processed at the template declaration is that its base class is.

template<typename A>
class Foo : public Base
{
     A bar();
}

is sufficent to notify the compiler that (all) specializations of Foo are drived from Base. However the termination of "A is NOT processed. So, the compiler can get the previously missing information about co-variance without having to actually process the detailed header:

Similar to:

#include "vector.h"
template<typename OTHER_TYPE>
class RowVector : public Vector {
public:
  virtual OTHER_TYPE *getTranspose();
}

template<typename OTHER_TYPE>
class ColVector : public Vector {
public:
  virtual OTHER_TYPE *getTranspose();
}

Now we know the inheritance (and hence covariance) relationships
so:

RowVector<ColVector> rv;
ColVector<RolVector> cv;

Can properly be utilized.

[treuss]

Now we know the inheritance (and hence covariance) relationships
so:

RowVector<ColVector> rv;
ColVector<RolVector> cv;

Can properly be utilized.

I guess there is something more tricky involved here, as this would have to be something like

RowVector<ColVector<RowVector<ColVector<.....> > > > > rv;

But I admid I had to try out your suggestion before actually seing that problem

[treuss]

OK, some trying out and I made it to compile by templating only one of the two:

class Vector {
public:
  Vector(int a, int b, int c) { x=a; y=b; z=c; }
  virtual Vector *getTranspose() = 0;
protected:
  int x,y,z;
};

template<typename TT>
class _RowVector : public Vector {
public:
  _RowVector(int a, int b, int c) : Vector(a,b,c) {}
  virtual TT *getTranspose();
};

class ColumnVector : public Vector {
public:
  ColumnVector(int a, int b, int c) : Vector(a,b,c) {}
  virtual _RowVector<ColumnVector> *getTranspose();
};

typedef _RowVector<ColumnVector> RowVector;

template<typename TT>
TT * _RowVector<TT>::getTranspose() {
  return new TT(x,y,z);
}

RowVector * ColumnVector::getTranspose() {
  return new RowVector(x,y,z);
}

int main() {
  RowVector rv(1,2,3);
  ColumnVector * cvp = rv.getTranspose();
  ColumnVector cv(5,6,7);
  RowVector * rvp = cv.getTranspose();
}

This would make a nice exam exercise

[Lindley]

Erg. See, this is the point at which I would take a step back and wonder if I wasn't going about the problem all wrong. High-level coding is supposed to make the logic clearer, but this looks about as opaque as anything I've seen.......

C++ is a great language, but if you have to jump through these sorts of hoops to do something this conceptually simple, I'd say it qualifies as a broken aspect of the language.

Myself, I'd probably just define a Matrix class, and then define RowVector and ColVector as specializations of it.

[TheCPUWizard]

Erg. See, this is the point at which I would take a step back and wonder if I wasn't going about the problem all wrong. High-level coding is supposed to make the logic clearer, but this looks about as opaque as anything I've seen........

Have your read "Modern C++ Design"? I typically recommend they wear a helmet to reduce the mess when their brains explode...yet it is one of the driving reference books in most top-notch development shops.

Regarding the use of templates to break cyclic definitions, it is a fairly well established process and is discussed frequently on the "official" moderated C++ language newsgroup.

covariant return types are a relatively new technique (primarily becuase wide spread compiler support is recent) They do introduce new features and techniques which may seem "unusual" but the variety of situations that were previously "hacked" together (multiple methods, explicit casting) that they directly address really [IMPO] has a major net (no "dot" o capitalization ) benefit.

[Graham]

Applying my favourite dictum of "if it's proving hard to do, you're probably doing it wrong":

Why do you need it to be a virtual function? It strikes me that Vector* Vector::getTranspose() doesn't really make sense - if you have an arbitrary vector, then the result of this function will be an arbitrary vector: you have no way of sorting things out. Presumably, you're separating row and column vectors so that you can do things like enforce correct multiplication by ensuring that one of each type is provided. If so, then a Vector object doesn't help.

Also, I'd personally be a bit unhappy about returning a pointer rather than an actual vector object, since you're entering the realms of memory management - someone's got to dispose of the created vector, and you'll get into real trouble with statements like "func(*v.getTranspose());"

My feeling is that getTanspose() doesn't really work above the level of row- and column-vector, so I'd just leave it out of the base class and declare it non-virtual in the derived classes (returning an object, not a pointer), thus completely sidestepping the problem.

[TheCPUWizard]

100% agreement with your dictum

But there are times when doing certain mathematical modeling algorithms, where you need the "normal" vector of information to the current axis, regardless of which axis is current.

This hierarchy directly support this functionallity.

OF course this can be done simply using a "Vector" as the return type, but then you introduce casting when the operation is specific to an axis, and you want compile time safety.

So to get the general and specific vectors, you create two differently named methods. One virtual with the base as the return type, and one non-virtual with the specific return type.

Now you have introduced duplication (albiet trivial in most cases).

This brings us to one of my favorites:

Always strive to use the most approriate approach given full knowledge of your situation!

For example, in a general application with mid-level programmers, I will ALWAYS advocate STL over "Raw" or "Custom". But if I am working on a real-time project (typically embedded or industrial automation system) AND I know the developers have good memory management expertise, AND have a solid history of using "Raw" techniques AND believe that optimization will impact a relatively significant part of the job...then my architectural focus on STL solutions is greately reduced.

In this case, if the development team [even a team of 1] is already experienced at C++ and has a good solid grasp of all of the ramifications, there is no issue with using covariant returns..but for a beginner, it would be a completely different recommendation.

[cooperised]

Thanks for all your help, especially CPUWizard and treuss. I'm marking this thread as resolved. I'd managed to get something very similar to treuss's solution on my own after thoroughly reading the link posted early on by CPUWizard, so it was great to return here and find that I was on the right track. So thanks for that, and thanks also to CPUWizard for the description of what happens to the compiler when it encounters a templated class.

I'd like to take the opportunity to respond to the emerging debate about whether this workaround is necessary because of failings in my design. I would, in general, wholeheartedly agree with Graham's dictum - but not always. It is possible for languages to implement features badly, especially those features that have been added to the language retrospectively. (If any of you are also Java developers, see the ungodly mess that is Java generics for a good example). In this case, my desired inheritance and covariance structure is syntactically and semantically accurate, and entirely free of logical inconsistencies; its meaning is clear, and the inability of the compiler to interpret it correctly without invoking an unnecessary (in this context) language feature to influence its behaviour indicates to me that in this case it's the language that's at fault, not me.

For those who are interested, the reason that the 'getTranspose()' method is virtual is that the much-simplified inheritance tree I presented when asking my original question is part of a larger one that includes non-square, square, symmetric, and diagonal matrices. Transposition is a valid operation for all of these types, but since their implementations vary widely for efficiency (interface and implementation are kept well separated) the transpose operation must be virtual. Graham, there are many reasons for the constructive call (pointer return). For one, the intended application of this library is likely to generate very large matrices, and we wish to avoid passing them around on the stack; for another, the ability to apply polymorphism to the returned value is important in context. Additionally, the covariant return relies on a pointer or reference as a return type of course, and as CPUWizard pointed out, this approach saves on duplication. I agree that constructive calls can lead to memory leaks for the unwary, but my team (of two!) and I considered that they represented the least of the available evils.

Once again, thanks to all for your help with this.
cooperised

[TheCPUWizard]

One "final" suggestion [I deliberately held off until the main topic was resolved].

STRONGLY consider using some type of "smart" pointer rather than a "Raw" pointer.

The benefits can be dramatic, and the risks minimal.

Imagine having thousands of matrices/vectors floating around with just a small "leak" factor due to a bug......