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

Question

Vengo in C ++ da Java, e hanno un situazione di progetto comune in cui ho un elemento (un non-primitivo) che mi piacerebbe per rimuovere da uno std :: vector.

in Java, mi piacerebbe scrivere qualcosa di simile a: arrayList.remove (arrayList.indexOf (myClassInstance));

in C ++, con uno std :: vector, qual è la migliore / più performante / modo più pulito di fare questo?

la cosa migliore che mi viene in mente è quello di creare un riferimento all'istanza che sto cercando, e poi scorrere l'vettore fino a quando ho trovato quel riferimento. in sostanza, per confrontare l'indirizzo di memoria di ciascun elemento nel vettore con il riferimento fino ottengo una corrispondenza.

Sono sulla strada giusta? o c'è un modo migliore di fare questo? (Magari utilizzando un contenitore std diverso, 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

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

std::find un'iterazione essenzialmente attraverso il vettore di trovare l'elemento, e non si può fare di meglio con un semplice vettore (lo stesso è il caso con ArrayList di Java). O se non si dovrebbe usare un contenitore diverso dipende dalle vostre 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 allora:

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

Nessuno di questi metodi sono il modo più performante perché richiedono ricerca lineare e anche se il vostro elemento si trova nella fase iniziale, la cancellazione è costoso perché deve spostare tutti gli altri elementi da una posizione per tenerli contigui.

Utilizzando std :: lista sarebbe affrontare il secondo di questi:. La ricerca sarebbe lineare, ma la cancellazione sarebbe costante di tempo

Se è possibile memorizzare i vostri elementi in un contenitore associativo che utilizza una ricerca della chiave che poi sarebbe più efficiente:. O (log N) di ricerca e la rimozione costante di tempo

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

Per quello che si sta suggerendo, vale a dire la cancellazione dal puntatore di un oggetto, è possibile utilizzare std :: set per il tipo T. Quindi utilizzare mySet.erase( pt ); dove pt è il puntatore. È necessario per gestire il ciclo di vita dei vostri puntatori, naturalmente, ma il fatto di sapere che uno di cancellare dalla vostra collezione suggerisce di avere una copia di esso 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());
   }
};