Building a parent/child tree relationship

Question

I have a problem: build a tree relationship parent/child like this one:

Can you review this piece of code please since I am convinced it could be improved?

struct item {
    char value;
    std::list<item*> children;
};

I write a comparison function for a sort :

bool compareChild(const item *first, const item *second)
{
    return ( first->value < second->value );
}

a function to get the parent:

item *getTopParent(const char src_data[][2], int len)
{
    for (int i = 0; i < len; ++i)
    {
        if (src_data[i][0] == '\0')
        {
            item* head = new item;
            head->value = src_data[i][1];
            return head;
        }
    }
    return NULL;
}

Two functions to push the children:

bool PushChildren(const char src_data[][2], int len, item *parent)
{
    bool parentGotChildren = false;

    for (int i = 0; i < len; ++i)
    {
        if (src_data[i][0] == parent->value)
        {
            item* child = new item;
            child->value = src_data[i][1];
            parent->children.push_back(child);
            parentGotChildren = true;
        }
    }
    parent->children.sort(compareChild);

    return parentGotChildren;
}

bool PushChildrenforAParent(const char src_data[][2], item *parent, int len)
{
    bool hasGotAChild = true;
    std::list<item*>::iterator itchild = parent->children.begin();
    std::list<item*>::iterator childLast = parent->children.end();

    while (hasGotAChild && (itchild != childLast))
    {
        hasGotAChild = PushChildren( src_data, len, *itchild);
        if (hasGotAChild)
        {
            hasGotAChild = PushChildrenforAParent( src_data, *itchild, len);
        }
        ++itchild;
    } 
    return hasGotAChild;
}

A function to initialise the "tree":

item* initialize_tree(const char src_data[][2], int len)
{
    bool hasTopParentGotAChild = false;
    //initialisation of the head
    item *head = getTopParent( src_data, len);

    if (head != NULL)
    {
        hasTopParentGotAChild = PushChildren( src_data, len, head);

        if (head != NULL)
        {
            if (hasTopParentGotAChild)
            {
                PushChildrenforAParent(src_data, head, len);
            }
            return head;
        }
        else 
        {
            return NULL;
        }
    }
    return NULL;
}

Answer 1

Some quick comments:

• Your code style is all over the place. You have three different styles for function names: initialize_tree, PushChildren and getTopParent, pick one and stick to it. I would recommend the last one.
• Your code looks more like C and not C++ with what I presume to be free functions.
• item is an inappropriate name, a more typical name is Node.
• You really should push the functionality to modify the nodes, or tree in general onto the item type and turn it into a class using member functions (methods).
• You are allocating memory with new but never freeing it with delete thus you are leaking memory like it's 1995.
• You are handling raw pointers, this is not recommended. Prefer to use the std containers or smart pointers for managing memory.
• If you feel that you need to explain something to the reader, that's usually a hint that your code needs better structure. hint
• std::list is slow, prefer to use std::vector on modern CPUs. Vector is \$\mathcal{O}(n)\$ insertion and removal at the front while list is \$\mathcal{O}(1)\$. However the cost of poor locality of reference on the list means that the cross-over point when the list becomes faster than the vector for just about anything at all is when you have about 100-1000 elements (depending on size) and are hitting the worst case for vector. Which I doubt you won't reach in your program. So unless you have a very specific reason to use std::list prefer a std::vector.

Answer 2

Here are some things that may help you improve your code.

Use relevant #includes

Your implementation requires std::list so the interface should have the line #include <list>.

Name classes wisely

The code currently uses a class named item which is a very generic word. A more descriptive name would be Tree. Also note that, while not compulsory, a common convention in C++ is to use capitalized names for classes, and lowercase names for instances of classes and other variables.

Follow a naming convention

Some of your functions, such as compareChild use camel-case, and others, such as PushChildren start with a capital letter, and others, such as initialize_tree use embedded underscores. This inconsistency makes it harder to read, understand and maintain the code. Better would be to use a convention consistently. There are many different ones out there and some, such as Google's are available on the web. Pick one and use it consistently; consistent use is more important than which particular convention you use.

Use object orientation

Because you're writing in C++, it would make sense to have methods that operate on a class such as Tree (using my suggested rename of item) be member functions rather than separate functions. For example, when I re-implemented your code as an object, I got this:

class Tree {
public:
    Tree(char val) : value(val), children() {}
    Tree(const char src_data[][2], int len);
    bool operator<(const Tree &other) const { return value < other.value; }
    bool PushChildren(const char src_data[][2], int len);
    bool PushChildrenforAParent(const char src_data[][2], int len);
    std::ostream& printLevel(std::ostream &out, int level) const {
        for (int i=0; i<level; ++i)
            out << "   ";
        out << value << '\n';
        ++level;
        for (const auto &kid : children)
            kid.printLevel(out, level);
        return out;
    }
    friend std::ostream& operator<<(std::ostream &out, const Tree &node) {
        return node.printLevel(out, 0);
    }
private:
    char value;
    std::list<Tree> children;

    // a function to get the parent:
    static char getTopParent(const char src_data[][2], int len) {
        for (int i = 0; i < len; ++i)
            if (src_data[i][0] == '\0')
                return src_data[i][1];
        return '\0';
    }
};

Note that one of the things I added was a means to print out the tree. That kind of thing can be very handy for debugging.

Avoid using pointers

Modern C++ doesn't really need pointers very often. It's usually better to either use a smart pointer, such as std::unique_ptr or simply use objects or object references. For this code, that suggests that instead of children being a std::list<Tree*> that they would probably be better as std::list<Tree>.

Avoid new and delete

If you don't use pointers, you have much less reason to use new and delete. But if you do use new, each instance of new must be matched to a corresponding delete. Often the best way to do this is to put delete in a destructor.

Prefer class to struct

The only real difference, of course, is that by default, the members of a struct are public, while the members of a class are private. Still, it's best to keep the internals of a class private to reduce linkage among objects to only what they need. This simplifies the interface and therefore the maintenance. If, for example, you wanted to use a std::array instead of a std::list internally to the Tree, it shouldn't require that any code using the tree is affected.

Answer 3

Use nullptr:

NULL is a macro from the C library and its use in C++ is very outdated. Start using nullptr.

Use auto for compile-time type inference:

std::list<item*>::iterator is very lengthy and easy to mistype. This can easily be improved with the use of auto.

auto itchild   = parent->children.begin();
auto childLast = parent->children.end();

Use references whenever possible:

C++ references are safer than pointers. You should give them the preference.

bool compareChild(const item & first, const item & second)
{
    return first.value < second.value;
}

Note: As @Edward commented, compareChild() should instead be a comparison operator of your type, in this case item (still use the references):

struct item 
{
    bool operator < (const item & other) const { return value < other.value; }
    ...
};

Avoid deep nesting and return early:

Deeply nested logic can get very hard to read an follow. If you can return early, do so. It will make your code simpler and more straightforward.

Example with initialize_tree():

item* initialize_tree(const char src_data[][5], int len)
{
    item *head = getTopParent( src_data, len);
    if (head == nullptr)
    {
        return nullptr;
    }

    bool hasTopParentGotAChild = PushChildren( src_data, len, head);
    if (head == nullptr)
    {
        return nullptr;
    }

    if (hasTopParentGotAChild)
    {
        PushChildrenforAParent(src_data, head, len);
    }

    return head;
}