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

Question

此网站上有几个关于通过索引访问 std::set 中的元素的问题，但我看到的答案很旧且没有启发性。

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

尽管如此，如果我想要 set::set 中按排序顺序排列的第 k 个元素，我必须从 begin() 开始一直到 k，使用 O(k) 时间。一般来说，这可能相当于 O(n) 时间。

所以，我的问题是:

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

Answer 1

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

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

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

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

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