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

From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2006-10-30 17:39:47

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.

The name must encompass "Sequence container with O(log n) random
access _and_ O(log n) insertion/removal (wherever)" (the subject line
conveniently enough), and in hindsight, none of my suggestions cover
everything the author wants to convey.

> 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 don't think so.  I'm pretty sure RandomAccess only means that the
iterator supports the required arithmetic syntax, i.e. ++iter, iter++,
iter + n, iter += n.  I am by no means an iterator guru.

> I guess I felt guilty that I brought up the naming issue, even though
> he subsequently mentioned he was looking for a better name, because it
> derailed the topic to some degree.  What I meant to say was that
> focusing on reading through and commenting on his implementation is
> probably a higher priority, and the name discussion should either be
> happening parallel to that or it should be put on the back burner.

Agreed.

> My apologies if the statement sounded accusatory.

None necessary, I only responded to clarify that my e-mail was merely
a humble suggestion.

--Michael Fawcett