76

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<std::string> m_vPaths;
Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
cchampion
  • 7,607
  • 11
  • 41
  • 51
  • 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 :) – cchampion Oct 22 '09 at 01:43

3 Answers3

145

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;
}
sth
  • 222,467
  • 53
  • 283
  • 367
  • 2
    Subtle. I almost downvoted this because I thought the erase would invalidate the following iterators. Thanks for the link. – Dan Hook Oct 22 '09 at 13:57
  • 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. – Matthieu M. Oct 22 '09 at 19:10
  • 4
    For `std::map` you can use `erase(iter++);` since there `erase` doesn't invalidate other iterators than the one erased. – sth Oct 22 '09 at 19:18
  • 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. – average joe Apr 15 '16 at 08:26
  • 4
    @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. – sth Apr 15 '16 at 12:00
  • 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 ? – Ayush Jun 28 '21 at 07:08
79

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

GManNickG
  • 494,350
  • 52
  • 494
  • 543
  • 1
    I wanted to use this on a std::vector where the value was an std::pair 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. – scippie Aug 21 '22 at 11:52
7

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.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • 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. – saurabheights May 28 '17 at 10:10