C++ : Data Structure withe fast searching and less memory requirements

Question

我想知道在我的情况下哪种数据结构内存效率高。请指导我。以下是要求。如下图所示，在三个值 A、B 和 C 的基础上(其中 A 将是一个整数值，B、C 将是字符)我想存储两个接受规则编号和 true/false 的值。因此，对于 A、B 和 C 的每个唯一值，我想存储与它们对应的两个值(接受规则编号和 true/false)。请指导我哪种数据结构可以快速搜索并且内存效率高。就像我的情况一样表格长度可达65025或以上。

Answer 1

标准库中明显的可能性是 std::map 和 std::unordered_map。对于 std::map，您将创建一些包含 A、B 和 C 的类，并定义一个该类的比较函数。对于 std::unordered_map，您需要改为定义哈希函数。

为了快速搜索(对插入和删除的速度很少或根本不感兴趣)，您还可以考虑使用按 A、B 和 C 字段排序的 vector 。与 std::map 相比，这通常会提高速度并减少使用的空间。缺点是插入和删除变得线性而不是对数(即更慢——可能慢很多，尤其是当集合很大时)。

至于更喜欢哪一个:如果您正在使用足够大的表，大 O 复杂性可能占主导地位，那么 std::unordered_map 将是显而易见的选择——它给出了恒定的(预期的)复杂性。 std::map 给出对数复杂度。如果您仅使用二进制搜索，排序后的 vector 也将是对数的。假设您的 key 分布合理，您可以使用内插搜索，它通常具有大致 O(log log N) 复杂度。 log log N 增长非常缓慢——如此缓慢，它通常被称为“伪常数”或类似的东西。 IOW，即使对于非常大的表，也没有太多理由相信散列一定会快得多。

Big-O 分析与更多 更大的表最相关(例如，数亿，而不是问题中建议的数万)。对于您建议的表大小，对数搜索算法可能完全具有竞争力。例如，最多 65536 个项目，我们期望二分查找不超过 16 次比较。

很多事情都归结为平衡内存使用和搜索速度。如果您愿意牺牲一些空间来获得更好的搜索速度，哈希表 (std::unordered_map) 可能是显而易见的选择。如果您更关心最小化内存使用量，那么排序 vector 可能会胜出。 std::map 可能是三者中最容易实现的，并且(考虑到你所说的大小)它的速度可能也不会是一个重大问题(但其他两个 会可能会更快)。