C ++ передать по ссылке - PullRequest
5 голосов
/ 28 июня 2010

Я недавно (4 дня) начал изучать C ++, исходя из фона C / Java. Чтобы выучить новый язык, я, как правило, начинаю с переосмысления различных классических алгоритмов, насколько это возможно для конкретного языка.

Я пришел к этому коду, это 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 ++?

ПОСЛЕДНЕЕ РЕДАКТИРОВАНИЕ:

Хорошо, я проанализировал ваши ответы (спасибо всем) и переписал код более ООП. Также я понимаю, что такое ссылка и как ее использовать. Это несколько похоже на указатель 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);
}

Ответы [ 4 ]

8 голосов
/ 28 июня 2010

За 4 дня в C ++ вы отлично справляетесь. Вы уже используете стандартные контейнеры, алгоритмы и пишете свои собственные шаблоны функций. Самая острая нехватка, которую я вижу, относится именно к вашему вопросу: необходимость проходить по ссылке / константной ссылке.

Каждый раз, когда вы передаете / возвращаете объект C ++ по значению, вы вызываете глубокую копию его содержимого. Это совсем не дешево, особенно для чего-то вроде вашего класса матрицы.

Сначала давайте посмотрим на showMatrix. Цель этой функции - вывести содержимое матрицы. Нужна ли копия? Нет. Нужно ли что-то менять в матрице? Нет, его цель - просто показать это. Таким образом, мы хотим передать Матрицу по константной ссылке.

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

[Примечание: я использовал некоторые typedef для облегчения чтения и записи. Я рекомендую это, когда у вас есть много параметров параметризации].

Теперь давайте посмотрим на getMatrixFromFile:

SquareMatrix getMatrixFromFile(string fName);

Возвращение SquareMatrix по значению здесь может быть дорогостоящим (в зависимости от того, применяет ли ваш компилятор оптимизацию возвращаемого значения к этому случаю) и поэтому передает строку по значению. С C ++ 0x у нас есть rvalue ссылки, чтобы сделать это, поэтому нам не нужно возвращать копию (я также изменил строку, передаваемую по ссылке const по тем же причинам, что и showMatrix, нам не нужна копия имя файла):

SquareMatrix&& getMatrixFromFile(const string& fName);

Однако, если у вас нет компилятора с этими функциями, то общий компромисс - передать матрицу по ссылке и позволить функции заполнить ее:

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

Это не дает такой удобный синтаксис для клиента (теперь им приходится писать две строки кода вместо одной), но это последовательно устраняет издержки на глубокое копирование. Существует также MOJO для решения этой проблемы, но он устареет с C ++ 0x.

Простое практическое правило: если у вас есть какой-либо определенный пользователем тип (не простой старый тип данных), и вы хотите передать его в функцию:

  1. передавать по константной ссылке, если функция должна только читать из нее.
  2. передать по ссылке, если функции необходимо изменить оригинал.
  3. передавать по значению , только если функция нуждается в копии для изменения.

Существуют исключения, когда у вас может быть дешевый UDT (определяемый пользователем тип), который дешевле копировать, чем передавать по постоянной ссылке, например, но придерживайтесь этого правила на данный момент, и вы будете в пути на написание безопасного и эффективного кода C ++, который не тратит драгоценные такты на ненужные копии (обычная проблема плохо написанных программ на C ++).

2 голосов
/ 28 июня 2010

Чтобы перейти по ссылке, вы обычно меняете это:

vector<unsigned int> DFS(vector< vector<short> > mat){

до:

vector<unsigned int> DFS(vector<vector<short>> const &mat) { 

Технически, это передает ссылку const, но это то, что вы обычно хотите использовать, когда / если вы не планируете изменять исходный объект.

С другой стороны, я бы, наверное, изменил это:

for_each((*row).begin(), (*row).end(), utilShow<short>);

что-то вроде:

std::copy(row->begin(), row->end(), std::ostream_iterator<short>(std::cout, " "));

Аналогично:

for_each(dfsResult.begin(), dfsResult.end(), utilShow<unsigned int>);

станет:

std::copy(dfsResult.begin(), dfsResult.end(),
          std::ostream_iterator<unsigned int>(std::cout, " "));

(... похоже, это полностью исключит utilShow).

Что касается 2D матриц, если вам не нужна рваная матрица (где разные строки могут иметь разную длину), вы обычно используете простой интерфейс для обработки индексации в одном векторе:

template <class T>
class matrix { 
    std::vector<T> data_;
    size_t columns_;
public:
    matrix(size_t rows, size_t columns) : columns_(columns), data_(rows * columns)  {}

    T &operator()(size_t row, size_t column) { return data[row * columns_ + column]; }
};

Обратите внимание, что для индексации используется operator(), поэтому вместо m[x][y] вы будете использовать m(x,y), примерно как в BASIC или Fortran. Вы можете перегрузить operator[] таким образом, чтобы вы могли использовать эту нотацию, если хотите, но это довольно много дополнительной работы с (IMO) небольшим реальным преимуществом.

1 голос
/ 28 июня 2010

Ссылки и указатели тесно связаны между собой. Оба являются способами передачи параметров без копирования значения параметра в кадр стека подпрограммы.

Основное различие между ними:

  • Указатель p указывает на объект o.
  • Ссылка i является объектом o. Другими словами, в псевдониме.

Чтобы сделать вещи более запутанными, насколько я знаю, реализация компилятора между ними почти одинакова.

Представьте себе функции Ptr(const T* t) и Ref(const T& t).

int main () { int a; Ptr (& а); Ссылка (а); }

В Ptr, t будет указывать на местоположение a. Вы можете разыменовать его и получить значение a. Если вы введете &t (берете адрес t), вы получите адрес параметра.

In Ref, t равно a. Вы можете использовать a для значения a. Вы можете получить адрес a с помощью &a. Это маленький синтаксический сахар, который дает вам c ++.

Оба предоставляют механизм для передачи параметров без копирования. В вашей функции (кстати, вам не нужно объявление):

template <class T> void utilShow(T elem) { ... }

Каждый раз, когда его вызывают, T будет копироваться. Если T большой вектор, он копирует все данные в векторе. Это довольно неэффективно. Вы не хотите передавать весь вектор в новый кадр стека, вы хотите сказать «эй - новый кадр стека, используйте эти данные». Таким образом, вы можете перейти по ссылке. Как это выглядит?

template <class T> void utilShow(const T &elem) { ... }

elem равно const, потому что оно не изменяется функцией. Он также будет использовать память для elem, хранящуюся в вызывающей стороне, вместо того, чтобы копировать ее в стек.

Опять же, по той же причине (чтобы избежать копирования параметров), используйте:

vector< vector<short> > getMatrixFromFile(const string &fName) { ... }
void showMatrix(const vector< vector<short> > &mat) { ... }

Единственная сложность в том, что вы можете подумать: «Эй, ссылка означает отсутствие копий! Я буду использовать ее все время! Я буду возвращать ссылки из функций!» И вот где ваша программа падает.

Представьте себе это:

// Don't do this!
Foo& BrokenReturnRef() {
  Foo f;
  return f;
}

int main() {
  Foo &f = BrokenReturnRef();
  cout << f.bar();
}

К сожалению, это сломано! Когда BrokenReturnRef работает, f находится в области видимости, и все круто. Затем вы возвращаетесь к main и продолжаете ссылаться на f. Фрейм стека, который создал f, исчез, и это местоположение больше недействительно, и вы ссылаетесь на ненужную память. В этом случае у вас будет для возврата по значению (или для выделения нового указателя в куче).

Единственное исключение из правила "не возвращать ссылки" - это когда вы знаете, что память превзойдет стек. Вот как STL реализует operator[] для своих контейнеров.

Надеюсь, это поможет! :)

1 голос
/ 28 июня 2010
void utilShow(T& elem);
vector< vector<short> > getMatrixFromFile(const string& fName);
void showMatrix(vector< vector<short> >& mat);
vector<unsigned int> DFS(vector< vector<short> >& mat);

Некоторые, которые я мог бы выяснить. И если возможно, если вы не изменяете или намереваетесь изменить состояние объекта внутри тела вашего метода, сделайте переменные переданными как const.

Я бы не стал просить вас включать все конструкции C ++ в вашу первую попытку, но постепенно, чтобы вы не перегружали себя депрессией. Вектор - наиболее часто используемый контейнер STL. И использование контейнеров зависит от ваших потребностей, а не от фантазии использовать один над другим.

Одно краткое описание контейнеров. http://msdn.microsoft.com/en-us/library/1fe2x6kt%28VS.80%29.aspx

@ Джерри Спасибо за редактирование. Вектор не используется слишком часто, но используется больше из-за своей простоты для простых объектов, а не для больших объектов монолитного класса. Он напоминает массив в стиле C, но не так, с множеством дополнительных алгоритмов. Еще два, которые используются довольно часто, это карты и списки. Возможно, из-за мест, где я работаю, они нуждаются в использовании этих контейнеров больше, чем в других местах.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...