Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is deleting an element in the middle of a std::vector still expensive with movable types?

It is generally thought of deleting an element in the middle of a std::vector to be costly, as it needs to copy every element after it down to fill the hole.

With C++11, std::vector will instead move all the elements down, which should be very fast (if only in relation to the copy), atleast I think so. It will still be linear in time, sure, but in general it should be faster than the old version.

Will this be true? Do I not have to worry about deleting some object in the middle anymore?

like image 457
Xeo Avatar asked Jul 02 '11 13:07

Xeo


People also ask

Does deleting a vector delete its contents?

Yes, erase destroys the element.

Can we delete element from vector?

Vectors are same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container. clear() function is used to remove all the elements of the vector container, thus making it size 0. 1.

How do you remove a specific element from a vector in C++?

The erase() function can remove an element from the beginning, within, or end of the vector. In order to remove all the elements from the vector, using erase(), the erase() function has to be repeated the number of times there are elements, beginning from the first element.


1 Answers

It depends on what's in the vector. If it's a POD or pointer I can't imagine that it would make any difference. If it's class instances that are heavy to copy, but can be moved very fast I'd expect a speedup with C++0x.

However, I think that if deleting elements from the middle of std::vectors is a bottleneck in your code, C++0x is probably not the right fix. Consider datastructures that handles such cases better instead, or std::iter_swap plus std::vector::pop_back if the order of the elements doesn't matter.

like image 182
larsmoa Avatar answered Oct 14 '22 21:10

larsmoa