如何修复 two-dimensional 嵌套向量的分段错误

Question

我已经从 gitHub 的一个 Adj 列表中编写了一个简单的图形 Adj 矩阵。

第一个是Adj列表，其次是Adj矩阵。

第一个很好用。但是第二个是错误的 int Num ，它表示像第一个 int numOfVertices 一样的顶点数。它像 'int Num' 一样成为只读变量。它撞到了 Process finished with exit code 11 。

我找wiki找到了"segmentation default"，有4个原因，其中一个是试图修改只读变量。

然后我在 Adj 矩阵的构造函数中取消对 "Num" 的修改。效果不错。

但是我不知道为什么第一个很好，第二个就错了？以及如何解决？因为我需要修改Num的值...

Adj 列表代码

#ifndef ALTHGORITHM_GRAPH_ADJ_LIST_H
#define ALTHGORITHM_GRAPH_ADJ_LIST_H
#include <iostream>
#include <vector>
#include <queue>
namespace graph_adj_list {
    template <class dataType>                                 // Type of data vertex will hold
    class Graph {
        int numOfVertices;                                      // number of vertices.
        struct Vertex;                                          // forward declaration of vertex structure
        struct Node {                                           // linkedlist for mapping edges in the graph
            Vertex * vertexPtr;                                   // points to the vertex to which the edge is adjecent
            Node * next;                                          // points to the next edge belonging to same vertex
        };
        enum visitedState{                                      // Enum representing visited state of vertex
            WHITE,                                                // not yet visited
            GRAY,                                                 // being visited
            BLACK                                                 // visited
        };
        struct Vertex {
            visitedState state;                                   // state of vertex, visited/being visited/done
            dataType data;                                        // the template data
            Node * list;                                          // Pointer to all edges (linkedlist)
        };

        std::vector<Vertex> vertices;                           // vector of all vertices.
  //private methods
        Node * getNode( Vertex * );                             // allocate and initialize a newnode for the adj list.
        void insertAtEnd( Node * & , Vertex * );                // insert at the end of adjacency list of vertex.
        void deleteAllAfter( Node * );                          // delete the adjacency list of the vertex.
  public:
        Graph() = default;                                      // Default constructor
        Graph(std::vector<dataType> &); 
        ~Graph();
}
  template <typename dataType>
    typename Graph<dataType>::Node *
    Graph<dataType>::getNode(Vertex * v)                // allocate and initialize a newnode for the adj list.
    {
        Node * newNode = new Node;
        newNode->vertexPtr = v;
        newNode->next = nullptr;
        return newNode;
    }
  template <typename dataType>
    void Graph<dataType>::insertAtEnd( Node * & node, Vertex * v)  // insert at the end of adjacency list of vertex.
    {
        Node *newNode = getNode(v);
        if ( node == nullptr ) {
            node = newNode;
        } else {
            Node * temp = node;
            while( temp->next != nullptr ) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
    }
    template <typename dataType>
    void Graph<dataType>::deleteAllAfter( Node * node )                  // delete the adjacency list of the vertex.
    {
        Node * nextNode;
        while( node != nullptr ) {
            nextNode = node->next;
            delete(node);
            node = nextNode;
        }
    }


   template <typename dataType>
    Graph<dataType>::Graph(std::vector<dataType> & values)              // Non default constructor, takes a vector of vertices data
            : numOfVertices(values.size()),
              vertices(numOfVertices)
    {
        for ( int i = 0; i < numOfVertices; ++i ) {
            vertices[i].data = values[i];
            vertices[i].list = nullptr;
            vertices[i].state = WHITE;
        }
    }

    template <typename dataType>
    Graph<dataType>::~Graph()
    {
        for( int i = 0; i < numOfVertices; ++i ) {
            deleteAllAfter(vertices[i].list);
        }
    }
} //end of namespace graph

Adj矩阵代码

#ifndef ALTHGORITHM_GRAPH_ADJ_MATRIX_H
#define ALTHGORITHM_GRAPH_ADJ_MATRIX_H
#include <iostream>
#include <vector>
namespace graph_adj_matrix {
    template<typename T>
    class Graph {
        int Num ;
        enum visitedState {
            NO_VISIT,
            VISITING,
            VISITED
        };
        struct vertex {
            T data;
            visitedState state;
        };

        std::vector<std::vector<int>> Matrix;
        std::vector<vertex> matrix_list;

    public:
        Graph() = default;
        Graph(std::vector<T> &);
        ~Graph();
        void setMatrix(size_t index1, size_t index2);
        void display();
    };


    template<typename T>
    Graph<T>::Graph(std::vector<T> &values) :
                            Num(values.size())
                            ,matrix_list(Num){
        for (typename std::vector<T>::size_type i = 0; i < Num; ++i)
        {
            matrix_list[i].data = values[i];
            matrix_list[i].state = NO_VISIT;
        }
        for (typename std::vector<T>::size_type i = 0; i < Num; ++i)
            for (typename std::vector<T>::size_type j = 0; j < Num; ++j)
                Matrix[i].push_back(0);
    }

    template<typename T>
    void Graph<T>::setMatrix(size_t index1, size_t index2) {
        for (size_t i = 0; i < Num; ++i) {
            if (i == index1 || i == index2) {
                for (size_t j = 0; j < Num; ++j) {
                    if (((i == index1) && (j == index2)) || ((i == index2) && (j == index1))) {
                        Matrix[i][j] = 1;
                        break;
                    }
                }
                break;
            }
        }
    }

    template<typename T>
    void Graph<T>::display() {
        for (size_t i = 0; i < Num; ++i) {
            for (size_t j = 0; j < Num; j++)
                std::cout << Matrix[i][j] << " ";
            std::cout << std::endl;
        }
    }

    template <typename T>
    Graph<T>::~Graph() {}
}
#endif //ALTHGORITHM_GRAPH_ADJ_MATRIX_H

Cpp:

#include "Graph_Adj_List.h"
#include "Graph_Adj_Matrix.h"

int main() {


    std::vector<std::string> myVec{"ABC","DEF","GHI","ZZZ"};


    graph_adj_list::Graph<std::string> myGraph(myVec);



    graph_adj_matrix::Graph<std::string> myGraph_matrix(myVec);



}

我有调试程序

    graph_adj_list::Graph<std::string> myGraph(myVec);

工作顺利。但是

    graph_adj_matrix::Graph<std::string> myGraph_matrix(myVec);

停在

#ifndef _LIBCPP_CXX03_LANG

template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
void
vector<_Tp, _Allocator>::push_back(value_type&& __x)
{
    if (this->__end_ < this->__end_cap())
    {
        __RAII_IncreaseAnnotator __annotator(*this);
        __alloc_traits::construct(this->__alloc(),
                                  _VSTD::__to_raw_pointer(this->__end_),
                                  _VSTD::move(__x));
        __annotator.__done();
        ++this->__end_;
    }
    else
        __push_back_slow_path(_VSTD::move(__x));
}

来自向量 header 从 1635 到 1653 的行的函数。调试器报告这个

Exception = EXC_BAD_ACCESS (code=1, address=0x8)
this = {std::_11::vector<int,std::_1::allocator> * |0x0 } NULL

当我输入设置 ```Matrix[i].push_back(0)''' 的 body 时，它崩溃了错误的条件。

Answer 1

以下只是一个猜测，经过短暂的尝试你的代码：

Process finished with exit code 11

可能意味着您的程序遇到了 信号 11（SIGSEGV，又名分段错误）

我的猜测： 你忘了初始化 Matrix，所以 Matrix[i].push_back(0); 导致了未定义的行为，幸运的是导致了分段错误。

编辑： 您可以使用向量构造函数轻松初始化内部向量：std::vector<std::vector<int>>(Num, std::vector<int>(Num));。这将创建一个向量，其中包含 Num 个具有 Num 个整数的向量的副本。

Answer 2

解决@churill 提出的问题后：

我没有编译你的代码，但我认为问题在于这些行：

Matrix[i][j] = 1;

在这种情况下 Matrix[i] 是一个 vector<int>，但您永远不会为其保留容量，因此 Matrix[i][j] 正在写入受保护/未分配的内存，从而导致段错误。

用足够的容量初始化您的 "internal" 向量（所有 Matrix[i]），看看是否能解决您的段错误。

如何修复 two-dimensional 嵌套向量的分段错误

How to fix segmentation fault with two-dimensional nested vectors

c++

exit-code

multidimensional-array

segment

clion