Public Group

C++ unordered vector erasure

This topic is 2904 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

For a standard vector, random access erasures are linear time, due to shifting all the elements. However, sometimes you don't care about ordering, so you instead want to do a constant time erasure by swapping with the final element and then removing it. Is there any standard implementation of this? It seems like a common task, but I couldn't find anything by googling.

Share on other sites
Not sure if there's a standard algorithm for it, but it's only two lines of code:std::swap( container.back(), *iterator ); container.resize( container.size()-1 );

Share on other sites
It may be common enough, but it's still only a two line task. AFAIK everyone just writes the two lines, possibly putting them into their own function.

Share on other sites
In bulk erasures you can use the remove-erase idiom with partition in place of remove.

Share on other sites

Not sure if there's a standard algorithm for it, but it's only two lines of code:std::swap( container.back(), *iterator ); container.resize( container.size()-1 );

Dumb question, but is there any reason why you aren't pop_back()-ing in the example?

Share on other sites
Dumb question, but is there any reason why you aren't pop_back()-ing in the example?
Not a dumb question I wrote that code off the top of my head and apparently had forgotten about [font="'Courier New"]pop_back[/font]; using it would indeed be clearer and more succinct.

Share on other sites
I've thought about asking this question numerous times, glad I'm not alone in wondering what other folks are doing in this case ;)

• Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 12
• 9
• 11
• 15