C++ 向量的 std::remove 和 erase 之间的区别？

Difference between std::remove and erase for vector?

提问by Abruzzo Forte e Gentile

I have a doubt that I would like to clarify in my head. I am aware of the different behavior for std::vectorbetween eraseand std::removewhere the first physically removes an element from the vector, reducing size, and the other just moves an element leaving the capacity the same.

我有一个疑问，我想在我的脑海中澄清。我知道对于不同的行为std::vector之间erase，并std::remove在第一物理载体中删除的元素，减小尺寸和其他只是移动而使容量相同的元素。

Is this just for efficiency reasons? By using erase, all elements in a std::vectorwill be shifted by 1, causing a large amount of copies; std::removedoes just a 'logical' delete and leaves the vector unchanged by moving things around. If the objects are heavy, that difference might matter, right?

这仅仅是出于效率原因吗？通过使用erase，a中的所有元素std::vector都会被移位1，造成大量的拷贝；std::remove只做一个“逻辑”删除，并通过移动东西来保持向量不变。如果物体很重，这种差异可能很重要，对吗？

采纳答案by David Rodríguez - dribeas

Is this just for efficiency reason? By using erase all elements in a std::vector will be shifted by 1 causing a large amount of copies; std::remove does just a 'logical' delete and leaves the vector unchanged by moving things around. If the objects are heavy that difference mihgt matter, right?

这只是出于效率原因吗？通过使用擦除 std::vector 中的所有元素将被移动 1 导致大量副本；std::remove 只是一个“逻辑”删除，并通过移动东西使向量保持不变。如果物体很重，那么差异可能很重要，对吗？

The reason for using this idiom is exactly that. There is a benefit in performance, but not in the case of a single erasure. Where it does matter is if you need to remove multiple elements from the vector. In this case, the std::removewill copy each not removedelement only once to its final location, while the vector::eraseapproach would move all of the elements from the position to the end multiple times. Consider:

使用这个成语的原因正是如此。在性能上有好处，但不是在单个擦除的情况下。重要的是您是否需要从向量中删除多个元素。在这种情况下，std::remove将每个未删除的元素仅复制一次到其最终位置，而该vector::erase方法会将所有元素从该位置移动到末尾多次。考虑：

std::vector<int> v{ 1, 2, 3, 4, 5 };
// remove all elements < 5

If you went over the vector removing elements one by one, you would remove the 1, causing copies of the remainder elements that get shifted (4). Then you would remove 2 and shift all remainding elements by one (3)... if you see the pattern this is a O(N^2)algorithm.

如果您逐一查看删除元素的向量，则会删除 1，从而导致剩余元素的副本被移动 (4)。然后您将删除 2 并将所有剩余元素移动一（3）...如果您看到该模式，这是一个O(N^2)算法。

In the case of std::removethe algorithm maintains a read and write heads, and iterates over the container. For the first 4 elements the read head will be moved and the element tested, but no element is copied. Only for the fifth element the object would be copied from the last to the first position, and the algorithm will complete with a single copy and returning an iterator to the second position. This is a O(N)algorithm. The later std::vector::erasewith the range will cause destruction of all the remainder elements and resizing the container.

在std::remove算法维护一个读写头的情况下，并遍历容器。对于前 4 个元素，将移动读取头并测试元素，但不会复制任何元素。只有对于第五个元素，对象才会从最后一个位置复制到第一个位置，算法将完成一个副本，并返回一个迭代器到第二个位置。这是一个O(N)算法。后面std::vector::erase的范围将导致所有剩余元素的破坏并调整容器的大小。

As others have mentioned, in the standard library algorithms are applied to iterators, and lack knowledge of the sequence being iterated. This design is more flexible than other approaches on which algorithms are aware of the containers in that a single implementation of the algorithm can be used with any sequence that complies with the iterator requirements. Consider for example, std::remove_copy_if, it can be used even without containers, by using iterators that generate/accept sequences:

正如其他人所提到的，标准库中的算法应用于迭代器，并且缺乏对被迭代序列的了解。这种设计比算法了解容器的其他方法更灵活，因为该算法的单个实现可以与符合迭代器要求的任何序列一起使用。例如，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
                    );

That single line of code will filter out all even numbers from standard input and dump that to standard output, without requiring the loading of all numbers into memory in a container. This is the advantage of the split, the disadvantage is that the algorithms cannot modify the container itself, only the values referred to by the iterators.

那一行代码将过滤掉标准输入中的所有偶数并将其转储到标准输出，而无需将所有数字加载到容器的内存中。这是拆分的优点，缺点是算法不能修改容器本身，只能修改迭代器引用的值。

回答by yves Baumes

std::removeis an algorithm from the STL which is quite container agnostic. It requires some concept, true, but it has been designed to also work with C arrays, which are static in sizes.

std::remove是来自 STL 的一种算法，它与容器无关。它需要一些概念，没错，但它也被设计为也适用于大小为静态的 C 数组。

回答by Zac Howland

std::removesimply returns a new end()iterator to point to one past the last non-removed element (the number of items from the returned value to end()will match the number of items to be removed, but there is no guarantee their values are the same as those you were removing - they are in a valid but unspecified state). This is done so that it can work for multiple container types (basically any container type that a ForwardIteratorcan iterate through).

std::remove简单地返回一个新的end()迭代器，指向最后一个未删除元素之后的元素（从返回值到end()的项目数将与要删除的项目数相匹配，但不能保证它们的值与您之前的值相同删除 - 它们处于有效但未指定的状态）。这样做是为了它可以用于多种容器类型（基本上是ForwardIterator可以迭代的任何容器类型）。

std::vector::eraseactually sets the new end()iterator after adjusting the size. This is because the vector's method actually knows how to handle adjusting it's iterators (the same can be done with std::list::erase, std::deque::erase, etc.).

std::vector::erase实际上end()在调整大小后设置新的迭代器。这是因为vector的方法实际上知道如何处理它调整的迭代器（同样是可以做到的std::list::erase，std::deque::erase等等）。

removeorganizes a given container to remove unwanted objects. The container's erase function actually handles the "removing" the way that container needs it to be done. That is why they are separate.

remove组织给定的容器以删除不需要的对象。容器的擦除功能实际上以容器需要的方式处理“删除”。这就是为什么它们是分开的。

回答by Nathan Monteleone

I think it has to do with needing direct access to the vector itself to be able to resize it. std::remove only has access to the iterators, so it has no way of telling the vector "Hey, you now have fewer elements".

我认为这与需要直接访问向量本身才能调整其大小有关。std::remove 只能访问迭代器，所以它无法告诉向量“嘿，你现在的元素更少了”。

See yves Baumes answer as to why std::remove is designed this way.

请参阅 yves Baumes 关于为什么 std::remove 以这种方式设计的回答。

回答by Jon

Yes, that's the gist of it. Note that eraseis also supported by the other standard containers where its performance characteristics are different (e.g. list::eraseis O(1)), while std::removeis container-agnostic and works with any type of forward iterator(so it works for e.g. bare arrays as well).

是的，这就是它的要点。请注意，erase其他标准容器也支持它的性能特征不同（例如list::erase是 O(1)），而std::remove容器不可知并且适用于任何类型的前向迭代器（因此它适用于例如裸数组同样）。

回答by Duncan Smith

Kind of. Algorithms such as remove work on iterators (which are an abstraction to represent an element in a collection) which do not necessarily know which type of collection they are operating on - and therefore cannot call members on the collection to do the actual removal.

的种类。诸如 remove 之类的算法在迭代器上工作（它是表示集合中元素的抽象），它们不一定知道它们正在操作哪种类型的集合 - 因此不能调用集合上的成员来执行实际删除。

This is good because it allows algorithms to work generically on any container and also on ranges that are subsets of the entire collection.

这很好，因为它允许算法在任何容器上以及作为整个集合的子集的范围上通用。

Also, as you say, for performance - it may not be necessary to actually remove (and destroy) the elements if all you need is access to the logical end position to pass on to another algorithm.

此外，正如您所说，为了性能 - 如果您只需要访问逻辑结束位置以传递给另一个算法，则可能没有必要实际删除（和销毁）元素。

回答by Pete Becker

Standard library algorithms operate on sequences. A sequence is defined by a pair of iterators; the first points at the first element in the sequence, and the second points one-past-the-end of the sequence. That's all; algorithms don't care where the sequence comes from.

标准库算法对序列进行操作。一个序列由一对迭代器定义；第一个点在序列中的第一个元素，第二个点在序列的末尾。就这样; 算法不关心序列来自哪里。

Standard library containers hold data values, and provide a pair of iterators that specify a sequence for use by algorithms. They also provide member functions that may be able to do the same operations as an algorithm more efficiently by taking advantage of the internal data structure of the container.

标准库容器保存数据值，并提供一对迭代器来指定算法使用的序列。它们还提供成员函数，通过利用容器的内部数据结构，这些成员函数可能能够更有效地执行与算法相同的操作。

回答by RLT

Try following code to get better understanding.

尝试以下代码以获得更好的理解。

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
const auto newend (remove(begin(v), end(v), 2));

for(auto a : v){
    cout << a << " ";
}
cout << endl;
v.erase(newend, end(v));
for(auto a : v){
    cout << a << " ";
}