如何在存储坐标距离的std::set中按指定x1、x2查询对应距离

首先明确前提：std::set 默认使用 std::less<std::array<double,5>> 作为排序规则，会按数组下标0到4的顺序依次比较元素（即先比x1，再y1，再x2，再y2，最后比distance），原生不支持直接按x1、x2两个字段快速查找，以下是几种可行方案：

方案1：全量遍历匹配（实现最简单，适合数据量小的场景） #

直接遍历set中所有元素，匹配x1、x2字段后返回对应distance。注意double类型存在精度误差，不能直接用==比较，需要设置误差阈值epsilon

#include <cmath>
double get_distance(double x1, double x2, loc_distances const& set) {
    constexpr double eps = 1e-9; // 可根据实际精度需求调整
    for (const auto& item : set) {
        if (std::fabs(item[0] - x1) < eps && std::fabs(item[2] - x2) < eps) {
            return item[4];
        }
    }
    // 没找到的情况可根据需求处理，比如抛异常、返回NAN等
    return NAN;
}

优缺点：实现零成本，不需要修改原有存储逻辑；缺点是时间复杂度O(n)，数据量大时性能差。

方案2：自定义set排序规则（查询效率更高，适合查询频繁的场景） #

如果可以修改loc_distances的定义，自定义排序规则让set优先按x1、x2排序，就能用set::lower_bound/set::upper_bound快速定位目标区间，时间复杂度降到O(logn)

// 自定义比较器，优先比较x1、x2
struct CoordCmp {
    constexpr bool operator()(const coord_distance& a, const coord_distance& b) const {
        constexpr double eps = 1e-9;
        if (std::fabs(a[0] - b[0]) > eps) return a[0] < b[0];
        if (std::fabs(a[2] - b[2]) > eps) return a[2] < b[2];
        // 剩下字段比较保证严格弱序即可
        if (std::fabs(a[1] - b[1]) > eps) return a[1] < b[1];
        if (std::fabs(a[3] - b[3]) > eps) return a[3] < b[3];
        return a[4] < b[4] - eps;
    }
};
// 修改loc_distances定义
typedef std::set<coord_distance, CoordCmp> loc_distances;

// 此时get_distance可以用二分查找实现
double get_distance(double x1, double x2, loc_distances const& set) {
    constexpr double eps = 1e-9;
    // 构造下界哨兵：x1、x2为目标值，其余字段取最小值
    coord_distance lower = {x1 - eps, -INFINITY, x2 - eps, -INFINITY, -INFINITY};
    auto it = set.lower_bound(lower);
    if (it != set.end() && std::fabs((*it)[0] - x1) < eps && std::fabs((*it)[2] - x2) < eps) {
        return (*it)[4];
    }
    return NAN;
}

优缺点：查询效率高，适合数据量大、查询频繁的场景；缺点是需要修改原有set的定义，已有存量数据的场景改造成本高。

方案3：更换存储容器（最优性能方案，适合新开发场景） #

如果可以调整存储结构，直接用std::map<std::pair<double, double>, double>存储，key为(x1,x2)，value直接存distance，查找复杂度为O(logn)，如果不需要排序也可以用std::unordered_map做到平均O(1)查找。

// 新存储结构定义
#include <map>
typedef std::pair<double, double> CoordKey;
// 如需处理浮点精度问题，可给map传入自定义比较器，逻辑同方案2的CoordCmp
typedef std::map<CoordKey, double> loc_distances;

// 插入示例
loc_distances[{1,5}] = sqrt(pow(5-1,2) + pow(6-4,2)); // key为(x1,x2)，value为distance

// get_distance实现
double get_distance(double x1, double x2, loc_distances const& map) {
    auto it = map.find({x1, x2});
    if (it != map.end()) return it->second;
    return NAN;
}

优缺点：查找逻辑最简洁，性能最优；缺点是需要完全调整原有存储结构，存量代码改造成本最高。

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