Nicolas Alvarez <nic### [at] gmailcom> wrote:
> Warp wrote:
> >> (And that you can *query the size* of an array?)
> > 
> >   Getting the size of a vector, string, deque and binary tree is O(1).
> > (For doubly-linked lists it's not guaranteed.)

> And libstdc++ developers decided to keep list::size as O(n) as a tradeoff
> (otherwise mutating operations would have to keep the size up-to-date,
> making *them* slower).

  It's perfectly possible to have an O(1) size() function *and* O(1) splicing,
with the only price to pay that immediately after a splice (one where the
list cannot know how many elements were spliced) size() becomes an O(n)
operation once (but O(1) in subsequent calls).

  I really don't understand why standard library developers are not doing
that. I have been studying the problem and can't see any rational reason
not to do that. Some sacrifice the speed of size() to get a constant-time
splice(), others do the other way around, but I have never heard of an
implementation like the one I describe, even though it's perfectly
possible. It's not only possible, it's rather trivial to do. (I have even
tested it myself in practice. There's no problem with it.)

  Go figure.

-- 
                                                          - Warp

Post a reply to this message