c++ - 可以或为什么不能在 std::set 中按索引搜索元素？

Question

这个站点上有几个关于按索引访问 std::set 中的元素的问题，但我看到的答案是陈旧的且没有启发性。

有序集可以(并且经常)实现为二叉搜索树。在二叉搜索树中，通过存储以每个节点为根的树中的节点数，我们可以在 O(log n) 中按排序顺序访问第 k 个元素在不增加其他操作的算法复杂度的情况下节省时间(如果这是我的想法错误，请纠正我)。

不过，如果我想从 set::set 中按排序顺序排列第 k 个元素，我必须从 begin() 开始一直到 k，使用 O(k) 时间代替。通常，这可能相当于 O(n) 时间。

所以，我的问题是:

• 我们可以维护一个高度平衡的二叉搜索树是否正确，其中可以在 O(log n) 时间内找到第 k 个元素而不损坏其他操作的时间复杂度？
• 如果是这样，C++ 标准库中是否有我可以利用的函数或替代数据结构？
• 如果前者为"is"而后者为“否”，是否已经或正在考虑？是因为某些技术障碍而未实现，还是仅仅因为实现成本被认为对于此功能的潜在用途来说过于昂贵？

Answer 1

有可能用额外的信息来扩充(平衡的)搜索树，这些信息可用于在对数时间内通过索引实现搜索。这种增强的搜索树可以称为 order statistic tree .

扩充树不会影响主要操作(插入、查找、删除)的最坏情况渐近复杂度:它们的最坏情况仍然是对数的。我不知道它是否可以防止有序关联容器的删除和暗示插入操作所需的分摊常数复杂性。

然而，渐近复杂性并不是特征的唯一标准。扩充树会增加对数运算的复杂系数，使所有(或大多数)其他运算变慢。它还增加了数据结构的空间开销。因此，仅仅因为这样的数据结构是可能的，并不一定意味着使用它来实现标准库提供的通用关联容器是个好主意。

没有。标准库中没有基于带有对数索引查找的搜索树的容器。

我找到了一个提案 n3700基于建议添加通用树结构的 Boost 树组件库。它包括 rank_tree 类，它似乎是一个增强的搜索树，提供您正在寻找的操作。