6

I just realize the standard doesn't guarantee the order of applying function callback in std::transform. And it doesn't allow the callback function or functor have side effect. But at the same time std::for_each actually guarantee the order.

One guess is the transform can using high performance algorithm which doesn't guarantee order, But O(N) is the best algorithm already.

So why the standard doesn't make the transform have the behavior as for_each from the view of apply callback function order? The user will benefit form this guarantee.

Improve this question
3
  • 4
    O(N) doesn't tell you anything about the actual performance, i.e. it neglects constant factors. Commented Jun 28, 2013 at 3:28
  • 2
    the standard does guarantee sequential ordering of operation. see new answer below. Commented Oct 23, 2015 at 15:46
  • Note that this question only concerns the execution order of the callback functors of std::transform() (and nowadays also std::ranges::transform()); NOT the order of the processed elements! The C++ standard guarantees that the order of the result elements matches the order of the input elements, since transform is defined as a 1:1 projection. The question text clarifies this. However, the question title, "std::transform does not guarantee the order," might mislead you into thinking that the order of the result elements could change in transform. At least, I went wrong here. Commented Aug 7 at 16:14

3 Answers 3

Reset to default
5

This non-restrictive definition allows for parallel computing. An implementation may choose to apply transform function using several threads. See also related question: STL algorithms and concurrent programming

Think of it as a semantic difference in algorithms (that is, that represents programmer's intent rather than being just another tool). With for_each you state that you need a sequential scan. With transform you state that you only need to aply a function to every item in the container, but you don't care how it will be done.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks, that exactly answer my question
I'm not sure, if this was different in c++11, but according to the last working draft for c++14, there is no requirement on op, that would allow std::transform to be executed in parallel.
this answer is incorrect. The specification of the InputIterator concept implicitly disallows a concurrent implementation.
@Richard I think that, at least for the c++20 standard and older, there is nothing that explicitly prohibits parallel execution of the transform algorithm. Although I respect your answer as being practical and very informative, taking into account the iterators requirements. But as soon as someone invents an parallel transform algorithm respecting all iterator requirements, your answer will be wrong.
4

Quoting directly from the standard (copied at end):

You will see from the template declaration of std::transform<> that the input iterator parameters must conform to the concept of an InputIterator.

An InputIterator is one of the most restrictive iterator concepts in c++. It does not support any kind of random access. It is only able to advance.

Therefore any implementation of std::transform that requires the iterator to do anything other than be dereferenced or advance is ill-formed. Remember that by specifying InputIterator, the standard is explicitly allowing the use of a std::istream_iterator (for example) and the implementation of std::transform is required to respect the restrictions therein. It must be written only in terms of the methods available on the InputIterator concept.

Therefore, by implication, the implementation of this function must access elements sequentially (and therefore transform values sequentially) since to not do so would break the contract implicit in the interface.

Therefore the standard does (implicitly and quietly) guarantee that std::transform initialise its elements sequentially. It would be impossible to write a well-formed implementation of std::transform that did not.

25.3.4 Transform [alg.transform]

template<class InputIterator, class OutputIterator, class UnaryOperation> OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op);

1 Effects: Assigns through every iterator i in the range [result,result + (last1 - first1)) a new corresponding value equal to op(*(first1 + (i - result)) or binary_op(*(first1 + (i - result)), *(first2 + (i - result))).

2 Requires: op and binary_op shall not invalidate iterators or subranges, or modify elements in the ranges [first1,last1], [first2,first2 + (last1 - first1)], and [result,result + (last1 - first1)].

3 Returns: result + (last1 - first1).

4 Complexity: Exactly last1 - first1 applications of op or binary_op.

5 Remarks: result may be equal to first in case of unary transform, or to first1 or first2 in case of binary transform.

Improve this answer

7 Comments

Maybe I am being naive, but couldn't the implementation iterate through the values, put them in a vector or some other structure that did have random access, and then process them in parallel or reverse or something?
The implementation is free to detect stronger iterator strengths and apply a different (possibly out-of-order) algorithm.
As the wording stands, one could argue that such an implementation conforms to the standard. I asked a friend of mine who contributes to the c++ standard. His view was that the ambiguity in the wording is an error, and the intent is that the transform function is applied linearly. Whether that's the view of the entire committee I cannot say.
@clcto Not possible. Among other things, it incurs lots of copies, and the type need not be copyable, and there's no reliable way for the implementation to detect whether it is copyable. (is_copy_constructible won't work, because it can't detect errors outside the immediate context.)
Sounds to me like this question needs to be addressed by the committee. And how to use transform if f depends on interation count. std::for_each works, but requires capture of the OutputIt, which is ugly.
|
3

Despite some earlier answers, I think it is possible to implement std::transform in a parallel way. For instance like this:

1) Fetch all input sequentially.

2) Iterate over OutputIterator, initialising dummy objects and keep a reference to each output.

3) Distribute the input with the corresponding output iterator to different threads, each doing the transformation independently.

Like this, the iterators are only incremented as allowed.

As pointed out by clcto, another implementation could do step 1) first, then create a vector for all output elements, then compute all of these in parallel using the given function argument and then write them sequentially into the output.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.