the design of st_tree

st_tree Home

Design Goals
The st_tree container class was designed with several goals in mind:

• Provide an easy-to-use and reasonably feature-rich template class for creating and using data in tree form
• Adhere to STL standards, including standard container interfaces, iterators, type definitions and allocator support
• Provide configurable container storage models for child nodes, including vector, multiset and map container models
• Ensure that no operation has greater than logarithmic complexity (except operations that deep copy data, which are of necessity linear in size of data)

Logarithmic Complexity
It is more precise to say that st_tree operations are O(D), where D is the depth of the node on which the operation is performed. However, in any typical tree with a mean branching factor of > 1, D is logarithmic in the number of nodes, and so pragmatically operations are O(log(N)), where N is the tree size.

One consequence of ensuring logarithmic complexity is that some operations that might have been constant-time are logarithmic, for example ply(), however these tradeoffs allowed other operations to avoid requiring linear complexity.

Separate Tree and Node Types
In principle, a tree class can be made purely recursive, where each ‘node’ is itself a tree type. The st_tree template class involves two separate data types: a tree<> class and a node<> class. This provided some design benefits:

• More efficient use of allocators
• More straightforward support of configurable node storage models
• The ability to support a default constructable empty tree (having no nodes), which is a standard STL container property