C++ multiset比较器参数动态修改问题及Bentley-Ottman适配

问题背景 #

我在实现Bentley-Ottman算法以找出所有线段交点时，遇到了一个关键问题：插入新线段左端点时，需要快速找到上下相邻的线段，因此需要支持O(logn)插入、查找、删除操作的数据结构。我选择了C++的multiset，但遇到了线段排序的动态更新问题。

举个实际场景：5条起点在X=0、初始Y值为(0,1,2,6,7)的线段插入后，新增一条起点在X=1、初始Y=3的线段——从初始Y值看似乎应该放在Y=2和Y=6之间，但实际上原Y=2的线段在X=1处的Y值为4，位于新线段上方，因此排序逻辑需要基于当前X位置的线段Y值（计算公式为Y = line.A*X + line.B）动态调整。

尝试的方案及问题 #

我尝试使用带动态X参数的比较器来实现multiset的排序，但修改X参数后，新插入的元素仍然按照旧的X值排序，测试代码如下：

#include <iostream>
#include <set>

struct line {
    int A;
    int B;
};

struct LineComparator {
    int X;

    LineComparator(int x) : X(x) {}

    bool operator()(const line& lhs, const line& rhs) const {
        int y_lhs = lhs.B + lhs.A * X;
        int y_rhs = rhs.B + rhs.A * X;
        return y_lhs < y_rhs;
    }
};

int main() {
    std::multiset<line, LineComparator> myMultiset(LineComparator(1)); // 初始X值为1

    // 插入初始线段（基于X=1排序）
    myMultiset.insert({ 1, 5 });
    myMultiset.insert({ 2, 2 });
    myMultiset.insert({ 3, 8 });
    myMultiset.insert({ 4, 2 });

    // 输出当前元素
    std::cout << "Elements in the multiset:" << std::endl;
    for (const line& l : myMultiset) {
        std::cout << "A: " << l.A << ", B: " << l.B << std::endl;
    }

    // 修改X值为10
    myMultiset.value_comp() = LineComparator(10);

    // 插入新线段（期望按X=10排序）
    myMultiset.insert({ 4, 4 });

    // 输出修改X后的元素
    std::cout << "Elements in the multiset:" << std::endl;
    for (const line& l : myMultiset) {
        std::cout << "A: " << l.A << ", B: " << l.B << std::endl;
    }

    return 0;
}

这段代码无法正常工作：修改X为10后插入的新线段，仍然按照X=1的排序逻辑放置。我的核心需求是必须保持O(logn)的插入、删除复杂度，因此每次X变化时重建multiset或更新线段Y值的方案都不可行。

求助需求 #

如果multiset无法实现这种动态排序的需求，希望推荐其他适配的数据结构，或者提供解决该问题的有效思路。

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