Containers and Iterators

This lecture covers a broad overview of containers as well as the fundamental approaches to implementing their underlying data structures.

Containers serve a variety of purposes. Here's a few containers from the C++ standard library as examples:

  • A std::vector<double> could store datapoints for statistical analysis
  • A std::set<string> could represent uniqnames of students registered for a course
  • A std::map<string, double> could allow us to look up the price of an item on a menu by providing its name

We'll also take a look at the way the standard library uses iterators as the abstraction for locating and traversing through elements.

Updated Spring 2025

1: Introduction to Standard Library Containers




2: Exceptions

We'll briefly cover a miscellaneous topic, exception handling. Some functions on containers (and other functions, generally) from the C++ standard library "throw" exceptions in cases of invalid input.

For example, consider hypothetical RMEs for the [] operator and .at() functions on a std::vector<T>:

// REQUIRES: The vector is not empty.
// EFFECTS: Returns (by reference) the element at the given index.
T & operator[](size_t index);

// EFFECTS: Returns (by reference) the element at the given index,
// unless the index is out of bounds, in which casea std::out_of_range
// exception is thrown.
T & at(size_t index);

The [] operator uses a REQUIRES clause to specify that the vector must not be empty, otherwise undefined behavior may occur. On the other hand, the .at() function uses an EFFECTS clause to specify that it will deterministically throw a std::out_of_range exception if the index is out of bounds.

So what does "throwing an exception" mean? First, an exception is an object that represents an error that has occurred. When the function throws the exception, it does not return in the normal way or yield a result, but instead begins an alternate control flow path to seek out appropriate error handling code.

Error handling code is specifed with a try/catch construct. The try block contains the code that may throw an exception, and the catch block contains the code that will handle the exception if it is thrown. The catch block also specifies the type of exception it can handle. If an exception is thrown, but not caught, the program terminates with an error message.

Here's an example:

#include <iostream>
#include <vector>
#include <stdexcept>
int main() {
  std::vector<int> vec = {1, 2, 3};
  try {
    int value = vec.at(3); // 3 is out of bounds
  }
  catch (const std::out_of_range &e) {
    cout << "Error - index was out of bounds." << endl;
  }
}

This also works across function calls, so if an exception were to be thrown in a helper function, it could be caught by the caller (or the caller's caller, and so on…).

In project 4, you'll use the csvstream library to read CSV (Comma Separated Values) input files, and you'll catch an exception thrown by the library if the input file cannot be opened. The project spec links to an example of how to do this.

We'll return to exceptions near the end of the course and discuss them in more detail.



3: Sequential Containers with Contiguous Allocation
3.1 Not Started

There are two fundamental approaches to data representation for containers. The first of these is to use a contiguous allocation (i.e. elements are stored in an underlying array). std::array and std::vector are sequential containers from the C++ standard library that use this approach.


3.1

Which of the following are true?



4: Sequential Containers with Linked Structures
4.1 Not Started 4.2 Not Started

The second fundamental approach to data representation for containers is to use a linked structure (i.e. elements are stored in nodes that point to each other). std::list and std::forward_list are sequential containers from the C++ standard library that use this approach.


4.1 Exercise: Time Complexity

Determine the time complexity of each of the following operations on the given data structure. Using a worst-case analysis, determine whether each function has O(1) constant time complexity or O(n) linear time complexity.

Updating the value of the first element in a std::array.

Inserting a new element at the front (left) of a std::vector.

Inserting a new element at the back (right) of a std::vector.

Printing the value of the first element in a std::list.

Inserting a new element at the front (left) of a std::list.

Printing the element in the middle of a std::list.

Assuming you already have a pointer to some node within a std::list, inserting a new element right after that position.


4.2 Exercise: Binary Search

Recall the binary search algorithm, where we find a desired value in a sorted array by:

  1. Finding the middle value current search range by indexing at the halfway point.
  2. Comparing the query value to the middle value.
  3. Repeating the process on the left or right half of the array, depending on the comparison result (or stop if we find the value).

Using binary search, a lookup operation in a sorted array can be implemented in worst-case logarithmic time, O(log n).

However, this isn't the case for a sorted linked list! Why not? Explain why binary search is not a good fit for a linked list.


Sample solution…

Binary search relies on efficient indexing to get the middle value in the array. In an array, this is possible via pointer arithmetic. But linked lists do not support efficient indexing! To take one step of the binary search algorithm, we'd need to traverse linearly through 50% of the list by following next pointers. This first step alone already puts us at linear time complexity (and rules out logarithmic time).



5: Iterators and Traversal by Iterator

The C++ standard library uses the concept of an iterator to indicate the position of an element in a list and to facilitate traversal through elements.


Note that traversal by iterator is analogous to traversal by pointer, which we've seen previously. (Although not all iterators are literally implemented as pointers.)



6: The auto Keyword




7: Range-based for Loops




8: Iterator Interfaces

Iterator types are also used to specify the parameter or return types for many functions from the standard library.




9: Sets and Maps
9.1 Not Started


9.1

Select the item below for participation credit.

You've reached the end of this lecture! Your work on any exercises will be saved if you re-open this page in the same web browser.

Participation Credit
Make sure to sign in to the page, complete each of the exercises, and double check the participation indicator at the top left of this page to ensure you've earned credit.