sum of elements in a `std::vector`

Question

What are the good ways of finding the sum of all the elements in a std::vector?

Suppose I have a vector std::vector<int> vector with a few elements in it. Now I want to find the sum of all the elements. What are the different ways for the same?

Answer 1

Actually there are quite a few methods.

 int sum_of_elems=0;

1)

for(std::vector<int>::iterator j=vector.begin();j!=vector.end();++j)
    sum_of_elems += *j;

2)

sum_of_elems =std::accumulate(vector.begin(),vector.end(),0);//#include <numeric>

3) C++ 0x only (using lambdas)

 std::for_each(vector.begin(),vector.end(),[&](int n){

                        sum_of_elems += n;

 });

4) C++ 0x only (similar to previous approach) #include<functional>

 std::tr1::function<int()> l=[&]()->int {
    sum_of_elems=0;
    std::for_each(vector.begin(),vector.end(),[&](int n){

                        sum_of_elems += n;  
    });
    return sum_of_elems;
  };

 std::cout<<l(); //prints the sum of elements

5) Using Range for statement (C++0x only) (Thanks to Roger Pate)

(Not supported even by g++ 4.6 with -std=c++0x option)

  for (int n : vector) 
    sum_of_elems += n;  

Answer 2

I'm a Perl user, an a game we have is to find every different ways to increment a variable... that's not really different here. The answer to how many ways to find the sum of the elements of a vector in C++ is probably an infinity...

My 2 cents:

Using BOOST_FOREACH, to get free of the ugly iterator syntax:

sum = 0;
BOOST_FOREACH(int & x, myvector){
  sum += x;
}

iterating on indices (really easy to read).

int i, sum = 0;
for (i=0; i<myvector.size(); i++){
  sum += myvector[i];
}

This other one is destructive, accessing vector like a stack:

while (!myvector.empty()){
   sum+=myvector.back();
   myvector.pop_back();
}

Answer 3

Prasoon has already offered up a host of different (and good) ways to do this, none of which need repeating here. I'd like to suggest an alternative approach for speed however.

If you're going to be doing this quite a bit, you may want to consider "sub-classing" your vector so that a sum of elements is maintained separately (not actually sub-classing vector which is iffy due to the lack of a virtual destructor - I'm talking more of a class that contains the sum and a vector within it (has-a rather than is-a) and provides the vector-like methods).

For an empty vector, the sum is set to zero. On every insertion to the vector, add the element being inserted to the sum. On every deletion, subtract it.

That way, you have a very efficient O(1) method for "calculating" the sum at any point in time (just return the sum currently calculated). Insertion and deletion will take slightly longer as you adjust the total and you should take this performance hit into consideration.

Answer 4

Why perform the summation forwards when you can do it backwards? Given:

std::vector<int> v;     // vector to be summed
int sum_of_elements(0); // result of the summation

We can use subscripting, counting backwards:

for (int i(v.size() - 1); i >= 0; --i)
    sum_of_elements += v[i];

We can use range-checked "subscripting," counting backwards (just in case):

for (int i(v.size() - 1); i >= 0; --i)
    sum_of_elements += v.at(i);

We can use reverse iterators in a for loop:

for(std::vector<int>::const_reverse_iterator i(v.rbegin()); i != v.rend(); ++i)
    sum_of_elements += *i;

We can use forward iterators, iterating backwards, in a for loop (oooh, tricky!):

for(std::vector<int>::const_iterator i(v.end()); i != v.begin(); --i)
    sum_of_elements += *(i - 1);

We can use accumulate with reverse iterators:

sum_of_elems = std::accumulate(v.rbegin(), v.rend(), 0);

We can use for_each with a lambda expression using reverse iterators:

std::for_each(v.rbegin(), v.rend(), [&](int n) { sum_of_elements += n; });

So, as you can see, there are just as many ways to sum the vector backwards as there are to sum the vector forwards, and some of these are much more exciting and offer far greater opportunity for off-by-one errors.

Answer 5

C++0x only:

vector<int> v; // and fill with data
int sum {}; // or = 0 ... :)
for (int n : v) sum += n;

This is similar to the BOOST_FOREACH mentioned elsewhere and has the same benefit of clarity in more complex situations, compared to stateful functors used with accumulate or for_each.

Answer 6

#include<boost/range/numeric.hpp>
int sum = boost::accumulate(vector, 0);