ArrayList-style indexOf para std :: vector en C++?

Question

vengo a C++ desde Java y tengo una situación de diseño común en la que tengo un elemento (no primitivo) que me gustaría eliminar de un std :: vector.

en Java, escribiría algo como: arrayList.remove (arrayList.indexOf (myClassInstance));

en C++, con std :: vector, ¿cuál es la mejor/más eficiente forma de hacer esto?

lo mejor que puedo pensar es crear una referencia a la instancia que estoy buscando, y luego recorrer el vector hasta encontrar esa referencia. esencialmente, para comparar la dirección de memoria de cada elemento en el vector con la referencia hasta que obtenga una coincidencia.

¿estoy en el camino correcto? o hay una forma mejor de hacer esto? (tal vez usando un contenedor std diferente, solo he usado std :: vector hasta ahora.)

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

Usa std::find para encontrar el elemento y vector::erase para eliminarlo.

std::find esencialmente itera a través del vector para encontrar el elemento, y no se puede hacer nada mejor con un vector simple (el mismo es el caso con Java ArrayList). Si debe o no usar un contenedor diferente depende de sus requisitos.

Answer 3

Si desea buscar de forma lineal a través del vector continuación

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

Si usted tiene un predicado y desea eliminar todos los elementos que coinciden con el predicado a continuación:

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

Ninguno de estos métodos son los más efectivos porque requieren una búsqueda lineal e incluso si su elemento se encuentra al principio, el borrado es costoso porque tiene que mover todos los demás elementos para mantenerlos contiguos s.

El uso de std :: list abordaría el último de estos: la búsqueda sería lineal pero el borrado sería un tiempo constante.

Si es posible almacenar sus elementos en un contenedor asociativo que utiliza una búsqueda de claves, entonces eso sería más eficiente: búsqueda O (log N) y eliminación de tiempo constante.

Un mapa hash puede ser incluso mejor, cerca de la búsqueda y eliminación de tiempo constante.

Por lo que está sugiriendo, es decir, borrando por el puntero del objeto, puede usar std :: set para su tipo T. Luego use mySet.erase(pt); donde pt es su puntero. Necesita administrar la duración de sus punteros, por supuesto, pero el hecho de que sepa cuál borrar de su colección sugiere que tiene una copia en otro lugar.

Es posible utilizar std :: set, SharedPtrLess>

donde se define de la siguiente manera SharedPtrLess:

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