Jump to content
  • Advertisement
Sign in to follow this  
crocomire

std::vector efficiency question

This topic is 5451 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

Hello, I have a pointer to a std::vector object that contains myType objects: std::vector<myType>* myVec; Now, I'd like to test each element of this vector for a certain condition. If this condition fails I'd like to remove this element. After each element has been tested I will insert a number of new elements in the vector that is about the same as the removed elements. What is the most efficient way to do this? My current solution: std::vector<myType>* myVec; std::vector<myType>* tempVec; //some other code tempVec->clear(); vector<myType>::iterator i; for (i = myVec->begin(); i != myVec->end(); ++i) { if ( ... ) { tempVec->push_back(*i); } } myVec->clear(); myVec->insert(myVec->begin(), tempVec->begin(), tempVec->end()); //the insert seems rather inefficient [Edited by - crocomire on October 14, 2004 4:27:42 PM]

Share this post


Link to post
Share on other sites
Advertisement
std::vector<myType>::iterator != std::vector<myType*>::iterator, anyways is there a particular reason you wont create the vector of some type on the heap? or was you trying to make a vector of pointers to some type? you can use the STL algorithm remove_if in-conguction with vector::erase to conditionally remove elements.

Share this post


Link to post
Share on other sites
This is less a problem with vector and more a problem of choosing the right tool for the job. I would think you would want to use a list for this and not a vector. A vector is going to be very inefficient for arbitrary inserting and deleting.

Share this post


Link to post
Share on other sites
I recommend not using vector::clear(), instead use vector::resize(0). It is much faster.

I learned this from one of the GDC slides called

Common C++ Performance Mistakes in Games

You can find it on this page
http://www.gdconf.com/archives/2004/index.htm

Very good performance tips in there.

Edit: regarding your original question, something you can try is instead of removing elements from the vector, swap the element you want to remove with the last element in the vector, and then you can pop_back() without suffering the cost of removing from a vector.

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
std::vector<myType>::iterator != std::vector<myType*>::iterator, anyways is there a particular reason you wont create the vector of some type on the heap? or was you trying to make a vector of pointers to some type? you can use the STL algorithm remove_if in-conguction with vector::erase to conditionally remove elements.


Yes, I made an error (corrected now): it should be std::vector<myType>::iterator
Is vector::erase the fastest way to remove an element from an vector?

Share this post


Link to post
Share on other sites
Quote:
Original post by CodeMunkie
This is less a problem with vector and more a problem of choosing the right tool for the job. I would think you would want to use a list for this and not a vector. A vector is going to be very inefficient for arbitrary inserting and deleting.


I use a vector because I also need to sort later on. I think sorting a vector is much faster than sorting a list, or am I wrong?
So I need fast soring and fast arbitrary removing of elements.

Share this post


Link to post
Share on other sites
If you need fast insertion and deletion of elements, then you don't get faster than a list, algorithmically.

For removing if a certain condition is true, check this out:


struct is_odd
{
template<type T>
bool operator()(const T& left) const
{
return left % 2 == 1;
}
};


std::vector<int> intVector;
// Add values to intVector

intVector.erase(
std::remove_if(
intVector.begin(),
intVector.end(),
is_odd()
),
intVector.end()
);





You can find out more about remove_if here. remove doesn't actually remove or destruct elements, rather it just reorders them so that all the elements that meet the condition are grouped at the end.

Share this post


Link to post
Share on other sites
Quote:
Original post by crocomire
I use a vector because I also need to sort later on. I think sorting a vector is much faster than sorting a list, or am I wrong?
So I need fast soring and fast arbitrary removing of elements.


What is your usage pattner more exactly, you could use std::set to have O(log N) insertions and removal problem is you'll take the same (or actually slightly more) performance hit as a list when iterating.

So if you also does a lot of iterating a vector could be the best option anyhow even if you need to resort it.

But for that case I advice you to not use remove but instead swap the last element with whatever element needs to be deleted and then pop_back and when you're done with all removals and insertions just resort it.

Share this post


Link to post
Share on other sites
oh, and if you have pointers in that vector that needs to be deleted don't use remove_if or similar algorithms since that will create memory leaks in that case the correct algorithm is partition .

Share this post


Link to post
Share on other sites
Quote:
Original post by crocomire
I think sorting a vector is much faster than sorting a list, or am I wrong?


it depend on which sort algorithm you use, list has it's own sort method.

Quote:
Original post by crocomire
So I need fast soring and fast arbitrary removing of elements.


list is better than vectors for insertion & deletion in arbitarty places.

The other alternative is to use a container that is always sorted, std::set (as is std::map) is implemented with a red-black tree, there is also an STL extension for red-black tree container type but its not in the c++ standard currently.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!