Подтвердить что ты не робот

STL "erase-remove" idiom: Почему бы не "изменить размер"?

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

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

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() ); 
}
4b9b3361

Ответ 1

По моему мнению, есть две причины:

  • std::remove алгоритм требует только Forward Iterator, но - op требует Итератора с произвольным доступом.

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

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