STL vector problems

[Christian Chrismann]

Hi,

I've a runtime problem with STL vectors.
Here is the simplified version of the code:

template <class T> class A {
...
private:
vector<T*> myvector;
typename vector<T*>::itarator mIt;
...
};

template <class T>
T* A<T>::function1()
{
typename vector<T*>::iterator it( mIt );
if ( it != myvector.end() )
return function2();

return NULL;
}

template <class T>
T* A<T>::function2()
{
T *temp = *mIt;

if ( mIt != ( --( myvector.end()) ) )
++mIt;
else // line1
mIt = myvector.end(); // line 2

return temp;
}


When the gcc-compiled program is run, I get the error message:

*** glibc detected *** double free or corruption (fasttop): 0x0819b210 ***

When "line1" and "line2" are removed (the else-part of function2),
the program works fine.

What might be the problem?

And another question:
What happens exactly in line "T *temp = *mIt;" ?
I assume that a new variable of type "pointer to T" is defined and
initialized with the address to an element of type T that is stored in
the STL vector. The class T constructor is never invoked here, right? And
why do I actually need to define the type of the pointer (here pointer to
class T)? I mean, the size of the address is always the same. Or is
it important for type checking?

Regards,
Chris

 

[Howard]

template <class T>
T* A<T>::function2()
{
T *temp = *mIt;

if ( mIt != ( --( myvector.end()) ) )
++mIt;
else // line1
mIt = myvector.end(); // line 2

return temp;
}

Not an aswer to your question, but...

What is that supposed to do? It looks like either case is identical to me.
If you increment the iterator, and it is equal to one before the end()
iterator, then setting it to end() is identical to incrementing it. So why
not just increment it?

-Howard

 

[Volker Lukas]

I've a runtime problem with STL vectors.
Here is the simplified version of the code:

Unfortunately it is simplified too much, I think: You left out the main
function, so that compiling the code will not produce a testcase which
reproduces the problem.

template <class T> class A {
...
private:
vector<T*> myvector;
typename vector<T*>::itarator mIt;
...
};

[One other function definition]

template <class T>
T* A<T>::function2()
{
T *temp = *mIt;

if ( mIt != ( --( myvector.end()) ) )
++mIt;

I can not claim that this is the cause of your problem, but you must not
call function2 if mlt compares equal to myvector.end(). Since the message
you see goes away if the next lines, which set mlt to myvector.end(), are
removed, one could guess that this is eventually the case.

else // line1
mIt = myvector.end(); // line 2

return temp;
}


When the gcc-compiled program is run, I get the error message:
[...]

If you use GCC, you have at least two debugging tools at your hand. One is
the "Mudflap"-Option, and the other one is "Libstdc++ debug mode". You may
want to read in GCCs documentation what these do exactly. (Your GCC must be
sufficiently recent for both)

 

[Christian Chrismann]

Hi,

I've a runtime problem with STL vectors. Here is the simplified version of
the code:

template <class T> class A {
...
private:
vector<T*> myvector;
typename vector<T*>::itarator mIt;
...
};

template <class T>
T* A<T>::function1()
{
typename vector<T*>::iterator it( mIt ); if ( it != myvector.end() )
return function2();

return NULL;
}
}
template <class T>
T* A<T>::function2()
{
T *temp = *mIt;

if ( mIt != ( --( myvector.end()) ) )
++mIt;
else // line1
mIt = myvector.end(); // line 2

return temp;
}
}

When the gcc-compiled program is run, I get the error message:

*** glibc detected *** double free or corruption (fasttop): 0x0819b210 ***

When "line1" and "line2" are removed (the else-part of function2), the
program works fine.

Sorry, I made a mistake. Removing lines "line1" and "line2" will not fix
the problem. However, when instead of returning "temp" NULL is returned in
function2, the glibc message does not show up anymore.
Maybe this helps

 

[Thorsten Kiefer]

Hi, Hi,

When the gcc-compiled program is run, I get the error message:

*** glibc detected *** double free or corruption (fasttop): 0x0819b210 ***

The problem might be that you use a vector of pointers. So if you copy class
A, not the objects in the vector are copied, but just the pointers. Do you
have a vector<A> in your program ? STL containers make excessive use of the
copy constructor for which the compiler creates a default implementation.
But in your case the default implementation is not correct. The best
solution to this is use vector<T> instead of vector<T*>.

The default implementation for the copy assignment operator and the copy
constructor don't work for you.

Regards,
Chris

Regards
Thorsten

 

[Christian Chrismann]

Hi,

I've a runtime problem with STL vectors. Here is the simplified version of
the code:

What I just figured out. When the vector is replaced by an STL list, the
problem runs without the "double free or corruption" message. That's
really strange since both an STL vector and a list should work
equivalently.

 

[Kai-Uwe Bux]

What I just figured out. When the vector is replaced by an STL list, the
problem runs without the "double free or corruption" message. That's
really strange since both an STL vector and a list should work
equivalently.

Just a thought: One difference between std::vector and std::list is
invalidation of iterators due to reallocation of the vector when you insert
elements. This does not happen within std::list.


Best

Kai-Uwe Bux

 

[Christian Chrismann]

Just a thought: One difference between std::vector and std::list is
invalidation of iterators due to reallocation of the vector when you
insert elements. This does not happen within std::list.

This is very probably the problem
The iterator "mIt" points always to the successor of the element that gets
deleted. Thus, after deleting the current element (and automatic
reallocation of the vector), "mIt" points not more to the old element but
to an element that follows in the vector.

Is there a way to get existing iterators updated when elements in the
vector are inserted/removed so that it always points to the same element?
One possible but also very expensive way is to always update the iterator
with STL's "find" algorithm but this is what I try to avoid.

Regards,
Chris

 

[Kai-Uwe Bux]

This is very probably the problem
The iterator "mIt" points always to the successor of the element that gets
deleted. Thus, after deleting the current element (and automatic
reallocation of the vector), "mIt" points not more to the old element but
to an element that follows in the vector.

The code you posted in the original post does not contain enough detail to
confirm or dispute that theory.

Is there a way to get existing iterators updated when elements in the
vector are inserted/removed so that it always points to the same element?

Not in a clean and general way. One could write a drop-in replacement for
std::vector that does this: the iterator type would consist of a pointer to
the underlying vector and the position of the element within the vector;
each iterator would register with the container upon creation and the
container would keep a list of all iterators pointing into it; when the
container changes due to an insert or delete, it would send a message to
all registered iterators. Those that point after the position of change
will update themselves. I did that once for a text-buffer data structure.
If you do not have that many iterators, the overhead is not that big a
deal. Within a text-buffer, you usually have only a cursor and two markers
for a highlighted block. So that is easy. If you have a whole shadow
data-structure made up of iterators, this approach will become infeasible.

One possible but also very expensive way is to always update the iterator
with STL's "find" algorithm but this is what I try to avoid.

Another possibility is to use std::list. If you have insertions and
deletions at random places, that might be better. After all, that is what
std::list is for.


Best

Kai-Uwe Bux

 

[Daniel T.]

This is very probably the problem
The iterator "mIt" points always to the successor of the element that gets
deleted. Thus, after deleting the current element (and automatic
reallocation of the vector), "mIt" points not more to the old element but
to an element that follows in the vector.

Your answer is contained in your question. If 'mIt' always points to the
successor of the element that gets deleted, then it is the value that
'erase' returns.

mIt = myVec.erase( itToDelete );