Step 5 of 7

Iterators

You've been writing v.begin() and v.end() for a while. Those are iterators: generalized pointers that mark positions in a container. Every container provides them, and they all support the same basic moves:

• *it reads (or writes) the element,
• ++it moves to the next element,
• it == other / it != other compares positions.

begin() is the first element; end() is one past the last, a stop marker you never dereference.

A function for any container

A function written against an iterator pair works with vectors, arrays, deques, lists and even plain C arrays. To accept any iterator type, the function is a template: template <typename It> means "It is a type the compiler fills in from the arguments". Templates get their own module soon; this is all you need for now.

#include <array>
#include <iostream>
#include <list>
#include <string>
#include <vector>

template <typename It>
It find_first_longer(It first, It last, std::size_t n) {
    for (; first != last; ++first) {
        if (first->size() > n) return first;
    }
    return last;                   // "not found" is the end of the range
}

int main() {
    std::vector<std::string> v = {"hi", "hello", "hey"};
    std::list<std::string> l = {"a", "bb", "ccc"};

    auto it = find_first_longer(v.begin(), v.end(), 3);
    std::cout << *it << " at " << (it - v.begin()) << "\n";

    auto jt = find_first_longer(l.begin(), l.end(), 5);
    std::cout << (jt == l.end() ? "none in list" : *jt) << "\n";

    std::array<int, 4> a = {1, 2, 3, 4};
    for (auto r = a.rbegin(); r != a.rend(); ++r) std::cout << *r;
    std::cout << "\n";
}

hello at 1
none in list
4321

How it works

• The same function body runs on a vector and on a linked list, because it only uses !=, ++ and -> on the iterator.
• Returning last means "not found". That's the convention of every standard algorithm, so callers compare the result with end().
• rbegin() and rend() walk backwards. std::next(it, n) and std::distance(a, b) move and measure for any iterator type.

Your task: finding the maximum

Keep an iterator to the best element so far, starting at first. Walk the rest; when an element is strictly greater than the best, remember its iterator. Using > (not >=) is what makes it the first largest. Handle the empty range (first == last) by returning last straight away.

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