基于字符串与数值范围键的C++数据结构选型与实现问询

一、标准库组合实现（无需自行造轮子） #

你可以直接用C++标准库的容器组合来满足需求，核心是两层结构：

1. 第一层：名称到表的映射
   用std::unordered_map<std::string, TableType>或std::map<std::string, TableType>：

   • 追求极致查询性能选std::unordered_map（平均O(1)查找）；
   • 需要名称有序则用std::map（O(log n)查找）。
     其中TableType是单张表的类型，用于存储数值范围到字符串的映射。

2. 第二层：数值范围到字符串的映射
   基于你的示例，范围是不重叠且有序的，推荐用std::map<int, std::string>：

   • 把每个范围的左边界作为键，对应字符串作为值；
   • 查询时用std::map::upper_bound找到第一个大于目标数值的键，迭代器回退一位即可得到所属范围的字符串；
   • 例如Table1存储为{5: "Apple", 25: "Boat", 60: "Cow"}，查询15时，upper_bound(15)指向25，回退后就得到5对应的"Apple"。
     注意：如果范围不是“下一个左边界-1等于当前右边界”的连续结构，需要额外存储右边界并做合法性校验。

示例代码片段 #

#include <unordered_map>
#include <map>
#include <string>
#include <stdexcept>

// 单张表的类型定义
using RangeTable = std::map<int, std::string>;

// 全局的名称-表映射
std::unordered_map<std::string, std::shared_ptr<RangeTable>> tableMap;

// 初始化数据
void initTables() {
    // 初始化Table1，对应名称["One", "Two"]
    auto table1 = std::make_shared<RangeTable>();
    (*table1)[5] = "Apple";
    (*table1)[25] = "Boat";
    (*table1)[60] = "Cow";
    tableMap["One"] = table1;
    tableMap["Two"] = table1; // 多名称共享同一张表，避免内存复制

    // 初始化Table2，对应名称["Three"]
    auto table2 = std::make_shared<RangeTable>();
    (*table2)[5] = "Air";
    (*table2)[25] = "Bard";
    (*table2)[60] = "Camera";
    tableMap["Three"] = table2;
}

// 查询函数
std::string query(const std::string& name, int value) {
    // 第一步：通过名称找对应表
    auto tableIt = tableMap.find(name);
    if (tableIt == tableMap.end()) {
        throw std::invalid_argument("无效的表名称");
    }
    const RangeTable& table = *(tableIt->second);

    // 第二步：通过数值找对应范围的字符串
    auto rangeIt = table.upper_bound(value);
    if (rangeIt == table.begin()) {
        throw std::invalid_argument("数值不在任何范围内");
    }
    --rangeIt;
    // 若需验证右边界，可在这里添加判断（比如value <= 当前范围的右边界）
    return rangeIt->second;
}

二、进阶优化建议 #

• 如果范围固定不修改，可将每个表的范围数据存入有序数组，用std::lower_bound/std::upper_bound做二分查找，内存连续性更好，缓存命中率更高，性能优于std::map；
• 若需动态增删范围，std::map的O(log n)操作已足够高效，无需自行实现平衡树；
• 多名称共享同一张表时，用std::shared_ptr存储表对象，避免重复复制数据浪费内存。

三、第三方库选项 #

C++标准库没有直接提供“数值范围映射”容器，但Boost库的boost::icl（区间容器库）可直接处理区间到值的映射。不过如果只是简单需求，用标准库组合已足够，没必要引入第三方依赖。

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