www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Static arrays and std.algorithm.sort

reply "D Apprentice" <j teamraging.com> writes:
Greetings, D wizards.

Given a static array, int[5] a, presumed to be filled with random
numbers, how does one sort it using std.algorithm.sort? Calling
sort(a) by itself errors out with:

test.d(7): Error: template std.algorithm.sort does not match any
function template declaration. Candidates are:
/usr/share/dmd/src/phobos/std/algorithm.d(8387):
std.algorithm.sort(alias less = "a < b", SwapStrategy ss =
SwapStrategy.unstable, Range)(Range r) if ((ss ==
SwapStrategy.unstable && (hasSwappableElements!Range ||
hasAssignableElements!Range) || ss != SwapStrategy.unstable &&
hasAssignableElements!Range) && isRandomAccessRange!Range &&
hasSlicing!Range && hasLength!Range)
test.d(7): Error: template std.algorithm.sort(alias less = "a <
b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r) if
((ss == SwapStrategy.unstable && (hasSwappableElements!Range ||
hasAssignableElements!Range) || ss != SwapStrategy.unstable &&
hasAssignableElements!Range) && isRandomAccessRange!Range &&
hasSlicing!Range && hasLength!Range) cannot deduce template
function from argument types !()(int[5])

This is a general interest question. As I understand it, D static
arrays are value types, as opposed to their dynamic siblings
which are reference types, and I suspect that is the underlying
issue here.

One little idiom I found, though I do not know if it's very
efficient, is using the array slice syntax:

sort (a[0..a.length]);

This works, but I'm curious if there's another (better) way? The
biggest advantage that I can see to the slice syntax is that it
allows the programmer to sort only part of the array, which one
could do in C with qsort.

Source:

import std.stdio;
import std.algorithm;

void main ()
{
	int[5] a = [9, 5, 1, 7, 3];
	//sort (a); //Fails
	//sort (a[0..a.length]); //Works
	writeln (a);
}

Thank you for your time.
Feb 20 2014
next sibling parent reply "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
On Thursday, 20 February 2014 at 17:24:55 UTC, D Apprentice wrote:

 This works, but I'm curious if there's another (better) way?
sort(a[]);
Feb 20 2014
parent reply "D Apprentice" <j teamraging.com> writes:
On Thursday, 20 February 2014 at 17:29:44 UTC, Stanislav Blinov
wrote:
 On Thursday, 20 February 2014 at 17:24:55 UTC, D Apprentice 
 wrote:

 This works, but I'm curious if there's another (better) way?
sort(a[]);
That's still using the slice syntax though? I just reread the documentation and it says that slicing does not copy any data, so there shouldn't be any issues with this method. But I'm curious, are there any other known ways, or is this the only one? Thank you for your reply.
Feb 20 2014
next sibling parent "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
On Thursday, 20 February 2014 at 17:34:37 UTC, D Apprentice wrote:
 On Thursday, 20 February 2014 at 17:29:44 UTC, Stanislav Blinov
 wrote:
 sort(a[]);
That's still using the slice syntax though? I just reread the documentation and it says that slicing does not copy any data, so there shouldn't be any issues with this method.
Yup.
 But I'm curious, are there any other known ways, or is
 this the only one?
No. To be honest, I'm not fully agreeing with sort(a) not working too, but it seems unlikely it'd be supported. See http://d.puremagic.com/issues/show_bug.cgi?id=4114
Feb 20 2014
prev sibling parent reply "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
Note that you can create your own overload. Though it has to be 
done "the long way", because dmd doesn't (yet?) allow overloading 
templates imported from other modules:

import std.stdio;
import std.algorithm;
import std.traits;

template sort(alias less = "a < b", SwapStrategy ss = 
SwapStrategy.unstable)
{
     auto sort(Arr)(ref Arr arr) if (isStaticArray!Arr) {
         return std.algorithm.sort!(less, ss)(arr[]);
     }

     auto sort(Range)(Range r) if (!isStaticArray!Range) {
         return std.algorithm.sort!(less, ss)(r);
     }
}

void main ()
{
     int[5] a = [ 9, 5, 1, 7, 3 ];
     int[]  b = [ 4, 2, 1, 6, 3 ];

     sort(a);
     sort(b);
     writeln(a);
     writeln(b);
}
Feb 20 2014
parent "Jesse Phillips" <Jesse.K.Phillips+D gmail.com> writes:
On Thursday, 20 February 2014 at 18:33:02 UTC, Stanislav Blinov 
wrote:
 Note that you can create your own overload. Though it has to be 
 done "the long way", because dmd doesn't (yet?) allow 
 overloading templates imported from other modules:
Guess we will find out: https://d.puremagic.com/issues/show_bug.cgi?id=12216
Feb 20 2014
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
I believe the problem is that std.algorithm.sort requires a
range, and fixed-size arrays are not ranges in D. I believe it's
because the most basic range functionality is the ability to do
this:

int[] arr = [0, 1, 2, 3];
while (arr.length > 0)
{
      arr = arr[1..arr.length];
}

In other words, shrink the range size, which is obviously not
possible with a fixed-size array, since its size is... fixed. The
reason your example code works:

void main ()
{
	int[5] a = [9, 5, 1, 7, 3];
	//sort (a); //Fails
          //Note that `a[0..a.length]` is equivalent to the shorter
syntax `a[]`
	//sort (a[0..a.length]); //Works
	writeln (a);
}

Is because while int[5] is not a range, int[] *is* a range, as I
demonstrated above. Although int[5] is not a range, you can
obtain a range "view" of it with the square brackets syntax. This
is referred to as slicing. The following are all valid slices of
an int[5]:

int[5] arr = [0, 1, 2, 3];
auto slice1 = arr[0..$]; //$ means arr.length in this context.
                           //slice1 == [0, 1, 2, 3]

auto slice2 = arr[1..$]; //slice2 == [1, 2, 3]

auto slice3 = arr[1..3]; //slice3 == [1, 2]

auto slice4 = arr[0..0]; //slice4 == [] empty slice, length == 0
but ptr != null
Feb 20 2014
prev sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 20 February 2014 at 17:24:55 UTC, D Apprentice wrote:
 Greetings, D wizards.

 Given a static array, int[5] a, presumed to be filled with 
 random
 numbers, how does one sort it using std.algorithm.sort? Calling
 sort(a) by itself errors out with:

 test.d(7): Error: template std.algorithm.sort does not match any
 function template declaration. Candidates are:
 /usr/share/dmd/src/phobos/std/algorithm.d(8387):
 std.algorithm.sort(alias less = "a < b", SwapStrategy ss =
 SwapStrategy.unstable, Range)(Range r) if ((ss ==
 SwapStrategy.unstable && (hasSwappableElements!Range ||
 hasAssignableElements!Range) || ss != SwapStrategy.unstable &&
 hasAssignableElements!Range) && isRandomAccessRange!Range &&
 hasSlicing!Range && hasLength!Range)
 test.d(7): Error: template std.algorithm.sort(alias less = "a <
 b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r) if
 ((ss == SwapStrategy.unstable && (hasSwappableElements!Range ||
 hasAssignableElements!Range) || ss != SwapStrategy.unstable &&
 hasAssignableElements!Range) && isRandomAccessRange!Range &&
 hasSlicing!Range && hasLength!Range) cannot deduce template
 function from argument types !()(int[5])

 This is a general interest question. As I understand it, D 
 static
 arrays are value types, as opposed to their dynamic siblings
 which are reference types, and I suspect that is the underlying
 issue here.

 One little idiom I found, though I do not know if it's very
 efficient, is using the array slice syntax:

 sort (a[0..a.length]);

 This works, but I'm curious if there's another (better) way? The
 biggest advantage that I can see to the slice syntax is that it
 allows the programmer to sort only part of the array, which one
 could do in C with qsort.

 Source:

 import std.stdio;
 import std.algorithm;

 void main ()
 {
 	int[5] a = [9, 5, 1, 7, 3];
 	//sort (a); //Fails
 	//sort (a[0..a.length]); //Works
 	writeln (a);
 }

 Thank you for your time.
static arrays are not slices. Using [] gives you a slice from a static array. I often find myself writing this: int[5] aStatic = [9, 5, 1, 7, 3]; auto a = aStatic[]; and just being careful not to leak references.
Feb 21 2014