我正在研究数据结构，其中输入非常大，几乎 1 TB。我需要将数据加载到关联容器中。
数据有一些重复的整体，所以我正在使用 multimap ，但有人建议我使用 vector map 而不是使用它。我可以知道性能方面的差异是什么吗？
map<const char*, const char*, cmptr> mulmap;
map <const char*, vector <const char*> ,cmptr> mmap;
最佳答案
你在浪费时间思考 map与 multimap 相比.假设 bin 的数量为 N，每个 bin 的平均项目数为 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 对于大多数系统来说根本不可行，而且我听说没有主板支持它。
您最好使用数据库来存储 1 TB 的数据。您可以为此任务选择几乎任何数据库。 Kyoto Cabinet很简单，做你想做的事，但你也可以使用 PostgreSQL、MySQL、Sqlite、Dynamo、Redis、MongoDB、Cassandra、Voldemort...
关于c++ - C++中的 map 与多 map (性能)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14932007/