Why is erase() function so expensive?

Question

Consider a 2d vector vector < vector <int> > Nand lets say its contents are as follows:

1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

So the size of N here is 4 i.e. N.size() = 4

Now, consider the following code :

int i = 0;
while(N != empty()){
N.erase(i);
++i;
}

I calculated the time just for this piece of code alone with various sizes for N and following are the results:

The size of N is 1000 Execution Time: 0.230000s

The size of N is 10000 Execution Time: 22.900000s

The size of N is 20000 Execution Time: 91.760000s

The size of N is 30000 Execution Time: 206.620000s

The size of N is 47895 Execution Time: 526.540000s

My question is why is this function so expensive ? If it is so then conditional erase statements in many programs could take forever just because of this function. It is the same case when I use erase function in std::map too. Is there any alternative for this function. Does other libraries like Boost offer any?

Please do not say I could do N.erase() as a whole because I'm just trying to analyze this function.

Answer 1

Consider what happens when you delete the first element of a vector. The rest of the vector must be "moved" down by one index, which involves copying it. Try erasing from the other end, and see if that makes a difference (I suspect it will...)