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
