How to sort vector of pointer-to-struct

Question

I'm trying to sort a concurrent_vector type, where hits_object is:

struct hits_object{
        unsigned long int hash;
        int position;
};

Here is the code I'm using:

concurrent_vector<hits_object*> hits;

for(i=0;...){
    hits_object *obj=(hits_object*)malloc(sizeof(hits_object));
    obj->position=i;
    obj->hash=_prevHash[tid];
    hits[i]=obj;
}

Now I have filled up a concurrent_vector<hits_object*> called hits.

But I want to sort this concurrent_vector on position property!!!

Here is an example of what's inside a typical hits object:

0 1106579628979812621
4237 1978650773053442200
512 3993899825106178560
4749 739461489314544830
1024 1629056397321528633
5261 593672691728388007
1536 5320457688954994196
5773 9017584181485751685
2048 4321435111178287982
6285 7119721556722067586
2560 7464213275487369093
6797 5363778283295017380
3072 255404511111217936
7309 5944699400741478979
3584 1069999863423687408
7821 3050974832468442286
4096 5230358938835592022
8333 5235649807131532071

I want to sort this based on the first column ("position" of type int). The second column is "hash" of type unsigned long int.

Now I've tried to do the following:

std::sort(hits.begin(),hits.end(),compareByPosition);

where compareByPosition is defined as:

int compareByPosition(const void *elem1,const void *elem2 )
{
  return ((hits_object*)elem1)->position > ((hits_object*)elem2)->position? 1 : -1;
}

but I keep getting segmentation faults when I put in the line std::sort(hits.begin(),hits.end(),compareByPosition);

Please help!

Answer 1

Your compare function needs to return a boolean 0 or 1, not an integer 1 or -1, and it should have a strongly-typed signature:

bool compareByPosition(const hits_object *elem1, const hits_object *elem2 )
{
    return elem1->position < elem2->position;
}

The error you were seeing are due to std::sort interpreting everything non-zero returned from the comp function as true, meaning that the left-hand side is less than the right-hand side.

NOTE : This answer has been heavily edited as the result of conversations with sbi and Mike Seymour.

Answer 2

Without knowing what concurrent_vector is, I can't be sure what's causing the segmentation fault. Assuming it's similar to std::vector, you need to populate it with hits.push_back(obj) rather than hits[i] = j; you cannot use [] to access elements beyond the end of a vector, or to access an empty vector at all.

The comparison function should be equivalent to a < b, returning a boolean value; it's not a C-style comparison function returning negative, positive, or zero. Also, since sort is a template, there's no need for C-style void * arguments; everything is strongly typed:

bool compareByPosition(hits_object const * elem1, hits_object const * elem2) {
    return elem1->position < elem2->position;
}

Also, you usually don't want to use new (and certainly never malloc) to create objects to store in a vector; the simplest and safest container would be vector<hits_object> (and a comparator that takes references, rather than pointers, as arguments). If you really must store pointers (because the objects are expensive to copy and not movable, or because you need polymorphism - neither of which apply to your example), either use smart pointers such as std::unique_ptr, or make sure you delete them once you're done with them.

Answer 3

int (*)(void*, void*) is the comparator for C qsort() function. In C++ std::sort() the prototype to the comparator is:

bool cmp(const hits_object* lhs, const hits_object* rhs)
{
    return lhs->position < rhs->position;
}

std::sort(hits.begin(), hits.end(), &cmp);

On the other hand, you can use std::pair struct, which by default compares its first fields:

typedef std::pair<int position, unsigned long int hash> hits_object;
// ...
std::sort(hits.begin(), hits.end());

Answer 4

The third argument you pass to std::sort() must have a signature similar to, and the semantics of, operator<():

bool is_smaller_position(const hits_object* lhs, const hits_object* rhs)
{
  return lhs->position < rhs->position;
}

When you store pointers in a vector, you cannot overload operator<(), because smaller-than is fixed for all built-in types.

---

On a sidenote: Do not use malloc() in C++, use new instead. Also, I wonder why you are not using objects, rather than pointers. Finally, if concurrent_vector is anything like std::vector, you need to explicitly make it expand to accommodate new objects. This is what your code would then look like:

concurrent_vector<hits_object*> hits;

for(i=0;...){
    hits_object obj;
    obj.position=i;
    obj.hash=_prevHash[tid];
    hits.push_back(obj);
}

Answer 5

You can add a Lambda instead of a function to std::sort.

struct test
{
    int x;
};

std::vector<test> tests;

std::sort(tests.begin(), tests.end(),
    [](const test* a, const test* b) 
    { 
        return a->x < b->x; 
    });

Answer 6

This doesn't look right:

for(i=0;...){
    hits_object *obj=(hits_object*)malloc(sizeof(hits_object));
    obj->position=i;
    obj->hash=_prevHash[tid];
    hits[i]=obj;
}

here you already are sorting the array based on 'i' because you set position to i as well as it becomes the index of hits!

also why using malloc, you should use new(/delete) instead. You could then create a simple constructor for the structure to initialize the hits_object

e.g.

struct hits_object
{
   int position;
   unsigned int hash;

   hits_object( int p, unsigned int h ) : position(p), hash(h) {;}
};

then later write instead

hits_object* obj = new hits_object( i, _prevHash[tid] );

or even

hits.push_back(  new hits_object( i, _prevHash[tid] ) );

Finally, your compare function should use the same data type as vector for its arguments

bool cmp( hits_object* p1, hits_object* p2 )
{
  return p1->position < p2->position;
}