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

From: Jason Hise (0xchaos_at_[hidden])
Date: 2006-10-28 16:37:21

On 10/28/06, Hervé Brönnimann <hervebronnimann_at_[hidden]> wrote:
> > I woud like a name focused on what it provides: a sequence, random
> > access, insertion/deletion, logarithmic complexity, alternative index
> > derived from the sum of 'widths'...
>
> The technical term which you'll find in accepted text books for the
> ADT is OS-dictionary, or Order-Statistics Dictionary.  Random-access
> dictionary might be just as adequate.  Binary Tree with Rank does not
> speak about the ADT but about its implementation

Doesn't 'dictionary' imply a key-value relationship?  Granted, one can
think of the index as the key, but this key is not bound or related to
the object.  It changes the moment a new object is inserted before it.
 This is not an associative container, it is a sequence.

> On Oct 28, 2006, at 10:37 AM, Jason Hise wrote:
> > I think random access list, or ralist, would be the most technically
> > descriptive.
> >
> > However, perhaps it would be preferable to create an association
> > between an existing word that is currently unused for sequences and
> > this new type of sequence container.  How about chain?
> >
> > vector, deque, chain, list... I think it fits right in.
>
> I've never heard of RALists, which can be implemented in a number of
> ways (Skip lists, Jump lists, binary trees), so I don't think it's a
> very good term.

I don't know that this structure with it's complexity guarantees can
be implemented in multiple different ways... but how does that imply
that the name doesn't fit?  The name describes the advantages of the
container: it is used as a list that supports random access.  I havn't
seen this type of sequence container in widespread use elsewhere, so
why should we expect that there is an existing term to use as a
precident?

> Chain is plain bad, due to its ambiguity with
> chaining (hashing)  and its quasi-synonymity with list in a number of
> contexts (buffer chain, hashing, etc.)

It does not seem to me that this terminology is in conflict.  Chaining
is a verb, and chain is a noun.  So there is no reason that you
couldn't implement chaining with a chain, or with a list, or even with
a vector.  All of these make sense.  In fact, I bet that a hash
container that implemented chaining with a chain instead of a list
might be pretty effective.

Is chain really commonly used as a synonym for linked list?  I havn't
ever encountered that use of the term before.

Although there exist naming precidents for the implementation of this
structure, I don't believe there is a precident for naming its
interface.  As such, my opinion is that it is our responsibility to
invent the terminology.  We should find a name which is short, not
already in use, and implies that this is a sequence (not a tree or
associative container).  Then as more people use it they would come to
associate the term with its complexity guarantees.

-Jason