更改 C++ 多重集中比较器的参数

Question

我想在 C++ 中拥有多行集。应根据各线的 Y 值进行比较，计算公式如下：
线.A*X+线.B
X是可以改变的参数。

我想插入一些元素，假设 X=1，然后将 X 更改为 10。我 100% 确定此更改不会更改多重集中元素的顺序。
然后我想插入第五行，例如，如果 X 仍然是 1，则该行将位于第三位，但在我想要的更改（X=10）之后，它将位于第五位。

这是我的代码：

#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)); // Initial X value of 5

    // Insert some lines with initial X = 1
    myMultiset.insert({ 1, 5 });
    myMultiset.insert({ 2, 2 });
    myMultiset.insert({ 3, 8 });
    myMultiset.insert({ 4, 2 });

    // Print all the elements
    std::cout << "Elements in the multiset:" << std::endl;
    for (const line& l : myMultiset) {
        std::cout << "A: " << l.A << ", B: " << l.B << std::endl;
    }

    // Change X value to 10
    myMultiset.value_comp() = LineComparator(10);

    // Insert a line with updated X = 10
    myMultiset.insert({ 4, 4 });

    // Print all the elements
    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=1 一样。

我的主要目标是保持插入和删除的 O(logn) 复杂度，因此，例如每次 X 更改时创建新的多重集就不是选项。同样的问题是将 Y 值存储在线条对象中，因为这会需要大量更新。

如果您向我展示另一种能够执行此类操作的数据结构（例如，如果它无法在多重集中完成），我将不胜感激。

Answer 1

你在这里调用的方法：

myMultiset.value_comp() = LineComparator(10);

是（参见cppreference）：

std::multiset::value_compare value_comp() const;

这是一个按值返回比较器的

const

方法。它不能用于更改地图的比较器。修改地图上的比较器会破坏其不变量。

我 100% 确定此更改不会改变多重集中元素的顺序。

即使您确定顺序不会改变，多重映射也无法在您更改比较器后确保正确的顺序（假设您可以）。当订单确实发生变化时，就必须重建整个容器，这将是一项相当昂贵的操作。此外，以前被认为等效的元素可能不再等效。地图无法追溯地将它们添加回来。