Solved

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

Posted on 2001-06-13
7
602 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
Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

 

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

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

Question has a verified solution.

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

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…
How to install Selenium IDE and loops for quick automated testing. Get Selenium IDE from http://seleniumhq.org Go to that link and select download selenium in the right hand columnThat will then direct you to their download page.From that page s…
The viewer will learn how to use NetBeans IDE 8.0 for Windows to connect to a MySQL database. Open Services Panel: Create a new connection using New Connection Wizard: Create a test database called eetutorial: Create a new test tabel called ee…
THe viewer will learn how to use NetBeans IDE 8.0 for Windows to perform CRUD operations on a MySql database.

785 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