Title
std::erase_if overloads for non-associative containers should move (and not copy) their predicate object
Status
new
Section
[string.erasure][deque.erasure] [forward.list.erasure][list.erasure][vector.erasure]
Submitter
Giuseppe D'Angelo

Created on 2022-12-04.00:00:00 last changed 3 weeks ago

Messages

Date: 2023-01-06.14:40:19

Proposed resolution:

This wording is relative to N4917.

  1. Modify [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 [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 [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 [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 [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;
    
Date: 2023-01-15.00:00:00

[ 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.

Date: 2022-12-04.00:00:00

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 [string.erasure], [vector.erasure], [list.erasure], [forward.list.erasure], and [deque.erasure]).

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

History
Date User Action Args
2023-01-06 14:40:19adminsetmessages: + msg13172
2022-12-10 12:06:23adminsetmessages: + msg13148
2022-12-04 00:00:00admincreate