TITLE: The Standard Template Library


RESPONSE: pete@genghis.interbase.borland.com (Pete Becker)

	Save your pity until there is such a thing as standard C++. At the 
moment there is no standard. And, with the acceptance of STL into the standard
library at last week's ANSI/ISO meeting, you may find that your pity has been
wasted.


RESPONSE: John Nagle <nagle@netcom.com>

Tell us more about STL, please.  Thanks.


RESPONSE: pete@genghis.interbase.borland.com (Pete Becker), 19 Jul 94

	STL is the Standard Template Library, developed by Alexander Stepanov
at HP. The basic idea is that by imposing a standard interface on all
containers, you are able to write algorithms that manipulate those containers
independently of any of the structural details of the containers. Here's the
basic idea:

	void Show( int *start, int *end )	// 1
	{
	while( start != end )			// 2
		{
		cout << *start;			// 3
		start++;			// 4
		}
	}

	int a[100];
	// add some code to stuff some values into a
	Show( a, a+100 );

	The algorithm implemented in Show() relies on four features of
pointers. 1) pointers can be copied, 2) pointers can be compared for equality,
3) pointers can be dereferenced, and 4) pointers can be incremented. The
crucial insight in STL is that this same algorithm works for any data type
that satisfies these four conditions. That is, Show() should be written as a
template:

	template <class T> void Show( T start, T end )
	{
	while( start != end )
		{
		cout << *start;
		start++;
		}
	}

	int a[100];
	// add some code to stuff some values into a
	Show( a, a+100 );

Having done this, we can now write, say, a vector class that has its own
internal pointer-like thing (known in STL as an iterator):

	template <class T> class vector
	{
	class iterator
	{
	// whatever is appropriate...
	};
	public:
	    iterator start();
	    iterator end();
	// other stuff, of course
	};

And now we can do this:

	vector<int> v(100);
	// add some code to stuff some values into v
	Show( v.start(), v.end() );

As long as each container provides an iterator type that satisfies the four
requirements listed above, and provides member functions start() and end()
that return instances of this iterator type, Show() can be used without
knowing anything about the details of the container.
	Extending this to, say, a linked list is left as an exercise for the
reader.
	There's much more to STL that what I've covered here. There are much
more powerful forms of iterators, and algorithms that depend on those more
powerful forms (qsort, for instance, requires an iterator that supports
random access). When you invoke sort(), if your container only supports the
operations I've used here, the best you can do is some variation on an
insertion sort. On the other hand, if your container provides a random access
iterator, you can use qsort(). When you call sort() the compiler figures out
which way to do it, based on the iterator that you provide. It basically
amounts to an inline call of the appropriate overloaded function.
	Anyway, look for papers in The C++ Report and JOOP on this stuff, and
look for talks at various future conferences.