关于通过索引访问std::set中的元素，这个网站上有几个问题，但我看到的答案是旧的，没有启发性。
有序集可以（并且通常）实现为二叉搜索树。在二叉搜索树中，通过存储以每个节点为根的树中的节点数，我们可以在k时间内按排序顺序访问O(log n)th元素，而不会增加其他操作的算法复杂度（如果这是错误，请纠正我我的想法）。
然而，如果我想从k排序的set::setth元素，我必须从begin()一直走到k，使用O(k)时间代替。一般来说，这可能等于O(n)时间。
所以，我的问题是：
k时间内找到O(log n)th元素而不破坏其他操作的时间复杂度是否正确？可以使用可用于在对数时间内通过索引实现搜索的额外信息来扩充（平衡的）搜索树。这种增强的搜索树可以被称为order statistic tree。
增加树不会影响主要操作（插入，查找，擦除）的最坏情况渐近复杂性：它们的最坏情况仍然是对数。我不知道它是否会阻止有序关联容器的擦除和提示插入操作所需的摊销常数复杂性。
然而，渐近复杂度不是特征的唯一标准。增加树增加了对数运算的复杂系数，使得所有（或大多数）其他运算更慢。它还增加了数据结构的空间开销。因此，仅仅因为这样的数据结构是可能的，并不一定意味着使用它来实现标准库提供的通用关联容器是个好主意。
没有。在标准库中没有基于搜索树的容器具有对数索引查找。
我找到了一个基于Boost树组件库的提议n3700，它建议添加通用树结构。它包括类rank_tree，它似乎是一个增强的搜索树，提供您正在寻找的操作。