Skip to main content
GameDev.net gamedev.net
🔒 Locked

C++ std library iterator inheritance HELP!

Started by AnimateDream May 12, 2009 at 2:20 AM 17 replies 5k views
Original Post
AnimateDream
AnimateDream
This std code is simple enough to use as a template but when i tried to create a child class out of the iterator I'm getting all kinds of headaches, but I'm still prone to newbishness. I suppose I should explain my goal and someone might suggest a better method. With edited names for relevance, I have a class myContainer that contains a list, and what I really want to add to this is a myContainerChild class to inherit the same functionality but operate on a list. Unfortunately I can't use a virtual data member, because c++ just doesn't work like that, and I can't use a template because I need data specific to the object class and its children and as far as I know templates can't be that specific. I settled on leaving the list the same but adapting the add and remove functions to take only childOfObject even though the list remains a list, as well as modifying the iterator to automatically cast the objects in the list as childOfObject, which should work as long as my add function is safe. I thought I finally had a good idea, but using the code below i quickly get the error ITERATOR LIST CORRUPTED! I suspect my constructor omits something important but the iterator code is so cryptic.

// ->>         in sim.h
// typedef std::list<sim *> simList;
// typedef simList::iterator simListIt;
// <<-

class objectListIt	: public simListIt
{
	typedef simListIt Parent;
public:
	objectListIt(simListIt input)
	{
		this->_Mycont = input._Mycont;
		this->_Mynextiter = input._Mynextiter;
		this->_Ptr = input._Ptr;
	}
	object* operator->() const
	{	// return pointer to class object
		return (static_cast<object*>(&**this));
	}
	
	
	object& operator*() const
	{	// return designated value
		return (static_cast<object&>(*(reference)**(_Mybase_iter *)this));
		//return **this);
	}
};
If anyone has any suggestions, thanks in advance. My brain is running down trying to read through the std library and make sense of its internal workings. Every few lines there's a preprocessor command. Its kind of rediculous. By the way i'm using visual c++ 2008 express.
Cornstalks
Cornstalks
Just so you know, any identifier starting with an underscore followed by an upper case letter or starting with two underscores is reserved for the implementation. In other words, the compiler gets to use them; you don't. Of course the compiler doesn't necessarily stop you from using them should you choose to, but it is not standards compliant and not necessarily compatible with other compilers.

But it gets worse. You aren't supposed to derive from standard containers. Just don't do it. Honestly, you don't need to.

Your casts and use of the * operator are horribly confusing. There's a better way to do this (I'll suggest an alternative below).

Your const functions do not return const references. Someone could modify the object reference that you return, thus breaking your const promise. Const correctness is a must read.

I don't know why you say you can't use templates. Why not just make a templated class where you pass in the type of the object you want to store in the list? Something like this:
template <typename T>class MyContainer{    public:        // you may have to use typename here too, I'm not sure        typedef std::list<T> ListType;        const ListType& getList() const        {            return myList;        }        ListType::iterator getListBegin()        {            return myList.begin();        }    private:        ListType myList;};// Later on in your codeMyContainer<object> myContainer;MyContainer<childOfObject> myContainerChild;


Disclaimer: I haven't actually tested the code above. It's just a way of showing things. It may not be 100% corect (but it's close).
ToohrVyk
ToohrVyk
@MikeTacular: actually, he's correct. operator* on pointers is a const function that can return a non-const reference. The following code is valid:

int i         = 5;int * const p = &i*i = 6;


@AnimateDream: list iterators are not classes or structures, so you can't inherit from them. They also have no such members as _MyCont, _Mynextiter or _Ptr. I know that your IDE or compiler might think that they do, and they might tell you so, and they might even let you use these, but never forget that you are progamming in C++. The most fundamental aspect of C++ is that "it works on my machine" is never a reliable indicator that your code is correct. If the language standard (or the stable parts of the official compiler documentation, if you don't care about portability) don't say it, then you shouldn't rely on it.

Now, if I get what you're trying to do... I would make both myContainer and myContainerChild class templates, where myContainerChild inherits from myContainer.


Cornstalks
Cornstalks
Quote:
Original post by ToohrVyk
@MikeTacular: actually, he's correct. operator* on pointers is a const function that can return a non-const reference. The following code is valid:

int i = 5;int * const p = &i*i = 6;

I'm not saying it's necessarily invalid, but bad practice. I'm also not talking about making the address of the pointer/reference const, but the value the pointer/reference refers to const. Perhaps I'm misunderstanding section 18.11 of the FAQ though, so if I am, please elaborate; I'd love to have a proper understanding.
ToohrVyk
ToohrVyk
Quote:
Original post by MikeTacular
Perhaps I'm misunderstanding section 18.11 of the FAQ though, so if I am, please elaborate; I'd love to have a proper understanding.
The state of a given iterator is what value it references. The state of that value is not part of the state of the iterator, it is actually part of the container/sequence the iterator iterates over. This leads to four different combinations of const-ness :

iterator : can change both iterator state and value state
const iterator : can change value state but not iterator state
const_iterator : can change iterator state but not value state
const const_iterator : can change neither state

But even assuming that const iterator wouldn't let you change the value state, you can always write:

const iterator c_it;iterator it(c_it);modify(*it);


That is, since the value state is the same for all iterators that reference that value, it's easy to create a non-const iterator to change the state through.
AnimateDream
AnimateDream
Thanks for the suggestions. I was aware of the problems I still had with const correctness, i was just having enough trouble getting it to allow me to compile.

My apologies if my explanations have been difficult to understand. The problem with a template I tried to explain earlier, is that my class is really designed around a list of one specific class and its children, and uses its member data and functions. Here's the whole parent container class I created.

//Basic storage hierarchy for everything in the simulation//A sim can be in only one simGroup//Becuase simGroup is a sim, it to can be stored in another simGroup//This should make it easy to organize game objects//::example:: bot4 might be stored in simGroup team2 which is in simGroup objects which is in root//            root->objects->team2->bot4typedef std::list<sim *> simList;typedef simList::iterator simListIt;class simGroup : public sim{public:	typedef sim Parent;	simList list;	simGroup(){}		//Add a sim to this simGroup, Ensure that sim is in only one simGroup	virtual bool add (sim* addition)	{		if (addition->group)			remove(addition);		addition->group = this;		list.push_back(addition);		return true;	}	//remove a sim from whatever simGroup its in	virtual bool remove(sim* removal)	{		if (removal->group)			removal->group->list.remove(removal);		removal->group = NULL;		return true;	}	bool isEmpty()	{		return list.empty();	}		//Update will update every sim in the simgroup.	//Because simgroups are also sims, this is recursive.	//Updating root should update everything in the simulation.	virtual bool update(float deltaTime)	{		//hge->System_Log((name + " " + typeid(*this).name() + "::update()").c_str());		if (list.empty())			return false;		//sim* current = NULL;		for(simList::iterator iter = list.begin(); iter != list.end(); iter++)		{			(*iter)->update(deltaTime);		}		return true;	}	//Not used yet	virtual bool bigUpdate()	{		if (list.empty())			return false;		//sim* current = NULL;		for(simList::iterator iter = list.begin(); iter != list.end(); iter++)		{			(*iter)->bigUpdate();		}		return true;	}};


If you look at my simGroup::update() function, it calls the sim::update() on every item stored. If I were using a template, the items stored would be an undefined type with no member function update() to call.

This class works great by itself but I want a child class of this container which
1. stores only a child class of the class its currently storing
2. can safely use member functions of this child class that aren't a part of sim used in the list in the parent container

Its starting to look like the easiest way is just to not have my second container class inherit from the first, despite needing to perform all of the same operations.

Quote:
Original post by MikeTacular
But it gets worse. You aren't supposed to derive from standard containers. Just don't do it. Honestly, you don't need to.

Technically I never did derive from a standard container I just derived from its iterator class. Which in retrospect is probably even worse.

Quote:
Original post by ToohrVyk
list iterators are not classes or structures, so you can't inherit from them. They also have no such members as _MyCont, _Mynextiter or _Ptr. I know that your IDE or compiler might think that they do,

Um. No actually it is a class in the standard library. Here's its definition header. Do a search for that.
template <bool _SECURE_VALIDATION>	class _Iterator		: public _Const_iterator<_SECURE_VALIDATION>

...and it also has all of the aforementioned data members. I can see the code and my ide isn't lying to me. I just didn't know if there were more data members I missed that might be critical to creating a copy of an initialized iterator.

Quote:
Original post by MikeTacular
Just so you know, any identifier starting with an underscore followed by an upper case letter or starting with two underscores is reserved for the implementation.
Seems logical enough, and in retrospect given the difficulty i had I can see why they'd use that naming convention. I'll remember that for the future. Thanks.


Quote:
Original post by MikeTacular
Your casts and use of the * operator are horribly confusing.
I agree the use of the * operator is horribly confusing. Its copied directly from the stl iterator class. Blame the people who wrote the standard library for that one. The casts themselves are the only new addition to those operator overrides, and they are the crucial part that was missing.

Thanks for your support everyone.

p.s. Why are none of my code tags working?
SiCrane
SiCrane
Quote:
Original post by AnimateDream
Um. No actually it is a class in the standard library. Here's its definition header. Do a search for that.
template <bool _SECURE_VALIDATION>	class _Iterator		: public _Const_iterator<_SECURE_VALIDATION>

...and it also has all of the aforementioned data members. I can see the code and my ide isn't lying to me. I just didn't know if there were more data members I missed that might be critical to creating a copy of an initialized iterator.

Names beginning with _ followed by an upper case are implementation details; they aren't part of the public interface of the standard library. This means that if you write code that depends directly on these types your code will only work with your current standard library implementation. It can and will break without warning if you move it to another compiler including possibly an upgraded version of your current compiler.
stonemetal
stonemetal
Quote:
Original post by AnimateDream
If you look at my simGroup::update() function, it calls the sim::update() on every item stored. If I were using a template, the items stored would be an undefined type with no member function update() to call.
Incorrect, the class will exist and be known when the template is instantiated. Much like the difference in declaration and definition, Template definition and Instantiation are two different things.
ToohrVyk
ToohrVyk
Quote:
Original post by AnimateDream
Do a search for that.


> grep '_MyCont' `find /opt/local/solaris/include/c++/`


Sorry, no results. Looks like my C++ compiler has no trace of the word _MyCont... nor does it define any _Iterator class, or contain any _SECURE_VALIDATION, or any of the terms you mention.

The result would probably be the same with many of my other compilers, and I wouldn't be surprised if several versions of your compiler also didn't come with it.

Quote:
I can see the code and my ide isn't lying to me.
O hai, welcome to C++. The IDE lies to you. The compiler lies to you. The entire C++ language is based on the assumption that the programmer knows what he is doing, so if you don't know what you're doing you will end up being screwed big time.

In this particular situation, both the IDE and the compiler expect you to know that any identifiers starting with underscore-uppercase are reserved and should therefore not be relied on. So, the IDE doesn't bother hiding the _Iterator class from you because, since you are a competent C++ programmer, you know that a class with that name should not be used by your own code.

AnimateDream
AnimateDream
Quote:
Original post by stonemetal
Quote:
Original post by AnimateDream
If you look at my simGroup::update() function, it calls the sim::update() on every item stored. If I were using a template, the items stored would be an undefined type with no member function update() to call.
Incorrect, the class will exist and be known when the template is instantiated. Much like the difference in declaration and definition, Template definition and Instantiation are two different things.


Forgive me I didn't mean to refer to the instantiation of the simgroup class. I need to use the objects member functions and data in the containers member functions. Perhaps I'm missing something fundamental about templates



EDIT: Ok. Ok. I totally botched that short bit of code I just posted and as soon as I noticed it my internet connection went out so I'm just now retracting it. sorry.

[Edited by - AnimateDream on May 13, 2009 1:09:23 PM]
Fruny
Fruny
list.begin() should be myList.begin(). Same for list.end().

Also note that, in standard C++, there is no such thing as a _tmain() function.
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
Codeka
Codeka
Quote:
Original post by AnimateDream
for(std::list::iterator iter = list.begin(); iter != list.end(); iter++)
list is referring to the std::list type (presumably you have a using namespace std; somewhere). You want to use myList instead.
Cornstalks
Cornstalks
First, you have to use the keyword typename, like so:

typename std::list::iterator iter

Second, your for-loop uses list.begin() and list.end() when it should be myList.begin() and myList.end(). Adding those things together gives you the following compilable code:

#include <cstdlib> // notice I removed the ".h" and appended a 'c' to the front like you should#include <list>#include <iostream>class parent{    public:        int data;                virtual void print()        {            std::cout << "parent" << std::endl;        }};template <typename T>class container{    public:        std::list<T*> myList;                void printAll()        {            for(typename std::list<T*>::iterator iter = myList.begin(); iter != myList.end(); ++iter)            {                (*iter)->print();            }        }};int main(){    container<parent> myContainer;    myContainer.printAll();}


Don't worry, I often forget the typename keyword and am left with puzzling errors. Anyway, the MSDN documentation for typename is here.

@ToohrVyk: thanks for the explanation. I'm still a little confused though. I don't want to derail this thread though so I'm going to do some googling and searching outside of this thread.
AnimateDream
AnimateDream
It seems I wasn't aware of just how versatile templates are. Sorry if I frustrated anyone with my newbish comments. Here is my solution. Its still got a few things to work out. For example, to make objectGroups able to store more objectGroups it had to use a dual inheritance even though it really isn't an object itself.


//----------------------------------------------------------------------------// File:         sim/sim.h// Description:  Defines the sim and simgroup to organize all entities in the// simulation, and provide useful data and functions to all entities.//----------------------------------------------------------------------------#ifndef SIM_H#define SIM_H#include <list>#include <typeinfo>#include <stdlib.h> #include <string>template <typename T>class simulationGroup;//class simGroup;//everything in the simulation should be a sim or child of sim//this allows for universal polymorphic functions and universal storageclass sim{public:	friend class simulationGroup<sim>;	//friend class simGroup;	std::string name;	HGE* hge;	//TO DO: pointer directly to simgroup list node for faster removal etc.	simulationGroup<sim>* group; // the simGroup this sim is contained in. Otherwise this should be NULL.	//simGroup *group;	sim(){group = NULL; name = "Unnammed!"; hge = hgeCreate(HGE_VERSION);}	sim(float x, float y){group = NULL; name = "Unnammed!"; hge = hgeCreate(HGE_VERSION);}	virtual ~sim(){}	//shouldn't be needed yet, this was used for testing	virtual bool operator < (const sim& other)	{		hge->System_Log((name + " " + typeid(*this).name() + "::<()").c_str());		return (this->name < other.name);	}		//overriden by children	virtual void update(float deltaTime)	{		//hge->System_Log((name + " " + typeid(*this).name() + "::update()").c_str());	}	//runs the correct update function not a parent's	void triggerUpdate(float deltaTime)	{		update(deltaTime);	}	//To Do: implement system for certain tasks to be performed over bigger intervals	// example: ai cycles need not be performed every frame	virtual void bigUpdate(){}	//To Do: implement some kind of handy function that displays all info for any sim	virtual void dumpInfo(){}};template <typename T>class simulationGroup : public virtual sim{public:	typedef sim Parent;	typedef std::list<T*> simulationList;	//typedef simulationList::iterator simulationListIt;	simulationList list;	simulationGroup(){}	virtual ~simulationGroup()	{		//list.~list();	}	 //Add a sim to this simGroup, Ensure that sim is in only one simGroup	 bool add (T* addition)	{		if (addition->group)			remove(addition);		addition->group= reinterpret_cast<simulationGroup<sim>*>(&*this);		list.push_back(addition);		return true;	}	//remove a sim from whatever simGroup its in	bool remove(T* removal)	{		if (removal->group)			removal->group->list.remove(removal);		removal->group = NULL;		return true;	}	bool isEmpty()	{		return list.empty();	}		//Update will update every sim in the simgroup.	//Because simgroups are also sims, this is recursive.	//Updating root should update everything in the simulation.	virtual void update(float deltaTime)	{		Parent::update(deltaTime);		//hge->System_Log((name + " " + typeid(*this).name() + "::update()").c_str());		if (list.empty())			return;		//sim* current = NULL;		for(simulationList::iterator iter = list.begin(); iter != list.end(); iter++)		{			(*iter)->triggerUpdate(deltaTime);		}	}	//Not used yet	virtual void bigUpdate()	{		if (list.empty())			return;		//sim* current = NULL;		for(simulationList::iterator iter = list.begin(); iter != list.end(); iter++)		{			(*iter)->bigUpdate();		}	}};typedef simulationGroup<sim> simGroup;typedef simulationGroup<sim>::simulationList::iterator simIterator;#endif

//----------------------------------------------------------------------------// File:         sim/object.h// Description:  Objects are simulated entities with a body that interacts// physically and is rendered to the screen according to its world position.//----------------------------------------------------------------------------#ifndef OBJECT_H#define OBJECT_H#include <hge.h>#include <hgevector.h>#include <math.h>#include "sim.h"#include "camera.h"#include "physics.h"class object;class objectGroup;// ratio of diagonal movement to direct movement on each axisstatic float diagonal = sqrt(0.5f);class object : public virtual sim{//LONG CODE BLOCK OMITTED};class objectGroup : public simulationGroup<object>, public object{	virtual void RenderEx( camera* cam )	{		if (list.empty())			return;		for(simulationList::iterator iter = list.begin(); iter != list.end(); iter++)		{			(*iter)->RenderEx(cam);		}	}};typedef objectGroup::simulationList::iterator objectListIt;


[Edited by - Zahlman on May 25, 2009 7:59:27 PM]
rip-off
rip-off
You don't need to check if a list is empty before iterating over it. If the list is empty, begin() will equal end() and the loop will never execute. Your way, you are doing this check twice.

Your use of reinterpret_cast<> is worrying though. I suggest you structure your code so that it is not necessary. I think you may be invoking
undefined behaviour
at the moment however.

Finally, use [source][/source] tags for long code blocks, not quote.
nullsquared
nullsquared
Your design is quite confusing. I think your reinterpret_cast and virtual inheritance are out of place.

What exactly, in words, do you want to accomplish?
AnimateDream
AnimateDream
Quote:
Original post by nullsquared
Your design is quite confusing. I think your reinterpret_cast and virtual inheritance are out of place.

What exactly, in words, do you want to accomplish?


What am I trying to accomplish? I thought I explained before but I'll provide more detail this time.

Everything in my simulation is a sim. Objects are a class derived from sims. All sims are organized into simGroups, stay in one simGroup exclusively, and contain a pointer to their simGroup. simGroups are containers that store any kind of sim, and are also themselves sims, allowing nested storage structures. simGroups override the update() function and other sim member functions to perform the operations on all contained sims. This automatically recurses through all simgroups in the simgroup as well. objectGroups are simgroups that store only objects, not just any sim.

That being said, to allow objectGroups to store other objectGroups they have to inherit from the object class, even though they are simGroups. Both simGroup and object inherit from the sim class, so to avoid conflicts with a diamond style inheritance, I used virtual inheritances.

The sim's pointer to its simGroup is automatically assigned when it is added to a simGroup. To allow this to still work in objectGroups a reinterpret_cast is performed. I couldn't figure out a simpler way to assign the pointer, but there shouldn't be any behavior that would cause problems.


Quote:
Original post by rip-off
You don't need to check if a list is empty before iterating over it. If the list is empty, begin() will equal end() and the loop will never execute. Your way, you are doing this check twice.

Good point! Thank you.

Quote:
Original post by rip-off
Your use of reinterpret_cast<> is worrying though. I suggest you structure your code so that it is not necessary. I think you may be invoking
undefined behaviour
at the moment however.

I don't think so, but I didn't want to resort to a reinterpret_cast myself. If you read my explanation above and understand what I'm trying to do perhaps you can suggest a better way of making it work.
Quote:
Original post by rip-off
Finally, use [source][/source] tags for long code blocks, not quote.

Ah. Thank you so much. I've been using [code] instead of [source] and wondering why it didn't give me that nice effect. I'll go edit my previous post now.
rip-off
rip-off
That sounds like a very complicated system. The role of sym and object still aren't very clear.

Are there any sims that arent objects? If you could merge the two classes, the system might be cleaner (no virtual inheritance).

Otherwise I would be tempted to separate the classes further. Could an object have a sim as a member? Prefer composition over inheritance etc.
AnimateDream
AnimateDream
Quote:
Original post by rip-off
That sounds like a very complicated system. The role of sym and object still aren't very clear.

Are there any sims that arent objects? If you could merge the two classes, the system might be cleaner (no virtual inheritance).

Otherwise I would be tempted to separate the classes further. Could an object have a sim as a member? Prefer composition over inheritance etc.


Its working great so far. The system is kind of complicated in implementation, but very simple to use, and very powerful. Currently there are only 2 sim derived classes that are not objects, so it wouldn't be too difficult to merge the sim and object class. However being able to easily add a new class to the simulation that isn't necessarily a real world object isn't something I want to give up.

Making an object have sim as a member would undo the purpose of the sim class, which is to organize all game entities into a simple interface. To update my simulation for a frame I have a root simGroup, and I just call its update function and input the delta time as a parameter.

Perhaps if I show some of my code usage...

These simGroups organize my demo game.
	simGroup root;		//The entire simulation belongs in the root group	objectGroup objects;	//All simulated objects belong in the objects group	objectGroup team1;	objectGroup team2;



Initializing them is fairly simple.
	objects.name = "objects";	team1.name = "team 1";	team2.name = "team 2";	root.name = "root";	root.add(&objects);	objects.add(&team1);	objects.add(&team2);	//Player1	player1 = new player(0,0);	objects.add(player1); //add to simulation	player1->name = "player1";


Performing all calculations for each frame gets to be completely object oriented.
	//!!! UPDATE ALL SIMS IN SIMULATION !!!	root.update(dTime);

Rendering is also handled completely in OOP leaving one simple command for the main code.
	objects.RenderEx(&cam1);


Once my engine is a bit more robust, better organized, and better commented, I'll make the full source code available online. My current issues are no longer really relevant to the thread title though so it's probably time to let this thread die soon. Thank you everyone for your help.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.