Standard Template Library, STL

Introduction

History

Why STL?

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:

Main Components

Containers

  • data structures that contain a homogeneous collection of objects
  • class templates parametrized by element type
  • examples:
    • vector
    • list
    • set
    • map

Algorithms

  • function templates parametrized by argument type
  • examples:
    • sort
    • find
    • copy
    • binary_search
    • for_each

Iterators

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

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.

The last line is particularly notable.