Changing the comparator's parameter in the C++ multiset

Question

I want to implement Bentley-Ottman algorithm to find all intersections between the line segments. I was using this tutorial: https://www.hackerearth.com/practice/math/geometry/line-intersection-using-bentley-ottmann-algorithm/tutorial/ Unfortunately they don't say how to find the segment above and below when inserting a new leftpoint of a segment. I wanted to have a structure that enables O(logn) segment insertion, find and deletion, so each new leftpoint can be inserted quickly. I thought a multiset would be a good data structure to do it, but I have a problem with sorting the segments properly in my multiset. For example I can have 5 lines that start at X=0 and their Y are (0,1,2,6,7). Inserting them is easy. Then I have the next segment that starts at X=1 and Y=3. It seems that it should be placed between 2 and 6 but it is not true. The line that was at (0,2) is now at (1,4) and therefore is above the new line that is at (1,3).

I want to have a multiset of lines in C++. The lines should be compared based on their Y value that is calculated as:
line.A*X+line.B
X is the parameter that can change.

I want to insert a few elements with let's say X=1 and then change the X to 10. I am 100% sure that this change won't change the order of the elements in the multiset. I know that in this particular case it does change, but I did it on purpose to see whether the change of a comparator works.
Then I want to insert the fifth line that for example would be on the 3rd place if X were still 1 but after the change that I want (X=10) it will be at 5th place.

This is my code:

#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;
}

And it does not work because it still inserts this line as if X=1.

My main goal is to maintain O(logn) complexity for inserting and deleting so, for example making new multiset every time X is changed is not and option. The same problem is with storing the Y values in the line objects, because it would be a lot of updating.

I would be grateful if you show me another data structure that is capable of doing such things if for example it cannot be done in the multiset.

Answer 1

The method you call here:

myMultiset.value_comp() = LineComparator(10);

is (cf cppreference):

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

It is a const method that returns the comparator by value. It cannot be used to change the comparator of the map. Modifying the comparator on the map would break its invariants.

I am 100% sure that this change won't change the order of the elements in the multiset.

Even if you are sure that the order will not change, the multimap has no way to ensure correct order after you changed the comparator (assumed you could). And when order does change, it would have to rebuild the whole container which would be a rather expensive operation.

I am not sure if I understand your original problem. Maybe instead of storing the lines in a map and keep the map sorted, you could populate a 2D container containing for each combination of two lines L1 and L2 the X such that L1(X) == L2(X) together with a bool to indicate whether for some positive delta either L1(X+delta) > L2(X+delta) or the opposite. This 2D structure needs to be populated once and can aid to order the lines for any given X.