两全其美:向量与列表的插入/删除效率

你可能在找一些散列图,比如 boost::unordered_map (很快就会出现在C++标准中)。还有很多其他的散列实现。

您正在寻找std::deque,它在许多(但不是所有)情况下都比std::list执行得好,因为需要在端点以外的位置插入。它使用“bucket”来实现这一点,并支持随机访问。实际上,对于任何标准库容器,您都需要根据应用程序对它的使用情况来测试它的性能—我们无法为您预测什么是最好的。

我需要这种容器作为我编写的稀疏向量容器,我不能使用map<&燃气轮机;因为它占用了太多内存(向量没有那么稀疏)。

最后我用了一个 compressed bit vector . 每个枚举值都有自己的位向量,这一点显示得相当好。

我仍然希望我能找到一个有效的向量/列表混合,在随机访问中是O(1),在擦除/插入中至少是O(logn)。