This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

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

Section: 23.4.4.5 [string.erasure], 24.3.8.5 [deque.erasure], 24.3.9.7 [forward.list.erasure], 24.3.10.6 [list.erasure], 24.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 23.4.4.5 [string.erasure], 24.3.11.6 [vector.erasure], 24.3.10.6 [list.erasure], 24.3.9.7 [forward.list.erasure], and 24.3.8.5 [deque.erasure]).

Now, algorithms are generally allowed to take as many copies of predicates as they want — this is 27.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 23.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 24.3.8.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 24.3.9.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 24.3.10.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. 


  5. Modify 24.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;

    

    

    

    6.