c++ - 保持排序的数据结构，允许 log N 插入时间，并且可以返回我在 log N 中查找的元素的索引

Question

我想要一个数据结构，我可以在其中插入元素，插入后，它保持排序，并且我在 log N 次中找到刚刚插入的元素的索引。

我尝试过使用 vector 和多重集，但都不能满足这两个要求。

vector :

如果我想找到一个元素的索引，我可以这样做:

using namespace std;
vector<int>::iterator it = lower_bound(myvec.begin(), myvec.end(), someElement);
int index = (it - myvec.begin());

但是， vector 在保持排序的同时不允许插入时间为 O(log N)。每次插入后对 vector 进行排序的时间复杂度为 O(N log N)。我尝试过:

vector<int>::iterator it = lower_bound(myvec.begin(), myvec.end(), someElement);
myvec.insert(it, someElement);

这会找到插入元素的正确位置，但 myvec.insert 的运行时间为 O(N)，而不是 O(log N) 时间。

多集:

多重集允许我插入并保持排序，但它缺少的是在插入后获取元素的索引。

multiset<int>::iterator it = lower_bound(myset.begin(), myset.end(), someElement);

使用 lower_bound 后，我不能仅仅这样做

int index = (it - myset.begin());

就像我对 vector 所做的那样。相反，我考虑的一种方法是:

int index = distance(myset.begin(), it);

但是，距离运行的时间为 O(N)，而不是 O(log N) 时间。

是否有一种数据结构或方法可以让我在 log N 时间内满足这两个要求？

Answer 1

vector 和多重集都无法达到要求。

能够满足要求的数据结构是平衡二叉搜索树，它通过在节点中存储子树的大小来增强。这种增强搜索树称为“顺序统计树”。

尽管标准库的有序关联容器在内部使用搜索树实现，但标准库没有提供可用于实现此目的的通用树数据结构。