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

Question

假设我想从 std::vector 中删除 unique 元素（不是删除重复项，而是只保留至少出现 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 << ' ';
}

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

进一步解释我的担忧 - 我们可以看到应该删除的元素是 1、3、5 和 7 - 唯一独特的价值。 std::remove_if 会将 1 移动到末尾，但不能保证在上述操作后末尾会有一个值 1。这是否可以（由于该值是 未指定的）它将变成 3 并使 std::count 调用 return 计数（对于example) 2 为后来遇到的值 3?

基本上我的问题是 - 这是否保证有效，并且 work 我的意思是低效地从 std::vector?

中删除唯一元素

我对语言律师的回答（可能是“标准说这种情况是可能的，你应该避免它”）和实践中的回答（这可能是“标准说这种情况是可能的，但实际上没有办法让这个值最终成为一个完全不同的值，例如 3”）。

Answer 1

我添加了一些输出：

#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 三次。计数是错误的，你不能依赖它们。

Answer 2

谓词returnstrue第一次之后，范围内会有一个未指定的值。这意味着谓词的任何后续调用都将计算一个未指定的值。因此计数可能不正确，您可以不影响您打算丢弃的值，也可以丢弃应保留的值。

您可以修改谓词，让它记录返回 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 3

您误解了 std::remove_if 的工作原理。 to-be-removed 值不一定移到末尾。参见：

Removing is done by shifting (by means of move assignment) the elements in the range in such a way that the elements that are not to be removed appear in the beginning of the range. 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 的计数和删除的值可能是错误的。其他剩余值不应留在数组的末尾部分，因为没有完成任何副本。

请注意，这些值并非未指定，因为您无法知道它们。它们正是移动分配的结果，可能会使值处于未指定状态。如果它指定了 moved-from 变量的状态（如 std::unique_ptr 那样），那么它们将是已知的。例如。如果 move==swap 则仅排列范围。

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

Is it safe to traverse a container during std::remove_if execution?

c++

algorithm

stdvector