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]

Re: std::vector removing a random element

"vsgdp" <spam@void.co m> wrote in message
news:tA%3f.2513 $i%.1327@fed1re ad07[color=blue]
> From what I learned, if you want to do random element insertions and
> deletions you should use a list.[/color]

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.
[color=blue]
> 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?[/color]

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.
[color=blue]
> Does erase do this internally? Or does erase do the
> element shift to fill in the gap?[/color]

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


--
John Carson

[Alipha]

Re: std::vector removing a random element


vsgdp wrote:[color=blue]
> 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?[/color]

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.