C ++中使用Vector、Map还是Hash Map？

Question

C ++中使用Vector、Map还是Hash Map？

4

我有大量记录，大约四百万条，我想重复地处理这些记录并将信息放入与该记录链接的类中。我不确定应该使用什么类型的数据结构？应该使用向量，映射还是哈希映射？我不需要插入记录，但我需要读取包含这些记录编号（或名称）集合的表，然后获取一些与该记录相关联的数据并对其进行某些处理。对于此示例，查找地图是否足够快，以免选择哈希映射？记录具有类作为其结构，以前我没有使用过具有类作为其值的映射或哈希映射（如果可能）。提前感谢大家。

编辑：

目前我不需要同时将所有记录保存在内存中>我需要先给它一个结构，然后从某些记录中获取数据。总记录数约为2000万，我想读取每个原始记录，然后如果其基本信息不存在于要创建和放入其中的新映射或向量中，则将其余数据作为向量放入其中。因为我有2000万条记录，所以对于每条记录都要遍历400万条记录来查找是否存在该记录的基本信息就会非常痛苦。我大约有400万种类型的软件包，每个软件包可以有多种类型的服务（大约每个软件包5（20/4）种）。我想读取每个记录，然后如果包ID不存在于向量或我想使用的任何其他位置，并将基本信息推入向量中，然后将与该包相关的服务保存在包类内部的向量中。

- POD

这是一个不错的链接（众多链接之一）：https://dev59.com/ym435IYBdhLWcg3w6EmF。就我个人而言，听起来“map”可能更适合您的需求。仅供参考... - paulsm4

这里没有足够的细节来确定答案 - 这些结构中的任何一个都可能是合适的。您如何在此列表中查找记录？您是否需要一次性将它们全部加载到内存中？您能详细说明用例吗？ - vercellop

我不确定我理解你想做什么。如果您能简要列举所需的所有操作，可能会有所帮助... 如果您希望在固定大小的数据集上快速检索并减少开销，请选择 std::array。如果大小可变，请选择 std::vector。如果您需要按某种方式对内容进行排序，请选择 std::map（或 std::multimap，如果 ID 可以多次出现）。如果不需要排序，则可以根据数据结构使用 std::set。 - Mihai Todor

你所描述的听起来像是关系型数据库的工作。否则，考虑到你想要快速查找（将记录“链接”到彼此），你可能需要使用哈希表，即unordered_map。 - Preet Kukreti

不，目前我不需要将所有记录同时存储在内存中。我需要先创建一个结构，然后从某些记录中获取数据。总记录数约为2000万条，我想读取每个原始记录，如果其基本信息不存在于我要创建的新映射或向量中，则将其余数据放入其中作为向量。因为我有2000万条记录，所以我认为对于每条记录都遍历400万条记录以查找该记录的基本信息是否存在会非常痛苦。 - POD

我大约有四百万种包裹类型，每个包裹可能有多种服务类型（大约每个包裹有5种服务类型）。我想读取每个记录，如果包裹ID不存在于向量或其他我想使用的数据结构中，则将基本信息推入向量中，并将与该包裹相关的服务保存在包裹类内部的向量中。 - POD

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Samy Arous · Accepted Answer

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

一个 vector 基本上是一个动态数组，非常适合索引值。

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

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

对于你的例子，我认为最好使用一个 hash_map，其中键将是记录号码（假设记录号码是唯一的）。

如果这些记录号码是密集的（意味着索引之间几乎没有空隙，例如：1、2、4、5、8、9、10...），那么你可以使用一个 vector。如果你的记录来自具有自增主键并且没有太多删除的数据库，通常情况下都应该这样做。