c++ - C ++的向量或映射或哈希映射？

Question

我有大量记录，比如大约 4,000,000 条，我想反复处理它们并将信息放入与该记录链接的类中。我不确定我应该使用什么样的数据结构？我应该使用向量、映射还是哈希映射。我不需要插入记录，但我需要读取包含这些记录编号（或名称）集的表，然后获取一些链接到该记录的数据并对它们进行一些处理。在 map 上的发现是否足够快以至于不能在这个例子中使用 hashmaps？这些记录有一个类作为它的结构，并且我之前没有做过任何使用以类作为其值的映射或哈希映射（如果可能的话）。提前谢谢各位。

编辑：

我暂时不需要将所有记录同时保存在内存中>我需要先给它一个结构，然后从一些记录中获取数据。记录总数约为 2000 万条，我想读取这些原始记录中的每一个，然后如果我要创建的新地图或矢量中不存在其基本信息，然后将其余数据作为一个向量。因为我有 2000 万条记录，我认为每条记录都要经过 400 万条记录才能找到该记录的基本信息是否存在，这将是非常痛苦的。我有大约 400 万个类型的包，每个包都可以有不止一种类型的服务（每个包大约 5 (20/4) 个）。

Answer 1

这三种数据结构各有不同的用途。

Avector基本上是一个动态数组，适用于索引值。

Amap是具有 O(log(n)) 检索和插入时间的排序数据结构（使用平衡二叉树实现，通常是红黑）。如果您找不到有效的哈希方法，这是最好的。

Ahash_map使用哈希来检索对象。如果您有一个定义良好且冲突率低的哈希函数，您将获得恒定的平均检索和插入时间。hash_maps 通常比map但并非总是更快。它高度依赖于哈希函数。

对于您的示例，我认为最好使用 a hash_mapwhere key 将是记录号（假设记录号是唯一的）。

如果这些记录数密集（意味着索引之间几乎没有间隙，例如：1,2,4,5,8,9,10...），您可以使用vector. 如果您的记录来自具有自动增量主键且删除次数不多的数据库，则通常应该是这种情况。