Re: Why is DList insertion log n?
On Sunday, 16 February 2025 at 20:57:58 UTC, rkompass wrote: From the source code at [https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784](https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784) I would say it is O(1), as you expected. So the docs you refer to seem to be not correct in this case. I assume the complexity info did not have the highest priority at creation of the docs. Rather attention was on the usage details. That's fair. So it is O(1) in the end. I was trying and failing to imagine what kind of operation would be happening there to make it O(log n).
Re: Why is DList insertion log n?
On Sunday, 16 February 2025 at 20:57:58 UTC, rkompass wrote: From the source code at [https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784](https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784) I would say it is O(1), as you expected. So the docs you refer to seem to be not correct in this case. I assume the complexity info did not have the highest priority at creation of the docs. Rather attention was on the usage details. Fix to match `SList.insertFront` complexity docs: https://github.com/dlang/phobos/pull/10638
Re: Why is DList insertion log n?
On Monday, 17 February 2025 at 03:39:46 UTC, Jonathan M Davis wrote: On Sunday, February 16, 2025 1:57:58 PM MST rkompass via Digitalmars-d-learn wrote: From the source code at [https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784](https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784) https://vema-star-pt.com/ I would say it is O(1), as you expected. So the docs you refer to seem to be not correct in this case. I Actually, the complexity of each of the operations was a key part of the design, but when you're editing the documentation of a bunch of containers with the same or similar operations, That makes sense. Copy-paste errors are easy to miss, especially when dealing with similar APIs.
Re: Why is DList insertion log n?
On Sunday, February 16, 2025 1:57:58 PM MST rkompass via Digitalmars-d-learn wrote: > From the source code at > [https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784](https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784) > I would say it is O(1), as you expected. > So the docs you refer to seem to be not correct in this case. I > assume the complexity info did not have the highest priority at > creation of the docs. Rather attention was on the usage details. Actually, the complexity of each of the operations was a key part of the design, but when you're editing the documentation of a bunch of containers with the same or similar operations, it's pretty easy to end up with copy and paste errors that you miss. And they were added early enough in Phobos v2 that I don't know if they were reviewed by anyone other than Andrei when he wrote them, which makes it more likely that something would have been missed. - Jonathan M Davis
Re: Why is DList insertion log n?
On 17/02/2025 11:55 AM, Andy Valencia wrote: Apparently this link on the doc web page is how you submit an issue: https://issues.dlang.org/enter_bug.cgi? bug_file_loc=http%3A%2F%2Fdlang.org/phobos/ &component=phobos&op_sys=All&priority=P3&product=D&rep_platform=All&short_desc=%5Bstd.container.dlist%5D&version=D2&bug_severity=enhancement Its on GitHub now. https://github.com/dlang/phobos/issues
Re: Why is DList insertion log n?
On Sunday, 16 February 2025 at 20:57:58 UTC, rkompass wrote: I'm looking at the double linked list in std.containers and it says that insertion in front or back are O(log n). How come they are not O(1) ? From the source code at [https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784](https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784) I would say it is O(1), as you expected. So the docs you refer to seem to be not correct in this case. I assume the complexity info did not have the highest priority at creation of the docs. Rather attention was on the usage details. Apparently this link on the doc web page is how you submit an issue: https://issues.dlang.org/enter_bug.cgi?bug_file_loc=http%3A%2F%2Fdlang.org/phobos/&component=phobos&op_sys=All&priority=P3&product=D&rep_platform=All&short_desc=%5Bstd.container.dlist%5D&version=D2&bug_severity=enhancement It doesn't jump out at me as an existing issue. Andy
Re: Why is DList insertion log n?
On Sunday, 16 February 2025 at 18:46:56 UTC, Ian wrote: Hi, I'm looking at the double linked list in std.containers and it says that insertion in front or back are O(log n). How come they are not O(1) ? https://dlang.org/phobos/std_container_dlist.html#.DList.insertFront Also, is this question more for "General"? I'm a "new user" and "learning" so it made sense here, but I'm learning my way around the forum. Ian From the source code at [https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784](https://github.com/dlang/phobos/blob/master/std/container/dlist.d#L784) I would say it is O(1), as you expected. So the docs you refer to seem to be not correct in this case. I assume the complexity info did not have the highest priority at creation of the docs. Rather attention was on the usage details.
Re: Why is DList insertion log n?
On Sunday, 16 February 2025 at 18:46:56 UTC, Ian wrote: Hi, I'm looking at the double linked list in std.containers and it says that insertion in front or back are O(log n). How come they are not O(1) ? https://dlang.org/phobos/std_container_dlist.html#.DList.insertFront Also, is this question more for "General"? I'm a "new user" and "learning" so it made sense here, but I'm learning my way around the forum. Ian No one actually uses any of them nor reads the code often; but Im pretty sure aa is on team "once you define an api it must never change" and probably over estimated to allow swapping to other academia theatrical ideas or is considering some absurd edge case
