std :: remove和erase之间的区别？

Question

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

这只是出于效率原因吗？通过使用erase,a中的所有元素std::vector将被移位1,从而导致大量复制; std::remove做一个'逻辑'删除并通过移动东西保持向量不变.如果物体很重,这种差异可能很重要,对吧？

Answer 1

这只是出于效率的原因吗？通过使用擦除,std :: vector中的所有元素将被移位1,从而导致大量复制; std :: remove只是一个'逻辑'删除,并通过移动东西保持向量不变.如果物体很重,那么差异很重要吧？

使用这个习语的原因正是如此.性能有一个好处,但不是单擦除的情况.重要的是你需要从向量中删除多个元素.在这种情况下,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
                    );

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

Answer 2

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

Answer 3

std::remove只返回一个新的end()迭代器,指向一个超过最后一个未删除的元素(返回值中end()的项目数将匹配要删除的项目数,但不能保证它们的值与您的值相同删除 - 它们处于有效但未指定的状态).这样做是为了使它可以用于多种容器类型(基本上任何ForwardIterator可以迭代的容器类型).

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

remove组织一个给定的容器来删除不需要的对象.容器的擦除功能实际上处理"移除"容器需要它完成的方式.这就是他们分开的原因.

Answer 4

我认为这与需要直接访问矢量本身以便能够调整它有关.std :: remove只能访问迭代器,所以它无法告诉向量"嘿,你现在有更少的元素".

请参阅yves Baumes回答为什么std :: remove是这样设计的.