Iterate a vector, delete some elements as I go

Question

I have std :: vector m_vPaths; I will iterate over this vector and call :: DeleteFile (strPath) when I go. If I successfully delete the file, I will delete it from the vector. My question is: can I get around to using two vectors? Is there any other 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 you delete with 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 way to do what I'm trying to do?

btw, if it is unclear, m_vPaths is declared like this (in my class):

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

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 std::list to stop the problem with invalid iterators, although you are losing random access. (And cache performance in general)

---

To write a way to implement your code:

 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 have to use std::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 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 of erasing the file, this probably doesn't matter, but I would still advise iterating through the vector backwards - this way you usually remove elements from (near the end) of the vector. The time taken to remove an element is proportional to the number of elements following it in the vector. If (for example) you have a vector of 100 file names and you successfully delete all of them, you will copy the last element 100 times in the process (and copy the second to the last element 99 times, etc.).

OTOH, if you start from the end and work backwards, you will not copy until the deletion of files is successful. You can use inverse iterators to move the vector backward without changing much of anything else. For example, GMan code using remove_if should continue to work (only a little faster) by simply replacing rbegin () for begin () and rend () for the end.

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