我需要一个排序和索引的容器。我想基于 std:set 或 std::vector 构建它。通过使用 set，我需要昂贵的 std::distance 来计算其元素的索引。通过使用 vector，我知道添加或删除元素的成本很高。假设我的元素是一个指针(小对象)。我知道两个操作的复杂性是一样的。但是哪个更快呢？谢谢。
最佳答案
如果您需要一个支持排序顺序和按索引查找的数据结构，您绝对应该查看 order statistic tree ，这是一个专门为支持这些操作而设计的数据结构。它支持在 O(log n) 时间内插入和删除，在 O(log n) 时间内查找元素的索引，以及在 O(log n) 时间内按值或按索引查找，因此它应该比 O(log n) 快得多 vector 或集合方法。
不幸的是，STL 没有构建订单统计树，因此您必须搜索第三方库 (this earlier question and answer provides an example of one)。也就是说，您应该期望从订单统计树中获得的加速应该使它非常值得投资。
希望这对您有所帮助!
关于c++ - 用于按排序顺序存储元素并允许快速索引的数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14124825/