Solved

Problem with STL vector.erase() on classes with pointers

Posted on 2001-06-13
7
626 Views
Last Modified: 2013-12-14
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",it->val);
  }

  show_vect(vint);
  vint.erase(vint.begin());
  show_vect(vint);

  return 0;
}
0
Comment
Question by:champie
  • 4
  • 3
7 Comments
 
LVL 5

Accepted Solution

by:
proskig earned 200 total points
ID: 6187455
There is no paticular reason why, but let me point out why your code produces an error.

To be continued
0
 
LVL 5

Expert Comment

by:proskig
ID: 6187471
1. if you use new[] then you have to use delete[]
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;



0
 
LVL 5

Expert Comment

by:proskig
ID: 6187530
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!

0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:champie
ID: 6188950
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).
0
 

Author Comment

by:champie
ID: 6188954
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).
0
 
LVL 5

Expert Comment

by:proskig
ID: 6189904
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
0
 

Author Comment

by:champie
ID: 6190259
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. ;^)
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
THe viewer will learn how to use NetBeans IDE 8.0 for Windows to perform CRUD operations on a MySql database.

685 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question