The STL (Standardized Template Library)

Written by Gordon Zeglinski

Introduction

There is a new C++ library out called STL (Standardized Template Library). As the name implies, the library is being standardized and consists of template classes and functions. There are a couple of versions of STL available. The easiest (and cheapest) one to get is the HP source code available from butler.hpl.external.hp.com in the /stl directory.

So now that you know where to get it, let's take a brief look at it.

What Is STL?

STL is a set of template functions and classes that provide a portable compiler neutral toolkit for manipulating and storing data. Roughly speaking, STL does for "container objects" what the IOSTREAM library does for I/O. The two implementations of STL that I've looked at were not header file compatible. Thus, one should consider STL still in its infancy.

The design of STL is very different from most other container type object classes. While most use templates, they also use inheritance and virtual functions. This both affects the performance and the ability to share the object across processes. Virtual functions are usually implemented as lookup tables attached to the object's instance; when a virtual function is called, its address is pulled from the lookup table. This address is then used to call the appropriate member function. If, for example, an instance of an object is created in shared memory, and this object has virtual functions, the lookup table would be filled with addresses of functions belonging to the process that created the instance. This of course means that only the process creating this instance can use this instance. Because STL doesn't use virtual functions, this limitation is not present.

Another interesting point about the design of STL is that functions to sort, search or otherwise manipulate data are not member functions of the container classes. This allows the same functions to operate on C-style arrays and C++ based container classes. The class can be divided into 5 primary components: algorithms, containers, iterators, function objects and adaptors. Algorithms perform actions such as sorting, searching, merging and the like. Containers manipulate groups of objects and the memory they require. Iterators are used to move through a container. Function objects encapsulate functions used by other parts of the library. Adaptors provide an alternative interface to a component of the library.

A Simple Program

Let's look at a simple simple test program using standard C-style arrays. The following sample is a modified version of the sort_example.cpp program. The program was modified to work with C-Set++. Also note that the STL header file algobase.h had the definitions for min and max commented out to prevent conflict with the min and max macros defined in C-Set++.

#include "defalloc.h"
#include "algo.h"
#include "tempbuf.cpp"  // Can also just compile and link with this file
#include "heap.h"
#include "function.h"

#include "random.cpp"   // Can also just compile and link with this file

//Rand is used to fill the array with sequential numbers
class Rand{
   int I;

public:
   Rand(unsigned long X):I(X){}

   int operator()(){return I++;}
};

void main(int argc, char *argv[]){
    int    *last1;
    int    *middle;
    int	test_sequence1[15];

    middle = test_sequence1 + 10;
    last1 = test_sequence1 + 15;

    ostream_iterator<int> out_stream(cout, " ");
    less<int> less_than;

    generate((int*)test_sequence1, last1, Rand(0));
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    random_shuffle((int*)test_sequence1, last1);
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: (the sequence of 0 through 14 with elements in random order)

    sort((int*)test_sequence1, last1);
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    random_shuffle((int*)test_sequence1, last1);
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: (the sequence of 0 through 14 with elements in random order)

    sort((int*)test_sequence1, last1, less_than);
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    random_shuffle((int*)test_sequence1, last1);
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: (the sequence of 0 through 14 with elements in random order)

    stable_sort((int*)test_sequence1, last1);
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    random_shuffle((int*)test_sequence1, last1);
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: (the sequence of 0 through 14 with elements in random order)

    stable_sort((int*)test_sequence1, last1, less_than);
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    random_shuffle((int*)test_sequence1, last1);
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: (the sequence of 0 through 14 with elements in random order)

    partial_sort((int*)test_sequence1, middle, last1);
    copy((int*)test_sequence1, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 1? 1? 1? 1? 1?

}

In the above example, last1 and middle are iterators. The array test_sequence1[15] is the container.

Basically, the sample involves filling the container, shuffling the elements and then sorting them using the various sort algorithms. Similarly, one can use a vector container. A vector container is the closest thing to a C array. The follow example uses a vector instead of an array.

#include "defalloc.h"
#include "algo.h"
#include "tempbuf.cpp"  // Can also just compile and link with this file
#include "heap.h"
#include "function.h"
#include "vector.h"

#include "random.cpp"   // Can also just compile and link with this file

//Rand is used to fill the array with sequential numbers
class Rand{
   int I;

public:
   Rand(unsigned long X):I(X){}

   int operator()(){return I++;}
};

void main(int argc, char *argv[]){
    vector::iterator   Start;
    vector::iterator   last1;
    vector::iterator   middle;
    vector        	test_sequence1(15);

    ostream_iterator out_stream(cout, " ");
    less less_than;

    Start=test_sequence1.begin();
    last1 = Start + 15;

    generate(Start, last1, Rand(0));

    Start=test_sequence1.begin();
    middle = Start + 10;
    last1 = Start + 15;

    copy(Start, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    random_shuffle(Start, last1);
    copy(Start, last1, out_stream), cout << endl;
    // Output: (the sequence of 0 through 14 with elements in random order)

    sort(Start, last1);
    copy(Start, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    random_shuffle(Start, last1);
    copy(Start, last1, out_stream), cout << endl;
    // Output: (the sequence of 0 through 14 with elements in random order)

    sort(Start, last1, less_than);
    copy(Start, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    random_shuffle(Start, last1);
    copy(Start, last1, out_stream), cout << endl;
    // Output: (the sequence of 0 through 14 with elements in random order)

    stable_sort(Start, last1);
    copy(Start, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    random_shuffle(Start, last1);
    copy(Start, last1, out_stream), cout << endl;
    // Output: (the sequence of 0 through 14 with elements in random order)

    stable_sort(Start, last1, less_than);
    copy(Start, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    random_shuffle(Start, last1);
    copy(Start, last1, out_stream), cout << endl;
    // Output: (the sequence of 0 through 14 with elements in random order)

    partial_sort(Start, middle, last1);
    copy(Start, last1, out_stream), cout << endl;
    // Output: 0 1 2 3 4 5 6 7 8 9 1? 1? 1? 1? 1?
}

As before, last1 and middle are iterators. The container is test_sequence1. However, a new iterator called Start is introduced. In the first example, the container could double as the starting iterator because the container was simply a pointer. In the second sample, the container is a vector class. The vector class can't act as an iterator so we use Start. In our last example, we will use the set manipulation functions to create a vector based upon 2 other vectors.

typedef vector<int> IVec;

void main(int argc, char *argv[]){
   vector<int> Set1,Set2,Output;

   ostream_iterator<int> out_stream(cout, " ");
   less<int> less_than;

   //let's insert some values at the END
   // of the vector
   Set1.insert(Set1.end(),10);
   Set1.insert(Set1.end(),11);
   Set1.insert(Set1.end(),2);
   Set1.insert(Set1.end(),1);
   Set1.insert(Set1.end(),12);
   Set1.insert(Set1.end(),5);

   Set2.insert(Set2.end(),10);
   Set2.insert(Set2.end(),5);
   Set2.insert(Set2.end(),2);
   Set2.insert(Set2.end(),20);
   Set2.insert(Set2.end(),24);

   //let's display our two vectors
   cout<<"Set 1"<<endl;
   copy(Set1.begin(),Set1.end(), out_stream), cout << endl;
   cout<<"Set 2"<<endl;
   copy(Set2.begin(),Set2.end(), out_stream), cout << endl;

   //set operations work on sorted containers.. sooo
   //let's sort these puppies and then display them..

   sort(Set1.begin(),Set1.end());
   cout<<"Set 1 Sorted"<<endl;
   copy(Set1.begin(),Set1.end(), out_stream), cout << endl;

   sort(Set2.begin(),Set2.end());
   cout<<"Set 2 Sorted"<<endl;
   copy(Set2.begin(),Set2.end(), out_stream), cout << endl;

   //let's get the union and put it in the Output vector

   set_union(Set1.begin(),
		 Set1.end(),
		 Set2.begin(),
		 Set2.end(),
		 insert_iterator<IVec>(Output,Output.begin()));
   cout<<"Union"<<endl;

   //display the output vector
   copy(Output.begin(),Output.end(), out_stream), cout << endl;

   //display the result
   Output.erase(Output.begin(), Output.end());

   //get the intersection
   set_intersection(Set1.begin(),
			  Set1.end(),
			  Set2.begin(),
			  Set2.end(),
			  insert_iterator<IVec>(Output,Output.begin()));
   cout<<"Intersection"<<endl;
   copy(Output.begin(),Output.end(), out_stream), cout << endl;

   Output.erase(Output.begin(), Output.end());

   //lets find the difference between set1 and set2
   set_difference(Set1.begin(),
			Set1.end(),
			Set2.begin(),
			Set2.end (),
			insert_iterator<IVec>(Output,Output.begin()));
   cout<<"Difference Set1 <-> Set2"<<endl;
   copy(Output.begin(),Output.end(), out_stream), cout << endl;
   Output.erase(Output.begin(), Output.end());

   //lets find the difference between set2 and set1
   set_difference(Set2.begin(),
			Set2.end(),
			Set1.begin(),
			Set1.end (),
			insert_iterator<IVec>(Output,Output.begin()));
   cout<<"Difference Set2 <-> Set1"<<endl;
   copy(Output.begin(),Output.end(), out_stream), cout << endl;
}

An interesting point worth noting is that the set_* functions use iterators to determine where the results of the set operations go. There's no reason the output couldn't have been sent directly to the display instead of to the Output vector. This is left as an exercise for the curious.

Wrapping Things Up

Well, that's about it for our quick look at STL. The files arraysort.cpp, vecsort.cpp and vecunion.cpp are included in OOPS.ZIP if you wish to try and compile the sample programs. Note the HP STL release may not compile on your particular C++ compiler. It requires a very accurate template implementation to work.

Coming up in future issues, we'll be looking at various OS/2 C++ compilers. We'll be using STL as part of our compiler testing.