>我想要一个数据结构,我将元素插入其中,并且在插入后,它保持排序,我找到我刚刚在log N时间插入的元素的索引。
我尝试使用向量和多重集,但都不能满足这两个要求。
向量:
如果我想找到一个元素的索引,我可以做:
using namespace std;
vector<int>::iterator it = lower_bound(myvec.begin(), myvec.end(), someElement);
int index = (it - myvec.begin());
但是,向量不允许在保持排序的同时进行 O(log N( 插入时间。每次插入后对向量进行排序将是 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 允许我插入并保持排序,但它缺乏的地方是在插入后获取元素的索引。
multiset<int>::iterator it = lower_bound(myset.begin(), myset.end(), someElement);
使用lower_bound后,我不能仅仅做
int index = (it - myset.begin());
就像我对矢量一样。相反,我考虑的一种方法是:
int index = distance(myset.begin(), it);
但是,距离在 O(N( 时间而不是 O(log N( 时间上运行。
是否有一种数据结构或方法允许我在log N时间内同时满足这两个要求?
向量和多重集都无法满足要求。
满足要求的数据结构是平衡的二叉搜索树,通过在节点中存储子树的大小来增强。这种增强搜索树称为"订单统计树"。
尽管标准库的有序关联容器是使用搜索树在内部实现的,但标准库不提供可用于实现此目的的通用树数据结构。