In c++ code, set.erase(it) is halting execution, where it=set.begin() for a set of pairs, why is this happening?

Question

Sorry for any inconvenience I am a beginner at C++ and was stuck with an empty set... Thank you for the helpful comments that helped me figure out what the problem was

I wrote a C++ code for a question in which I need to use Dijkstra's shortest path algorithm in n*log(n) time and so I am using set of pairs to obtain the vertex with shortest distance from source vertex. The code was not giving any errors at runtime but it wasn't giving the output either. So to see where it was getting stuck I used cout statements at certain points in the code and figured that the code is stopping execution right after the erase statement.

The statement is used in the code for erasing the first pair in the set and so the iterator pointing to set.begin() of the set is given as argument. It was earlier written in the format set.erase(iterator), but after searching for this problem on stack overflow I found someone saying iterator=set.erase(iterator) will solve the problem. I tried that and it still was getting stuck at that line, neither stopping execution and returning to the terminal nor giving a runtime error. I don't know what is wrong with this so I thought I would get some help here.

I am providing my code and a screenshot of the running too I would really appreciate your help.

#include<bits/stdc++.h>
using namespace std;

# define _z ios_base::sync_with_stdio(false); cin.tie(NULL);
# define ll long long int
#define mod 1000000007

int n;
set<pair<int, int>> dist;

void dij(vector<pair<int, int>> tree[], int decided[], int d[], vector<int>path[]) {
    int mindist=INT_MAX, ind=0;
    auto it=dist.begin();
    ind=it->second;
    cout<<"inbetween"<<endl;
    dist.erase(it);
    cout<<"inbetween"<<endl;
    decided[ind]=1;
    for(int i=0; i<tree[ind].size(); i++) {
        int update=d[ind]+tree[ind][i].second;
        int previous=d[tree[ind][i].first];
        if(update<previous) {
            pair<int, int>p=make_pair(previous, tree[ind][i].first);
            dist.erase(dist.find(p));
            p=make_pair(update, tree[ind][i].first);
            dist.insert(p);
            path[tree[ind][i].first]=path[ind];
            cout<<*path[tree[ind][i].first].begin()<<endl;
            path[tree[ind][i].first].push_back(tree[ind][i].first);
        }
        d[tree[ind][i].first]=min(update, previous);
    }
}

int main()
{
    int edges;
    cin>>n>>edges;
    vector<pair<int, int>> graph[n];
    set<pair<int, int>> dist;
    for(int i=0; i<edges; i++) {
        int x, y, weight;
        cin>>x>>y>>weight;
        x--; y--;
        graph[x].push_back({y, weight});
        graph[y].push_back({x, weight});
    }
    int src=1;
    //cin>>src;
    cout<<"here"<<endl;
    src--;
    int d[n];
    for(int i=0; i<n; i++) {
        if(src==i) {
            dist.insert({0, i});
            d[i]=0;
        }
        else {
            dist.insert({INT_MAX, i});
            d[i]=INT_MAX;
        }
    }
    int decided[n]={0};
    vector<int> path[n];
    path[src].push_back(src);
    for(int i=0; i<n; i++) dij(graph, decided, d, path);
    if(path[n-1].begin()==path[n-1].end()) cout<<-1<<endl;
    for(auto it=path[n-1].begin(); it!=path[n-1].end(); it++) cout<<*it+1<<" ";
    cout<<endl;
}

Image of the running code: Note that the highlighted lines are the problematic ones neither does iterator manipulation exist in the part of code that is getting stuck nor is the iterator accessed again after erasing.

It is only printing the line before the erase statement and not printing the one after...

[Useful reading](https://en.cppreference.com/w/cpp/container/vector/erase). Specifically *The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferenceable) cannot be used as a value for pos.* — user4581301, Dec 13 '20 at 17:54
Conditional or not, the problem is still the same. Your iterator is invalidated when `erase()` was called in it. Same for all other iterators pending on that vector. — πάντα ῥεῖ, Dec 13 '20 at 17:55
"erase() ing the iterator invalidates the current one, thus the next it++ is undefined behavior. That's the reason why erase() returns an iterator value, that you can use to continue the loop in place (do the it++ conditionally in cases you don't erase)" There is no it++!! — costheta_z, Dec 13 '20 at 17:55
@costheta_z To put it simple for you: `erase(it)` invalidates `it` for ***any*** further use. You may be also interested in reading this: https://stackoverflow.com/questions/347441/erasing-elements-from-a-vector — πάντα ῥεῖ, Dec 13 '20 at 17:57
@πάντα ῥεῖ it is not being used further anywhere! It is being redefined and thus reinitiated in every call of the function it is not being used anywhere after erasing! — costheta_z, Dec 13 '20 at 18:01
Unrelated, probably. `int decided[n]={0};` Doesn't do what you seem to expect it to do. Check your compiler's documentation on how it initializes Variable Length Arrays. The Standard C++ array initialization rules do not apply because Variable Length Arrays are not allowed in Standard C++. — user4581301, Dec 13 '20 at 18:03
@user4581301 the iterator is pointing to set.begin() in every run. I'm not trying to erase anything that is not dereferenceable... Is it because the elements are pairs and *it won't give you anything it->first or it->second will? how do i erase the first pair in the set then? — costheta_z, Dec 13 '20 at 18:09
And who said `begin()` can't equal `end()`? That's exactly what you'll get if the set is empty, something you aren't testing for. Drop something like `if (it == dist.end()) { cerr << "Oh snap!"; exit(-1); }` after you get the iterator and see what happens. — user4581301, Dec 13 '20 at 18:13
[What you think is happening is not happening.](https://ideone.com/5NY0q3) — user4581301, Dec 13 '20 at 18:19
``` auto it=dist.begin(); if(it==dist.end()) cout<<"nope"<first<second; ``` This code results in " nope 0 " this output.. How can it point to end and yet print ->first I don't understand I'm sorry if I sound dumb but I am a beginner and I really don't know how this could be happening... — costheta_z, Dec 13 '20 at 18:22
Dereferencing an undereferencable iterator invokes [Undefined behaviour](https://en.cppreference.com/w/cpp/language/ub). If you do something wrong, usually the program does the exact same thing it would do if the code was correct. If this means it read invalid memory, so be it. This makes for faster code when you get the logic right because there are no checks to see if you got something wrong. With great power comes great responsibility. — user4581301, Dec 13 '20 at 18:38
Thank you so much I'll look into it, sorry for the inconvenience. — costheta_z, Dec 13 '20 at 18:41

costheta_z · Accepted Answer · 2020-12-13T19:21:09.060

The problem as told by user4581301 in the comments was that the iterator was pointing to the end() of the set, which means the set was empty as it was initialized to point to begin() of the set. Thus an undereferencable iterator was dereferenced resulting in undefined behavior, (this means it may not necessarily give a runtime error but rather provide an output when dereferenced). Although the program thus gets stuck at this line as a result of this invalid accessing.

The fault in the code was that set was defined globally but then was refined by the same name inside main, this meant when the values are filled in the set inside main, they are filled in the set that was defined within main not the one defined globally. But when accessing the set in the function dij, the global set is accessed which is actually empty!

Removing the redefinition in main would resolve the issue.

#include<bits/stdc++.h>
using namespace std;

# define _z ios_base::sync_with_stdio(false); cin.tie(NULL);
# define ll long long int
#define mod 1000000007

int n;
set<pair<int, int>> dist;

void dij(vector<pair<int, int>> tree[], int decided[], int d[], vector<int>path[]) {
    int mindist=INT_MAX, ind=0;
    auto it=dist.begin();
    if(it==dist.end()) return;
    ind=it->second;
    dist.erase(it);
    decided[ind]=1;
    for(int i=0; i<tree[ind].size(); i++) {
        int update=d[ind]+tree[ind][i].second;
        int previous=d[tree[ind][i].first];
        if(update<previous) {
            pair<int, int>p=make_pair(previous, tree[ind][i].first);
            dist.erase(dist.find(p));
            p=make_pair(update, tree[ind][i].first);
            dist.insert(p);
            path[tree[ind][i].first]=path[ind];
            path[tree[ind][i].first].push_back(tree[ind][i].first);
        }
        d[tree[ind][i].first]=min(update, previous);
    }
}

int main()
{
    int edges;
    cin>>n>>edges;
    vector<pair<int, int>> graph[n];
    for(int i=0; i<edges; i++) {
        int x, y, weight;
        cin>>x>>y>>weight;
        x--; y--;
        graph[x].push_back({y, weight});
        graph[y].push_back({x, weight});
    }
    int src=1;
    src--;
    int d[n];
    for(int i=0; i<n; i++) {
        if(src==i) {
            dist.insert({0, i});
            d[i]=0;
        }
        else {
            dist.insert({INT_MAX, i});
            d[i]=INT_MAX;
        }
    }
    int decided[n]={0};
    vector<int> path[n];
    path[src].push_back(src);
    for(int i=0; i<n; i++) dij(graph, decided, d, path);
    if(path[n-1].begin()==path[n-1].end()) cout<<-1<<endl;
    for(auto it=path[n-1].begin(); it!=path[n-1].end(); it++) cout<<*it+1<<" ";
    cout<<endl;
}

The above code thus works perfectly fine. Below is the screenshot of the working code's output:

Here are some of the links provided in the comments that helped:

https://en.cppreference.com/w/cpp/language/ub (undefined behaviour)
https://ideone.com/5NY0q3 (code that proved begin is pointing to end)
https://en.cppreference.com/w/cpp/container/vector/erase (about erase)
https://codeforces.com/contest/20/problem/C (problem statement that the code pertains to)

P.S. The code finds the path through which the shortest distance between vertex 1 and vertex n of a graph with weighted edges can be obtained, in O(n*log(n)).

Thank you.

In c++ code, set.erase(it) is halting execution, where it=set.begin() for a set of pairs, why is this happening?

1 Answers1