时间戳

首页 > 解决方案 > 如何使用迭代器在 C++ 中的递归函数中传递值？

c++ - 如何使用迭代器在 C++ 中的递归函数中传递值？

问题描述

如果我按以下方式运行代码，那么它会因输入而崩溃。但是，如果我不使用迭代器并使用注释部分（DFS()函数中）编写的代码，那么它会运行良好并且不再崩溃。我不明白为什么这段代码会被迭代器崩溃。

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<stack>

using namespace std;

vector<pair<int, int> > graph[30009];
vector<pair<int, int> >:: iterator it;

long long int far;
int  visit[30001], last;

void DFS(int vertex, long long int edge)
{
    if(edge > far){
        far = edge;
        last = vertex;
    }
    /*for(int i = 0; i < graph[vertex].size(); i++){
        int node = graph[vertex][i].first;
        int weight = graph[vertex][i].second;
        if(visit[node] == 0){
        visit[node] = 1;
        DFS(node, edge+weight);
    }
}*/
    for(it = graph[vertex].begin(); it != graph[vertex].end(); it++){
        int node = it->first;
        int weight = it->second;
        if(visit[node] == 0){
            visit[node] = 1;
            DFS(node, edge+weight);
        }
    }

return;

}
int main()
{
    int T, n,u,v,w;
    scanf("%d", &T);
    for(int i = 1; i <= T; i++){
            far = 0;

        memset(visit, 0, sizeof(visit));
        scanf("%d", &n);
        for(int j = 0; j < 30001; j++)
            graph[j].clear();
        for(int j = 1; j < n; j++){
            scanf("%d%d%d", &u, &v, &w);
            graph[u].push_back(make_pair(v,w));
            graph[v].push_back(make_pair(u,w));
        }
        visit[0] = 1;
        DFS(0, 0);

        memset(visit, 0, sizeof(visit));
        visit[last] = 1;
        DFS(last, 0);

        printf("Case %d: %lld\n", i, far);
    }
    return 0;
}

标签： c++recursionvectoriterator

解决方案

问题

it是全局的，所以每次调用DFS都使用相同的it. 所以当你

for(it = graph[vertex].begin(); it != graph[vertex].end(); it++){

it被“指向”不同vector的迭代。当DFS返回时，调用DFS尝试在它停止的地方继续，错误的vectorANDvector已经被迭代到end()。it将增加超出范围，一旦发生这种情况，任何使用都是Undefined Behavior。此外it != graph[vertex].end()，由于它们都指的是不同的 s，因此只能在意外情况下为真vector，因此循环会进一步游荡到未知领域，最终这个错误会在崩溃中显现出来，无论如何，对于询问者来说。

解决方案

消除

vector<pair<int, int> >:: iterator it;

并更换

for(it = graph[vertex].begin(); it != graph[vertex].end(); it++)

和

for(auto it = graph[vertex].begin(); it != graph[vertex].end(); it++)

或者

for(vector<pair<int, int> >::iterator it = graph[vertex].begin(); 
    it != graph[vertex].end(); 
    it++)

取决于目标 C++ 标准。

警告

这只能解决最明显的问题。可能还有其他人。我没有检查。

推荐阅读