STL container wrappers

posted in Beals Software
Published October 11, 2006
Advertisement
I think I talked about these in one of my earlier entries, but I'm going to again. Before I start I have to ask why nobody has made simpler enumeration/iteration systems for containers yet? Or have people and they just haven't shared them yet? Or do I just not know about them? lol.

My container system is practically done (for now.) I've added a bunch of stuff and left some stuff out (because I've never used them; I'll add them when the time comes.)

Anyway, to the point of the post. I'm really sick of all of these for() loops that look horrid and are a pain to read through, so I made a simpler system. I kept my old dfg::Vector and dfg::Dictionary and added dfg::EnumerableVector and dfg::EnumerableDictionary (just in case I'm overlooking a major problem in the design.) I also added a base class named Enumerable:
template class Enumerable{public:	Enumerable()	{	}	virtual ~Enumerable()	{	}	virtual void Reset() = 0;	virtual bool MoveNext() = 0;	virtual TYPE GetCurrent() = 0;};


And this is what my new containers look like:
template class EnumerableVector : public dfg::Enumerable, public dfg::Vector{	typename dfg::Vector::Iterator Current;public:	EnumerableVector()	{		Current = 0;	}	void Reset()	{		Current = 0;	}	bool MoveNext()	{		if(Current == 0)			Current = this->Begin();		else			++Current;		if(Current == this->End())		{			Current = 0;			return false;		}		return true;	}	TYPE GetCurrent()	{		if(Current == 0)			throw dfg::NullException(__FILE__, __LINE__, "EnumerableVector::Current has not been set. Try calling Reset() and then MoveNext() before GetCurrent().");		return (*Current);	}};


And:
template class EnumerableDictionary : public dfg::Enumerable, public dfg::Dictionary{	typename dfg::Dictionary::Iterator Current;public:	EnumerableDictionary()	{		Current = 0;	}	void Reset()	{		Current = 0;	}	bool MoveNext()	{		if(Current == 0)			Current = this->Begin();		else			++Current;		if(Current == this->End())		{			Current = 0;			return false;		}		return true;	}	KEY GetCurrentKey()	{		if(Current == 0)			throw dfg::NullException(__FILE__, __LINE__, "EnumerableDictionary::Current has not been set. Try calling Reset() and then MoveNext() before GetCurrentKey().");		return (*Current).first;	}		TYPE GetCurrent()	{		if(Current == 0)			throw dfg::NullException(__FILE__, __LINE__, "EnumerableDictionary::Current has not been set. Try calling Reset() and then MoveNext() before GetCurrent().");		return (*Current).second;	}};


And some test code:
dfg::EnumerableDictionary Words;int main(){	for(int Index = 0; Index < 10; ++Index)		Words.Add(dfg::String::Format("%i", Index), dfg::String::Format("String number %i", Index + 1));	while(Words.MoveNext())		std::cout<") "
< return 0;
}





Questions, comments, and/or suggestions are always welcome! If I don't find anything that's deathly wrong with it, I'll be releasing the whole library sometime this week/early next week.


Check out OpenXNA, we're going to be hosting open-source libraries, projects, tutorials, and games all about XNA. Methinks the first thing on my list is going to be a GUI for XNA. Hopefully Raymond doesn't read that... >_> <_<
Previous Entry XNA woes
Next Entry New enumerator
0 likes 11 comments

Comments

Aardvajk
Hey programmer16.

I hope this isn't taken as criticism but I was just wondering what would happen if you were halfway through a MoveNext() sequence and called a function that, within that, had to run through the WordDictionary seperately?

I had a problem with a list of game objects once that provided an interface like yours with a position marker internal to the list class. During one of the iterations, it called another function that also had to iterate through the list and it all went a bit mad.
October 12, 2006 02:43 AM
Programmer16
Quote:Original post by EasilyConfused
Hey programmer16.

I hope this isn't taken as criticism but I was just wondering what would happen if you were halfway through a MoveNext() sequence and called a function that, within that, had to run through the WordDictionary seperately?

I had a problem with a list of game objects once that provided an interface like yours with a position marker internal to the list class. During one of the iterations, it called another function that also had to iterate through the list and it all went a bit mad.


Hey EasilyConfused.

Yea, this problem was brought up in my forums post and I have a pretty simple solution. I'll implement Enumerable's functionality in a seperate internal class conveniently named Enumerator and supply a function (again, conveniently named) GetEnumerator(). I'll probably get rid of the Enumerable class after that. I already had it working, but I deleted it because I didn't think I needed it lol.

The new design will make things a little bit heavier, but I still like it much better than any STL solution I've come up with or have seen.

The issue of adding/removing elements causing the iterators to become invalid will still exist, but they would anyway (except for std::map.)

An example of the new design:

typedef dfg::Vector<YourTypeHere> Vector;

Vector::Enumerator Enumerator = Vector.GetEnumerator();
while(Enumerator.MoveNext())
{
    // do stuff using Enumerator.GetCurrent();
    Vector::Enumerator EnumeratorB = Vector.GetEnumerator();
    while(EnumeratorB.MoveNext())
    {
        // do stuff using EnumeratorB.GetCurrent();
    }
}



Thanks for the reply!
October 12, 2006 03:02 AM
Aardvajk
Yeah, thought you'd probably already thought of that.

When I had the problem with my game list, I ended up with a very simple solution, since the list was specific to game items and they had a next pointer. I just added this inline member function to the list:


Item *operator()(Item *I=0){ return(I ? I->Next : Top); }


Then I could just do:


for(Item *I=Items();I;I=Items(I)) I->DoStuff();


That was nice and concise but I'm now realising that it was a bad design to have a specific list like that and also probably violates the principle of least surprise.

I should have generalised the list so it wasn't specific to the game items. The iterator approach you describe above seems like a much cleaner solution.

I must admit though that with your new design, I'd be hard pressed to resist implementing MoveNext as operator++, then operator* and operator-> for access, then you're pretty much back to the STL iterator design.

[EDIT] I just read your forum post on this subject and realised I'm not adding anything new to the debate here [smile].
October 12, 2006 03:35 AM
Programmer16
Quote:Original post by EasilyConfused
Yeah, thought you'd probably already thought of that.

When I had the problem with my game list, I ended up with a very simple solution, since the list was specific to game items and they had a next pointer. I just added this inline member function to the list:


Item *operator()(Item *I=0){ return(I ? I->Next : Top); }


Then I could just do:


for(Item *I=Items();I;I=Items(I)) I->DoStuff();


That was nice and concise but I'm now realising that it was a bad design to have a specific list like that and also probably violates the principle of least surprise.

I should have generalised the list so it wasn't specific to the game items. The iterator approach you describe above seems like a much cleaner solution.

I must admit though that with your new design, I'd be hard pressed to resist implementing MoveNext as operator++, then operator* and operator-> for access, then you're pretty much back to the STL iterator design.

[EDIT] I just read your forum post on this subject and realised I'm not adding anything new to the debate here [smile].


Adding the operator++, operator*, and operator-> wouldn't really be a bad idea. The enumerator is pretty much just a wrapped iterator that can tell when it's found the end. Thanks for the input!
October 12, 2006 04:06 AM
Deyja
I'm not seeing any advantage in this design over iterators and standard algorithms.

In fact, without an iterator interface, I can't use your containers with standard algorithms anyway.
October 12, 2006 06:02 AM
EDI
This is a Bad Idea (TM),

I used a similar system in my home-rolled containers, so as you stated first off your iterator object must be an external object so that you dont get nested enumeration issues. Second, you should just get used to:

std::vector<int>::iterator it=vec.begin();
while(it!=vec.end())
{
int i=*it;

++it;
}

I am currently removing my:

EnumRewind, EnumWhile, EnumNext functions as well as my home-rolled container classes from Morning's Wrath, that should be a signal that this may not be the way to go about things :)
October 12, 2006 07:59 AM
Saruman
I don't mean to be rude but I have to say that you are definately going down the wrong road with this and should be using the standard way of doing things.
October 12, 2006 09:30 AM
Programmer16
Quote:Original post by Deyja
I'm not seeing any advantage in this design over iterators and standard algorithms.

In fact, without an iterator interface, I can't use your containers with standard algorithms anyway.


My classes are STL wrappers, and thus you still have full access to pretty much everything as well as the underlying container. It was brought to my attention that I don't have custom allocator support though. My wrappers can also be used with any STL code. Converting STL to my structures requires only that which copying between containers would cost.

Quote:Original post by EDI
This is a Bad Idea (TM),

I used a similar system in my home-rolled containers, so as you stated first off your iterator object must be an external object so that you dont get nested enumeration issues. Second, you should just get used to:

std::vector<int>::iterator it=vec.begin();
while(it!=vec.end())
{
int i=*it;

++it;
}

I am currently removing my:

EnumRewind, EnumWhile, EnumNext functions as well as my home-rolled container classes from Morning's Wrath, that should be a signal that this may not be the way to go about things :)


I am quite used to that way, as I've been doing it for over 5 years now. I just like this way a lot better and didn't see any problem with trying to clean up the interface for code that I use on a day-to-day basis[smile].

Also, before anyone says anything, the new classes are just temporary. If I feel that I that it's still worth my time, EnumerableVector and Vector will be a single class (actually, EnumerableVector will be removed and Enumerator will be added to my classes.) But then again, I'll probably run into an issue and just drop the whole thing anyway.
October 12, 2006 09:49 AM
Programmer16
Quote:Original post by Saruman
I don't mean to be rude but I have to say that you are definately going down the wrong road with this and should be using the standard way of doing things.


Not rude at all. And I understand what you're saying, which is why I'm contemplating throwing out. I just was looking for a simpler way of doing code that I write 10 to 20 times a day and I figured this was a much better idea than writing custom container classes.
October 12, 2006 10:11 AM
Programmer16
I posted it in the forums and I'll reiterate it here: this library wasn't done so that I could use it in projects like Asrion or even smaller projects like MalykAI. It was done to hasten production of smaller projects (like very simple puzzle games) and test code (which I do a lot of.)
October 12, 2006 10:55 AM
Aardvajk
Y'know, I'm probably going to be attacked for saying this (been one of those days really) but I'm actually quite interested in the idea of an iterator that can tell when it is at the end of a sequence without having to refer back to its generating container.

In the sense that an STL iterator is analogous to a pointer, an iterator that could be end-aware would be analogous to the way we used to deal with c-strings.

I haven't really thought this through and I'm sure there are lots of examples where such iterators would be impossible, impracticle or useless but I think it is an interesting idea anyway.

Surely if std::vector could emit an end-aware iterator, and std::list and so on, you could write a function like:


template<class T> void write(ofstream &os,T i)
{
    while(!i.at_end()) os << *i++;
}

void f()
{
    ofstream os("test.txt");

    std::vector v; // fill with values
    write(os,v.end_aware_iterator());

    std::list l; // fill with values;
    write(os,l.end_aware_iterator());
}


I appreciate that it wouldn't be compatible with normal pointers, unlike the STL algorithms, and I also appreciate that the above (contrived) examples could have just as easily be done with the normal STL interface, but I still think an end aware iterator is an interesting idea perhaps worth slightly more discussion than it seems to have recieved today.
October 12, 2006 12:41 PM
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!
Advertisement
Advertisement