cin is not taking in the last input in a while loop

Question

In the following code segment, the cin inside the while loop, which is nested inside the while loop in the main function, is somehow not working during the last input (i.e, when h == n-1) and reporting a segmentation fault instead.

I figured this out by using the print statements (which are commented in the code below), one at the start of the inner while loop, one after the cin statement (to find the read values of v and x decremented by 1) and one outside the while loop. The third cout statement doesn't execute, from which I concluded that the segmentation fault is inside the while loop.

Moreover, in the last iteration of the inner while loop, the cout statement after the cin statement (to print the values of v and x) also didn't execute. And so, I think that the cin inside the inner while loop isn't working in the last iteration.

I tried searching a lot and put in the cin.clear() and cin.ignore(numeric_limits<streamsize>::max(), '\n'); statements but still no use!

Why is there such an issue?

#include <bits/stdc++.h>

using namespace std;
vector <vector<int>> adj;
vector<unordered_set <int>> leaf;

int process(int node, int *pans, int k){
    *pans = *pans + (leaf[node].size() / k) * k;
    int temp = (leaf[node].size() / k) * k;
    if(temp == 0) return 0;
    for(auto it : leaf[node]){
        if(temp == 0) break;
        leaf[node].erase(it);
        auto j = find(adj[node].begin(), adj[node].end(), it);
        adj[node].erase(j);
        temp --;
    }
    if(adj[node].size() == 1){
        leaf[adj[node][0]].insert(node);
        process(adj[node][0], pans, k);
    }
    return 0;
}

int main(){
    int t, v, x, n, k;
    cin>>t;
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    while(t--){
        int ans = 0;
        cin>>n>>k;
        cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        adj.resize(n);
        int h = 1;
        while(h < n){
            // cout<<"r";
            cin>>v>>x;
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            v --; x --;
            cout<<v<<" "<<x<<"\n";
            adj[v].push_back(x);
            adj[x].push_back(v);
            h++;
        }
        // cout<<"out";
        leaf.resize(n);
        for(int i = 0; i < n; i ++){
            if(adj[i].size() == 1) leaf[adj[i][0]].insert(i);
        }
        for(int i = 0; i < n; i ++){
            if(leaf[i].size() >= k) process(i, &ans, k);
        }
        cout<<ans<<"\n";
        adj.clear();
        leaf.clear();
    }
}

Following is an example of the input:

Please try to reduce the amount of code here. For example, you said your problem is in the input, so there's no reason for you to show the code that processes the data. Also, [`#include ` is a horrible idea](https://stackoverflow.com/q/31816095/9254539). — eesiraed, Jul 20 '20 at 06:34
Don't do the "clear and ignore" thing in situations where you don't need it. Doing it as an automatic incantation can cause bugs. — molbdnilo, Jul 20 '20 at 06:34
The ignore and clear calls are only necessary to recover the steam from a failed state when invalid inputs have been entered — Alan Birtles, Jul 20 '20 at 06:36
I had already tried without "clear and ignore" in the first place already but was finding this error and so then tried using it after which the error didn't change — sksingh, Jul 20 '20 at 06:37
@BessieTheCow , you are absolutely right. But I have already tried taking inputs using while loops many times before and this is the first time I got an error. Moreover without the rest of the code and just with a plane while loop there is no issue after all, so I thought mentioning the whole of the code might give a clarity in what exactly have I done (Although it isn't necessary, but still just for clarity). You may just focus on the input part! — sksingh, Jul 20 '20 at 06:42
The segmentation fault could be caused by a bug AFTER the last cin read. The code following cout << ... will execute (and can crash) before anything is printed. — Bartosz Bosowiec, Jul 20 '20 at 06:43
Oh! I didn't know that. Thank you very much for pointing out that, in that case I guess there is a problem with the range based for loop as @john has said — sksingh, Jul 20 '20 at 06:56
@SaketSingh Rather than putting `cout` statements into your code you should learn how to use a debugger. It's generally a much more reliable way to track down bugs than using `cout`. If you do use `cout` then remember to flush the output each time, otherwise you may not see all the output when you have a crash. — john, Jul 20 '20 at 06:59
Oh! thanks for the advice too! I will surely check out what a debugger is. Never tried out though. — sksingh, Jul 20 '20 at 07:00
When removing code that is executed after the input operations caused the bug to disappear, it's evidence that the bug is in the code that you removed. — eesiraed, Jul 20 '20 at 18:06

john · Accepted Answer · 2020-07-20T07:05:19.473

2

The error is here

for(auto it : leaf[node]){
    if(temp == 0) break;
    leaf[node].erase(it);
    auto j = find(adj[node].begin(), adj[node].end(), it);
    adj[node].erase(j);
    temp --;
}

By modifying the unordered_set leaf[node].erase(it); you are invalidating the implicit iterator used by the range based for loop. Rewrite your loop with an explciit iterator so you can account for the iterator invalidation. Like this

for (auto i = leaf[node].begin(); i != leaf[node].end(); ) {
    if(temp == 0) break;
    auto it = *i;
    i = leaf[node].erase(i);
    auto j = find(adj[node].begin(), adj[node].end(), it);
    adj[node].erase(j);
    temp --;
}

With this loop your code runs to completion (at least for me). I've no idea if the output is correct or not.

edited Jul 20 '20 at 07:05

answered Jul 20 '20 at 06:43

john

85,011
4
57
81

Thank you very much for pointing out that, could you also please also tell why is it illegal! However this answer is not related to my question I guess. Could you please check out the question again! There is a segmentation fault before the last input and this range based for loop never runs at all! – sksingh Jul 20 '20 at 06:46
@SaketSingh I ran you code an got an error in the above loop. There maybe other errors in your code. – john Jul 20 '20 at 06:47
Could you please tell whether have you run the entire code or just the for loop? In case you have run the entire code, could you tell which version of compiler did you use? I have tried it out on C++17 of onlinegdb.com and was getting an error in the input and the range based for loop didn't execute before the error (and the question is regarding this error). Could you also please provide some reference for me to understand why this for loop is incorrect? – sksingh Jul 20 '20 at 06:52
1

@SaketSingh I expect you are running into the problem where if your code crashes then then you don;t necessarily see all the output from your program. So it can seem that your crash is earlier than it actually is. With the change to the loop above the code runs to completion for me. – john Jul 20 '20 at 06:54
1

@SaketSingh Here a link about how range based loops actually work https://en.cppreference.com/w/cpp/language/range-for, and heres a link about iterator invalidation. https://en.cppreference.com/w/cpp/container – john Jul 20 '20 at 06:56
I didn't know that! Thank you very much for helping me out. Also thank you for providing the resource for me to understand range based for loops in a better way! Thanks a lot! – sksingh Jul 20 '20 at 06:59

cin is not taking in the last input in a while loop

1 Answers1