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

Mirjam Akkersdijk noreply at noreply.com
Tue Aug 13 09:48:52 UTC 2019


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?


More information about the Digitalmars-d-learn mailing list