for( MessageItr itr = message.begin(); itr != message.end(); ++itr)
{
itr->time -= ElapsedTime;
if( itr->time < 0.0 )
{
//std::cout << "Erasing" << std::endl;
itr = message.erase( itr );
}
}
Works for list not for deque/vector
Author
Well I was debuggin' one day (or maybe late at night) and I happened upon a bug that warse crashing me program.
I was using a deque for a change, not too familiar with it. I would iterate over the elements and erase some of them, and it would crash.
I changed it to a std::list and it worked. Changed to a vector and it failed. Here is the code.
Maybe you can help me explain this phenomenon.
Quote:Original post by Nitage
When you erase from a vector or deque, the iterators to that vector/deque become invalid.
Isn't that the point of erase returning a new iterator?
This leads directly to the problem: erase returns a new iterator. The iterator is the element *after* the one you just deleted. You then end your loop, and that iterator is automatically incremented. If you have to erase the last element, message.erase(i) returns message.end(), which you then proceed to increment.
#include <iostream>#include <vector>using namespace std;int main(){ vector<int> v; for(int i = 0; i < 10; i++) v.push_back(i); vector<int>::iterator i = v.begin() + 5; cout << "Before erase: " << *i << endl; i = v.erase(i); cout << "After erase: " << *i << endl; i += 3; cout << "Last element: " << *i << endl; i = v.erase(i); cout << ((i == v.end()) ? "We're at the end" : "We're not at the end")<< endl; system("PAUSE"); return 0;}CM
yep, in this case you might use sthg. like :
actually, you should make use of ::find() to find and remove the element!
[edit]
Conner McCloud beat me to it ;)
int size = message.size();for( int i = 0; i < size; i++) { itr->time -= ElapsedTime; if( itr->time < 0.0 ) { message.erase( message.begin() + i ); brake; } }actually, you should make use of ::find() to find and remove the element!
[edit]
Conner McCloud beat me to it ;)
Quote:you should make use of ::find() to find and remove the element!
If you want to do this with std library functions:
bool shouldEraseMessage(const StoredType& object){ return object.time < 0.0;}//then to erase//for vector/dequemessage.erase( std::remove_if(message.begin(),message.end(),shouldEraseMessage) , message.end() );//for listmessage.remove_if(shouldEraseMessage);
Author
Thanks for all the help and the nice solutions.
So I guess this means it is safe to increment std::list::back() but not std::vector::back().
I know I am never going to have more than five elements and I don't need random access, so I think I will use a list. But might the code crash on another compiler?
So I guess this means it is safe to increment std::list::back() but not std::vector::back().
I know I am never going to have more than five elements and I don't need random access, so I think I will use a list. But might the code crash on another compiler?
Nah, it's even simpler than that. Just don't increment the iterator unless you don't erase.
Of course, you could (and should, in this example) do this with library functions. First use std::transform to do the subtraction, then apply erase/remove to erase the expired elements.
That's not what it means - it just means that you were able to do it without noticing. Yes, it might crash in a different environment.
for( MessageItr itr = message.begin(); itr != message.end(); ){ itr->time -= ElapsedTime; if( itr->time < 0.0 ) { //std::cout << "Erasing" << std::endl; itr = message.erase( itr ); } else ++itr;}Of course, you could (and should, in this example) do this with library functions. First use std::transform to do the subtraction, then apply erase/remove to erase the expired elements.
Quote:
So I guess this means it is safe to increment std::list::back() but not std::vector::back().
That's not what it means - it just means that you were able to do it without noticing. Yes, it might crash in a different environment.
You shouldn't both grab the return value of erase and increment. Increment only when not erasing. Otherwise, you may very well advance your iterator beyond the end of the container (if you happen to erase the last element, erase returns end() and you increment that... ooops).
For performance, consider combining erase with remove_if. Your code is O(n^2) when it could easily be O(n). That's horribly inefficient.
For performance, consider combining erase with remove_if. Your code is O(n^2) when it could easily be O(n). That's horribly inefficient.
Author
Quote:Original post by RDragon1
Whos code is O(n^2) ?
I was wondering that too.
I thought about it. It is because erase() runs in O(n) for vector/deque
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement