469,950 Members | 2,369 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,950 developers. It's quick & easy.

std::vector removing a random element

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?

Oct 15 '05 #1
2 4362
"vsgdp" <sp**@void.com> wrote in message
news:tA%3f.2513$i%.1327@fed1read07
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.
--
John Carson

Oct 15 '05 #2

vsgdp wrote:
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.

Oct 15 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

1 post views Thread by Tino | last post: by
18 posts views Thread by Janina Kramer | last post: by
11 posts views Thread by Steve | last post: by
2 posts views Thread by Morten Aune Lyrstad | last post: by
17 posts views Thread by Michael Hopkins | last post: by
8 posts views Thread by Ross A. Finlayson | last post: by
82 posts views Thread by Peter Olcott | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.