c++ - 树在递归时不维护迭代器成员

Question

我正在构建一个简单的包围体层次结构，以二叉搜索树结构实现。有时，一个树节点最终会附加多个对象(例如，如果它们的质心位于同一位置)。所以，我必须让每个节点维护一个对象集合而不是单个指针。

我尝试通过迭代器让每个树节点包含对象集合的特定片段来做到这一点。在生成树时分发它们似乎可以正常工作，但在检索叶子时迭代器会以某种方式损坏。

代码的简化版本:

#include <iostream>
#include <cstdlib>
#include "util.h"
#include <vector>
#include <algorithm>

using namespace std;

class Point {
public:
    Point() : x(0), y(0) {}
    Point(double x, double y) : x(x), y(y) {}
    double x;
    double y;
};

Point elementWiseMin(Point a, Point b) {
    return Point(min(a.x, b.x), min(a.y, b.y));
}

Point elementWiseMax(Point a, Point b) {
    return Point(max(a.x, b.x), max(a.y, b.y));
}

class BoundingBox {
public:
    BoundingBox(Point minCorner, Point maxCorner) : minCorner(minCorner), maxCorner(maxCorner) {}
    Point minCorner;
    Point maxCorner;
};

class Shape {
public:
    Shape(BoundingBox* obj, Point x) : boundingBox(obj), centroid(x) {}
    BoundingBox* boundingBox;
    Point centroid;
};

typedef vector<Shape*> ShapeContainer;

class Tree {
public:
    Tree(ShapeContainer::iterator begin, ShapeContainer::iterator end) :
        begin(begin), end(end), hasNodes(true) {
        cout << end - begin << "\n";
        if (end - begin < 1) hasNodes = false;
        else {
            minCorner = (*begin)->boundingBox->minCorner;
            maxCorner = (*begin)->boundingBox->maxCorner;
            for (ShapeContainer::iterator i = begin + 1; i < end; i++) {
                minCorner = elementWiseMin(minCorner, (*i)->boundingBox->minCorner);
                maxCorner = elementWiseMax(maxCorner, (*i)->boundingBox->maxCorner);
            }

            double split = minCorner.x + ((maxCorner.x - minCorner.x) / 2);
            splitAt = split;
            ShapeContainer::iterator middle = partition(begin, end,
                [split](Shape* n) {
                return n->centroid.x < split;
            });

            if (middle - begin > 0 && end - middle > 0) {
                Tree c1 = Tree(begin, middle);
                child1 = &c1;
                Tree c2 = Tree(middle, end);
                child2 = &c2;
            }
        }
    }
    ShapeContainer::iterator begin;
    ShapeContainer::iterator end;
    Point minCorner;
    Point maxCorner;
    Tree* child1 = nullptr;
    Tree* child2 = nullptr;
    bool hasNodes;
    double splitAt;

    //get the node at x
    Tree* getNode(int x) {
        cout << end - begin << "\n";
        if (x < splitAt) {
            if (child1 == nullptr) return this;
            else return child1->getNode(x);
        }
        else {
            if (child2 == nullptr) return this;
            else return child2->getNode(x);
        }
    }
};

int main() {
    ShapeContainer container;
    Shape shape1 = Shape(new BoundingBox(Point(0, 0), Point(1, 1)), Point(0.5, 0.5));
    container.push_back(&shape1);
    Shape shape2 = Shape(new BoundingBox(Point(-2, 0), Point(-1, 1)), Point(-1.5, 0.5));
    container.push_back(&shape2);
    Shape shape3 = Shape(new BoundingBox(Point(2, 0), Point(3, 1)), Point(2.5, 0.5));
    container.push_back(&shape3);
    Shape shape4 = Shape(new BoundingBox(Point(4, 0), Point(5, 1)), Point(4.5, 0.5));
    container.push_back(&shape4);

    cout << "Generate tree\n";
    Tree t = Tree(container.begin(), container.end());

    cout << "Traverse tree\n";
    Tree* node = t.getNode(-1);
    return 0;
}

输出:

Generate tree
4
2
1
1
2
1
1
Traverse tree
4
-47673

生成时的输出正是我所期望的，但看起来迭代器没有正确保存到子级。

Answer 1

在 Tree 构造函数的末尾，您将局部变量的地址分配给 Tree 类的成员 (child1 = &c1).这很糟糕，因为几行之后 c1 对象超出范围并将被销毁。这使得 child1(和 child2)成为悬空指针，因为它们指向的对象不再有效。

您可能希望使用动态内存分配(使用 unique_ptr 或 shared_ptr)来正确构建树。