www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - sort struct of arrays

reply =?UTF-8?B?Ikx1w61z?= Marques" <luis luismarques.eu> writes:
If you have an array of structs, such as...

      struct Foo
      {
          int x;
          int y;
      }

      Foo[] foos;

...and you wanted to sort the foos then you'd do something like...

      foos.sort!(a.x < b.x),

..and, of course, both of the fields x and y get sorted together.
If you have a so-called struct of arrays, or an equivalent
situation, such as...

      int[] fooX;
      int[] fooY;

...is there a simple way to sort fooX and fooY
"together"/coherently (keyed on, say, fooX), using the standard
lib?
May 09 2014
next sibling parent reply "anonymous" <anonymous example.com> writes:
On Friday, 9 May 2014 at 14:23:41 UTC, Luís Marques wrote:
 If you have an array of structs, such as...

      struct Foo
      {
          int x;
          int y;
      }

      Foo[] foos;

 ...and you wanted to sort the foos then you'd do something 
 like...

      foos.sort!(a.x < b.x),

 ..and, of course, both of the fields x and y get sorted 
 together.
 If you have a so-called struct of arrays, or an equivalent
 situation, such as...

      int[] fooX;
      int[] fooY;

 ...is there a simple way to sort fooX and fooY
 "together"/coherently (keyed on, say, fooX), using the standard
 lib?
std.range.zip(fooX, fooY).sort!((a, b) => a[0] < b[0]); I wasn't sure if that's supposed to work. Turns out the documentation on zip [1] has this exact use case as an example. [1] http://dlang.org/phobos/std_range.html#zip
May 09 2014
parent =?UTF-8?B?Ikx1w61z?= Marques" <luis luismarques.eu> writes:
On Friday, 9 May 2014 at 14:48:50 UTC, anonymous wrote:
 std.range.zip(fooX, fooY).sort!((a, b) => a[0] < b[0]);

 I wasn't sure if that's supposed to work. Turns out the
 documentation on zip [1] has this exact use case as an example.

 [1] http://dlang.org/phobos/std_range.html#zip
Ha! Awesome! Sorry that I missed that example.
May 09 2014
prev sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Friday, 9 May 2014 at 14:23:41 UTC, Luís Marques wrote:
 If you have an array of structs, such as...

      struct Foo
      {
          int x;
          int y;
      }

      Foo[] foos;

 ...and you wanted to sort the foos then you'd do something 
 like...

      foos.sort!(a.x < b.x),

 ..and, of course, both of the fields x and y get sorted 
 together.
 If you have a so-called struct of arrays, or an equivalent
 situation, such as...

      int[] fooX;
      int[] fooY;

 ...is there a simple way to sort fooX and fooY
 "together"/coherently (keyed on, say, fooX), using the standard
 lib?
For some situations (expensive/impossible to move/copy elements of fooY), you would be best with this: auto indices = zip(iota(fooX.length).array, fooX).sort!"a[1] < b[1]".map!"a[0]"; auto sortedFooY = fooY.indexed(indices); bearing in mind that this causes an allocation for the index, but if you really can't move the elements of fooY (and fooX isn't already indices of fooY) then you don't have much of a choice.
May 09 2014
parent reply "Rene Zwanenburg" <renezwanenburg gmail.com> writes:
On Friday, 9 May 2014 at 15:52:51 UTC, John Colvin wrote:
 On Friday, 9 May 2014 at 14:23:41 UTC, Luís Marques wrote:
 If you have an array of structs, such as...

     struct Foo
     {
         int x;
         int y;
     }

     Foo[] foos;

 ...and you wanted to sort the foos then you'd do something 
 like...

     foos.sort!(a.x < b.x),

 ..and, of course, both of the fields x and y get sorted 
 together.
 If you have a so-called struct of arrays, or an equivalent
 situation, such as...

     int[] fooX;
     int[] fooY;

 ...is there a simple way to sort fooX and fooY
 "together"/coherently (keyed on, say, fooX), using the standard
 lib?
For some situations (expensive/impossible to move/copy elements of fooY), you would be best with this: auto indices = zip(iota(fooX.length).array, fooX).sort!"a[1] < b[1]".map!"a[0]"; auto sortedFooY = fooY.indexed(indices); bearing in mind that this causes an allocation for the index, but if you really can't move the elements of fooY (and fooX isn't already indices of fooY) then you don't have much of a choice.
It's probably better to use makeIndex: http://dlang.org/phobos/std_algorithm.html#makeIndex
May 09 2014
parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Friday, 9 May 2014 at 16:26:22 UTC, Rene Zwanenburg wrote:
 On Friday, 9 May 2014 at 15:52:51 UTC, John Colvin wrote:
 On Friday, 9 May 2014 at 14:23:41 UTC, Luís Marques wrote:
 If you have an array of structs, such as...

    struct Foo
    {
        int x;
        int y;
    }

    Foo[] foos;

 ...and you wanted to sort the foos then you'd do something 
 like...

    foos.sort!(a.x < b.x),

 ..and, of course, both of the fields x and y get sorted 
 together.
 If you have a so-called struct of arrays, or an equivalent
 situation, such as...

    int[] fooX;
    int[] fooY;

 ...is there a simple way to sort fooX and fooY
 "together"/coherently (keyed on, say, fooX), using the 
 standard
 lib?
For some situations (expensive/impossible to move/copy elements of fooY), you would be best with this: auto indices = zip(iota(fooX.length).array, fooX).sort!"a[1] < b[1]".map!"a[0]"; auto sortedFooY = fooY.indexed(indices); bearing in mind that this causes an allocation for the index, but if you really can't move the elements of fooY (and fooX isn't already indices of fooY) then you don't have much of a choice.
It's probably better to use makeIndex: http://dlang.org/phobos/std_algorithm.html#makeIndex
good call, I didn't realise that existed.
May 09 2014