How do you remove elements from a std::vector while iterating? [duplicate]

Question

I have a std::vector<std::string> m_vPaths; I iterate over this vector and call ::DeleteFile(strPath) as I go. If I successfully delete the file, I remove it from the vector.

My question is: can I get around having to use two vectors? Is there a different data structure that might be better suited for what I need to do?

Example

Using iterators almost does what I want, but the problem is that 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've used erase,
        // but I want to continue deleting 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?

In case it is unclear, m_vPaths is declared like this (in my class):

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

Erhart

Also, I dont' really case what kind of data structure it uses, if there is something better than a vector let me know. I don't think std::queue or std::list has anything that will help me (I could be wrong though :) – Erhart

Answer 1

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

Use a std::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 std::remove_if (reinventing the wheel is bad).

Charentemaritime

I wanted to use this on a std::vector where the value was an std::pair<double, std::string> and the double decreased with time. When it became <= 0.0, something had to be done with the string and then the item had to be removed. It seems it is impossible to change the key from the function you pass to std::remove_if so sadly I had to implement it the 'old' way. – Muscovado

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

Clowers

Subtle. I almost downvoted this because I thought the erase would invalidate the following iterators. Thanks for the link. – Fivespot

However, this approach does not work for all STL container (in particular std::map), while the erase(range) / remove combination works with any STL container. – Pesky

For std::map you can use erase(iter++); since there erase doesn't invalidate other iterators than the one erased. – Clowers

Is it actually incorrect to do '++iter' as the normal, third expression of the foor loop? Doing so seems to cause it to skip element n if n-1 is erased. – Seymour

@averagejoe: If you do that, the iterator returned by erase() is incremented for the next loop iteration. But you don't want it incremented - erase() returned the correct iterator for the next loop iteration, additionally incrementing it skips an element. – Clowers

Isn't "erase" an expensive operation? Since it leads to relocation of all the elements after the one which was erased. And this would happen for every iteration of the loop whenever erase is called ! Am I right ? – Parthenope

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.

Sain

Wouldn't it be better to move the nth good item to nth index? We just need to index location value, one for nth good item location and one for the nth index. This will make sure all good items move forward, and once done we can resize vector to n elements(not sure if support). At most, n-1 swap happens when the first element is to be removed. – Tsang

Answer 4

Since C++20, the most elegant solution is std::erase_if:

std::erase_if(m_vPaths, [](const auto& path) {
    return ::DeleteFile(path.c_str());
});

Prior to C++20, you can use the erase-remove idiom, which does basically the same, but in two functions:

#include <algorithm>

m_vPaths.erase(std::remove_if(m_vPaths.begin(), m_vPaths.end(), [](const auto& path) {
    return ::DeleteFile(path.c_str());
}), m_vPaths.end());

Payola