qsort a list of class objects

Question

I'm writing a sorting code to an existing library, so I cannot make changes in the data model I have the following

 class Point
 {

   //Some functions 
   public:
       float x, y, z;

  };

int less_than_key (const void *arg1, const void *arg2)
 {

      Point *r1 = (Point*) arg1;
      Point *r2 = (Point*) arg2;

      if(r1->z < r2->z )
        return -1;

     else if(r1->z > r2->z )
       return 1;
    else
       return 0;
}

int main()
{
   list<Point> myPoints; 

    Point p;
    p.x = 0;
    p.y = 0;
    p.z = 0;
    myPoints.push_back(p);

    p.x = 0;
    p.y = 0;
    p.z = 6;
    myPoints.push_back(p);

    p.x = 0;
    p.y = 0;
    p.z = 2;
    myPoints.push_back(p);

    for(int i=0; i<myPoints.size(); i++)
      cout<<" Point "<<p[i].x<<", "<<p[i].y<<", "<<p[i].z<<"\n";

    qsort(&myPoints, myPoints.size(), sizeof(Point), less_than_key);

    for(int i=0; i<myPoints.size(); i++)
      cout<<"Point "<<p[i].x<<", "<<p[i].y<<", "<<p[i].z<<"\n";
 }

I want to sort the objects depending on the z value. The output I expect is the following

 Before sorting 
 Point 0, 0, 0
 Point 0, 0, 6
 Point 0, 0, 2

 After sorting 
 Point 0, 0, 0
 Point 0, 0, 2
 Point 0, 0, 6

When I run the following code, it crashes during the sorting call and I get the following error

  terminated with signal 11

I read in other solutions that I should pass the list as the following

   qsort(&myPoints[0], myPoints.size(), sizeof(Point), less_than_key);

But when I try to compile it I get the following

  no match for 'operator[]' (operand types are 'std::list<Point>' and 'int')

Answer 1

qsort is old school C. It expects 4 parameters:

ptr - pointer to the array to sort

count - number of elements in the array

size - size of each element in the array in bytes

comp - comparison function which returns ​a negative integer value if the first argument is less than the second, a positive integer value if the first argument is greater than the second and zero if the arguments are equal.

from std::qsort

What it has been given is

• pointer to a list
• number of elements in the array
• size of each element in the array in bytes
• Comparison function

It's the pointer to list that kills you. I suspect this is a std::list, but can't prove that. Whatever it is, it is a templated data structure and this makes things hairy. It is NOT an array and should not be used as an array.

qsort tried to use it as an array, and to quote Dune:

They tried and failed?

They tried and died.

Now for all we know, list could be a very simple structure that contains an array of Point that is perfectly positioned to line up with the beginning of the instance--the address of the contained array is the same as the address of the instantiated list--but the crash suggests otherwise.

And if list is a dynamic array (suggested by its usage) or linked list (suggested by the name and the usage), then a list instance doesn't even contain its data. It contains a pointer to the data. There is no array for qsort to use and it will quickly run through what little data is stored in list, out the other side and into the wild and wacky world of Undefined Behaviour. That said, The instance you passed a non-array into qsort you'd already hit Undefined Behaviour.

The solution is to use C++'s built in std::sort if list has an iterator interface. if list is really std::list there may be performance advantages in using std::list::sort. If neither is true and list is an unfortunately named custom class, you'll have to write your own sort routine (or do the smart thing and chuck the custom class in favour of a library container).

Answer 2

You can use std::sort with lambda expresion, here is an example:

#include <algorithm>

std::list<Point> myPoints;

//adding points to list...

std::sort(myPoints.begin(), myPoints.end(), [](const Point& lhs, const Point& rhs)
{
   return lhs.z < rhs.z;
});

for(int i=0; i<myPoints.size(); i++)
  cout<<"Point "<<p[i].x<<", "<<p[i].y<<", "<<p[i].z<<"\n";

Code above will sort, and then print sorted list of points

Answer 3

Stl list has its own sort function that accepts a compare function. You can write a compare function that takes two reference Point objects and pass it to myPoints.sort(..)

See [1]http://www.cplusplus.com/reference/list/list/sort/