如何排序的矢量指针到结构

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。

但我想排序此位置属性上的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

你比较函数需要返回一个布尔值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

传递给std::sort()第三个参数必须有相似的签名，语义，operator<()：

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

当存储指针的载体，你不能超载operator<()，因为较小的比适用于所有内置类型。

---

在一个旁注：Do not use malloc() in C++，用new代替。另外，我想知道你为什么不使用对象，而不是指针。最后，如果concurrent_vector与std::vector类似，您需要明确地使其扩展为以适应新的对象。这是您的代码将然后看起来像：

concurrent_vector<hits_object*> hits; 

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

Answer 3

不知道什么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 4

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::pair结构，默认情况下它的第一场比较：

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

Answer 5

这看起来不正确：

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

这里您已经在基于'i'对数组进行排序，因为您将位置设置为i以及它成为匹配索引！

也是为什么使用malloc，你应该使用新的（/删除）代替。然后，您可以创建一个简单的构造函数结构初始化hits_object

例如

struct hits_object 
{ 
    int position; 
    unsigned int hash; 

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

后来写的，而不是

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

甚至

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

最后，你的比较函数应该使用相同的数据类型为矢量其参数

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