C++ Tree Object Class

Question

I'm writing a class that acts as the base for almost all objects in my project. I know this class technically doesn't represent a tree structure, because it can have more than 2 children. What should I change? Should I be using smart pointers? I'm a self-taught C++ programmer, so I've got much more to learn.

Here's the declaration:

class Object
{
public:
    Object();
    Object(const std::string& name);
    Object(Object* const parent);
    Object(const std::string& name, Object* const parent);

public:
    virtual ~Object();

public:
    virtual void AddChild(Object* const obj) final;
    virtual void RemoveChild(Object* const obj) final;

    virtual std::vector<Object*> FindChildren(const std::string& name, const bool recursive = false) final;

    virtual Object* FindFirstChild(const std::string& name, const bool recursive = false) final;
    virtual Object* FindLastChild(const std::string& name, const bool recursive = false) final;

    virtual std::vector<std::string> ChildrenNames() const final;

    virtual bool HasChild(Object* const obj) const final;

public:
    virtual Object* GetRoot() final;

public:
    virtual bool IsRoot() const final;
    virtual bool IsParent() const final;

public:
    virtual const std::string& GetName() const final;
    virtual void SetName(const std::string& name) final;

    virtual Object* GetParent() const final;

protected:
    std::string name = unnamed_object;

protected:
    Object* parent;
    std::vector<Object*> children;
};

Here's the definitions:

Object::Object() : Object("", nullptr) {}
Object::Object(const std::string& name) : Object(name, nullptr) {}
Object::Object(Object* const parent) : Object("", parent) {}
Object::Object(const std::string& name, Object* const parent)
{
    if(!name.empty()) this->name = name;
    if(parent != nullptr) parent->AddChild(this);
}

Object::~Object()
{
    for(auto& child : children) delete child;
    children.clear();

    if(parent != nullptr) parent->children.erase(std::find(parent->children.begin(), parent->children.end(), this));
}

void Object::AddChild(Object* const obj)
{
    if(obj == nullptr) throw std::invalid_argument("The object cannot be null.");
    if(HasChild(obj)) throw std::invalid_argument("The object is already a child.");

    obj->parent = this;
    children.push_back(obj);
}

void Object::RemoveChild(Object* const obj)
{
    if(obj == nullptr) throw std::invalid_argument("The object cannot be null.");

    auto iter = std::find(children.begin(), children.end(), obj);

    if(iter == children.end()) throw std::invalid_argument("The object is not a child.");

    obj->parent = nullptr;
    children.erase(iter);
}

std::vector<Object*> Object::FindChildren(const std::string& name, const bool recursive)
{
    std::vector<Object*> result;

    for(auto& child : children)
    {
        if(name == child->name) result.push_back(child);

        if(recursive)
        {
            if(child->IsParent())
            {
                std::vector<Object*> resultRecursive = child->FindChildren(name, true);

                result.insert(result.end(), resultRecursive.begin(), resultRecursive.end());
            }
        }
    }

    return result;
}

Object* Object::FindFirstChild(const std::string& name, const bool recursive)
{
    for(auto& child : children)
    {
        if(name == child->name) return child;

        if(recursive)
        {
            if(child->IsParent()) return child->FindFirstChild(name, true);
        }
    }

    return nullptr;
}

Object* Object::FindLastChild(const std::string& name, const bool recursive)
{
    const std::vector<Object*> children = FindChildren(name, recursive);

    if(children.size() > 0)
    {
        return children.at(children.size() - 1);
    } else {
        return nullptr;
    }
}

std::vector<std::string> Object::ChildrenNames() const
{
    std::vector<std::string> result;

    for(auto& child : children) result.push_back(child->name);

    return result;
}

bool Object::HasChild(Object* const obj) const
{
    if(obj == nullptr) throw std::invalid_argument("The object cannot be null.");

    return (std::find(children.begin(), children.end(), obj) != children.end());
}

Object* Object::GetRoot()
{
    if(parent != nullptr)
    {
        return parent->GetRoot();
    } else {
        return this;
    }
}

bool Object::IsRoot() const { return (parent == nullptr); }
bool Object::IsParent() const { return (children.size() > 0); }

const std::string& Object::GetName() const { return name; }
void Object::SetName(const std::string& name)
{
    if(!name.empty())
    {
        this->name = name;
    } else {
        this->name = unnamed_object;
    }
}

Object* Object::GetParent() const { return parent; }

Answer 1

There's more than binary trees

The nodes in a tree can have any number of children. Binary trees (where each node has either two or zero children) are just a special-case. So that's not something to feel bad about. Of course, I'm assuming that your application actually needs this semantics.

A word of caution about inventing base classes

Your sentence

I'm writing a class that acts as the base for almost all objects in my project.

made me a little worried. While it could totally be that such a type is useful for your problem, do resist the temptation to “fix” C++' lack of a base object like java.lang.Object in Java. If you're coming to C++ with a background in a language that has such a base type, it is time to overcome that and accept that C++ is different. Every solution has some benefits and drawbacks associated with it but if you decide to use C++, you'll likely get the worst of both worlds if you think of it as Java (or C# or Python or really any other language).

Follow the “Rule of Five”

If your type needs a custom destructor, it almost certainly also needs

• a custom copy constructor,
• a custom copy assignment operator

and should very likely also have

• a custom move constructor,
• a custom move assignment operator

and maybe also

• a custom swap overload.

Alternatively, all these operations can be deleted. (Which is a decent thing to do for a polymorphic type.)

In your case, if I copy an Object with children, the std::vector<Object*> will happily copy the pointers. Now, when the first of the two objects gets destroyed, it will delete all children and subsequent use of the other copy will invoke undefined behavior. (Even if you just dispose of it as its destructor will attempt to delete an already deleted pointer again.)

These problems will go away if instead of raw pointers (Object*) you use std::unique_ptr<Object>s. If you do this, you'll notice that you probably want to add avirtual Object::clone() member function so you can make copies of trees. Resist the temptation to simply use std::shared_ptr<Object> instead as it will almost certainly not do what you want. (For immutable trees, std::shared_ptr<const Object> would be a decent solution, though.)

Rethink the combination of virtual and final

Declaring a member function as virtual means that a derived class can override it. Declaring a virtual member function as final means that no (further) derived class can override it again. But declaring a function in the base class as virtual and immediately final does no good. Just use an ordinary (non-virtual) function and you'll be good.