擦除和移除的区别

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。

然而，如果我使用像这样的remove和erase：

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

我得到的输出为2。

所以我的问题是:

(1). 除了与erase函数一起使用外，是否有其他用途可以使用std::remove？

(2). 即使执行了std::remove，为什么a.size()返回2而不是1？

我在Scott Meyer的Effective STL书中读到了关于erase-remove惯用语的内容。但我仍然对此感到困惑。

- Naveen

---

我觉得这个问题最难的部分是"erase"和"remove"在英语中的意思几乎相同，所以很容易忘记它们各自的含义。 - Chris Huang-Leaver

Answer 1

remove() 实际上并不会从容器中删除元素，它只会将未删除的元素向上移动到已删除元素的位置。关键在于要认识到 remove() 不仅适用于容器，还可以适用于任何任意的前向迭代器对：这意味着它不能实际删除元素，因为任意迭代器对并不一定具有删除元素的能力。

例如，常规 C 数组的起始和结束指针是前向迭代器，因此可以与 remove() 一起使用：

int foo[100];

...

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

很明显这里remove()不能改变数组的大小！

- j_random_hacker

Answer 2

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 的 remove 后，向量现在具有 {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());

这被称为remove-erase惯用语。它为什么被设计成这样呢？洞见是查找元素的操作更加通用并独立于基础容器(只依赖于迭代器)。但是，删除的操作取决于容器存储内存的方式(例如，您可能有链接列表而不是动态数组)。因此，STL希望容器进行自己的删除，同时提供通用的“remove”操作，使所有容器都不必实现该代码。在我看来，这个名字非常误导，std :: remove应该被称为std :: find_move。

注意：上面的代码严格来说是伪代码。实际的STL实现更加智能，例如使用std :: move而不是拷贝。

- Shital Shah

Answer 3

std::remove并不会真正删除对象，而是将它们移动到容器的末尾。实际的删除和内存释放是通过erase完成的。因此：

(1). 除了与erase函数一起使用，std::remove是否还有其他用途？

是的，它帮助我们获得一组新序列的迭代器，而不必担心正确的内存释放等问题。

(2). 即使执行了std::remove，为什么a.size()返回2而不是1？

容器仍然持有那些对象，你只是有了一组新的迭代器来操作它们。因此，大小仍然与原来一样。

- dirkgently

---

实际上，std::remove()函数并不会将删除的元素移动到容器的末尾--容器的剩余位置仍然包含它们原来的值。（这是为了保持使用前向迭代器的O(n)时间复杂度。） - j_random_hacker

它的意思是：“消除迭代器i所引用的范围[first，last)中满足以下相应条件的所有元素：*i == value”，我解释为最终该范围不再包含任何“已删除”值。有趣的是，我以前不知道这一点。但我认为不能指望这些元素与之前完全相同。至少，如果该范围包含了一个“已删除”的值，那么肯定不行。所以我认为cplusplus.com又错了:D - Johannes Schaub - litb

仍在阅读草稿--使用erase更有趣，它调用dtors。在我看来，remove只是关于交换指针，这也是迭代器的实现方式，或多或少。 - dirkgently

最后，我认为这只是措辞不当，我不应该删除我的回答。我认为 returned_iterator 后面的元素只有一些不确定的值。唉 :( 嘿嘿 - Johannes Schaub - litb

@litb：我认为remove()不能只是“将剩余的元素清零”，因为表达式“*i = 0”（其中i是前向迭代器）不一定是有效的。 - j_random_hacker

Answer 4

在容器（比如 vector）中，如果想要删除一些元素（例如值相等或其他条件，如小于），通常会结合成员函数 erase 和 std::remove 或 std::remove_if 使用。

在 vector 中，函数 erase 可以根据位置删除元素，例如：

iterator erase (iterator position);

iterator erase (iterator first, iterator last);

但如果你想删除满足某些条件的元素，则可以将它与 std::remove 或 std::remove_if 结合使用。

例如，如果你想删除下面 vector 中所有为 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);

通过范围来擦除（总是以 end() 结尾）

vec.erase(last, vec.end());

来源：

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

- Jayhello

---

这是最清晰和最全面的答案。此外，它还直观地展示了迭代器，包括remove返回的迭代器，并显示了remove和erase之间的迭代器关系。在阅读这个答案之前，我不理解事情是如何工作的。 - mireazma

Answer 5

我曾经遇到过同样的问题，试图理解它们之间的差异。到目前为止所给出的解释都是非常准确的，但是在看到一个示例之后，我才真正理解了它们。

#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"
    }

}

正如您所看到的，remove()方法只是将小写字母“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()"，它将知道从那里开始删除直到字符串的末尾，并重新调整字符串的大小。

- Molegrammer

Answer 6

我能想到的最简单的解释是：

erase() 是可以对容器中的元素执行的操作。给定一个指向容器中某个元素的迭代器/索引，erase( it ) 将从容器中删除该迭代器所指向的元素。

remove() 是可以对一段范围进行操作的函数，它重新排列了该范围但不会从范围中删除任何内容。

- anon

Answer 7

remove并不能真正的“删除”任何东西，因为它无法做到。

为了从容器中“真正”删除元素，你需要访问容器API。而remove仅使用迭代器，不管这些迭代器指向哪个容器。因此，即使remove想要“真正删除”，它也做不到。

remove通过其它未被删除的元素覆盖“已移除”的元素，然后由调用方决定是否使用返回的新逻辑end，而非原始的end。

在你的情况下，remove在vector a中逻辑上删除了1，但大小仍然保持为2。erase实际上从向量中删除了元素。[从向量new end到old end]

remove的主要思想是它不能改变元素的数量，它只能按照条件从范围中删除元素。

- aJ.