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-31 11:19:12

On 10/31/06, Martin Bonner <martin.bonner_at_[hidden]> wrote:
>
> > On 10/30/06, Jason Hise <0xchaos_at_[hidden]> wrote:
>
> >> 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?
> >
> From: Michael Fawcett
> > 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.
>
> Sorry.  Jason is right.  Section 24.1 paragraph 8 of the standard:
>     All the categories of iterators require only those functions that
>     are realizable for a given category in constant time (amortized).
>
> (If there weren't a constant time requirement, there would be no point
> in distinguishing bi-directional iterators from random access iterators.
> bi-directional iterators can always implement += n by repeated
> increment.)

Thanks for the clarification, it makes perfect sense.  That neatly
removes all "random access" suggestions from the name list.   =)

--Michael Fawcett