At Monday 2004-12-20 05:42, you wrote:
Victor A. Wagner Jr. wrote:
are the lists sorted?
Cory Nelson wrote:
Yep. If you're going where I think you're going (binary search), I was about halfway through the modifications when I opened the email. Lack of sleep will get to you... :(
Dave Abrahams wrote:
That'll only work if the ranges are non-overlapping. Otherwise you'll need to use an interval tree to avoid an O(N) search for each interval you want to remove.
you're likely correct, but we were looking at handling some stuff with imprecise (error probabilities) results and we were on the track of doing some stuff along these lines. The project was cancelled (shame, I
Victor A. Wagner Jr. Replied: think it
would fit well with the physical quantities systems... you just can't measure things as closely as you'd like) so we never got to see how/if all of the algorithms would work or whether we'd have to specialize them for "fuzzy" numbers.
Have you seen the Boost Interval library?
I think it's worth pursuing for ranges tho.
Why should the OP pursue anything that's likely (your words) to be O(N^2) when there's a known and proven O(N log N) approach?
you know dave, sometimes I think you just like to dis me. you sure as hell don't pay attention to anything I actually write. I never suggested anyone pursue ANY O(N^2) approach. I was SUGGESTING that maybe there is an O(N+M) approach although allowing that perhaps YOU are correct and there isn't. btw, "these lines" referred to my previous message about modifying set_difference() not your silly O(n) search for every interval you want to remove.
-- Dave Abrahams Boost Consulting http://www.boost-consulting.com
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Victor A. Wagner Jr. http://rudbek.com The five most dangerous words in the English language: "There oughta be a law"