Re: [Boost-users] [multi_index] range selection over composit_key problem

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2008-01-09 04:04:40

"Kowalke Oliver (QD IT PA AS)" ha escrito:

> Hi Joaquín,

[...]

> >   // get all elements with function>=0 and arbitrary active:
> > these do always form
> >   // a range.
> >   std::pair<
> >     idx_type::iterator,
> >     idx_type::iterator
> >   > p(
> >     idx.begin(),
> >     idx.upper_bound( boost::make_tuple(0.0) ) );
> >
> >   // filter out the elements with !active
> >   for ( ; p.first != p.second; ++p.first)
> >     if(p.first->active)
> >       std::cout << p.first->function << " " << std::boolalpha
> > << p.first->active << std::endl;
>
> Would this result in an algorithm complexity of ( n lg n) in the worst case
> (function >= 0 and active == false for all elements)?

AFAICS in the worst case the resulting complexity would be O((log n) + n):
log n to retrieve the initial range and n to traverse it.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo