Software Interest Group

• Schedule
• Documentation
• Resources
• Thanks

STL Tutorial

by Andy Linfoot

Hello, this is a short tutorial on the Standard Template Library, or STL as it is commonly called. After reading this tutorial, or even before getting done, you might want to see the official SGI website. It can be found at "http://www.sgi.com/tech/stl/". It is a great place to start and a great reference on all things STL and generic programming. Also you might try doing a search on Google.

Templates are the corner stone of the STL. A template is a way of writing generic functions and classes that reduces type dependencies. In C++ this lets a lot of code to be reused without having to be rewritten. Generic Programming is programming with templates. In the examples we will look at below you will see exactly what I mean. The STL is a library of common data structures and algorithms written as templates.

Using the STL is like having a personal assistant that is a great programmer. For instance if you needed to sort something you could use the STL sort algorithm. Maybe you also need a random access container, a doubly linked list, or a priority queue. This is where the STL is so helpful and useful. It lets you concentrate on the ideas of your project and not on the implementation details of a sort, find_if, copy, vector, list, etc.

Download the source code for these examples, "complex.tar.gz" and "fraction.tar.gz"

Generic Functions

In this section we will examine a small example of using Generic Functions (templates) in a Newton root finding. The goals are to write a generic function and how they are declared and called. All the code here was written and tested on a PowerBook G4 running OS X 10.3.6. Therefore there might be some minor changes needed in the makefile and what not. I have noticed that the Apple compilers are a tad looser than vanilla GCC. The source code for this example is in "complex.tar.gz", so without further ado lets get started.

Let's start with complex numbers. In C++ they are implemented as templates. Thus, if you find yourself in the need of computing something with complex numbers, don't worry they are here. Of course there is always FORTRAN, but then again you might not want all the restrictions associated with using that language. To use them just include the appropriate header. On my system this is done by just adding the following directive, #include <complex>. Declaring a variable as a complex number has a minor wrinkle. Looking at the source code we can see how it is done.

## declaring complex numbers

	// complex numbers ... 
	complex<double> a(1,2);
	... 
	complex<double> c;

At first sight this seems rather strange. The type of complex number is enclosed in the "< >". Complex numbers can be declared as float, double, and long double. All the operators are overloaded as can be seen in the source code. In addition they can be passed to functions in <cmath> and also have real and imaginary accessors.

Suppose we had a function whose domain was "numbers", for instance we wanted to cube the inputed number and subtract one from the result. To implement this once we could use a function template or generic function as it is commonly called. The function will take the inputed number raise it to the third power and then subtract one from the result, as such it will be semantically the same function regardless of the type of inputed number. Doing this without templates one would have to write a function for each type that might be used. A lot of code would be duplicated. We would have a function for integers, floats, longs, doubles, etc. Or worse we could write one function and have everything implicitly cast, an even worse idea.

The syntax for writing a generic function is,

Breaking it down, the above is not much different than a normal function. The exceptions are the extra "qualifier" declaring it as a template function. Also the return-type can be any valid return type including other templates. Arguments as expected can be any mixture of predefined types or templates just as with any normal function. For instance this is how the function for cubing and then subtracting one would look as a generic function.

## example of a generic function

    // the function ( )^3 - 1;
    template <class T_> T_ f(T_ &point) {

        return point*point*point-static-cast<T_>(1);

    }

This function will now work on any number type in C++, whether the input was integers, floats, complex, etc. Something of note is that in C++ it is best to avoid C-style casting. There are several built in casting operators that should be used, hence the "static-cast". It is somewhat off topic to discuss it here. If you are curious and want to know more there are many good references and web pages online.

Declaring this function is done in the usual way except for the template specifier. The important point is that there is no need to declare it separately for each type used. As can be seen in the toy code the generic functions are used with complex and doubles with only the following declaration.

## declaring a generic function

// generic functions
template <class T_> T_ f(T_ &point);

Finishing up the example is a composite function representing Newton's root finding method. As you will notice it is also written as a generic function.

## Newton's Method

    template <class T_> T_ newton(int stop, double delta, T_ &point) {

        T_ tmp_zero, tmp_one;

	tmp_zero = point;
       
        for (int k = 0; k < stop; k++) {
	
	    tmp_one = tmp_zero - f(tmp_zero)*pow(df(tmp_zero),-1);

	    if (abs(tmp_one - tmp_zero) < delta)
	         return tmp_one;
                
	    tmp_zero = tmp_one;

	}
        
	return tmp_one;
        
}

Important things to notice are the argument list contains a variety of types. Also some local variables are created using the template parameter, T_. The other generic functions found in function.h are also called by this function with all types being resolved by the compiler.

In main.cpp these functions are used to find some roots using complex and double numbers. All the magic happens at compile time as the appropriate function is built by the compiler for the specified types. Hence in our example the compiler makes versions of the functions for doubles and versions for complex<double>'s. What functions get built depend on the instantiations encountered during compilation.

This is the output I get on my machine when the code is compiled and executed.

Hello, SWIG!

COMPLEX NUMBERS EXAMPLE
a: (1,2)
b: (-5,-1)

Re(a): 1 Im(a): 2
a+b: (-4,1)
a*b: (-3,-11)

calling some functions
f(a): (-12,-2)
df(a): (-9,12)


NEWTON EXAMPLE
finding roots ... using complex numbers
a root: (1,1.28742e-25)
another: (-0.5,-0.866025)

now using doubles
the root: 1

Now onto the next example.

Containers, Iterators, and Algorithms

In this example we will use the vector container type found in the STL in an example computing continued fractions. The vector container is basically a variable sized array. The source code can be found in "fraction.tar.gz". Again all the code was written and run on a PowerBook G4 so your mileage might vary.

Containers are generic data structures that are built to hold other objects. For instance in this example we will be using the vector container. The STL has many other containers, much too many to discuss here. In addition to holding objects a container also needs to have methods of accessing these objects. This is were iterators are important. Iterators are generalized pointers. An iterator is an object used to access objects in containers and also used as an interface between containers and algorithms. So technically containers hold other objects and define a way to access the held objects. For instance the vector container we will be using is sequence with random access of elements. The other types of containers in the STL will define access differently, make the elements associated in some manner, or both.

As the number of steps in a general continued fraction calculation can not be known ahead of time it is convenient to have a variable sized array. This is were the beauty of the STL is once again on full display. Someone has already done the heavy lifting for us. All we need to do is include the appropriate header file and designate what the container will hold. The vector container like all the goodies in the STL is in namespace std. To use the vector container give the following directive, #include <vector>.

In main.cpp the container is designated much like complex numbers in the previous example. For this example the vector is designated to hold integers. Vectors in general can hold any object, although if you are using your own classes make sure you at least define a copy constructor or some weird behavior might ensue. The declaration looks like this,

# declaring a vector container

     std::vector<int> r,q;

It is not necessary to define the size of the container, remember they are variable sized. To append the container just use "push_back". This algorithm attaches a copy of the input to the end of the vector. Note vectors can not directly contain different types, for example a our vector could not be used to contain doubles as well. If you need to do something like that you will probably need to make your own container, but it is perfectly reasonable to define classes using containers from the STL. This is more than we have time, so lets get back on topic. The source code has several examples of appending our vectors. Here are the first examples.

# appending a vector container

    r.push_back(tmp_one%tmp_two);
    q.push_back((tmp_one - *r.begin())/tmp_two);

In the second example we see the first use of iterators. Each container has a beginning and an end. The beginning of container X is always X.begin() and the ending is always X.end(). As iterators are like pointers they can be incremented. For instance the second entry in X would be accessed as X.begin()+1. Vectors are somewhat special in that they also have the operator [] overloaded so in our example code we could have just accessed everything using subscripts.

Iterators are declared much like containers. To define an iterator for a vector of integers we would do it as follows.

# declaring an iterator

    vector<int>::iterator foo_bar

The calculation more or less proceeds as you might imagine. The division algorithm is applied until the remainder is 0. At which time the continued fraction calculation is complete. The interesting point is that an iterator pointing to the end of our vector will continue to point to the end as we push_back on the vector. It automatically gets advanced.

Now the displaying of our containers is our first run in with an algorithm in the STL, copy(). The display() function outputs to the terminal the contents of a vector. As you will notice the input and output of the copy() algorithm are iterators. As previously mentioned iterators are not only a way to access elements in a container, but also provide a way of interfacing containers to algorithms.

Some other algorithms demonstrated in the example code are element insertion, sorting, and swapping. In every case the input are iterators and the output are iterators. The code is pretty well commented so take a look at the various operations and the associated comments.

This is a typical interaction with the program for this example.

Hello, SWIG!
Computing a Continued Fraction.
input numerator: 1973
input denominator: 101
the coefficients! q ->
19 1 1 6 1 2 2 
the remainders! r -> 
54 47 7 5 2 1 0 
some useful canned algorithms, since we are here
SWAPPING VECTORS
q -> 
54 47 7 5 2 1 0 
r ->
19 1 1 6 1 2 2 
INSERTING ELEMENTS
q -> 
101 19 1 1 6 1 2 2 
r -> 
19 10101 1 1 6 1 2 2 
SORTING
the whole vector
1 1 1 2 2 6 19 101 
a section
1 1 6 19 10101 1 2 2 

Conclusion

The STL is a great collection of canned data structures and algorithms. It alleviates a lot of implementation issues and lets you concentrate about the ideas of your project. For further reading I would suggest the SGI website, "http://www.sgi.com/tech/stl/". Also doing a search on Google should turn up some interesting stuff. Good luck and may the compiler be friendly.