C ++ Pass по ссылке

StackOverflow https://stackoverflow.com/questions/3133909

Вопрос

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

Я пришел к этому коду, его DF - глубин первый поиск в неориентированном графике. Тем не менее, от того, что я прочитал, лучше пропускать параметры по ссылкам в 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, кроме того, что указатель этого типа может удерживать нуль.

Это мой последний код:

#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 дня в C ++ вы делаете отличную работу. Вы уже используете стандартные контейнеры, алгоритмы и написание собственных шаблонов функций. Самое всего не хватает того, что я вижу, именно со ссылкой на ваш вопрос: необходимость пройти через ссылку / Const.

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

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

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

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

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

SquareMatrix getMatrixFromFile(string fName);

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

SquareMatrix&& getMatrixFromFile(const string& fName);

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

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

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

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

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

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

Другие советы

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

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 Matrices Go, если вам не нужна рваная матрица (где разные строки могут быть разными длинами), вы обычно используете простой интерфейс для обработки индексации в одном векторе:

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), как в базовом или фортране. Вы можете перегружать operator[] Таким образом, что позволяет вам использовать это обозначение, если вы предпочитаете, но это простое количество дополнительной работы с (IMO) мало реальной выгоды.

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

Основное отличие между ними:

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

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

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

int main () {int a; Ptr (& a); Ref (а); }

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

В 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[] для ее контейнеров.

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

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, но не с большим количеством дополнительных алгоритмов. Еще два, которые используются довольно часто, являются карты и списки. Это может быть так из-за мест, где я работаю, им нужна использование этих контейнеров больше, чем в других местах.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top