Write Functions Which Take Iterators, Not Collections
C++ c++ stl
Published: 2005-09-05
Write Functions Which Take Iterators, Not Collections

If my experience is typical, this is a very common construct:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
ReturnType Function
    (
    const std::vector<T>& container
    )
{
    typedef std::vector<T>::const_iterator iterator_t;
    for (iterator_t iter = container.begin();
         iter != container.end();
         ++iter)
    {
        // Work with *iter
    }
}

The problem with this construct is that you have forced a container choice upon the user of your function. Slightly better, and basically your only choice when interoping with C, is this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
ReturnType Function
    (
    T* array,
    int numItems
    )
{
    for (int i = 0; i < numItems; ++i) {
        // Work with array[numItems]
    }

    // Or perhaps:
    // for (T* pT = array; pT != array + numItems; ++pT) {
    //     Work with *pT
    // }
}

With the above construct you can pass in any container which uses contiguous storage, such as an array or a std::vector (yes, std::vectors are guaranteed to store the data contiguously). Passing a std::vector to the above function looks like:

1
2
std::vector<T> v;
ReturnType ret = Function(v.empty() ? 0 : &v[0], v.size());

However, in C++ its far better to do as the STL does and write your function to accept iterators, as in:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
template <class InputIterator>
ReturnType Function
    (
    InputIterator first,
    InputIterator last
    )
{
    for (InputIterator iter = first; iter != last; ++iter) {
        // Work with *iter
    }
}

By using this construct, you allow vast usage flexibility. Try to limit yourself to input iterator expressions on first and last (basically preincrement, dereference, and comparison) to minimize the requirements the InputIterator class must fulfill.

Most (all?) STL containers can pass their contents to Function() by using the containers’ begin() and end() functions, as in:

1
2
std::vector<T> v;
ReturnType ret = Function(v.begin(), v.end());

As C pointers are random-access iterators, you can pass arrays to Function() as follows:

1
2
3
const int arraySize = ...;
T array[arraySize];
ReturnType ret = Function(array, array + arraySize);

By the way, this lesson also applies to C#: prefer writing functions which accept IEnumerables rather than collections such as arrays. (In C# 2.0, you should be able to regain the lost typesafety by accepting IEnumerable<T>)