Cancellazione di più oggetti da un vettore std ::?

Question

Ecco il mio problema, diciamo che ho un file std :: vector con ints.

diciamo che ha 50,90,40,90,80,60,80.

So che ho bisogno di rimuovere il secondo, il quinto e il terzo elemento. Non necessariamente conosco sempre l'ordine degli elementi da rimuovere, né quanti. Il problema è cancellando un elemento, questo cambia l'indice degli altri elementi. Pertanto, come posso cancellarli e compensare il cambio dell'indice. (Smistamento quindi linearmente cancellare con un offset non è un'opzione)

Grazie

Answer 1

sto offrendo diversi metodi:

1. Un metodo veloce che non trattiene l'ordine originale degli elementi:

assegnare l'ultimo elemento corrente del vettore per l'elemento da cancellare, quindi cancellare l'ultimo elemento. Questo eviterà grandi mosse e tutti gli indici tranne l'ultimo rimarranno costanti. Se inizi a cancellare dal retro, tutti gli indici precompilati saranno corretti.

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

vedo questo è essenzialmente una versione hand-coded dell'idioma erase-remove sottolineato da Klaim ...

2. Un metodo più lento che mantiene l'ordine originale degli elementi:

Passaggio 1: Contrassegna tutti gli elementi vettoriali da eliminare, ovvero con un valore speciale. Questo ha O (| indexes per eliminare |).

Fase 2: Cancella tutti gli elementi contrassegnati con v.erase(remove (v.begin(), v.end(), special_value), v.end());. Questo ha O (| vector v |).

Il tempo di funzionamento totale è quindi O (| vettore v |), assumendo la lista degli indici è più corto del vettore.

3. Un altro metodo più lento che mantiene l'ordine originale degli elementi:

Usare un predicato e rimuovere se come descritto in https://stackoverflow.com/a/3487742/280314. Per rendere questo efficiente e rispettando il requisito di non "ordinamento, quindi cancellando linearmente con un offset", la mia idea è di implementare il predicato usando una tabella hash e regolare gli indici memorizzati nella tabella hash mentre la cancellazione procede al ritorno true, come Suggerì Klaim.

Answer 2

Utilizzando un predicato e l'algoritmo remove_if è possibile ottenere ciò che si vuole: vedi http://www.cplusplus.com/reference/algorithm/remove_if/

Non dimenticare di cancellare la voce (vedi remove-erase idiom).

tuo predicato semplicemente tenere premuto l'IDX di ogni valore per eliminare e ridurre tutti gli indici Mantiene ogni volta che restituisce true.

Detto questo se puoi permetterti di rimuovere ogni oggetto usando l'idioma remove-erase, rendi semplicemente la tua vita semplice facendolo.

Answer 3

Sposterei gli elementi che non si desidera a un vettore temporaneo e quindi sostituire il vettore originale con questo.

Answer 4

Cancella gli elementi all'indietro. In altre parole, cancella prima l'indice più alto, poi quello più alto, ecc. Non invalidererai alcun iteratore o indice precedente in modo da poter semplicemente utilizzare l'approccio ovvio di più chiamate di cancellazione.

Answer 5

Sarebbe questo lavoro:

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

Si tratta di un'operazione O (n), non importa quanti elementi si elimina. Potresti guadagnare un po 'di efficienza riordinando il vettore in linea (ma penso che sia più leggibile).