C++ Template Function – How to Pass Iterators

citeratortemplates

I am struggling with making a design choice in the following setup:

I am writing (C++) functions which take a pair of iterators (to template containers) and compute a return value of the same type that the iterators are pointing to.

Let's say I want to implement a sum function (this is just an example to illustrate the point).

The way I see it I have two options and both have a downside:

Option 1

Make the function template parameter T defining the type the container stores.

I only need one parameter but I can only use the function on iterators of MyContainer.

template <class T>
T sum(typename MyContainer<T>::IteratorRange range){

    T sum;
    for (auto it = range.first; it < range.second; ++it) {
        sum += *it;
    }
    return sum;
}

Option 2

Have the function take an arbitrary IteratorRange template class
and a second class U determining the return type.

While the iterators can be sourced from any container, I need two template classes even though the return type is always the same type as pointed to by the iterators.

template <class IteratorRange, class U>
U sum(IteratorRange range){

    U sum;
    for (auto it = range.first; it < range.second; ++it) {
        sum += *it;
    }
    return sum;
}

Which option is cleaner or is there an alternative offering the benefits of both options?

Bonus Question

How should one initialize the sum variable?

Best Answer

The range to iterate over

The C++ standard library offers something of a canonical form here, accumulate;

template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );

It takes a range from first to last (excluding last) and adds each element in the range to the init value as an initial value. It will also infer the return type from the initial type.

If the an implementation of sum is required, I would advise the use of accumulate here as is. If not suitable, the function signature taking the range [first, last) is "normal" as it mirror the standard library.

Deduce the return type

To get the value type "behind" the iterator, std::iterator_traits, in particular the embedded type value_type can be used;

typedef typename std::iterator_traits<InputIt>::value_type Result;
// .. default initialise
Result sum = Result{}; // or Result() if earlier than C++11

Design choice

I would design the function to (variation of option 2);

  • Accept a range [first, last)
  • Use std::iterator_traits (that work with pointers as well) to infer the return type
  • Use the C++11 default initialisation to initialise the result

As follows:

template <class Iterator, class U = typename std::iterator_traits<Iterator>::value_type>
U sum(Iterator first, Iterator last)
{
    U sum = U{};
    for (auto it = first; it != last; ++it) {
        sum += *it;
    }
    return sum;
}

An alternative with reduced template arguments.

template <class Iterator>
typename std::iterator_traits<Iterator>::value_type sum(Iterator first, Iterator last)
{
    using U = typename std::iterator_traits<Iterator>::value_type;
    U sum = U{};
    for (auto it = first; it != last; ++it) {
        sum += *it;
    }
    return sum;
}
Related Topic