CS102: Introduction to Computer Science II
Unit 3: C++ Standard Template Library
Nearly every C++ programmer uses the C++ Standard Template Library (STL), a powerful and highly useful library of generic-typed data structures and algorithms. In this unit, we will learn how and why the STL was originally developed. The unit will also introduce you to the history and basics of templates and generic programming before presenting the structures (Containers, Iterators, and Functors) and algorithms that the Standard Template Library contains. By the end of this unit, you will be familiar with the STL, its uses, and its structures and algorithms.
Completing this unit should take you approximately 7 hours.
Upon successful completion of this unit, you will be able to:
- demonstrate an understanding of the history of Generic Programming and the motivation behind the Generic Programming development;
- demonstrate an understanding of the detailed components used in Generic Programming; and
- demonstrate an understanding of the basic components used in the Standard Template Library with C++.
Read this section for an explanation of the history and purpose of generic programming and the precursor language, Ada. Ada is an Object-Oriented programming language used predominantly in military applications. It shares many of its features - including its structure and typing, with C++. While both languages were developed in the same year, Ada's rapid adoption by certain circles within the Computer Science world led computer scientists to modify C++ by adopting some of Ada's features in subsequent C++ releases. These changes are seen as an important evolutionary step in Object-Oriented programming. These materials cover generic programming, precursor Ada, and ANSI/ISO.
A software engineering version of the general computation has four fundamental states: requirements, design, code, validation; or in process terms, defining a problem or task, designing a solution, coding the solution, and testing, the solution. Programming paradigms support the transition from designing to coding. To exploit the similarity among problems and tasks, it is beneficial to reuse existing designs and code on new problems and tasks. The principle concepts of modularity, abstraction and composition support reusability. This article shows how programming languages implement these principles using data, expressions, functions, and control statements.
Watch these lectures. These videos are part of another course. For our course, focus on the hardware hierarchy introduced in the first 20 minutes of lecture 1 and the first 34 minutes of lecture 2. These videos reinforce the concepts of modularization, abstraction, composition, and hierarchy, but it does so by stepping 'aside' to take a look at computer hardware.
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.
Read chapter 23, which covers containers and iterators.
Read this article, which further discusses the STL.
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.
A functor is a name for a function object, which is an object that is called like a function.