我写了一个程序，对图的两个实现，邻接列表和邻接矩阵进行深度优先搜索。然而，我的程序总是以以下行崩溃：
HPCHW2（1532,0x7fff727c6310）malloc:***对象0x1002000c8的错误：释放的对象的校验和不正确-对象可能在释放后被修改。
这两个十六进制数字在不同的运行中是相同的。然而，这种崩溃发生在不同运行的不同行，并且我自己在这个程序中没有分配任何堆内存。该程序总是使其通过main中的第一个外部for循环，但随后在第二次迭代中在AdjacencyMatrixGraph代码中的某个地方崩溃。大多数崩溃都发生在方法connected中，但发生在不同的行和不同的变量上，有时在推进stack时崩溃，有时在定义变量discovered时崩溃。该程序在AdjacencyMatrixGraph的构造函数中也崩溃过一次。
如果我自己没有分配内存，是什么原因导致了这个错误？我假设任何后台分配通常都不应该修改释放的内存。此外，我将如何调试此错误？
这是C++11，我在Mac OS Mavericks上。
这是我的代码供参考：
相邻列表.cpp
#include "AdjacencyListGraph.h"
#include <cstdlib>
using std::list;
AdjacencyListGraph::AdjacencyListGraph(int size) :
adjacencyList(vector<vector<int>>(size)),
_size(size) {
}
void AdjacencyListGraph::addEdge(int begin, int end) {
adjacencyList[begin].push_back(end);
adjacencyList[end].push_back(begin);
}
int AdjacencyListGraph::size() {
return _size;
}
bool AdjacencyListGraph::connected(int begin, int end) {
// stack to track vertices to process
list<int> stack = list<int>();
stack.push_front(begin);
// value of discovered[i] is whether vertex i has been discovered
vector<bool> discovered = vector<bool>(size(), false);
while (!stack.empty()) {
// process top vertex
int curr = stack.front();
stack.pop_front();
if (!discovered[curr]) {
discovered[curr] = true;
vector<int>& neighbors = adjacencyList[curr];
// examine neighbors
for (size_t i = 0; i < neighbors.size(); ++i) {
int neighbor = neighbors[i];
// done
if (neighbor == end) {
return true;
}
// else process later
stack.push_front(neighbor);
}
}
}
return false;
}
相邻矩阵图形.cpp
#include "AdjacencyMatrixGraph.h"
using std::list;
AdjacencyMatrixGraph::AdjacencyMatrixGraph(int size) :
adjacencyMatrix(vector<bool>(size * size, false)),
_size(size) {
// has crashed here once
}
void AdjacencyMatrixGraph::addEdge(int begin, int end) {
if (begin == end) {
return;
}
adjacencyMatrix[begin * size() + end] = true;
adjacencyMatrix[end * size() + begin] = true;
}
int AdjacencyMatrixGraph::size() {
return _size;
}
bool AdjacencyMatrixGraph::connected(int begin, int end) {
// stack to track vertices to process
list<int> stack = list<int>();
stack.push_front(begin); // sometimes crashes here
// value of discovered[i] is whether vertex i has been discovered
vector<bool> discovered = vector<bool>(size(), false); // sometimes crashes here
while (!stack.empty()) {
// process top vertex
int curr = stack.front();
stack.pop_front();
if (!discovered[curr]) {
discovered[curr] = true;
// examine neighbors
for (int i = 0; i < size(); ++i) {
// no edge between curr and i
if (!adjacencyMatrix[curr * size() + i]) {
continue;
}
// done
if (i == end) {
return true;
}
// else process later
stack.push_front(i); // sometimes crashes here
}
}
}
return false;
}
main.cpp
#include <cstdio>
#include <vector>
#include <set>
#include <chrono>
#include <random>
#include <algorithm>
#include "AdjacencyListGraph.h"
#include "AdjacencyMatrixGraph.h"
using std::vector;
using std::set;
using std::chrono::high_resolution_clock;
using std::chrono::duration;
using std::chrono::duration_cast;
using std::mt19937;
void clearCache() {
const vector<int> intsToSum = vector<int>(1e9, 1);
volatile long long sum = 0;
for (size_t i = 0; i < intsToSum.size(); ++i) {
sum += intsToSum[i];
}
}
bool randomBool() {
const double seed = high_resolution_clock::now().time_since_epoch().count();
mt19937 mt_rand(seed);
return bool(mt_rand() % 2);
}
vector<bool> randomAdjacencyMatrix(int size) {
vector<bool> adjacencyMatrix = vector<bool>(size);
for (int i = 0; i < size * size; ++i) {
adjacencyMatrix[i] = randomBool();
}
return adjacencyMatrix;
}
int main() {
const vector<int> sizes = {20, 50, 100, 200};
const int numRepeats = 1;
for (int i = 0; i < sizes.size(); ++i) {
int size = sizes[i];
printf("size: %dn", size);
/* Initialize function-wide variables */
vector<bool> adjacencyMatrix = randomAdjacencyMatrix(size);
high_resolution_clock::time_point start;
high_resolution_clock::time_point stop;
/* Initialize adjacency matrix */
AdjacencyMatrixGraph adjacencyMatrixGraph = AdjacencyMatrixGraph(size);
for (int row = 0; row < size; ++row) {
for (int col = 0; col < size; ++col) {
if (adjacencyMatrix[row * size + col]) {
adjacencyMatrixGraph.addEdge(row, col);
}
}
}
/* Time 1 */
double time1Elapsed = 0;
volatile int count = 0;
for (int j = 0; j < numRepeats; ++j) {
clearCache();
start = high_resolution_clock::now();
for (int begin = 0; begin < size; ++begin) {
for (int end = 0; end < size; ++end) {
if (adjacencyMatrixGraph.connected(begin, end)) {
++count;
}
}
}
stop = high_resolution_clock::now();
time1Elapsed += duration_cast<duration<double>>(stop - start).count();
}
printf(" time1 -- average time: %fn", time1Elapsed / numRepeats);
/* Initialize adjacency list */
AdjacencyListGraph adjacencyListGraph = AdjacencyListGraph(size);
for (int row = 0; row < size; ++row) {
for (int col = 0; col < size; ++col) {
if (adjacencyMatrix[row * size + col]) {
adjacencyListGraph.addEdge(row, col);
}
}
}
/* Time 2 */
double time2Elapsed = 0;
count = 0;
for (int j = 0; j < numRepeats; ++j) {
clearCache();
start = high_resolution_clock::now();
for (int begin = 0; begin < size; ++begin) {
for (int end = 0; end < size; ++end) {
if (adjacencyListGraph.connected(begin, end)) {
++count;
}
}
}
stop = high_resolution_clock::now();
time2Elapsed += duration_cast<duration<double>>(stop - start).count();
}
printf(" time2 -- average time: %fnn", time2Elapsed / numRepeats);
}
return 0;
}
编辑：我想清楚了，这是一个愚蠢的错误，我分配的空间比向量所需的空间要少得多，但程序很乐意在崩溃前读取数百个值。
如果我自己没有分配内存，是什么原因导致了这个错误？
std::vector等人代表您分配内存。如果你滥用了它们，你很容易就会出现类似于你所经历的错误。
如果非要我猜测的话，我会说你在代码中的某个地方有一个越界访问（请记住，像std::vector的[]这样的运算符不会验证你试图访问的索引）。
如果您无法通过检查代码找到错误，那么尝试一下Valgrind可能是值得的。