Re: [boost] [proposal] Sequence container with O(log n) randomaccess _and_ O(log n) insertion/removal (wherever)

From: Martin Knoblauch Revuelta (mkrevuelta_at_[hidden])
Date: 2006-10-30 19:05:44

On 10/30/06, Jason Hise <0xchaos_at_[hidden]> wrote:
> On 10/30/06, Michael Fawcett <michael.fawcett_at_[hidden]> wrote:
> > How about ra_sequence?
>
> Random access sequence sounds like the definition of vector more than
> a new container type.  Actually, I wonder if it is even valid to say
> that this container supports random access... although it supports the
> syntax for it, isn't random access defined as being constant time?

I think I read that somewhere too.

> > > Perhaps it would be best to leave the ultimate decision up to the
> > > library author, who came up with the idea and may want the privlege of
> > > choosing a name for it.  If he would prefer to leave the decision to
> > > group concensus, we could put the name to a vote.
> >
> > It seemed like the author was asking for suggestions.  I can't speak
> > definitively for the others, but I don't think anyone was presuming to
> > name the library for him.

Oh, sorry. I was actually asking for help in the naming issue (too).

> [..]
> focusing on reading through and commenting on his implementation is
> probably a higher priority, [..]

Yes, I'd love to read your comments about both, interface and
implementation. I still have not written a separate documentation, but
you will find _lots_ of comments (really). So, what should I change in
first place?   ;-)

Back to the naming issue, and more important: another precedent of the
idea in boost, "order-statistics trees" together with "ranked indices"
are the names used in the "future work" section of multi_index
documentation:
http://www.boost.org/libs/multi_index/doc/future_work.html#ranked_indices
>From there: http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree

Though, I can't see how is it related to "Order statistic" (I'm not a
mathematician):
http://en.wikipedia.org/wiki/Order_statistics#Computing_order_statistics

Thanks in advance,
Martin