Ответ 1

Это интуитивно понятный подход к проблеме, который сохраняет структуру цикла - в то время как он выполняет только один проход из-за повторного стирания, который, вероятно, будет менее эффективным, чем двухпроходный. Для этого более эффективного подхода вы должны использовать ответ Бенджамина Линдли.

Изменив код в ответе на первую ссылку, которую вы дали, похоже, что что-то вроде этого будет соответствовать вашей спецификации:

for (auto i = vec.begin(); i != vec.end();)
{
    if (*i == whatImLookingFor)
        return i;
    else if (isInvalid(*i))
        i = vec.erase(i);       // slow, don't use this version for real
    else
        ++i;
}

• Если мы найдем элемент, который вы ищете, мы вернем ему итератор.
• Если мы найдем недопустимый элемент по пути (но не после нужного элемента), мы его удалим.
• Мы избегаем аннулирования итератора, сохраняя итератор возвращенным из erase.

Вам все равно придется обрабатывать случай, когда элемент не найден, возможно, вернув vec.end().

Ответ 2

Вы все равно должны использовать std::remove_if, просто вызовите std::find заранее.

auto el = std::find(vec.begin(), vec.end(), whatImLookingFor);
auto p = std::remove_if(vec.begin(), el, isInvalid);

// returns the iterator, not the element itself.
// if the element is not found, el will be vec.end()
return vec.erase(p, el);

Обычно это будет более эффективным, чем удаление одного элемента за раз.

Ответ 3

Мне было интересно узнать об этом, поэтому я провел быстрый наивный бенчмарк, сравнивающий Benjamin, который затем частично очистил и hnefatl for-loop. Бенджамин действительно быстрее: 113 раз быстрее. Впечатляет.

Но мне было любопытно, куда больше всего remove_if, поскольку оно было больше суммы remove_if и find, которые являются единственными функциями, которые фактически перебирают массив. Однако, как vec.erase строка vec.erase в его коде на самом деле довольно медленная. Это происходит потому, что в remove_if он remove_if область от начала до местоположения найденного значения, что приводит к разрыву в середине массива из недопустимых значений. vec.erase должен скопировать оставшиеся значения, чтобы заполнить пробел и, наконец, изменить размер массива.

Я провела третий тест с полноразмерным remove_if/vec.erase а затем find, поэтому разрыв происходит в конце, и копия не нужна, просто усечение. Он оказался примерно на 15% быстрее и оставляет весь вектор чистым. Обратите внимание, что это предполагает, что тестирование на достоверность дешево. Если это больше, чем несколько простых сравнений, ответ Бенджамина выиграет раздачу, как отметил Крис в комментариях.

Код

auto p = std::remove_if(vec.begin(), vec.end(), isInvalid);
vec.erase(p, vec.end());
return std::find(vec.begin(), vec.end(), whatImLookingFor);

Бенчмарк

Ответ 4

Как отметил @BenjaminLindley и @JMerdich, для поставленной проблемы двухпроходный подход, вероятно, проще и эффективнее.

В реалистичной ситуации возможно, что существует некоторая дорогостоящая калькуляция, которая должна быть выполнена либо для определения того, является ли элемент недопустимым, либо для определения того, является ли элемент тем, который мы ищем:

В этом случае двухпроходный подход становится менее желательным, поскольку он заставляет нас делать этот дорогостоящий расчет дважды.

Но можно сделать однопроходный подход без вызова std::vector::erase несколько раз в цикле. Сложно написать std::remove_if самостоятельно, тогда мы можем заставить его делать обе проверки в одно и то же время. Мы все еще просто вызываем std::vector::erase один раз в конце:

std::vector<T>::iterator 
findAndRemoveInvalid(std::vector<T>& vec, U whatImLookingFor) {

  // Find first invalid element - or element you are looking for
  auto first = vec.begin();
  for(;first != vec.end(); ++first) {
    auto result = someExpensiveCalculation(*first);
    if (result == whatImLookingFor)
      return first;  
    if (isInvalid(result))
      break;
  }
  if (first == vec.end())
    return first;

  // Find subsequent valid elements - or element you are looking for
  auto it = first + 1;
  for(;it != vec.end(); it++) {
    auto result = someExpensiveCalculation(*it);
    if (result == whatImLookingFor)
      break;
    if (!isInvalid(result)) {
      *first++ = std::move(*it);  // shift valid elements to the start
      continue;
    }
  }

  // erase defunct elements and return iterator to the element
  // you are looking for, or vec.end() if not found.
  return vec.erase(first, it);
}

Демо-версия.

Очевидно, что это сложнее, поэтому сначала измерьте производительность.

Ответ 5

Если простой цикл, выходящий с break, слишком примитивен для вас, я бы предложил использовать std::find() чтобы получить итератор для vector.erase() элемента, а затем использовать vector.erase() для удаления элементов othere.