Datarep Section 0: C++ containers

How this section works

We release section material via the CS 61 course site (where you’re reading this now) and the cs61-sections repository (obtain a local copy with a command like git clone git@github.com:cs61/cs61-sections).

This specific “section material,” though, will not be covered explicitly during allocated section time. Instead, this page covers important foundational information about C++ data structures. Please read this offline, at your own pace, before Section 1. The material should be familiar to you if you know C++.

Container data structures

C++’s standard containers library (ref1, ref2, ref3) offers several powerful container data structures, including:

Container data structures have similar APIs, and the algorithms library (ref1, ref2) offers generic algorithms that can operate on many containers.

C++ container APIs resemble APIs in other languages, but do have some unique features, especially in the way they use iterators (ref) to represent positions in a data structure.

You will definitely use C++ containers in Problem Set 1 and many later problem sets.

std::map (ordered search tree)

We’ll first discuss std::map, since this is used in Section 1.

std::map<K, V> is a search data structure that maps keys of type K to values of type V. V can be almost any C++ type; K can be any C++ type that supports comparison with the less-than operator <. (Integers, pointers, and C++ std::strings all support <, as do many other types.) For example, std::map<std::string, int> could be used to track the number of times different words appear in a text.

std::map stores its arguments in ascending order by key: if you use std::map functions to visit a map’s contents, the returned elements have increasing keys.

This code creates an empty map, inserts a few elements, checks that they exist, and then uses C++ iterators to visit every element of the map and print it.

std::map<std::string, int> m;

// `insert` takes a key-value pair as argument
m.insert({ "Hello", 0 });
m.insert({ "world", 1 });
m.insert({ "!", 2 });

// if an element exists, bracket notation can find it
assert(m["Hello"] == 0);
assert(m["world"] == 1);
assert(m["!"] == 2);

// visit all elements in map
for (auto it = m.begin(); it != m.end(); ++it) {
    fprintf(stderr, "key %s, value %d\n", it->first.c_str(), it->second);
}

Iterators, such as the it object above, represent positions within, or cursors into, a container data structure like a map. A map iterator “points at” a key-value pair, where the key is in it->first and the value in it->second. (Iterators are actually objects, not primitive pointers, but they support pointer notation anyway.)

Several map functions return iterators. The m.begin() iterator points at the first key-value pair in the map. The special m.end() iterator represents the absence of an item. Its position is “one past” of all the valid positions in the map; it’s illegal to refer to m.end()->first or m.end()->second. There’s also m.find(K), which returns an iterator pointing at the element with a given key (or m.end() if the key is missing), and m.lower_bound(K) and a.upper_bound(K), which return iterators pointing at elements nearest a given key.

The for loop above—for (auto it = m.begin(); it != m.end(); ++it)—is a natural and idiomatic way to visit all the elements of a C++ container. (The expression ++it means it = it + 1.)

map methods

Here are some important methods for std::map.

map.insert({key, value})
Insert a key-value pair into the map. (In this context, the {key, value} syntax creates a std::pair.) Does nothing if key is already present in the map. Returns a pair std::pair<iterator, bool>, where the iterator component is an iterator pointing at the entry for key, and the bool is true iff the element was inserted. You can unpack the result of map.insert with syntax like this: 
auto [iterator, inserted] = map.insert({key, value});
map[key] = value
map.insert_or_update({key, value})
Set key to value in the map. Unlike map.insert({key, value}), these operations always install the new value.
map.count(key)
Return the number of map elements with key key. For std::map, this is always 0 or 1.
map.begin()
Return an iterator to the first map element ordered by key. Returns map.end() if the map is empty.
map.end()
Return the end iterator for the map. It is illegal to dereference map.end().
map.find(key)
Return an iterator pointing at the map element with key key, or map.end() if there is no such element.
map.erase(key)
Remove the element with key key, if there is one. Returns the number of elements removed, which is 0 or 1.
map.erase(iterator)
Remove the element pointed to by iterator. Returns a new iterator to the next element in the map.

This code demonstrates a bunch of std::map methods. Read it to internalize how maps work. The code is in your section repository in the cs61-sections/s00-cpp directory. You can build and run it with cd cs61-sections/s00-cpp; make map1; ./map1.

s00-cpp/map1.cc
#include <map>
#include <string>
#include <cstdio>
#include <cassert>

int main() {
    // Map strings to integers
    std::map<std::string, int> m;

    // Insert without overwriting (leaves map unchanged if key present)
    m.insert({"one", 1});

    // Number of keys in map
    assert(m.size() == 1);
    assert(!m.empty());
    printf("m.size = %zu\n", m.size());

    // Test if key is in map
    size_t exists = m.count("one");
    assert(exists == 1);

    exists = m.count("two");
    assert(exists == 0);

    // Find matching element; returns `m.end()` if not found
    auto it0 = m.find("one");
    assert(it0 != m.end());
    // Iterator points to a key-value pair: `first` is the key, `second` the value
    assert(it0->first == "one");
    assert(it0->second == 1);
    printf("m.find(\"one\") -> %d\n", it0->second);

    auto it1 = m.find("two");
    assert(it1 == m.end());

    // Array syntax inserts or modifies
    m["one"] = 61;               // Insert into map (with overwrite semantics)
    assert(m["one"] == 61);
    // But beware; array syntax inserts a default if not found!
    int two_value = m["two"];
    assert(two_value == 0);
    assert(m.size() == 2);
    assert(m.find("two") != m.end());

    // Remove key
    m.erase("two");
    assert(m.size() == 1);

    // Iterate in sorted order
    m.insert({"two", 2});
    m.insert({"three", 3});
    m.insert({"four", 4});
    m.insert({"five", 5});
    for (auto it = m.begin(); it != m.end(); ++it) {
        // `it->first` is the key, `it->second` the value
        // (`it->first.c_str()` transforms a C++ string to printf form)
        printf("Found %s -> %d\n", it->first.c_str(), it->second);
    }

    printf("Done!\n");
}

Go to the cs61-sections/s00-cpp directory, run make, and then run ./map1 to check that the assertions all succeed.

Exercise. Fill in the ?s. Check your answers by modifying mapq.cc and running make mapq && ./mapq.

s00-cpp/mapq.cc
std::map<int, int> m;

m.insert({1, 2});
assert(m[1] == ?);
assert(m.count(1) == ?);
assert(m.count(2) == ?);
assert(m.size() == ?);

int x = m[2];
assert(x == ?);
assert(m.size() == ?);

m.insert({1, 3});
assert(m[1] == ?);

m.erase(1);
assert(m.size() == ?);

m.insert({1, 3});
assert(m[1] == ?);

Optional Advanced Exercise. Use print_bytes to print out the representation for a (non-empty) map object. Also print out the representations of a map iterator (it) and element (*it), for all positions in the map; and print out the representation of m.end(). What conclusions can you draw? How is a map represented in memory? (Maps are complicated, so don’t knock yourself out—just try to make some observations.)

Learn more:

Reference: Common methods on containers

Many C++ container types have methods with similar names. Here’s what they do.

container constructor
A “constructor” in C++ is a function that initializes an object. (This terminology is common to other object-oriented languages, such as Java.) Containers typically support several constructors that take different parameters. The empty constructor, which is called for a declaration like std::map<K, V> m or std::map<K, V> a{} with no arguments, leaves the container empty. An “initializer list,” such as std::map<K, V> a = {x, y, z} or std::vector<T> a{x, y, z}, fills the container with the given elements.
container.size()
Return the number of elements in the container. The return type is usually size_t.
container.empty()
Return true iff the container is empty (has size() == 0).
container.clear()
Remove all elements from the container, leaving it empty().
container[index]
Return a modifiable reference to the element of the container at position index. “Modifiable reference” means the element value can be either read (as in e = v[i]) or written (as in v[i] = e). This method is only supported on containers where access by index is efficient, such as vectors, maps, and hash tables (but not linked lists).
container.back()
Return the last element in the container. This method is only supported on containers that represent a sequence, such as vectors and linked lists (but not maps and hash tables).
container.push_back(value)
Add a new element to the end of the container, containing a copy of value.
container.pop_back()
Remove the last element in the container.
container.begin()
Return an iterator pointing to the first element in the container.
container.end()
Return an iterator pointing “one past the end” of the container. (This is analogous to array sizes: the size of an array is “one past” the last valid index.) container.end() must never be dereferenced. If a container is empty, container.begin() == container.end().

And here are some common methods on iterators.

++iterator
Move the iterator to point at the next element of the container. You must not call ++it when it == container.end().
--iterator
Move the iterator to point at the previous element of the container. You must not call --it when it == container.begin().
std::next(iterator)
Return the next iterator into the container. Like auto next = iterator; ++next; return next.
std::prev(iterator)
Return the next iterator into the container. Like auto prev = iterator; --next; return prev.
iterator == iterator2, iterator != iterator2
Compare iterators for equality (or inequality).
iterator + N, iterator - N
Return an iterator that ponts N elements ahead or behind iterator. These methods are only available if they can be implemented very efficiently (which, in practice, means only for std::vector).

END OF MANDATORY WORK FOR SECTION 1

Everything below this point is optional—you don’t need to complete it before Section 1. It will be useful for the class in general, though.

std::vector (resizable array)

std::vector<T> represents an array of objects of type T that can dynamically change size. Access into std::vector is as fast as access into a normal array, even though elements can be added and removed at runtime.

Here are some examples of basic std::vector methods.

s00-cpp/vector1.cc
#include <vector>     // include declaration of `std::vector`
#include <cstdio>
#include <cassert>

int main() {
    // Create a vector containing specific elements
    std::vector<int> a = { 1, 2, 3, 4 };

    // Create a vector containing 12 copies of the `long` value `61`
    std::vector<long> a2(12, 61);

    int e2 = a[2];         // get element
    assert(e2 == 3);

    a[2] = 4;              // set element
    assert(a[2] == 4);

    auto sz = a.size();    // return the number of elements
    assert(sz == 4);

    a.push_back(5);        // add element to the end
    assert(a.size() == 5);
    assert(a[4] == 5);

    auto back = a.back();  // return last element (requires `a` is not empty)
    assert(back == 5);

    a.pop_back();          // remove last element (but do not return it)
    assert(a.size() == 4);

    bool e = a.empty();    // return true iff `size() == 0`
    assert(!e);

    // Print vector contents
    printf("a: [");
    for (size_t i = 0; i != a.size(); ++i) {
        printf("%s%d", i ? ", " : "", a[i]);
    }
    printf("]\n");

    a.clear();             // erase all elements
    assert(a.empty());

    printf("Done!\n");
}

Go to the cs61-sections/s00-cpp directory, run make, and then run ./vector1 to check that the assertions all succeed.

Exercise. Write code that creates an empty vector of longs called a.

Exercise. Write code that creates a vector containing 5 copies of the C string "HI". Try to do this at least three different ways. Use the compiler to check for syntax errors—for instance, put your code in vector2.cc and run make vector2.

Learn more:

Optional Exercise. Complete this function:

/** Return an iterator that points at the first occurrence of `value` in `a`.
 * For example, if `a` holds values [1, 2, 3], then `find_first(a, 1)`
 * should return `a.begin()`. */
std::vector<int>::iterator find_first(std::vector<int>& a, int value) {
    ...
}

You should decide what to return if value is not present in a!

Iterator computations (reference)

Since std::vector’s underlying array representation allows efficient access at any index, vector iterators can efficiently be moved around by arbitrary distances. Such iterators are called random-access iterators.

To move a random-access iterator, you use syntax that looks like arithmetic.

iterator + count
Return an iterator that points count positions forward relative to iterator. For example, if it points at the 7th element of a vector, then it + 5 points at the 12th.
iterator - count
Return an iterator that points count positions backward relative to iterator.
it += count
Move it forward count positions.
it -= count
Move it backward count positions.
it1 - it2
(it1 and it2 must point into the same vector.) Return the number of positions from it2 to it1. For instance, (it + 5) - it == 5, and v.end() - v.begin() == v.size().

Modifying vectors

The following methods can be used to modify vectors. Many of them also apply to other containers.

container.insert(iterator, value)
Inserts a copy of value into the container immediately before iterator, shifting *iterator and all later elements up. container.insert(container.end(), value) does the same thing as container.push_back(value). Returns an iterator pointing at the newly inserted element.
container.insert(iterator, {value1, value2, value3, ...})
Adds the values to the container before iterator.
container.erase(iterator)
Removes the element pointed to by iterator, shifting all later elements down. Returns an iterator pointing at the first non-removed element, or end() if there is no such element; the input iterator becomes invalid.
container.erase(first, last)
(first and last are iterators into the container.) Removes the elements from first up to, but not including, last, shifting all later elements down. container.erase(container.begin(), container.end()) does the same thing as container.clear().
vector.resize(size)
Resize the vector to contain size elements. If size is bigger than the current size, adds new elements as required. vector.resize(0) does the same thing as vector.clear().

Growing a vector can force reallocation of the underlying storage for elements. When this happens, all previously-existing iterators into the vector are invalidated (they point into garbage memory and dereferencing them is illegal). This is why it‘s often important to use the return value from vector.insert() or vector.erase().

Question. Fill in the ?s. Check your answers by modifying vectorq.cc and running make vectorq && ./vectorq.

s00-cpp/vectorq.cc
std::vector<int> v = { 1, 2, 3, 4, 5 };

assert(v.size() == ?);
assert(v[3] == ?);

v.push_back(6);

assert(v.size() == ?);
assert(v.back() == ?);

v.erase(v.begin(), v.begin() + 1);

assert(v.size() == ?);
assert(v.back() == ?);
assert(v[0] == ?);

v.insert(v.begin() + 1, 10);
assert(v.size() == ?);
assert(v[0] == ?);
assert(v[1] == ?);

Exercise. Complete this function:

/** Insert `value` into `a`, preserving the sort order. For example,
 * if `a` holds [1, 3, 4], then after `insert_sorted(a, 2)`, `a` should
 * hold [1, 2, 3, 4]. `a` must be sorted on input. */
void insert_sorted(std::vector<int>& a, int value) {
    ...
}

Exercise. Write a set of tests for your insert_sorted function. Here’s an example test to get you started:

void test_insert_sorted() {
    std::vector<int> a{};
    insert_sorted(a, 1);

    std::vector<int> expected = {1};
    assert(a == expected);   // vectors have the same elements in the same order
}

When writing tests, think about situations that might be difficult to get right (edge cases). What are some edge cases for insert_sorted? Another great way to write tests is to generate tests randomly! Computers are very fast, and can run a ton of tests in very little time. This process is sometimes called fuzzing.

Exercise. Complete this function, which should remove any elements of v that are even.

void remove_even_elements(std::vector<int> &v) {
    ...
}

Warning: This is tricky because the vector’s erase operation invalidates iterators!

Advanced Home Exercise. Write a version of insert_sorted that is efficient on large vectors. For example, you might use binary search to find the insertion position.

Vector representation

Exercise. A vector can change size as the program runs. In which segment do you think the elements of the vector are most likely to be stored?

Exercise. Use hexdump_object to print out the representation for a (non-empty) vector object. Also print out the representations of a vector iterator (it) and a vector element (*it or v[idx]), for all positions in the vector; and print out the representation of v.end(). What conclusions can you draw? How is a vector represented in memory?

Correspondences with other programming languages

C++ Python Javascript Java PHP
std::vector<T> list Array ArrayList<T> array
v.size() len(l) a.length al.size() count($a)
v.empty() not l a.length === 0 al.isEmpty() empty($a)
v.clear() l.clear() a.length = 0 al.clear() $a = []
v[idx] l[idx] a[idx] al.get(idx) $a[$idx]
v.back() l[-1] a[a.length - 1] al.get(al.size() - 1) $a[count($a) - 1]
v.push_back(e) l.append(e) a.push(e) al.add(e) array_push($a, $e) or $a[] = $e
v.pop_back() l.pop() a.pop() al.remove(al.size() - 1) array_pop($a)
v.insert(it, value) l.insert(idx, value) a.splice(idx, 0, value) al.add(idx, value) array_splice($a, $idx, 0, $value)
v.erase(it1, it2) del l[idx1:idx2] a.splice(idx1, idx2 - idx1) al.removeRange(idx1, idx2) array_splice($a, $idx1, $idx2 - $idx1)

std::list (doubly-linked list)

The std::list type is another sequence structure that implements a doubly-linked list. Its methods resemble std::vector’s, but because indexing into a linked list at a specific position is not efficient, it does not support the index notation l[idx]—you have to use iterators to find a list element.

Reference material (comprehensive but scary): cplusplus.com, cppreference.com

std::unordered_map (hash table)

The std::unordered_map<K, V> data structure, like std::map<K, V>, maps keys to values. However, it’s a hash table, not an ordered map, so it can be faster when order is not required. (That is, lookup can be take O(1) time in the number of elements, rather than O(log N) time like std::map.) std::unordered_map has the same methods as std::map, but instead of just requiring comparison on K, it also requires a hash function. If you see a horrible error like

error: static_assert failed "the specified hash does not meet the Hash requirements"

or (EUUUUUGGGGGHHHHHHHHH—this kind of error is one of the very worst aspects of C++)

In file included from /opt/homebrew/Cellar/gcc/15.1.0/include/c++/15/bits/unordered_map.h:33,
                 from /opt/homebrew/Cellar/gcc/15.1.0/include/c++/15/unordered_map:43,
                 from uomap1.cc:1:
/opt/homebrew/Cellar/gcc/15.1.0/include/c++/15/bits/hashtable.h: In instantiation of 'class std::_Hashtable<foo, std::pair<const foo, int>, std::allocator<std::pair<const foo, int> >, std::__detail::_Select1st, std::equal_to<foo>, std::hash<foo>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >':
/opt/homebrew/Cellar/gcc/15.1.0/include/c++/15/bits/unordered_map.h:115:18:   required from 'class std::unordered_map<foo, int>'
  115 |       _Hashtable _M_h;
      |                  ^~~~
uomap1.cc:8:34:   required from here
    8 |     std::unordered_map<foo, int> f;
      |                                  ^
/opt/homebrew/Cellar/gcc/15.1.0/include/c++/15/bits/hashtable.h:210:51: error: static assertion failed: hash function must be copy constructible
  210 |       static_assert(is_copy_constructible<_Hash>::value,
      |                                                   ^~~~~
/opt/homebrew/Cellar/gcc/15.1.0/include/c++/15/bits/hashtable.h:210:51: note: 'std::integral_constant<bool, false>::value' evaluates to false
uomap1.cc: In function 'int main()':
uomap1.cc:8:34: error: use of deleted function 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = foo; _Tp = int; _Hash = std::hash<foo>; _Pred = std::equal_to<foo>; _Alloc = std::allocator<std::pair<const foo, int> >]'
    8 |     std::unordered_map<foo, int> f;
      |                                  ^
...
HUNDREDS
MORE
LINES
OF
ERROR
(ALWAYS LOOK AT THE FIRST ERROR FIRST)!
...

that means that the key type has no hash function yet. You can use a std::map (which doesn’t require a hash function, but features slower lookup), or write your own hash function, using syntax like this:

namespace std {
     template <> struct hash<MY_TYPE> {
         size_t operator()(const MY_TYPE& x) const {
             return ... whatever ...;
         }
     };
}

Here is a pretty good hash function for pairs (based on the one in Boost). Do not ask your TF about it during section but feel free to ask us offline :)

namespace std {
    template <typename T, typename U> struct hash<pair<T, U>> {
        size_t operator()(const pair<T, U>& x) const {
            size_t h1 = std::hash<T>{}(x.first);
            size_t h2 = std::hash<U>{}(x.second);
            size_t k = 0xC6A4A7935BD1E995UL;
            h2 = ((h2 * k) >> 47) * k;
            return (h1 ^ h2) * k;
        }
    };
}

And here is a garbage hash function. You could use it as a placeholder if you like making your computer work hard.

namespace std {
     template <> struct hash<MY_TYPE> {
         size_t operator()(const MY_TYPE& x) const {
             return 0;
         }
     };
}

Exercise. The s00-cpp/uomap1.cc file is exactly like map1.cc, but uses std::unordered_map rather than std::map. Run ./uomap1; how does its output differ from ./map1, and why?

std::set, std::unordered_set

The std::set<T> and std::unordered_set<T> types represent sets of T objects. They are implemented like std::map and std::unordered_map, but since they don’t store values, their iterator types point to T objects rather than pairs and they do not support map[key] bracket notation.

Exercise. Look at s00-cpp/uoset1.cc and compare it to s00-cpp/uomap1.cc. How is it similar and how is it different?

Standard algorithms

The <algorithm> header defines useful algorithms that work on all kinds of C++ data structures, and even on C-style arrays. Here are some of the best. (The names first and last denote two iterators into the same container; they delimit a range of elements starting at first, and going up to, but not including, last. Most often you will pass container.begin() and container.end() for these arguments.)

std::sort(first, last)
Sort the elements of the range. Element objects must be comparable using <.
std::sort(first, last, compare)
Sort the elements of the range according to a compare function. compare(e1, e2) should return true iff e1 sorts below e2.
std::find(first, last, value)
Return an iterator to the first element of the range that equals value, or last if no element is found.
std::find_if(first, last, predicate)
Return an iterator to the first element of the range for which predicate(*it) returns true, or last if no element is found.
std::lower_bound(first, last, value)
(The range between first and last must be sorted.) Return an iterator to the first position in the range that is greater than or equal to value, or last if all the elements of the range are less than value. Uses binary search, so it’s efficient if used on a vector or array.

Functions like std::find_if are often given lambda functions as arguments. Lambda functions bring functional programming techniques to C++. Some programming languages have nice syntax for lambda functions; here is a Javascript function that returns true iff its argument is even:

(x) => x % 2 === 0

C++’s syntax is weirder.

[&] (int x) { return x % 2 == 0; }

Here’s a use of that syntax to sort an array of ints by their distance from int center, so that elements e appear in increasing order by \left| e - \texttt{center} \right|.

void sort_by_distance_from_center(std::vector<int>& a, int center) {
    std::sort(a.begin(), a.end(), [&] (int x, int y) {
        return abs(x - center) < abs(y - center);
    });
}