By Prasoon Saurav


2010-07-11 03:59:34 8 Comments

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?

10 comments

@NeutronStar 2017-12-05 09:30:18

One can also use std::valarray<T> like this

#include<iostream>
#include<vector>
#include<valarray>

int main()
{
    std::vector<int> seq{ 1,2,3,4,5,6,7,8,9,10 };
    std::valarray<int> seq_add{ seq.data(), seq.size() };
    std::cout << "sum = " << seq_add.sum() << "\n";

    return 0;
}

Some may not find this way efficient since the size of valarray needs to be as big as the size of the vector and initializing valarray will also take time.

In that case, don't use it and take it as yet another way of summing up the sequence.

@paxdiablo 2010-07-11 04:15:53

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. Basically, anything that can change the underlying vector is intercepted to ensure the sum is kept consistent.

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.

Vectors where the sum is needed more often than the vector is changed are the ones likely to benefit from this scheme, since the cost of calculating the sum is amortised over all accesses. Obviously, if you only need the sum every hour and the vector is changing three thousand times a second, it won't be suitable.

Something like this would suffice:

class UberVector:
    private Vector<int> vec
    private int sum

    public UberVector():
        vec = new Vector<int>()
        sum = 0

    public getSum():
        return sum

    public add (int val):
        rc = vec.add (val)
        if rc == OK:
            sum = sum + val
        return rc

    public delindex (int idx):
        val = 0
        if idx >= 0 and idx < vec.size:
            val = vec[idx]
        rc =  vec.delindex (idx)
        if rc == OK:
            sum = sum - val
        return rc

Obviously, that's pseudo-code and you may want to have a little more functionality, but it shows the basic concept.

@Evan Teran 2010-07-11 04:50:49

interesting, but be careful as std::vector isn't meant for subclassing.

@paxdiablo 2010-07-11 05:08:03

Sorry, I should have been clearer - you could create your own class with the same methods as vector which maintained a has-a vector within it, rather than being a proper subclass (is-a).

@Matt Joiner 2010-11-14 07:02:56

@paxdiablo: Very nice with the has-a.

@David Rodríguez - dribeas 2010-12-02 19:25:41

This is problematic unless you disable the accessors into the data, including but not limited to operator[](int), non-const iterators...

@paxdiablo 2010-12-02 22:32:11

Not sure what you mean, @David, you won't have access to the actual vector, it will be a private member of your own class. Any accesses/changes will have to be through functionality provided by your class so you will be able to intercept all use of the underlying vector.

@Bret Kuhns 2012-09-04 03:21:12

@paxdiablo I believe David means if the data stored in the vector is manipulated through the use of operator[] or indirecting through a non-const iterator. The value at the manipulated position will now be different which will make the sum incorrect. There's no way to assure the sum is correct if client code is ever able to hold a mutable reference to any element within the "subclassed" vector.

@paxdiablo 2012-09-04 03:39:40

That makes sense, but surely that's just a matter of providing the operator[] or iterator over the UberVector object rather than the Vector member. The whole point is to protect the vector from outside changes so the sum is always consistent with the data. If you expose the internal vector somehow, all bets are off.

@Basilevs 2012-09-04 09:11:46

This approach causes performance penalty for basic vector operations.

@t.y 2018-07-11 17:56:08

has-a over is-a is synonymous to the maxim "prefer composition over inheritance," and is discussed further here: stackoverflow.com/questions/49002/…

@paxdiablo 2018-11-05 03:26:25

@Basilevs: yes it will have an cost. The question is, does that cost outweigh the benefits? What you'll most likely be looking at is a single extra layer of call to the underlying vector, there'll be no extra checks taking place or anything like that. I'll note, as one example, that smart pointers also have a cost but the chances of me going back to the bad old days of raw pointers is very slim :-) Basically, if the benefit of having a constant-time sum() function are worth more than the cost, use this solution. If not, calculate the sum each time.

@Haresh karnan 2019-01-16 06:33:28

It is easy. C++11 provides an easy way to sum up elements of a vector.

sum = 0; 
vector<int> vec = {1,2,3,4,5,....}
for(auto i:vec) 
   sum+=i;
cout<<" The sum is :: "<<sum<<endl; 

@beahacker 2018-10-07 04:33:00

The easiest way is to use std:accumuate of a vector<int> A:

#include <numeric>
cout << accumulate(A.begin(), A.end(), 0);

@Ravi Kumar Yadav 2018-06-24 11:07:31

I found the most easiest way to find sum of all the elements of a vector

#include <iostream>
#include<vector>
using namespace std;

int main()
{
    vector<int>v(10,1);
    int sum=0;
    for(int i=0;i<v.size();i++)
    {
        sum+=v[i];
    }
    cout<<sum<<endl;

}

In this program, I have a vector of size 10 and are initialized by 1. I have calculated the sum by a simple loop like in array.

@Vincent Saulue-Laborde 2018-06-24 11:56:52

Using int to index a std::vector is not safe in general. v.size() might be bigger than the highest value that can be stored in int (note that with some target platforms & compilers, size_of(int) < size_of(size_t)). In this case, your code will overflow the index. std::vector<T>::size_type should be prefered.

@Ravi Kumar Yadav 2018-06-25 14:13:37

It's an example @VincentSaulue-Laborde You can take data type and it's size according to your requirement.

@Prasoon Saurav 2010-07-11 04:01:52

Actually there are quite a few methods.

int sum_of_elems = 0;

C++03

  1. Classic for loop:

    for(std::vector<int>::iterator it = vector.begin(); it != vector.end(); ++it)
        sum_of_elems += *it;
    
  2. Using a standard algorithm:

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

    flag

    Be careful with accumulate. The last argument's type is used not just for the initial value, but for the type of the result as well. If you put an int there, it will accumulate ints even if the vector has float. If you are summing floating-point numbers, change 0 to 0.0 or 0.0f (thanks to nneonneo).

C++11 and higher

  1. Using std::for_each:

    std::for_each(vector.begin(), vector.end(), [&] (int n) {
        sum_of_elems += n;
    });
    
  2. Using a range-based for loop (thanks to Roger Pate):

    for (auto& n : vector)
        sum_of_elems += n;
    

@Ben Voigt 2010-07-11 04:04:16

Of course in C++03 you can use std::for_each with a functor, it just takes more lines of code to define than the C++0x lambda.

@jalf 2010-07-11 07:15:44

Why do your lambda examples use for_each? accumulate would be more concise (even if it doesn't need the lambda)

@Prasoon Saurav 2010-07-11 07:37:58

@jalf: your point is correct, I should have used accumulate inside for_each but isn't this example useful(for learning purpose) as it shows that we can also have nested lambdas :-)

@jalf 2010-07-11 08:14:48

@Prasoon: true. I was just worried that it might give some people the idea that lambas only work with for_each.

@Amnon 2010-07-11 11:24:52

Can someone explain what does case 4 add to case 3? Is there more to it than wrapping the operation in a function?

@Prasoon Saurav 2010-07-11 11:29:12

@Amnon: Is there more to it than wrapping the operation in a function? Nopes, the example was just to show that lambdas can be nested inside the other as I have mentioned in my last comment.

@Roger Pate 2010-07-11 20:20:01

You missed the most obvious – and, IMHO, the most natural – 0x-only solution. :)

@bobobobo 2010-08-20 12:52:56

You missed the vanilla (non-iterator) for loop!

@nneonneo 2013-02-19 03:30:48

Be careful with accumulate. The last argument's type is used not just for the initial value, but for the type of the result. If you put an int there, it will accumulate ints even if the vector has float. The result can be subtly wrong, and the compiler will cast the result back up to a float without telling you.

@silvergasp 2016-01-07 00:26:56

It is better when using a range based for loop to pass by a const reference, particularly when you are not changing any elements in the iterated container. Your example above copies each element to a temporary variable first wich adds significant overhead. For example use for (int const &n : vector) or perhaps a more future proof version for (auto const &n : vector) . It is possible that your compiler is intelligent enough to make this optimisation anyway however it should not be relied upon.

@juanchopanza 2016-02-11 19:44:04

Why would you use for_each if you have accumulate?

@Isaac 2016-12-15 04:42:13

@nneonneo: Thank you!! Wow. just wow! I personally believe the compiler must use the type of the given range and cast the last parameter to it, not the other way around. Besides that, why the compiler doesn't even tell about this implicit conversion from double/float to int?

@nneonneo 2016-12-15 13:16:53

@Isaac: because this is just how accumulate is implemented - as essentially decltype(initial) accum = initial; for(auto i : vec) accum += i; return accum;. Doing int += float doesn't warn.

@James McNellis 2010-07-11 04:53:38

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()); i > 0; --i)
    sum_of_elements += v[i-1];

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

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

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.

@paxdiablo 2010-07-11 05:17:45

And why not also cycle through the vector by adding a prime number with the modulus operator for wraparound? :-)

@msandiford 2010-07-13 04:55:02

@paxdiablo You only really need to be relatively prime to v.size().

@Moberg 2014-02-05 10:06:09

msandiford: not only. @paxdiablo: you need to be realtively prime if you want to access all elements. stepping +7 in a vector of size 7 wont give you much...

@Julien Guertault 2014-04-23 06:19:36

-1: vector::size() returns an unsigned value, making expressions like (v.size() - 1) generate warnings, or a minefield in worst cases.

@Lynn 2017-03-14 20:39:24

Why does this answer exist? Is there an advantage to summing backwards, or are you just trolling?

@Peter Cordes 2017-07-30 06:10:46

@Lynn: If the end of the vector is hot in cache (from a previous loop that went forwards), then yes, looping backwards can be measurably faster on current Intel x86 CPUs. Also, counting a loop-counter down to zero can save the compiler an instruction in the asm, which can be significant if it doesn't unroll the loop. Prefetching sometimes works slightly better when looping forwards, though, so in general it's not better to always loop backwards.

@kriss 2010-07-11 04:15:13

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

@bobobobo 2010-08-20 12:53:58

Why do you say iterating on indices is inefficient? What's your basis for saying that?

@kriss 2010-08-20 13:28:48

@bobobobo: well, inefficient is probably excessive. You have both to compute effective data position from vector and increment counter but one of these two operations should be enough, but cost of dereferencing iterators may even be worse. Hence I will remove the word.

@Peter Cordes 2017-07-30 06:18:25

An optimizing compiler can optimize away the index variable and just use a pointer increment if it wants to. (It can make the loop-exit condition be a pointer-comparison against start + length). Actual iterators should also optimize away entirely. Remember, it's not perl; it's fully compiled to asm, not interpreted.

@rafak 2010-08-06 15:40:40

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

@Prasoon Saurav 2010-08-15 08:56:13

Thanks for the answer. BTW what is the difference between std::accumulate and boost::accumulate in time complexity?

@metal 2010-09-11 15:16:59

The time complexity is the same for std's and boost's accumulate -- linear. In this case, boost::accumulate is just easier to type than sending in the begin and end manually. There's no real difference.

@rafak 2010-09-15 10:15:25

boost::accumulate is just a wrapper around std::accumulate.

@Peter Cordes 2017-07-30 06:14:46

The non-boost way is not much harder: #include <numeric> and std::accumulate(v.begin(), v.end(), (int64_t)0);. Notice that the type of the initial accumulator value is used as the accumulator type, so if you want to sum 8-bit elements into a 64-bit result, that's how you do it.

@Roger Pate 2010-07-11 20:16:52

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.

@Jonas 2014-10-20 12:10:46

If you change for (int n : v) sum += n; into for (auto n : v) sum += n; it will work with any vector template. I known OP referes to vector<int>, but this way is slightly more general :-)

Related Questions

Sponsored Content

1 Answered Questions

[SOLVED] The Definitive C++ Book Guide and List

  • 2008-12-23 05:23:56
  • grepsedawk
  • 2275458 View
  • 4245 Score
  • 1 Answer
  • Tags:   c++ c++-faq

39 Answered Questions

22 Answered Questions

[SOLVED] What is the "-->" operator in C++?

15 Answered Questions

[SOLVED] Best way to extract a subvector from a vector?

  • 2009-01-07 18:56:28
  • An̲̳̳drew
  • 296639 View
  • 282 Score
  • 15 Answer
  • Tags:   c++ stl vector range

19 Answered Questions

[SOLVED] How to find out if an item is present in a std::vector?

  • 2009-02-20 21:58:41
  • Joan Venge
  • 888276 View
  • 596 Score
  • 19 Answer
  • Tags:   c++ vector std

18 Answered Questions

[SOLVED] Why should C++ programmers minimize use of 'new'?

13 Answered Questions

[SOLVED] How do I erase an element from std::vector<> by index?

  • 2009-05-17 17:59:36
  • dau_man
  • 711802 View
  • 471 Score
  • 13 Answer
  • Tags:   c++ stl vector erase

10 Answered Questions

Sponsored Content