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

From: Jason Hise (0xchaos_at_[hidden])
Date: 2006-10-30 16:23:13

On 10/30/06, Michael Fawcett <michael.fawcett_at_[hidden]> wrote:
> On 10/30/06, François Duranleau <duranlef_at_[hidden]> wrote:
> > On Mon, 30 Oct 2006, John Maddock wrote:
> >
> > > Giovanni Piero Deretta wrote:
> > >>
> > >> What about log-list or llist (think of SGI's slist)? Or if you want to
> > >> emphatize the random access property, log-array or larray.
> > >
> > > Or "chain", or "random_list",
> >
> > Or then "rlist"?
>
> How about "ra_list" or "ralist" to emphasize "random access" rather
> than just "random"?

I think the reason to perfer a new word to an augmented form of list
is that this really is a new type of sequence.  A singly linked list
(slist in SGI) is a specialization of a linked list that trades some
functionality for some space.  A balanced tree is not a specialization
of a linked list, but a new structure altogether.

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.

-Jason