创建指针向量时的分段错误（C++）

Question

我正在研究一个实现Dijkstra算法的程序。

我第一次在txt文件数据读入指针数组的向量，所以我可以使用它。 （该文件包含顶点数（在这种情况下为7），顶点及其各自的边和重量）。请看下图：

7 
2 
2 2 
4 1 
2 
4 3 
5 10 
2 
1 4 
6 5 
4 
3 2 
5 2 
6 8 
7 4 
1 
7 6 
0 
1 
6 1 

在我Main.cpp的我试图创建的指针下面的行向量到顶点对象：

vector<Vertex*> vertices; 

然后我试图填充矢量与下面的代码：

for(int i=1;i < numVertices; i++) 
    { 
     file >> numEdges; 
     cout << "At vertex " << i << " the number of edges is " << numEdges << endl; 
     vertices[i] = new Vertex(); 
     //Vertex newVertex; 

     //Using the i counter variable in the outer for loop to identify 
     //the what vertex what are currently looking at in order to read in the correct adjacent vertex and weight 
     cout << "LENGTH OF VERTICES[i]: " << vertices.size() << endl; 
     vertices[i]->setVertexNum(i); 
     //newVertex.setVertexNum(i); 

     for(int j=1;j<=numEdges;j++) 
     { 
      file >> adjacentVertex; 
      cout << "The adjacent vertex is: " << adjacentVertex << endl; 


      file >> weight; 
      cout << "The weight is: " << weight << endl; 
      cout << endl; 

      vertices[i]->setAdjacentVertex(adjacentVertex, weight); 
     } 
     //cout << "LENGTH OF VERTICES[i]: " << vertices.size() << endl; 
     vertices.push_back(vertices[i]); 
    } 

但是，我得到一个seg故障，我不明白为什么。我之前宣布了像这样的指针向量，没有任何问题，我希望这里有人能够指出我正确的方向。

虽然因为如果我改变矢量初始化下面，我没有得到一个赛格故障有趣的是：

vector<Vertex*> vertices(numVertices + 1, NULL); 

不过，我不想矢量预置为特定的大小，我只是想要它初始化。

谢谢

Answer 1

你为什么要在最后一行做这件事？

vertices.push_back(vertices[i]); 

您已经拥有顶点[i]的顶点，为什么再次插入它呢？它会导致错误，因为你为第i个条目分配了内存，但push_back将尝试再次放入第（i + 1）个条目中，并且该内存未分配。分段错误意味着程序尝试访问未经授权的内存。

也为他人所提到的，开始循环为阵列，矢量或类似的容器应该是从0

编辑

当您使用

vector<Vertex*> vertices(numVertices + 1, NULL); 

然后不发生因为该问题，向量具有numVertices + 1个指向其中的vetex项目的指针。当 I = numVertices，然后在线路

vertices.push_back(vertices[i]); 

第i个元素是第（i + 1）个位置推动。但在之前的情况下，当i = numVertices时没有第（i + 1）个元素，因此在尝试写入不可用的内存位置时发生段错误。

Answer 2

您尚未提供足够的信息来明确回答您的问题，但我可以在代码中指出一些明显的缺陷。

“在我的主要。CPP我试图与顶点下面一行对象创建的指针的向量：

vector<Vertex*> vertices; 

我们不知道剩下的代码是否是在主与否，或者如果你正在传递，但常见的错误是通过价值而不是参考来传递向量。按值传递将来自main的空向量复制到本地函数副本中，填充该向量，然后丢弃它。该代码返回到主那里顶点的主要的副本是不变：

void wrong(vector<Vertex*> vertices) { 
} 

void right(vector<Vertex*>& vertices) { 
} 

vector<Vertex*> alternative() { 
    vector<Vertex*> vertices; 
    ... 
    return vertices; 
} 

下一个问题是你的for循环，它从1开始在C和C++语言，数组使用“零基础”偏移。也就是说，在一个阵列或向量的第一个元素是元素0：

char str[] = "hello"; 
std::cout << "str[0] = " << str[0] << "\n"; 
std::cout << "str[1] = " << str[1] << "\n"; 

将输出

str[0] = h 
str[1] = e 

您的代码由于某种原因在1碱基运转补偿：

for(int i=1;i < numVertices; i++) 

接下来的问题是你立即引用向量的元素。 C++的vector类不自动增长数据时，你这样做：

std::vector<int> v; 
int i = v[23]; // may crash; "undefined behavior". 

您的代码似乎做到这一点：

for(int i=1;i < numVertices; i++) 
{ 
    ... 
    vertices[i] = new Vertex(); 

你要问的载体，使i元素可用。你可以这样做两种方式：

vertices.resize(numVertices); 

这种预尺寸一气呵成的载体，并在一个弹出numVertices默认初始化值填充它。好，高效。或者你也可以做到以下几点：

vertices.reserve(numVertices); 
for (...) { 
    Vertex* newVert = new Vertex(); 
    vertices.push_back(newVert); 

这告诉矢量准备为numVertices大，但实际上并没有增加“大小（）”，这样就不必四处移动内存，因为它生长的载体。

但你实际上可以避开所有这些新的/删除的麻烦，合理地利用矢量：

vector<Vertex> vertices; 
... 
vertices.resize(numVertices); 

在这一点上，你有一个数组numVertices默认初始化顶点的对象，准备要工作。现在，您可以只使用：

for (size_t i = 0; i < vertices.size(); ++i) { 
    Vertex& vert = vertices[i]; // 'vert' is now a short-cut alias to vertices[i]. 
    vert.setVertNum(i); 
} 

或者你可以使用“emplace_back”如果你正在使用C++ 11，这是为“创建在后面一个新的向量元素的功能，这里是它的构造函数论据“：

class Vertex { 
    size_t m_vertNum; 
    float m_x, m_y; 
public: 
    Vertex(size_t vertNum, float x, float y) 
     : m_vertNum(vertNum) 
     , m_x 
     , m_y 
    { 
    } 
}; 

vector<Vertex> vertices; 
size_t numVertices = 10; 
vertices.reserve(numVertices); 
for (size_t i = 0; i < numVertices; ++it) { 
    vertices.emplace_back(/*vertNum*/ i, /*x*/ float(i * 3), /*y*/ float(i * 2)); 
    Vertex& vert = vertices.back(); 
    ... 
} 

Answer 3

对不起，这不是一个答案，而是一个重要的建议，可能导致一个答案。我想我已经重复了这么多次，我应该写一篇关于这个的博客文章。 为什么你认为你需要一个指针向量？

指针向量是非常非常少见的必需，而且它们很难管理，尤其是如果你是C++初学者的话。 Dijkstra算法不是您需要它们的情况之一。出于某种原因，我发现C++初学者使用类似于Java的关键字new，但他们似乎并不明白在C++中，你需要负责内存管理。这很可能是您的问题海事组织的来源。

我的建议：尝试通过将std::vector<Vertex*>替换为std::vector<Vertex>来实现完全相同的算法。让我们看看，这可能会通过使它消失而“解决”你的段错误问题。