如何高效获取std::map中部分匹配字符串的上下界迭代器？

因为std::map的键默认按字典序排序，所有匹配指定前缀的键会形成连续区间，我们可以通过lower_bound方法在O(log n)时间内快速定位区间首尾迭代器，无需遍历整个容器。

具体实现步骤 #

1. 确定目标前缀，比如示例中的/abc/x。
2. 构造「前缀的后继字符串」：将前缀的最后一个字符加1（比如/abc/x变为/abc/y）。这个字符串是所有以目标前缀开头的键的最小上界——所有匹配前缀的键都会小于它。
3. 用lower_bound获取区间迭代器：
   • start = myMap.lower_bound(prefix)：找到第一个不小于目标前缀的键（即匹配前缀的第一个键）。
   • end = myMap.lower_bound(upper_prefix)：找到第一个不小于后继字符串的键（即匹配前缀的最后一个键的下一个位置）。
4. 区间[start, end)就是所有匹配指定前缀的键值对范围。

代码示例 #

#include <map>
#include <string>

// 假设你的map定义如下
std::map<std::string, AnyType> myMap;

// 目标前缀
std::string prefix = "/abc/x";
// 构造前缀的后继字符串
std::string upper_prefix = prefix;
upper_prefix.back() += 1;

// 获取范围迭代器
auto range_start = myMap.lower_bound(prefix);
auto range_end = myMap.lower_bound(upper_prefix);

// 遍历处理匹配的键值对
for (auto it = range_start; it != range_end; ++it) {
    // 操作 it->first（键）和 it->second（值）
}

注意事项 #

• 如果前缀最后一个字符是z，加1后会变成ASCII码中z的下一个字符（如{），这依然有效——字典序中{大于所有字母，所有以原前缀开头的键都会小于这个后继字符串。
• 该方法时间复杂度为O(log n)，比遍历整个map的O(n)高效得多，适合大数据量场景。

内容的提问来源于stack exchange，提问作者no one special