Come ordinare vettore di puntatore a struct

Question

Sto cercando di risolvere un tipo di concurrent_vector, dove hits_object è:

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

Ecco il codice che sto utilizzando:

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

Ora ho riempito uno concurrent_vector<hits_object*> chiamato hits.

Ma voglio ordinare questo concurrent_vector sulla proprietà position !!!

Ecco un esempio di ciò che è all'interno di una tipica colpi oggetto:

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 

Voglio risolvere la questione sulla base della prima colonna ("posizione" di tipo int). La seconda colonna è "hash" di tipo unsigned long int.

Ora ho provato a fare quanto segue:

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

dove compareByPosition è definito come:

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

ma io continuo a ricevere errori di segmentazione quando ho messo nella linea std::sort(hits.begin(),hits.end(),compareByPosition);

Si prega di aiuto!

Answer 1

tua funzione di confronto deve restituire un valore booleano 0 o 1, non un intero 1 o -1, e dovrebbe avere una firma fortemente tipizzato:

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

L'errore si stava vedendo sono dovuti a std::sort interpretando tutto ciò che è diverso da zero restituito dalla funzione comp come true, il che significa che il lato sinistro è inferiore al lato destro.

NOTA: questa risposta è stata pesantemente modificata a seguito di conversazioni con sbi e Mike Seymour.

Answer 2

Il terzo argomento si passa alla std::sort() deve avere una firma simile a, e la semantica di, operator<():

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

Quando si memorizza puntatori in un vettore, non si può sovraccaricare operator<(), perché piccolo-che è corretto per tutti i tipi built-in.

---

Su un sidenote: Do not use malloc() in C++, utilizzare new invece. Inoltre, mi chiedo perché non stai utilizzando gli oggetti anziché puntatori. Infine, se concurrent_vector è qualcosa come std::vector, è necessario espanderlo in modo esplicito per accogliere nuovi oggetti.Questo è ciò che il codice sarà quindi simile:

concurrent_vector<hits_object*> hits; 

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

Answer 3

senza sapere cosa concurrent_vector è, non posso essere sicuro che cosa sta causando l'errore di segmentazione. Supponendo che sia simile a std::vector, è necessario popolarlo con hits.push_back(obj) anziché hits[i] = j; non è possibile utilizzare [] per accedere a elementi oltre la fine di un vettore o per accedere a un vettore vuoto.

La funzione di confronto dovrebbe essere equivalente a a < b, restituendo un valore booleano; non è una funzione di confronto in stile C che restituisce valori negativi, positivi o pari a zero. Inoltre, poiché sort è un modello, non sono necessari argomenti in stile C void *; tutto è fortemente tipizzato:

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

Inoltre, di solito non si desidera utilizzare new (e certamente mai malloc) per creare oggetti per memorizzare in un vettore; il contenitore più semplice e sicuro sarebbe vector<hits_object> (e un comparatore che prende i riferimenti, piuttosto che i puntatori, come argomenti). Se davvero devi memorizzare puntatori (perché gli oggetti sono costosi da copiare e non movibili, o perché hai bisogno di polimorfismo - nessuno dei quali si applica al tuo esempio), usa puntatori intelligenti come std::unique_ptr o assicurati di averli delete una volta fatto con loro.

Answer 4

int (*)(void*, void*) è il comparatore per la funzione C qsort(). In C++ std::sort() il prototipo al comparatore è:

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

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

D'altra parte, è possibile utilizzare std::pair struct, che di default a confronto i suoi primi campi:

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

Answer 5

Ciò non guardare a destra:

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

qui si sta già ordinando l'array in base a 'i' perché si imposta grado di i, così come diventa l'indice di colpi!

anche perché utilizzando malloc, si dovrebbe usare nuovo (/ delete). Potresti quindi creare un semplice costruttore per la struttura per inizializzare l'oggetto hits_

ad es.

struct hits_object 
{ 
    int position; 
    unsigned int hash; 

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

poi scrivere invece

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

o anche

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

Infine, la funzione di confronto dovrebbe usare lo stesso tipo di dati come vettore per i suoi argomenti

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