digitalmars.D.learn - get number of items in DList
- pgtkda (2/2) Jul 11 2014 How can i get the number of items which are currently hold in a
- bearophile (5/7) Jul 11 2014 Try (walkLength is from std.range):
- Ary Borenszweig (3/9) Jul 11 2014 So the doubly linked list doesn't know it's length? That seems a bit
- bearophile (12/14) Jul 11 2014 Have you tried to compile mydList.length or mydList[].length? If
- H. S. Teoh via Digitalmars-d-learn (11/26) Jul 11 2014 It should be relatively simple to write a wrapper that *does* keep track
- pgtkda (4/35) Jul 14 2014 I just wanted to use a DList because you can easily add new items.
- Jonathan M Davis via Digitalmars-d-learn (19/43) Jul 15 2014 On Fri, 11 Jul 2014 07:46:37 -0700
How can i get the number of items which are currently hold in a DList?
Jul 11 2014
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
Jul 11 2014
On 7/11/14, 4:46 AM, bearophile wrote:pgtkda:So the doubly linked list doesn't know it's length? That seems a bit inefficient...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
Jul 11 2014
"bearophile" <bearophileHUGS lycos.com> Ary Borenszweig:So the doubly linked list doesn't know it's length? That seems a bit inefficient...Have you tried to compile mydList.length or mydList[].length? If both don't compile, then you have to walk the items. Walking the items is not efficient, but: - Linked lists are very uncommonly needed. In 98-99% of cases an array of items or an array of pointers is better (faster for all operations, more efficient for memory used, leading to smaller binary, more compatible with other APIs, and so on). - Most functional algorithms that work on lists do not need to know the length of the list. Bye, bearophile
Jul 11 2014
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: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. :) T -- Valentine's Day: an occasion for florists to reach into the wallets of nominal lovers in dire need of being reminded to profess their hypothetical love for their long-forgotten.pgtkda:So the doubly linked list doesn't know it's length? That seems a bit inefficient...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
Jul 11 2014
On Friday, 11 July 2014 at 14:48:26 UTC, H. S. Teoh via Digitalmars-d-learn wrote:On Fri, Jul 11, 2014 at 10:23:58AM -0300, Ary Borenszweig via Digitalmars-d-learn wrote:I just wanted to use a DList because you can easily add new items. The walkLength property works perfectly, thank you.On 7/11/14, 4:46 AM, bearophile wrote: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. :) Tpgtkda:So the doubly linked list doesn't know it's length? That seems a bit inefficient...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
Jul 14 2014
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: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 DavisOn 7/11/14, 4:46 AM, bearophile wrote: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. :)pgtkda:So the doubly linked list doesn't know it's length? That seems a bit inefficient...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
Jul 15 2014