Sign in to follow this  
Juliean

proper use of std::vector erase()

Recommended Posts

Hi,

I wanted to know how to properly delete certain items from a vector..? I thought I was doing it correctly:
[code]
vector<vector<FadeElements>::iterator> Temp;
for(vector<FadeElements>::iterator ii = m_FadeElements.begin(); ii!= m_FadeElements.end();++ii)
{
ii->TimeLeft -= dt;
if(ii->TimeLeft <= 0)
{
Temp.push_back(ii);
}
}

for(vector<vector<FadeElements>::iterator>::iterator ii = Temp.begin(); ii != Temp.end();++ii)
{
m_FadeElements.erase(*ii);
}[/code]

I thought storing the iterator in another vector and using this data to erase an item would do, but if I have multiple items that should be deleted within the same frame, I get an error (vector iterator out of range). What is the proper way of doing so? I could think of a solution:
[code]
vector<int> Temp;
int i = 0;
for(vector<FadeElements>::iterator ii = m_FadeElements.begin(); ii!= m_FadeElements.end();++ii)
{
ii->TimeLeft -= dt;
if(ii->TimeLeft <= 0)
{
Temp.push_back(i);
}
i++;
}

int Erased = 0;
for(vector<int>::iterator ii = Temp.begin(); ii != Temp.end();++ii)
{
m_FadeElements.erase(m_FadeElements.begin() + *ii - Erased);
Erased += 1;
}[/code]

However this is giving me the error "vector iterator + offset out of range" on the 3rd element when I have 5 elements (0, 1, 2, 3, 4) to delete, although *ii = 3 and Erased = 3. Do you see any mistakes in my code, or is there another solution?

Share this post


Link to post
Share on other sites
erase() returns an new iterator to the element after the one being erased. Use that iterator instead of stepping to the next element when you erase an item from the vector.
[source]
for(vector<FadeElements>::iterator ii = m_FadeElements.begin(); ii!= m_FadeElements.end(); /* no ++ii here */)
{
ii->TimeLeft -= dt;

if(ii->TimeLeft <= 0) {
ii = FadeElements.erase(ii);
} else {
++ii;
}
}
[/source]
Note that you shall not step the iterator in the for loop's header in this case.

Share this post


Link to post
Share on other sites
Thanks a lot! Beside of it working know, your solution seems a lot faster, too (no additional vector insertions and iterators for each deleted object).

Just an additional question considering vectors, while I'm at it so I don't have to open a new post:

can I optimize a vector iteration loop by doing this:

[code]vector<FadeElements>::iterator end = m_FadeElements.end();
for(vector<FadeElements>::iterator ii = m_FadeElements.begin(); ii != end;++ii)
{

}[/code]

It seems like caching the end element is a good idea to me, as it saves 1 function call and propably a vector element access per iteration, however I wonder if the compiler isn't intelligent enough to do this by himself? And what if I am erasing elements like in my example, is this even valid?

Share this post


Link to post
Share on other sites
In terms of efficiency, using erase() in a loop on a std::vector is O(n[sup]2[/sup]). You may want to instead consider using std::remove_if() or the swap and pop idiom if order doesn't matter.

[quote name='The King2' timestamp='1318685057' post='4872833']
And what if I am erasing elements like in my example, is this even valid?
[/quote]
No, it's not valid if you're erasing in the loop for std::vector.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this