Inserting elements in an empty container using insert function from algorithm not giving expected results

Question

I'm doing some homework, which includes a generic class with a lot of methods and constructors, but I'm only interested in the following constructor where i take the elements from initializer list and put them in my Container:

template <typename T, template <typename...> class Container = std::vector>
class Tok{
    Container<T> collection;
    public:
    Tok(std::initializer_list<T> list);
}

We were told we cant use push_back function from algorithm, but only insert elements using insert function from algorithm. Firstly I implemented the constructor like this:

template <typename T, template <typename...> class Container>
Tok<T,Container>::Tok(std::initializer_list<T> list){
auto it2=collection.end();
    for(auto it1=list.begin(); it1!=list.end(); it1++) {
        {collection.insert(it2,*it1); it2++;}
    }
}

But it didn't work, the program was crashing and throwing a memory error. Then I changed it a bit and got it to work using the next implementation:

template <typename T, template <typename...> class Container>
Tok<T,Container>::Tok(std::initializer_list<T> list){
    for(auto it=list.begin(); it!=list.end(); it++) 
        collection.insert(collection.end(),*it);
}

Now my question is why doesn't the first one work, and what is the difference between these two?(I get the same result using begin instead of end)

score 5 · Answer 1 · answered Jun 15 '19 at 17:06

Inserting into a container like std::vector may invalidate iterators.

In your first example, after you've inserted something into collection, it2 isn't valid any more (because the vector might have had to reallocate its storage) but you increment it and use it again for the next iteration. In your second example, it works because you're getting a new end iterator on every iteration.

You can work around the problem in your first example by using insert's return value. It will return a valid iterator to the inserted value, which you can assign to it2. This also works if you want to insert multiple elements into the middle of the container, like so:

auto pos = getInsertPosition();
for(auto &val : source) {
    pos = destination.insert(pos, val);
}

score 3 · Answer 2 · answered Jun 15 '19 at 17:02

In the first case, as you start adding elements, you invalidate the it2 iterator. See it as : the end changed, if you will.

In the second case, at every iteration you query a new end() iterator, so you always get a valid one.

You can find the rules there: Iterator invalidation rules

Inserting elements in an empty container using insert function from algorithm not giving expected results

2 Answers2