c++ - 我可以或为什么不能在 std::set 中按索引搜索元素？
问题描述
这个网站上有几个关于std::set按索引访问元素的问题，但我看到的答案是陈旧的，没有启发性。
有序集可以（并且经常）实现为二叉搜索树。在二叉搜索树中，通过存储以每个节点为根的树中的节点数，我们可以在不增加其他操作的算法复杂度的情况下及时访问k排序顺序的第 th 元素O(log n)（如果这是我的错误，请纠正我思维）。
不过，如果我希望第kth 元素从 a 开始排序set::set，我必须从begin()一直走到 k，O(k)而使用时间。一般来说，这可能等同于O(n)时间。
所以，我的问题是：
- 我们可以维护一个高度平衡的二叉搜索树，它可以在不破坏其他操作的时间复杂度的情况下及时找到第
kth 个元素，这是否正确？O(log n) - 如果是这样，我可以利用 C++ 标准库中的函数或替代数据结构来达到这个效果吗？
- 如果前者是，但后者不是，是否已经或正在考虑？是因为某些技术障碍而没有实施，还是仅仅因为实施成本被认为对于该功能的潜在效用而言过于昂贵？
解决方案
可以使用额外信息来扩充（平衡）搜索树，这些信息可用于在对数时间内实现按索引进行搜索。这种增强的搜索树可以称为顺序统计树。
增强树不会影响主要操作（插入、查找、擦除）的最坏情况渐近复杂性：它们的最坏情况仍然是对数的。我不知道它是否可以防止有序关联容器的擦除和暗示插入操作所需的摊销常数复杂性。
然而，渐近复杂度并不是特征的唯一标准。扩充树会增加对数运算的复杂系数，从而使所有（或大多数）其他运算变慢。它还增加了数据结构的空间开销。因此，仅仅因为这样的数据结构是可能的，并不一定意味着使用它来实现标准库提供的通用关联容器是个好主意。
没有。标准库中没有基于对数索引查找的搜索树的容器。
我发现了一个基于 Boost 树组件库的提案n3700 ，它建议添加通用树结构。它包括 class rank_tree，它似乎是一个增强的搜索树，提供了您正在寻找的操作。