[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:

1. Non mi sembra di vedere nulla di sbagliato nei due snippet, l'errore potrebbe essere nella funzione getVetArchi().
2. 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.
3. Se ti serve solo di testare la presenza dell'elemento, e non ti serve di avere l'iteratore, puoi usare binary_search.

[fracarro]

Originariamente inviato da 71106

Tre osservazioni:

1. Non mi sembra di vedere nulla di sbagliato nei due snippet, l'errore potrebbe essere nella funzione getVetArchi().
2. 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.
3. Se ti serve solo di testare la presenza dell'elemento, e non ti serve di avere l'iteratore, puoi usare 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]

Originariamente inviato da fracarro

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