如何排序指向结构的向量

Question

我正在尝试对concurrent_vector类型进行排序,其中hits_object:

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

这是我正在使用的代码:

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;
}

现在我已经填满了一个concurrent_vector<hits_object*>电话hits.

但我想在position属性上对这个concurrent_vector进行排序!

以下是典型命中对象内部的示例:

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

我想根据第一列(类型的"位置" int)对此进行排序.第二列是类型的"哈希" unsigned long int.

现在我尝试做以下事情:

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

其中compareByPosition定义为:

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

但是当我放入线路时,我不断收到分段错误 std::sort(hits.begin(),hits.end(),compareByPosition);

请帮忙!

Answer 1

你的compare函数需要返回一个布尔值0或1,而不是整数1或-1,它应该有一个强类型签名:

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

您看到的错误是由于std::sort解释了从comp函数返回的所有非零值true,这意味着左侧小于右侧.

注意:由于与sbi和Mike Seymour的对话,这个答案经过大量编辑.

Answer 2

不知道是什么concurrent_vector,我不能确定是什么导致了分段错误.假设它类似于std::vector,你需要填充hits.push_back(obj)而不是hits[i] = j; 你不能[]用来访问向量末尾之外的元素,或者根本不能访问空向量.

比较函数应该等效于a < b,返回一个布尔值; 它不是C风格的比较函数,返回负数,正数或零.此外,由于sort是模板,因此不需要C风格的void *参数; 一切都是强类型的:

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

此外,您通常不希望使用new(当然也不会malloc)创建存储在向量中的对象; 最简单和最安全的容器vector<hits_object>(以及一个比较器,它将引用而不是指针作为参数).如果你真的必须存储指针(因为复制对象很昂贵而且不可移动,或者因为你需要多态性 - 这两者都不适用于你的例子),要么使用智能指针,要么在完成后std::unique_ptr确保delete它们跟他们.

Answer 3

int (*)(void*, void*)是C qsort()函数的比较器.在C++ std::sort()中,比较器的原型是:

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

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

另一方面,您可以使用std::pairstruct,默认情况下比较其第一个字段:

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