C++如何从键为区间对的map中筛选与给定范围相交的对应值

核心思路 #

• std::map<std::pair<int,int>> 本身按pair的字典序升序排列：优先比较区间左端点，左端点相同再比较右端点。
• 两个区间[s1, e1]（存储的键区间）和[target_s, target_e]（目标查询区间）存在交集的判定条件为：s1 <= target_e && e1 >= target_s（如果是开区间自行调整为</>即可）。
• 无需全量遍历的核心是提前截断右边界：所有左端点大于目标区间右端点的区间，必然和目标区间无交集，可以直接跳过。我们可以用map自带的upper_bound接口快速定位到截断位置，仅遍历截断位置之前的元素即可。

完整实现代码 #

#include <iostream>
#include <map>
#include <climits>
using namespace std;

void printMap(map<pair<int, int>, char> &my_map)
{
    cout << "-----------------------------" << endl;
    for(auto it = my_map.begin(); it != my_map.end(); ++it)
    {
        cout << " key : ( " << it->first.first << ", " << it->first.second << " ) - value : " << it->second << endl;
    }
    cout << "-----------------------------" << endl;
}

int main()
{
    map<pair<int, int>, char> my_map;
    my_map.insert({{1,4}, 'a'});
    my_map.insert({{6,8}, 'b'});
    my_map.insert({{7,10}, 'c'});
    my_map.insert({{14,16}, 'd'});
    my_map.insert({{18,23}, 'e'});

    // 目标查询区间
    int target_s = 7, target_e = 9;
    // 快速定位右边界：第一个左端点大于target_e的区间位置，后面的元素全部跳过
    auto end_it = my_map.upper_bound({target_e, INT_MAX});

    // 仅遍历[begin, end_it)区间的元素，不需要全量遍历整个map
    for (auto it = my_map.begin(); it != end_it; ++it) {
        int s1 = it->first.first;
        int e1 = it->first.second;
        // 判定是否存在交集
        if (s1 <= target_e && e1 >= target_s) {
            cout << "'" << it->second << "'" << endl;
        }
    }

    return 0;
}

输出结果 #

'b'
'c'

优化说明 #

如果需要处理超大规模区间数据，还可以进一步优化左边界：提前过滤掉所有右端点小于目标区间左端点的区间，但因为标准库map仅按区间左端点排序，无法直接通过键查询快速定位左边界，这种场景可以考虑自定义区间排序规则，或者使用专门的区间容器实现更高性能的查询。

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