Introduction

• part of the C++ Standard Library
• a selection of basic algorithms, data structures and related components
• heavy use of templates to achieve abstractness without loss of efficiency
• based on generic programming

History

• 1979: the idea of generic programming (Alex Stepanov)
• 1987: Ada library (Stepanov and Dave Musser)
• 1994: C++ library (Stepanov, Musser and Meng Lee)
  • July: approved by ANSI/ISO comittee
  • August: freely available on the internet
• 1998: part of C++ Standard Library

Why STL?

• contains some of the most useful algorithms and data structures
• part of C++ Standard Library
  • available to almost every C++ programmer
  • ... also in the future
  • lots of documentation, guides, examples, etc.
  • established programming techniques, idioms and styles
  • readable to many C++ programmers
  • usually very-well tested
  • usually highly optimized (might use optimizations that are not available to ordinary programmer)
• generic programming
  • highly customizable without loss of efficiency
  • model for many other algorithm libraries
  • close to implementing an abstract algorithm
• problems
  • limited selection of algorithms and data structures
  • learning curve
  • high compilation time
  • sometimes messy expressions
  • long error messages
  • limited support on older compilers
  • standard cannot be changed

Generic Programming

The programming paradigm underlying STL is called generic programming. Here is one definition:

"Generic programming is a sub-discipline of computer science that deals with finding abstract representations of efficient algorithms, data structures, and other software concepts, and with their systematic organization. The goal of generic programming is to express algorithms and data structures in a broadly adaptable, interoperable form that allows their direct use in software construction. Key ideas include:

• Expressing algorithms with minimal assumptions about data abstractions, and vice versa, thus making them as interoperable as possible.
• Lifting of a concrete algorithm to as general a level as possible without losing efficiency; i.e., the most abstract form such that when specialized back to the concrete case the result is just as efficient as the original algorithm.
• When the result of lifting is not general enough to cover all uses of an algorithm, additionally providing a more general form, but ensuring that the most efficient specialized form is automatically chosen when applicable.
• Providing more than one generic algorithm for the same purpose and at the same level of abstraction, when none dominates the others in efficiency for all inputs. This introduces the necessity to provide sufficiently precise characterizations of the domain for which each algorithm is the most efficient."

Main Components

Iterators

• generalized pointers
• represent positions in containers
• used as input to algorithms
• abstraction layer between algorithms and data

A Simple Example

unix command sort in basic form

1. read lines from standard input
2. sort them
3. write to standard output

int main() {
  vector<string> V;
  string tmp;

  while (getline(cin, tmp))
    V.push_back(tmp);

  sort(V.begin(), V.end());
  copy(V.begin(), V.end(), ostream_iterator<string>(cout,"\n"));
}

The example already illustrates the main components.

• container
  • vector<string>
• algorithms
  • sort
  • copy
• iterators
  • V.begin(), V.end()
  • ostream_iterator<string>(cout,"\n")

The last line is particularly notable.

• The algorithm copy copies elements from one container to another.
• Here the target is the standard output stream cin made to look like a container of strings.