C++中&运算符对代码性能的影响：为何循环拷贝触发超时？

下面两个用于验证图中路径是否存在的C++函数几乎完全一致，仅范围for循环的遍历对象声明方式不同，为何第二个函数会触发Time Limit Exceeded（超时）错误？

解决方案1（正常运行） #

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {    
    vector<bool> visited(n, false);
    queue<int> queue; 
    queue.push(source);
    visited[source] = true; 

    while(queue.size() > 0) {
        int currentVertex = queue.front();
        if(currentVertex == destination) return true; 
        queue.pop();
        for(vector<int>& edge : edges) {
            if(currentVertex == edge[0] && !visited[edge[1]]) {
                visited[edge[1]] = true; 
                queue.push(edge[1]);
                
            } else if(currentVertex == edge[1] && !visited[edge[0]]) {
                visited[edge[0]] = true; 
                queue.push(edge[0]);
            }
        }
    }
    return false; 
} 

解决方案2（超时） #

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {    
    vector<bool> visited(n, false);
    queue<int> queue; 
    queue.push(source);
    visited[source] = true; 

    while(queue.size() > 0) {
        int currentVertex = queue.front();
        if(currentVertex == destination) return true; 
        queue.pop();
        for(vector<int> edge : edges) {
            if(currentVertex == edge[0] && !visited[edge[1]]) {
                visited[edge[1]] = true; 
                queue.push(edge[1]);
                
            } else if(currentVertex == edge[1] && !visited[edge[0]]) {
                visited[edge[0]] = true; 
                queue.push(edge[0]);
            }
        }
    }
    return false; 
} 

两者唯一区别 #

• 方案1的循环语句：for(vector<int>& edge : edges)
• 方案2的循环语句：for(vector<int> edge : edges)

原因分析 #

核心差异在于遍历是否使用引用类型：

• 方案1中vector<int>& edge是原元素的引用，遍历edges时直接访问容器内的原始数据，没有任何拷贝开销。
• 方案2中vector<int> edge是值拷贝，遍历每一条边时，都会把edges里的对应vector<int>完整复制一份。

当测试用例的边集规模较大时（比如数万条边），这种拷贝会带来指数级的性能损耗：

1. 每次拷贝vector<int>都需要分配内存、复制元素，单条边的拷贝成本虽小，但乘以边的总数和BFS遍历的节点数后，总开销会急剧上升。
2. 频繁的内存分配与释放还会触发系统内存管理的额外开销，进一步拖慢程序运行速度。

原本BFS的时间复杂度是O(N+M)（N为边数，M为节点数），方案2因为额外的拷贝操作，时间复杂度会飙升至O(N*K + M)（K为单条边的拷贝成本），直接超出题目时间限制。

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