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
