I originally expected to use two STL container types,
a map
There was a particular problem with looking things up in the node set. Input data is read in standard C string format (I used fgets rather than stream IO because the data strings contain proper names, some of which have embedded spaces). Because the fast (tree-based) lookup method does not take a custom comparison procedure, this code often creates an object just to destroy it again when it finds out that such a node already exists. I understand a putative custom comparison procedure would have to order the nodes in the same manner as the red-black trees are organized, but I would be willing to live with such a caveat, I just want the search target to be a char * flavor string instead of a bstring.h flavor string.
There seemed to be about four basic approaches to this problem.
NodeMem *node = new NodeMem(name); NodeSet::iterator nit = set.find(node); if ( set.end() != nit ) { delete node; return(**nit); } else { set.insert(node); return(*node); }This could be the most expensive approach since we have to do heap allocation to make the new node object.
string s(name); return( set.find((NodeMem *)&s) ); // **UGLY!!!**This seems ugly and dangerous, and it only saves us the heap allocation, since we still need to make the string object in the local stack frame.
It's a pity I wasn't able to user more polymorphism or more of STL's facilities, but my natural tendancy to optimize seems to have taken over, in that various opportunities to do more work were avoided when a simplification was seen to be possible.