How should I sort a doubly linked list the D way?

Mike Parker aldacron at
Tue Aug 13 23:39:04 UTC 2019

On Tuesday, 13 August 2019 at 22:12:23 UTC, Mirjam Akkersdijk 

> Though, it left me with some semi-offtopic questions unanswered:
> (1) Ali, do you mean that from an optimization viewpoint, it's 
> better to keep appending like `nodes ~= ...` instead of setting 
> the length first? I would like to have some more background on 
> that claim.

He's not saying it will be better, but that the cost will be 
negligible. On every append, the GC allocates new memory only if 
the current capacity == 0. When it does allocate, it allocates 
more space than it actually needs based on the current length of 
the array, so you don't actually have an allocation on every 
append. Also, when the adjacent memory block is free and can hold 
the additional elements, the allocation consists of extending the 
array's memory block and no copying is performed, making the cost 
of the allocation even cheaper than it could be.

Anyway, you can use `reserve` when appending rather than setting 
the length. This will allocate enough memory without 
default-initializing anything and you don't have to worry about 
bounds checking.

int[] ints;
foreach(i; 0..100) {
     ints ~= i;

See Steve Schveighoffer's array article for details:

More information about the Digitalmars-d-learn mailing list