我最近(4 天)开始学习来自 C/Java 背景的 C++。为了学习一门新语言，我通常会从重新实现不同的经典算法开始，尽可能地针对特定语言。

我来到这段代码，它是一个 DFS - 无向图中的深度优先搜索。从我读到的内容来看，最好在 C++ 中通过引用传递参数。不幸的是，我不能完全理解引用的概念。每次我需要引用时，我都会感到困惑，我会根据指针来思考。在我当前的代码中，我使用按值传递。

这是代码(可能不是它应该的 Cppthonic):

#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <stack>
#include <vector>

using namespace std;

template <class T>
void utilShow(T elem);

template <class T>
void utilShow(T elem){
    cout << elem << " ";
}

vector< vector<short> > getMatrixFromFile(string fName);
void showMatrix(vector< vector<short> > mat);
vector<unsigned int> DFS(vector< vector<short> > mat);

/* Reads matrix from file (fName) */
vector< vector<short> > getMatrixFromFile(string fName)
{
    unsigned int mDim;
    ifstream in(fName.c_str());
    in >> mDim;
    vector< vector<short> > mat(mDim, vector<short>(mDim));
    for(int i = 0; i < mDim; ++i) {
        for(int j = 0; j < mDim; ++j) {
            in >> mat[i][j];
        }
    }
    return mat;
}

/* Output matrix to stdout */
void showMatrix(vector< vector<short> > mat){
    vector< vector<short> >::iterator row;
    for(row = mat.begin(); row < mat.end(); ++row){
        for_each((*row).begin(), (*row).end(), utilShow<short>);
        cout << endl;
    }
}

/* DFS */
vector<unsigned int> DFS(vector< vector<short> > mat){
    // Gives the order for DFS when visiting
    stack<unsigned int> nodeStack;
    // Tracks the visited nodes
    vector<bool> visited(mat.size(), false);
    vector<unsigned int> result;
    nodeStack.push(0);
    visited[0] = true;
    while(!nodeStack.empty()) {
        unsigned int cIdx = nodeStack.top();
        nodeStack.pop();
        result.push_back(cIdx);
        for(int i = 0; i < mat.size(); ++i) {
            if(1 == mat[cIdx][i] && !visited[i]) {
                nodeStack.push(i);
                visited[i] = true;
            }
        }
    }
    return result;
}

int main()
{
    vector< vector<short> > mat;
    mat = getMatrixFromFile("Ex04.in");
    vector<unsigned int> dfsResult = DFS(mat);

    cout << "Adjancency Matrix: " << endl;
    showMatrix(mat);

    cout << endl << "DFS: " << endl;
    for_each(dfsResult.begin(), dfsResult.end(), utilShow<unsigned int>);

    return (0);
}

您能否通过引用这段代码给我一些关于如何使用引用的提示？

我当前的编程风格是否与 C++ 的结构兼容？

对于 C++ 中的二维数组，是否有一个标准的替代 vector 和类型**？

后期编辑:

好的，我已经分析了您的答案(谢谢大家)，并且以更面向对象的方式重写了代码。我也了解什么是引用并打算使用它。它有点类似于 const 指针，除了该类型的指针可以保存 NULL。

这是我最新的代码:

#include <algorithm>
#include <fstream>
#include <iostream>
#include <ostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

template <class T> void showUtil(T elem);

/**
* Wrapper around a graph
**/
template <class T>
class SGraph
{
private:
    size_t nodes;
    vector<T> pmatrix;
public:
    SGraph(): nodes(0), pmatrix(0) { }
    SGraph(size_t nodes): nodes(nodes), pmatrix(nodes * nodes) { }
    // Initialize graph from file name
    SGraph(string &file_name);
    void resize(size_t new_size);
    void print();
    void DFS(vector<size_t> &results, size_t start_node);
    // Used to retrieve indexes.
    T & operator()(size_t row, size_t col) {
        return pmatrix[row * nodes + col];
    }
};

template <class T>
SGraph<T>::SGraph(string &file_name)
{
    ifstream in(file_name.c_str());
    in >> nodes;
    pmatrix = vector<T>(nodes * nodes);
    for(int i = 0; i < nodes; ++i) {
        for(int j = 0; j < nodes; ++j) {
            in >> pmatrix[i*nodes+j];
        }
    }
}

template <class T>
void SGraph<T>::resize(size_t new_size)
{
    this->pmatrix.resize(new_size * new_size);
}

template <class T>
void SGraph<T>::print()
{
    for(int i = 0; i < nodes; ++i){
        cout << pmatrix[i];
        if(i % nodes == 0){
            cout << endl;
        }
    }
}

template <class T>
void SGraph<T>::DFS(vector<size_t> &results, size_t start_node)
{
    stack<size_t> nodeStack;
    vector<bool> visited(nodes * nodes, 0);
    nodeStack.push(start_node);
    visited[start_node] = true;
    while(!nodeStack.empty()){
        size_t cIdx = nodeStack.top();
        nodeStack.pop();
        results.push_back(cIdx);
        for(int i = 0; i < nodes; ++i){
            if(pmatrix[nodes*cIdx + i] && !visited[i]){
                nodeStack.push(i);
                visited[i] = 1;
            }
        }
    }
}

template <class T>
void showUtil(T elem){
    cout << elem << " ";
}

int main(int argc, char *argv[])
{
    string file_name = "Ex04.in";
    vector<size_t> dfs_results;

    SGraph<short> g(file_name);
    g.DFS(dfs_results, 0);

    for_each(dfs_results.begin(), dfs_results.end(), showUtil<size_t>);

    return (0);
}

最佳答案

在 C++ 的 4 天里，您做得很好。您已经在使用标准容器、算法并编写自己的函数模板。我看到的最缺乏的东西正是关于你的问题:需要通过引用/const 引用传递。

任何时候按值传递/返回 C++ 对象，都在调用其内容的深层拷贝。这一点都不便宜，尤其是对于像矩阵类这样的东西。

首先让我们看看 showMatrix。这个函数的目的是输出一个矩阵的内容。它需要拷贝吗？不，它需要改变矩阵中的任何东西吗？不，它的目的只是为了展示它。因此我们想通过 const 引用传递 Matrix。

typedef vector<short> Row;
typedef vector<Row> SquareMatrix;
void showMatrix(const SquareMatrix& mat);

[注意:我使用了一些 typedef 来使它更易于阅读和编写。当你有很多模板参数化时，我推荐它]。

现在让我们看看 getMatrixFromFile:

SquareMatrix getMatrixFromFile(string fName);

此处按值返回 SquareMatrix 可能代价高昂(取决于您的编译器是否对这种情况应用返回值优化)，按值传递字符串也是如此。使用 C++0x，我们有右值引用来创建它，因此我们不必返回拷贝(出于与 showMatrix 相同的原因，我还修改了要通过 const 引用传入的字符串，我们不需要拷贝文件名):

SquareMatrix&& getMatrixFromFile(const string& fName);

但是，如果您没有具有这些功能的编译器，那么一个常见的折衷方案是通过引用传入矩阵并让函数填充它:

void getMatrixFromFile(const string& fName, SquareMatrix& out_matrix);

这并没有为客户端提供方便的语法(现在他们必须编写两行代码而不是一行)，但它始终如一地避免了深度复制开销。还有MOJO来解决这个问题，但这将在 C++0x 中过时。

一个简单的经验法则:如果你有任何用户定义的类型(不是普通的旧数据类型)并且你想将它传递给函数:

1. 如果函数只需要从中读取，则传递 const 引用。
2. 如果函数需要修改原件，则按引用传递。
3. 仅当函数需要一个拷贝进行修改时才按值传递。

有一些异常(exception)情况，例如，您可能拥有廉价的 UDT(用户定义类型)，它的复制成本低于通过 const 引用传递的成本，但是现在坚持这条规则，您将继续前进编写安全、高效的 C++ 代码，不会在不必要的拷贝上浪费宝贵的时钟周期(编写糟糕的 C++ 程序的常见祸根)。

关于C++ 通过引用传递，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3133909/