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

Question

假设我想从std::vector中删除唯一的元素(不是去掉重复的元素，而是只保留至少发生了2次的元素)，并且我希望以一种非常低效率的方式来实现这一点--在std::remove_ifing时调用std::count。考虑以下代码：

#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的工作原理。要移除的值不一定会移到末尾。请参见：

移除是通过(通过移动赋值)移动范围中的元素来完成的，其方式是使不被移除的元素出现在范围的开头。优先选择

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

从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，那么范围只会被置换。

Answer 3

我增加了一些产出：

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

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) {

        std::cout << "number " << n << ": ";
        for (auto i : vec) std::cout << i << ' ';
        auto c = std::count(vec.begin(), vec.end(), n);
        std::cout << ", count: " << c << std::endl;
        return c == 1;
    });

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

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

并得到了

number 1: 1 2 6 3 6 2 7 4 4 5 6 , count: 1
number 2: 1 2 6 3 6 2 7 4 4 5 6 , count: 2
number 6: 2 2 6 3 6 2 7 4 4 5 6 , count: 3
number 3: 2 6 6 3 6 2 7 4 4 5 6 , count: 1
number 6: 2 6 6 3 6 2 7 4 4 5 6 , count: 4
number 2: 2 6 6 3 6 2 7 4 4 5 6 , count: 2
number 7: 2 6 6 2 6 2 7 4 4 5 6 , count: 1
number 4: 2 6 6 2 6 2 7 4 4 5 6 , count: 2
number 4: 2 6 6 2 4 2 7 4 4 5 6 , count: 3
number 5: 2 6 6 2 4 4 7 4 4 5 6 , count: 1
number 6: 2 6 6 2 4 4 7 4 4 5 6 , count: 3
2 6 6 2 4 4 6 

正如你所看到的，计数可能是错误的。我无法为您的特例创建一个示例，但通常您必须担心错误的结果。

首先，数字4被计数两次，在接下来的步骤中，数字4被计数为三次。计数是错误的，你不能依赖它们。