iterare il vettore, rimuovere alcuni elementi mentre vado

Question

Ho uno std :: vector m_vPaths; Ripeterò questo vettore e chiamerò :: DeleteFile (strPath) mentre vado. Se cancello correttamente il file, lo rimuoverò dal vettore. La mia domanda è: posso evitare di usare due vettori? Esiste una diversa struttura di dati che potrebbe essere più adatta a ciò che devo fare?

Esempio: usare gli iteratori fa quasi quello che voglio, ma il problema è che quando si cancella un iteratore, tutti gli iteratori diventano invalidi.

 std::vector<std::string> iter = m_vPaths.begin();
    for( ; iter != m_vPaths.end(); iter++) {
        std::string strPath = *iter;
        if(::DeleteFile(strPath.c_str())) {
            m_vPaths.erase(iter);   
                //Now my interators are invalid because I used erase,
                //but I want to continue deleteing the files remaining in my vector.    
        }
    }

Posso usare due vettori e non avrò più un problema, ma esiste un metodo migliore e più efficiente per fare ciò che sto cercando di fare?

a proposito, nel caso in cui non sia chiaro, m_vPaths è dichiarato così (nella mia classe):

std::vector<std::string> m_vPaths;

Answer 1

Guarda std :: remove_if :

#include <algorithm> // for remove_if
#include <functional> // for unary_function

struct delete_file : public std::unary_function<const std::string&, bool> 
{
    bool operator()(const std::string& strPath) const
    {
        return ::DeleteFile(strPath.c_str());
    }
}

m_vPaths.erase(std::remove_if(m_vPaths.begin(), m_vPaths.end(), delete_file()),
                m_vPaths.end());

Usa un std :: list per interrompere il problema di iteratori non validi, anche se si perde l'accesso casuale. (E prestazioni della cache, in generale)

---

Per la cronaca, il modo in cui implementeresti il ??tuo codice sarebbe:

typedef std::vector<std::string> string_vector;
typedef std::vector<std::string>::iterator string_vector_iterator;

string_vector_iterator iter = m_vPaths.begin();
while (iter != m_vPaths.end())
{
    if(::DeleteFile(iter->c_str()))
    {
        // erase returns the new iterator
        iter = m_vPaths.erase(iter);
    }
    else
    {
        ++iter;
    }
}

Ma dovresti usare std :: remove_if (reinventare la ruota è male).

Answer 2

Il metodo erase () restituisce un nuovo iteratore (valido) che punta all'elemento successivo dopo quello eliminato. Puoi utilizzare questo iteratore per continuare con il ciclo:

std::vector<std::string>::iterator iter;
for (iter = m_vPaths.begin(); iter != m_vPaths.end(); ) {
    if (::DeleteFile(iter->c_str()))
        iter = m_vPaths.erase(iter);
    else
        ++iter;
}

Answer 3

Dato il tempo necessario per cancellare un file, probabilmente non ha importanza, ma consiglierei comunque di ripetere il vettore all'indietro, in questo modo normalmente si eliminano gli elementi dalla (vicina) alla fine del vettore. Il tempo impiegato per eliminare un elemento è proporzionale al numero di elementi che lo seguono nel vettore. Se (ad esempio) hai un vettore di 100 nomi di file e li elimini con successo, copierai l'ultimo elemento 100 volte nel processo (e copi il penultimo elemento 99 volte e così via).

OTOH, se inizi dalla fine e lavori all'indietro, non copi finché l'eliminazione dei file ha esito positivo. È possibile utilizzare iteratori inversi per attraversare il vettore all'indietro senza modificare gran parte di qualsiasi altra cosa. Ad esempio, il codice di GMan che utilizza remove_if dovrebbe continuare a funzionare (solo un po 'più velocemente) semplicemente sostituendo rbegin () con begin () e rend () con end.

Un'altra possibilità è quella di usare un deque anziché un vettore: un deque può cancellare gli elementi dalla fine o dall'inizio della raccolta in tempo costante.