www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Why is DList insertion log n?

reply Ian <ian iangarcia.net> writes:
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
Feb 16
next sibling parent monkyyy <crazymonkyyy gmail.com> writes:
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
Feb 16
prev sibling parent reply rkompass <rkompass gmx.de> writes:
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.
Feb 16
next sibling parent reply Andy Valencia <dont spam.me> writes:
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
Feb 16
parent "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz> writes:
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
Feb 16
prev sibling next sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
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
Feb 16
parent mig09 <alb94825 gmail.com> writes:
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/con
ainer/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.
Feb 17
prev sibling next sibling parent Nick Treleaven <nick geany.org> writes:
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
Feb 17
prev sibling parent Ian <ian iangarcia.net> writes:
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).
Feb 17