C++中的map和multimap有什么区别（性能方面）？

Question

我正在处理一个数据结构，输入数据非常大，几乎有1TB。我需要将数据加载到关联容器中。

数据中存在一些重复的记录，所以我正在使用multimap，但有人建议我使用map of vector而不是使用multimap。从性能方面来说，这两者有何区别？

 map<const char*, const char*, cmptr> mulmap;

 map <const char*, vector <const char*> ,cmptr> mmap;

- Manish

---

为什么不尝试两者，然后找出答案呢？ - Oliver Charlesworth

实际上，在这两种情况下，除非你拥有1TB的RAM系统，否则你的性能很可能会被磁盘速度所限制。 - Oliver Charlesworth

如果您想使用 const char* 作为键，您必须同时提供一个比较谓词才能使其工作。使用 std::map<std::string, std::string> 可能更容易些。 - Olaf Dietsche

请不要使用 const char* 作为字符串，如果您想使用字符串，请改用 std::string。拜托了！ - Mark Garcia

https://dev59.com/kms05IYBdhLWcg3wQvoe - Pheonix

Answer 1

你浪费时间思考使用 map 还是 multimap 。假设箱子的数量为 N，每个箱子平均包含 M 个物品。

std::multimap<Key, Val> 通常使用带有重复键的 RB 树实现。

• 获取 O(log N + log M)
• 插入 O(log N + log M)
• 删除 O(log N + log M)
• 迭代 O(1)

std::map<Key, std::vector<Val>> 通常使用唯一键的 RB 树实现。

• 获取 O(log N)
• 插入 O(log N)
• 删除 O(log N)
• 迭代 O(1)

如你所见，除非 M 很大，否则不值得讨论区别。

但是，两种存储方式的存储都受到 RAM 的限制。 对于大多数系统来说，1 TB 是不可行的，并且我听说没有任何支持它的主板。

对于1TB数据，最好使用数据库，几乎可以选择任何数据库来完成此任务。 Kyoto Cabinet 简单易用，符合你的需求，但你也可以使用 PostgreSQL、MySQL、Sqlite、Dynamo、Redis、MongoDB、Cassandra、Voldemort 等。

- Dietrich Epp

---

对于“1 TB的数据”，我们实际上需要小心选择数据库和访问数据的方式，因为可能会有一些限制和其他情况。 - user166390

@user15662：对于这种工作，我仍然建议使用Kyoto Cabinet而不是std::。 - Dietrich Epp

+1 @user15662，那么拥有一个坚如磐石的数据库后端应该是必须的。我在这里同意Dietrich的观点。 - WhozCraig

对于我们这些仅拥有人类级别的RAM的人来说，我们可以预期multimap的性能与使用vector的map大致相同？ - Carbon

@Carbon：取决于您要如何使用数据。一般而言，不会。但是向量通常是正确的选择。 - Dietrich Epp

Answer 2

如果有1TB的输入，我不会使用任何一种方法。很可能你的内存不够用。可以使用一些磁盘数据结构，比如B-树。

- Olaf Dietsche