iterate vector, remove certain items as I go.

Question

I have a std::vector m_vPaths; I will iterate this vector and call ::DeleteFile(strPath) as I go. If I successfully delete the file, I will remove it from the vector. My question is can I get around having to use two vectors? Is there different data structure that might be better suited for what I need to do?

example: using iterators almost does what I want, but problem is once you erase using an iterator, all iterators become invalid.

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

I can use two vectors and I will no longer have a problem, but is there a better, more efficient method of doing what I'm trying to do?

btw, incase it is unclear, m_vPaths is declared like this (in my class): std::vector m_vPaths;

Answer 1

Check out 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());

Use a list to stop the invalid iterators problem, though you lose random access. (And cache performance, in general)

---

For the record, the way you would implement your code would be:

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

But you should use remove_if (reinventing the wheel is bad).

Answer 2

The erase method returns a new (valid) iterator that points to the next element after the deleted one. You can use this iterator to continue with the loop:

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

Given the time to erase a file, it probably doesn't matter, but I'd still advise iterating through the vector backwards -- that way you're normally deleting items from (close to) the end of the vector. The time taken to delete an item is proportional to the number of items following it in the vector. If (for example) you have a vector of 100 file names, and you successfully delete all of them, you'll copy the last element 100 times in the process (and copy the second to last element 99 times, and so on).

OTOH, if you start from the end and work backwards, you don't copy as long as deleting the files is successful. You can use reverse iterators to traverse the vector backwards without changing much of anything else. For example, GMan's code using remove_if should continue to work (only a tad faster) simply by substituting rbegin() for begin(), and rend() for end.

Another possibility is to use a deque instead of a vector -- a deque can erase items from the end or the beginning of the collection in constant time.