5 Replies - 2542 Views - Last Post: 25 July 2008 - 02:35 PM Rate Topic: -----

#1 mjdamico  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 15-May 08

STL lists and virtual functions

Posted 24 July 2008 - 01:50 PM

I'm just starting to experiment with STL lists, but I'm running into trouble when I try to add objects of both a base class and a derived class and then iterate through and execute virtual functions. Here's the code:

#include <iostream>
#include <cstring>
#include <list>

using namespace std;

class Player
	{
	protected:
		string name;
	public:
		Player(string setname) {name = setname;}
		virtual void Display() {cout << "Hi, I'm " << name << ".";}
	};
	
class Monster : public Player
	{
	public:
		Monster(string setname) : Player(setname) {}
		void Display() {cout << "I'm " << name << ", the monster!";}
	};

main()
	{
	list<Player> enemies;
	
	Player petey("Petey");
	Monster timmy("Timmy");
	Monster gus("Gus");
	
	enemies.push_back(petey);
	enemies.push_back(timmy);
	enemies.push_back(gus);
	
	list<Player>::iterator i;
		
	for(i=enemies.begin();i != enemies.end(); i++)
		{
		i->Display();
		cout << endl;
		}
	}



The output of the above code is:
Hi, I'm Petey.
Hi, I'm Timmy.
Hi, I'm Gus.

Whereas, I would expect it to be:
Hi, I'm Petey.
I'm Timmy, the monster!
I'm Gus, the monster!

I'd previously created a linked list template from scratch, and that's how it worked. Am I doing something wrong here?

Thanks.

Is This A Good Question/Topic? 0
  • +

Replies To: STL lists and virtual functions

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: STL lists and virtual functions

Posted 24 July 2008 - 02:15 PM

This is a well known and documented problem when dealing with STL containers. (you know I think I posted a question about this myself on DIC).

This has to do with run time evaluation of types. See you normally you use the compiler to figure out that some class is a subclass of another... But once the program starts running how can the container tell (it can't evaluate the source)? You told it in the code that it would be holding a Player and so that is what it expects.

You will also find the the containers don't copy derived classes properly since they call the wrong copy constructor. Again because during run time the container does not know enough about the class structure.

I *think* that the boost classes address some of these issues -- but my solution was to only store pointers to the objects.


Hopefully someone with a little more STL background will help explain. Else I will pull out my STL book and find the answer tonight.

This post has been edited by NickDMax: 24 July 2008 - 02:17 PM

Was This Post Helpful? 0
  • +
  • -

#3 mjdamico  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 15-May 08

Re: STL lists and virtual functions

Posted 24 July 2008 - 02:50 PM

OK, well that's good to know. I think I can deal with it storing pointers, even if it makes the code a bit more confusing. However, I can't quite seem to get the syntax correct for the line that executes the Display function in the for loop.

Here's my modified code:

#include <iostream>
#include <cstring>
#include <list>

using namespace std;

class Player
	{
	protected:
		string name;
	public:
		Player(string setname) {name = setname;}
		virtual void Display() {cout << "Hi, I'm " << name << ".";}
	};
	
class Monster : public Player
	{
	public:
		Monster(string setname) : Player(setname) {}
		void Display() {cout << "I'm " << name << ", the monster!";}
	};

main()
	{
	list<Player*> enemies;
	
	Player* petey = new Player("Petey");
	Monster* timmy = new Monster("Timmy");
	Monster* gus = new Monster("Gus");
	
	enemies.push_back(petey);
	enemies.push_back(timmy);
	enemies.push_back(gus);
	
	list<Player*>::iterator i;
		
	for(i=enemies.begin();i != enemies.end(); i++)
		{
		i->Display();
		cout << endl;
		}
	}



The compiler is giving me this error:
Error E2288 stllisttest.cpp 39: Pointer to structure required on left side of ->
or ->* in function main()

I know I need to make a change due to the fact that i is now a pointer to a pointer... but heck if I know what the correct syntax is!

Thanks!
Was This Post Helpful? 0
  • +
  • -

#4 perfectly.insane  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 70
  • View blog
  • Posts: 644
  • Joined: 22-March 08

Re: STL lists and virtual functions

Posted 24 July 2008 - 04:37 PM

This has little, if nothing, to do with STL, and is related to how C++ implements polymorphism.

This might help understand why pointers/references are necessary to use polymorphism in general:


class Player
{
     char* name;

     // other variables/methods
};

class SkilledPlayer : public Player
{
     int skill_level;
};




Ok, now, what is the size of a Player object? It's definitely at least 4 bytes. How about a SkilledPlayer? Definitely at least 8 bytes. You cannot store 8 bytes in a 4 byte container (well, some may try it).

Objects are always of the type they are instantiated as. One may be able to use different looking "interfaces" to deal with an object, but the actual type of the object never changes. So in reality, you cannot use a homogeneous collection to store a heterogeneous set of objects (well, there are ways, but they are cumbersome). You might be able to store a set of pointers to those objects, but not the objects themselves.

I suppose one could use raw byte arrays, with placement new, to attempt to construct objects into arbitrary chunks of memory (where these chunks would be at least as large as the largest derived class), but it's probably not worth the effort.

By the way... the original code compiles as the push_back method uses a reference parameter, which the compiler can cast your object to a Player&, much like it casts Monster* to Player*.

About calling display on the iterator object, the syntax would be (*i)->Display(); for the double de-reference.


Also, here's an example that may shed some light on how polymorphism is implemented in C++.... This is analogous to the provided code, but it demonstrates how the polymorphism works under the hood:

player.c
// Class Player
#include <stdlib.h>
#include <stdio.h>

// This is a virtual function table (vtable) for the Player class.  
// Every function in the class will have a function in this table.
// Subclasses will override the methods by using different function pointers.
struct PlayerVtbl
{
    void (*Display)(void* this);
};

// The class Player.  The vtable should always come first, and then any
// member variables.
struct Player
{
    struct PlayerVtbl* vtbl;
    char* name;
};

// This is what implements Player::Display.  Note that the object
// pointer is provided as an ordinary argument, and is always
// the first argument.
void Player_Display(void* this)
{
    printf("Hi, I'm %s\n", ((struct Player*)this)->name);
}

// Instead of allocating a new vtable for each object, it can
// be hardcoded as it never changes.
struct PlayerVtbl __vtbl_Player = { Player_Display };

// This implements similar functionality to a constructor in C++.
// Since constructors are specialized syntactic features in C++,
// they cannot be implemented directly, but a function can be used
// for the same purpose.
struct Player* New_Player(const char* name)
{
    struct Player* p = malloc(sizeof(struct Player));
    p->vtbl = &__vtbl_Player;
    int len = strlen(name);
    p->name = malloc(len + 1);
    memcpy(p->name, name, len + 1);
    return p;
}

// A destructor function.
void Delete_Player(struct Player* p)
{
    free(p->name);
    free(p);
}

// Class Monster inherits from Player

// This isn't necessary in this case, but is here for completeness.
// If Monster has more functions than Player, it is necessary.
struct MonsterVtbl
{
    void (*Display)(void* this);
};

// Same as above.  Note that the structure is the same as Player.
// If adding member variables, they should be added after name.
struct Monster
{
    struct MonsterVtbl* vtbl;
    char* name;
};

// The monster specific Display function.
void Monster_Display(void* this)
{
    printf("I'm %s, the monster!\n", ((struct Monster*)this)->name);
}

// The important part... the monster vtable will have a function
// pointing to Monster_Display, not Player_Display.  This is
// how the override is implemented.
struct MonsterVtbl __vtbl_Monster = { Monster_Display };

// A constructor function.  It creates a monster with a monster vtable.
struct Monster* New_Monster(const char* name)
{
    struct Monster* p = malloc(sizeof(struct Monster));
    p->vtbl = &__vtbl_Monster;
    int len = strlen(name);
    p->name = malloc(len + 1);
    memcpy(p->name, name, len + 1);
    return p;
}

// Destroy the monster.
void Delete_Monster(struct Monster* p)
{
    free(p->name);
    free(p);
}




playertest.cpp
#include <list>

using namespace std;

// Player interface.  The Player/Monster implentation is actually in C.
class Player
{
    public:
        virtual void Display() = 0;
};

// Monster and Player have the same interface, a "Display" method.
class Monster : public Player { };

// Declare the constructor/destructor methods.  They
// could have been in a .h file as well.
extern "C" {
    Player* New_Player(const char* name);
    void Delete_Player(Player* p);
    Monster* New_Monster(const char* name);
    void Delete_Monster(Monster* p);
};

// Putting the classes to the test.
// This should yield to the console:
//
// Hi, I'm Petey
// I'm Timmy, the monster!
// I'm Gus, the monster!
//

int main()
{
    list<Player*> enemies;

    Player* petey = New_Player("Petey");
    Monster* timmy = New_Monster("Timmy");
    Monster* gus = New_Monster("Gus");

    enemies.push_back(petey);
    enemies.push_back(timmy);
    enemies.push_back(gus);

    for(list<Player*>::iterator i = enemies.begin(); i != enemies.end(); i++) {
        (*i)->Display();
    }

    Delete_Player(petey);
    Delete_Monster(timmy);
    Delete_Monster(gus);
    return 0;
}


This post has been edited by perfectly.insane: 24 July 2008 - 04:39 PM

Was This Post Helpful? 0
  • +
  • -

#5 mjdamico  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 9
  • Joined: 15-May 08

Re: STL lists and virtual functions

Posted 25 July 2008 - 01:26 PM

Thanks for the detailed response. I understand what you're saying (sort of), although you lost me in the C code you provided. I guess I have a ways to go before I "get" all of this. Right now, I'm just trying to put together working programs by any means necessary. Hopefully I'll pick up the details and nuances as I go.

Regarding my attempt to create multiple object types, then store pointers to them in a list, and execute the virtual functions via the iterator... is this a "proper" way to implement polymorphism? I mean, it seems to work, but would a seasoned programmer look at it and say it was sloppy or wrong?

Not that I'm worried that the C++ Police are going to take me away... I figure I ought to learn good coding practices early on, you know.
Was This Post Helpful? 0
  • +
  • -

#6 perfectly.insane  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 70
  • View blog
  • Posts: 644
  • Joined: 22-March 08

Re: STL lists and virtual functions

Posted 25 July 2008 - 02:35 PM

Well, think about it this way. In Java, you're required to do this. In C#, you're required to do this. In Visual Basic (pre-.NET), Perl, and Python, you're also required to do this. Why? Because accessing objects in these languages is always done by reference/pointer anyway. So it's not really any different than what you would do in other programming languages. C++ is one of the few languages in which so much control is given to the programmer as to how objects are allocated/instantiated.

In C++, it's a bit messier as one has to deal with freeing memory when done using it. To mitigate this, you can use a reference counted smart pointer, like the boost::shared_ptr class from the Boost C++ libraries. That way, when the container is destroyed, all of the memory referenced by the pointers will automatically be destroyed as well.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1