多重映射 vs 带有集合的映射

Question

我想知道哪个更有效率。

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

或者

std::multimap< String, int >

编辑： 我不打算对这些映射进行任何超出寻常的操作。标准的插入、删除、修改、搜索。每个集合或多关键字字符串的大小不应超过100。

- Kaiser Wilhelm

---

你想要执行哪些操作？这将定义不同的成本，因为第一种方法可以让你通过字符串和整数进行快速查找，而第二种方法则需要你迭代并测试整数部分是否与相同字符串的每个值相同...但如果你不需要那个操作，在某些用例中第二个选项可能更好... - David Rodríguez - dribeas

两者并不等价：multimap可以存储多个("foo", 1)的副本，而map+set则不能。 - Kerrek SB

今天在SO上为什么会充斥着这些“哪个容器更有效”的问题，一个接一个地出现呢？我们认为有什么特别的原因吗？ - Lightness Races in Orbit

我主要会查找一个字符串并遍历与该字符串相关联的每个整数。我想知道比较这两个容器是否有任何明显的差异或需要注意的事项。 - Kaiser Wilhelm

@Kaiser：最后一条评论应该是你问题的关键所在：你正在查找字符串，然后迭代所有包含的元素意味着（再次取决于使用模式，即如果没有重复的整数），map<string,set<int>>与第二种替代方案相比没有明显的优势，而且在某些情况下，map<string,vector<int>>可能更好或更差...不知道问题的具体情况是无法判断的。 - David Rodríguez - dribeas

可能是重复的问题：std::multimap<key, value> 和 std::map<key, std::set<value>> 有什么区别？ - Ciro Santilli OurBigBook.com

Answer 1

我认为这是实现相关的，但是有一个（不）受过教育的猜测：

实际上，这取决于您将在 multimap 或 std :: set 中保留的整数数量。 multimap将很可能在键的log(n)搜索后使用值的线性搜索。 如果您有大量整数值，则键的log(n)搜索后跟随值的log(n)搜索可能略快。

但是，从效率的角度来看，在 map 或 multimap 中存储具有 string 键的任何内容几乎肯定会超过两种情况之间的差异。

如下所述，使用 multimap 很可能更易于使用和维护，具有明显的优势。

- Chad

Answer 2

“set”选项将消除键值对的重复，而multimap则不会。”

- Pedro Reis

Answer 3

它们实际上并不等价。一个 multimap<X,Y> 允许存储重复的键值对，而 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方法。语法也更优美。我认为性能和内存使用方面的差异并不大。

- Timmmm

---

那应该是被接受的答案。谈论不同事物的效率是没有意义的。 - Andreas Pasternak

Answer 4

如果你对目前的答案不满意（并不是说你不满意），而我必须回答，那么我会给出我的"猜测"：

插入时，multimap似乎更"高效"。使用map方法时，首先必须检索，然后在集合上执行操作。 删除/检索时，map似乎更"高效"。

- Kevin Le - Khnle

Answer 5

我不能确定，但考虑到multimap的设计目的是执行另一个表达式的功能，更好的做法应该是具体化并使用multimap，这更有意义，它还具有用作概念的multimap成员函数，使用其他方法会有些奇怪。

- John Leidegren

Answer 6

std::multimap< String, int > 很可能更加内存高效。

- Man Vs Code

---

两者存储的数字数量相同，但由于您使用了两个红黑树，因此使用的“簿记”结构的数量是必要的两倍。此外，由于大多数std :: string STL实现使用引用计数和写时复制语义，因此字符串使用的数据可能不会加倍。希望这样讲述有意义，因为我正在手机上输入。 - Man Vs Code

实际上，你还没有证明映射和集合占用的空间比multimap多（multimap的额外簿记呢？），但实际上你将存储比两个树更多的东西。而且这些是如何实现为树并没有指定。在STL中没有std命名空间。而且，我的评论真的是想激发你为你的回答添加一个合理性的 ;) - Lightness Races in Orbit

STL中没有std命名空间？这对我来说是新鲜事。std::multimap通常使用红黑树实现，使用opetator<=。std::set通常也是一个红黑树，但使用operaror<。事实是，它的实现取决于具体情况，在PC上，我所说的通常是正确的。 - Man Vs Code

你可能将STL和C++标准库混淆了。 - Lightness Races in Orbit