Jump to content

  • Log In with Google      Sign In   
  • Create Account

C++ unordered vector erasure


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 Storyyeller   Members   -  Reputation: 212

Like
1Likes
Like

Posted 08 November 2011 - 11:35 PM

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.
I trust exceptions about as far as I can throw them.

Sponsor:

#2 Hodgman   Moderators   -  Reputation: 30384

Like
0Likes
Like

Posted 08 November 2011 - 11:39 PM

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 );


#3 iMalc   Crossbones+   -  Reputation: 2306

Like
0Likes
Like

Posted 09 November 2011 - 12:42 AM

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.
"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#4 SiCrane   Moderators   -  Reputation: 9596

Like
0Likes
Like

Posted 09 November 2011 - 05:52 AM

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

#5 InvalidPointer   Members   -  Reputation: 1433

Like
1Likes
Like

Posted 09 November 2011 - 02:57 PM

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?
clb: At the end of 2012, the positions of jupiter, saturn, mercury, and deimos are aligned so as to cause a denormalized flush-to-zero bug when computing earth's gravitational force, slinging it to the sun.

#6 Hodgman   Moderators   -  Reputation: 30384

Like
0Likes
Like

Posted 09 November 2011 - 06:19 PM

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

Not a dumb question Posted Image I wrote that code off the top of my head and apparently had forgotten about pop_back; using it would indeed be clearer and more succinct.

#7 latent   Members   -  Reputation: 139

Like
0Likes
Like

Posted 09 November 2011 - 07:09 PM

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




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS