[C++] Ricerca binaria su vettore di puntatori a struct

[fracarro]

Salve a tutti.
Come da titolo avrei bisogno di implementare una ricerca binaria (che restituisce un iteratore e non un valore bool) per un vettori di puntatori a struttura (dichiarato come std::vector<datiArco*> vetArchi; ). La struttura dati è la seguente:
struct datiArco{
int da;
int a;
std::vector<int> colori;

bool operator<(const datiArco &other) const {
if(this->da == other.da) return this->a < other.a;
else return this->da < other.da;
}

bool operator==(const datiArco &other) const {
return ((this->da == other.da) && (this->a == other.a));
}
};

static bool comparePtrToArc(const datiArco* ptr1, const datiArco* ptr2) {
if(ptr1->da == ptr2->da) return (ptr1->a < ptr2->a);
else return (ptr1->da < ptr2->da);
}

La funzione comparePtrToArc serve per il sort del vettore (e fino qui tutto ok). Leggendo su internet mi sembra possibile implementare la ricerca binaria in c++ utilizzando la funzione lower_bound. Tuttavia quando invoco la funzione tramite il seguente comando:

datiArco arcoTmp;
arcoTmp.da = i;
arcoTmp.a = j;
std::vector<datiArco*>::iterator itArco = std::lower_bound(getVetArchi().begin(), getVetArchi().end(), &arcoTmp,comparePtrToArc);

ricevo sempre una segmentation fault proprio nella riga di invocazione della funzione lower_bound. So che utilizzare un vettore di puntatori non è consigliato ma non posso cambiare questa struttura. Qualche esperto di c++ può darmi qualche consiglio per individuare l'errore?

[71106]

Tre osservazioni:

Non mi sembra di vedere nulla di sbagliato nei due snippet, l'errore potrebbe essere nella funzione getVetArchi().
L'implementazione comparePtrToArc è identica a quella dell'operatore <, quindi puoi eliminare quella funzione e affidarti sempre all'uso implicito dell'operatore, sia nel sort che nella ricerca binaria.
Se ti serve solo di testare la presenza dell'elemento, e non ti serve di avere l'iteratore, puoi usare binary_search (http://en.cppreference.com/w/cpp/algorithm/binary_search).

[fracarro]

Tre osservazioni:

Non mi sembra di vedere nulla di sbagliato nei due snippet, l'errore potrebbe essere nella funzione getVetArchi().
L'implementazione comparePtrToArc è identica a quella dell'operatore <, quindi puoi eliminare quella funzione e affidarti sempre all'uso implicito dell'operatore, sia nel sort che nella ricerca binaria.
Se ti serve solo di testare la presenza dell'elemento, e non ti serve di avere l'iteratore, puoi usare binary_search (http://en.cppreference.com/w/cpp/algorithm/binary_search).


Innanzitutto grazie per le risposte. Riguardo i tre punti:
1. La funzione getVetArchi() è la seguente:
std::vector<datiArco*> getVetArchi() const {
return vetArchi;
}

ossia è il metodo "getter" di una classe X che contiene il vettore di struct vetArchi definito in questo modo: std::vector<datiArco*> vetArchi;

Nel primo post non avevo indicato questo dettaglio per non complicare la descrizione del problema ma la chiamate reale nel mio codice è:
std::vector<datiArco*>::iterator itArco = std::lower_bound(p->getVetArchi().begin(), p->getVetArchi().end(), &arcoTmp,comparePtrToArc);

dove p è un oggetto della classe X.

2. Giusto, eliminerò la funzione inutile.

3. Purtroppo è proprio quello il problema. Tutta la questione nasce dalla necessità di avere l'iteratore o l'indice dell'elemento nell'array, non mi basta sapere se l'elemento è presente o meno.

[71106]

Innanzitutto grazie per le risposte. Riguardo i tre punti:
1. La funzione getVetArchi() è la seguente:
std::vector<datiArco*> getVetArchi() const {
return vetArchi;
}

ossia è il metodo "getter" di una classe X che contiene il vettore di struct vetArchi definito in questo modo: std::vector<datiArco*> vetArchi;

Nel primo post non avevo indicato questo dettaglio per non complicare la descrizione del problema ma la chiamate reale nel mio codice è:
std::vector<datiArco*>::iterator itArco = std::lower_bound(p->getVetArchi().begin(), p->getVetArchi().end(), &arcoTmp,comparePtrToArc);

dove p è un oggetto della classe X.

Ora è più chiaro: getVetArchi effettua una copia del vettore, e la invochi indipendentemente per ottenere l'iteratore di inizio e quello di fine, quindi i due iteratori tra i quali la lower_bound si trova ad iterare appartengono a due vettori diversi.

Prova così:


std::vector<datiArco*> vetArchi = p->getVetArchi();
std::vector<datiArco*>::iterator itArco = std::lower_bound(vetArchi.begin(), vetArchi.end(), &arcoTmp,comparePtrToArc);