c++ - 快速插入和快速搜索的正确数据结构？

Question

我有一个数组，我需要尽快在其中插入项目。在添加项目之前，我需要查看它是否存在，因此我进行了全阵列扫描。我无法使用二进制搜索，因为我无法在每次插入后对数组进行排序。

这个作业是否有更高效的数据结构？

编辑:我在那个数组上存储字符串。在每个字符串旁边，我存储了一个 4 字节的哈希值。我首先比较哈希值，如果它们相同，则比较字符串。

Answer 1

std::unordered_map 通常实现为 ( hashtable ) 将为您提供最佳插入/搜索时间 (O(1))，但不保留也不提供任何顺序。

std::map给你 O(log(n)) 用于搜索和插入，因为它需要特定的顺序(不是你必须插入项目的顺序)并且通常用平衡树实现。

自定义 balanced search trees如果您需要排序顺序和快速 (O(log n)) 插入/搜索，则是另一种选择。

已排序 std::vector (以支持添加项目的能力)是另一种选择，如果 O(n) 是可接受的插入时间，但您需要最小的内存占用和 O(log n) 搜索时间。由于需要复制数组的其余部分，因此您需要按 O(n) 的排序顺序插入项目。

如果您需要保留原始顺序，那么如果您只使用数组 ('std::vector')，那么插入/搜索的时间复杂度为 O(n)。

除了“std::vector”之外，您还可以使用单独的 std::unordered_map/std::unordered_set 添加“已存在”检查以提高速度以 2-3 倍内存空间为代价，并且在添加项目时需要更新 2 个结构。这种数组+哈希表组合将为您提供 O(n) 插入和 O(1) 搜索。