3837. std::erase_if overloads for non-associative containers should move (and not copy) their predicate object

Section: 27.4.4.5 [string.erasure], 23.3.5.5 [deque.erasure], 23.3.7.7 [forward.list.erasure], 23.3.9.6 [list.erasure], 23.3.11.6 [vector.erasure] Status: New Submitter: Giuseppe D'Angelo Opened: 2022-12-04 Last modified: 2023-01-06

Priority: 3

View all issues with New status.

Discussion:

Consistent uniform erasure added several overloads of std::erase_if. All these overloads have fully specified effects, and are either implemented through the erase/remove_if idiom (for string, vector and deque), through calls to the container's own remove_if non-static member function (for list and forward_list), or through a hand-rolled loop (for the associative containers — map, set, and their unordered and multi variants).

For the overloads that deal with non-associative containers the predicate passed to std::erase_if is always copied into the inner call to std::remove_if or the container's remove_if (see 27.4.4.5 [string.erasure], 23.3.11.6 [vector.erasure], 23.3.9.6 [list.erasure], 23.3.7.7 [forward.list.erasure], and 23.3.5.5 [deque.erasure]).

Now, algorithms are generally allowed to take as many copies of predicates as they want — this is 26.2 [algorithms.requirements]/9, but cf. LWG 3049. However it still feels strange/sloppy that a copy here is mandated by the Standard. An implementation that would otherwise make no copies of a predicate in an algorithm must make a copy in the erase_if overloads.

The copy of the predicate could be instead replaced by a move without any change in functionality; after being passed to the underlying algorithm, the predicate object is never used again by erase_if. I am therefore proposing to add a std::move call for the predicate object.

One could argue that erase_if should be re-specified so that it is not necessarily implemented in terms of underlying calls to other facilities, and could therefore even remove the need of a move on a high-quality implementation. This is a design change, and so I consider it out of scope for a library issue.

Of course, moving instead of copying is a detectable change, and "pathological" predicate types that are copyable but have disabled moves will get broken, but I don't think those deserve to be supported.

[2023-01-06; Reflector poll]

Set priority to 3 after reflector poll.

"An alternative resolution would be to wrap the predicate in reference_wrapper."

"I'd prefer blanket wording that says the actual number of copies and/or moves is unspecified when the wording depicts a copy of a function object."

Related to LWG 3049.

Proposed resolution:

This wording is relative to N4917.

1. Modify 27.4.4.5 [string.erasure] as indicated:

   template<class charT, class traits, class Allocator, class Predicate>
     constexpr typename basic_string<charT, traits, Allocator>::size_type
       erase_if(basic_string<charT, traits, Allocator>& c, Predicate pred);
   

   -2- Effects: Equivalent to:

   auto it = remove_if(c.begin(), c.end(), std::move(pred));
   auto r = distance(it, c.end());
   c.erase(it, c.end());
   return r;
   

2. Modify 23.3.5.5 [deque.erasure] as indicated:

   template<class T, class Allocator, class Predicate>
     typename deque<T, Allocator>::size_type
       erase_if(deque<T, Allocator>& c, Predicate pred);
   

   -2- Effects: Equivalent to:

   auto it = remove_if(c.begin(), c.end(), std::move(pred));
   auto r = distance(it, c.end());
   c.erase(it, c.end());
   return r;
   

3. Modify 23.3.7.7 [forward.list.erasure] as indicated:

   template<class T, class Allocator, class Predicate>
     typename forward_list<T, Allocator>::size_type
       erase_if(forward_list<T, Allocator>& c, Predicate pred);
   

   -2- Effects: Equivalent to: return c.remove_if(std::move(pred));

4. Modify 23.3.9.6 [list.erasure] as indicated:

   template<class T, class Allocator, class Predicate>
     typename list<T, Allocator>::size_type
       erase_if(list<T, Allocator>& c, Predicate pred);
   

   -2- Effects: Equivalent to: return c.remove_if(std::move(pred));

5. Modify 23.3.11.6 [vector.erasure] as indicated:

   template<class T, class Allocator, class Predicate>
     constexpr typename vector<T, Allocator>::size_type
       erase_if(vector<T, Allocator>& c, Predicate pred);
   

   -2- Effects: Equivalent to:

   auto it = remove_if(c.begin(), c.end(), std::move(pred));
   auto r = distance(it, c.end());
   c.erase(it, c.end());
   return r;