154. The C++ Standard Template Library

Rev. 1.2

 

The C++ Standard Template Library is a large part of the C++ Standard Library. STL consists of three major components: data structures, algorithms and iterators. Every data structure you are likely to want is available, including familiar containers such as array, list, deque, stack, queue, set and others. Also available are a plethora of algorithms, such as sort(), search(), merge(), find() and others. The third major component of STL, iterators, link the algorithms to the data structures. Iterators are a generalization of pointers, and are designed for efficient traversal through the data structures.

 

The course consists of two modules. The first module, Fundamentals of STL, begins with an overview of C++ templates. If your students are already familiar with templates, this chapter can be covered briefly as a review. Otherwise, it should be covered thoroughly, including the exercises at the end of the chapter. The second chapter gives an overview of STL, including its history and evolution. It also surveys the major features of STL. There is no lab for this chapter, which is intended to provide an orientation to the whole subject, not the details. Chapter 3 contains a large number of simple examples illustrating the main features of STL. It could be called “a tour of STL.” At this point students should already have a reasonable working knowledge of the subject. The rest of the course elaborates on the individual features. Chapter 4 covers STL containers, and Chapter 5 covers STL iterators.

 

The second module, Intermediate STL, covers the remaining features of STL. Chapter 1 introduces function objects, which are objects of any class that overloads the function call operator, operator(). Most STL algorithms accept a function object as a parameter, allowing the programmer to vary the way an algorithm works. Chapter 2 covers STL algorithms. The third chapter discusses container adaptors, which are STL components that can be used to change the interface of another component. They support the creation of STL classes such as stack and queue from lower-level components such as vector and list. The course concludes with an introduction to allocators, which are used by STL to encapsulates memory model information.

 

LEARNING OBJECTIVES

 

·         Use any of the data structures contained in STL

·         Use any of the algorithms contained in STL

·         Connect algorithms to containers using STL iterators

·         Demonstrate the principles of generic programming

·         Apply STL algorithms to the standard C and C++ data types

 

Course Duration:  3 days

 

Prerequisites:  Students should have a working knowledge of C++.

 

Module 1.  Fundamentals of STL

 

1.      An Overview of Templates

Templates

Overloading functions

Template functions

Specializing a template function

Disambiguation under specialization

Template classes

An array template class

Instantiating a template class object

Rules for templates

Non member function with a template argument

Friends of template classes

Templates with multiple type parameters

Non type parameters for template classes

Comments regarding templates

 

2.      Overview of the Standard Template Library

Perspective

History and evolution

New features in C++

The Standard Template Library

Design goals

Header files

STL components

Containers

Algorithms

Iterators

 

3.      Examples from STL

Example: vectors, lists

Example: maps

Example: sets

Example: multiset

Example: find with a vector

Example: find with a list

Example: merge

Iterators

Function objects

Adaptors

 

4.      STL Containers

Vector

Deque

List

The beauty of STL

Associative Containers

Set

Multiset

Map

Multimap

 

5.      STL Iterators

Input iterators

Output iterators

Forward iterators

Backward iterators

 

Module 2.  Intermediate STL

 

1.      Function Objects

Function objects vs. function pointers

Predicate function objects

Comparison function objects

Numeric function objects

Programmer supplied function objects

Built-in function objects

 

2.      STL Algorithms

Non-Mutating sequence algorithms

Mutating sequence algorithms

Sorting and searching algorithms

Numeric algorithms

General

 

3.      Container Adaptors

Wrapper classes

Stack container adaptors

Queue container adaptors

Priority_Queue container adaptors

 

4.      Allocators

Rationale

Default Allocator

Custom Allocators

Container Storage Allocation

 

System Requirements

 

The course is designed to be delivered in any environment supporting an ANSI C++ compiler.