C++中的map vs multimap(性能)

Question

我正在研究数据结构,其输入非常大,接近1 TB.我需要将数据加载到关联容器中.

数据有一些重复的entires所以我使用multimap但有人建议我使用vector的map而不是使用它.我可以知道明智的表现有什么不同吗？

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

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

Answer 1

你在浪费时间思考map对抗multimap.假设箱的数量是N并且每箱的平均物品数是M.

A std::multimap<Key, Val>通常使用具有重复键的RB树.

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

A std::map<Key, std::vector<Val>>通常使用具有唯一键的RB树.

• 获取为O(log N)
• 插入是O(log N)
• 删除是O(日志N)
• 迭代是O(1)

正如你所看到的,除非M非常大,否则差异不值得讨论.

但是,两者的存储都受RAM的限制.对于大多数系统来说,1 TB根本不可行,而且我听说没有支持它的主板.

最好使用1 TB数据的数据库.您可以为此任务选择几乎任何数据库. 京都内阁很简单,做你想要的,但你也可以使用PostgreSQL,MySQL,Sqlite,Dynamo,Redis,MongoDB,Cassandra,Voldemort ......

Answer 2

使用1 TB的输入,我也不会使用.最有可能的是,你没有足够的内存.在B-tree等磁盘数据结构上使用一些.