Блог пользователя Letscode_sundar

Strange observation with accumulate() function in STL
Автор Letscode_sundar, история, 3 года назад, По-английски

I was doing this problem and i noticed a strange thing.

In order to calculate sum of the vector elements , I used the accumulate function available in STL

typedef long long ll;
#define int ll
//the sum variable and elements in vector becomes long long type
int sum=0;
sum=accumulate(v.begin(),v.end(),0);

127183042

This basically gives the wrong answer .

But

#define int ll
int sum=0;
sum=accumulate(v.begin(),v.end(),sum);
or
sum=accumulate(v.begin(),v.end(),0LL);

127184393

127184828

gets accepted.

Why is this happening ?

All these days, I thought it is just an initial value that we give to the accumulate function (the last argument), but it is not just an initial value and plays a big role in the outcome of the sum.

I am telling it isn't just a value because 

ll sum=10;
sum+=20;

Now it wouldn't matter if 20 is given in LL or not , but here 0 gives WA but 0LL is accepted.

  • Проголосовать: нравится
  • -26
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Letscode_sundar (previous revision, new revision, compare).

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
sum=accumulate(v.begin(),v.end(),0);

is as the same as

int result = 0;
for (int x : v) result += x;
sum = result;

Which give you overflow, but 0LL and sum isnt because they are long long type

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

#define is nothing more than a copy paste instruction to preprocessor, #define int ll just replaces every occurence of int in your code with ll, but these types don't get magically linked and 0 is still a regular 32-bit int.

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Referring to https://www.cplusplus.com/reference/numeric/accumulate/

The behavior of this function template is equivalent to:

template <class InputIterator, class T>
   T accumulate (InputIterator first, InputIterator last, T init)
{
  while (first!=last) {
    init = init + *first;  // or: init=binary_op(init,*first) for the binary_op version
    ++first;
  }
  return init;
}

Assuming you know how Templates work (if not http://www.cplusplus.com/doc/oldtutorial/templates/),

calling sum=accumulate(v.begin(),v.end(),0);

The template resolves to accumulate(vector<ll>::iterator, vector<ll>::iterator, int)

and calling sum=accumulate(v.begin(),v.end(),0LL); or sum=accumulate(v.begin(),v.end(),sum); [sum is long long because of macro]

it resolves to accumulate(vector<ll>::iterator, vector<ll>::iterator, ll)

This should explain the behavior as the integer will overflow in the first case and the ll will not in the second.

→ Ответить