多图与带集合的地图

2022-01-17 00:00:00 set c++ map std multimap

我想知道哪个更有效.

std::map< String, std::set<int> >

std::multimap< String, int >

我不打算用这些地图做任何不寻常的事情.标准的插入、删除、修改、搜索.每个 set 或 multi keyed String 的大小不应超过 100.

I do not plan on doing anything out of the ordinary with these maps. Standard insert, delete, modify, search. The size of each set or multi keyed String shouldn't be more than 100.

推荐答案

我相信这取决于实现,但一个(未经)教育的猜测:

This I believe is implementation dependant, but an (un)educated guess:

实际上,这取决于您将在 multimapstd::set 中保留的整数数量.multimap 很可能会在对键进行 log(n) 搜索之后对值进行线性搜索.如果您有大量整数值,则对键进行 log(n) 搜索,然后对值进行 log(n) 搜索可能会稍微快一些.

In practice it depends on the number of integers that you will be keeping in the multimap or the std::set. A multimap will most likely use a linear search of the values after the log(n) search of the key. If you have a large number of integer values, then the log(n) search of the keys followed by a log(n) search of the values may be slightly faster.

然而,就效率而言,使用 string 键将任何内容存储在 mapmultimap 中几乎肯定会超过两者的差异案例.

However, in terms of efficiency, storing anything in a map or multimap with a string key will almost certainly outweigh the differences in either case.

如下所述,multimap 可能会更易于使用且更易于维护,从而具有明显的优势.

As said below, a multimap will likely be easier to use and more clear to maintain giving it a distinct advantage.

相关文章