c++ - 搜索和更新整数值列表最快的数据结构是什么？

Question

我必须维护一个无序整数列表，其中整数的数量是未知的。它可能会随着时间的推移而增加或减少。我需要经常更新这个整数列表。我试过使用 vector 。但它真的很慢。 Array 看起来更快，但由于 list 的长度不固定，因此需要花费大量时间来调整它的大小。请提出任何其他选项。

Answer 1

使用 hash table ，如果值的顺序不重要。时间是 O(1)。我很确定您会在标准模板库中找到实现。

否则，一个 splay tree非常快，特别是如果你想保持列表有序:每次操作的摊销成本为 O(ln n)，常数因子非常低。我认为 C++ stdlib 映射是这样的。

了解你的数据结构。