多重贴图与带集合的贴图

Question

我想知道哪个更有效率。

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

或

std::multimap< String, int >

编辑： 我不打算对这些地图做任何不寻常的事情。标准插入、删除、修改、搜索。每个集合或多键字符串的大小不应超过 100。

Answer 1

我认为这取决于实现，但这是一个（未）受过教育的猜测：

实际上，它取决于您将在 multimap 或 std::set 中保留的整数数量代码>.在对键进行 log(n) 搜索之后，multimap 很可能会使用线性搜索值。如果您有大量整数值，则对键进行 log(n) 搜索，然后对值进行 log(n) 搜索可能会稍快一些。

然而，就效率而言，使用 string 键将任何内容存储在 map 或 multimap 中几乎肯定会超过这两种情况的差异。

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

Answer 2

“set”选项将消除键+值对的重复，无论多重映射是否不会。

Answer 3

无论如何，它们实际上并不等同。 multimap 允许存储重复的键值对，而 map> 则不允许。

multimap<int, int> m;
m.insert(make_pair(2, 3));
m.insert(make_pair(2, 3)); // This changes the size of m!

否则

map<int, set<int>> m;
m[2].insert(3);
m[2].insert(3); // This does nothing.

因此，除非您需要重复的键值对， 我会使用 set 方法。语法也更好。我预计性能和内存使用方面的差异不会那么大。

Answer 4

如果您到目前为止对这些答案不满意（并不是说您不满意）并且我绝对被迫回答，我也会给出我有根据的“猜测”：

要插入，多重映射似乎更“有效” 。使用映射方法，您首先必须检索集合，然后对集合执行操作。
要删除/检索，地图似乎更“高效”。

Answer 5

我不能肯定地说，但考虑到 multimap 的设计目的是执行另一个表达式的操作，最好具体化并使用 multimap，它更有意义，它还具有用于使用的成员函数多重映射作为一个概念，使用其他方法这些函数会有点时髦。

Answer 6

std::multimap<字符串、整数>很可能更有效率的内存。