Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at