如何在迭代时从 std::vector 中删除元素？

Question

我有一个

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

，我迭代这个向量并调用

::DeleteFile(strPath)

。如果我成功删除该文件，我会将其从向量中删除。

我的问题是：我可以避免使用两个向量吗？是否有不同的数据结构可能更适合我需要做的事情？

示例

使用迭代器几乎可以达到我想要的效果，但问题是，一旦你

erase

使用迭代器，所有迭代器都会变得无效。

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

我可以使用两个向量，我将不再有问题，但是有没有更好、更有效的方法来完成我想做的事情？

如果不清楚，

m_vPaths

是这样声明的（在我的课堂上）：

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

Answer 1

erase()

方法返回一个新的（有效）迭代器，该迭代器指向已删除元素之后的下一个元素。您可以使用此迭代器继续循环：

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 2

查看

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

使用

std::list

来阻止无效迭代器问题，尽管您会失去随机访问权限。 （以及一般情况下的缓存性能）

---

郑重声明，您实现代码的方式是：

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

但是你应该使用

std::remove_if

（重新发明轮子是不好的）。

Answer 3

考虑到删除文件的时间，这可能并不重要，但我仍然建议向后迭代向量 - 这样你通常会从向量末尾（接近）删除项目。删除一个项目所花费的时间与向量中跟随该项目的项目数量成正比。例如，如果您有一个包含 100 个文件名的向量，并且成功删除了所有文件名，则您将在此过程中复制最后一个元素 100 次（并将倒数第二个元素复制 99 次，依此类推）。

OTOH，如果从头开始向后操作，只要删除文件成功，就不会复制。您可以使用反向迭代器向后遍历向量，而无需更改任何其他内容。例如，使用remove_if的GMan代码应该可以继续工作（只是更快一点），只需用rbegin()代替begin()，用rend()代替end即可。

另一种可能性是使用双端队列而不是向量——双端队列可以在恒定时间内删除集合末尾或开头的项目。