Разница между std:: удалить и удалить для вектора?

Ответ 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

Стандартные библиотечные алгоритмы работают с последовательностями. Последовательность определяется парой итераторов; первые точки в первом элементе в последовательности, а второй - один за концом последовательности. Все это; алгоритмы не заботятся о том, откуда происходит последовательность.

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