std ::删除和擦除矢量的区别？ [英] Difference between std::remove and erase for vector?

问题描述

我有一个疑问，我想在我的头脑中澄清。我知道 std :: vector 在擦除和 std ::之间的不同行为remove 其中第一个从向量中物理删除一个元素，减小大小，另一个只是移动一个元素，使容量保持不变。

这是为了效率的原因吗？通过使用 erase ， std :: vector 中的所有元素将被移动1，导致大量副本; std :: remove 只是一个逻辑删除，并通过移动它使矢量保持不变。如果对象很重，那差别可能很重要，对吗？

解决方案

原因？通过使用擦除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 
）; 
 

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

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

Is this just for efficiency reasons? 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 might matter, right?

解决方案

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?

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::remove will copy each not removed element only once to its final location, while the vector::erase approach would move all of the elements from the position to the end multiple times. Consider:

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.

In the case of std::remove the 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::erase with the range will cause destruction of all the remainder elements and resizing the container.

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::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.

这篇关于std ::删除和擦除矢量的区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！