Hello everybody,

sorry for my bad english(nativ german). D is a very nice language and easy to learn because i am a c# (only private) developer.
The only bad is to find examples is very hard.

My question:
How can i sort a slist or dlist with custom types and lambda expressions?

The sort function from std.algorithm works only with arrays (in my test).

Can give anyone an short example?

Thanks for your help.

George

On Monday, 11 July 2016 at 18:54:44 UTC, George M wrote:
> Hello everybody,
>
> sorry for my bad english(nativ german). D is a very nice language and easy to learn because i am a c# (only private) developer.
> The only bad is to find examples is very hard.
>
> My question:
> How can i sort a slist or dlist with custom types and lambda expressions?
>
> The sort function from std.algorithm works only with arrays (in my test).
>
> Can give anyone an short example?
>
> Thanks for your help.
>
> George

The "tipical" sorting functions (as those in std.algorithm) expect their input to be a RandomAccessRange, while slists and dlists are, by definition, ForwardRanges and BidirectionalRanges respectively. So I'm afraid there's no standard function to order them out-of-the-box.
That's a limitation of many languages (e.g. C++ sort requires a RandomIterator, which  forward_list and list do not provide).

What's the best workaround depends on your exact use case.

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.

p.s. i mean simple D dynamic arrays, like `MyType[] arr;`, not std.array.array. ;-)

On 7/11/16 2:54 PM, George M wrote:
> Hello everybody,
>
> sorry for my bad english(nativ german). D is a very nice language and
> easy to learn because i am a c# (only private) developer.
> The only bad is to find examples is very hard.
>
> My question:
> How can i sort a slist or dlist with custom types and lambda expressions?

No. Those would need merge sort, which I don't think is implemented in there.

-Steve

On Monday, 11 July 2016 at 19:12:13 UTC, ketmar wrote:
> p.s. i mean simple D dynamic arrays, like `MyType[] arr;`, not std.array.array. ;-)

Ok thank you all for the fast help. I will use  Dynamic arrys. For this case my code is working. Super language and super forum :-)

Thanks!!

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?

Or are lists more of a data type exercise?

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