c++ - vector 的 std::remove 和删除之间的区别？

Question

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

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

Answer 1

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?

使用这个成语的原因正是如此。在性能上有好处，但在单次删除的情况下没有。重要的是您是否需要从 vector 中删除多个元素。在这种情况下，std::remove 只会将每个 not removed 元素复制一次到其最终位置，而 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
                    );

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