Разница между std:: удалить и удалить для вектора?
У меня есть сомнения, что я хотел бы уточнить в моей голове. Я знаю о различном поведении std::vector
между erase
и std::remove
, где первый физически удаляет элемент из вектора, уменьшая размер, а другой просто перемещает элемент, оставляя емкость одинаковым.
Это просто по соображениям эффективности? Используя erase
, все элементы в std::vector
будут сдвинуты на 1, вызывая большое количество копий; std::remove
выполняет только "логическое" удаление и оставляет вектор неизменным, перемещая вещи вокруг. Если объекты тяжелые, эта разница может иметь значение, верно?
Ответы
Ответ 1
Это просто по соображениям эффективности? При использовании стирания все элементы в std::vector будут сдвинуты на 1, вызывая большое количество копий; std:: remove выполняет только "логическое" удаление и оставляет вектор неизменным, перемещая вещи вокруг. Если объекты тяжелы, то разница в значении mihgt, правильно?
Причиной использования этой идиомы является именно это. В производительности есть преимущество, но не в случае единственного стирания. Если это имеет значение, вам нужно удалить несколько элементов из вектора. В этом случае std::remove
будет копировать каждый не удаленный элемент только один раз до его конечного местоположения, тогда как подход vector::erase
будет перемещать все элементы с позиции до конца несколько раз. Рассмотрим:
std::vector<int> v{ 1, 2, 3, 4, 5 };
// remove all elements < 5
Если вы переместили элементы, удаляющие вектор, один за другим, вы должны удалить 1, вызывая копирование оставшихся элементов, которые будут сдвинуты (4). Затем вы удаляете 2 и смещаете все элементы останова на один (3)... если вы видите шаблон, это алгоритм O(N^2)
.
В случае std::remove
алгоритм поддерживает головки чтения и записи и выполняет итерацию по контейнеру. Для первых 4 элементов считываемая головка будет перемещена и элемент проверен, но ни один элемент не будет скопирован. Только для пятого элемента объект будет скопирован с последней на первую позицию, и алгоритм завершится одной копией и вернет итератор во вторую позицию. Это алгоритм O(N)
. Более поздний std::vector::erase
с диапазоном приведет к разрушению всех остальных элементов и изменению размера контейнера.
Как отмечали другие, в стандартной библиотеке алгоритмы применяются к итераторам и не знают, что последовательность повторяется. Этот дизайн более гибкий, чем другие подходы, по которым алгоритмы осведомлены о контейнерах, что одна реализация алгоритма может использоваться с любой последовательностью, которая соответствует требованиям итератора. Рассмотрим, например, std::remove_copy_if
, его можно использовать даже без контейнеров, используя итераторы, которые генерируют/принимают последовательности:
std::remove_copy_if(std::istream_iterator<int>(std::cin),
std::istream_iterator<int>(),
std::ostream_iterator<int>(std::cout, " "),
[](int x) { return !(x%2); } // is even
);
Эта единственная строка кода отфильтровывает все четные числа со стандартного ввода и дампа, что на стандартный вывод, не требуя загрузки всех чисел в память в контейнере. Это преимущество разделения, недостатком является то, что алгоритмы не могут изменять сам контейнер, только значения, на которые ссылаются итераторы.
Ответ 2
std::remove
- это алгоритм из STL, который вполне агностик. Это требует некоторого понятия, правда, но оно также предназначено для работы с массивами C, которые являются статичными по размерам.
Ответ 3
std::remove
просто возвращает новый итератор end()
, чтобы указать на один минус последнего неиспользуемого элемента (количество элементов из возвращаемого значения до end()
будет соответствовать количеству элементов, которые нужно удалить, но там не гарантирует, что их значения совпадают с теми, которые вы удаляли - они находятся в действительном, но неуказанном состоянии). Это делается так, что он может работать для нескольких типов контейнеров (в основном, любой тип контейнера, который может ForwardIterator
выполнить через).
std::vector::erase
фактически устанавливает новый итератор end()
после настройки размера. Это связано с тем, что метод vector
действительно знает, как обрабатывать его итераторы (то же самое можно сделать с помощью std::list::erase
, std::deque::erase
и т.д.).
remove
организует данный контейнер для удаления нежелательных объектов. Функция стирания контейнера фактически обрабатывает "удаление" способа, которым это необходимо для контейнера. Вот почему они разделены.
Ответ 4
Я думаю, что это связано с необходимостью прямого доступа к самому вектору, чтобы иметь возможность изменять его размер. std:: remove имеет доступ только к итераторам, поэтому он не может передать вектор "Эй, у вас теперь меньше элементов".
См. yves Baumes ответьте, почему std:: remove сконструирован таким образом.
Ответ 5
Да, это суть. Обратите внимание, что erase
также поддерживается другими стандартными контейнерами, где его характеристики производительности различны (например, list:: erase - O (1)), в то время как std::remove
является агрегированным с контейнером и работает с любым типом forward iterator (так что он работает, например, для голых массивов).
Ответ 6
Вид. Алгоритмы, такие как удаление работы с итераторами (которые представляют собой абстракцию для представления элемента в коллекции), которые не обязательно знают, к какому типу коллекции они работают, и, следовательно, не могут вызвать членов коллекции для фактического удаления.
Это хорошо, потому что это позволяет алгоритмам работать в общем случае на любом контейнере, а также на диапазонах, которые являются подмножествами всей коллекции.
Кроме того, как вы говорите, для производительности - может быть необязательно фактически удалять (и уничтожать) элементы, если все, что вам нужно, - это доступ к логической конечной позиции для перехода к другому алгоритму.
Ответ 7
Стандартные библиотечные алгоритмы работают с последовательностями. Последовательность определяется парой итераторов; первые точки в первом элементе в последовательности, а второй - один за концом последовательности. Все это; алгоритмы не заботятся о том, откуда происходит последовательность.
Контейнеры стандартной библиотеки хранят значения данных и предоставляют пару итераторов, которые определяют последовательность для использования алгоритмами. Они также предоставляют функции-члены, которые могут выполнять те же операции, что и алгоритм, более эффективно, используя внутреннюю структуру данных контейнера.