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

From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2006-10-28 13:57:57

> 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.

As for the compaction of elements in width, it seems to fit with the  
framework of weighted data structures.  There is  quite a body of  
work focussing on the entropy function (where the weights describe  
some probability of access), but that's not what you have here, where  
the weights describe the number of elements/representatives.  But  
that seems to fit with weight-balanced trees and the like.

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.  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.)
--
Hervé Brönnimann
CIS Polytechnic University