A neutral element? Time for maths?

What happens, if we call sum2 for a vector of strings? The decisive spot is the initialization of res:

template<typename Iterator>
typename value_type<Iterator>::result
sum2(Iterator  a, Iterator a_end)
{
  typename value_type<Iterator>::result res = 0;
  for(; a != a_end; ++a)
    res += *a;
  return res;
}

What should really happen, when we pass a sequence of std::string into sum2? The return value res should be initialized with an empty string. An in general, res should be initialized with the neutral element with respect to the addition. For built-in number types, this is the value 0, and therefore sum2 works for those types. Where do we get the correct value for initialization?

Alternatives for initializing the sum

There are several possibilities:

1. We use a technique analogous to value_type
2. We introduce an additional argument init to pass the neutral element
3. We initialize res with the first element of the sequence and start iteration with the second element

All these solutions have their pros and cons. The first solution requires some effort from the user, if "his" type is not yet supported. Also, there are types for which the correct value of the neutral element can only be determined at run time (for instance, a matrix type with dimensions determined at run time). We'll come back to this solution and extend it in a more general context.

Solution no. 2 complicates the interfaces, but permits to nest calls to sum2:

x = sum(a.begin(), a.end(), sum(b.begin(), b.end(), init));

However, the problem is simply moved to a higher level: If the calling context is generic as well, it does not know the correct neutral element either. On the other hand, the implementation gets more general, because the type of init could be different from the iterator's value type (which is a danger as well, we'll discuss this below).

The 3rd solution keeps the simple interface, initializes automatically and correctly, and might be a bit more efficient. However, it does not work any more for empty sequences. This does not seem to be a big restriction, but if the function is used within a larger iteration computing partial sums of potentially empty sub-sequences, the ability to correctly deal with those could spare a lot of tests.

A solution attempts for initialization

Lacking a clear winner, let's try to combine the strengths of the individual solutions. Solution no. 2 is certainly the most general, at the expense of being less comfortable to use. Thus, it seems natural to implement this as a basis and offer the other solutions later as convenience wrappers without the init argument. Here, we could also test at compile time, whether a neutral element is known, and then branch to either solution 1 or 3. Thus, the restriction of not being able to sum up empty sequences only applies when — lacking a neutral element — it does not make sense anyway.

Let's thus concentrate on solution 2 with the init argument:

template<typename Iterator, typename T>
T
sum3(Iterator  a, Iterator a_end, T init)
{
  T res = init;
  for(; a != a_end; ++a)
    res += *a;
  return res;
}

Next try with strings ...

Now, a call with a vector of string should be possible:

std::string words[] = { "This", "is", "a", "sentence" };
// ...
std::string sentence = sum3(words, words+4, ""); // Ouch

Unfortunately, the compiler does not like this, because it determines the type of the literal "" not as std::string but as const char*. Thus, we have to be a bit more specific:

std::string sentence = sum3(words, words+4, std::string("")); // So!

Now it works! (Btw: Does the output in sentence look like you want it? And should we use sum for strings at all?)

Let's try what we can do with the additional parameter init ...

• <<<Previous page
• Next page >>>