Different behavior of list C++

Question

I need help. I can't figure out why my program works differently in main function and in any other function, lets say solve() function. I want to solve this problem http://codeforces.com/contest/768/problem/B?locale=en. I have written the code and it works fine, but gets time limit in the server. My code is like this and it works fine when I compile it:

#include<iostream>
#include<windows.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<list>
#include<iterator>

using namespace std;

main()
{
    list < int > li;
    list < int >::iterator i;
    list < int >::iterator end = li.begin();
    int n, l, r, buffer, ans = 0;
    cin >> n >> l >> r;
    li.push_back(n);
    for(i=li.begin(); i!=li.end(); i++)
    {
        while(*i>1)
        {
            buffer = *i;
            i = li.erase(i);
            li.insert(i, buffer/2);
            li.insert(i, buffer%2);
            li.insert(i, buffer/2);
        }
    }
    advance(end, r+1);
    i = li.begin();
    for(advance(i, l-1); i!=end; i++)
        ans += *i; 
    cout << ans << endl;
    return 0;
}

When I rewrited the code like this, it stopps working properly, so I think the time limit is because of this:

#include<iostream>
#include<windows.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<list>
#include<iterator>

using namespace std;

int solve()
{
    list < int > li;
    list < int >::iterator i;
    list < int >::iterator end = li.begin();
    int n, l, r, buffer, ans = 0;
    cin >> n >> l >> r;
    li.push_back(n);
    for(i=li.begin(); i!=li.end(); i++)
    {
        while(*i>1)
        {
            buffer = *i;
            i = li.erase(i);
            li.insert(i, buffer/2);
            li.insert(i, buffer%2);
            li.insert(i, buffer/2);
        }
    }
    advance(end, r+1);
    i = li.begin();
    for(advance(i, l-1); i!=end; i++)
        ans += *i; 
    cout << ans << endl;
}

main()
{
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

Anybody knows why?

Do you know that `#define {in|out} blah` don't do anything unless you use `in` or `out`? — HolyBlackCat, Jan 24 '18 at 18:28
I highly recommend not using `#define` to abbreviate function calls. If you want to develop faster, take a keyboarding class. When people read your code and encounter `revs()`, they will have to hunt for the macro, then insert the macro at the invocation. Bad form. — Thomas Matthews, Jan 24 '18 at 18:29
If you want to speed up I/O, block read the data into a buffer, then parse the buffer. Input is faster when it is continuous. — Thomas Matthews, Jan 24 '18 at 18:30
you are modifying your list while iterating over it - this is not allowed. Similar issue with sets https://stackoverflow.com/questions/2088495/how-to-remove-all-even-integers-from-setint-in-c/2088542#2088542 — pm100, Jan 24 '18 at 18:37
your problem is Undefined Behaviour. Dont try to reason about UB. What you see is that UB code does different things in different places. In one case it even seems to work - the worst kind of UB — pm100, Jan 24 '18 at 18:39
@FrançoisAndrieux - on the bright side he doesnt use them so its all good :-) — pm100, Jan 24 '18 at 18:40
use std::vector instead of List. You can use direct indexing rather than all that iterator messing. — pm100, Jan 24 '18 at 18:42

R Sahu · Answer 1 · 2018-01-24T19:10:29.813

0

Your program had undefined behavior.

You have:

list < int >::iterator end = li.begin();

before anything is added to the list, which is the same as

list < int >::iterator end = li.end();

followed by

advance(end, r+1);

that is a problem since you can not advance end.

edited Jan 24 '18 at 19:10

answered Jan 24 '18 at 18:30

R Sahu

204,454
14
159
270

The problem is in while loop. But I don't know what is exactly the problem. Code works in main function but in other function not. – Muhammadali Nazarov Jan 24 '18 at 18:35
@MuhammadaliNazarov If you have undefined behavior, it doesn't matter *where* you see the problem. It's just a symptom. The real problem is whatever caused the undefined behavior. In cases of undefined behavior, the error and the consequences of that error can be very distant from one another. It's been demonstrated that, in some situations, the behavior can be affected before the line containing the undefined behavior is executed due to how the compiler manipulates your code. – François Andrieux Jan 24 '18 at 18:42

score 0 · Accepted Answer · answered Jan 24 '18 at 18:58

I have found the answer.

    while(*i>1)
    {
        buffer = *i;
        i = li.erase(i);
        li.insert(i, buffer/2);
        li.insert(i, buffer%2);
        li.insert(i, buffer/2);
    }

In this part of code. When iterator 'i' reaches the end and erases the value, it points to (right) unexisted part of list, so program behaves unexpectedly.

Different behavior of list C++

2 Answers2