get number of items in DList

[Jonathan M Davis via Digitalmars-d-learn]

On Fri, 11 Jul 2014 07:46:37 -0700
"H. S. Teoh via Digitalmars-d-learn"
<digitalmars-d-learn at puremagic.com> wrote:
> On Fri, Jul 11, 2014 at 10:23:58AM -0300, Ary Borenszweig via
> Digitalmars-d-learn wrote:
> > On 7/11/14, 4:46 AM, bearophile wrote:
> > >pgtkda:
> > >
> > >>How can i get the number of items which are currently hold in a
> > >>DList?
> > >
> > >Try (walkLength is from std.range):
> > >
> > >mydList[].walkLength
> > >
> > >Bye,
> > >bearophile
> >
> > So the doubly linked list doesn't know it's length? That seems a bit
> > inefficient...
>
> It should be relatively simple to write a wrapper that *does* keep
> track of length.
>
> The main problem, though, comes from list splicing: given two
> arbitrary points in the list, if you splice out the section of the
> list in between, there's no easy way to know how many items lie in
> between, so you'll have to walk the list to recompute the length
> then. Which sorta defeats the purpose of having a linked list. :)

You can either make a doubly-linked list which is efficient for splicing or
efficient for getting the length, not both. It's trivial to build a linked
list type which knows its length efficiently around one which splices
efficiently, but not the other way round.

C++98 went with one which spliced efficiently but then made the mistake of
providing size(), and people kept using it, thinking that it was O(1), when it
was O(n). C++11 silently switched it to so that size() is O(1) and splicing is
inefficient (which I object to primarily on the grounds that it was silent). D
went the route of making splicing efficient but not providing length/size so
that folks don't accidentally think that it's O(1), when it's actually O(n).
Having to use walkLength makes it more explicit.

That being said, we should probably consider making a wrapper type for
std.container which wraps DList and has O(1) length, allowing folks to choose
which they want based on the requirements of their program. That way, we get
the best of both worlds.

- Jonathan M Davis