为何vector<vector<int>>比vector<int>[]更慢？LeetCode323实践疑问

我在解决LeetCode 323题时，代码思路和官方题解基本一致，唯一区别是我用vector<vector<int>>存储节点邻接表，而官方题解用的是vector<int>[]。我想知道vector<int>[]相对vector<vector<int>>有哪些优势？

我的代码 #

class Solution {
    public :
    void explore(vector<bool> & visited,vector<int> nei[],int cur){
        visited[cur]=true;
        for(int i=0;i<nei[cur].size();i++){
            if(!visited[nei[cur][i]]){
                explore(visited,nei,nei[cur][i]);
            }
        }
    }
    
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<bool> visited(n);
       vector<vector<int>> neighbors(n);
        int count=0;
        for(int i=0;i<edges.size();i++){
            neighbors[edges[i][0]].push_back(edges[i][1]);
             neighbors[edges[i][1]].push_back(edges[i][0]);
        }
        for(int j=0;j<n;j++){
            if(!visited[j]){
                count++;
                explore(visited,neighbors,j);
            }
        }
        return count;

    }
};

官方题解代码 #

class Solution { 
public: void dfs(vector<int> adjList[], vector<int> &visited, int src) { 
visited[src] = 1;    

for (int i = 0; i < adjList[src].size(); i++) {
        if (visited[adjList[src][i]] == 0) {
            dfs(adjList, visited, adjList[src][i]);
        }
    }
}

int countComponents(int n, vector<vector<int>>& edges) {
    if (n == 0) return 0;
  
    int components = 0;
    vector<int> visited(n, 0);
    vector<int> adjList[n];

    for (int i = 0; i < edges.size(); i++) {
        adjList[edges[i][0]].push_back(edges[i][1]);
        adjList[edges[i][1]].push_back(edges[i][0]);
    }
    
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
            components++;
            dfs(adjList, visited, i);
        }
    }
    return components;
}
};

vector<int>[]相对vector<vector<int>>的优势 #

• 内存访问效率更高：vector<int>[]是固定大小的指针数组，内存上连续分布，每个指针指向对应的vector<int>数据区。而vector<vector<int>>是嵌套容器，内部每个vector的内存是动态分配的，容易产生内存碎片化。遍历邻接表时，连续的指针数组更易被CPU缓存命中，访问速度更快。
• 写法更贴近经典数据结构模型：邻接表的经典实现是“数组+链表”，vector<int> adjList[n]的写法直接对应这个模型，阅读代码时更直观，一眼就能明确这是n个节点的邻接表。而vector<vector<int>>是容器嵌套，需要多一层理解成本。
• 函数传参更简洁：将邻接表传给DFS/BFS函数时，vector<int> nei[]的参数写法更简洁，本质是传递数组指针；而vector<vector<int>>&虽然也是引用传递，但语法上多了容器嵌套的层级，对习惯C风格数组的开发者来说，数组形式更符合直觉。

需要注意的是，vector<int> adjList[n]属于变长数组（VLA），这是C99的特性，并非标准C语法（仅部分编译器如GCC支持作为扩展）。而vector<vector<int>>是标准C写法，兼容性更强。但LeetCode的OJ环境支持VLA，所以可以正常运行。

内容的提问来源于stack exchange，提问作者Si Thu