STL "erase-remove" идиома: почему не "изменить размер-удалить"?

Обычно считается, что это хороший способ полностью удалить нужные элементы из std::vector идиома стирания-удаления

Как отмечено в приведенной выше ссылке (на дату публикации), в коде идиома удаления-удаления выглядит следующим образом:

int main()
{
  // initialises a vector that holds the numbers from 0-9.
  std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  // erase-remove idiom to completely eliminate the desired items from the vector
  v.erase( std::remove( std::begin(v), std::end(v), 5 ), std::end(v) ); 
}

Я хотел бы знать, является ли resize-remove идиома эквивалентна с точки зрения функциональности и производительности erase-remove идиома. Или, может быть, я упускаю что-то очевидное?

Является ли следующее resize-remove идиома, эквивалентная вышеупомянутой erase-remove идиома?

int main()
{
  std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  // Is this "resize-remove" approach equivalent to the "erase-remove" idiom?
  v.resize( std::remove( std::begin(v), std::end(v), 5 ) - v.begin() ); 
}
Источник

4 ответа

Решение

На мой взгляд, есть две причины:

  1. std::remove алгоритм требует только прямой итератор, но - Оператор требует итератор произвольного доступа.

  2. Результат std::remove означает "новый конец контейнера". Логически мы должны стереть [ "новый конец контейнера", "старый конец контейнера").

Источник

Это эквивалентно для std::vector, но не для std::list или других контейнеров. Не уверен, возможно ли даже вычитание итераторов для std::list, и даже если это так, это операция O(N).

Источник

Это не должно иметь никакого значения; resize определяется с точки зрения insert а также erase, Но обычно предпочтительнее использовать стандартную идиому, чтобы ее можно было легко распознать. И, конечно, идиома erase-remove будет работать с любым контейнером последовательностей, а не только с теми, которые поддерживают resize, (Кажется, все стандартные контейнеры поддерживают resize, но это не является обязательным требованием. Поэтому он может быть недоступен для пользовательских контейнеров, даже если они поддерживают все необходимые операции.)

С точки зрения производительности: resize Я должен сделать еще один тест, чтобы определить, стирает ли он или вставляет, но я не могу себе представить, что это оказывает существенное влияние.

Источник

Я думаю erase в erase(first,last) гарантирует отсутствие элементов first доступны или изменены, в то время как resize гарантирует это только тогда, когда перераспределение не происходит из-за изменения размера.

Изменить: как отмечают другие, такое перераспределение никогда не произойдет, поэтому нет никакой разницы

Источник
Другие вопросы по тегам