7
\$\begingroup\$

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

enter image description here

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;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks Jamal for the formatting. Just notice that the tree can be longer but we always have one parent and/not children. \$\endgroup\$ – mastercode Nov 12 '14 at 15:13
12
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ +1, but I'd recommend the name Node or Vertex over Tree. This is because a Tree object should know how many vertices/nodes are in the tree, its maximum depth, etc. All a vertex/node needs to know is what children it possesses. \$\endgroup\$ – apnorton Nov 12 '14 at 16:34
  • \$\begingroup\$ @anorton: that's one way to do it, but it's also common for each subtree to also be a tree. Whether that object also knows how many vertices are there is an orthogonal issue; one could easily write a member function for that. \$\endgroup\$ – Edward Nov 12 '14 at 16:38
5
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Good points. A minor note about compareChild is that it's better written as a member function operator: bool operator<(const Tree &other) const { return value < other.value; } with a reference as you note. Done that way, children.sort() needs no argument. \$\endgroup\$ – Edward Nov 12 '14 at 17:07
  • 1
    \$\begingroup\$ @Edward, yes quite right. \$\endgroup\$ – glampert Nov 12 '14 at 17:14
  • 1
    \$\begingroup\$ Please note that nullptr and auto are only available in C++11 and above. OP is not tagged with C++11 so YMMV. \$\endgroup\$ – Emily L. Nov 12 '14 at 17:18
  • \$\begingroup\$ Yes, that's true @EmilyL. I'm never sure when to assume C++11 or not. I'd say it is likely to be the case, but there are some compilers out there that haven't caught up with the standard yet... \$\endgroup\$ – glampert Nov 12 '14 at 17:33
  • 1
    \$\begingroup\$ It may be that people new to the language don't necessarily know to specify C++11 or C++14, but they're sure it's C++. \$\endgroup\$ – Edward Nov 12 '14 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.