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

Question

Я немного озадачен разницей между использованием алгоритма 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» об идиоме удаления-удаления. Но я все еще испытываю эту путаницу.

Answer 1

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

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

int foo[100];

...

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

Iter remove(Iter start, Iter end, T val) {
    Iter destination = start;

    //loop through entire list
    while(start != end) { 
        //skip element(s) to be removed
        if (*start == val) { 
            start++; 
         }
         else //retain rest of the elements
             *destination++ = *start++;
     }

     //return the new end of the list
     return destination;
}

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

Что делает vector :: erase?

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 вместо copy.

Answer 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' в конец строки, а новый итератор возвращается в конец новой строки (новая строка - старая строка до того места, где удален элемент вставлен) Вот почему, когда вы печатаете итератор, который вы получили от "удалить"

   "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 ()", он будет знать, что стереть оттуда до конца строки, изменяя размер строки в процессе

Answer 5

Самое простое, что я могу придумать:

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

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

Answer 6

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

Чтобы "фактически" удалить элементы из контейнера, вам нужно получить доступ к API-интерфейсам контейнера. Где as remove работает только с итераторами, независимо от того, на какие контейнеры указывают эти итераторы. Следовательно, даже если удаление хочет «фактическое удаление», оно не может.

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

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

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

Answer 7

Чтобы удалить элемент с некоторым условием (равным некоторому значению или другим условием, например, меньшим) в контейнере, как вектор, он всегда объединяет функцию-функцию erase и std::remove или std::remove_if.

В векторе функция erase может просто удалять элемент по позиции, например:

стирание итератора (позиция итератора);

стирание итератора (сначала итератор, потом итератор);

Но если вы хотите стереть элементы с некоторым условием, вы можете объединить их с std::remove или std::remove_if.

Например, вы хотите стереть все элементы 6 в приведенном ниже векторе:

std::vector<int> vec{6, 8, 10, 3, 4, 5, 6, 6, 6, 7, 8};
// std::remove move elements and return iterator for vector erase funtion
auto last = std::remove(vec.begin(), vec.end(), 6);
for(int a:vec)
    cout<<a<<" ";
cout<<endl;
// 8 10 3 4 5 7 8 6 6 7 8 

vec.erase(last, vec.end());
for(int a:vec)
    cout<<a<<" ";
cout<<endl;
// 8 10 3 4 5 7 8 

std::remove работает как показано ниже, он не стирает никаких элементов, он просто перемещает элементы и возвращает итератор.

Возможная реализация:

template< class ForwardIt, class T >
ForwardIt remove(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::find(first, last, value);
    if (first != last)
        for(ForwardIt i = first; ++i != last; )
            if (!(*i == value))
                *first++ = std::move(*i);
    return first;
}

Вывод:

Если вы хотите удалить элементы с некоторым условием, вы по существу используете vector::iterator erase (iterator first, iterator last);.

Первый запуск диапазона:

auto last = std :: remove (vec.begin (), vec.end (), equal_condition_value);

стирать по диапазону (всегда с концом ())

vec.erase (последняя, ​​vec.end ());

цитируется:

https://en.cppreference.com/w/cpp/algorithm/remove