Sorting an array of structures with a pointer

[skiner36]

Hi,
I have a pointer to an array of structures in a DLL that I need to sort. I have searched the Internet but I can’t find an example that reflects what I am doing.

In a calling program I have a structure defined in the following manner and an array is created using the struct.

  struct BinData
{
    int Number;
    double Amplitude;
    int Correction;
}

I pass the array to a function in a DLL like below
void Calculate(BinData *bins, const int binCount)

With as many as 3000000 rows what is the best and fastest way to sort this array by the Amplitude field?

Thanks very much for your help,

John

[Repeater]

Start with the std::sort function. You provide the function with the comparison. Here's an example showing how to call the sort function on the array, with some output so you can see it's sorted.

#include <cstdlib>
#include <algorithm>
#include <iostream>

struct BinData
{
    int Number;
    double Amplitude;
    int Correction;
};

int main()
{
  // create 3000000 instances
  BinData* array = new BinData[3000000]; // just filled with garbage values

  for (int i=0; i<3000000; ++i)
    {
      array[i].Amplitude = rand(); // set some values in the amplitude fields
    }

  std::cout << "Example section of unsorted array:\n";
   for (int i = 345; i < 355; ++i)
    {
      std::cout << array[i].Amplitude << ' ';
    }
   std::cout << std::endl;

  // SORTING CODE BEGINS HERE
  std::sort(array, array+3000000,
	    [](const BinData& a, const BinData& b) -> bool
	    {
	      return a.Amplitude < b.Amplitude;
	    });
  // SORTING CODE ENDED

   std::cout << "\nSame section, sorted:\n";
  for (int i = 345; i < 355; ++i)
    {
      std::cout << array[i].Amplitude << ' ';
    }

  delete[] array;

}

If that's fast enough for you, job done.

[anup30]

#include <iostream>
#include <algorithm>
using namespace std;

struct BB{
	int a;
	char c;
	BB(int n, char s){
		a=n;
		c=s;
	}
	bool operator<(BB i){
		return(a<i.a);
	}
};

int main(){
	BB b[3]={{3,'d'},{1,'n'},{2,'r'}};	
	if(b[1]<b[2]) cout <<"hi\n";
	sort(b,b+3);
	for(int i=0;i<3;i++){
		cout <<b[i].a << " "<< b[i].c<< "\n";
	}
return 0;	
}

output

hi
1 n
2 r
3 d

[skiner36]

Thanks Repeater, That worked and was plenty fast enough. Thanks for your reply too anup30

[Duthomhas]

Reading the title to your question, I thought you had an array of pointers to struct.

When dealing with heavy objects, it is often useful to sort the pointers instead of the objects themselves. With reference to Repeater’s code:

std::vector <BinData*> array;
…
std::sort( array.begin(), array.end(), []( auto a, auto b )
{
  return a->amplitude < b->amplitude;
} );

Hope this helps.

[skiner36]

Thanks Duthomhas,

i will experiment with this. You have all been a big help

[keskiverto]

Note that the other form of sort that anup30 did use:
std::sort( array.begin(), array.end() );
does call operator< that accepts array elements. The op< is the default comparator. If you always order BinData by amplitude, then the default is convenient.

anup30 did supply such operator< as member function, but could have written a standalone functions:

bool operator< ( BinData* a, BinData* b )
{
  return a->amplitude < b->amplitude;
}

bool operator< ( const BinData& a, const BinData& b )
{
  return a.amplitude < b.amplitude;
}

Repeater did use the sort that takes a comparator function (object) as argument. The function could be standalone and have name, but the C++11 lambda syntax allows definition of such function in-place.

If you need different sorts, then you need the argument version (but you can have a default too).