Week 6 - Templates and Linear Array-Based Data Structures

Learning objectives

Upon finishing this week, you should be able to:

  • Create and use generic functions using templates
  • Create and use generic array-based data structures

Suggested pacing

Monday

Tuesday

Wednesday

Thursday

  • Std::Algorithms
  • Do Algorithms CPPLab - this one has an intentionally late due date. You have a few weeks to get it done.

Friday

  • Take Quiz 3 - it covers through vectors (no std algorithms)

Templates Intro

Read 12.1-12.3

Watch this video on working with templates

CPPLab Templated Functions

Templated Array-Based Container Classes

Read 12.4-12.5. Note we are going to come back to 12.6/12.7 later - but feel free to peek at them now. The ArrayList sample code I show in the video below is essentially a simplified version of vector.

Watch these videos on the book Stack class and the ArrayList class you can find in the Github repository. Building a similar container class is your project this week.

Vectors & Iterators

The idea of an "ArrayList" is an important one. Programmers often need a way to store a "list" of items in a structure that is easier to work with than a low-level array.

Rather than each programmer building their own version of an "ArrayList", there is a standard one provided with the C++ standard libraries. It is called a vector. Think of vector as the industrial grade version of the simple ArrayList we just looked at. Under the hood it uses most of the same tricks our basic ArrayList did.

Read 12.6-12.7 and watch this video for the basics of their use:

One of the tricky bits for vectors is how we specify locations within them. We often don't use numeric indexes, instead we use something called an iterator - a special object that keeps track of a location.

Read Liang Ch 22.3, you can skim once you get to 22.3.1 - don't worry about memorizing every detail. Also read 22.4. This video is an overview:

Do the Vector Basics CPP Lab.

std::algorithms

When a developer needs a standard algorithm like a sort, they generally reach for a library implementation of that algorithm. Once someone has built and tested a version of a sort algorithm, there isn't a need to reinvent the wheel.

In C++, there are a large collection of generic classes and algorithms known as the Standard Template Library (STL). As the name implies, these are templated constructs that can be used to work with any type of data. These constructs can be roughly divided into two categories of things: containers and algorithms.

The containers are things like vector - classes designed to hold data and handle the low level work of managing memory while allowing us to program using a higher level interface. In CS260 we will cover a number of other containers from the STL.

The algorithms are functions designed to do all kinds of jobs on data structures - find things, sort things, copy things, modify items, etc.... They are a powerful way to interact with data.

Read Ch 23.1-23.2. Use the rest of 23 as reference as you do CPPLabs. You should NOT try to memorize all the algorithms, just become familiar with what tools there are.

This video covers how the algorithms work:

And this one compares solving a problem with and without using the std::algorithms:

Do Algorithms CPPLab.

Optional Extra - Check out Boost::Units

Template-based programming is responsible for some of the coolest "tricks" possible in C++. Boost is an open-source library of C++ code - most of which involves templates. Boost::Units provides a way to use templates to check dimensional analysis at compile time. If you just store different units all as doubles, there is no way for the compiler to catch errors like myArea = length + width. Boost::units gives explicit templated types to those ideas. For more details, you can read the Boost::units quick start.