Welcome to Programming and Data Structures

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

We start by assuming the value we are looking for is not present. This is done on line 10 where we set the location to the size of the array. If the size is 4, the only valid values are 0-3, so we know size() represents an impossible value. Then, we traverse the vector to check each element. If we find the target value in the vector, we change the location and break out of the loop. When the loop is done, if location still matches the size(), we know the value was not found.

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:

double minValue(const vector<double>& values) {
    // assume the first element is the minimum
    int minimum = values.at(0);
    // loop through the rest of the vector to see if any elements are smaller
    for (size_t i = 1; i < values.size(); ++i) {
        int value = values.at(i);
        if (value < minimum) {
            minimum = value; // found a new minimum
        }
    }
    return minimum;
}

A map operation transforms each element in a vector to a new value. In Section 13.7 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.

Finally, a filter operation traverses a vector and only keeps values that meet a certain condition. Although we could do this by removing unwanted values from the vector we start with, it is much easier to build up a vector with just the ones we want. This final sample demonstrates a function that filters out 0 values from a vector, producing a new one with only non-zero values: