Step 5 of 7

Iterators

Iterators are the glue between containers and algorithms: generalized pointers with *it to read, ++it to advance, and == to compare. begin() points at the first element; end() points one past the last (never dereference it).

Writing a function against an iterator pair instead of a specific container makes it work with vectors, arrays, deques, lists and even plain C arrays:

template <typename It>
int count_negatives(It first, It last) {
    int n = 0;
    for (; first != last; ++first)
        if (*first < 0) n++;
    return n;
}

That's exactly how <algorithm> is written. rbegin()/rend() walk backwards, and std::next(it, n)/std::distance(a, b) move and measure.

Your turn: write template <typename It> It find_max(It first, It last) returning an iterator to the first largest element, or last if the range is empty. Don't use std::max_element.

Previous: priority_queue and top-k Next: Iterator invalidation