Title
Missing wording allowing algorithms to use copies of function objects as substitutes for their parameters
Status
open
Section
[algorithms.requirements]
Submitter
Jared Hoberock

Created on 2017-12-04.00:00:00 last changed 23 months ago

Messages

Date: 2022-04-25.15:09:07

Proposed resolution:

This wording is relative to N4910.

  1. Modify [algorithms.requirements] as indicated:

    -10- [Note 2: Unless otherwise specified, algorithms that take function objects as arguments canare permitted to copy those function objects freely. When an algorithm's specification requires the invocation of a function object parameter, such a copy may be invoked as a substitute for the original function object parameter. [Note: This implies that copyable user-supplied function objects should not rely on their identity. If object identity is important, a wrapper class that points to a noncopied implementation object such as reference_wrapper<T> ([refwrap]), or some equivalent solution, can be used. — end note]

  2. Modify [alg.foreach] as indicated:

    template<class InputIterator, class Function>
      constexpr Function for_each(InputIterator first, InputIterator last, Function f);
    

    […]

    -2- Effects: Applies the function object f to the result of dereferencing every iterator in the range [first, last), […]

    […]

    template<class ExecutionPolicy, class ForwardIterator, class Function>
      void for_each(ExecutionPolicy&& exec,
                    ForwardIterator first, ForwardIterator last,
                    Function f);
    

    -6- Preconditions: Function meets the Cpp17CopyConstructible requirements.

    -7- Effects: Applies the function object f to the result of dereferencing every iterator in the range [first, last). […]

    […]

    template<class InputIterator, class Size, class Function>
    constexpr InputIterator for_each_n(InputIterator first, Size n, Function f);
    

    […]

    -18- Effects: Applies the function object f to the result of dereferencing every iterator in the range [first, first + n) in order. […]

    […]

    template<class ExecutionPolicy, class ForwardIterator, class Size, class Function>
      ForwardIterator for_each_n(ExecutionPolicy&& exec, ForwardIterator first, Size n,
                                 Function f);
    

    […]

    -22- Preconditions: n >= 0 is true. Function meets the Cpp17CopyConstructible requirements.

    -23- Effects: Applies the function object f to the result of dereferencing every iterator in the range [first, first + n). […]

    […]

Date: 2022-04-15.00:00:00

[ 2022-04-25; Daniel comments ]

Bryce and Jared have unassigned from this issue.

Date: 2022-04-15.00:00:00

[ 2022-04-25; Daniel rebases wording on N4910 ]

The previously refactored note term "can" in [algorithms.requirements] p10 has been reverted to "permitted" to specify a normative implementation freedom.

Date: 2018-03-14.00:00:00

[ 2018-3-14 Wednesday evening issues processing; move to Open ]

We thought that the notes in [alg.foreach]/1 and /11 should be unwrapped as well. Bryce to work with Jared on updated wording.

Previous resolution [SUPERSEDED]:

This wording is relative to N4713.

  1. Modify [algorithms.requirements] as indicated:

    -8- [Note: Unless otherwise specified, algorithms that take function objects as arguments are permitted to copy those function objects freely. When an algorithm's specification requires the invocation of a function object parameter, such a copy may be invoked as a substitute for the original function object parameter. [Note: This implies that copyable user-supplied function objects should not rely on their identity. Programmers for whom object identity is important should consider using a wrapper class that points to a noncopied implementation object such as reference_wrapper<T> ([refwrap]), or some equivalent solution. — end note]

  2. Modify [alg.foreach] as indicated:

    template<class InputIterator, class Function>
      constexpr Function for_each(InputIterator first, InputIterator last, Function f);
    

    […]

    -2- Effects: Applies the function object f to the result of dereferencing every iterator in the range [first, last), […]

    […]

    template<class ExecutionPolicy, class ForwardIterator, class Function>
      void for_each(ExecutionPolicy&& exec,
                    ForwardIterator first, ForwardIterator last,
                    Function f);
    

    -6- Requires: Function shall meet the requirements of CopyConstructible.

    -7- Effects: Applies the function object f to the result of dereferencing every iterator in the range [first, last). […]

    […]

    template<class InputIterator, class Size, class Function>
    constexpr InputIterator for_each_n(InputIterator first, Size n, Function f);
    

    […]

    -13- Effects: Applies the function object f to the result of dereferencing every iterator in the range [first, first + n) in order. […]

    […]

    template<class ExecutionPolicy, class ForwardIterator, class Size, class Function>
      ForwardIterator for_each_n(ExecutionPolicy&& exec, ForwardIterator first, Size n,
                                 Function f);
    

    -16- Requires: Function shall meet the requirements of CopyConstructible.

    […]

    -18- Effects: Applies the function object f to the result of dereferencing every iterator in the range [first, first + n). […]

    […]

Date: 2018-01-29.17:21:16

[ 2018-01; Priority set to 3 after mailing list discussion ]

Date: 2017-12-04.00:00:00

When designing the parallel algorithms library, we intended for parallel algorithms to copy their function objects parameters when it is possible and useful to do so, but there doesn't appear to be any wording to enable that latitude. To the contrary, algorithm specifications refer to their function object parameters by name, implying that a copy of the parameter may not be used as a substitute.

This was noticed when Billy O'Neal observed that parallel generate() did not share parallel for_each() and for_each_n()'s special requirement for a CopyConstructible user-provided function object.

This CopyConstructible Function requirement was added to relax legacy for_each()'s MoveConstructible Function requirement to allow parallel implementations to make copies as necessary. All parallel algorithms need similar permissions, but a strong requirement for CopyConstructible in all algorithms is too restrictive.

What we require is to allow algorithm implementations to use copies of function objects as substitutes for their original parameters, while not requiring that all function object parameters be copyable.

Casey Carter noted that [algorithms.requirements] p8 grants permission to all algorithms to copy their function object parameters. However, this paragraph is not normative and does not indicate how the algorithm is allowed to use such copies. Additionally, it does not specify which algorithm parameters are the ones called out as function objects. For example, [alg.generate] refers to gen as a function object, but [alg.foreach] does not refer to f as a function object. All the other types of callable algorithm parameters (i.e. Predicate, BinaryPredicate, Compare, UnaryOperation, BinaryOperation, BinaryOperation1, and BinaryOperation2) are defined to be function objects in [algorithms.requirements] and [algorithms.parallel.user]. This list intentionally omits Function and Generator by design.

A potential resolution would introduce normative wording to explicitly allow algorithms to use copies of function object parameters as substitutes for their function object parameters, and remove ambiguity in algorithm specifications about which parameters are function objects.

History
Date User Action Args
2022-04-25 15:09:07adminsetmessages: + msg12438
2022-04-25 14:19:42adminsetmessages: + msg12435
2018-03-19 00:12:24adminsetmessages: + msg9763
2018-03-19 00:12:24adminsetstatus: new -> open
2018-01-29 17:21:16adminsetmessages: + msg9663
2017-12-18 21:29:40adminsetmessages: + msg9598
2017-12-04 00:00:00admincreate