Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

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

Posted on 2001-06-13
7
Medium Priority
?
655 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
7 Comments
 
LVL 5

Accepted Solution

by:
proskig earned 800 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
Industry Leaders: 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

New benefit for Premium Members - Upgrade now!

Ready to get started with anonymous questions today? It's easy! Learn more.

Question has a verified solution.

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

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

722 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