Как бы вы удалили элементы 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;