C++ 中的& 运算符及其如何影响代码性能

Question

这两个函数完全相同，唯一的区别是 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; 
    } 
};

唯一的区别是：

for(vector<int>& edge : edges)

与

for(vector<int> edge : edges)

Answer 1

for(vector<int> edge : edges)

会复制！每个边向量都需要时间。

for(vector<int>& edge : edges)

创建对给定向量的引用，无需任何复制操作。

很明显，向量的完整副本总是会更慢。

顺便说一句：在第一个视图中，您可以将一些变量定义为

const

，这可能会带来更好的优化。有时，编译器“看到”您没有修改变量并进行优化，就好像该变量已经定义为 const 一样。