Home > Archive > VC STL > August 2005 > STL Vector: Unexpected behavior
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
STL Vector: Unexpected behavior
|
|
|
| Hello all,
I have been experiencing some strange behavior removing elements from
an STL vector; the elements are pointers to some class I have created.
Hypothetical code fragment follows:
typedef std::vector<MyClass*> MyClassVector;
typedef MyClassVector::iterator MyClassIterator;
....
....
....
MyClassVector localVector;
MyClassIterator localIterator;
// put some pointers to MyClass objects in vector (not shown)
....
....
....
/* Now I want to iterate through each object pointer in the vector,
depending upon some fields in the object, I will call some functions */
MyClass* obj_ptr = NULL
for (localIterator = localVector.begin(); localIterator !=
localVector.end(); ++localIterator) {
obj_ptr = *localIterator; // dereference to get element
if(obj_ptr->some_field == true) do_stuff();
else do_different_stuff();
// now remove element from list
localVector.erase(remove(localVector.begin(), localVector.end(),
*localIterator), localVector.end());
} // end of for loop
I have put a single pointer into the vector. During the first iteration
of the for loop, the appropriate object is dereferenced and the
appropriate function called, i.e. do_stuff(). Next the pointer is
successfully removed from the list (I can tell this by accessing the
size() function which noew reads 0).
I would, therefore, expect the loop to execute only once, however, it
executes a second time. This results in an error since there is nothing
in the vector to dereference!
Strangely, if I do not attempt to remove the element using
localVector.erase(remove(localVector.begin(), localVector.end(),
*localIterator), localVector.end()), the loop executes only once as
would be expected.
I guess I could change the for loop to something like:
for (unsigned index = 0; index < localVector.size; ++index)
Whilst that _may_ solve the problem, it won't allow me to _understand_
why the other approach doesn't work.
Any clues?
Thanks
Bob
| |
| Ulrich Eckhardt 2005-08-25, 7:03 pm |
| bob wrote:
> for (localIterator = localVector.begin(); localIterator !=
> localVector.end(); ++localIterator) {
> MyClass* obj_ptr = *localIterator; // dereference to get element
> if(obj_ptr->some_field == true) do_stuff();
> else do_different_stuff();
> // now remove element from list
> localVector.erase(remove(localVector.begin(), localVector.end(),
> *localIterator), localVector.end());
> } // end of for loop
Erasing an element from a container always invalidates the iterator used for
the deletion, i.e. you can't use it afterwards, not even increment it to
the next element. For a vector, you should expect it to invalidate every
iterator of that container. Also, removing elements from the middle of a
vector is a slow operation, you should use list<> instead, then you can use
this simple algorithm:
iterator it = the_list.begin();
while(it!=the_list.end)
{
if(some_condition(*it))
the_list.erase(it++);
else
++it;
}
Other than that, you could move all pointers you want to keep to a new
vector and then swap the former one with it.
> This results in an error since there is nothing
> in the vector to dereference!
Yes, you also omit checking if the pointer is zero in your loop. I'd
consider using boost::shared_ptr<>, btw.
> for (unsigned index = 0; index < localVector.size; ++index)
>
> Whilst that _may_ solve the problem, it won't allow me to _understand_
> why the other approach doesn't work.
No, this also doesn't work, because when you erase an element from the
middle and then increment 'index' you skipped an element.
Uli
| |
|
| Hi Uli,
Thanks for the reply.
>Erasing an element from a container always invalidates the iterator used for
>the deletion, i.e. you can't use it afterwards, not even increment it to
>the next element. For a vector, you should expect it to invalidate every
>iterator of that container.
I have read this before but I dont really understand it :(
>Also, removing elements from the middle of a
>vector is a slow operation, you should use list<> instead, then you can use
>this simple algorithm:
>iterator it = the_list.begin();
>while(it!=the_list.end)
>{
> if(some_condition(*it))
> the_list.erase(it++);
> else
> ++it;
>}
Actually, the obj is always removed; it is not conditional. This also
means that I am removing elements from the top of the vector.
Thanks
| |
| Igor Tandetnik 2005-08-25, 7:03 pm |
| bob <bobtabulous@yahoo.co.uk> wrote:
>
> I have read this before but I dont really understand it :(
It's pretty simple. Vector keeps elements in a contiguous memory buffer.
When adding or removing, it has to move elements around to keep the
buffer contiguous. Now, iterators are essentially pointers into this
buffer. When the underlying buffer is rearranged, you no longer know
what an iterator is pointing at. The safest course of action is to treat
all iterators that existed before the move as garbage, and avoid using
them. This is what the C++ standard mandates.
> Actually, the obj is always removed; it is not conditional. This also
> means that I am removing elements from the top of the vector.
So you are saying that as a result of this operation, you are removing
all elements from the vector. In this case, you don't need to remove as
you go. Run through the loop, call do_stuff() but do not call erase.
After exiting the loop, call localVector.clear() to remove all elements
at once.
--
With best wishes,
Igor Tandetnik
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925
| |
| Stephen Howe 2005-08-25, 7:03 pm |
| > Also, removing elements from the middle of a vector is a slow operation...
A generalisation. It has to weighed up against the fact that list erasing of
nodes, there will be deallocation
of memory which itself can be slow. Used properly, generally vectors beat
all other containers for a small number of items. Depending on both memory
allocation and the time it takes to assign/copy an object - eventually list
and map's big-O behaviour kicks in and they start to shine as containers,
beating vector.
Stephen Howe
| |
| Ken Alverson 2005-08-25, 7:03 pm |
| "bob" <bobtabulous@yahoo.co.uk> wrote in message
news:1124985235.002308.218870@g47g2000cwa.googlegroups.com...
>
>
> Actually, the obj is always removed; it is not conditional. This also
> means that I am removing elements from the top of the vector.
Consider deque<> instead of vector<>. It is highly efficient at adding or
removing from the front or back of the container. Deletions from the middle
are on par with vector<>.
// process and remove elements from the front of a deque
while (!myDeque.empty()) {
if (myDeque.front()->some_field) {
do_stuff();
} else {
do_different_stuff();
}
myDeque.pop_front();
}
Ken
| |
| Ken Alverson 2005-08-25, 7:03 pm |
| "Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
news:u4f68PZqFHA.2816@tk2msftngp13.phx.gbl...
>
> A generalisation. It has to weighed up against the fact that list erasing of
> nodes, there will be deallocation
> of memory which itself can be slow. Used properly, generally vectors beat
> all other containers for a small number of items. Depending on both memory
> allocation and the time it takes to assign/copy an object - eventually list
> and map's big-O behaviour kicks in and they start to shine as containers,
> beating vector.
deques beat vectors in a surprising number of cases. There are specific cases
where vectors really shine, but a lot of the time, deque is the better choice,
even if you don't take advantage of the front insertion/deletion property, in
large part due to the fact you don't have to maintain one large contiguous
chunk of memory, as well as the fact that growing a deque doesn't mean copying
all the elements within.
list, as you indicate, has to allocate/deallocate when creating and destroying
nodes. It really shines when you absolutely have to shuffle things around in
the middle of the list on a regular basis, and when you are working with
heavyweight objects that are expensive to copy.
Ken
| |
| Stephen Howe 2005-08-25, 7:03 pm |
| > deques beat vectors in a surprising number of cases. There are specific
cases
> where vectors really shine, but a lot of the time, deque is the better
choice,
> even if you don't take advantage of the front insertion/deletion property,
in
> large part due to the fact you don't have to maintain one large contiguous
> chunk of memory, as well as the fact that growing a deque doesn't mean
copying
> all the elements within.
Very true. I know that deque is very "OS friendly" as the OS does not have
to come up with large continuous block of memory. It is conceivable that for
a large vector, some OS's might run out of memory where as the equivalent
large deque might manage it as it's block size demands on the OS are less
(even if the total amount of memory requested is larger than vector).
vector's reserve() somewhat compensates.
> list, as you indicate, has to allocate/deallocate when creating and
destroying
> nodes. It really shines when you absolutely have to shuffle things around
in
> the middle of the list on a regular basis, and when you are working with
> heavyweight objects that are expensive to copy.
Very very true as well. All the node containers shine with objects that have
heavy copy/assign.
Think also of list's sort() where nothing is copied around. list is also a
good choice when the exception gurantees are important.
Stephen Howe
| |
| David D 2005-08-26, 3:57 am |
| As erase returns an iterator to the element following the one erased one might use
localIterator = localVector.erase(.....
But you must remove the incrementing of the iterator from the for statement or you skip every second element.
/David
Ulrich Eckhardt wrote:
> bob wrote:
>
>
>
> Erasing an element from a container always invalidates the iterator used for
> the deletion, i.e. you can't use it afterwards, not even increment it to
> the next element. For a vector, you should expect it to invalidate every
> iterator of that container. Also, removing elements from the middle of a
> vector is a slow operation, you should use list<> instead, then you can use
> this simple algorithm:
>
> iterator it = the_list.begin();
> while(it!=the_list.end)
> {
> if(some_condition(*it))
> the_list.erase(it++);
> else
> ++it;
> }
>
> Other than that, you could move all pointers you want to keep to a new
> vector and then swap the former one with it.
>
>
>
>
> Yes, you also omit checking if the pointer is zero in your loop. I'd
> consider using boost::shared_ptr<>, btw.
>
>
>
>
> No, this also doesn't work, because when you erase an element from the
> middle and then increment 'index' you skipped an element.
>
> Uli
>
| |
| Ulrich Eckhardt 2005-08-26, 7:58 am |
| bob wrote:
> Actually, the obj is always removed; it is not conditional. This also
> means that I am removing elements from the top of the vector.
Apart from calling clear() afterwards, you can also use this way:
for( Container c=GetContainer();
!c.empty();
c.pop_front())
{
do_something_with(c.front());
}
This works with every container except vector<>, as that one has no
pop_front() - you could use pop_back()/back() there instead. It has the
different behaviour that the elements are handled and then removed, just in
case that is important to you.
Uli
|
|
|
|
|