std::forward_list::remove_if谓词的要求

Question

考虑以下代码：

struct T
{
bool status;
UsefulData data;
};

std::forward_list<T> lst;

lst.remove_if([](T &x) -> bool { return x.status= !x.status; });

比如一次性切换状态并删除不活跃元素。

根据cppreference的说法，上述代码似乎是未定义行为（强调我的）：

template< class UnaryPredicate >
void remove_if( UnaryPredicate p );

p - unary predicate which returns true if the element should be removed. The signature of the predicate function should be equivalent to the following:

bool pred(const Type &a);

The signature does not need to have const &, but the function must not modify the objects passed to it. The type Type must be such that an object of type forward_list<T,Allocator>::const_iterator can be dereferenced and then implicitly converted to Type.

然而，当前的工作草案似乎不那么严格（N4659 [forwardlist.ops]）：

void remove(const T& value)
template <class Predicate> void remove_if(Predicate pred);

Effects:

Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value (for remove()), pred(*i) is true (for remove_if()). Invalidates only the iterators and references to the erased elements.

Throws:

Nothing unless an exception is thrown by the equality comparison or the predicate.

Remarks:

Stable (20.5.5.7).

Complexity:

Exactly distance(begin(), end()) applications of the corresponding predicate.

标准的其他部分是否对谓词有额外限制？

我已在多个编译器上测试了上面的代码，它可以编译并似乎按预期工作。我真的需要两次遍历列表吗？

- metalfox

---

我们几乎可以确定是从 [algorithms.requirements]/6 导入了该要求。 - T.C.

尽管这样做很不礼貌，但由于forward_list的迭代器是单向的，我无法想象在谓词中修改对象会成为问题的合理实现。 - Richard Hodges

确实有些棘手。我强烈怀疑它们是有意的，但措辞可能不够明确。 - T.C.

当我有时间的时候，我可能会为此提交一个LWG问题以获得澄清。虽然remove_if并不特别棘手，但允许Compare修改list::sort元素肯定是一个非常糟糕的想法，而且这种非修改要求仅在[alg.sorting]中找到。 - T.C.

现在LWG 2998。 - T.C.

Answer 1

鉴于您问题下的评论，我的看法是：

• forward_list::remove_if不是算法，因此不属于[algorithms.requirements]规则。

• [forwardlist.ops]对谓词的要求没有限制。

• forward_list::remove_if需要在范围内的每个项上应用谓词一次。

因此，在这种情况下修改谓词中的对象是严格合法的，尽管有些反社会。

编辑：

根据T.C.后来的答案，这样做很快就不合法了... https://dev59.com/raPia4cB1Zd3GeqPvDiC#45052149

- Richard Hodges

Answer 2

委员会的图书馆工作组刚刚将LWG issue 2998移至“就绪”状态，基本上确认了该委员会在此处的意图是适用于类似列表操作的28条款（算法条款）中的相关要求。这包括要求Predicate不应用任何非常量函数。

一旦问题解决方案被采纳（这应该会在下次委员会会议上进行），OP中的代码将正式具有未定义行为。尽管如此，除了故意敌对的实现外，它通常应该可以正常工作。如果需要保证具有良好定义行为的实现，则使用迭代器和erase_after手动编写一个并不太困难。

- T.C.