Welcome to Programming and Data Structures

Our first common pattern is a search, which involves traversing an vector while “searching” for a particular element.

Our strategy will be to assume the value is not present. We will do that by setting a variable location to be the size of the vector. That location can’t possibly be valid as there never is an index size() in a vector. Then we will use a loop to look for the item. If we find it, we will change the location. After that is done, we can check the location to see if it is still the invalid value.

Another common traversal is a reduce operation, which “reduces” an vector of values down to a single value. Examples include the sum or product of the elements, the minimum, and the maximum. The following function takes an vector and returns the sum of its elements. A reduction always needs an accumulator variable where we store the answer. As we visit each element, we update that variable as appropriate.

We have already seen one reduction recipe - calculating the sum of the values in a vector. In this recipe, our accumulator is the total and starts with a value of 0:

double sum(const vector<double>& values) {
    double total = 0.0;
    for (double value : values) {
        total += value;
    }
    return total;
}

Finding the smallest value in a vector can also be thought of as a reduction. In this case, our accumulator needs to keep track of the “smallest value we have seen so far” (called minimum in the sample below). As we visit each element, we compare it to minimum, and if it is lower, we need to change minimum to store the new lowest value that we have just discovered. But for this to work, we can’t start with 0 in our accumulator. If we did, we could go through the entire vector and never find anything smaller, and thus end up thinking that 0 was the minimum value. For situations like this it is common to use the first value to initialize the accumulator and then loop through all the elements after the first:

This function does assume that the vector is not empty. If it is, values.at(0) will cause an error. If we wanted to handle that case, we could add a check at the beginning of the function to see if the vector is empty. But there would not be any logical value to return, so we would likely need to just throw an exception ourselves.

A map operation transforms each element in a vector to a new value. In Section 13.9 we saw two versions of the doubleValues function that performed a map operation. The first version created a new vector and returned it. The second version modified the original vector in place.

Here again is the version that creates a new vector where each value is doubled:

Finally, a filter operation traverses a vector and only keeps values that meet a certain condition. As with a map, there are two ways we could do this. One approach is to modify the vector that is passed in to remove unwanted items. The other approach is to build a new vector with just the ones we want.

The advantages of each approach remain the same. Modifying the original vector can be more memory efficient since it doesn’t require additional storage, but building a new vector can be simpler and less likely to introduce errors. In addition, it is often faster to build a new vector than to remove multiple items from an existing one. (Something we will learn more about later on.)

This sample uses the approach of building a new vector. It takes a vector and produces a copy with 0 values filtered out: