C'è un motivo per usare `remove` al di fuori dell'idioma di cancellazione-rimozione?

Question

Per quanto riguarda l'algoritmo, la rimozione di un set di elementi da un array contiguo può essere eseguita in modo efficace in due parti.

1. Sposta tutti gli elementi da non eliminare nella parte anteriore dell'array.
2. Contrassegna la matrice più piccola.

Questo può essere fatto in C++ con l'idioma di cancellazione-rimozione.

vector<T> v; // v = {0,1,2,3,0,0,7}; 
vector<T>::iterator it = remove(v.begin(),v.end(),e); 
// move all elements not to be deleted to the front 
// Yes, remove is not the brightest name for that. 
// Especially as list::remove really remove elements from the list. 
// now v = {1,2,3,7,?,?,?} results marked in question marks 
// are implementation dependent. 
v.erase(it,v.end()); 
// get rid of the elements marked as question marks. 
// v = {1,2,3,7} 

Ora, il contenuto degli elementi nel punto interrogativo è sconosciuto. L'unica cosa che possiamo fare con loro è eliminarli (sovrascrivendoli o rimuovendoli).

Esiste una situazione reale in cui è necessario utilizzare remove senza cancellarlo? L'unica situazione che potrei pensare è

copy(src.begin(),src.end(),remove(v.begin(),v.end(),e),v.end()); 

sostituendo tutti A s con B s, e richiedendo che tutti i nuovi B s saranno contigue. Non ha molto senso.

modificare: Ha senso a qualcosa di diverso contenitore di memoria contigious (deque e vector in realtà)?

Se davvero io sono corretto, perché è stato implementato come un algoritmo autonomo, invece di vector::remove_if, dequeue::remove_if ecc

Answer 1

La sua domanda va alla rovescia. Piuttosto, si potrebbe chiedere "perché dovrei implementare questo algoritmo identico ripetitivo per ogni contenitore, invece di renderlo una singola funzione libera"?

L'idea chiave per separare contenitori, iteratori e algoritmi è che non si ha un'esplosione di complessità mentre si scrivono più algoritmi e più contenitori. Se si desidera scrivere un nuovo contenitore con spazio di archiviazione contiguo, è possibile utilizzare remove direttamente dalla confezione (a condizione che si forniscano iteratori di inoltro o ad accesso casuale), senza duplicare il codice.

L'unica ragione che certi contenitori implementano le loro versioni utente di algoritmi è perché o possono farlo meglio della versione generica (es std::set::find vs. std::find oppure list::remove), o perché possono fare ciò che la versione generica non può fare (es. std::list::sort vs. std::sort). Ma se puoi, dovresti usare la versione gratuita per la massima generalità e genericità.

Answer 2

Se, per qualche motivo, non si desidera ridimensionare il contenitore, ma rimuovere solo alcuni elementi e successivamente impostare altri valori per sostituire lo spazio rimosso, è possibile utilizzare solo rimuovere.

Come ho capito, il valore degli elementi rimossi non è specificato dopo la rimozione, quindi non è possibile utilizzare i loro dati. Sono in qualche modo rimossi, ma lo spazio non è liberato.

Answer 3

Prima di tutto: l'implementazione effettiva di remove_if come metodo dei membri avrebbe significato duplicare il codice ancora e ancora.Ho sempre considerato che l'errore fosse remove: MarkB ha risposto a questo, in C++ 03 è più efficiente e in C++ 11 è leggermente più efficiente)

Questo è l'obiettivo di progettazione di STL: strutture e algoritmi di dati separati in modo che se si dispone delle strutture N e degli algoritmi M, non si hanno implementazioni degli algoritmi N*M, ma solo N+M che è decisamente più gestibile.

In particolare, la specifica di remove che gli elementi "mancati" hanno un valore non specificato consente l'applicazione delle nuove operazioni C++ 11 move per una rimozione efficiente.

Ora, lo ammetto che il più delle volte, è usato come parte dell'idioma di cancellazione. Nessuno ti impedisce di crearne uno:

template <typename C> 
void erase(C& container, typename C::const_reference r) { 
    container.erase(std::remove(container.begin(), container.end(), r), container.end()); 
} 

Answer 4

Sì. prima di tutto remove() è indipendente dal contenitore. Si può usare su 2 iteratori di qualsiasi contenitore e non dovrebbe fare le cose come:

if(<iterator is vector iterator>) 
{ 
    vector::remove_if(...); 
} 
else(<iterator is dequeue iterator>) 
{ 
    dequeue::remove_if(...); 
} 
else(<iterator is list iterator>) 
{ 
    list::remove_if(...); 
} 
// etc 

Sì c'è motivo per non eseguire la erase(). Per il vettore lo rende più piccolo e quindi esegue la ridistribuzione della memoria. Ciò che non è sempre desiderato, perché causerà molti costruttori di copia per altri elementi del vettore.

Answer 5

Sì. Un semplice contro-esempio:

void bar { 
    // Get vector of T's from foo() 
    vector<T> v = foo(); 
    // Print only non-zero elements. 
    vector<T>::iterator it = remove(v.begin(),v.end(), T(0)); 
    // I could call erase here, but why bother? 
    std::copy(v.begin(), it, std::ostream_iterator<T>(std::cout)); 
} 

Se ho intenzione di usare solo la parte selezionata del vettore, e non hanno altri usi per il vettore, non ho bisogno di erase il vettore. Tutti gli elementi saranno comunque distrutti quando il vettore esce dal campo di applicazione.