多图与地图集

Question

我想知道哪个更有效率.

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

要么

std::multimap< String, int >

编辑: 我不打算用这些地图做任何与众不同的事情.标准插入,删除,修改,搜索.每个集合或多键字符串的大小不应超过100.

Answer 1

我相信这是依赖于实现的,但是(未)教育的猜测:

在实践中,它取决于你将保留在multimap或中的整数的数量std::set.multimap在log(n)搜索密钥之后,A 很可能会使用值的线性搜索.如果您有大量的整数值,那么log(n)搜索键后跟log(n)搜索值可能会稍快一些.

但是,就效率而言,将任何内容存储在一个map或multimap一个string密钥中几乎肯定会超过两种情况下的差异.

如下所述,a multimap可能更容易使用,更清晰,以保持其独特的优势.

Answer 2

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

Answer 3

无论如何，它们实际上并不等同。Amultimap<X,Y>允许存储重复的键值对，而 a 则map<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 方法，除非您需要重复的键值对。语法也更好。我预计性能和内存使用方面的差异不会那么大。