Re: [Boost-users] Re: Efficient removal of std::list items

From: Victor A. Wagner Jr. (vawjr_at_[hidden])
Date: 2004-12-20 13:15:51

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.
> >
>Victor A. Wagner Jr. Replied:
> > 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 
> 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_at_[hidden]
>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"