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:
- describe the basic components used in the C++ Standard Template Library;
- demonstrate the various components within the C++ Standard Template Library; and
- solve simple problems using C++ template programming.
3.1: History and Motivation
Read this page to gain insight into the history of C++' Standard Template Library. You will see that it did not suddenly appear on the scene. Also, its ideas have been incorporated into other languages. In particular, its support of data-generic programming is important to the construction and flexibility of modern systems.
3.2: Main Design Ideas
Paraphrasing the introduction, this video introduces STL, a formal part of the modern C++ language standard. The speaker demonstrates many STL core features (iterators, algorithms, and data structures). He elaborates on technical details in very substantive way. STL, is a C++ library of classes, algorithms, and iterators, while providing many fundamental algorithms, data structures, and templates.
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: The Elements of C++ STL
Software engineering implements general computation using four fundamental steps: requirements, design, code, and validation. In process terms, this becomes defining a problem or task, designing a solution, coding the solution, and testing the solution. C++ STL supports 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. Essentially C++ STL, and also Java Container Library, are a set of pre-tested trusted modules that implement standard data structures, containers, traversals, and data manipulations.
Study these slides for a good foundation discussion of generic programming concepts. The examples are in C++ but the principles apply also to Java.
The objective of the programming process is a solution to a problem or to complete task. The programming process itself includes requirements development (understanding the problem), design (formulating a plan or strategy), implementation in a programming language (completing the plan by providing details from previous or known solutions), verification and validation (checking the solution). Given a specific problem (program), we can develop a specific solution (specific program); or, we could use abstraction to view the program generically, and develop a generic solution. Using generic functions and generic data structures, a generic design and generic implementation can be developed that will solve, not just a specific problem, but a general class of problems. That is the idea of generic programming; a form of reuse on a large scale, of requirements, design, and implementation.
Libraries of Templates and Containers are an approach to generic programming. One approach to generic programming is a capability that allows functions that apply to more than one type of data (polymorphism). For example, a generic search should work for searching data of any type, as long as the data is comparable.
Inheritance, Polymorphism, and the STL
Read this chapter, which covers iterators for groups of classes in contiguous memory.
Read Chapter 2 for an introduction to basic STL classes and their application.
A functor is a name for a function object, which is an object that is called like a function.
Unit 3 Assessment
- Receive a grade
Take this assessment to see how well you understood this unit.
- This assessment does not count towards your grade. It is just for practice!
- You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.