c++ - Overflowing the stack memory with my quadtree class and don't know why

Question

I have been working on a quadtree class for possible collision detections, but the more items I add the faster I overflow the stack.

I also noticed the memory usage increases linearly as the program runs so I assume I am not deleting something properly and it is just stacking on each other?

I know most stack overflow errors are caused by recursion but it shouldn't be happening with just 100 objects.

#include "Quadtree.h"

Quadtree::Quadtree(Rectangle* bounds)
{
    this->bIsSplit = false;
    this->bounds = bounds;
    this->maxObjects = 5;
}

void Quadtree::Split(std::vector<std::pair<SpaceObject*, SpaceObject*>> &collidingObjects)
{
    float x = bounds->x;
    float y = bounds->y;
    float subWidth = bounds->width / 2;
    float subHeight = bounds->height / 2;

    // Top Left
    nodes.push_back(new Quadtree(new Rectangle(x, y, subWidth, subHeight)));
    // Top Right
    nodes.push_back(new Quadtree(new Rectangle(x + subWidth, y, subWidth, subHeight)));
    // Bottom Left
    nodes.push_back(new Quadtree(new Rectangle(x, y + subHeight, subWidth, subHeight)));
    // Bottom Right
    nodes.push_back(new Quadtree(new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight)));

    // takes all the objects in the parent node and splits them into there corresponding subdivided quadtree
    for (auto o : this->objects)
    {
        for (int i = 0; i < nodes.size(); i++)
        {
            if (nodes[i]->bounds->Contains(o->x, o->y, o->size))
            {
                nodes[i]->Insert(o, collidingObjects);
            }
        }
    }

    this->objects.clear();
    this->bIsSplit = true;
}

void Quadtree::Insert(SpaceObject* spaceObject, std::vector<std::pair<SpaceObject*, SpaceObject*>> &collidingObjects)
{
// if the object does not fit inside this quadtree, this isn't the right quadtree
if (!bounds->Contains(spaceObject->x, spaceObject->y, spaceObject->size))
{
    return;
}

if (!bIsSplit && this->objects.size() < maxObjects) // add the object to the quadtree if the max has not been hit
{
    objects.push_back(spaceObject);

    for (auto o : this->objects)
    {
        // if the objects are not the same and overlapping (pythag)
        if (spaceObject != o &&
            ((spaceObject->x - o->x) * (spaceObject->x - o->x)) + ((spaceObject->y - o->y) * (spaceObject->y - o->y)) <= (spaceObject->size + o->size) * (spaceObject->size + o->size))
        {
            // Add colliding pair to the collidingObjects vector
            collidingObjects.push_back(std::make_pair(spaceObject, o));
        }
    }

}
else
{
    if (!this->bIsSplit) // splits the quadtree if this quadtree has not been split yet
    {
        this->Split(collidingObjects);
    }

    // adds the passed in object to one of the subnodes
    for (auto n : nodes)
    {
        n->Insert(spaceObject, collidingObjects);
    }
}
}

void Quadtree::Delete(SpaceObject* spaceObject)
{
    if (!bounds->Contains(spaceObject->x, spaceObject->y, spaceObject->size))
    {
        return;
    }

    if (!bIsSplit)
    {
        for (int i = 0; i < objects.size(); i++)
        {
            if (objects[i] == spaceObject)
            {
                this->objects.erase(objects.begin() + i);
                return;
            }
        }
    }
    else
    {
        for (auto n : nodes)
        {
            n->Delete(spaceObject);
       }
    }
}

void Quadtree::Clear()
{
    if (bIsSplit)
    {
        for (auto n : nodes)
        {
            n->Clear();
        }
        this->bIsSplit = false;
    }
    nodes.clear();
    objects.clear();
}

标签： c++recursionstack-overflow

Answer 1

好吧，我不知道是什么nodes或如何Quadtree定义的，因为您没有显示完整的代码。但是您使用的是new. 是nodes指针的集合吗？如果是这样，您可能会将它们放在地板上，因为它们永远不会被删除。

---

不要到处写this->。成员在成员函数的范围内。您的Quadtree构造函数应该对常量成员使用内联初始化程序，并为bounds. 而且，在这里使用裸指针是一个危险信号。这是什么所有权bounds？为什么它需要是一个指针而不是简单的 Rectangle 类型的值？

我想知道您是否习惯了另一种语言，一种new用于所有构造的语言，并且具有引用语义，并且对象实际上是指针。C++ 是不同的。

我建议在不使用任何指针的情况下编写它。当然，Rectangle应该是一个值。Quadtree 如果可以有效地移动元素，则向量在插入和删除等时可能是有效的。所以，Quadtree应该有一个移动构造函数。如果您还不完全了解构造函数和特殊成员，这可能是一个高级概念。

⧺C.149是您绝对应该遵循的，即使是（尤其是作为）初学者，也不能裸露new或delete. 因此，如果您需要制作指向 的指针向量，请将其设为Quadtree的向量shared_ptr。请记住，您在 C++ 中没有垃圾收集，因此任何使用指针的东西都必须明确处理生命周期管理的责任。Ashared_ptr将表现得更像您习惯的那样，并且它们可以安全地用于vector.