An extract from http://www.byte.com/art/9510/sec12/art3.htm :

The Standard Template Library

Part of the draft C++ standard, STL provides the framework for building
generic, highly reusable algorithms and data structures

Alexander Stepanov

In every programming language, there's a need for various data structures,
such as vectors, lists, and associative arrays. Programmers also need
fundamental algorithms -- for sorting, searching, and copying -- defined
for the data structures. It has long been lamented that C++ doesn't provide
a good set of standard data structures.

But at last this problem has been remedied. The Standard Template Library
is a framework of data structures (called containers in STL) and algorithms
accepted as part of the draft C++ standard. A reference implementation of
STL has bee n put into the public domain by Hewlett-Packard (it can be
downloaded from butler.hpl.hp.com), and a growing number of commercial
vendors are now shipping STL.

In the short time since its release, STL has generated many emotional --
and conflicting -- assessments. On one hand, for example, Bjarne Stroustrup
of Bell Laboratories calls it a "large, systematic, clean, formally
sound, comprehensible, elegant, and efficient framework." On the other
hand, Pamela Seymour of Leiden University writes that "STL looks like
the machine language macro library of an anally retentive assembly language
programmer."

Goal: Generality + Efficiency

STL is not an attempt to impose yet another standard on a suffering
humanity. And it was not designed by or for a committee. It is the result
of over 15 years of research in generic programming that I've done in
different places, with different collaborators, and in different
programming languages. I did this research with a concrete goal in mind: to
find a way to write algorithms in the most general way, but in such a way
that their abstractness would not impose any performance penalty.

What do I mean by "in the most general way"? Simply that an
algorithm works on all data types for which it makes sense. For example, a
linear-search algorithm is written in the most general way if it can search
any data structure for which the operations of looking at data, going to
the next data element, and indicating the end of the search range are
defined. So, it should work for an array, a singly linked list, a doubly
linked list, a file, and even a binary tree.

An algorithm should also work for portions of such structures. For example,
you might want to search half a list or sum the set of elements in an array
that are n spaces apart (i.e., a stride).

What do I mean when I say that an algorithm does not "impose any
performance penalty"? In other words, how do you know that a generic
algorithm is efficient? An algorithm is called rel atively efficient if
it's as efficient as a nongeneric version written in the same language, and
it's called absolutely efficient if it's as efficient as a nongeneric
assembly language version.

For many years, I tried to achieve relative efficiency in more advanced
languages (e.g., Ada and Scheme) but failed. My generic versions of even
simple algorithms were not able to compete with built-in primitives. But in
C++ I was finally able to not only accomplish relative efficiency but come
very close to the more ambitious goal of absolute efficiency. To verify
this, I spent countless hours looking at the assembly code generated by
different compilers on different architectures.

I found that efficiency and generality were not mutually exclusive. In
fact, quite the reverse is true. If a component is not efficient enough, it
usually means that it's not abstract enough. This is because efficiency and
abstractness both require a clean, orthogonal design. A similar phenomenon
occurs in mathematics: Making a proof more abstract makes it more concise
and elegant.

-- mail{at}ozzmosis.com

--- timEd/FreeBSD 1.11.b1