在std :: remove_if执行期间遍历容器是否安全？

Question

假设我想从中删除唯一元素std::vector（不消除重复项，而仅保留至少出现2次的元素），并且我想以一种非常低效的方式实现这一点-通过std::count在std::remove_ifing时调用。考虑以下代码：

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 6, 3, 6, 2, 7, 4, 4, 5, 6};

    auto to_remove = std::remove_if(vec.begin(), vec.end(), [&vec](int n) {
        return std::count(vec.begin(), vec.end(), n) == 1;
    });

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

    for (int i : vec) std::cout << i << ' ';
}

从参考开始，std::remove_if我们知道从开始的元素to_remove具有未指定的值，但是我想知道它们到底有多未指定。

为了解释我所关心的远一点-我们可以看到，应删除的元素是1，3，5和7-唯一的唯一值。std::remove_if会将移至1末尾，但不能保证1在上述操作之后末尾会有一个值。可以（由于未指定该值）将其转换为该值3，并使该std::count调用返回（例如）2作为随后遇到的值的计数3吗？

本质上，我的问题是-这是否一定能正常工作，而我的意思是从工作中低效率地擦除唯一元素std::vector？

我对语言-律师答案（可能是“ 标准说这种情况是可能的，应该避免这种情况 ”）和实践中的答案（可能是“ 标准说这种情况是可能的，但实际上3）都很感兴趣此值不可能最终成为完全不同的值，例如 “）。

Answer 1

谓词true第一次返回后，范围中将有一个未指定的值。这意味着谓词的任何后续调用都将计入未指定的值。因此，该计数可能不正确，您可以保留不希望被丢弃的值，也可以丢弃应保留的值。

您可以修改谓词，以便保留其返回true的次数，并相应地减小范围。例如;

std::size_t count = 0;
auto to_remove = std::remove_if(vec.begin(), vec.end(), [&vec, &count](int n)
{
    bool once = (std::count(vec.begin(), vec.end() - count, n) == 1);
    if (once) ++count;
    return once;
 });

从向量的结束迭代器中减去整数值是安全的，但对于其他容器而言不一定是正确的。

Answer 2

您误解了std::remove_if工作原理。要删除的值不一定要移到最后。看到：

删除是通过移动（通过移动分配）范围中的元素来完成的，要删除的元素出现在范围的开头。cppreference

这是范围状态的唯一保证。据我所知，并不是禁止将所有值转移，它仍然可以满足复杂性。因此，某些编译器可能会将不需要的值移到最后，但这只是多余的工作。

可能的实现示例1 2 3 4 8 5：

   v               - read position
   1 2 3 4 8 5     - X will denotes shifted from value = unspecified
   ^               - write position
     v          
   1 2 3 4 8 5     1 is odd, ++read
   ^
       v
   2 X 3 4 8 5     2 is even, *write=move(*read), ++both
     ^   
         v
   2 X 3 4 8 5     3 is odd, ++read
     ^
           v
   2 4 3 X 8 5     4 is even, *write=move(*read), ++both
       ^
             v
   2 4 8 X X 5     8 is even, *write=move(*read), ++both
         ^

   2 4 8 X X 5     5 is odd, ++read
         ^         - this points to the new end.

因此，通常来说，您不能依赖于count返回任何有意义的值。由于在move == copy的情况下（按原样ints），结果数组为2 4 8|4 8 5。奇数和偶数的计数都不正确。在情况下std::unique_ptr的X==nullptr，从而为计数nullptr和删除值可能是错误的。其他剩余值不应留在数组的末尾，因为没有完成任何复制。

请注意，这些值不是未指定的，因为您无法知道它们。它们正是移动分配的结果，可能会使值保持未指定状态。如果它指定了移出变量的状态（也是std::unique_ptr如此），那么它们将是已知的。例如，如果move==swap这样，范围将仅被置换。