Generic C-Trees and C++ std::maps

How many lines of code do I need, to set up a typical tree structure? What are the pros and cons between a C-style generic tree and an std::map or an std::set ?




We often create a tree of temporary elements, just to see if a particular element has been visited once.

The following piece of code is a typical one in C, where you have a number of shapes, whose edges you wish to store in a tree.

The edge is comprised of two nodes of a shape:

struct MyEdgeNodes {
    Node *n1;
    Node *n2;
};

Typically, a generic C-based tree requires copy, free, and compare functions.

/* the tree */
Tree *edges_tree = NewTree(compareMyEdgeNodes, copyMyEdgeNodes, freeMyEdgeNodes);

/* support functions */
void *copyMyEdgeNodes(void *edge)
{
   MyEdgeNodes *tmp_edge_nodes = (MyEdgeNodes *)edge;
   MyEdgeNodes *new_edge_nodes;

   new_edge_nodes = malloc(sizeof(struct MyEdgeNodes));
   new_edge_nodes->n1 = tmp_edge_nodes->n1;
   new_edge_nodes->n2 = tmp_edge_nodes->n2;

   return new_edge_nodes;
}

int compareMyEdgeNodes(void *edge1, void *edge2)
{
    MyEdgeNodes *edge_nodes1 = (MyEdgeNodes *)edge1;
    MyEdgeNodes *edge_nodes2 = (MyEdgeNodes *)edge2;

    if( edge_nodes1->n1 > edge_nodes2->n1 ) return 1;
    else if( edge_nodes1->n1 < edge_nodes2->n1 ) return -1;
    else {
        if( edge_nodes1->n2 > edge_nodes2->n2 ) return 1;
        else if( edge_nodes1->n2 < edge_nodes2->n2 ) return -1;
        else return 0;
    }
}

void freeMyEdgeNodes(void *edge)
{
    free(edge);
}

All this code, simply to set up a tree of edges.


Reflecting on the code above, we know that

• C++ provides implicit copy constructors, so we shouldn't need the copyMyEdgeNodes()
• we know that there is nothing in the struct to be deleted, so there's no need for freeMyEdgeNodes()
• the struct is merely a pair of members, and std::pair already provides an operator<

therefore, the struct and the code above reduces to :

typedef pair<Node *, Node*> MyEdgeNodes;

set< MyEdgeNodes > edges_tree;

This does the same job, plus it has some advantages:

• it requires less calls to malloc and free.

Compare the C tree layout to the std::set layout:

memory layout of a generic tree in C

memory layout of an std::set