Iterators and Container Traversal

Imagine you have written a routine that scans a container and collects the positions where a given value occurs. Once it works for a string of characters, the natural next step is to want the same routine for a list of doubles, a vector of strings, or any other sequence you might store. Rewriting the routine for every container type would duplicate the same loop again and again. This article follows one generic routine, find_all(), and shows how a single template can serve all of these containers, and what the template must say about the types involved in order to compile correctly.

The routine find_all() takes a container and a value, walks through the container with an iterator, and returns a vector of the iterators that point at each matching element. Returning iterators rather than copies of the values is a deliberate design choice. The caller receives a handle to each match, so it can inspect or change the element in place.

Two template parameters do the work. C stands for whatever container type the caller passes in, and V stands for the type of the value being searched for. Because C is a parameter, the function accepts a string, a list, or a vector without any change to its body. The return type is a vector of iterators into that container, so the caller always receives positions expressed in the container's own iterator type.

The code above is an illustrative sketch that follows the description in the source: one signature, a scan from begin() to end(), a comparison of each element with the search value, and a vector of matching iterators as the result. Notice that the body never mentions string, list, or vector. That is the point of the template.

The source tests the generic version on three containers: a string, a list of doubles, and a vector of strings. Each call uses the same template text, but the compiler produces a separate concrete version of find_all for each container type that is used. Each version has its own element type and its own iterator type, while the order of the steps stays the same.

This is why the loop variable p in the test has a different concrete type in each call, even though the source text of the loop is the same in all three cases. The instantiation is decided by the container type the caller passes, and the caller never has to write three versions of the routine.

Because find_all() returns iterators rather than copies, a caller can write through them. The source extends the test with a loop over the results of find_all(vs, "green") that assigns a new string through each iterator. The matching elements of vs change in place, and the loop variable is only a handle to them. The diagram below uses a small container of our own, holding red, green, blue, and green, to show how each returned iterator maps to a specific position.

The contents of vs in the diagram are our own illustration; the source describes the mechanism, not these particular values. The key idea is that each returned iterator is tied to a position in the container. If a result contains the wrong positions, the iterator is not the place to look first, because iterators faithfully record where the routine found each match. The error comes from the routine itself, specifically from the comparison that decides a match or the range that decides which elements are scanned.

A dependent name is a name whose meaning depends on a template parameter. In C::iterator, the name iterator lives inside C, and C is only known when the template is used. Many learners assume the compiler will look at the name, notice that C is a template parameter, and work out on its own whether C::iterator is a type or some value. It is a reasonable guess, because in ordinary code a name usually has one obvious meaning. In a template, however, the compiler is not allowed to rely on guessing for it.

The correction is that the programmer has to say it. The typename keyword is that marker. It tells the compiler that a dependent name refers to a type. Writing typename C::iterator is therefore a claim about meaning rather than decoration: it says the member named iterator inside C is a type to be used in a declaration. Without the marker, a declaration like the one below is not something the compiler can be trusted to read the way the author intended.

Repeating typename C::iterator in every signature and body is noisy, and it exposes an implementation detail that callers do not need to think about. The source introduces a type alias template, Iterator<T>, to hide it. A type alias gives a shorter name to a type expression. Here the alias takes a container type T and produces that container's iterator type, and the generic function uses the alias in place of the long form.

The alias splits what each side needs to know. The caller passes a container and reads the result as a vector of iterators; the caller does not need to see the member name inside the container. The implementer writes the body and uses Iterator<C> wherever an iterator type is needed. The practical payoff is maintainability: if the way you obtain an iterator ever has to change, the change happens in the alias rather than in every function that uses it.