Week 10 - Algorithms & The Standard Template Library (STL)

Learning objectives

Upon finishing this week, you should be able to:

  • Write MergeSort
  • Use std::algorithms
Quiz 4 is open this Thurs-Sunday. It covers weeks 8-10
The final is next week is an in-person, pen and paper exam during the scheduled final time.

Suggested pacing

Day 1

  • Std::Algorithms
  • Do Algorithms CPPLab

Day 2

  • Regular Expressions

Day 3

  • Final review
  • Review guide in Files area of Elearn under Week 10

Day 4

  • Review for and take Quiz 4

Final Notes

Here are the big ideas you should feel confident writing code on/answering questions about:

  • Pointers & Shared memory
  • Container classes - especially memory management (copy ctor, destructor and assignment operator)
  • Templated functions/classes
  • Recursion
  • Searching & Sorting

These topics are important and may appear, but were covered on the midterm and thus will not be as big an emphasis on the final.

  • Objects & Composition
  • Inheritance, Polymorphism & Virtual Functions

Activity Outline

STL 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.

Regular Expressions

Regular expressions don't really relate to anything else from this week, but they are an invaluable tool for searching and modifying strings - they are the go to tool of programmers who need to search and extract information from big text files.

To learn about regular expressions, check out the video below and then do the activities in the Regular Expression worksheet (see Files in elearn)

You do not have to write any C++ code to work with regexes. But, if you are interested, there is a project provided in the cs162Code repository (check the Extras folder) that you can check out to see regexes in action.

Regex Tools and References

Quiz & Final Review

The last quiz includes material from weeks 8, 9, and 10.

There is a review guide for the final in the Files area of week 10.