champie
asked on
Problem with STL vector.erase() on classes with pointers
Despite being a competant C programmer (possibly a dangerous thing to claim on a site like this ;^) I've rather thrown myself in the deep end with both C++ and STL, so forgive me if this is a newbie question.
Why does the implementation of .erase(iterator) for vector<> (and I've looked at several versions, both MS and GNU) copy the elements down, then destroy the last element, rather than destroying the element to erase, then shifting the rest down? Doing it the former way causes problems with classes with pointers that are freed in the destructor, such as;
#include <vector>
#include <iostream>
using namespace std ;
class test {
public:
test(int v);
~test();
int val;
char *ptr;
};
typedef vector<test> ARRAY;
test::test(int v)
{
val = v;
ptr = NULL;
}
test::~test()
{
if(ptr)
{
cout << "deleting " << val;
cout << " \"" << ptr << "\"";
cout << endl;
delete ptr;
ptr = NULL;
}
}
void show_vect(ARRAY& vint)
{
cout << "== LIST =====" << endl;
for( ARRAY::iterator i = vint.begin() ;
i != vint.end() ;
i++ )
{
cout << i->val << " = \"" << i->ptr << "\"" << endl;
}
cout << "=============" << endl;
}
int main(int argc, char* argv[])
{
ARRAY vint;
for( int i=0 ; i < 5 ; i++ )
{
test test_n(i);
vint.push_back( test_n );
}
//Now give each element a pointer
for( ARRAY::iterator it = vint.begin() ;
it != vint.end() ;
it++ )
{
it->ptr = new char[16];
sprintf(it->ptr,"test%d",i
}
show_vect(vint);
vint.erase(vint.begin());
show_vect(vint);
return 0;
}
Why does the implementation of .erase(iterator) for vector<> (and I've looked at several versions, both MS and GNU) copy the elements down, then destroy the last element, rather than destroying the element to erase, then shifting the rest down? Doing it the former way causes problems with classes with pointers that are freed in the destructor, such as;
#include <vector>
#include <iostream>
using namespace std ;
class test {
public:
test(int v);
~test();
int val;
char *ptr;
};
typedef vector<test> ARRAY;
test::test(int v)
{
val = v;
ptr = NULL;
}
test::~test()
{
if(ptr)
{
cout << "deleting " << val;
cout << " \"" << ptr << "\"";
cout << endl;
delete ptr;
ptr = NULL;
}
}
void show_vect(ARRAY& vint)
{
cout << "== LIST =====" << endl;
for( ARRAY::iterator i = vint.begin() ;
i != vint.end() ;
i++ )
{
cout << i->val << " = \"" << i->ptr << "\"" << endl;
}
cout << "=============" << endl;
}
int main(int argc, char* argv[])
{
ARRAY vint;
for( int i=0 ; i < 5 ; i++ )
{
test test_n(i);
vint.push_back( test_n );
}
//Now give each element a pointer
for( ARRAY::iterator it = vint.begin() ;
it != vint.end() ;
it++ )
{
it->ptr = new char[16];
sprintf(it->ptr,"test%d",i
}
show_vect(vint);
vint.erase(vint.begin());
show_vect(vint);
return 0;
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Now finally let's answer you original question:
why do they copy the elements down, then destroy the last element, rather than destroying the element
to erase, then shifting the rest down.
The answer is simple: they do not shift the rest down, they copy elements, one after another.
If you delete first the element, you cannot copy on its place another element!
Note that vector is always implemented as a contingent memory space. what the standard does is quite obvious: copy all elements (after element to erase) one position down, then decrease vector size by removing the last element.
You propose to delete memory in the middle of coningent array and then shift things down. It will not work, at least because, you cannot request space in the middle of array.
Hope it is now obvious. If not, let us know!
why do they copy the elements down, then destroy the last element, rather than destroying the element
to erase, then shifting the rest down.
The answer is simple: they do not shift the rest down, they copy elements, one after another.
If you delete first the element, you cannot copy on its place another element!
Note that vector is always implemented as a contingent memory space. what the standard does is quite obvious: copy all elements (after element to erase) one position down, then decrease vector size by removing the last element.
You propose to delete memory in the middle of coningent array and then shift things down. It will not work, at least because, you cannot request space in the middle of array.
Hope it is now obvious. If not, let us know!
ASKER
Thanks for the replies (this is my first "question" so forgive me if I get any etiquette wrong)
I had twigged that the problem came from copying the memory pointer, though it would have taken me ages to work out the solution of writing an =operator that allocated new memory and copied the contents over.
Needing to get something running fast, my quick'n'dirty workaround was to add a myerase() to the standard <vector> header file (yeuch, I know), which *did* call destroy() on the middle element and then copy the rest down. This seems to work fine in the actual program, as well as my sample above, as far as I could tell. It also seems a more effecient way of doing it, given that it avoids having to allocate/copy/delete the memory, rather than just copying a pointer, especially as my real world code the object is far more complex than just a single simple char pointer. Plus I still can't see under what circumstances doing it the other way would go wrong (not to say I believe it never would fail).
I was working on the assumption that calling a destructor on an object doesn't free its memory, only vice versa, ie that calling delete (either explicitely or implicitely) automatically calls its destructor. Also that a vector allocates its space just like an array, so you could no more "delete" the last element (which might not even be the last element allocated anyway) than you could one in the middle, merely shrink the amount of memory allocated for the array (which the implementation didn't seem to do anyway).
I had twigged that the problem came from copying the memory pointer, though it would have taken me ages to work out the solution of writing an =operator that allocated new memory and copied the contents over.
Needing to get something running fast, my quick'n'dirty workaround was to add a myerase() to the standard <vector> header file (yeuch, I know), which *did* call destroy() on the middle element and then copy the rest down. This seems to work fine in the actual program, as well as my sample above, as far as I could tell. It also seems a more effecient way of doing it, given that it avoids having to allocate/copy/delete the memory, rather than just copying a pointer, especially as my real world code the object is far more complex than just a single simple char pointer. Plus I still can't see under what circumstances doing it the other way would go wrong (not to say I believe it never would fail).
I was working on the assumption that calling a destructor on an object doesn't free its memory, only vice versa, ie that calling delete (either explicitely or implicitely) automatically calls its destructor. Also that a vector allocates its space just like an array, so you could no more "delete" the last element (which might not even be the last element allocated anyway) than you could one in the middle, merely shrink the amount of memory allocated for the array (which the implementation didn't seem to do anyway).
ASKER
Thanks for the replies (this is my first "question" so forgive me if I get any etiquette wrong)
I had twigged that the problem came from copying the memory pointer, though it would have taken me ages to work out the solution of writing an =operator that allocated new memory and copied the contents over.
Needing to get something running fast, my quick'n'dirty workaround was to add a myerase() to the standard <vector> header file (yeuch, I know), which *did* call destroy() on the middle element and then copy the rest down. This seems to work fine in the actual program, as well as my sample above, as far as I could tell. It also seems a more effecient way of doing it, given that it avoids having to allocate/copy/delete the memory, rather than just copying a pointer, especially as my real world code the object is far more complex than just a single simple char pointer. Plus I still can't see under what circumstances doing it the other way would go wrong (not to say I believe it never would fail).
I was working on the assumption that calling a destructor on an object doesn't free its memory, only vice versa, ie that calling delete (either explicitely or implicitely) automatically calls its destructor. Also that a vector allocates its space just like an array, so you could no more "delete" the last element (which might not even be the last element allocated anyway) than you could one in the middle, merely shrink the amount of memory allocated for the array (which the implementation didn't seem to do anyway).
I had twigged that the problem came from copying the memory pointer, though it would have taken me ages to work out the solution of writing an =operator that allocated new memory and copied the contents over.
Needing to get something running fast, my quick'n'dirty workaround was to add a myerase() to the standard <vector> header file (yeuch, I know), which *did* call destroy() on the middle element and then copy the rest down. This seems to work fine in the actual program, as well as my sample above, as far as I could tell. It also seems a more effecient way of doing it, given that it avoids having to allocate/copy/delete the memory, rather than just copying a pointer, especially as my real world code the object is far more complex than just a single simple char pointer. Plus I still can't see under what circumstances doing it the other way would go wrong (not to say I believe it never would fail).
I was working on the assumption that calling a destructor on an object doesn't free its memory, only vice versa, ie that calling delete (either explicitely or implicitely) automatically calls its destructor. Also that a vector allocates its space just like an array, so you could no more "delete" the last element (which might not even be the last element allocated anyway) than you could one in the middle, merely shrink the amount of memory allocated for the array (which the implementation didn't seem to do anyway).
As an idea: instead of having vector<yourClass> try to make vector<yourClass*> - probably will be easier for you. Another thing: anyway you will have issues with allocation/deallocation when vector grows - think of using deque instead
ASKER
Many thanks again for the comments. What I'm doing at the moment is writing a standalone utility that is not performance critical (to the point where memory leaks/bugs etc are less important than having something that basically works), but which is based on existing code from a project where the vector<> stuff works fine (as far as my limited understanding of C++/STL goes). As this is for internal use only, and I'm not really in a position to change any of the existing code structure, a kludge will do just fine for now. ;^)
Your suggestion to write a proper =operator() was the right one I think (though using vector of pointers seems equally valid, under different circumstances), it's just that in my real world case, it's more than a simple alloc and copy. ;^)
Your suggestion to write a proper =operator() was the right one I think (though using vector of pointers seems equally valid, under different circumstances), it's just that in my real world case, it's more than a simple alloc and copy. ;^)
2. If you want your object to be stored in any STL container (I am talking about the most general case) you have to provide: default constructor, operator =, copy constructor (properly implemented of course)
So, to fix your code, one shall write something like:
class test {
public:
test();
test(int v);
test(const test& test1);
test& operator =(const test& other);
~test();
int val;
char *ptr;
};
test& test::operator =(const test& other)
{
if (ptr)
{
delete ptr;
ptr =0;
}
val = other.val;
if (other.ptr)
{
ptr = new char[strlen(other.ptr)+1];
strcpy(ptr, other.ptr);
}
return *this;
}
test::test(int v)
{
val = v;
ptr = NULL;
}
test::test()
{
val = 0;
ptr = NULL;
}
test::test(const test& other)
{
val = other.val;
if (other.ptr)
{
ptr = new char[strlen(other.ptr)+1];
strcpy(ptr, other.ptr);
}
else
ptr = 0;
}
test::~test()
{
if(ptr)
{
cout << "deleting " << val;
cout << " \"" << ptr << "\"";
cout << endl;
delete [] ptr;
ptr = NULL;
}
}
Note that in your case you do not really need default operator, I added it "just in case". You might need to have it if you decide to write
ARRAY vint(5);
instead of
ARRAY vint;