Jump to content

  • Log In with Google      Sign In   
  • Create Account

#ActualServant of the Lord

Posted 28 January 2013 - 01:33 PM

Moving every element down costs you one copy (or one 'move-semantics' move if you are using C++11) for every element above the deleted element, but is necessary if you are preserving the relative order of the elements.

If the relative order of the elements in the array doesn't matter:

You could swap (std::swap()) the element you are deleting and the last element in the array. (Good: Three* copies or three moves (if C++11))
Or, since you're discarding the deleted element anyway, you could just copy (std::copy()) the last element over the deleted element. (Better: One copy)
Or, since you aren't saving the previous usage of the last element and only want one copy of it, you could just use move-semantics (C++11) to move (std::move()) the last element over the deleted element. (Best: One move)

*temp = A, A = B, B = temp

Normally I wouldn't bother mentioning the costs of each option (pre-optimization is generally considered a bad idea), but for the sake of understanding the differences between the options I thought it relevant to the discussion.

This same information applies also to std::vector, since std::vector suffers from alot of the same limitations of a regular array (being held in a single continuous block of memory for faster reads and writes). These limitations don't apply to std::list though, since an std::list is optimized for insertions, movements, and deletions.

#1Servant of the Lord

Posted 28 January 2013 - 01:26 PM

Moving every element down costs you one copy (or one 'move-semantics' move if you are using C++11) for every element above the deleted element, but is necessary if you are preserving the relative order of the elements.

 

If the relative order of the elements in the array doesn't matter:

 

You could swap (std::swap()) the element you are deleting and the last element in the array. (Good: Three* copies or three moves (if C++11))

Or, since you're discarding the deleted element anyway, you could just copy (std::copy()) the last element over the deleted element. (Better: One copy)

Or since you aren't saving the previous usage of the last element and only want one copy of it, you could just use move-semantics (C++11) to move (std::move()) the last element over the deleted element. (Best: One move)

 

*temp = A, A = B, B = temp


PARTNERS