On Tuesday, August 13, 2019 3:48:52 AM MDT Mirjam Akkersdijk via Digitalmars-d-learn wrote: > Hello there, > If I had a DLL, how would I sort it judging by the node contents, > the D way? > > In C if I were to sort a piece of malloc'd memory pointing to > node pointers, I would write my compare function and let qsort > sort it out. In D, I tried to use std.algorithm's sort > functionality to no avail, because my guess would be it only > operates on arrays. This opens up another can of worms as I am > not fond of VLAs and D desperately wants to know what the size is > at compile time. > > Let's say we this trivial implementation: > > Node* get_node(DLL* list, uint index); > > struct Node { > int x; > Node* prev, next; > }; > > struct DLL { > Node* head; > uint size; > }; > > Node** nodes = cast(Node**) malloc(DLL.size * (Node*).sizeof); > > and I would like to sort based on Node.t, how should I tackle it, > preferably without resorting to C libraries?
std.algorithm.sort operates on random-access ranges, not just dynamic arrays, and there's no need to know the size at compile time. I don't know why you would think that arrays would need to know their size at compile time unless you've only been using static arrays. However, a doubly-linked list definitely isn't random access, so it wouldn't work with std.algorithm.sort, and I don't think that Phobos has anything which would be able to sort it. There might be a solution somewhere on code.dlang.org, but I don't know of any that I could point you to. Either way, if there's a solution floating around that you can use to sort a doubly-linked list in place, it's not an official one. - Jonathan M Davis