std::vector removing a random element

[vsgdp]

From what I learned, if you want to do random element insertions and
deletions you should use a list. But, with std::vector, if the order of the
elements does not matter, couldn't you efficiently remove a random element
by swapping it with the last element and then just using pop_back? Does
erase do this internally? Or does erase do the element shift to fill in the
gap?

 

[John Carson]

From what I learned, if you want to do random element insertions and
deletions you should use a list.

A list inserts/deletes equally well in the middle of a list as at either end
whereas a vector inserts/deletes more quickly at the end than it does in the
middle. This doesn't actually tell you anything about the relative
efficiency of lists and vectors for middle operations; it only compares list
operations to other list operations and vector operations to other vector
operations. If relative efficiency of lists and vectors is important, you
should time them for the actual container sizes and operations that are
relevant to you.

But, with std::vector, if the order
of the elements does not matter, couldn't you efficiently remove a
random element by swapping it with the last element and then just
using pop_back?

Yes. For large vectors, a swap and pop_back operation would be quicker. Much
of the time, however, preserving the order of elements does matter.

Does erase do this internally? Or does erase do the
element shift to fill in the gap?

erase preserves the order of remaining elements, so it shifts elements.

 

[Alipha]

From what I learned, if you want to do random element insertions and
deletions you should use a list. But, with std::vector, if the order of the
elements does not matter, couldn't you efficiently remove a random element
by swapping it with the last element and then just using pop_back? Does
erase do this internally? Or does erase do the element shift to fill in the
gap?

What operations are you doing with this collection of objects? By
random, do you mean, randomly selected or random access? If you mean
random access, and if the sequence order of the elements does not
matter, it sounds like you should be using a std::set or std::multiset.