Passing std algorithm iterator parameters by value vs. by reference

Question

I'm wondering why in many template algorithms in the STL the arguments are not passed by reference but rather by value. Here is an example from the <iterator> header:

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last);

When I pass two iterators to this function, they are copied. My naive thoughts are that it would be better to pass these iterators by const-reference to avoid copying the iterator objects:

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (const InputIterator &first, const InputIterator &last);

One could say that iterators are in general very small objects and that copying them is not expensive. But even still: cheap copying would be more expensive than no copying at all.

So what is the reason that in the STL-version, the iterators are passed by value?

Thank you!

Answer 1

One thing that comes to my mind and which is against the constness in the reference: the iterators need to be modified when using them.

Another implementation detail may be that iterators are really just implemented as pointers. So are references in most cases. If you pass the pointer by value, you copy it once but dereference it only when needed. If, however, the iterator-pointer itself is passed by a reference-pointer, then that has to be dereferenced first, just in order to get to the iterator, and that must be done each time the iterator is accessed. That is superfluous.

Answer 2

For certain cheap-to-copy types, passing them by value is actually faster than passing by reference. Conventional wisdom from tutorials, etc., states that by reference is faster, but this does not necessarily apply to cheap-to-copy types.

How do you pass an object by value? You make a copy of it, which means you take the value and push it to the stack for the function call. And how do you pass by reference? You push the memory address to the stack, and then the called function has to fetch whatever is at that address. Now, optimization and caching may come into play to make that memory fetch much cheaper, but you still don't get cheaper than taking the exact value from the stack. Which in the case of iterators is often something as simple as a mere pointer. Which is one word long and so very cheap to copy.

Also, note you're suggesting to pass a const reference. Which means it would have to be copied anyway in the called function to let it be modified (such as incrementing in a loop).

Answer 3

The concept of std iterators is the generalisation of a pointer. The iterators of the std containers are commonly implemented as a type that composes a single pointer. In the case of an argument type that is as cheap to copy as a pointer, passing the argument by reference is more expensive than passing it by value. A reference to an object must be dereferenced before the object's value can be used. See this answer for more details.

Because almost all std algorithms need to make copies of iterators, in order to obtain the best performance it's already essential that an iterator is cheap to copy. For this reason, it's very unusual to find an iterator which is significantly more expensive to pass by value than by reference.

In the case of std::distance - and many other algorithms - the entire algorithm is so simple that the call will very likely be inlined by the compiler. If the call is inlined, it does not matter whether the argument passed by reference or by value. [Note that an inlined function call is not the same as an inline function declaration!]

In the case of an iterator being more expensive to pass by value than by reference, and the function call not being inlined, you could make an argument for passing iterators by rvalue-reference. The performance gain in such a rare case is probably not worth the additional complexity.

Answer 4

Most algorithms modify their arguments. For instance, distance might be implemented as follows¹:

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last) {
    typename iterator_traits<InputIterator>::difference_type result{};
    while (first++ != last)
        ++result;
    return result;
}

Clearly this doesn’t work if you pass first as a const reference.

And it also doesn’t work if you pass it as a non-const reference because in most calling contexts the caller’s objects cannot be modified (for instance if you pass the result of container.begin() to the function.

Of course you could still pass by const reference, make a copy inside the function and then modify that. At which point we’d have gained exactly nothing.

Coupled with the C++ standard recommendation that iterators should be lightweight types that should be cheap to copy, it’s more simple and in most cases more efficient to pass them by value:

But even still: cheap copying would be more expensive than no copying at all.

Not true. You also need to copy the reference (which, in the case of a non-inlined function call, is going to be implemented as a pointer). And then you need to dereference that pointer which also adds overhead. Compared to a straight copy which may be as cheap as copying a pointer in many cases, and doesn’t incur any dereferencing overhead.

---

¹ Of course a real implementation would be optimised for random access iterators to have constant rather than linear runtime. The above implementation is for exposition only.