Containers and Iterators

Apologies – this section has not been written yet.

Range-Based For Loops

A range-based for loop is a special syntax for iterating over sequences that support traversal by iterator. Rather than writing out each piece of the traversal, we can have the compiler generate it for us:

vector<int> vec = { 1, 2, 3, 4, 5 };
for (int item : vec) {
  cout << item << endl;
}

The syntax of a range-based for loop is:

for (<type> <variable> : <sequence>)
  <body>

In the example above, the variable is named item and has type int, and vec is the sequence over which the loop iterates. The compiler automatically converts this into a traversal by iterator:

for (auto it = vec.begin(); it != vec.end(); ++it) {
  int item = *it;
  cout << item << endl;
}

The variable item is initialized in each iteration from an element in the sequence. Then the code in the body of the range-based for loop follows.

The following loop attempts to set every element in the vector to the value 42:

for (int item : vec) {
  item = 42;             // attempt to set element to 42
}

However, this loop does not actually modify any elements. To understand why, let us take a look at its translation into a traversal by iterator:

for (auto it = vec.begin(); it != vec.end(); ++it) {
  int item = *it;
  item = 42;
}

The loop is actually modifying a copy of each element rather than an element itself. To avoid making a copy, we can declare the loop variable to be a reference:

for (int &item : vec) {
  item = 42;             // actually set element to 42
}

This translates to:

for (auto it = vec.begin(); it != vec.end(); ++it) {
  int &item = *it;
  item = 42;
}

This successfully modifies each element to have the value 42.

Range-based for loops are often used in combination with auto, as in the following:

vector<int> vec = { 1, 2, 3, 4, 5 };

for (auto &item : vec) {
  item = 42;
}

for (auto item : vec) {
  cout << item << endl;
}

The first loop declares item as a reference, so that it aliases an element in the sequence. The second loop does not declare item as a reference, so it produces a copy of an element in the sequence. The following is the translation of both loops:

vector<int> vec = { 1, 2, 3, 4, 5 };

for (auto it = vec.begin(); it != vec.end(); ++it) {
  int &item = *it;                                     // alias
  item = 42;
}

for (auto it = vec.begin(); it != vec.end(); ++it) {
  int item = *it;                                      // copy
  item = 42;
}

With a range-based for loop, we can simplify print_all():

template <typename Sequence>
void print_all(const Sequence &sequence) {
  for (auto &item : sequence) {
    cout << item << endl;
  }
}

We can call it on any sequence [1] that supports traversal by iterator, as long as the element type can be inserted into an output stream:

vector<string> vec = { "hello", "world!" };
print_all(vec);

Iterating over a Map

The standard-library map defines an iterator that produces key-value pairs upon dereference. The following is an example that constructs a map, counting how many times each unique word occurs in a vector. It then iterates over the map to print out the counts.

void print_word_counts(const std::vector<std::string> &words) {
  std::map<std::string, int> word_counts;

  // Each time a word is seen, add 1 to its entry in the map
  for (const auto &word : words) {
    word_counts[word] += 1;
  }

  // Print out the results by iterating through the map.
  for (const auto &key_value : word_counts) {     // key-value pairs
    const auto &word = key_value.first;
    const auto &count = key_value.second;
    cout << word << "occurred " << count << " times." << endl;
  }
}

When incrementing a word’s count, we do not need to check whether the word is in the map; if not, the map automatically inserts the word into the map with a value-initialized count of zero, which we then increment to one.

We use range-based for loops to iterate over both the vector and the map, declaring a type-deduced reference to each element. A reference avoids making a copy, which is nontrivial for strings. The iteration over the map produces key-value pairs (std::pair<std::string, int>), and we access the first and second members to obtain the word and count, respectively.