c++ - 快速容器以实现一致的性能

Question

我正在寻找一个支持频繁添加/删除的容器。我不知道容器会增长到多大，但我不想因为巨大的重新分配而停滞不前。我需要在性能和一致的行为之间取得良好的平衡。

最初，我考虑过 std::tr1::unordered_map，但由于我不知道数据集的上限，冲突确实会降低 unordered_map 的性能。这不是一个好的散列函数的问题，因为无论它有多好，如果映射的占用率超过桶数的一半，冲突就可能成为问题。

现在我正在考虑 std::map，因为它没有冲突问题，但它只有 log(n) 性能。

当您不知道 unordered_map 的目标大小时，有没有办法智能地处理碰撞？处理这种情况的任何其他想法，我想这并不少见？

谢谢

Answer 1

这是一个运行时容器，对吧？

您是在末尾添加(如 push_back)还是在前面或中间？您是在随机位置移除还是什么？

您如何引用其中的信息？随机，或从前面或后面，还是什么？

如果您需要随机访问，首选基于数组或散列的东西。

如果重新分配是个大问题，您需要更像树或列表的东西。

即便如此，如果您不断地新建(和删除)您要放入容器中的对象，那么仅此一项就可能会消耗大部分时间，在这种情况下，您可能会发现将用过的对象保存在垃圾列表中很有意义，这样您就可以回收它们。

我的建议是，与其纠结于容器的选择，不如选择一个，编写程序，然后tune it, as in this example .无论您选择什么，您都可能想要更改它，而且可能不止一次。我在该示例中发现，任何预先存在的容器类都通过易于编程而不是最快的速度来证明其存在。

我知道这是违反直觉的，但是除非您程序中的某些其他事件最终成为主要成本，并且您无法缩减它，否则您最终的速度爆发将需要手动编码数据结构。