c++ - 是什么导致了我的代码中的堆损坏和无关值？

Question

我正在为我类的一个项目编写代码，它产生了非常不寻常的结果。行和列值以数百万的随机数结尾，它最终会抛出异常，我不明白为什么。

#include <iostream>
using namespace std;

class SparseRow {
protected:
    int row;
    int col;
    int value;
public:
    SparseRow();
    SparseRow(int inRow, int inCol, int inVal);
    SparseRow(const SparseRow& newRow);
    SparseRow& operator=(const SparseRow& newRow);
    ~SparseRow();
    void display();
    int getRow();
    int getCol();
    int getValue();
    void setRow(int inRow);
    void setCol(int inCol);
    void setValue(int inVal);
};

class SparseMatrix {
protected:
    int noRows;
    int noCols;
    int commonValue;
    int noSparseValues;
    SparseRow *myMatrix;
    void setNoSparseValues(int noSV);
public:
    SparseMatrix();
    SparseMatrix(int rows, int cols, int cv, int noSV);
    SparseMatrix(const SparseMatrix& matrix);
    SparseMatrix& operator=(const SparseMatrix& matrix);
    ~SparseMatrix();
    void readMatrix();
    SparseMatrix* transpose();
    SparseMatrix* multiply(SparseMatrix& M);
    SparseMatrix* add(SparseMatrix& M);
    void display();
    void displayMatrix();
    int getNoRows();
    int getNoCols();
    int getCommonValue();
    int getNoSparseValues();
    int getValue(int row, int col);
    void setValue(int row, int col, int val);
};

SparseRow::SparseRow() {
    row = -1;
    col = -1;
    value = 0;
}

SparseRow::SparseRow(int inRow, int inCol, int inVal) {
    row = inRow;
    col = inCol;
    value = inVal;
}

SparseRow::SparseRow(const SparseRow& newRow) {
    row = newRow.row;
    col = newRow.col;
    value = newRow.value;
}

SparseRow& SparseRow::operator=(const SparseRow& newRow) {
    if (this != &newRow) {
        row = newRow.row;
        col = newRow.col;
        value = newRow.value;
    }
    return *this;
}

SparseRow::~SparseRow() {
    cout << "Deleting SparseRow with values: " << endl;
    display();
}

void SparseRow::display() {
    cout << "Row: " << row << ", Column: " << col << ", Value: " << value << endl;

}

int SparseRow::getRow() {
    return row;
}

int SparseRow::getCol() {
    return col;
}

int SparseRow::getValue() {
    return value;
}

void SparseRow::setRow(int inRow) {
    row = inRow;
}

void SparseRow::setCol(int inCol) {
    col = inCol;
}

void SparseRow::setValue(int inVal) {
    value = inVal;
}

SparseMatrix::SparseMatrix() {
    noRows = 0;
    noCols = 0;
    commonValue = 0;
    noSparseValues = 0;
}

SparseMatrix::SparseMatrix(int rows, int cols, int cv, int noSV) {
    noRows = rows;
    noCols = cols;
    commonValue = cv;
    noSparseValues = noSV;
    myMatrix = new SparseRow[rows * cols];
}

SparseMatrix::SparseMatrix(const SparseMatrix& matrix) {
    noRows = matrix.noRows;
    noCols = matrix.noCols;
    commonValue = matrix.commonValue;
    noSparseValues = matrix.noSparseValues;
    myMatrix = matrix.myMatrix;
}

SparseMatrix& SparseMatrix::operator=(const SparseMatrix& matrix) {
    if (this != &matrix) {
        delete[] myMatrix;

        noRows = matrix.noRows;
        noCols = matrix.noCols;
        commonValue = matrix.commonValue;
        noSparseValues = matrix.noSparseValues;
        myMatrix = matrix.myMatrix;
    }
    return *this;
}

SparseMatrix::~SparseMatrix() {
    cout << "Deleting SparseMatrix with values: " << endl;
    display();

    delete[] myMatrix;
}

void SparseMatrix::readMatrix() {
    int count = 0;
    int val;

    for (int i = 0; i < noRows; i++) {
        for (int j = 0; j < noCols; j++) {
            cin >> val;
            if (val != commonValue) {
                myMatrix[count].setRow(i);
                myMatrix[count].setCol(j);
                myMatrix[count].setValue(val);
                // Why does C++ prevent me from calling a constructor on objects in an array? It doesn't make sense.
                count++;
            }
        }
    }

    if (count != noSparseValues) {
        cout << "ERROR: Incorrect number of sparse values! Changing to correct number." << endl;
        noSparseValues = count;
    }
}

SparseMatrix* SparseMatrix::transpose() {
    SparseMatrix *newMatrix = new SparseMatrix(noCols, noRows, commonValue, noSparseValues);

    for (int i = 0; i < noSparseValues; i++) {
        newMatrix->setValue(myMatrix[i].getCol(), myMatrix[i].getRow(), myMatrix[i].getValue());
    }

    return newMatrix;
}

SparseMatrix* SparseMatrix::multiply(SparseMatrix& M) {
    if (noCols != M.getNoRows()) {
        cout << "ERROR: Matrices cannot be multiplied!" << endl;
        return NULL;
    }

    SparseMatrix *newMatrix = new SparseMatrix(noRows, M.getNoCols(), commonValue, noRows * M.getNoCols());
    // Why does C++ prevent me from creating an array to store this information? It doesn't make sense.

    int SVCount = 0;
    for (int i = 0; i < noRows; i++) {
        for (int j = 0; j < M.getNoCols(); j++) {
            int sum = 0;
            for (int k = 0; k < noCols; k++) {
                sum += getValue(i, k) * M.getValue(k, j);
            }
            if (sum != newMatrix->getCommonValue()) {
                SVCount++;
            }
            newMatrix->setValue(i, j, sum);
        }
    }
    newMatrix->setNoSparseValues(SVCount);

    return newMatrix;
}

SparseMatrix* SparseMatrix::add(SparseMatrix& M) {
    if (noRows != M.getNoRows() || noCols != M.getNoCols()) {
        cout << "ERROR: Matrices cannot be added!" << endl;
        return NULL;
    }

    SparseMatrix *newMatrix = new SparseMatrix(noRows, noCols, commonValue + M.getCommonValue(), noRows * noCols);

    int SVCount = 0;
    for (int i = 0; i < noRows; i++) {
        for (int j = 0; j < noCols; j++) {
            int sum = getValue(i, j) + M.getValue(i, j);
            if (sum != newMatrix->getCommonValue()) {
                SVCount++;
            }
            newMatrix->setValue(i, j, sum);
        }
    }

    newMatrix->setNoSparseValues(SVCount);

    return newMatrix;
}

void SparseMatrix::display() {
    for (int i = 0; i < noSparseValues; i++) {
        myMatrix[i].display();
    }
}

void SparseMatrix::displayMatrix() {
    for (int i = 0; i < noRows; i++) {
        for (int j = 0; j < noCols; j++) {
            cout << getValue(i, j) << " ";
        }
        cout << endl;
    }
}

int SparseMatrix::getNoRows() {
    return noRows;
}

int SparseMatrix::getNoCols() {
    return noCols;
}

int SparseMatrix::getCommonValue() {
    return commonValue;
}

int SparseMatrix::getNoSparseValues() {
    return noSparseValues;
}

void SparseMatrix::setNoSparseValues(int noSV) {
    noSparseValues = noSV;
}

int SparseMatrix::getValue(int row, int col) {
    for (int i = 0; i < noSparseValues; i++) {
        if (myMatrix[i].getRow() == row && myMatrix[i].getCol() == col) {
            return myMatrix[i].getValue();
        }
    }
    return commonValue;
}

void SparseMatrix::setValue(int row, int col, int val) {
    bool replacingSparse = (getValue(row, col) != commonValue);
    bool replacingWithSparse = (val != commonValue);

    int index = -1;

    if (replacingSparse) {
        for (int i = 0; i < noSparseValues; i++) {
            if (myMatrix[i].getRow() == row && myMatrix[i].getCol() == col) {
                index = i;
                break;
            }
        }
        if (replacingWithSparse) {
            myMatrix[index].setValue(val);
        }
        else {
            for (int i = index; i < noSparseValues; i++) {
                myMatrix[i] = myMatrix[i + 1];
            }
            noSparseValues--;
        }
    }
    else {
        if (replacingWithSparse) {
            for (int i = 0; i < noSparseValues; i++) {
                if (myMatrix[i].getRow() > row || (myMatrix[i].getRow() >= row && myMatrix[i].getCol() > col)) {
                    index = i;
                    break;
                }
            }
            for (int i = noSparseValues; i > index; i--) {
                myMatrix[i] = myMatrix[i - 1];
            }
            myMatrix[index].setRow(row);
            myMatrix[index].setCol(col);
            myMatrix[index].setValue(val);
            noSparseValues++;
        }
    }
}

int main() {
    int n, m, cv, noNSV;
    SparseMatrix* temp;

    cin >> n >> m >> cv >> noNSV;
    SparseMatrix* firstOne = new SparseMatrix(n, m, cv, noNSV);
    firstOne->readMatrix();

    cin >> n >> m >> cv >> noNSV;
    SparseMatrix* secondOne = new SparseMatrix(n, m, cv, noNSV);
    secondOne->readMatrix();

    cout << "First one in sparse matrix format" << endl;
    firstOne->display();

    cout << "First one in normal matrix format" << endl;
    firstOne->displayMatrix();

    cout << "Second one in sparse matrix format" << endl;
    secondOne->display();

    cout << "Second one in normal matrix format" << endl;
    secondOne->displayMatrix();

    cout << "After Transpose first one in normal format" << endl;
    temp = firstOne->transpose();
    temp->displayMatrix();

    cout << "After Transpose second one in normal format" << endl;
    temp = secondOne->transpose();
    temp->displayMatrix();

    cout << "Multiplication of matrices in sparse matrix form:" << endl;
    temp = secondOne->multiply(*firstOne);
    temp->display();

    cout << "Addition of matrices in sparse matrix form:" << endl;
    temp = secondOne->add(*firstOne);
    temp->display();
}

输入:

3 3 0 3
2 2 2
0 0 0
0 0 0

3 3 0 3
2 2 2
0 0 0
0 0 0

预期输出:(格式不完全相同，但数字应该相同)

First one in sparse matrix format
0, 0, 2
0, 1, 2
0, 2, 2
First one in normal matrix format
2     2     2
0     0     0
0     0     0
Second one in sparse matrix format
0, 0, 2
0, 1, 2
0, 2, 2
Second one in normal matrix format
2     2     2
0     0     0
0     0     0
After Transpose first one
2     0     0
2     0     0
2     0     0
After Transpose second one
2     0     0
2     0     0
2     0     0
Multiplication of matrices in sparse matrix form:
0, 0, 4
0, 1, 4
0, 2, 4
Addition of matrices in sparse matrix form:
0, 0, 4
0, 1, 4
0, 2, 4

实际输出:

First one in sparse matrix format
Row: 0, Column: 0, Value: 2
Row: 0, Column: 1, Value: 2
Row: 0, Column: 2, Value: 2
First one in normal matrix format
2 2 2
0 0 0
0 0 0
Second one in sparse matrix format
Row: 0, Column: 0, Value: 2
Row: 0, Column: 1, Value: 2
Row: 0, Column: 2, Value: 2
Second one in normal matrix format
2 2 2
0 0 0
0 0 0
After Transpose first one in normal format
0 0 0
2 0 0
2 0 0
After Transpose second one in normal format
0 0 0
2 0 0
2 0 0
Multiplication of matrices in sparse matrix form:
Row: 0, Column: 1, Value: 4
Row: 0, Column: 2, Value: 4
Row: 369, Column: -33686019, Value: 9
Addition of matrices in sparse matrix form:
(Exceptions thrown here, line 222 in code)

抛出的异常:

Project1.exe has triggered a breakpoint.

Unhandled exception at 0x777E8499 (ntdll.dll) in Project1.exe: 0xC0000374: A heap has been corrupted (parameters: 0x77825890).

Answer 1

我只会解决已发布代码中的部分问题。

指针

他们的明确使用总是容易出错，并且在标准的每个新版本中都越来越不鼓励使用。在 OP 的代码中，他们拥有管理内存资源的责任，但在 C++ 中，当对象超出范围时，他们不会自动调用对象的析构函数。这就是像 std::unique_ptr 这样的智能指针可以做到。

让我们看看 main 中发生了什么:

int n, m, cv, noNSV;
SparseMatrix* temp;  // <- Declaration far from initialization

cin >> n >> m >> cv >> noNSV;
SparseMatrix* firstOne = new SparseMatrix(n, m, cv, noNSV);
//          ^^^^^^^^^^^^^^^^ Why?    
// ...
temp = firstOne->transpose();  // <- Here the pointer is initialized
// ...
temp = secondOne->transpose(); // <- Here the pointer is overwritten, but the allocated memory
                               //    isn't released, it leaks.
// ...
temp = secondOne->multiply(*firstOne); // <- Again...
// ...
temp = secondOne->add(*firstOne);  // <- ...and again
// ...
// No 'delete' calls at the end, so no destructor is called for the previously allocated objects 

这里使用指针的唯一原因是 SparseMatrix::transpose() 旨在返回一个，但它可以轻松地重新运行 SparseMatrix(返回值优化将避免不必要的拷贝)。

对于 new 的每次调用都应该对应一个 delete 并且由于像 transpose 这样的函数返回一个指向新分配的对象的指针， delete temp; 应该在覆盖 temp 之前调用，以确保调用正确的析构函数。

不过，在 C++ 中，我们应该利用 RAII (Resource Acquisition Is Initialization，也叫Scope-Bound Resource Management):

{   // <- Start of a scope
    int n, m, cv, noNSV;

    std::cin >> n >> m >> cv >> noNSV;
    // Declare a variable using the constructor. Its lifetime begins here.     
    SparseMatrix firstOne(n, m, cv, noNSV);
    // The same for 'secondOne'
    // ...
    // SparseSparse::transpose() here should return a SparseMatrix, not a pointer
    SparseMatrix temp = firstOne.transpose(); 

    // ...
    // Here the matrix is reassigned (which can be cheap if move semantic is implemented) 
    temp = secondOne.transpose();
    // ...
    temp = secondOne.multiply(firstOne); // <- Again...
    // ...
 }  // <- End of scope, all the destructors are called. No leaks. 

特殊成员函数

这实际上与前一点有关，看看如何复制赋值运算符在发布的代码片段中实现:

 SparseMatrix& SparseMatrix::operator=(const SparseMatrix& matrix) {
     if (this != &matrix) {     // <- debatable, see copy-and-swap idiom
         delete[] myMatrix;     // <- putted here makes this function not exception safe ^^

         noRows = matrix.noRows;
         noCols = matrix.noCols;
         commonValue = matrix.commonValue;
         noSparseValues = matrix.noSparseValues;
         myMatrix = matrix.myMatrix; // <- The pointer is overwritten, but this is shallow copy
                                     //    what you need is a deep copy of the array
     }
     return *this;
 }

此函数和其他特殊函数的正确实现将利用 copy-and-swap 惯用语，此处对其进行了巧妙的描述:

What is the copy-and-swap idiom?

此外，关于 OP 阅读功能中的评论:

for (int i = 0; i < noRows; i++) {
    for (int j = 0; j < noCols; j++) {
        cin >> val;
        if (val != commonValue) {
            myMatrix[count].setRow(i);
            myMatrix[count].setCol(j);
            myMatrix[count].setValue(val);
            // Why does C++ prevent me from calling a constructor on objects in an array? It doesn't make sense.
            count++;
        }
    }
}

提问者可以使用 new 的放置参数(放置新)，那里:

for (int i = 0; i < noRows; i++) {
    for (int j = 0; j < noCols; j++) {
        cin >> val;
        if (val != commonValue) {

            new (myMatrix + count) SparseRow(i, j, val);

            count++;
        }
    }
}

许多其他问题留给 OP 解决。