sorting std.container

[Steven Schveighoffer via Digitalmars-d-learn]

On 7/12/16 1:05 AM, WhatMeWorry wrote:
> On Monday, 11 July 2016 at 19:07:51 UTC, ketmar wrote:
>> list slices are not random-access ranges, thus they can't be sorted
>> in-place (this is what std.algorithm.sort does). so the only way is to
>> convert list to array, sort it, and make a list from sorted array.
>> probably not something you want. ;-)
>>
>> this is common for any "traditional" linked list implementation:
>> random access is very costly, thus even if it is implemented, it's
>> better to not use it. SList and DList are "traditional" lists without
>> any fancy algorithms inside (like finger trees or skip lists).
>>
>> you may want to use arrays instead (it is often more efficient anyway,
>> especially if you don't need to insert elements in the middle of the
>> array), or associative arrays.
>
> If I may deviate from the discussion a bit,are there any real world
> scenarios where the SList and DList (that is, "traditional" linked
> lists) is superior to fixed, dynamic or associative arrays?

IMO, singly linked lists are almost always better as home-grown types. 
This is because there is too much overhead for a generic "list", and it 
almost never does everything you need it to. Just about the only real 
good use for a generic singly-linked list is a stack, though arrays can 
cover that. Where singly-linked lists may be better is if you are moving 
pre-allocated nodes onto the stack and don't want to allocate space for 
them (or change their address). Again, a home-grown version will do 
better here too.

A dual-linked list, on the other hand, is not as easy to write, and 
functions well as a generic container. With O(1) front/back insertion 
and O(1) front/back removal, it makes a great base for a FIFO queue.

-Steve