CS 70

Before You Start

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

Fill in the body of the function using an iterator to find the minimum item in the list.

#include <limits>

// Returns the minimum item in the list.
// - Precondition: myList is not empty
//    (i.e., users must not call this function with an empty list,
//    and we don't need to handle that case here)

int findMin(const IntList& myList) {
    int min = myList.front();

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

    return min;
}

Here's one possible implementation:

int findMin(const IntList& myList) {
    int min = myList.front();

    // 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;
}
  • Cat speaking

    That's what I came up with. But a part of me doesn't like the fact that if I call the function with an empty list, it will call myList.front(), which leads to undefined behavior. Is there a better way to do it?

  • LHS Cow speaking

    Well, we did say in the precondition that the list must not be empty, so the function is allowed to assume that. And we could always add an assert(!myList.empty()); at the start of the function to catch that case and crash out nicely if someone does call it with an empty list. But there is another option…

There is an alternative way to initialize min that avoids needing to call myList.front()—we can initialize it to the largest possible int value, which we can get using std::numeric_limits<int>::max(). That way, any actual item in the list will be less than that initial value of min, so the first item we look at will always replace min.

Here's a version that does that and also uses auto for the iterator type:

int findMin(const IntList& myList) {
    int min = std::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 (auto 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.
  • We can't leave min uninitialized at the start, as who knows what random junk value it would have, so we need to initialize it to something.

You can also use a range-based for loop, like

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

to avoid needing to write out the iterator at all (this code still uses 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

For our implementation using iterators and std::numeric_limits, give an exact expression for the best-case number of times we access an item in a list of size \( n \).

Give an exact expression for the worst-case number of times we access an item in a list of size \( n \).

Which of the following is the most accurate and precise characterization of the complexity of our findMin() implementation?

(When logged in, completion status appears here.)