C STL 中缺少树容器

C 标准模板库 (STL) 不提供任何“树”容器。这一遗漏提出了一个问题：为什么？什么是合适的替代方案？

为什么 STL 中没有树容器？

人们可能需要树数据结构有两个原因：

1.分层对象表示： 使用树结构在代码中建模树状对象层次结构。

2。高效访问特点：保证根据排序关系快速访问元素，类似于二叉搜索树。

树结构的替代方案

• Boost Graph Library： 用于表示任意图，包括分层图

• 有序关联容器：

  • std::map 和 std::multimap：将键映射到值，按键排序。
  • std::set 和 std::multiset：唯一元素的集合，排序依据value.

这些容器有效地作为平衡二叉树运行，保证插入、删除和搜索的高效对数访问时间。它们还提供了其他优点，例如：

• 按排序顺序对元素进行恒定时间迭代器遍历。
• 用于键排序的内置比较逻辑。
• 通用接口，允许它们与任何支持比较的键类型一起使用Operators.

示例：

如果要存储员工的层次结构，其中以 CEO 为根，并有多个级别的下属，可以使用std::map<:string std::vector>>。这里，映射键将是员工姓名，关联向量将保存其直接报告的姓名。

结论

虽然 C STL 没有提供直接树容器，它为层次表示和高效访问特性提供了合适的替代方案。 Boost 的图形库可以处理复杂的图形结构，而有序关联容器通过通用且完善的接口提供树状访问。