关于 vector 指针式&下标式遍历

学术版

云浅知处 @ 2020-10-25 18:43:20

比如我们要对一棵有根树进行 \texttt{DFS},使用邻接表 vector 存储树,像这样:

vector<int>v[100005];//存树
int d[100005];//深度
void DFS(int u,int fa,int dep){
    d[u]=dep;
    for(int i=0,s=v[u].size();i<s;i++){
        if(v[u][i]==fa)continue;
        DFS(v[u][i],u,dep+1);
    }
}

那么,5-8 行应该可以换成:

if(!v[u].empty()){
    for(vector<int>::iterator it=v[u].begin();it!=v[u].end();it++){
        if(*it==fa)continue;
        DFS(*it,u,dep+1);
    }
}

请问这两种哪个快啊QAQ


by Ryo_Yamada @ 2020-10-25 18:46:28

萌新觉得下面的快(


by BeyondHeaven @ 2020-10-25 18:50:28

你都用vector了还关心常数 卡常建议数组模拟链表


by Ryo_Yamada @ 2020-10-25 18:57:09

你都用 vector 了还关心常数


by Ryo_Yamada @ 2020-10-25 18:57:41

不过 srz 的 vector 跑的飞快,不知道怎么回事


by Lice @ 2020-10-25 18:57:58

快不快不清楚,只是觉得迭代器比较自然。。?

但是如果带边权之类的话并且你这样写:

vector<int> G[N];
vector<int> W[N];

迭代器就不得不搞两个,下标就只要一个 i。

不过如果你写 vector<pair<int, int> >vector<Edge> 就无所谓


|