Requirements on std::forward_list::remove_if predicates

Question

Consider this code:

struct T
{
bool status;
UsefulData data;
};

std::forward_list<T> lst;

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

i.e. switching the status and removing inactive elements in one go.

According to cppreference the above code seems to be undefined behavior (emphasis mine):

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.

However, the current working draft seems to be less restrictive (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.

Are there additional restrictions on predicates in other parts of the Standard?

I have tested the above code on a number of compilers and it compiles and seems to work as intended. Do I really need to transverse the list twice?

Answer 1

The committee's Library Working Group has just moved LWG issue 2998 to "Ready" status, essentially confirming that the committee's intent here is that the relevant requirements from Clause 28 (the algorithms clause) apply to the similar list operations. This includes the requirement that the Predicate does not apply any non-constant functions.

Once the issue resolution is adopted (which should happen at the next committee meeting), the code in the OP will formally have undefined behavior. Nonetheless, it should generally work as desired barring an intentionally hostile implementation. If an implementation with guaranteed well-defined behavior is desired, it's not too hard to write one manually with iterators and erase_after.

Answer 2

In light of the comments under your question, my view is that:

• forward_list::remove_if is not an algorithm, and as such does not fall under the rules of [algorithms.requirements].

• [forwardlist.ops] places no restriction on what you may do in the predicate.

• forward_list::remove_if is required to apply the predicate exactly once per item in the range.

Therefore, it's strictly legal to modify the object in the predicate in this case, if somewhat anti-social.

edit:

In the light of T.C.'s later answer, it won't be legal for long... https://stackoverflow.com/a/45052149/2015579