如何为vector<vector<double>>实现适用于std::set的稳定小于比较

要实现符合std::set要求的严格弱序比较（保证相等的多边形被视为同一索引），我们需要分层处理嵌套vector的比较，同时解决浮点数精度问题。以下是具体实现步骤：

1. 浮点数的安全比较工具 #

由于浮点数存在精度误差，直接用<或==会导致误判。先定义带epsilon的小于判断：

// 根据业务场景调整epsilon值，比如地理坐标可用1e-6（厘米级）
constexpr double EPS = 1e-9;

// 判断a是否严格小于b（考虑精度）
bool is_less(double a, double b) {
    return (b - a) > EPS;
}

2. 单层vector的比较 #

对两个点序列（比如多边形的外环或孔洞），逐个元素比较，前面元素相等则比较长度：

bool compare_point_sequence(const std::vector<double>& seq1, const std::vector<double>& seq2) {
    const size_t min_len = std::min(seq1.size(), seq2.size());
    for (size_t i = 0; i < min_len; ++i) {
        if (is_less(seq1[i], seq2[i])) {
            return true;
        }
        if (is_less(seq2[i], seq1[i])) {
            return false;
        }
        // 元素相等，继续下一个
    }
    // 前面元素全相等，短序列更小
    return seq1.size() < seq2.size();
}

3. 嵌套vector<vector>的多边形比较 #

按顺序比较每个环（外环优先，然后是孔洞），前面环相等则比较环的数量：

bool compare_polygon(const std::vector<std::vector<double>>& poly1, const std::vector<std::vector<double>>& poly2) {
    const size_t min_ring_count = std::min(poly1.size(), poly2.size());
    for (size_t i = 0; i < min_ring_count; ++i) {
        const auto& ring1 = poly1[i];
        const auto& ring2 = poly2[i];
        if (compare_point_sequence(ring1, ring2)) {
            return true;
        }
        if (compare_point_sequence(ring2, ring1)) {
            return false;
        }
        // 当前环相等，继续下一个环
    }
    // 前面环全相等，环数少的多边形更小
    return poly1.size() < poly2.size();
}

4. 多键索引的比较器（用于std::set） #

假设你的索引元素包含时间戳和多边形，优先按时间排序，时间相等时按多边形排序：

struct IndexedElement {
    double timestamp;
    std::vector<std::vector<double>> polygon;
};

// 自定义比较器，满足std::set的严格弱序要求
struct ElementComparator {
    bool operator()(const IndexedElement& a, const IndexedElement& b) const {
        // 优先比较时间戳
        if (is_less(a.timestamp, b.timestamp)) {
            return true;
        }
        if (is_less(b.timestamp, a.timestamp)) {
            return false;
        }
        // 时间相等，比较多边形
        return compare_polygon(a.polygon, b.polygon);
    }
};

// 使用方式
std::set<IndexedElement, ElementComparator> multi_key_set;

关键注意事项 #

• 严格弱序合规性：上述实现完全满足std::set要求的严格弱序规则，确保!(a < b) && !(b < a)时，a和b被视为相等，对应同一索引。
• epsilon调整：EPS的值必须根据你的业务场景选择，比如处理高精度几何数据时用更小的epsilon，地理数据则用与精度匹配的值。
• 多边形标准化（可选）：如果需要将几何形状相同但点顺序/方向不同的多边形视为相等，需要先对每个环做标准化处理：比如找到环的最小点作为起点，统一顺时针/逆时针方向，再进行比较。

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