Implementing Bentley-Ottmann in C++ using the STL

I want to implement the Bentley-Ottmann line segment crossing algorithm based on this description, using STL elements.

What I am struggling with is the implementation of the priority queue. The description asks me to erase any intersection:

If p is the left endpoint of a line segment s, insert s into T. Find the segments r and t that are immediately below and above s in T (if they exist) and if their crossing forms a potential future event in the event queue, remove it. If s crosses r or t, add those crossing points as potential future events in the event queue UPSers.

It doesn't seem to be possible to use an STL priority queue as the event queue, since its searching complexity is linear and I would need to find and remove any crossing of s and t. Should I use a set instead? Or is it possible with a priority queue?

Parents Reply Children
No Data