我正在尝试为简单的整数行创建对象的树结构。这是我的测试用例:

#include <vector>
#include <queue>
#include <iostream>

using std::vector;
using std::queue;
using std::cout;
using std::endl;

struct Node
{
    Node(int r, int i)
      : id(i)
      , row(r)
    {}

    explicit Node(int i)
      : id(i)
      , row(0)
    {}

    Node()
      : id(0)
      , row(0)
    {}

    int nextLayer(queue<int>& queue, int& curRow)
    {
        int nextId = queue.front();
        queue.pop();

        for (int i = 0; i < children.size(); i++) {
            if (children[i].id == nextId) {
               if (children[i].row == 0)
                  return children[i].nextLayer(queue, curRow);
               else
                  return children[i].row - 1;
            }
        }

        if (queue.size() == 0) {
            curRow++;
            children.push_back(Node(curRow, nextId));
            return curRow - 1;
        }
        else {
            children.push_back(Node(nextId));
            return children.end()->nextLayer(queue, curRow);
        }
    }

    int id;
    int row;
    vector<Node> children;
};

int main()
{
    queue<int> test;
    int row = 0;
    test.push(1);
    test.push(2);
    test.push(3);

    Node testNode;
    cout << testNode.nextLayer(test, row) << endl;
}


live demo

g++ -std=c++03 -O2 -Wall -pedantic -pthread main.cpp && ./a.out
main.cpp: In member function 'int Node::nextLayer(std::queue<int>&, int&)':
main.cpp:32:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < children.size(); i++) {
                           ^
bash: line 8: 15216 Segmentation fault      (core dumped) ./a.out


当我创建一个包含一些整数的队列并在其上调用nextLayer时,这给我带来了分段错误。进一步调查,似乎子节点的vector<Node>大小大于0。

为什么会这样?

最佳答案

问题出在行中

return children.end()->nextLayer(queue, curRow);


您取消引用end(),而不应该这样做。对于非空向量,正确的行是

return children.back().nextLayer(queue, curRow);

10-08 01:07