A polymorphism question

[Falco Girgis]

Im a little slow on the uptake on this buuuuut...

Code: Select all

class Ship
{
     protected:
     int Health; //For ex.
      public:
      float move(float gotoX, float GotoY); //For example demonstarting what you could have for more abstract methods.
};

class ShipB : public Ship
{
   protected:
      int Score; //This could have more things that would be more for the player.
};
class Player : public ShipB
class EShip : public Ship

Idk if that's the best solution.

I'm not so sure you understood the problem.

It was a matter of knowing when you can cast a pointer to a parent class down to a subclass to access subclass-specific data.

[THe Floating Brain]

Oh got it.

[Khearts]

The reason why I have vector<Ship*> instead of vector<EShip1*> , vector<Player*> , and vector <PShip1*> was to conveniently organize all heap-created objects and iterate through them later with no problem. Over the day, I thought of an alternative design that may solve my problem.

I should have presented my classes in more detailed but here is what I currently have

Ship
--Player
--EShip1
--BossShip1
--PShip1

I needed to include both EShip1 and BossShip into a single vector and keep Player and PShip1 into a single vector. Here's my alternative solution that I thought of today that "kinda" solves my issue:

Ship
--PShip
----Player
----PShip1
--EShip
----EShip1
----BossShip1

Then at this point I can make a vector of PShip* and EShip* and not have to worry about EShips having the functionality and data that PShips have. However, if I'm giving a score to my Player ship, I will be giving a score to my other PShips. I'll probably add in a feature that displays a total score for the sum of the Player's ship with the other friendly PShips.

I may have to come back later and see the other styles mentioned (like casting, etc...), but once again, I think that's probably a bit overkill for what a small app and a lightly experienced coder needs.

I do appreciate all of the other suggestions provided; many of them, however, was a bit more advanced than what I was expecting.

[EccentricDuck]

You could just use a single vector to contain your ships and have an additional pointer to your player ship where you call player specific code (like retrieving/modifying score). That way, you can deal with physics, rendering, collision, etc; with a shared list, and just act on the pointer when you need to deal with the player directly. It's convenient and fast (1 extra pointer isn't going to kill your memory usage).

[Khearts]

That idea also works too. I have actually executed that in some parts, but never thought to do it again in for score keeping, etc...Thanks.

[Falco Girgis]

I do appreciate all of the other suggestions provided; many of them, however, was a bit more advanced than what I was expecting. :

Haha, I definitely understand.

I most definitely agree with the separate lists of pointers for more specific types. That's very much a clean, efficient design. Even if some of the pointers are redundant (many of ours are), it provides any subsystem designed to operate on a child class with a list of ready-to-go child objects (that don't need casting or type checking or need to be skipped because they aren't of the proper type). In ES we handle our "components" like that. Each of our built-in component types get an array/vector of their own: warp, collidable, rigidbody, character, player, item, conversation, etc (for everything in the "scene"), while additional components created by client C++ code or Lua are stored in a common vector/array and are allocated using the dynamic allocator technique I discussed earlier. So it's really a hybrid between the two...

With that being said, I honestly encourage you to go back and look at the technique that GroundUpEngine and I were talking about (with the type property being used in a switch statement for a cast). If you plan to get into any form of serious OO development, the problem of storing various "child" objects in an array/list of the "parent" type is going to be a very, very commonly arising issue as this is an issue VERY common to OO development in general (it just happens that C++ is a special case, since it's low-level and provides no RTTI). After a bit of analysis, I think you will understand it very well. It's actually fairly intuitive and can be a pretty important technique in C++.

[Khearts]

Will do. Thanks again.

[bnpph]

Hello Khearts.

I think it is best idea to split into 2 seperate arrays. The only benefit I can see to having 1 single array is that it preserves ordering of insertion, and may be sorted. If you do not need either of these, then 2 arrays is preferred method.

If you want to iterate through every object in the arrays in one loop, then you can easily write your own iterator:
class FooContainer { //wrap both vectors into a class
public:
std::vector<a*> avec; //it is actually better practice to make these private, and write methods to access the data instead
std::vector<b*> bvec;
public:
class FooIterator : public iterator<random_access_iterator_tag, (...etc)> {
//implementation
//returns base class pointer when dereferenced
};
//add a "avec" iterator class and "bvec" too if you want
};
The iterator returns base class pointer when dereferenced.

About the RTTI stuff:
I have never used RTTI before (I prefer static polymorphism), but I think you do not need to add additional functions/variables to use.

Most implementations store a vtable pointer in every object with virtual methods - something that can be used to check the type.
Because C++ does not let us access vtable, we use typeid(). I believe typeid() checks based on v-table pointer, and so it should not take up additional space if you already are using virtual methods.

Here is example I made of using typeid():
#include <iostream>
#include <vector>

class A {
public:
int v;
int get_v() {
return v;
}
virtual int get_v_special() {
return v + 1;
}
};

class B : public A {
public:
int get_v_sqr() {
return v * v;
}
int get_v_special() {
return -v;
}
};

int main(int, char**) {
A a1;
a1.v = 5;

B b1;
b1.v = 8;

A a2;
a2.v = 3;

std::vector<A*> my_vector;
my_vector.push_back(&a1);
my_vector.push_back(&b1);
my_vector.push_back(&a2);

for(int i = 0; i < 3; ++i) {
std::cout << "my_vector[" << i << "]:\n";
std::cout << " v = " << my_vector->get_v() << '\n';
std::cout << " v special = " << my_vector->get_v_special() << '\n';
if(typeid(*my_vector) == typeid(B))
std::cout << " v sqr = " << ((B*)my_vector)->get_v_sqr() << '\n';
}
return 0;
}
As you can see, this checks type but does not use any extra stuff.

You should generally avoid this when possible though! Inheritance is designed to go one-way, that is dogs can be treated as animals, but animals cannot be treated as dogs. Putting dogs into std::vector<animal*> is actually treating animals as dogs (counter-intuitive), and is very common design flaw.

[Falco Girgis]

I have never used RTTI before (I prefer static polymorphism), but I think you do not need to add additional functions/variables to use.

Most implementations store a vtable pointer in every object with virtual methods - something that can be used to check the type.
Because C++ does not let us access vtable, we use typeid(). I believe typeid() checks based on v-table pointer, and so it should not take up additional space if you already are using virtual methods.

You are correct about the typeid() being stored in v-tables, but RTTI entails more than just the storage for a typeid(). First of all that typeid() grows linearly with the length of the class name. It also grows linearly with the depth of the inheritance tree (since a class must now be aware of its ancestry at run-time).

RTTI also entails and includes DYNAMIC CASTING.

RTTI also requires and throws run-time exceptions. Not only does enabling exceptions make your executable larger (yet more things to include in your executable), but code executed in try blocks is traditionally slower at least to some extent (possible by quite a bit).

Even the absolute teensiest amount of RTTI (typeid()) in the code you just posted hides some of this overhead:

Code: Select all

if(typeid(*my_vector[i]) == typeid(B))

The typeid() operator throws a bad_typeid exception if passed a NULL pointer. This goes to show that even the most innocent RTTI statements have more going on behind the scenes.

Your use of RTTI is also incorrect. You are checking the typeid()s of the objects against one another then STILL statically casting them? Why? You are already using RTTI, and even though that is safe in this particular situation, if you're already committing the sin of RTTI, you should at least be using a guaranteed type-safe, exception-throwing dynamic cast when you are doing something like that.

If you were using RTTI correctly, this scenario:

Code: Select all

if(typeid(*my_vector[i]) == typeid(B))
std::cout << " v sqr = " << ((B*)my_vector[i])->get_v_sqr() << '\n';

Would look like:

Code: Select all

B* b = dynamic_cast<B *>(my_vector[i])
if(!b) {
    //unable to perform the cast--my_vector[i] is not of a compatible type with b.
} else {
   //we are now SAFELY able to dereference b.
   b->someBOnlyVar = 10;
}

This scenario only even works as prettily with typeid() because your hierarchy is only 2 classes deep. Suppose you have a 3 deep hierarchy: A=>B=>C. What if you wanted to check if an object instantiated as type C is of type B?

Code: Select all

if(typeid(instanceC) == typeid(B))

This is going to return false. typeid() represents the static type of the object, not the dynamic type.


Once again, though, the dynamic_cast must traverse the inheritance tree until it finds the ancestor/descendent that you are casting to. This operation is slow, and becomes slower as the class hierarchies expand...

I definitely agree with not promoting this kind of backwards tree-traversal casting, but I disagree with your implementation. You're incurring all of the overhead of RTTI just for a couple of typeid() checks when this could more efficiently be implemented as a virtual getType() function (as in earlier posts). And while this particular scenario would work nicely with separate lists, problems DO arise where you need to cast in the other direction--that's the entire reason for the dynamic_cast<> and Java/C# have their own mechanisms. In this cases, I would muuuuuuch prefer to store my own typeid/metadata for that particular class than cause my entire program to suffer the overhead of unnecessary RTTI/exceptions.

There's a reason that most compilers either have it turned off by default or provide a very obvious mechanism for enabling and disabling "additional features" to the C++ language such as RTTI and run-time exceptions. I strongly disagree with folks who don't think twice before enabling and disabling these features in C++ just because it'll save them a few lines of code and some extra thought. You are already coding in a low-level, systems-oriented programming language. If runtime performance and overhead is not something you want to concern yourself with, why aren't you using Java or C#? What's the point then? You are using C++. Think about your problems like a C++ developer. This is the same language that still has a reserved word "register" and "unions" for consolidating groups of byte-aligned data. The power and beauty of the C/++ language(s) comes from its low level constructs, and I hate to see them molested. These are NOT standard features. They are additions and should be treated as such.

[bnpph]

Heya GyroVorbis!

I have very little experience with c++'s RTTI, and so I may be entirely wrong on the subject, but I do not understand some things you have said:

First of all that typeid() grows linearly with the length of the class name. It also grows linearly with the depth of the inheritance tree (since a class must now be aware of its ancestry at run-time).

You sure this is correct?

This scenario only even works as prettily with typeid() because your hierarchy is only 2 classes deep. Suppose you have a 3 deep hierarchy: A=>B=>C. What if you wanted to check if an object instantiated as type C is of type B?

Yeah, typeid doesn't care about inheritance, which may be beneficial.I think how I did it is still correct though.

typeid() represents the static type of the object, not the dynamic type.

I think it's still dynamic, dunno though.

The power and beauty of the C/++ language comes from its low level constructs, and I hate to see them molested. These are NOT standard features. They are additions and should be treated as such.

Molesting c++? Who would do such a thing!
Anyway, RTTI is standard C++, and so I don't think it should be shunned and called an "extension."
And as much as I love using unions, they can come with some silly overhead unless you use extensions like GCC's attributes to specify their use!


Anyway, I agree 100% on how RTTI is stupid and should be avoided. Still unsure if "enum RTII" is any better than "C++'s RTII" in this case they're both pretty unnessary. Don't think KHearts is too concerned over micro-optimizations, as he is using the STD and lots and lots of inheritance.

P.S.
I like your forums.

[Falco Girgis]

P.S.
I like your forums.

Haha, welcome to a place where men can bitch each other out over code and still respect each other enough to grab a beer later.

First of all that typeid() grows linearly with the length of the class name. It also grows linearly with the depth of the inheritance tree (since a class must now be aware of its ancestry at run-time).

You sure this is correct?

I probably should have elaborated here. I worded it fairly wonkily.

RTTI data is stored within a class's vtable as a pointer to an RTTI metadata object (called type_info). This metadata object must store the name of the class so at very least it is growing linearly by a byte in size with each character of the class name.

Along with this class-name overhead, the vtables themselves must now store "offsets" to the vtables of their parent classes. In a normal class inheriting from a virtual class WITHOUT RTTI, the only association the child's vtable even had with the parent is a few duplicate entries for virtual methods that were not overwritten. With RTTI, you have a new inter-vtable dependency since the dynamic_cast<> operator must now be able to jump from a child object's vtable to a parent object's vtable to inspect its type metadata object during the cast.

Once again, not only does the size of the vtable expand linearly with each virtual base class inherited, but the time complexity of the dynamic_cast<> operation literally becomes a tree traversal of linear time complexity for a failed cast (the entire tree must be checked).

I think it's still dynamic, dunno though.

Oops. I meant "dynamic" in the sense of being aware of a hierarchy. Observe:

Code: Select all

class A { virtual ... };
class B: public A { virtual ... };
[..]
if(typeid(A) == typeid(B)) {
    //This is never going to be true. You have to suffer the consequences of a dynamic_cast for this behavior...
}

In a "type" sense, you are correct, though. In the above example, if we had:

Code: Select all

B *b = new B;
A *a = b;

The static type of "a" would be "A," while the dynamic type of "a" would be "B."

Anyway, RTTI is standard C++, and so I don't think it should be shunned and called an "extension."

"Standard" is relative term. I feel like you're under a misconception as to how standard this feature actually is. Standard in that the compiler should support it is different than being a feature that is a standard part of the language. STL is more "standard" than RTTI, and it's a separate library. Most compilers disable RTTI by default. ALL compilers at least have options for it. MANY compilers (on embedded platforms) don't even implement RTTI. It might be ANSI standard "now" to "support" it, but it sure as hell isn't to allow it by default. What compiler are you using? You were able to use typeid() out of the box?

If all of the overhead I presented STILL hasn't convinced you (don't make me count clock cycles), then what about these?

RTTI should only be used sparingly in C++ programs. There are several reasons for this. Most importantly, other language mechanisms such as polymorphism and templates are almost always superior to RTTI. As with everything, there are exceptions, but the usual rule concerning RTTI is more or less the same as with goto statements. Do not use it as a shortcut around proper, more robust design. Only use RTTI if you have a very good reason to do so and only use it if you know what you are doing.

http://en.wikibooks.org/wiki/C%2B%2B_Programming/RTTI

Call the throw operator only when you want notify a user of the failure of the current command.
The raising of an exception has a very high cost, compared to a function call. It is thousands of processor cycles. If you perform this operation only when a message is displayed on the user interface or written into a log file, you have the guarantee that it will not be performed too often without notice.
Instead, if exception raising is performed for algorithmic purposes, even if such operation is initially thought to be performed rarely, it may end up to be performed too frequently.

http://en.wikibooks.org/wiki/Optimizing ... g_features

Bjarne Stroustrup (Father of C++) originally didn't want to include RTTI with the language.
http://www2.research.att.com/~bs/hopl2.pdf

AND LASTLY, observe the structure of the vtable itself. Each instance of a virtual class has a __dptr. Where does this point in the vtable? To the first virtual function entry. It then proceeds to grow in a downward direction. Where does this additional metadata (type_info and parent vtable offsets) wind up getting stored in the vtable? ABOVE the actual vtable pointer. Optional/additional metadata in the vtable grows upward (and is indexed with a negative offset) whereas standard vtable data grows downward. Even the design of the vtable itself implies that additional metadata overhead is not standard.

http://www.codesourcery.com/public/cxx- ... le-ex.html

^ That's actually a REALLY kickass article from HP comparing methods for handling additional offset/vtable metadata involved with virtual inheritance along with RTTI.

[bnpph]

RTTI data is stored within a class's vtable as a pointer to an RTTI metadata object (called type_info). This metadata object must store the name of the class so at very least it is growing linearly by a byte in size with each character of the class name.

IMO I don't think the few extra bytes matters very much, but I do see it as a downside.

Along with this class-name overhead, the vtables themselves must now store "offsets" to the vtables of their parent classes. In a normal class inheriting from a virtual class WITHOUT RTTI, the only association the child's vtable even had with the parent is a few duplicate entries for virtual methods that were not overwritten. With RTTI, you have a new inter-vtable dependency since the dynamic_cast<> operator must now be able to jump from a child object's vtable to a parent object's vtable to inspect its type metadata object during the cast.

Would the derived object already contain pointer to parent objects vtable if parent had one? It just seems very inefficient to traverse trees and offsets just to find type information.

"Standard" is relative term. I feel like you're under a misconception as to how standard this feature actually is. Standard in that the compiler should support it is different than being a feature that is a standard part of the language. STL is more "standard" than RTTI, and it's a separate library. Most compilers disable RTTI by default. ALL compilers at least have options for it. MANY compilers (on embedded platforms) don't even implement RTTI. It might be ANSI standard "now" to "support" it, but it sure as hell isn't to allow it by default. What compiler are you using? You were able to use typeid() out of the box?

Not so sure I agree with you here.
If I write code littered with "export," then it the compiler's fault, not mine, if it doesn't compile. I'm not saying that it is a good idea to do so, but it is the standard, and compilers should conform to the standard 100% by default.

If all of the overhead I presented STILL hasn't convinced you (don't make me count clock cycles), then what about these?

Hehe, I never meant to argue about the micro-efficiency of RTTI, just that it is valid to use and can be used to solve the problem. Thanks for the articles though! Actually, I had read through some of what you posted before posting my original message, do you have any detailed paper on how compilers specifically implement RTTI and inheritance? That would be very helpful!

AND LASTLY, observe the structure of the vtable itself. Each instance of a virtual class has a __dptr. Where does this point in the vtable? To the first virtual function entry. It then proceeds to grow in a downward direction. Where does this additional metadata (type_info and parent vtable offsets) wind up getting stored in the vtable? ABOVE the actual vtable pointer. Optional/additional metadata in the vtable grows upward (and is indexed with a negative offset) whereas standard vtable data grows downward. Even the design of the vtable itself implies that additional metadata overhead is not standard.

Hm, didn't know that metadata grew upwards, but makes sense.
Vtables are in standard?

Gyrovorbis, what is your opinion on inheritance and virtual functions?
Personally, never cared for it. It always seems like I end up with something too abstracted that carries extra baggage for no particular reason. I will take templates over inheritance any day. I like using exceptions, but I've only used them in applications and not games.
What about you?

P.P.S.
Arguing here is fun, much more so than stack overflow.