C++ Trees Part 1
For all of C++'s brilliance of strongly type-safe generic programming design, its standard library selection leaves much to be desired. Unlike Java, which has libraries for just about everything, C++ only has a handful. These C++ standard libraries are for containers, algorithms, streams and the like. Surprisingly, C++'s list of standard containers does not include a tree container [Musser1].
While hopes exist that C++0x may come with tree container support, C++'s current lack of native tree container support is enough to push programmers away from correctly designed systems using trees, in favor of poorly designed systems that use currently available standard containers. I created the core::tree<> container primarily to overcome this hurdle and add a missing piece to C++'s already powerful and elegantly designed generic containers.
After presenting the arguments made within this article to senior software engineers at Quark, Inc., they began adopting the core::tree<> family (tree, multitree, tree_pair, multitree_pair). Quark has since licensed the core::tree family (royalty free) and has been using it since 2002. They are currently using the core::tree family in their world class software, QuarkXPress 6.0 and expanding its use greatly for QuarkXPress 7.0 [Quark1].
This article is only part one of a series of articles written on the core::tree<> family. Part one primarily focuses on explaining the limitations of using C++'s map<> and multimap<> as tree containers and show the advantages of using the core::tree<> in its stead.
Additionally, simplistic sample core::tree<> code is given to increase basic familiarity with the core::tree<> design. Later installments of to the core::tree<> series will explain more complex usage of the core::tree<> and its flexibility in design.
Lastly, the core::tree<> source code is included for anyone to use, royalty free. The only request is that the licensing agreement found in the tree.h header is followed.
The layout of this article is as follows: