Template Function: Passing Iterators

Question

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?

Answer 1

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;
}

• 1v0: Thank you, I just used the sum function as a generic example, I am asking the question in a broader setting. But the accumulate example shows nicely how std is handling it.
• Niall: @1v0. I think iterator_traits may be what you are looking for.
• 1v0: Thanks for the edit. May I ask why you have the second template parameter U and not just let the sum variable be of type std::iterator_traits<Iterator>::value_type inside the function?
• Niall: @1v0. No reason really, just threw it in with the C++11. It could be used to specify the return type, but that would need the iterator type to be typed out as well... I've added an alternative. Note though, that the return type can't be U without it being a template argument, if no U then the return type needs to typed out the long way then.