Chapter 5

5. STL Basics

5.1 C++ Templates

Another thing that C++ offers is the concept of templates. In many ways, templates have many things in common with macros, but are processed by the C++ compiler itself, with the stronger type checking this implies, instead of the preprocessor. As an example, consider the old C macro

#define MAX(x,y) (((x)>(y))?(x):(y))

For simple cases, such as MAX(a,b) and even MAX(a+b,c*d), this will work fine, but what if we do MAX(a++,b++)? This is implementation-specific, but at least one of the parameters is likely to be incremented twice. Also, there is no type checking, which could cause problems with more complex macros, or confusing error messages. This is just a few of the drawbacks of using macros. Another common implementation is

inline int max(int a,int b) { return a>b?a:b; }

which does not suffer from the above drawbacks, but now will only support integers, and a new max() would have to be written for any other data type you might want to use. Even though they could all be overloaded, it would be tedious, and still not work for user-defined types.

C++ templates solves all of these problems. You can simply define max() for a templated abstract data type T, then the C++ compiler will automatically instantiate the template for any data types that is actually used.

template <class T>
inline T max(T a,T b) { return a>b?a:b; }

We now have a pretty perfect max() definition. However, in our game we're currently not really interested in defining template functions, but rather in finding a way to manage a list of sprite objects. Fortunately, templates can also be used for class data types. Here is an example of a template class that can store any data type.

template <class T>
class storage {
public:
 T data;
 storage(T dat) { data=dat; }
 T getdata() const { return data; }
};

The const in there means that the function does not have any side effects, and can safely be called for const (read-only) objects.

However, when we use such a template class, we must tell which data type the template should be instantiated for, like this:

 storage<int> my_int(200);

 cout << my_int.getdata() << endl;

This will, of course, print 200 to the screen. You can think of the instantiation process as replacing every occurrence of T in the class definition with the appropriate type, int in this case. This way, you can make a template class work with practically any data type you want. So what we are going to do, is to let STL work with our sprite base class.

5.2 The Standard Template Library

The Standard Template Library, or STL, is a collection of template classes and template functions to provide a general-purpose data-management system with extreme flexibility without sacrificing efficiency. This is, of course, very convenient for us, since we need to manage a list of game objects in an efficient way. However, this library does have a steep learning curve, and easily confuses beginners. So let's take a brief overview first, then show how it can be used in our game.

The STL provides a wide variety of container classes. We are just going to use sequences, of which STL provides these:

vector, essentially a resizeable array
deque, similar to a vector but can quickly add and remove elements at the beginning and end of the array
list, a double-linked list, can quickly add and remove elements anywhere
slist, a single-linked list, faster than list but one-way

For a game, where objects come and go at will, it seems most reasonable to use the "list" template class, so that's what we are going to use. So, let's see how we are going to use it to store pointers to sprite objects:

#include <allegro.h>
#include <stl.h>
#include "tutorial.h"

#define MIN_Y 8

DATAFILE*data;
BITMAP*backdrop,*framebuf;

class sprite {
protected:
 fix X,Y;
public:
 sprite(fix _X,fix _Y) { X=_X; Y=_Y; }
 virtual ~sprite() {}
 virtual void draw(BITMAP*dest) {}
 virtual void animate() {}
};

typedef list<sprite*> sprite_list;

sprite_list sprites;

class chopper : public sprite {
public:
 chopper(fix _X,fix _Y) : sprite(_X,_Y) {}
 virtual void draw(BITMAP*dest) {
  draw_rle_sprite(dest,(RLE_SPRITE*)data[TUT_CHOPPER].dat,X,Y);
 }
 virtual void animate();
};

void chopper::animate()
{
 if (key[KEY_LEFT]||joy_left) --X;
 if (key[KEY_RIGHT]||joy_right) ++X;
 if (key[KEY_UP]||joy_up) --Y;
 if (key[KEY_DOWN]||joy_down) ++Y;
}

class chopper2 : public chopper {
public:
 chopper2(fix _X,fix _Y) : chopper(_X,_Y) {}
 virtual void animate();
};

void chopper2::animate()
{
 if (key[KEY_LEFT]||joy_left) ++X;
 if (key[KEY_RIGHT]||joy_right) --X;
 if (key[KEY_UP]||joy_up) ++Y;
 if (key[KEY_DOWN]||joy_down) --Y;
}

int main()
{
 allegro_init();
 install_keyboard();
 initialise_joystick();

 data=load_datafile("tutorial.dat");

 set_gfx_mode(GFX_VGA,320,200,0,0);

 set_palette((RGB*)data[TUT_GAMEPAL].dat);

 // create 320x192 backdrop
 backdrop=create_bitmap(320,192);
 for (int Y=0; Y<128; Y++) hline(backdrop,0,Y,319, (Y/2)+128);
 for (int Y=128; Y<192; Y++) hline(backdrop,0,Y,319, ((Y-128)/2)+192);

 // create 320x200 double buffer
 framebuf=create_bitmap(320,200);
 clear(framebuf);

 chopper Hero(50,100);
 chopper2 AnotherHero(250,50);
 sprites.push_back(&Hero);
 sprites.push_back(&AnotherHero);

 while (!key[KEY_ESC]) {
  // build frame
  blit(backdrop,framebuf,0,0,0,MIN_Y,320,200);
  // draw sprites
  {
   sprite_list::const_iterator spr=sprites.begin();
   while (spr!=sprites.end()) {
    (*spr)->draw(framebuf);
    spr++;
   }
  }
  // display frame
  vsync();
  blit(framebuf,screen,0,0,0,0,320,200);
  // animate sprites
  poll_joystick();
  {
   sprite_list::const_iterator spr=sprites.begin();
   while (spr!=sprites.end()) {
    (*spr)->animate();
    spr++;
   }
  }
 }
 return 0;
}

Let's go through what exactly it is we are doing here. First, we #include <stl.h>, which should be fairly obvious what for. This is really a convenience header that includes all other STL header, it's not really part of STL itself. We could include the exact headers we need, especially if we wanted to reduce compilation time, or make our programs more portable, but for simplicity, we'll just use stl.h.

Next, we use typedef to define sprite_list as the instantiation of the list template class we are going to use. This is not strictly necessary, but it's easier to remember and perhaps change later, than to use list<sprite*> all over. Then we define the global variable sprites to be a variable of this type; that is, it will be our sprite list.

In the main code, we use the push_back() method to insert our helicopter object as the last element in the sprite list. We could also use push_front() instead to insert it as the first. We also insert two helicopter objects, to show that it actually works.

In the main game loop, we traverse the linked list twice, once to draw the sprites onto the double buffer, and once more to move them about. In each of these traversals, we need a variable that tells us where in the list we are. This is what an iterator does. Note that in C++ you can define types inside a class, and STL has conveniently defined the appropriate iterator types iterator and const_iterator inside the class, so we can define an iterator to traverse the list. The ++ operator of the iterator moves it to the next element. The * (dereferencing) operator of the iterator returns the element itself, which happens to be of the type sprite*.

As you can see, the power of STL is what we just did, to abstract a complex data structure into something as simple, flexible and manageable as this, even if it does take some effort to learn.

To learn more, proceed to the next chapter