如何在C++ multimap中查找指定键值对的出现范围与次数

std::multimap::equal_range 原生仅支持按键做等价匹配，无法直接筛选映射值，可通过两步法实现需求，不需要遍历整个容器，性能符合常规使用要求：

• 第一步：调用equal_range获取目标键对应的连续元素区间，这一步时间复杂度为O(log n)，直接把搜索范围从全容器缩小到同键的小范围
• 第二步：在上述区间内定位值匹配的起止迭代器，由于同键元素在multimap中是连续存储的，匹配相同值的元素遍历范围仅覆盖同键下的元素，时间复杂度为O(k)，k为该键对应的元素总数

示例代码 #

对应测试用例的可直接运行实现如下：

#include <map>
#include <algorithm>
#include <string>
#include <iostream>

int main() {
    std::multimap<std::string, std::string> mm = {
        {"BO", "MA"}, {"CL", "SC"}, {"DA", "TX"}, {"FL", "MI"},
        {"FL", "MI"}, {"MI", "FL"}, {"OR", "FL"}
    };
    const std::string target_key = "FL";
    const std::string target_val = "MI";

    // 提取同键元素范围（C++11环境可替换为显式pair类型声明）
    auto key_range = mm.equal_range(target_key);
    auto key_range_begin = key_range.first;
    auto key_range_end = key_range.second;
    
    // 定位第一个值匹配的迭代器，作为结果区间起点
    auto res_begin = std::find_if(key_range_begin, key_range_end, 
        [&target_val](const auto& kv) { return kv.second == target_val; });
    // 定位第一个值不匹配的迭代器，作为结果区间终点
    auto res_end = res_begin;
    while (res_end != key_range_end && res_end->second == target_val) {
        ++res_end;
    }

    // 计算匹配数量
    size_t match_count = std::distance(res_begin, res_end);
    std::cout << "键值对(" << target_key << ", " << target_val << ")出现次数：" 
              << match_count << std::endl; // 输出结果为2，符合预期
    return 0;
}

更高性能的可选方案 #

如果场景需要频繁做键+值的组合查询，对性能要求更高，可以根据业务特性选择替代存储结构：

• 不需要保留同键值对的插入顺序、仅需要统计出现次数时，直接用std::map<std::pair<Key, Value>, size_t>存储，键为完整的键值对，值为出现次数，单查询时间复杂度O(log n)
• 需要保留重复键值对的插入顺序、且查询频率远高于插入频率时，可以在插入元素时额外维护一个辅助哈希索引，记录每个键值对对应的起止迭代器，查询时直接读索引即可，时间复杂度O(1)，但插入、删除元素时需要同步更新索引，维护成本更高

注：C标准库目前没有提供直接对multimap同时按键、值匹配返回范围的现成接口，上述两步法是工业界最通用的实现方式，没有额外依赖，兼容性覆盖所有C11及以上版本。

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