IndexOf stile ArrayList per std :: vector in C++?

Question

Sto entrando in C++ da Java e ho una situazione di progettazione comune in cui ho un elemento (non primitivo) che vorrei rimuovere da un vettore std ::.

in Java, scriverei qualcosa tipo: arrayList.remove (arrayList.indexOf (myClassInstance));

in C++, con std :: vector, qual è il modo migliore/più performante/più pulito di farlo?

la cosa migliore che posso pensare è creare un riferimento all'istanza che sto cercando, quindi scorrere il vettore fino a trovare quel riferimento. in sostanza, per confrontare l'indirizzo di memoria di ogni elemento nel vettore con il riferimento fino a quando non ottengo una corrispondenza.

Sono sulla buona strada? o c'è un modo migliore per farlo? (forse usando un diverso contenitore std, ho usato solo std :: vector finora.)

Answer 1

#include <algorithm> 

std::vector<Foo>::iterator it = std::find(vec.begin(), vec.end(), foo_2b_found); 
if (it != vec.end()) vec.erase(it); 

Answer 2

Utilizzare std::find per trovare l'elemento e vector::erase per rimuoverlo.

std::find itera essenzialmente attraverso il vettore per trovare l'elemento, e non è possibile fare di meglio con un vettore semplice (lo stesso è il caso di Java ArrayList). Indipendentemente dal fatto che tu debba utilizzare un contenitore diverso dipende dalle tue esigenze.

Answer 3

Se si desidera cercare in modo lineare attraverso il vettore poi

seq.erase(std::find(seq.begin(), seq.end(), elt)); 

Se si dispone di un predicato e si desidera rimuovere tutti gli elementi che corrispondono al predicato poi:

seq.erase(std::remove_if(seq.begin(), seq.end(), Pred), seq.end()); 

Nessuno di questi metodi sono il modo più performante perché richiedono una ricerca lineare e anche se il tuo elemento viene trovato nella fase iniziale, la cancellazione è costosa perché deve spostare tutti gli altri elementi da una posizione per mantenerli contiguou S.

L'utilizzo di std :: list riguarderebbe l'ultimo di questi: la ricerca sarebbe lineare ma la cancellazione sarebbe un tempo costante.

Se è possibile memorizzare i propri elementi in un contenitore associativo che utilizza una ricerca di chiavi, sarebbe più efficiente: O (log N) ricerca e rimozione di tempo costante.

Una mappa di hash può essere anche migliore, vicino alla ricerca e alla rimozione di un tempo costante.

Per ciò che stai suggerendo, ovvero cancellando dal puntatore dell'oggetto, potresti usare std :: set per il tuo tipo T. Quindi usa mySet.erase(pt); dove pt è il tuo puntatore. È necessario gestire la durata dei tuoi puntatori, naturalmente, ma il fatto che tu sappia quale cancellare dalla tua raccolta suggerisce che ne hai una copia altrove.

È possibile utilizzare std :: set, SharedPtrLess>

in cui si definisce SharedPtrLess come segue:

template< typename T > 
struct SharedPtrLess 
{ 
    bool operator()(boost::shared_ptr<T> left, boost::shared_ptr<T> right) const 
    { 
    return std::less<T>()(left.get(), right.get()); 
    } 
};