Solved

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

Posted on 2001-06-13
7
573 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
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 

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

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

Suggested Solutions

Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

747 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now