Is it safe for the input iterator and output iterator in std::transform to be from the same container?

Question

In this post one of the answers recommends changing a std::string case this way:

std::string str = "Hello World";
std::transform(str.begin(), str.end(),str.begin(), ::toupper);

I've used it and it works so far in Visual Studio 2010. But is it guaranteed by the standard to always work? My concern is that I can imagine the possibility of implementations where writing to the output iterator (the third argument) could invalidate the input iterators (arguments one and two).

So, in summary, is the above method safe and portable?

The usage of the iterators is correct - but not the usage of `::toupper`. — nosid, Oct 05 '13 at 17:26
@nosid: I saw in the comments of the post I got the sample from that `::toupper` could be a macro. I will have to address that. — John Fitzpatrick, Oct 05 '13 at 17:39
It was trying to say: If you replace `toupper` with some function `char foobar(char)`, then your question can be directly answered. However, there are a lot of problems regarding `toupper`. Look for `unsigned char` in http://stackoverflow.com/questions/735204/convert-a-string-in-c-to-upper-case — nosid, Oct 05 '13 at 18:09

score 12 · Accepted Answer · edited Jul 03 '16 at 23:58

Yes, this is guaranteed to be safe (as long as operation itself doesn't modify the elements or invalidate iterators).
From chapter [alg.transform] from draft n3337:

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);

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)].

[...]

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

P0W · Answer 2 · 2013-10-05T19:13:41.970

3

If you look into the first possible implementation of std::transform

template<class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first1, InputIt last1, OutputIt d_first, 
                   UnaryOperation unary_op)
{
    while (first1 != last1) {
        *d_first++ = unary_op(*first1++);
    }
    return d_first;
}

It may appear that its not "safe".

However, with std::transform(str.begin(), str.end(),str.begin(), ::toupper);

d_first and first1 point to the same place, but they are not the same iterator !

There isn't any problem with incrementing both those iterators in a single statement.

Another implementation is some what like this (from MingW header file), which is equivalent, but looks bit cleaner

template<class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first1, InputIt last1, OutputIt d_first, 
                   UnaryOperation unary_op)
{

  for (; first1 != last1; ++first1, ++d_first)
    *d_first = unary_op(*first1);

    return d_first;
}

Edited thanks to John Bartholomew

edited Oct 05 '13 at 19:13

answered Oct 05 '13 at 17:40

P0W

46,614
9
72
119

Those two implementations look equivalent to me. Could you explain the operational difference between them? – John Bartholomew Oct 05 '13 at 17:58
I think it's undefined, but the first implementation doesn't do that -- it is incrementing two different variables in one line, not incrementing the same variable twice. – John Bartholomew Oct 05 '13 at 18:17
3

Only if the iterators are passed in as references, which they are not. – John Bartholomew Oct 05 '13 at 18:19
In fact they would also have to be returned as non-const references from `str.begin()` and `str.end()`, which is also not the case. – John Bartholomew Oct 05 '13 at 18:22
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/38669/discussion-between-john-bartholomew-and-p0w) – John Bartholomew Oct 05 '13 at 18:45

score 2 · Answer 3 · answered Oct 05 '13 at 17:44

2

Yes, you can use the input iterator as the output iterator also, on a modifying algorithm it just means the modification will be done inline (on the source container) rather than on some other destination container.

answered Oct 05 '13 at 17:44

Duncan Smith

530
2
10

Is it safe for the input iterator and output iterator in std::transform to be from the same container?

3 Answers3

Linked