Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

Tango analogue of c++ std::sort

Moderators: larsivi kris

Posted: 11/12/08 12:05:56

This is what I want:

#include <iostream>

#include <algorithm>
#include <vector>

class A
{
  int data_;
public:
  A( int data )
  {
    data_ = data;
  }

  bool operator()( int a, int b )
  {
    return abs( a - data_ ) < abs( b - data_ );
  }
};

int main()
{
  const int right = 10;

  std::vector< int > v;
  for( int i=0; i<right; i++ )
    v.push_back( i );

  std::sort( v.begin(), v.end(), A( right/2 ) );

  for( int i=0; i<v.size(); i++ )
  {
    std::cout << i << " " << v[i] << std::endl;
  }
}

I've tried to do it for Tango && D 1.0, but can't:

import tango.io.Stdout;
import tango.util.collection.ArraySeq;

class Sorter
{
  ArraySeq!( int ) array_;
public:
  this()
  {
    array_ = new ArraySeq!( int );
  }

  ~this()
  {
    delete array_;
  }

  int delegate( int, int ) comparator( int data )
  {
    int compare( int a, int b )
    {
      Stdout( data ); // trash in data
      int ia = tango.math.Math.abs( a-data );
      int ib = tango.math.Math.abs( b-data );
      if( ia < ib )
        return -1;
      else if( ia != ib )
        return 1;
      else
        return 0;
    }
    return &compare;
  }

  void work()
  {
    const int right = 10;
    for( int i=0; i<right; i++ )
      array_ ~= i;
    
    array_.sort( comparator ( right/2 ) );
  
    for( int i=0; i<right; i++ )
      Stdout.formatln( "{} {}", i, array_[i] );
  }
};

int main()
{
  auto sorter = new Sorter;
  sorter.work();
  delete sorter;
}

What is the best way to do it?

Author Message

Posted: 11/12/08 16:47:06

You can't return a delegate to a local function because the context pointer points to stack data that is being reused. This is why you get garbage.

I'd recommend a struct functor like your C++ code:

struct comparator
{
  int data;
  int opCall(int a, int b)
  {
    // copied body from your delegate
    Stdout( data ); // trash in data
    int ia = tango.math.Math.abs( a-data );
    int ib = tango.math.Math.abs( b-data );
    if( ia < ib )
      return -1;
    else if( ia != ib )
      return 1;
    else
      return 0;
  }
}


// should be able to use like this
array_.sort(comparator(right/2));

Posted: 11/13/08 05:17:26

Thank you. I was stupid.

I don't know how to get assembler listing via dsss. So... operator() in my c++ code is inlined. Is opCall inlined too?

Posted: 11/13/08 15:49:40

if you pass -inline to the compiler, it should be. Only for standalone functions, struct functions, or final class functions though. virtual functions cannot be inlined (and class functions are virtual by default).

BTW, if you are on Linux, dmd comes with an obj2asm program which allows you to view the assembly. On Windows, this program is not free.

Posted: 11/14/08 14:44:43

Ok, inlining is working for struct functors. Thank you for mention about obj2asm.

But... Sort function in tango.util.collection.ArraySeq? uses Comparator!(T):

public void sort(Comparator!(T) cmp)

And Comparator is just alias to delegate.

template Comparator(T)
{
        alias int delegate(T, T) Comparator;
}

Thus I do like that:

array_.sort( &comparator.init( a, b ).opCall );

How I can use opCall as functor to activate inlining?

Posted: 11/14/08 15:29:07

Even if sort is declared final, it probably won't be inlined. Inlining a delegate would be tough for the compiler to deduce, since it would have to build a different function for each delegate. The array sort inlines because sort is a template, with the functor as the type, so inlining is possible.

So bottom line, you can't have an inlined compare for sorting in the current Tango collection classes.

Also, you shouldn't use collection, it is being deprecated, use container instead. The container package does not have an array sequence, I'm not sure if it will get one, since D arrays are already pretty useful.

Posted: 11/14/08 18:21:25

There is a very efficient Vector type in container.more if you know the max size of your array. As for a extendable array interface - it is not necessarily unlikely to get in, but someone needs to write it.