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

Question

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

Answer 1

如果您对数组大小的动态增量感兴趣，您可以这样做。

current =0;
x = (int**)malloc(temp * sizeof(int*));
x[current]=(int*)malloc(RequiredLength * sizeof(int));

因此，将元素添加到数组中，当元素填充 x[current] 您可以通过执行为元素添加更多空间

x[++current]=(int*)malloc(RequiredLength * sizeof(int));

这样做可以容纳RequiredLength更多的元素。

您最多可以重复 1024 次，这意味着1024*RequiredLength元素可以是

容纳，在这里它使您有机会在需要时增加数组的大小。

您始终可以通过 X[ n / 1024 ][ n % 1024] 访问第 n 个元素；

Answer 2

std::set考虑到您的评论，它看起来std::unordered_set比std::vector.

Answer 3

如果值的顺序不重要，请使用哈希表。时间是 O(1)。我很确定你会在标准模板库中找到一个实现。

如果做不到这一点，splay 树会非常快，特别是如果您想保持列表有序：每次操作的 O(ln n) 摊销成本，常数因子非常低。我认为 C++ 标准库映射是这样的。

了解你的数据结构。

Answer 4

好吧，deque 没有resize 成本，但是如果是无序的，它的搜索时间是线性的，并且它在自身中间的删除和插入操作时间甚至比vector 更有价值。
如果您不需要按数字的值进行搜索，hashmap 或 map 可能是您的选择。没有调整大小的成本。然后您将映射的键设置为数字的索引，并将值设置为数字的值。搜索和插入操作优于线性。

Answer 5

如果顺序数据结构无法满足要求，您可以尝试查看树（二进制、AVL、m-way、红黑等...）。我建议您尝试实现 AVL 树，因为它会产生平衡或接近平衡的二叉搜索树，可以优化您的操作。有关 AVL 树的更多信息：http ://en.wikipedia.org/wiki/AVL_tree

Answer 6

std::list 绝对是为此类问题创建的，在列表中添加和删除元素不需要像向量中那样重新分配内存。但是，由于列表的非传染性内存分配，搜索元素可能会被证明是一种痛苦的体验，但如果您不经常搜索其条目，则可以使用它。