быстрое удаление из вектора с обратным итератором - PullRequest
Новая
       34

быстрое удаление из вектора с обратным итератором

0 голосов
/ 18 мая 2019

Я хочу удалить векторные записи, которые удовлетворяют некоторому условию, после вызова функции для них.Меня не интересует стабильное упорядочение, поэтому я обычно перемещаю последний элемент массива, чтобы заменить тот, который я изучаю.

Вопрос: какой изобразительный способ работыэто с итераторами?

(Да, erase-remove - это стандартная идиома, если вы хотите сохранить порядок, но в моем случае это не нужно, и я думаю, что будет медленнее, благодаря этим шагам, чеммоя версия приведена здесь.)

С индексом int я бы сделал это таким образом, и этот код работает: 

  for ( int i = (int) apc.size() - 1; i >= 0; i-- )
      if ( apc[i]->blah ) {
          MyFunc( apc[i] );
          apc[i] = apc.back();
          apc.pop_back();
      }

Я пытаюсь сделать то же самое с обратным итератором, и он взрывается в++ цикла for после того, как он вошел в блок if в первый раз.Я не могу понять, почему.Если бы я на самом деле вызывал erase () для * it, я знаю, что это сделало бы его неопределенным, но я этого не делаю.Я полагаю, что pop_back () отменяет определение rbegin ().Я должен проверить, входит ли он в блок if на первой итерации и падает ли он только в этой ситуации. 

  for ( auto it = apc.rbegin(); it != apc.rend(); it++ )
      if ( (*it)->blah ) {
          MyFunc( *it );
          *it = apc.back();
          apc.pop_back();
      }

С прямым итератором это работает, хотя мне не нравится эффект заикания, связанный с цикломостановись, когда найдешь элементы с бла-истиной.Обратный цикл немного уродлив, но, по крайней мере, это реальный цикл, а не эта кентавроподобная полу-петля-половинная смесь: 

  for ( auto it = apc.begin(); it != apc.end(); )
      if ( (*it)->blah ) {
          MyFunc( *it );
          *it = apc.back();
          apc.pop_back();
      } else
          it++;

Ответы [ 2 ]

1 голос
/ 18 мая 2019

Я думаю, что старая и проверенная идиома удаления-стирания охватывает это прекрасно. 

apc.erase(std::remove_if(apc.begin(), apc.end(), [](auto& v) {
    if (v->blah) {
        MyFunc(v);
        return true;
    }
    return false;
}), apc.end());

Эта идиома перемещает все элементы, которые должны быть удалены, до конца контейнера на std::remove_if, а затем мы удаляем все их за один раз с erase.

Редактировать: Как указал Маршалл, алгоритм переместит элементы, которые будут сохранены, вперед, что имеет смысл, учитывая, что он обещает сохранить относительный порядок сохраняемых элементов.

Если лямбда-выражение должно действовать на this или на любую переменную, отличную от переданной в v, она должна быть зафиксирована. В этом случае нам не нужно беспокоиться о времени жизни, поэтому захват по умолчанию - хороший выбор. 

[&](auto& v) {
    if (v->blah < x) { //captures x by reference
        MyFunc(v, member_variable); //current object is captured by reference, and can access member variables
        return true;
    }
    return false;
})

Если MyFunc потенциально может изменить member_variable, нам дополнительно нужно сделать лямбду изменчивой.

По умолчанию lambda создает функциональный объект с operator() const, но mutable удаляет const. 

[&](auto& v) mutable { ... }
1 голос
/ 18 мая 2019

pop_back обычно должны делать недействительными только back() и end(). Но вы можете быть захвачены угловым случаем, если последний элемент массива должен быть удален. С индексами нет проблем, вы пытаетесь переместить элемент на себя, который должен быть неактивным, и перейти к предыдущему индексу. Но с итераторами текущее значение back(), поэтому оно должно быть признано недействительным.

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

...