Sunday, August 24, 2008

C++ Iterators

A friend of mine and I are collaborating on a game in the C++ programming language. The part I'm writing is a general purpose engine that will be used on both the game server and the game client, so I decided to use templates to allow basic game objects to be replaced with entirely different classes in the client and server, yet still use all the same code on top of them.

In the process of moving my code from regular classes to template classes, I uncovered a fundamental language wart or compiler flaw. It has to do with a problem I ran into using STL iterators. Before I go into what the problem is, let me explain iterators a bit.

The people who wrote C++'s standard template library want to break you of the habit of writing things like:

for (int i=0; i < vec.size(); i++)

Instead you should write this:

for (vector< int >::iterator i=vec.begin(); i != vec.end(); i++)

Do you see the improvement? No? It's supposed to simplify code for traversing containers--except that it's twice as much typing! OK, well it also gives your code portability to use different containers besides vector ...theoretically... except that we have to specify "vector" directly in the for loop to say what kind of iterator it is! Oops.

The real motivation behind iterators is that it unifies the concepts for the people who write the container classes. I won't say the users of the container classes can't use iterators in ways that also provide benefit, but the users also bear a burden of extra boilerplate that adds as much work as it saves. This is the sort of thing Bjarne Stroustroup means when he talks about the compiler vendors and library/tools group being overrepresented on the C++ standards committee compared to actual users of C++. At least we users are finally going to get the auto keyword in C++0x, which will allow us to just write the word "auto" in place of the vector::iterator gobbledygook.

But being the good little C++ citizen that I am, I've taken the trouble to use iterators in all my code, even if it is a lot more typing. That's how when I moved my engine definition into templates, I got burned badly.

Where before I had this:

for (vector< GameObj >::iterator i=vec.begin(); i != vec.end(); i++)

I now have:

template < typename T >
... ...
for (vector< T >::iterator i=vec.begin(); i != vec.end(); i++)

What is supposed to happen is that when I instantiate the code with T=GameObj or T=OtherGameObj, the code will get built at the point I instantiated it and the result of the latter will look like the former except with either GameObj or OtherGameObj substituted for T.

Instead, it turns out that you can't (at least on my compiler) use a template argument like T to specify the type argument to a container iterator. You can declare the container using that T, but you cannot access the iterator of the container you just created! On some containers like vector you can just go back to the old notation, but for containers like map<>, iterators are the only way to loop over the container. This is a Really F*ing Big Problem. This is like laying the foundation for a building and realizing you didn't leave room in the floor plan for any doors. The irony is that iterators from the standard template library don't work with template arguments! This is like forgetting to leave room for doors in the plans for a f*ing door factory!
Post a Comment