c++ - 多图与带集合的地图

Question

我想知道哪个更有效。

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

或者

std::multimap< String, int >

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

Answer 1

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

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

但是，就效率而言，将任何内容存储在 a 中map或multimap使用stringkey 几乎肯定会超过两种情况下的差异。

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

Answer 2

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

Answer 3

无论如何，它们实际上并不等效。Amultimap<X,Y>允许存储重复的键值对，而 amap<T, set<X>>不允许。

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< String, int > 很可能内存效率更高。