CS102: Introduction to Computer Science II

3.3: Elements of C++ STL

• Alexander Stepanov's "STL and Its Design Principles" Page

  Watch this video, which discusses the principles of the C++ STL (Standard Template Library) and describes abstraction as it pertains to algorithms and data.

  There are different kinds of abstraction. For hardware, we used part-whole abstraction to decompose a computer into its module hierarchy. In this lecture, you encounter part-whole abstraction for data, but one based on generality for algorithms – when an algorithm is a special case of another algorithm, the latter is more general than the former. The discourse leads to object-oriented and generic programming.

  STL is an organized collection of generic algorithms applicable to a more general collection of problems and tasks. STL templates include Containers, Iterators, Algorithms, and Functors. In this long, but illuminating video, the lecturer gives his insight into the development of STL, its benefits and limitations. Focus on the parts of the lecture that relate to abstraction and composition, and the process of creating programs.

• 3.3.1: Containers and Iterators

  • Jeremy Hansen's "The Rook's Guide to C++" Page

    Read chapter 23, which covers containers and iterators.

  • Wikipedia: "Standard Template Library" Page

    Read this article, which further discusses the STL.
    

• 3.3.2: Complexity and Cost

  • Massachusetts Institute of Technology: Eric Grimson and John Guttag's "Complexity" Page

    In this unit we continue our exploration of abstraction with respect to algorithms. This lecture discusses the classification of algorithms according to how the performance of an algorithm grows relative to the size of the problem or task the algorithm solves or performs. Algorithms are classified by average run-time complexity, defined as the average number of steps the algorithm takes for a problem of size 'n'. Abstraction ignores the implementation of the algorithm and only considers the growth in the number of (primitive) steps an algorithm takes as the size of the problem grows. The video lecture introduces big 'O' notation and gives examples for linear, log, quadratic, and exponential complexity. The lecturer states that exponential complexity should be avoided in general.
    

• 3.3.3: Functors

  • Wikipedia: "Function Object"

    A functor is a name for a function object, which is an object that is called like a function.