Jump to content
  • Advertisement
Sign in to follow this  
Tispe

Efficient way to erase an element from std::vector

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi

 

I am using a "std::vector<std::pair<stuff1, stuff2>> myvec" that holds temporary data. A random element in the vector may be erased at any time. I don't want to use the std::vector::erase method as it will shuffle all elements which degrades performance.

 

What I want to do instead is to take the element to be erased and set it equal to the back() element, then pop_back(). This won't shuffle the elements down as the erase() method does (I think).

 

Now, will the std::pair class assign operator mess with me when I do this or is this code good?

void EfficientEraseElement(std::vector<std::pair<stuff1, stuff2>> &myvec, int i)
{
	myvec.at(i) = myvec.back();
	myvec.pop_back();
}

Share this post


Link to post
Share on other sites
Advertisement

AFAIK, std::vector needs to guarantee contiguous storage at all times, so I don't think there's any way to avoid memory moves when you delete an item. Std::list does not have that requirement, and it is designed specifically for random deletions and insertions. However, it does not provide random access (by index).

 

Another thing you could do if you still need to work with std::vector is to mark items as deleted instead of actually deleting them. For basic data types, you could reserve a specific value (like NULL for pointers) as meaning "deleted item". For structures and classes, you probably already use pointers, so NULL is good. If not, you could add a member m_bIsDeleted.

Share this post


Link to post
Share on other sites

Out of curiosity, does anyone know if there is any chance the swap can be optimized to a move when the items don't have destructors?

I guess that could be difficult unless the memory in the vector is actually shrunk..

Not that it should really matter, but for large POD types it seems unnecessary to exchange the memory instead of just copying.

Share this post


Link to post
Share on other sites

If by "items don't have destructors" you mean to say that your items are not pointers to objects, structures or other data, then no, there is not way to avoid a copy/move (actually three - one for the first item being moved to aux, one for the second item being moved into the first, and one for aux being moved to the second item).

 

Also, for 64-bit targets, the compiler will optimize those data moves into SSE instructions, if the data to be moved is 8 bytes or less...

Edited by tonemgub

Share this post


Link to post
Share on other sites

Wouldn't it be enough to test for std::is_trivially_copyable? Requiring the whole more restrictive POD-property seems unnecessary.

Yep. I forgot that C++'s definition of POD is now stupidly restrictive. I usually use "POD" to mean "memcpy-safe", which apparently C++ calls "trivially copyable" now sad.png

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!