iDevGames

written by ?

This is a short introduction to the STL (Standard Template Library), which you do need, you just didn’t know you did. It is intended to get you up to speed with STL, and learn enough to use it in your games. If you want to keep on discovering the STL, just Google for STL tutorials; there are a lot of them out there.

Every once in a while, we all need to keep track of lists of things. So, as beginner programmers, we declare static arrays and hope for the best. They are not the least bit flexible, though their size must be determined at compile-time, and they do not resize. So, after a while, we discover malloc, and after a bit of fiddling and crashing, we can finally make run-time sized arrays. We discover realloc, and we get resizeable arrays. All well, we can now start to manipulate our array, sort it, remove elements, insert elements in the middle and finally remove duplicates from it. Clearly, this isn’t much fun, but if we make a class out of it, we can make all those operations member variables. So, let’s say we make a MonsterList class, and teach it how to work with monsters. Now, we need to make one of these classes for WeaponList, CarList, and BirdList-and everything gets a little out of hand. But, this is only for sequential lists-say we would like a linked list or a map? Get out of here. Clearly, there’s bound to be a better way to do all this. Sure thing. Enter STL to make you scream.

The STL can be scary, no doubt about it. The headers are arcane, and it is based on templates, a concept that is not often used by non-advanced programmers. You’ll soon use a new way to write your for-loops (which was quite hard on me…) Still, not having to ever keep a numOfCars member variable around might compensate for that. (Not to mention STL’s string class.)

So, what’s the STL? Well, we’ll start out with a short explanation, and I’ll get back in depth later. In short, it is a collection of template classes for containers. (That is arrays, lists, maps and the like) STL stands for Standard Template Library, obviously. So, why templates? Well, a short explanation of templates might be useful. In short, it is a way to declare a class without making any assumptions about the type of its member variables. I will not go into templates here, all you need to know will unfold soon enough. (But I really recommend looking into templates, they can have a few nifty uses.)

In addition to merely being a collection of container classes, the STL also defines a wealth of operations to manipulate the containers. Among them are sort, copy, insert, copy_if, equal, max/@min@, search, and remove. (Check out the header for more!) One of the best things about the STL is that the containers are very alike, so that if you’ve learnt to use one, you can pretty much use all of them without too much thinking.

Let’s get to it, appetites hopefully whetted. An example:

@
#include <iostream>       // For cout
#include <vector>         // For the STL vector class
#include <algorithm>      // For sort et al.

using namespace std;            // All of the STL is in the std namespace

int main (void)
{
vector<int> numList;   // Declare a vector of int’s

numList.push_back (1);  // Add a few numbers to the end of the list
numList.push_back (4);
numList.push_back (3);
numList.push_back (9);
numList.push_back (-4);
// Now the list looks like this:
// 1, 4, 3, 9, -4

// numList.size() returns the vector’s length. (5, in this case.)
cout << “n The list has “ << numList.size() << “ elements.”;
cout << endl;   // New line

// Write out the elements of the list
for (int i = 0; i < numList.size(); i++)
cout << numList<i> << “, “;
// Let’s sort the list
sort (numList.begin(), numList.end());
// Write out the elements of the list again.
for (int i = 0; i < numList.size(); i++)
cout << numList<i> << “, “;
}
@

…and the play-by-play:

First, we need to include a few headers. Each of them are C++-style includes, without the “.h” suffix. There is one header for each container type, and one for the algorithms. (There are an assortment of others too, but they’re for really advanced uses.) The most common among the container types are vector and list, where vector is very similar to a regular array, and list is linked list. We include here. Then, we tell the compiler to use the std namespace. (Namespaces will not be covered here, though.) The vector<int> line is the first we’ll see of templates, so hang in here. It declares a vector, and tells it to use int as it’s type. Like so:

• vector<int> — declares a vector of ints.
• vector<float> — declares a vector of floats
• vector<ChipMunk> — declares a vector of ChipMunks
• vector<ChipMunk *> — declares a vector of ChipMunk pointers.
• vector<vector<ChipMunk *>> — declares a vector that’ll cause you some headache.

No way to go wrong here, really. Just pass in whatever you want a list of.

Then, we call push_back to add a few numbers to the end of the array. (There are push_front and insert too, for the curious.)

The size() method is the reason you’ll never keep a numOf-variable around-it just returns the number of elements in your vector. We then use it to construct a simple for-loop to sift through all the numbers, and write them out. Note that the vector class uses <i> like any other array. (There is also a numList.at(i) to use, which performs bounds-checking. I really recommend using it for all of your development to be on the safe side-it catches more bugs than you might imagine. If you’re pressed for speed, change all your .at:s to <i> instead when you deploy your build.)

Then, we sort this vector. Unfortunately, this introduces a little thing called iterators, which we had to stumble on sooner or later. An iterator is basically a pointer to an element in your container. It behaves in the exact same way—that is, you can use *myIterator to dereference its data, and ++/—to move back and forth. Almost every algorithm in the STL uses iterators to do it’s work, so you’d better get familiar with them. For now, they’re just fancy pointers.

sort() wants two iterators, one to know where to start sorting and one to know where to stop. begin() returns an iterator to the first element of your vector, and end() returns an iterator to the element after the last of your vector. So, sort(intList.begin(), intList.end()) sorts the entire vector.

So, that’s the short example. Now, it isn’t often that we keep complex lists of ints around—we could use something that is more like the ChipMunk vector. And yes, we just do the following to juggle a ChipMunk list:

vector<ChipMunk *> chipList;
chipList.push_back (new ChipMunk("Stanley"));
cout << chipList.at(0)->health;

This works for everything but the algorithms. You can add, remove, count, and access them as usual. However, let’s take a look at sorting the ChipMunk list. How do you sort ChipMunks? By age, weight, size, or fur factor? This alone is a little problem (very solvable, though), but there’s a more subtle problem. Since the vector is filled with pointers to chipmunks, it would actually sort them the same way as it sorted the intList-numerically. This would mean that the poor ChipMunks would be sorted by their location in memory-not very attractive. The solution is unfortunately a rather complex one, and involves subtleties of both the STL and templates that I won’t go into detail here. Still, here’s how to do it:

template <>

struct std::greater
{
bool operator()(const Foo *leftVal, const Foo *rightVal) const
{
return leftVal->val < rightVal->val;
}
};

Just put that into your class header, and substitute Foo for your class, and val for the variable to sort by. (If you want to look it up, it’s a predicate template specialization) Then, sort using this call:


sort (fooList.begin(), fooList.end(), greater&lt;Foo *&gt;());<br />


So, why doesn’t everybody use the STL if it’s that good? Well, I believe there are two reasons. One, people are not used to working with templates, and are scared away by that. (I was for a number of years!) Two, it is seen as something of the application programming industry that isn’t up to par in performance to be used in games. Well, this is interesting, and I’ll look a little at it.

The speed of the STL is, from my own experience, as well as other articles on the subject, very good. (I certainly couldn’t do any better!) In fact, it is usually a question of executable size than executable speed. More, few games today are so performance-critical that they couldn’t muster the overhead from a few extra function calls per frame. Still, I certainly wouldn’t use an STL vector to manage the pixels of an offscreen buffer—just use it with a little care. Develop with the STL, and if you need the speed later on, just rip it out again. Chances are that you’ll forget it’s even there. The main reason to use the STL is it’s reliability, however. If you’ve ever spent more than a day to track down a bug that was caused by improper bounds checking, then you can count on using that day for optimization later on. I know the quality of my code has improved a lot since I became a zealot.

Let me give you an example: I’m currently developing a 2D side-scrolling platformer. Each level is divided into a number of cells, for visibility checking. Each cell holds a pointer vector to all the level entities (enemies, decorations, platforms, bullets) it can see. Multiple cells can see the same entity if it crosses a cell boundary. Now, this meant two things: depth sorting was broken, (since the cells were drawn out-of-order), and I had to draw a few things twice, as there was no way to tell which entity had already been drawn by another cell. I used the STL to combine all the entity lists from all visible cells into one master “visible list” (copy), depth-sorted (stable_sort) it, and removed all duplicates (unique) from it. Needless to say, this gave me quite a performance improvement, all in five STL calls. I would never have taken the time to crank out all that code and bug-fix it in the first place, so for the performance hit of sorting a few hundred (at max) elements in a list, I improved my frame rate by almost 50%. Now, should I notice that the STL calls take to much time, I could concentrate my efforts to optimize them, yes—but it would have been stupid of me to go for maximum performance from the start.

Thus, my recommendation is to use the STL, and just make everything work; then, profile your code and optimize where needed. Use the days you used to spend bugfixing and writing linked lists to get superior performance.

introduction,to,stl

Further Resources