我有一个数组，我需要尽快在其中插入项目。在添加项目之前，我需要查看它是否存在，因此我进行了全阵列扫描。我无法使用二进制搜索，因为我无法在每次插入后对数组进行排序。
这个作业是否有更高效的数据结构？
编辑:我在那个数组上存储字符串。在每个字符串旁边，我存储了一个 4 字节的哈希值。我首先比较哈希值，如果它们相同，则比较字符串。
最佳答案
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) 搜索。
关于c++ - 快速插入和快速搜索的正确数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32061592/