| Thread overview | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
|
February 16 Why is DList insertion log n? | ||||
|---|---|---|---|---|
| ||||
 | 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 | |||
February 16 Re: Why is DList insertion log n? | ||||
|---|---|---|---|---|
| ||||
 Posted in reply to Ian | 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 | |||
February 16 Re: Why is DList insertion log n? | ||||
|---|---|---|---|---|
| ||||
 Posted in reply to Ian | 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 | |||
February 16 Re: Why is DList insertion log n? | ||||
|---|---|---|---|---|
| ||||
 Posted in reply to rkompass | 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) ? Apparently this link on the doc web page is how you submit an issue: It doesn't jump out at me as an existing issue. Andy | |||
February 17 Re: Why is DList insertion log n? | ||||
|---|---|---|---|---|
| ||||
 Posted in reply to Andy Valencia | 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 | |||
February 16 Re: Why is DList insertion log n? | ||||
|---|---|---|---|---|
| ||||
 Posted in reply to rkompass | 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
| |||
6 days ago Re: Why is DList insertion log n? | ||||
|---|---|---|---|---|
| ||||
 Posted in reply to Jonathan M Davis | 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.
| |||
6 days ago Re: Why is DList insertion log n? | ||||
|---|---|---|---|---|
| ||||
 Posted in reply to rkompass | 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 Fix to match | |||
6 days ago Re: Why is DList insertion log n? | ||||
|---|---|---|---|---|
| ||||
Posted in reply to rkompass | 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 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). | |||
Permalink
Reply
