C++: How come random deletion from a std::vector is faster than a std::list?

Question

How come that random deletion from a std::vector is faster than a std::list? What I'm doing to speed it up is swapping the random element with the last and then deleting the last. I would have thought that the list would be faster since random deletion is what it was built for.

for(int i = 500; i < 600; i++){
    swap(vector1[i], vector1[vector1.size()-1]);
    vector1.pop_back();
}

for(int i = 0; i < 100; i++){
        list1.pop_front();
}

Results (in seconds):
Vec swap delete: 0.00000909461232367903
List normal delete: 0.00011785102105932310

Answer 1

What you're doing is not random deletion though. You're deleting from the end, which is what vectors are built for (among other things).

And when swapping, you're doing a single random indexing operation, which is also what vectors are good at.

Answer 2

That's not random. Try vector1.erase(vector.begin() + rand() % vector.size()); instead.

Answer 3

The list erase will cause to delete the erased list element, this will invoke a call to the delete operator. The vector erase just causes a swap and then a integer decrement - this is a lot faster.

Answer 4

Actually if you want further speed-ups you should index elements in the vector via iterators. They are known to have better performance for some architectures.

Answer 5

The difference between std::list and std::vector is not merely down to performance. They also have different iterator invalidation semantics. If you erase an item from a std::list, all iterators pointing to other items in the list remain valid. Not so with std::vector, where erasing an item invalidates all iterators pointing after that item. (In some implementations, they may still serve as valid iterators, but according to the standard they are now unusable, and a checking implementation ought to assert if you try to use them.)

So your choice of container is also to do with what semantics you require.