C++ 扩充 STL 数据结构

Question

我的要求是能够快速检索树中的最小值和最大值。 (注意，不是最小/最大 key ，而是卫星数据的最小/最大)。

树将基于字符串作为键，每个节点将存储一个整数。这个整数必然会改变并不断更新。键保持固定

我正在考虑使用 here 中描述的方法扩充红黑树的方法，以便每个节点存储与最小值相似的最大值(左侧最大值和右侧最大值的最大值及其自身)。

因此，当我更新一个节点时，我会简单地更新遍历到达我当前节点的每个节点的最小值/最大值。

避免重写红/黑树的 STL 实现的最佳方法是什么。

Answer 1

您不能使用 STL 容器(例如 set，据我所知，从技术上讲它甚至不需要 BST)，因为它无法让您访问底层结构。

您的选择是:

• 正如您已经提到的，编写您自己的 BST。

• 只需使用按您的整数值排序的辅助 BST(或堆)。

• 使用 Boost 的 multi_index_container .