Unit 7: Template Programming
In Unit 3, we discussed the C++ Standard Template Library and introduced the concept of template programming. In this unit, we will further explore both templates and generic programming, cultivating a broader understanding of the topic. We will begin with a review of the STL and a discussion of the motivation behind template development. We will then discuss templates in a more generic fashion, referring back to the STL where necessary, and take a look at how templates are utilized within Java, comparing and contrasting with the C++ STL. By the end of this unit, you will recognize the importance of templates, be able to identify when they are needed, and know how to apply them efficiently.
Completing this unit should take you approximately 5 hours.
Upon successful completion of this unit, you will be able to:
- demonstrate a detailed understanding of generic programming and principles in the standard template library;
- demonstrate an understanding of various types used within the standard template library in C++; and
- demonstrate an understanding of various types used within the standard template library in Java.
7.1: Generic Programming
Study the slides for lectures 5 and 6 for a good foundation discussion of generic programming concepts.
Polya, a famous mathematician, wrote "How to Solve It", which introduced generic techniques, applicable to solving any problem. Since the objective of the programming process is a solution to a problem or task, perhaps the concepts in Polya's book are applicable. The programming process as we have seen 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.
Templates and Template Libraries 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.
7.2: Templates in C++
Read this section for an introduction to the generic programming in several languages, including Java and C++. It covers the standard template library, containers, algorithms, templates, and mentions compile time polymorphism vs. runtime polymorphism.
Explore the lecture notes and assignments for this short course, which discuss C++ templates, the Standard Template Library (STL), and operator overloading.
7.3: Commonly-Used Classes
Read section 10.2. In an class hierarchy, a base class is more generic than a class that implements it. In particular, functions or methods of a base class are more generic functions. While generality is desirable, it may be a trade-off with efficiency for certain problems. This section looks at several classes in the class hierarchy for lists and for sets, and the additional features implemented in the subclasses that make them more efficient depending on the problem to be solved.
In this activity, you will construct a basic Java application that contains a TreeSet object. You will also add items to this Treeset.
This activity provides an exercise to enable you to create a basic java application containing a HashSet object.