在 C++ 代码中，set.erase(it) 正在停止执行，其中 it=set.begin() 对于一组对，为什么会这样？

Question

对于给您带来的任何不便，我深表歉意，我是 C++ 的初学者，遇到了一个空集...感谢您提供的有用评论，帮助我找出问题所在

我为一个问题编写了 C++ 代码，其中我需要在 n*log(n) 时间内使用 Dijkstra 的最短路径算法，因此我使用一组对来获取与源顶点距离最短的顶点。该代码在运行时没有给出任何错误，但也没有给出输出。因此，为了查看卡住的位置，我在代码的某些点使用了 cout 语句，并发现代码在擦除语句后立即停止执行。

该语句在代码中用于擦除集合中的第一对，因此指向集合 set.begin() 的迭代器作为参数给出。之前写的是set.erase(iterator)格式，但是在stack overflow上搜索这个问题后发现有人说iterator=set.erase(iterator)会解决问题。我试过了，它仍然卡在那条线上，既没有停止执行也没有返回到终端，也没有给出运行时错误。我不知道这有什么问题，所以我想我会在这里得到一些帮助。

我也提供了我的代码和运行的屏幕截图，非常感谢您的帮助。

#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;
}

运行代码的图片：请注意，突出显示的行是有问题的行 在卡住的代码部分中不存在迭代器操作，之后也没有再次访问迭代器擦除.

它只打印擦除语句之前的行而不打印之后的...

Answer 1

user4581301 在评论中指出的问题是迭代器指向集合的 end()，这意味着集合是空的，因为它被初始化为指向集合的 begin()。因此，一个可引用不足的迭代器被取消引用，导致未定义的行为，（这意味着它可能不一定会给出运行时错误，而是在取消引用时提供输出）。尽管由于这种无效访问，程序因此卡在了这一行。

代码中的错误是集合是全局定义的，但随后在 main 中用相同的名称进行了细化，这意味着当值填充到 main 中的集合中时，它们将填充到定义的集合中主要不是全球定义的。但是在函数dij中访问集合时，访问的是全局集合，实际上是空的！

删除 main 中的重新定义将解决问题。

#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;
}

以上代码因此工作得很好。以下是工作代码输出的屏幕截图：

以下是评论中提供的一些有用链接：

https://en.cppreference.com/w/cpp/language/ub（未定义的行为）
https://ideone.com/5NY0q3（证明begin指向end的代码）
https://en.cppreference.com/w/cpp/container/vector/erase（关于擦除）
https://codeforces.com/contest/20/problem/C（代码所属的问题陈述）

P.S。代码在O(n*log(n)).

中找到了可以得到带权边图的顶点1和顶点n之间最短距离的路径。

谢谢。

在 C++ 代码中，set.erase(it) 正在停止执行，其中 it=set.begin() 对于一组对，为什么会这样？

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

c++

stl

dijkstra

stdset

std-pair