www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sorting structs?

reply "Boomerang" <nomailforme nomailforme.no> writes:
Hello everybody. I'm trying to learn D by solving simple
exercises.

The current exercise: read names and grades of students, then
print the names of students in descending order of their grades.

In C++, I would define a Student struct, overload the operators:
bool operator<(const Student&, const Student&)
std::istream& operator>>(std::istream&, Student&)

Then I'd store the Students in let's say a std::vector, sort it
in reverse, then print it accordingly.

But I don't know how to do things in D. I'm reading Cehreli's
book, so far I've only finished its first trinity (just before
struct).

I would appreciate it if you explained your approach and gave
source code illustrating it. Thanks!
Jan 29 2014
next sibling parent Benjamin Thaut <code benjamin-thaut.de> writes:
Am 29.01.2014 10:33, schrieb Boomerang:

 Hello everybody. I'm trying to learn D by solving simple
 exercises.

 The current exercise: read names and grades of students, then
 print the names of students in descending order of their grades.

 In C++, I would define a Student struct, overload the operators:
 bool operator<(const Student&, const Student&)
 std::istream& operator>>(std::istream&, Student&)

 Then I'd store the Students in let's say a std::vector, sort it
 in reverse, then print it accordingly.

 But I don't know how to do things in D. I'm reading Cehreli's
 book, so far I've only finished its first trinity (just before
 struct).

 I would appreciate it if you explained your approach and gave
 source code illustrating it. Thanks!


You can either overload the compare operator for the struct

struct bla
{
   int i;
   int opCmp(ref const(bla) rh)
   {
     if(this.i < rh.i)
       return -1;
     if(this.i > rh.i)
       return 1;
     return 0;
   }
}

or you could just pass a different compare less expression to sort

bla[] arrayToSort;
sort!"a.i < b.i"(arrayToSort);

You can also pass a lambda or any function as compare less function to 
sort:
sort!((a,b){return a.i < b.i;})(arrayToSort);


Kind Regards
Benjamin Thaut
Jan 29 2014
prev sibling parent reply "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
On Wednesday, 29 January 2014 at 09:33:50 UTC, Boomerang wrote:


 I would appreciate it if you explained your approach and gave
 source code illustrating it. Thanks!


This can be solved without sorting in reverse or overloading 
anything in C++ (with a predicate version of sort() algorithm), 
and in D too. Take a look at this code:

http://dpaste.dzfl.pl/2d0dd6f953dc

the std.algorithm.sort() takes an optional predicate (as a 
template argument) to resolve the order of elements. In this 
case, it is specified as an anonymous function

(a,b) => a.grade > b.grade

You could alternatively specify it as a string:

sort!"a.grade > b.grade"(students);

or like this:

sort!q{a.grade > b.grade}(students);
Jan 29 2014
parent reply "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
It's also worth noting that you can avoid passing structs into
predicate function by value, and instead pass them by reference:

sort!((ref const a, ref const b) => a.grade > b.grade)(students);

This is useful for "heavy" structs to save on performance. E.g.
in this case, Student.sizeof is 24 bytes on 64 bit machine.
Passing by reference will only need to copy 16 bytes (i.e. size
of two pointers), whereas passing by value will incur copying 48
bytes (two structs).
Jan 29 2014
parent reply "Boomerang" <nomailforme nomailforme.no> writes:
Thanks for the help so far.
My current code is here: http://dpaste.dzfl.pl/b9acff399649

Are there problems with my code, or do you have suggestions to 
improve it?
Jan 29 2014
parent reply "Boomerang" <nomailforme nomailforme.no> writes:
Also sorry for double posting but I'm confused how the sorting 
works when we only specify to be sorted by grade. I think in C++, 
disregarding other data members can lead to loss of data in 
things such as std::set.
Jan 29 2014
parent reply "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
On Wednesday, 29 January 2014 at 10:30:06 UTC, Boomerang wrote:

I'll paste here with comments:

import std.algorithm;
import std.stdio;
import std.array;

void main()
{
     struct Student
     {
         string name;
         float grade;
     }

     Student[] studs;

     writeln("Enter student data. Reading stops when student name 
is empty.");

     while (true)
     {
         // Calls to readf() may throw an exception
         // if user inputs invalid data.
         // You may want to consider accounting
         // for that.

         typeof(Student.name) name;
         write("Student name: ");
         readf("%s\n", &name);

         // Don't burden users with typing STOP :)
         if (name.empty)
             break;

         typeof(Student.grade) grade;
         write("Student grade: ");

         import std.exception;
         import std.conv : ConvException;
         // EXAMPLE: catch all ConvExceptions
         // to persuade user to input a number :)
         while(collectException!ConvException(readf("%s\n", 
&grade)))
         {
             // Conversion failed but there's still data in
             // stdin. We get rid of it:
             readln;
             write("Please enter NUMERIC student grade: ");
         }

         // Create Student only when necessary
         // (a good compiler will optimize that
         // to avoid copying):
         studs ~= Student(name, grade);
     }

     // Use anonymous function with explicit
     // parameter storage class specifier;
     // Also Use UFCS
     studs.sort!((ref const a, ref const b) => a.grade > b.grade);

     // You can omit type name in foreach;
     // also it's worth using ref const to avoid
     // unnecessary copies
     foreach (ref const s; studs)
         writeln(s.name);

     // Or avoid foreach altogether:
     studs.map!((ref const s) => writeln(s.name));
}


 Also sorry for double posting but I'm confused how the sorting 
 works when we only specify to be sorted by grade. I think in 
 C++, disregarding other data members can lead to loss of data 
 in things such as std::set.


Yes and no. In fact, std::set is by default instantiated with an 
std::less predicate. But std::set is intended to store unique 
elements. So if you try to insert an element that std::set 
already considers to exist (it uses the predicate to determine 
that), it doesn't insert it.

But you must understand that despite being generic, algorithms 
and containers still serve particular purposes. You wouldn't 
store students in a set unless you had some way to uniquely 
identify them :)
Jan 29 2014
next sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
On Wednesday, 29 January 2014 at 11:24:54 UTC, Stanislav Blinov 
wrote:

     // Or avoid foreach altogether:
     studs.map!((ref const s) => writeln(s.name));
 }


Did you test this one? std.algorithm.map is lazy.
Jan 29 2014
parent "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
On Wednesday, 29 January 2014 at 12:44:37 UTC, Tobias Pankrath 
wrote:

 On Wednesday, 29 January 2014 at 11:24:54 UTC, Stanislav Blinov 
 wrote:

    // Or avoid foreach altogether:
    studs.map!((ref const s) => writeln(s.name));
 }


 Did you test this one? std.algorithm.map is lazy.


Ah yes, sorry, my bad. I forgot to remove foreach during testing 
and assumed it worked. Facepalm m)
Jan 29 2014
prev sibling parent reply "Paul-Andre" <chapeaufeutre gmail.com> writes:
On Wednesday, 29 January 2014 at 11:24:54 UTC, Stanislav Blinov 
wrote:

 On Wednesday, 29 January 2014 at 10:30:06 UTC, Boomerang wrote:
     // also it's worth using ref const to avoid
     // unnecessary copies


I am new to D.
Why should someone use "ref const" instead of "in"?
Jan 29 2014
parent "Jesse Phillips" <Jesse.K.Phillips+D gmail.com> writes:
On Thursday, 30 January 2014 at 03:00:43 UTC, Paul-Andre wrote:

 On Wednesday, 29 January 2014 at 11:24:54 UTC, Stanislav Blinov 
 wrote:

 On Wednesday, 29 January 2014 at 10:30:06 UTC, Boomerang wrote:
    // also it's worth using ref const to avoid
    // unnecessary copies


 I am new to D.
 Why should someone use "ref const" instead of "in"?


in is the same as 'scope const' (scope checks aren't implemented) 
So you be relying on the optimizer to not copy.
Jan 29 2014