std::vector cleared without interaction

Question

I've got a issue with a std::vector being cleared but I can't figure out where. I have spent a lot of time debugging the issue and can't for the life of me find out where it is cleared.

Code:

    class ENGINE_API QuadTree {
    private:
        typedef std::unordered_set<QuadTreeObject*> EntityContainer;
        typedef std::vector<QuadTree> ChildContainer;

        const static int MAX_OBJECTS = 5;
        AABB bounds;

        ChildContainer children;
        EntityContainer entities;
        EntityContainer allEntities;

        // Internal methods
        void split();

        int getIndex(const AABB&)const;

        template <class T>
        void merge(T& one, const T& two) {
            one.insert(two.begin(), two.end());
        }
        // End Internal methods
    public:
        QuadTree(AABB bounds) : bounds(bounds), children(), entities(), allEntities() {
            children.reserve(4);
        }

        // Base
        void clear() {
            entities.clear();
            allEntities.clear();
            children.clear();
        }

        void insert(QuadTreeObject*);

        void remove(QuadTreeObject*, const AABB&);

        // Not the source, I've removed this and it still works fine (Nothing uses this method)
        ChildContainer& getChildren() {
            return children;
        }

        AABB& getBounds() {
            return bounds;
        }

        QuadTree getLowestRoot(const AABB& aabb)const {
            int index = getIndex(aabb);
            if (index == -1 || children.empty()) {
                return *this;
            }
            return children.at(index).getLowestRoot(aabb);
        }

        const EntityContainer& getAll()const {
            return allEntities;
        }
        // End Base
    };

void QuadTree::split() {
    children.clear(); // supposed to be there

    double width = (bounds.getWidth() / 2);
    double height = (bounds.getHeight() / 2);

    children.push_back(QuadTree(AABB(bounds.min.x + width, bounds.min.y, width, height)));
    children.push_back(QuadTree(AABB(bounds.min.x, bounds.min.y, width, height)));
    children.push_back(QuadTree(AABB(bounds.min.x, bounds.min.y + height, width, height)));
    children.push_back(QuadTree(AABB(bounds.min.x + width, bounds.min.y + height, width, height)));

    auto it = entities.begin();
    while (it != entities.end()) {
        int index = getIndex((*it)->getAABB());
        if (index != -1) {
            children.at(index).insert(*it);
            it = entities.erase(it);
        }
        else {
            it++;
        }
    }
}

int QuadTree::getIndex(const AABB& aabb)const {
    // Fits in top
    bool topQuadrant = aabb.max.y < aabb.horzMid;
    // Fits in botom
    bool bottomQuadrant = aabb.min.y > aabb.horzMid;

    // Fits in left
    if (aabb.max.x < aabb.vertMid) {
        if (topQuadrant) {
            return 1;
        }
        else if (bottomQuadrant) {
            return 2;
        }
    }
    // Fits in right
    else if (aabb.min.x > aabb.vertMid) {
        if (topQuadrant) {
            return 0;
        }
        else if (bottomQuadrant) {
            return 3;
        }
    }

    return -1;
}

void QuadTree::insert(QuadTreeObject* object) {
    AABB aabb = object->getAABB();

    allEntities.insert(object);

    if (children.empty()) {
        if (entities.size() <= MAX_OBJECTS) {
            entities.insert(object);
            return;
        }
        split();
    }

    int index = getIndex(aabb);
    if (index != -1) {
        children.at(index).insert(object);
    }
    else {
        entities.insert(object);
    }
}

void QuadTree::remove(QuadTreeObject* object, const AABB& aabb) {
    if (!allEntities.erase(object)) {
        return;
    }

    if (!entities.erase(object)) {
        if (!children.empty()) {
            int index = getIndex(aabb);

            if (index != -1) {
                children.at(index).remove(object, aabb);
            }
            else {
                throw std::logic_error("Can't be in allEntities but not entities!");
            }
        }
        else {
            throw std::logic_error("Can't be in allEntities but not entities!");
        }
    }
}

When the split method is called children.size() returns 4, but by the time it gets to insert it is 0 again. How is this possible?

Answer 1

This is a problem:

class ENGINE_API QuadTree {
    typedef std::vector<QuadTree> ChildContainer;

    ChildContainer children;

QuadTree is an incomplete type up until the class definition is finished. If you use std::vector with an incomplete type, the behaviour is undefined.

In other words, a class can't contain a vector of itself. You will have to redesign your class a bit, e.g.:

• switch to a vector of smart pointers,
• implement the vector in a pImpl idiom
• use a different container that is designed to work with incomplete types