如何在O(count(k))时间遍历std::unordered_multimap中键为k的元素？

直接通过find(k)获取迭代器后，向前/向后迭代直到键值变化，无法保证遍历到所有键为k的元素，原因如下：

• unordered_multimap基于哈希表实现，相同键的元素会被放入同一个桶，但迭代器的++/--操作是遍历整个容器的所有桶元素，并非仅局限于当前键所在的桶。从find(k)返回的迭代器开始遍历，会持续走到容器末尾，途中会包含其他键的元素（哪怕是哈希碰撞的键，或是其他桶的元素）。
• find(k)仅保证返回任意一个键匹配的元素，不保证它是同键元素区间的起始或结束位置，因此无法通过判断键值变化来确定何时停止遍历。

最优的正确做法 #

使用unordered_multimap::equal_range(k)方法，它会返回一个std::pair<iterator, iterator>：

• 第一个迭代器指向第一个键为k的元素
• 第二个迭代器指向最后一个键为k元素的下一个位置

遍历这个区间就能高效获取所有键为k的元素，无需遍历整个容器，示例代码：

auto range = umap.equal_range(k);
for (auto it = range.first; it != range.second; ++it) {
    // 处理it指向的元素
}

补充说明 #

和有序的std::multimap不同，无序容器没有upper_bound这类基于顺序的方法——因为它的元素排列不遵循键的有序性，equal_range是专门为无序多容器设计的、高效获取同键元素区间的接口。

内容的提问来源于stack exchange，提问作者galinette