итерация вектора, удаление определенных элементов по мере продвижения - PullRequest
Новая
       21

итерация вектора, удаление определенных элементов по мере продвижения

58 голосов
/ 22 октября 2009

У меня есть std :: vector m_vPaths; Я буду повторять этот вектор и вызывать :: DeleteFile (strPath) по мере продвижения. Если я удаляю файл успешно, я удаляю его из вектора. Мой вопрос заключается в том, можно ли обойтись без использования двух векторов? Есть ли другая структура данных, которая лучше подходит для того, что мне нужно делать?

Пример: использование итераторов почти делает то, что я хочу, но проблема в том, что когда вы стираете, используя итератор, все итераторы становятся недействительными. 

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

Я могу использовать два вектора, и у меня больше не будет проблем, но есть ли лучший, более эффективный способ делать то, что я пытаюсь сделать?

Кстати, если неясно, m_vPaths объявлен так (в моем классе): 

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

Ответы [ 3 ]

114 голосов
/ 22 октября 2009

Метод 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;
}
73 голосов
/ 22 октября 2009

Выезд 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 (изобретать колесо плохо).

7 голосов
/ 22 октября 2009

Учитывая время для удаления файла, это, вероятно, не имеет значения, но я бы все же посоветовал перебирать вектор в обратном направлении - таким образом, вы обычно удаляете элементы из (ближе к) конца вектора. Время, необходимое для удаления элемента, пропорционально количеству элементов, следующих за ним в векторе. Если (например) у вас есть вектор из 100 имен файлов, и вы успешно удалили все из них, вы скопируете последний элемент 100 раз в процессе (и скопируете второй в последний элемент 99 раз, и так далее).

OTOH, если вы начинаете с конца и работаете в обратном направлении, вы не копируете, пока удаление файлов прошло успешно. Вы можете использовать обратные итераторы, чтобы пройти вектор назад, не меняя ничего другого. Например, код GMan с использованием remove_if должен продолжать работать (только чуть быстрее), просто заменив rbegin () на begin () и rend () на end.

Другая возможность - использовать деку вместо вектора - дек может стереть элементы с конца или начала коллекции в постоянное время.

...