Vector vs list/deque, forward insertion.

[Olysold]

Why is it that vectors do not allow forward insertion and list and deque does? Or is it just a case of having different things for different jobs?

[Peter87]

Because inserting an element at the front of a vector can be very slow. It will have to move/copy all the elements one step to make room for the new element to be placed at the first location.

[Olysold]

#include<iostream>
#include<vector>
#include<deque>
#include<list>

using namespace std;

int main()
{
    vector<int> things {1};
    int x;

    auto iter = things.end();

    while (cin >> x)
    {
        things.insert(iter, x);
    }
return 0;
}

I suppose the above code works similarly to push_back? Why is it that running the while loop more than once crashes the program? But for list it works fine?

Edit: If both containers can grow dynamically, it shouldn't be a problem right? Unless when the elements are moved in the vector, it somehow allocated into a memory that doesn't exist? (yes, the whole edit can be thought of as nonsense)

[Peter87]

Vectors store the elements in an array internally. If an element is added and the array is too small to store one more element it will have to allocate a new array and copy all of the elements to the new array. You can get the size of the internal array by calling things.capacity().

Iterators to vector elements can be implemented with a simple pointer, so when reallocation takes the pointers will no longer point to the correct place in memory. The iterators are said to become invalidated, meaning you shouldn't use them.

If reallocation doesn't take place things.insert(iter, x); will still invalidate all iterators to from iter to things.end(), so you shouldn't be using iter afterwards anyhow. It is likely that you will be able to use iter to access the new element if no reallocation took place but to be safe and play by the rules you should not make any such assumptions.

Insert returns an iterator to the newly inserted element so to correct your code you can change line 17 to iter = things.insert(iter, x);. Note that this will only be equivalent to push_back in the first iteration because in the next iterations iter will not be equal to things.end(). If you want to insert at the back it's probably best to do things.insert(things.end(), x); or things.push_back(x);.

Your code worked fine with std::list because std::list::insert does not invalidate any iterators. std::list is implemented as a double linked list so to insert an element it just has to allocate a new node and change a few pointers without affecting any of the other elements.

[Olysold]

Thank you Peter for that complete explanation, much appreciated.