[Issue 4420] insertBack() for SList
http://d.puremagic.com/issues/show_bug.cgi?id=4420 Jonathan M Davis jmdavisp...@gmail.com changed: What|Removed |Added Severity|normal |enhancement -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4420] insertBack() for SList
http://d.puremagic.com/issues/show_bug.cgi?id=4420 Andrei Alexandrescu and...@metalanguage.com changed: What|Removed |Added CC||and...@metalanguage.com --- Comment #1 from Andrei Alexandrescu and...@metalanguage.com 2010-07-04 02:01:26 PDT --- SList can't implement insertBack due to complexity requirements. To append to a list, use lst.insertAfter(lst[], stuff). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4420] insertBack() for SList
http://d.puremagic.com/issues/show_bug.cgi?id=4420 --- Comment #2 from Jonathan M Davis jmdavisp...@gmail.com 2010-07-04 02:40:40 PDT --- Which complexity requirements? I understand that it can't do it as is because that would be O(n). I was pointing out that it kept track of the last element in addition to the first one, it could implement insertBack() in O(1) without needing the extra space per node that a doubly linked list requires. And if it keeps track of the next-to-last node as well, then it can implement popBack() in O(1) as well. Is it that other operations no longer fit the appropriate complexity requirements if it keeps track of the last element in addition to the first? I would think that the other operations would have the same complexity but with (in some cases) a slightly higher constant - as in xO(1) would have a greater value of x rather than becoming O(n) or O(log n) or anything worse than O(1). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4420] insertBack() for SList
http://d.puremagic.com/issues/show_bug.cgi?id=4420 Simen Kjaeraas simen.kja...@gmail.com changed: What|Removed |Added CC||simen.kja...@gmail.com --- Comment #3 from Simen Kjaeraas simen.kja...@gmail.com 2010-07-04 03:24:31 PDT --- (In reply to comment #2) And if it keeps track of the next-to-last node as well, then it can implement popBack() in O(1) as well. How could it? It could popBack once, then you'd need to recalculate next-to-last. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4420] insertBack() for SList
http://d.puremagic.com/issues/show_bug.cgi?id=4420 --- Comment #4 from Jonathan M Davis jmdavisp...@gmail.com 2010-07-04 03:38:29 PDT --- Ah. Good point. I obviously didn't think that one through thoroughly enough. You could popBack() once, but that would be it. Scratch that idea. However, you could still have insertBack() and back() if you kept track of the last element. back() would return that last element and insertBack() would insert after it, adjusting the last element's pointer to its next element to point to the new last element and adjusting the container's pointer to the last element to point to the new last element. So, that should work in O(1), but no popBack() wouldn't work. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4420] insertBack() for SList
http://d.puremagic.com/issues/show_bug.cgi?id=4420 Andrei Alexandrescu and...@metalanguage.com changed: What|Removed |Added Status|NEW |RESOLVED Resolution||WONTFIX --- Comment #5 from Andrei Alexandrescu and...@metalanguage.com 2010-07-04 12:42:42 PDT --- The main selling point of SList is simplicity. Adding all sorts of storage aides is possible but would work against SList's charter. Feel free to propose a new type based on SList in an enhancement proposal. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 4420] insertBack() for SList
http://d.puremagic.com/issues/show_bug.cgi?id=4420 --- Comment #6 from Jonathan M Davis jmdavisp...@gmail.com 2010-07-04 16:44:47 PDT --- Well, like I said, the addition might not be worthwhile. It would complicate some of the other functions somewhat. It's just that it would be a fairly simple addition to get some extra functionality in comparison to say, a doubly-linked list. I have no problem if you don't think that it's appropriate to add that extra functionality to SList. I just thought that I'd point it out in case such a change would be desirable and the idea hadn't occurred to you. Personally, in my code, I'd generally just as soon use a doubly-linked list in most cases if I'm going to use a list. But SList as-is definitely has its uses, and a doubly-linked list is overkill for some situations. It probably isn't worth creating a separate SList class with just the additions to support back() and insertBack() though. In any case, this was just a suggestion, and if you don't want to use it, that's fine by me. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
