Why does std::accumulate behave like this with standard arrays?

Question

I'm just getting into C++ and I think I have a handle on pointers, but std::accumulate() has me confused.

Given the array:

int a[3] = { 5, 6, 7 };

I'd like to sum the values of the array with std::accumulate(), so I pass it a pointer to the first element, then the last, then the starting value of the accumulator.

std::accumulate(a, a + 2, 0);
std::accumulate(&a[0], &a[2], 0);

Oops: either of these returns the sum of only the first two elements: 11.

On the other hand, if the second argument is a nonsensical pointer, just out of bounds...

std::accumulate(a, a + 3, 0);
std::accumulate(&a[0], &a[3], 0);

... the correct value of 18 is returned.

Could someone please explain this? I realise that I could avoid using simple arrays, but that's beside the point.

Answer 1

C++ ranges are defined as [first, last), and all the STL algorithm work like that. In this case, std::accumulate sums up all the elements behind the iterator-defined range, starting with first and ending at last without actually dereferencing it.

Thus, calling it like std::accumulate(a, a+3, 0) is actually correct and equal to calling it with std::accumulate(begin(a), end(a), 0).

Also note that this doesn't fall foul of the "no pointers to outside of allocated arrays" rule, as there is a specific exception for pointer to just behind the last element.

Answer 2

std::accumulate, like most STL algorithms, takes an iterator past the last element of the container. In this case, that iterator would be &a[3]. You might want to use std::begin(), std::end() since it works with all containers and is less error-prone. Also, since std::begin on arrays is just a pointer you can always say things like std::begin()+k. So, you don't lose any flexibility.

Answer 3

The end iterator is one past the last element since "ranges" are half open in the stl. This means that the first element is included and the last one is NOT included.

Besides that, I recommend you to use c++11 begin and end free functions. They are overloaded for plain c arrays as well.

Answer 4

I don't know the historical reason of this convention for iterators (including raw pointers and STL Iterators). But my opinion is it is consistent to the way we access arrays or containers with index.

1.

C/C++ array and C++ STL containers count the index from 0 to (size - 1).

Consider what will happen when you calculate the size of the array or container by taking the difference between a pair of pointers or iterators like:

size = ending_pointer - beginning_pointer;
// or
size = std::distance(beginning_iterator, ending_iterator);

This will really give you the size if ending_pointer or ending_iterator refers to the position past-the-last.

2.

Conventionally, looping through an array with index like this:

for (size_t i = 0 ; i < size ; ++i)

Note that we use less-than instead of less-than-or-equal-to.

For iterator:

// Usually found in implementations of STL algorithms
for (iterator_type it = beginning_iterator ; it != ending_iterator ; ++it)

Note that we use not-equal-to instead of equal-to.

3.

To handle the cases with an array or container of size 0, the convention of one-position-past-the-last is convenient for programmers and compiler optimization, since the beginning iterator will be equal to ending iterator.

for (iterator_type it = beginning_iterator ; it != ending_iterator_which_equals_the_beginning ; ++it)
// still consistent to
for (size_t i = 0 ; i < size_which_is_zero ; ++i)

---

As mentioned in others' answers, we prefer std::begin(container) and std::end(container). They can free us from the troubles of pointer arithmetic and thus less error prone. They also make generic coding easier.

Answer 5

std::accumulate(...) usually is better use with std::begin(...) and std::end(...) functions. According a code std::accumulate(first, last, 0) it sums up elements from first to last, but without the last one. When you are using container methods begin(), end() code sums up every elements (as you expect) because end() returns iterator to past-the-end element (element after the last true element). It is used for example in loops:

vector<int> vec = { 1, 2, 3, 4, 5, 6, 7, 8 };

for (auto it = begin(vec); it != end(vec); ++it)
{
    // do some work ...
}

Functions std::begin(...) and std::end(...) work with simple C++ array. Your code with &a[3] works because you point to the next element after the true last one. But your code is not correct and you mustn't code like that.