The Absence of Tree Containers in the C STL

The C Standard Template Library (STL) doesn't offer any "tree" containers. This omission raises the question: why? And what are suitable alternatives?

Why No Tree Containers in STL?

There are two reasons why one might desire a tree data structure:

1. Hierarchical Object Representation: Modeling a tree-like object hierarchy in the code using a tree structure.

2. Efficient Access Characteristics: Ensuring quick access to elements based on ordering relationships, similar to binary search trees.

Alternatives for Tree Structures

• Boost Graph Library: For representing arbitrary graphs, including hierarchical structures.

• Ordered Associative Containers:

  • std::map and std::multimap: Maps keys to values, ordered by key.
  • std::set and std::multiset: Collections of unique elements, ordered by value.

These containers effectively operate as balanced binary trees, guaranteeing efficient logarithmic access times for inserts, deletes, and searches. They also provide additional advantages, such as:

• Constant-time iterator traversal of elements in sorted order.
• In-built comparison logic for key ordering.
• Generic interfaces, allowing them to work with any key type that supports comparison operators.

Example:

If one wants to store a hierarchy of employees, with a CEO at the root and multiple levels of subordinates, one can use a std::map<:string std::vector>>. Here, the map keys would be employee names, and the associated vectors would hold the names of their direct reports.

Conclusion

While the C STL doesn't provide tree containers directly, it offers suitable alternatives for both hierarchical representation and efficient access characteristics. Boost's graph library can handle complex graph structures, while ordered associative containers provide tree-like access with a generic and well-established interface.