(algorithm) transform every element and append to the same container

[Nikko YL]

I have a vector with 3 string elements {"zero", "one", "two"}.
What I'm trying to do is to "repeat" every element and append to the back of the vector.
So the expected resulting vector should contain {"zero", "one", "two", "zerozero", "oneone", "twotwo"}.

When I used back_inserter as the OutputIterator in transform, I got a bad_alloc exception.

vector<string> v{ "zero", "one", "two" };
auto repeat = [](string s) -> string
{
    s += s;
    return s;
};
transform(v.cbegin(), v.cend(), back_inserter(v), repeat);

Therefore, I create a temporary vector to hold the transformed strings.
It works fine.

vector<string> temp;
transform(v.cbegin(), v.cend(), back_inserter(temp), repeat);
for (auto& s : temp)
    v.push_back(move(s));

I think the problem is related to the iterator returned by back_inserter. I have just learnt insert iterator, so I have only a superficial understanding on it.

[keskiverto]

How about v.reserve( 2 * v.size() ); before transform? (A push_back may require realloc, which invalidates iterators.)

[Nikko YL]

Thank you for replying. Your solution works.

Is it the InputIterator get invalidated?
I have tried mimicking the operations transform performs without using InputIterator and it works.

auto it = back_inserter(v);
int i = 0;
int sz = v.size();
while (i != sz)
{
    it = repeat(*(v.cbegin() + i++));
}

Why would the InputIterator get invalidated but it is not the case when it comes to the insert iterator?

I encountered the similar problem when I was taking a look at the example in vector::insert (http://www.cplusplus.com/reference/vector/vector/insert/ ).
On line 15, why is "it" no longer valid? I think "it" is still pointing to 200 on line 15.
How can I know whether an iterator is safe to be used or not?

Since the return type of vector::insert is an iterator that points to the first of the newly inserted elements, can I just write a single line of code in place of lines 13-16 in the example?
it = myvector.insert (it,2,300);

[keskiverto]

If a reallocation happens, all iterators, pointers and references related to the container are invalidated.

Your "mimic" does not use any of those and thus it is ok.

Back_inserter is not a regular iterator. Lets rewrite the mimic:

size_t i = 0;
const size_t sz = v.size();
while ( i < sz ) {
  v.push_back( repeat(*(v.cbegin() + i++)) );
}

Back_inserter knows the vector, but does not point to any element in it.

The transform, however, takes two iterators to the source vector and those will get invalidated by reallocation.

The reserve() makes sure that no reallocation is required during the transform.

On that example the line 11 already uses the return value of insert, and lines 13-16 explain the alternative/danger. However, should you insert in the middle, resetting the iterator would be more difficult.

auto index { std::distance( myvector.begin(), it ) };
myvector.insert (it,2,300);
it = myvector.begin() + index;
// or simply
it = myvector.insert (it,2,300);

[Nikko YL]

So back_inserter is just another way to call push_back?
If it does not point to anything, why name it as an iterator?

[keskiverto]

It behaves like an iterator. Generic algorithms expect iterator-like behaviour.
The transform, for example, does something like:

*result = ...;
++result;

* Dereference operator, that returns a reference to value_type object.
* Increment operator.

back_inserter is a function that creates a back_insert_iterator_object
http://www.cplusplus.com/reference/iterator/back_insert_iterator/

Technically, it is an iterator, but different. Iterator does not need to be a plain pointer in disguise.

A more "fat" iterator type could track its validity. Operations on invalid iterator would then fail gracefully. That requires more memory though, and collaboration with the container. In the example of vector reallocation, the vector should have a list of iterators pointing to it, and signal them all. The standard library emphasizes efficiency and does not have such iterators.

[Nikko YL]

Thank you. I have learnt a lot from your reply.