www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - sorting std.container

reply George M <gemo yahoo.de> writes:
Hello everybody,

sorry for my bad english(nativ german). D is a very nice language 

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
Jul 11 2016
next sibling parent Lodovico Giaretta <lodovico giaretart.net> writes:
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 

 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.
Jul 11 2016
prev sibling next sibling parent reply ketmar <ketmar ketmar.no-ip.org> writes:
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.
Jul 11 2016
next sibling parent reply ketmar <ketmar ketmar.no-ip.org> writes:
p.s. i mean simple D dynamic arrays, like `MyType[] arr;`, not 
std.array.array. ;-)
Jul 11 2016
parent George M <gemo yahoo.de> writes:
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!!
Jul 11 2016
prev sibling parent reply WhatMeWorry <kheaser gmail.com> writes:
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?
Jul 11 2016
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
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
Jul 12 2016
prev sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
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

 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
Jul 11 2016