On Fri, 11 Jul 2014 07:46:37 -0700 "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn@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