¿Borrar varios objetos de un std :: vector?

Question

Aquí está mi problema, digamos que tengo un std :: vector con ints en él.

Digamos que tiene 50,90,40,90,80,60,80.

Sé que necesito eliminar los elementos segundo, quinto y tercero. No necesariamente siempre sé el orden de los elementos para eliminar, ni cuántos. El problema es al borrar un elemento, esto cambia el índice de los otros elementos. Por lo tanto, ¿cómo podría borrar estos y compensar el cambio de índice? (Clasificación luego borrar de forma lineal con un desplazamiento no es una opción)

Gracias

Answer 1

me estoy ofreciendo varios métodos:

1. Un método rápido que no retenga el orden original de los elementos:

Asigna el último elemento actual del vector al elemento para borrar, luego borra el último elemento. Esto evitará movimientos grandes y todos los índices excepto el último permanecerán constantes. Si comienza a borrar desde la parte posterior, todos los índices precalculados serán correctos.

void quickDelete(int idx) 
{ 
    vec[idx] = vec.back(); 
    vec.pop_back(); 
} 

Veo esto es esencialmente una versión codificada a mano del idioma de borrado-remove señalado por Klaim ...

2. Un método más lento que conserva el orden original de los elementos:

Paso 1: Marque todos los elementos vectoriales a eliminar, es decir, con un valor especial. Esto tiene O (| índices para eliminar |).

Paso 2: borre todos los elementos marcados usando v.erase(remove (v.begin(), v.end(), special_value), v.end());. Esto tiene O (| vector v |).

El tiempo total de ejecución es, por lo tanto, O (| vector v |), suponiendo que la lista de índices es más corta que el vector.

3. Otro método más lento que conserva el orden original de los elementos:

Uso un predicado y eliminar si como se describe en https://stackoverflow.com/a/3487742/280314. Para hacer esto eficiente y respetando el requisito de no "ordenando luego borrando linealmente con un desplazamiento", mi idea es implementar el predicado usando una tabla hash y ajustar los índices almacenados en la tabla hash a medida que la eliminación continúa al volver verdadero, como Klaim sugirió.

Answer 2

El uso de un predicado y el algoritmo remove_if se puede lograr lo que quiere: ver http://www.cplusplus.com/reference/algorithm/remove_if/

No se olvide de borrar el artículo (ver remove-erase idiom).

Su predicado simplemente mantendrá el idx de cada valor para eliminar y disminuir todos los índices que mantiene cada vez que devuelve verdadero.

Dicho eso, si puedes permitirte simplemente eliminar cada objeto utilizando la expresión eliminar-borrar, simplemente haz tu vida más simple al hacerlo.

Answer 3

Me gustaría mover los elementos que no desea desea borrar a un vector temporal y luego reemplazar el vector original con esto.

Answer 4

Borre los elementos al revés. En otras palabras, borre el índice más alto primero, luego el siguiente más alto, etc. No invalidará ningún iterador o índice anterior, por lo que puede usar el enfoque obvio de múltiples llamadas de borrado.

Answer 5

Que este trabajo:

void DeleteAll(vector<int>& data, const vector<int>& deleteIndices) 
{ 
    vector<bool> markedElements(data.size(), false); 
    vector<int> tempBuffer; 
    tempBuffer.reserve(data.size()-deleteIndices.size()); 

    for (vector<int>::const_iterator itDel = deleteIndices.begin(); itDel != deleteIndices.end(); itDel++) 
     markedElements[*itDel] = true; 

    for (size_t i=0; i<data.size(); i++) 
    { 
     if (!markedElements[i]) 
      tempBuffer.push_back(data[i]); 
    } 
    data = tempBuffer; 
} 

Es una operación O (n), no importa cuántos elementos se elimina. Podrías ganar algo de eficiencia reordenando el vector en línea (pero creo que de esta manera es más legible).