Before You Start

Say we want to find the smallest item in an IntList…

#include <numeric_limits>

// Returns the minimum item in the list.
// Precondition: myList is not empty (i.e., users should not pass in an 
// empty list, and no specific result is required if myList is empty).

int findMin(const IntList& myList) {
    int min = numeric_limits<int>::max();
    // ^-- any actual minimum will be less than this value, as this is the
    //     largest possible int value, probably 2^31 - 1 = 2147483647.

    // find the minimum item in the list...

    return min;
}

Here's one possible implementation:

int findMin(const IntList& myList) {
    int min = numeric_limits<int>::max();
    // ^-- any actual minimum will be less than this value, as this is the
    //     largest possible int value, probably 2^31 - 1 = 2147483647.

    // find the minimum item in the list...
    for (IntList::const_iterator iter = myList.begin(); iter != myList.end(); ++iter) {
        if (*iter < min) {
            min = *iter;
        }
    }

    return min;
}

Some subtle issues to watch out for:

• Because myList is const, begin returns a const_iterator.
• If we initialize min with an arbitrary value, we might get the wrong value (i.e., if min's initial value is less than everything in the list).
• We initialized min with the largest possible int value, which is guaranteed to be greater than or equal to any actual value in the list.
• An alternative would have been to just read the first item in the list and use that as the initial value of min, but the two versions would differ in their behavior if the list were empty, although either is allowed by the precondition.

Some other ways to write the loop include:

    for (auto iter = myList.begin(); iter != myList.end(); ++iter) {
        if (*iter < min) {
            min = *iter;
        }
    }

to avoid needing to write out the type of the iterator, or:

    for (auto item : myList) {
        if (item < min) {
            min = item;
        }
    }

to avoid needing to write out the iterator at all (this code is still using iterators, but the compiler is writing the code for us behind the scenes).

But in the questions below, focus on the code that explicitly uses iterators.

Operation Counts and Complexity

(When logged in, completion status appears here.)