一个multimap的每个元素都包含键和值吗？

Question

我想象不到这个问题还没有被问过，但是我找不到任何相关的信息。

multimap的每个元素是否都包含它的值和它的键？

也就是说，multimap的内部结构是否更像这样：

map<key, vector<value>>

或者更像这样：

vector<pair<key, value>>

- Jonathan Mee

Answer 1

每个元素都包含其键和值。

你可以通过迭代返回一个稳定的非分配引用来判断，具体类型为std::pair<Key const, Value>。

更重要的是，键可以相等但不同。 multimap允许您在该键中存储“额外数据”，这些数据不是排序的一部分，您将在之后得到它，并与该值相关联。

将multimap实现为std::map<Key, std::vector<Value>>是一个比使用std::multimap<Key,Value>更好的选择，特别是在每个键有多个值的情况下，它将更具内存效率，具有更好的局部性等。 如果您想要均匀地迭代，那么遍历它可能会更加棘手，但是如果您想要按键聚集迭代，则更容易。

- Yakk - Adam Nevraumont

---

你能详细说明在哪里记录了multimap允许存储“额外数据”吗？ - Slava

@Slava struct Foo { std::string a; std::string b; bool operator<( Foo const& rhs) const { return a < rhs.a; } }; -- 这是一个有效的“Key”类型。它包含了a和“额外数据”在b中，而这不是排序的一部分。如果你插入 { Foo{"hello", "world"}, value );，迭代器将包含一个Foo const，其中b中有“world”。这对于multimap来说并不是很重要（为什么不把它放在值中呢？），但我有时会用它来做multiset或set（然而，你也可以说“为什么不直接使用map？”） - Yakk - Adam Nevraumont

是的，我理解这意味着什么，而且似乎很合理，但我在multimap的文档中找不到这样的保证。例如，当等效的键已经存在时，有什么防止它使用现有键的副本而不是提供的键的原因。 - Slava

@Slava，我仍然不清楚您想从Yakk那里得到什么。您的真正问题是什么？您是否认为容器的less需要比较键的所有字段？不需要。它是否说过只有由less比较的字段在对中的key部分中才保证有效？没有。那问题是什么呢？multimap必须将它们作为两个单独的对象保留的事实来自于上述两个事实。 - SergeyA

@SergeyA 我会说问题是“在多重映射规范中是否有什么阻止它为具有相等键的每个条目保留相同的键（或其副本）？” - Slava