是否存在可将值映射到键值范围的优秀C++键值数据结构？

你要的这种键到区间映射、返回对应值的需求，有几个现成的方案可以直接用，不用自己从头造轮子：

标准库原生实现（无依赖） #

基于std::map的区间查找是最直接的方案，利用std::map的有序性，结合upper_bound快速定位对应区间：

• 把每个区间的左边界作为std::map的键，对应值存为映射值
• 查找时用upper_bound(key)找到第一个大于key的左边界，前一个迭代器就是key所属区间的映射值
• 注意要保证所有区间左闭右开、不重叠且按左边界排序，必要时可以在添加区间时做合法性检查

示例代码：

#include <map>
#include <stdexcept>
#include <concepts>

template <std::totally_ordered KeyType, typename ValueType>
class IntervalTable {
private:
    std::map<KeyType, ValueType> interval_map_;
    // 存储每个区间的右边界，用于合法性检查
    std::map<KeyType, KeyType> interval_upper_;

public:
    void add_interval(const KeyType& lower, const KeyType& upper, ValueType value) {
        if (lower >= upper) {
            throw std::invalid_argument("区间左边界不能大于等于右边界");
        }
        if (!interval_map_.empty()) {
            auto last = interval_map_.rbegin();
            if (last->first >= lower || interval_upper_.at(last->first) > lower) {
                throw std::invalid_argument("区间重叠或顺序错误");
            }
        }
        interval_map_[lower] = std::move(value);
        interval_upper_[lower] = upper;
    }

    ValueType& get_value(const KeyType& key) {
        auto it = interval_map_.upper_bound(key);
        if (it == interval_map_.begin()) {
            throw std::out_of_range("key超出所有区间范围");
        }
        --it;
        const KeyType& upper = interval_upper_.at(it->first);
        if (key >= upper) {
            throw std::out_of_range("key超出所有区间范围");
        }
        return it->second;
    }
};

第三方库成熟方案 #

如果可以引入第三方库，这些现成组件能省更多事：

• Boost.Interval：Boost专门提供了区间处理的工具集，包含区间容器、重叠检查、高效查找等功能，可以直接基于boost::interval_map实现你的需求，它已经处理了区间的所有边界情况
• Abseil flat_hash_map + 二分查找：如果追求极致性能，把区间左边界和对应值存在排序后的std::vector里，用std::upper_bound做二分查找，再结合Abseil的flat_hash_map做辅助存储（适合静态或极少修改的场景）

轻量自定义实现（无依赖） #

如果不想用std::map的红黑树开销，可以用排序后的std::vector存储区间-值对，每次查找用std::upper_bound做二分查找，时间复杂度同样是O(log n)，比std::map的常数更小，适合数据量固定或修改很少的场景。

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