Have Geek Brain

How is random deletion from std :: vector faster than std :: list?

How is it that accidental deletion from std :: vector is faster than std :: list? What I am doing to speed this up is swapping a random element with the last one and then deleting the last one. I would have thought the list would be faster since accidental deletion is what it was created 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
Normal delete list: 0.00011785102105932310

-1


a source to share


5 answers


However, you are not doing this accidental deletion. You remove from the end, which is for vectors (among other things).



And when replacing, you do one random indexing operation, which is also fine for vectors.

+17


a source


The difference between std::list

and std::vector

doesn't just go down to performance. They also have different iterator invalidation semantics. If you remove an item from std::list

, any iterators that point to other items in the list remain in effect. Not so with std::vector

, where deleting an element invalidates all iterators pointing after that element. (In some implementations, they may still serve as valid iterators, but by the standard they are now unusable and the progress check must be asserted if you try to use them.)



So your choice of container also depends on what kind of semantics you need.

+5


a source


This is no coincidence. Try vector1.erase (vector.begin () + rand ()% vector.size ()); instead of this.

0


a source


The list erase

will lead to the deletion of the deleted list item, this will cause an operator call delete

. Erasing a vector just triggers an exchange and then an integer decrement is much faster.

0


a source


In fact, if you need further speed-ups, you must index the elements in the vector using iterators . They are known to have the best performance for some architectures.

0


a source






More articles:


All Articles