Back to General and Gameplay Programming

Simpler STL container enumeration

General and Gameplay Programming Programming

Started by Programmer16 October 11, 2006 09:23 PM

25 comments, last by Programmer16 17 years, 7 months ago

Programmer16

2,321

Author

October 11, 2006 09:23 PM

I was just wondering why nobody (that I can find) has written simpler STL container enumeration/iteration code. I've been writing some STL wrappers and came up with the following solution (similar to C#'s design) and it works really well and I don't see any problems.


template <typename TYPE>
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 <typename TYPE>
class EnumerableVector : public dfg::Enumerable<TYPE>, public dfg::Vector<TYPE>
{
	typename dfg::Vector<TYPE>::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 <typename KEY, typename TYPE>
class EnumerableDictionary : public dfg::Enumerable<TYPE>, public dfg::Dictionary<KEY, TYPE>
{
	typename dfg::Dictionary<KEY, TYPE>::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<dfg::String, dfg::String> 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<<Words.GetCurrentKey()<<") "<<Words.GetCurrent()<<std::endl;
	return 0;
}

What I'm wondering is - am I missing something that will cause some major PITA errors? Is my design bad? Thanks!

Oluseyi

2,123

October 11, 2006 09:30 PM

That's a lot of code to recreate std::foreach and std::bind1st...

Sneftel

1,788

October 11, 2006 09:36 PM

Hardcore C++:

typedef std::map<std::string, std::string> WordDict;WordDict Words;int main(){	for(int Index = 0; Index < 10; ++Index)                Words.insert(boost::format("%1%") % Index, boost::format("String number %1%") % Index + 1));        std::transform(Words.begin(), Words.end(),                 std::output_iterator<std::pair<std::string, std::string> >(cout),                boost::format("%1%) %2%\n") % bind(&std::pair<std::string, std::string>::first, _1) % bind(&std::pair<std::string, std::string>::second, _1));

Less hardcore:

typedef std::map<std::string, std::string> WordDict;WordDict Words;int main(){	for(int Index = 0; Index < 10; ++Index)                Words.insert(boost::format("%1%") % Index, boost::format("String number %1%") % Index + 1));        for(WordDict::const_iterator iw=words.begin(); iw != words.end(); ++iw)        {            std::cout << iw->first << ") "<< iw->second << std::endl;        }

Here's some wheels. Here's some more. Try not to reinvent them.

Programmer16

2,321

Author

October 11, 2006 09:41 PM

I don't see how it's recreating bind1st, but I've never actually used that. Actually, I don't see how it's recreating either, since both require pre-defined external functions.

Yes, it's a lot of code. However, it took about 5 minutes to write, is easier to read, and, as I said, doesn't require the user to write predictates (I think thats the word) for every type of action they want to do.

Edit:
@Sneftel: I know of both of those solutions and have used both, but that's not the point of my post. Both of those are not only extremely hard to read (the second is easier to read than the first), but they're majorly repetive and easy to screw up.

I also use both boost and (obviously) STL.

Thanks for the replies!

Sneftel

1,788

October 11, 2006 09:49 PM

Quote:Original post by Programmer16
is easier to read

No, it isn't. Speaking as someone who's been writing C++ for a decently long period of time, I am not familiar with the difference between GetCurrent and GetCurrentKey. I don't know what members dfg::String has, or what the algorithmic complexity of dfg::EnumerableDictionary is, or what arguments dfg::Format takes. But I do know the STL, because everyone whose code I read knows the STL. When I read your code, I don't want to have to get cozy with it. I don't want to have to learn about your beautiful new plan for enumerations, or how to get your clever classes to actually friggin' work. And I certainly don't want to do all this only to find that you're reimplementing the STL.

Quote:doesn't require the user to write predictates (I think thats the word) for every type of action they want to do.

Sure it does. What do you think that thing in your while statement is?

Programmer16

2,321

Author

October 11, 2006 10:00 PM

Quote:Original post by Sneftel
Quote:Original post by Programmer16
is easier to read

No, it isn't. Speaking as someone who's been writing C++ for a decently long period of time, I am not familiar with the difference between GetCurrent and GetCurrentKey. I don't know what members dfg::String has, or what the algorithmic complexity of dfg::EnumerableDictionary is, or what arguments dfg::Format takes. But I do know the STL, because everyone whose code I read knows the STL. When I read your code, I don't want to have to get cozy with it. I don't want to have to learn about your beautiful new plan for enumerations, or how to get your clever classes to actually friggin' work. And I certainly don't want to do all this only to find that you're reimplementing the STL.

I meant that it was easier for me to read.

Also, I'm not reimplementing anything, I said that they're wrappers for STL to simplify STL use for me. All I've done is added extra functionality that may or may not exist externally (I'm not positive about all of it.)

Plus the fact that I never said this was for other people, I'm doing this for myself and if other people end up using it, then they obviously don't care about having to learn. As I stated in my original post, I was wondering if I overlooked something that could cause some major issues.

Quote:Original post by Sneftel
Quote:doesn't require the user to write predictates (I think thats the word) for every type of action they want to do.
Sure it does. What do you think that thing in your while statement is?

I meant external predictates, which I stated: "as both require predefined external functions."

nolongerhere

569

October 11, 2006 10:43 PM

I like it dude, this is what ive been looking for!

Note to Sneftel: I would love to get "cozy" with something like this if its an improvement, hell, even if its slower ide still use it.

Extrarius

1,412

October 11, 2006 11:09 PM

It's not thread safe or thread friendly, and any subroutine that used the enumeration functions could produce bugs that are nearly impossible to trace down. If you want something like that, you should make a templated iterator wrapper instead.

"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

Programmer16

2,321

Author

October 11, 2006 11:40 PM

Quote:Original post by Extrarius
It's not thread safe or thread friendly, and any subroutine that used the enumeration functions could produce bugs that are nearly impossible to trace down. If you want something like that, you should make a templated iterator wrapper instead.

Thanks Extrarius. Threads actually hadn't crossed my mind since I've never used them. I've added it to my todo list for the next iteration of my code library.

The subroutine issue is already on my to-do list, as is the fact that you can't iterate a const version of the vector.

Writing an iterator wrapper hadn't crossed my mind either, but mostly for the fact that I'm not quite sure how they work. I've got the gist of things, just not the "in-depth" understanding that I'd like to have. That's why I'm writing containers as a side learning project (nobody yell and scream; I'm doing it for learning purposes only and I don't plan to use them in anything.)

Quote:Original post by Falling Sky
I like it dude, this is what ive been looking for!

Cool, I'm glad to hear you find it useful.

To those that are interested in the design, but don't want to use my whole containers library (I know there's at least two of you lol): I rewrote the classes to use STL classes instead of my wrappers. It's a bit more ugly, but it works. You can see it here. Make sure you read the comments in the GetCurrent() and GetCurrentKey() methods!

And for those that are interested in the rest of the library, I'll be putting it up in my journal within the next few days.

Quote:Original post by Falling Sky
hell, even if its slower ide still use it.

This shouldn't be a problem with any of my wrappers, since I'm storing STL internally. AFAIK the conversion operator (dfg::Vector to std::vector, dfg::Dictionary to std::map, and dfg::String to std::string) should be pretty much completely transparent since all I'm doing is returning the STL object.

This also brings up the point that my wrappers should integrate pretty seemlessly into other code (it has so far for me.) The only thing I can see at the moment that would slow things down are my copy constructors that take STL objects (since the data needs to be copied from the input container to my internal container.)

Thanks for the replies guys!

MaulingMonkey

1,729

October 11, 2006 11:52 PM

For the first time ever, I spawn two windows (one for each monitor at fullscreen), because replying to the numerous potential pitfalls of this particular snippet group would just take too damn long staying within one monitor.

Snippet #1: Enumerable< TYPE >

RE @ GetCurrent & Co.: By value semantics? So much for using it with expensive to copy types...

Snippet #2: EnumerableVector< TYPE >
Snippet #3: EnumerableDictionary< TYPE >

Iteration state data dosn't belong in a container. By forcibly coupling these two together, your code will go horribly awry if you try to iterate over the same container in multiple places at the same time. Many-to-many colision checking for example.

Further, you seem to have 0 interoperability with STL containers - so much for using other people's code easily. Presuming you've just ommited constructors - then you're still missing the ability to drop in a custom allocator, which seems pretty vital functionality to have available to me. Having basic utility stuff like having Dictionary able to return pairs directly for interoperating with other ("non owned") code's std::map would also be something I'd want.

RE @ "repetitive STL": You're also, you know, repeating the interface in a twisted up fashion that the standard library which has, you know, already been written for you. And dfg::Vector< TYPE > looks to be repeating std::vector's entire interface. With... different capitalization. Why?

Snippet #4: Some test code

If dfg::String::Format uses va_args, I should hunt you down and slap you. Seriously though, the moment "%i" becomes unsynced with the actual type of index (say you need to make it unsigned to handle a 3GB file or w/e) - your code fails to work right. It won't work correctly with objects either. And can totaly asplode if, say, you pass the wrong number of arguments. And some compilers still don't warn you about this shit either.

RE @ "easy to screw up: boost::format, on the other hand, will work completely correctly since it uses the far superior alternative - operator chaining. It has defined (and customizable!) semantics for what happens when you pass to few/many arguments. You know, defined behavior, especially useful if you want to add user-customizable formatting strings. And with the direct STL, iterators are explicit and unshared, meaning no weird logic bugs. What's there to screw up?

RE @ "harder to read": I find Sneftel's code far easier to read than yours as well. "while( Words.MoveNext() )"??? This code would make me hit up the documentation just to verify - after a delay of deliberation trying to decide what I expect that to do - that this is supposed to go through this entire container/iterator hybrid until the end. After I'd taken my sweet time realizing we're dealing with a container/iterator hybrid in the first place, that is.

I'd much rather use common existing sane idioms that I already grok and are functionally superior (while( iterator != end )). If I didn't grok that idiom, it'd be a far higher priority for me since that's what everyone else is going to be using, and I don't code in a vaccum.

Simpler STL container enumeration

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Simpler STL container enumeration

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines