deque erase questions
Hi. I have a few questions about std::deque.erase()
1.) when I erase one element in the middle of array how do I acces the elements after that element. Should I use the same indexes, or decrease the indexes by one?
2.) when I erase an element from the array (or decrese the size), is the memory deallocated (freed) automatically.
3.) what happens if I try to erase an element that does not exist ( index<0 or index>=size )? nothing or badthing
I am using the deque to create an array of a class and try to erase elements as follows with which I have problems. I think I am trying to erase with wrong indexes.
arrElement.erase(arrElement.begin()+ElementToDelete[i]-k);
ElementToDelete[i]: index of element to be deleted
k: number of deleted before - 1
Can anyone help please?
[842 byte] By [
candidate] at [2007-11-18 17:44:59]
# 1 Re: deque erase questions
1) You can obtain the next valid iterator from the deque<>::erase() function. e.g. MyIterator i = arrElement.erase(arrElement.begin()+ElementToDelete[i]-k);
2) That depends on the kind of element you are storing. If it is an instance (not pointer to an instance), the instance will be destroyed and its memory deallocated. If it is a pointer, you will have to delete the pointer explicitly.
3) The MSDN only mentioned that erase() never throws an exception. I guess the behavior should be vendor dependent.
Kheun at 2007-11-11 1:25:53 >
# 2 Re: deque erase questions
Originally posted by Kheun
1) You can obtain the next valid iterator from the deque<>::erase() function. e.g. MyIterator i = arrElement.erase(arrElement.begin()+ElementToDelete[i]-k);
Thank you for the reply but I could not understand exactly what you mean (I do not know what iterator really is, is that the same as index?). I want to reach the elements using arrElement[index]. Do the indexes of remaining elements change after the erase operation?
# 3 Re: deque erase questions
Originally posted by candidate
Thank you for the reply but I could not understand exactly what you mean (I do not know what iterator really is, is that the same as index?). I want to reach the elements using arrElement[index]. Do the indexes of remaining elements change after the erase operation? You are very right that after erase(), the elements in the container (deque) can be relocated and thus all indexes and iterators for deque is no longer valid. The erase() function returns the next vaid iterator is for the ease of erasing inside a loop.
Kheun at 2007-11-11 1:27:50 >
# 4 Re: deque erase questions
I solved the problem by sorting the indexes of elements to be deleted in the descending order so that it deletes from end to beginning without affecting the indexes of the elements to be deleted. It may not be the fastest solution, but it works. Thank you for your replies.
# 5 Re: deque erase questions
How about something like this, without sorting.
for(MyIterator i = arrElement.begin(); i != arrElement.end(); ++i)
{
if( shouldDelete(i) )
{
i = arrElement.erase(i);
}
}
Kheun at 2007-11-11 1:30:01 >
# 6 Re: deque erase questions
Originally posted by Kheun
How about something like this, without sorting.
[/code]
Your code looks cool. However can I use the same indexes of the elements which I create before starting deleting with your line
if( shouldDelete(i) )
Don't this line change the indexes and my ElementsToDelete array become invalid?
# 7 Re: deque erase questions
Originally posted by candidate
Your code looks cool. However can I use the same indexes of the elements which I create before starting deleting with your line
if( shouldDelete(i) )
Don't this line change the indexes and my ElementsToDelete array become invalid?
Due to the nature of deque (like most container), I afraid not. The shouldDelete() function shouldn't be changing the indexes. It only compares the instance dereferenced by the iterator with a value.
const int threshold = 10;
bool shouldDelete(const MyIterator& i)
{
// Should delete element which value is greater than threshold
return (i->value > threshold);
}
Kheun at 2007-11-11 1:31:56 >
# 8 Re: deque erase questions
Thank you very much for your replies
# 9 Re: deque erase questions
A small correction to Kheun's code to erase an element
from a deque (vector/list/string) while looping :
for(MyIterator i = arrElement.begin(); i != arrElement.end();) // no "++i"
{
if( shouldDelete(i) )
{
i = arrElement.erase(i);
}
else
{
++i;
}
}
# 10 Re: deque erase questions
Thanks for the correction.:blush:
Kheun at 2007-11-11 1:35:06 >
# 11 Re: deque erase questions
Originally posted by Philip Nicoletti
A small correction to Kheun's code to erase an element
from a deque (vector/list/string) while looping :
for(MyIterator i = arrElement.begin(); i != arrElement.end();) // no "++i"
{
if( shouldDelete(i) )
{
i = arrElement.erase(i);
}
else
{
++i;
}
}
Thank you for the replies. However, will this code work faster than a sorting? If I use your code I need to search all elements of ElementsToDelete array for each shouldDelete(i) because my ElementsToDelete array does not store the indexes of elements to delete in an ascending or descending order, they are just random. Please say that I am wrong, so my program works faster.
# 12 Re: deque erase questions
However, will this code work faster than a sorting?
I have not read all of this thread that closely, so maybe
the answer is posted earlier ...
It depends on what the "shouldDelete()" criteria is. If
it is such that sorting will speed it up, then that is
the way to go.
For example, I assume that you add all the elements
at the start into the deque. Then at various times
determine if you need to erase elements ...
If the shouldDelete() criteria is something like : delete
all items between 2 values (where they are sorted on
that specific value). Then sorting will speed it up ...
you can do lower_bound() and upper_bound() binary
searches to find the iterator range to delete and erase
them all at once.
On the other hand, say the deque holds a structure
made up of a number of fields (name,address,amount,etc.)
and you sort by name. Then deleting all elements that
have the amount field less than a specific value will require
a sequential search anyway, so sorting does not gain anything
(and you waster time doing the sort)
