Using Iterators with Containers

The alias does not create a new kind of iterator. It is only a shorter name for an iterator type that already exists inside each container.

Programming

Why Iterator Type Names Get Long

An iterator is an object that lets you move through the elements of a container and access each one. Different containers provide different iterator types. A string, a list, and a vector each have their own iterator type, and writing those full type names over and over makes generic code hard to read. This article looks at a small tool for that problem: a type alias that gives a container's iterator type a shorter name, used inside a function template called find_all.

What do you think happens?

Given a list of doubles that holds 1.1 at two positions, how many iterators does find_all return when you search for 1.1, and what kind of values are they?

One iterator holding the value 1.1
Two iterators of type list<double>::iterator
Two copies of the value 1.1 in a vector of doubles

Reveal answer

Answer:

Two iterators of type list<double>::iterator

find_all returns a collection of iterators into the container, not a collection of matching values. Because the list contains 1.1 at two positions, two iterators come back, and their type is taken from the container.

What the Iterator Alias Names

Definition

Iterator<T> is an alias template defined as typename T::iterator, so it names the iterator type a container already declares.

Read the definition in two parts. The part typename T::iterator says: take the type T, look inside it for a nested type called iterator, and use that. The word Iterator on the left is only the name you write in your code. It is a shorter label for a type that the container has already declared. When you write Iterator<string>, you are naming string::iterator. When you write Iterator<list<double>>, you are naming list<double>::iterator. The same reading applies to any container that declares its own iterator type.

The keyword typename appears because T::iterator depends on the template parameter T. Since the compiler cannot know in advance what T is, the keyword tells it that the name refers to a type. Without that keyword, the compiler would not know whether iterator names a type or a value.

Key point

The alias does not create a new kind of iterator. It is only a shorter name for an iterator type that already exists inside each container.

Resolving Iterator<vector<int>> Step by Step

Resolution happens in a fixed order. First, the argument vector<int> replaces the template parameter T. Second, the compiler looks inside vector<int> for its nested member iterator. Third, the name Iterator<vector<int>> stands for that member type, which is written vector<int>::iterator. The strip below follows those three stages from left to right.

How writing Iterator<vector<int>> resolves into the concrete type that the vector declares

How Containers Own Their Iterator Types

The relationship has three parts. The container declares its iterator type as a member. The alias Iterator<T> does not declare anything of its own; it refers to that existing member. The iterator type that results is the one the container owns. The diagram below shows which piece contains which, and where the alias sits in that picture.

What contains what: the container declares its iterator type, and the alias only refers to that existing declaration

Tracing the find_all Function Template

find_all is a function template that takes a container and a value, and returns the positions of that value as iterators. The code below is a reconstruction of that function written from its described signature and loop. Read it once without worrying about every detail. Your goal is to notice which names are used as types and which are used as values, because that distinction drives everything that follows.

cpp

template<typename T>
using Iterator = typename T::iterator;

template<typename C, typename V>
vector<Iterator<C>> find_all(C& c, V v) {
    vector<Iterator<C>> res;
    for (Iterator<C> p = c.begin(); p != c.end(); ++p)
        if (*p == v)
            res.push_back(p);
    return res;
}

template<typename T>
using Iterator = typename T::iterator;

template<typename C, typename V>
vector<Iterator<C>> find_all(C& c, V v) {
    vector<Iterator<C>> res;
    for (Iterator<C> p = c.begin(); p != c.end(); ++p)
        if (*p == v)
            res.push_back(p);
    return res;
}

Notes on the code

Iterator<T> is the alias; it stands for T::iterator
C& c takes the container by reference
V v takes the value to search for
The return type is a vector whose elements are iterators into C

Code walkthrough

template<typename C, typename V> ... find_all(C& c, V v)

1
The alias template Iterator<T> is defined as typename T::iterator, so every use of Iterator<C> names the iterator type the container C declares.
2
The return type vector<Iterator<C>> says the function returns a vector of iterators into the container, not a vector of matching values.
3
The loop starts at c.begin(), so the first position it examines is the beginning of the container.
4
The loop moves forward with ++p and stops when p reaches c.end().
5
Each time the element that p points to equals v, the iterator p itself is stored in res.
6
The function returns res. Nothing is copied out of the container except iterators, so the caller can use each one to reach the matching element in the original container.

Worked example

Searching a list for a repeated value

A list<double> holds the values 1.1, 2.2, and 1.1, in that order. What does find_all(ld, 1.1) return?

1
Identify the container
The container C is list<double>, so Iterator<C> names list<double>::iterator.
2
Walk from begin to end
The loop visits position 0, position 1, and position 2 in turn, stopping when p reaches end.
3
Compare each element
Position 0 holds 1.1 and matches. Position 1 holds 2.2 and does not match. Position 2 holds 1.1 and matches.
4
Collect the iterators
The iterators for positions 0 and 2 are pushed into res, and nothing else is stored.

Result

The function returns a vector of two list<double>::iterator values, one pointing to position 0 and one pointing to position 2.

Which element positions the returned iterators point to, and how they map back to the container's contents

The diagram shows the central idea of the function. The result vector does not hold the numbers 1.1 and 1.1. It holds two handles that point back into the list. The caller can follow each handle to the element it refers to, and the element itself stays in the container.

Declarations With and Without the Alias

The alias matters most in the return type. Without it, the same signature must spell out the container's iterator member in full each time it is needed, and it must do so in both the return type and the loop variable. The pair below places the two versions side by side. The second version is a rewrite that follows directly from the definition Iterator<T> as T::iterator, so both versions produce the same type.

Before

template<typename C, typename V>
vector<typename C::iterator> find_all(C& c, V v) {
    vector<typename C::iterator> res;
    for (typename C::iterator p = c.begin(); p != c.end(); ++p)
        if (*p == v)
            res.push_back(p);
    return res;
}

Without the alias: the full member name typename C::iterator is repeated in the return type, the result vector, and the loop variable.

After

template<typename C, typename V>
vector<Iterator<C>> find_all(C& c, V v) {
    vector<Iterator<C>> res;
    for (Iterator<C> p = c.begin(); p != c.end(); ++p)
        if (*p == v)
            res.push_back(p);
    return res;
}

With the alias: Iterator<C> is written in three places and names the same type each time.

Aspect	Without alias	With Iterator<C> alias
Return type	vector<typename C::iterator>	vector<Iterator<C>>
Loop variable	typename C::iterator p	Iterator<C> p
Resulting type	C's declared iterator type	The same C's declared iterator type
Runtime behavior	Identical	Identical
Readability	Long and repetitive	Short and easy to scan

Both declarations name the same iterator type; only the spelling differs

A mismatch between what you expect and what you get can start in either version. If you write the loop variable with a type that is not the container's iterator type, the declaration no longer agrees with the container. In the alias version, the mismatch is easier to spot because the name Iterator<C> is tied directly to the container argument C. A declaration that names the wrong container, or that treats the iterator as a value, will be the first place to look.

Mistakes When Reading Iterator Results

Common mistake
Treating the returned vector as a list of matching values
What it looks like
Assuming find_all(ld, 1.1) returns a vector holding 1.1 twice.
Why it fails
find_all returns a vector of iterators into the container, not a vector of matching values.
Do this instead
Read each returned element as a position in the container, then use the iterator to reach the value it points to.
Common mistake
Comparing the iterator itself to the searched value
What it looks like
Writing if (p == v) inside the loop, where p is an iterator and v is a double.
Why it fails
The iterator p and the value v are different kinds of objects, so the comparison does not check the element.
Do this instead
Compare the element the iterator points to with v, using the dereferenced value of p.
Common mistake
Assuming the alias creates a different iterator type
What it looks like
Believing Iterator<string> and string::iterator are two distinct types that could disagree.
Why it fails
The alias is only a shorter name for T::iterator, so the two spellings name the same type.
Do this instead
When a result looks wrong, check the container's declared iterator type directly, since the alias refers to it.
Common mistake
Forgetting the typename keyword in a rewritten declaration
What it looks like
Writing C::iterator p inside a template without typename.
Why it fails
C::iterator depends on the template parameter, so the compiler needs typename to know it names a type.
Do this instead
Write typename C::iterator, or keep the alias Iterator<C> to avoid repeating the keyword.

Predicting Results for a New Container

EASY

A vector<string> holds "red" once and "blue" twice. Without running the code, predict the type and the number of iterators that find_all returns for the search value "blue". Then explain which part of the declaration determines the type.

Hints

Start from the container: the iterator type comes from vector<string>, so write it as vector<string>::iterator.
Count the positions where the element equals "blue", not the number of times you see the word in the code.
The alias Iterator<C> with C equal to vector<string> names the same type as vector<string>::iterator.

Your attempt (not saved)

MEDIUM

Rewrite the declaration Iterator<list<double>> in full without the alias, then explain why the rewritten name and the alias name refer to the same type.