我想要一个结构来存储（例如）我可以在其中插入和删除元素的数字，我的结构始终保持排序（就像优先级队列一样），但可以知道给定数字在哪里，并且每个运算都可以对数时间进行。
也许使用lower_bound，upper_bound或仅进行二进制搜索，但是在priority_queue中，阻止我进行二进制搜索的原因是我无法访问只有第一个索引的元素。
最佳答案
我认为您正在寻找一种order statistics tree增强型BST，它支持时间为O（log n）的所有常规BST操作以及其他两个操作：
rank（elem）：返回排序后的元素将占用的索引。
index（k）：给定索引k，返回排序序列中该索引处的元素。
以上两个操作的运行时间为O（log n），因此非常快。
您可以将订单统计树视为优先级队列。插入与普通的BST插入一样工作，要提取最低/最高元素，您只需从树中删除最小/最大元素，就可以在时间O（log n）中通过沿着树的左或右棘走而完成。
关于c++ - 优先级队列之类的结构，但下限类似，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47370819/