Разница между стиранием и удалением

Я немного запутался в различии между использованием алгоритма std:: remove. В частности, я не могу понять, что удаляется, когда я использую этот алгоритм. Я написал небольшой тестовый код:

std::vector<int> a;
a.push_back(1);
a.push_back(2);

std::remove(a.begin(), a.end(), 1);


int s = a.size();

std::vector<int>::iterator iter = a.begin();
std::vector<int>::iterator endIter = a.end();

std::cout<<"Using iter...\n";
for(; iter != endIter; ++iter)
{
    std::cout<<*iter<<"\n";
}

std::cout<<"Using size...\n";
for(int i = 0; i < a.size(); ++i)
{
    std::cout<<a[i]<<"\n";
}

В обоих случаях выход был 2,2.

Однако, если я использую стирание с удалением что-то вроде этого:

a.erase(std::remove(a.begin(), a.end(), 1), a.end());

Я получаю вывод как 2.

Итак, мои вопросы:

(1). Существует ли использование std:: remove, кроме использования его с функцией стирания.

(2). Даже после выполнения std:: remove, почему a.size() возвращает 2, а не 1?

Я прочитал статью в Скотте Мейере. Эффективная книга STL об идиоме стирания-удаления. Но я все еще испытываю эту путаницу.

Ответ 1

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

Например, указатели на начало и конец обычного массива C являются форвардными итераторами и как таковые могут использоваться с remove():

int foo[100];

...

remove(foo, foo + 100, 42);    // Remove all elements equal to 42

Здесь очевидно, что remove() не может изменять размер массива!

Ответ 2

std::remove не удаляет фактические объекты, а скорее толкает их в конец контейнера. Фактическое удаление и освобождение памяти выполняется путем удаления. Итак:

(1). Существует ли использование std:: remove, кроме использования его с функцией стирания.

Да, это помогает получить пару итераторов в новую последовательность, не беспокоясь о надлежащем де-распределении и т.д.

(2). Даже после выполнения std:: remove, почему a.size() возвращает 2, а не 1?

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

Ответ 3

Проще всего я могу придумать:

erase() - это то, что вы можете сделать с элементом в контейнере. Учитывая, что итератор/индекс в контейнер, erase( it ) удаляет то, что итератор ссылается в контейнере.

remove() - это что-то, что вы можете сделать для диапазона, оно перенастраивает этот диапазон, но не стереть что-либо из диапазона.

Ответ 4

я столкнулся с той же проблемой, пытаясь понять разницу. объяснения, которые были даны до сих пор, справедливы на деньги, но я понял их только после просмотра примера;

#include <algorithm>
#include <string>
#include <iostream>
#include <cctype>

int main()
{
    std::string str1 = "Text with some   spaces";
    std::string::iterator it = remove(str1.begin(), str1.end(), 't');
    std::cout << str1 << std::endl;// prints "Tex wih some   spaceses"
    for (str1.begin();it != str1.end(); ++it) 
    {
         std::cout << *it; //prints "es"
    }

}

как вы можете видеть, удаление, только перемещает нижний регистр "t" в конец строки, возвращая новый итератор в конец новой строки (новая строка - это старая строка до того места, где удалена элемент вставлен) поэтому, когда вы печатаете итератор, который вы получили из "remove"

   "Text with some   spaces"
       ^   ^removes both 't', then shift all elements forward -1 //what we want to remove
   "Text with some   spaces"
                          ^ end of string                    -2 //original state of string
   "Tex with some   spacess"
                          ^end of string                     -3 //first 't' removed
   "Tex wih some   spaceses"
                          ^end of string                     -4 //second 't' removed
   "Tex wih some   spaceses"
                        ^new iterator that remove() returned -5 // the state of string after "remove" and without "erase"

если вы передадите итератор, полученный с шага 5, на "erase()", он будет знать, что он удалит оттуда до конца строки, переопределяющую строку в процессе

Ответ 5

Что делает std:: remove?

Здесь псевдокод std::remove. Возьмите несколько секунд, чтобы посмотреть, что он делает, а затем прочитайте объяснение.

Iter remove(Iter start, Iter end, T val) {
    Iter ret = start;
    while(start != end) {
        if (*start == val) {
            start++; //skip
         }
         else //copy value
             *ret++ = *start++;
     }
     return ret;
}

Обратите внимание, что remove просто перемещает элементы в последовательности, переписывая значения, которые вы хотите удалить. Значит, ценности, которые вы хотели удалить, действительно исчезли, но тогда какая проблема? Скажем, у вас есть вектор со значениями {1, 2, 3, 4, 5}. После вызова remove для val = 3 вектор теперь имеет {1, 2, 4, 5, 5}. То есть 4 и 5 были перемещены вверх так, что 3 ушло от вектора, но размер вектора не изменился. Кроме того, конец вектора теперь содержит дополнительную левую над копией 5.

Что делает вектор:: erase do?

std::erase принимает начало и конец диапазона, из которого вы хотите избавиться. Он не принимает значение, которое вы хотите удалить, только начало и конец диапазона. Здесь псевдокод для того, как он работает:

erase(Iter first, Iter last)
{
    //copy remaining elements from last
    while (last != end())
        *first++ = *last++;

   //truncate vector
   resize(first - begin());
}

Таким образом, операция стирания фактически изменяет размер контейнера и поэтому освобождает память.

Идиома удаления стирания

Комбинация std::remove и std::erase позволяет удалить соответствующие элементы из контейнера, чтобы контейнер фактически усекался, если элементы были удалены. Вот как это сделать:

//first do the remove
auto removed = std::remove(vec.begin(), vec.end(), val);

//now truncate the vector
vec.erase(removed, vec.end());

Это известно как идиома удаления-стирания. Почему он спроектирован так? Понимание заключается в том, что операция поиска элементов является более общей и независимой от базового контейнера (зависит только от итераторов). Однако операция стирания зависит от того, как контейнер хранит память (например, у вас может быть связанный список вместо динамического массива). Таким образом, STL ожидает, что контейнеры будут выполнять свою собственную стирание, одновременно предоставляя общую операцию "удалить", чтобы все контейнеры не могли реализовать этот код. На мой взгляд, имя очень вводит в заблуждение, а std::remove должно было быть вызвано std::find_move.

Примечание. Над кодом строго псевдокод. Фактическая реализация STL более умна, например, используя std::move вместо копирования.

Ответ 6

удалить не "действительно" удалить ничего, потому что он не может.

Чтобы "фактически" удалить элементы из контейнера, вам нужно получить доступ к API-интерфейсам контейнеров. Если удаление выполняется только с помощью итераторов, независимо от того, на какие контейнеры указывают эти итераторы. Следовательно, даже если удаление требует "фактического удаления", оно не может.

Удалите "удаленные" элементы с помощью следующих элементов, которые не были удалены, и тогда вызывающий может решить использовать возвращенный новый логический end вместо исходного end.

В вашем случае удалите логически удаленный 1 из vector, но размер остался до 2. Стереть фактически удалили элементы из вектора. [от вектора new end до old end]

Основная идея remove заключается в том, что она не может изменить количество элементов и просто удалять элементы из диапазона в соответствии с критериями.