TITLE: designing STL in C++ and other languages

(Newsgroups: comp.lang.c++, 12 May 97)

[ "He" below refers to Alexander Stepanov, the designer of
  the Standard Template Library (STL). -adc ]


XXX: cosc19z5@Bayou.UH.EDU (cosc19z5@bayou.uh.edu)

> The impression that I got from reading his postings was that while
> he could do STL in other languages, he couldn't do them in the same
> way that he did them in C++.


KOENIG: ark@research.att.com (Andrew Koenig)

A more accurate statement might be that he could not make make STL-like
libraries in other languages do all the things that they can do in C++,
different interface or not.

Here is one example from his long posting.  In STL, there is a swap
function:

	template<class T> void swap(T& x, T& y) {
		T z = x; x = y; y = z;
	}

This function is defined in terms of assignment and initialization for
type T.  Such a definition is natural, of course, but has the disadvantage
that for some types it might be much slower than expected.  For example:

	vector<int> v1, v2;
	// ...
	swap(v1, v2);

This call to swap will result in copying v1 to a temporary, assigning v2
to v1, and then assigning the temporary to v2.  In most implementations
of STL, that will require copying all the elements of v1 and v2 -- twice.
It is possible to imagine implementations that will avoid the copies by
inserting a level of indirection, but that would impose extra overhead on
every access to an array element.

On the other hand, it is possible to design vectors so that they have
a fast swap operation: The two data structures just exchange memory with
each other.  So suppose that vectors have that operation (in STL, they do),
and that it is expressed as v1.swap(v2).

Then there are two possible ways of swapping vectors:

	swap(v1, v2);	// horribly slow
	v1.swap(v2);	// fast

This is an unhappy state of affairs, because if you are writing a generic
program that needs to swap the values of two objects, you don't want to have
to know what the object types are in order to avoid all that overhead.

However, as Alex pointed out, C++ offers a useful solution to that problem,
namely a partial template specialization:

	template<class T> void swap(vector<T>& x, vector<T>& y) {
		x.swap(y);
	}

What we have said is that if x and y are vectors -- which can be determined
during compilation -- then swap(x, y) should use the fast swap operation
for vectors.  Otherwise, it should use copy and assignment.  With partial
specialization, the situation then becomes

	v1.swap(v2);	// fast
	swap(v1, v2);	// also fast

An important point about the partical specialization technique is that the
decision is made at compile time, with no run-time overhead at all.
What Alex was pointing out is that C++ is one of very few languages
that allows such compile-time type decisions.  It is certainly the only
such language that is any anywhere near such widespread use.

XXX:

> Maybe I'm mistaken, but the impression I'm getting is that he
> found that he couldn't do a 1-1 translation from C++ to Scheme
> (obviously) and concluded "therefore it can't be done" without
> realizing that maybe it could be done (and done better) in
> Scheme, it just needed a different approach since Scheme is
> a much different language.

KOENIG:

Alex wrote a generic algorithms library in Scheme before he ever learned C++.