STL «стереть-удалить» идиома: почему бы не «изменить размер-удалить»?
Обычно считается, что это хороший способ полностью удалить нужные элементы из 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() );
}
Решение
На мой взгляд, есть две причины:
-
std::removeалгоритм требует только прямой итератор, но-Оператор требует итератор произвольного доступа. -
Результат
std::removeозначает «новый конец контейнера». Логически, мы должны стереть [«новый конец контейнера», «старый конец контейнера»).
Другие решения
Это эквивалентно для std :: vector, но не для std :: list или других контейнеров. Не уверен, возможно ли даже вычитание итераторов для std :: list, и даже если это так, это операция O (N).
Это не должно иметь никакого значения; resize определяется в терминах
из insert а также erase, Но обычно предпочтительнее использовать
стандартная идиома, так что это может быть легко распознано. И из
Конечно, идиома стирания-удаления будет работать с любой последовательностью
контейнер, а не только те, которые поддерживают resize, (Все
стандартные контейнеры, кажется, поддерживают resize, но это
не похоже на требование. Так что это может быть недоступно
в пользовательских контейнерах, даже если они поддерживают все
необходимые операции.)
С точки зрения производительности: resize должен сделать еще один
тест, чтобы определить, стирает ли он или вставляет, но
Я не могу себе представить, что это оказывает существенное влияние.
Я думаю erase в erase(first,last) гарантирует отсутствие элементов first доступны или изменены, в то время как resize гарантирует это только тогда, когда перераспределение не происходит из-за изменения размера.
Изменить: как отмечают другие, такое перераспределение никогда не произойдет, поэтому нет никакой разницы
detector