Как бы вы удалили элементы std :: vector, основанные на некотором свойстве элементов?

Question

Если у вас есть std::vector<MyClass>, где MyClass имеет общедоступный метод: bool isTiredOfLife(), как удалить элементы, которые возвращают true?

Answer 1

Я предпочитаю remove_if

v.erase(remove_if(v.begin(), v.end(), 
       mem_fun_ref(&MyClass::isTiredOfLife)), 
     v.end()); 

remove_if возвращает итератор, указывающий после последнего элемента, который по-прежнему в последовательности. erase стирает все от первого до последнего аргумента (оба итератора).

Answer 2

Использование remove_if - это «правильный» способ сделать это. Будьте осторожны, чтобы не использовать итератор для циклического перехода и удаления, поскольку удаление элементов делает недействительным итератор. Фактически, любой пример, который использует erase() в качестве основного метода, является плохой идеей для векторов, потому что erase - это O (n), что сделает ваш алгоритм O (n^2). Это должен быть алгоритм O (n).

Метод, который я даю ниже, скорее всего будет быстрее, чем remove_if, но, в отличие от remove_if, НЕ сохранит относительный порядок элементов. Если вы заботитесь о поддержании порядка (т. Е. Ваш вектор отсортирован), используйте remove_if, как в ответе выше. Если вы не заботитесь о порядке, и если количество элементов, которые необходимо удалить, как правило, меньше, чем четверть вектора, этот метод, вероятно, будет быстрее:

for(size_t i = 0; i < vec.size();) 
    if(vec[i].isTiredOfLife()) 
    { 
     vec[i] = vec.back(); 
     vec.pop_back(); 
    } 
    else 
     ++i;