Solved

problems with C++ std Vectors

Posted on 2004-08-25
22
630 Views
Last Modified: 2013-12-14
Hello,

Recently I started experiencing weird application crashes related to my use of vectors, and I am having a hard time figuring out why this is occuring.

Previously I was able to have something similar to this:

vector<Curve> curves;
vector<Curve>::iterator curve_iter;

Where "Curve" is a class that contains a bunch of points making up a curve, as well as a name for that curve, etc.  I was then able to do the following:

-----------------
// Lets say I've previously initialized two curves, curve1 and curve2, and given them both valid //points

curves.push_back(curve1);
curves.push_back(curve2);  // This will cause he application to crash, but never used to
---------------------

The application crashes in the file xmemory, in the following function
------
emplate<class _Ty,
      class _Alloc> inline
      void _Destroy_range(_Ty *_First, _Ty *_Last, _Alloc& _Al,
            _Nonscalar_ptr_iterator_tag)
      {      // destroy [_First, _Last), arbitrary type
      for (; _First != _Last; ++_First)
            _Al.destroy(_First);   // PROGRAM WILL CRASH HERE
      }
--------

I took a guess that maybe this has something to do with insufficient memory allocation for the vector?  So I added the line "curves.reserve(25)" which I believe will reserve enough memory to contain 25 instances of my "Curve" class (I'm still only testing with 2).  After I've done that, the program no longer crashes at this point but now it crashes a little further down in another vector related problem.  When I try and remove a specific curve, it crashes..here is an example
----------------
// This is a method belonging to a class, all these variables have been defined as class members //already

RemoveCurve(string name){      
      curve_iter = curves.begin();
      
      while (curve_iter != curves.end()){                  
            if (curve_iter->GetName()==name){
                  curves.erase(curve_iter);      // Causes application to crash
                  break;
            }
            curve_iter++;
      }
}
--------

Now assuming I call this method and pass it a valid name (ie the name of the second curve I added to the vector), and I step through the code in debug mode, it seems to work fine until the line "curves.erase(curve_iter)" is executed.  I checked the value of "curve_iter" at this point, and it has indeed found and is pointing to the correct curve I want to erase.  Now the function causing the application to crash is in the file "vector" as below:
-----------------
iterator erase(iterator _Where)
            {      // erase element at where
            copy(_ITER_BASE(_Where) + 1, _Mylast, _ITER_BASE(_Where));  // CAUSES CRASH
            _Destroy(_Mylast - 1, _Mylast);
            --_Mylast;
            return (_Where);
            }
-------------------

I'm a little confused as to what I've done to cause these problems now, and what I should be doing to protect myself from something like this occuring in the future.

Any suggestions will be greatly appreciated.
0
Comment
Question by:nexisvi
  • 6
  • 5
  • 4
  • +4
22 Comments
 
LVL 3

Expert Comment

by:Indrawati
ID: 11898557
Hi
Be very careful when you are erasing an element from a vector, since removing an element from a vector INVALIDATES the iterator. If you want to erase while using an iterator, I suggest you make a copy of the vector first and erase from that copy, while keep iterating the original copy, somthing like:

vector<Curve> tmp = curves;
for(curve_iter = curves.begin(); curve_iter != curves.end(); ++curve_iter)
{
     if( something )
           tmp.erase(*curve_iter);    //erase based on value and not based on iterator
}
0
 
LVL 3

Expert Comment

by:Indrawati
ID: 11898577
Oh, and don't forget to add the line:

curves = tmp;

at the end of the code.

I believe there's a more efficient way to do this, but I couldn't recall it right now.
0
 
LVL 3

Expert Comment

by:Indrawati
ID: 11898603
Oh sorry, I just found out that vector's erase function does not accept a value as its argument. In this case, maybe you can do something like:

vector<Curve> tmp;
for(curve_iter = curves.begin(); curve_iter != curves.end(); ++curve_iter)
{
     if( !something )
           tmp.push_back(*curve_iter);
}
curves = tmp;
0
 
LVL 30

Expert Comment

by:Axter
ID: 11899683
I think it would help if you showed us more of your code.

Please post all the code directly accessing the vector.
0
 
LVL 30

Assisted Solution

by:Axter
Axter earned 150 total points
ID: 11899694
I'm sure the problem is some where else in your code, and it's currupting the memory in your vector.

I don't see anything wrong with the RemoveCurve function you posted that would cause the crash.
So the problem has to be some where else.

Please post more code.
0
 
LVL 19

Accepted Solution

by:
drichards earned 150 total points
ID: 11899736
You should also post the definition of Curve.  When you have an array of values rather than pointers, there is a lot of copying going on.  If you do not have a proper copy constructor/operator, things can go bad.  If you have pointers in the class and don't do deep copies, you can run into problems like seemingly random crashes.  You say Curve contains "a bunch of points ... as well as a string".  This implies a fairly complex structure and you may very well have trouble there.
0
 

Author Comment

by:nexisvi
ID: 11902412
I believe the problem may indeed be because I have not written a proper copy constructor.  Currently I am only doing a "shallow" copy, so if I pushed "copies" of a bunch of Curve objects onto a vector, the copies of those curve objects will only be shallow and will probably be missing/have strange information.  Although the Curve object has a vector of "point" objects, those point objects are very simple, wherease a vector of Curve objects would be fairly complex.  Here is what my "Curve" class looks like:

class Curve{

public:
            
      Curve();
      ~Curve();

      void SetName(string newname);
      string GetName(void);

      void AddPoint(double x, double y);
      void RemovePoint(int index);
      Point* GetPoint(int index);

      void ChangePoint(
                        int index,                         
                        double x,
                        double y);
      
      int GetSize(void);
      void RemoveAllPoints(void);
      
      void SetColour(
                        GLdouble red,      
                        GLdouble green,
                        GLdouble blue);

      GLdouble* GetColour(void);
      double GetMaxX(void);
      double GetMaxY(void);
      double GetMinX(void);
      double GetMinY(void);
      int GetNumberOfPublicMethods(void){return NumberOfPublicMethods;}

private:

      void RecalculateMinMax(void);
      
      double max_x;
      double max_y;
      double min_x;
      double min_y;
      GLdouble colour[3];
      string name;
      int NumberOfPublicMethods;

      vector<Point> points;
      vector<Point>::iterator point_iter;
};

I'm going to write a proper copy constructor right now, and let you know how it goes.
0
 
LVL 19

Expert Comment

by:drichards
ID: 11903081
Make sure you also do an operator= also.  The copy operator is what's being used most of the time in this case.
0
 
LVL 30

Expert Comment

by:Axter
ID: 11903184
IMHO, the problem is not in your constructor or lack of constructor with Curve.
I don't think adding an assignment operator will help fix your crash.

Curve has only one complex item, which is "string name", and I don't think that would cause the type of crash you're reporting.

What type is GLdouble?  It looks like a POD type data.


Can you post the implementation for the Curve member functions?
0
 
LVL 30

Expert Comment

by:Axter
ID: 11903255
I missed one member variable.
points is also a complex type, but again, I don't think missing a copy constructor or assignment operator would cause you the type of crash your reporting for this data type.

One member variable that I do see as a problem is the  point_iter.

What are you using this variable for?
I suspect that might be causing you problems.
That's the only member variable I see that might need a copy constuctor or assignment operator.
I highly recommend that you not use it at all, since saving this type of pointer can easily lead to trouble.
0
 

Author Comment

by:nexisvi
ID: 11903976
I created a copy constructor in the Curve class, but I'm still experiencing the crash when I try and remove a curve from the "Graph" classes curve vector.  Here is my implementation of the curve member functions:
------------------------

Curve::Curve(){      
      NumberOfPublicMethods = 14;
      max_x=0;
      max_y=0;
      min_x=0;
      min_y=0;
}

Curve::Curve(Curve* Destination){  // Newly added copy constructor
      Point _point;      
            
      max_x = Destination->max_x;
      max_y = Destination->max_y;
      min_x = Destination->min_x;
      min_y = Destination->min_y;
      colour[0] = Destination->colour[0];
      colour[1] = Destination->colour[1];
      colour[2] = Destination->colour[2];
      name = Destination->name;
      NumberOfPublicMethods = Destination->NumberOfPublicMethods;

      for (int i=0;i<Destination->GetSize();i++){
            _point = *Destination->GetPoint(i);
            AddPoint(_point.x,_point.y);
      }      
}

Curve::~Curve(){
}

void Curve::SetName(string newname){
      name=newname;
}

string Curve::GetName(void){
      return name;
}

void Curve::AddPoint(double x, double y){
      Point _point;
      
      if (max_x < x)
            max_x=x;
      if (max_y < y)
            max_y=y;
      if (min_x > x || min_x==0)
            min_x=x;
      if (min_y > y || min_y==0)
            min_y=y;
      
      _point.x = x;
      _point.y = y;      
      points.push_back(_point);      
}

void Curve::RemovePoint(int index){
      point_iter = points.begin()+index;

      if (point_iter!=NULL && index<(int)points.size())
            points.erase(point_iter);
      
      RecalculateMinMax();
}

void Curve::ChangePoint(int index,double x,double y){
      if (index < (int)points.size() && index >= 0){
            Point _newpoint;
            point_iter = points.begin()+index;
            
            _newpoint.x = x;
            _newpoint.y = y;
            
            *point_iter = _newpoint;

            RecalculateMinMax();
      }
}

Point* Curve::GetPoint(int index){
      if (index < (int)points.size() && index >= 0){
            Point* _point = new Point();
            point_iter = points.begin()+index;

            if (point_iter!=NULL && index<(int)points.size())
                  *_point= *point_iter;

            return _point;
      }
      return NULL;
}

int Curve::GetSize(void){
      return points.size();
}

void Curve::RemoveAllPoints(void){
      points.clear();
      max_x=0;
      max_y=0;
      min_x=0;
      min_y=0;      
}

void Curve::SetColour(GLdouble red, GLdouble green, GLdouble blue){
      colour[0]=red;
      colour[1]=green;
      colour[2]=blue;
}

GLdouble* Curve::GetColour(void){
      return colour;
}

double Curve::GetMaxX(void){
      return max_x;
}

double Curve::GetMaxY(void){
      return max_y;
}

double Curve::GetMinX(void){
      return min_x;
}

double Curve::GetMinY(void){
      return min_y;
}

void Curve::RecalculateMinMax(void){
      point_iter = points.begin();

      for (int i=0;i<(int)points.size();i++){
            if (max_x < point_iter->x)
                  max_x = point_iter->x;
            if (max_y < point_iter->y)
                  max_y = point_iter->y;            
            if (min_x > point_iter->x || min_x==0)
                  min_x = point_iter->x;
            if (min_y > point_iter->y || min_y==0)
                  min_y = point_iter->y;            
            point_iter++;
      }
}
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Author Comment

by:nexisvi
ID: 11904011
The graph class has these private member functions:

vector<Curve> curves;
vector<Curve>::iterator curve_iter;

and here is my implementation of the graph classes "AddCurve" and RemoveCurve methods, which should now be copying the new copy constructor I wrote for the curve class

void StepUPPGraph::AddCurve(StepUPPCurve* _curve){
      if (_curve->GetSize() > 0){
            if (max_x < _curve->GetMaxX())
                  max_x = _curve->GetMaxX();
            if (max_y < _curve->GetMaxY())
                  max_y = _curve->GetMaxY();
                              
            StepUPPCurve _newCurve(_curve);
            curves.push_back(_newCurve);
      }
}

void StepUPPGraph::RemoveCurve(string name){      
      curve_iter = curves.begin();
      
      while (curve_iter != curves.end()){                  
            if (curve_iter->GetName()==name){
                  curves.erase(curve_iter);                        
                  break;
            }
            curve_iter++;
      }

      RecalculateMax();
}
0
 

Author Comment

by:nexisvi
ID: 11904114
GLdouble is just a typedef for double, OpenGL has a bunch of typedefs for these common data types like GLint, GLFloat, etc.  

I'm currently using the iterators to cycle through the vectors to find what I am looking for, I though the vectors "erase" method requires an iterator as a parameter.  Is using the interator in the way that I am a bad idea?  I know that erasing something like that invalidates the iterator, but I'm immediately breaking afterwards, and I'm always pointing the iterator again before it is ever used.
0
 
LVL 2

Expert Comment

by:constructor
ID: 11904336
I think it's your bad programming trick
   point_iter = points.begin()+index;
in methods such as RemovePoint, ChangePoint and GetPoint that might get you into trouble. Especially RemovePoint seems very dangerous and implementation-dependent. If you call that anywhere in your code before the crash I bet it's the root of your problems.
0
 

Author Comment

by:nexisvi
ID: 11905719
Maybe this will help isolate the issue I'm experiencing:

If I change my RemoveCurve method to the following, without using the curve_iter at all, I'm still getting a crash:

curves.erase(curves.begin());  // This causes a crash too

There should be at least 4 curves in that vector by this point, and if I do the following right before

Curve _newCurve(*curves.begin());
_newCurve.GetName();  // Returns "curve 1" which is the correct name for the first curve I added

I get a valid curve...or so it seems anyway.  So why would I be able to retrieve curves no problem, but when I try and remove one that I know is in there, I get a complaint?  Seems the problem is happening when the vector is trying to reorder itself?

Here is what my debug window spits out during the crash

First-chance exception at 0x77e73887 in c_uds120.exe: Microsoft C++ exception: std::bad_alloc @ 0x0012e5dc.
First-chance exception at 0x77e73887 in c_uds120.exe: Microsoft C++ exception: std::bad_alloc @ 0x0012df70.
First-chance exception at 0x77e73887 in c_uds120.exe: Microsoft C++ exception: [rethrow] @ 0x00000000.
0
 
LVL 19

Expert Comment

by:drichards
ID: 11909524
>> Seems the problem is happening when the vector is trying to reorder itself?
Based on the original question post, it seems to be when elements are being destroyed.  In the very first example where you were pushing a second curve onto the array and getting a crash, the vector was expanding from 1 element to 2.  This is accomplished by allocating a new array, copying the original element into the new array, copying the new element into the new array, and then deleting the old array.  That's why the problem got delayed when you reserved more space in the vector up front.

The only thing that doesn't seemingly fit is that you say it's the 'copy' line in the erase that causes the crash.  I'd have thought it would be the destroy.  The common thing in both iof these scenarios is that elements are copied internally and then deleted.  It sure smells like a copy problem, even if it may not look like one.  One thing you could do would be to put a breakpoint in the Curve destructor and check the object state as it's being destructed.  Maybe (hopefully) something will be obviously wrong.
0
 
LVL 30

Expert Comment

by:Axter
ID: 11916984
I recommend you change your code to use standard syntax for STL iteration.
Example:

void Curve::RecalculateMinMax(void){
//     point_iter = points.begin(); // Do not use global variable for local requirements.
//It can put bugs in your code, that are harder to find

//Make your for loop declare iterators, and increment iterators in your for-loop
     for (vector<Point>::iterator point_iter = points.begin(), end = points.end();
           point_iter != end;++point_iter)
          if (max_x < point_iter->x)
               max_x = point_iter->x;
          if (max_y < point_iter->y)
               max_y = point_iter->y;          
          if (min_x > point_iter->x || min_x==0)
               min_x = point_iter->x;
          if (min_y > point_iter->y || min_y==0)
               min_y = point_iter->y;          
     }
}

Above method is more efficient then original code, and much, much safer.  Also easier to debug, and less code.

Again, I highly recommend that you remove the point_iter as a class member.  Keeping it as a class member will greatly increase your chances of having bugs in your code.

Another problem:
Don't use begin()+index
Insted use operator []
Example:
vector<Point>::iterator point_iter = &points[index];

Or

void Curve::RemovePoint(int index){
     if (index < points.size())
     {
             points.erase(&points[index]);
             RecalculateMinMax();
     }
}

So instead of
point_iter = points.begin()+index;

Use
point_iter = &points[index];

It's safer and portable.  The original method is not portable, and will not compile on some compilers like GNU.
0
 
LVL 19

Expert Comment

by:drichards
ID: 11918165
>> It's safer and portable.  The original method is not portable, and will not compile on some compilers like GNU.

What GNU compiler is that?  I am running 3.3.3 and it compiles (and runs).  Additionally, '+ n' and '+= n' are both requirements for random access iterators in the spec.  Vectors are required to support random access iterators.

Also, 'point_iter = &points[index];' does not compile (didn't when I tested with vector<int>).
0
 
LVL 11

Expert Comment

by:bcladd
ID: 11918873
Late to the party but:

Curve::Curve(Curve* Destination){  // Newly added copy constructor
     Point _point;    
     ...
}    
 
The signature is wrong for this to be used as a copy constructor. A copy constructor is a constructor that takes a const reference to the same type:

Curve::Curve(const Curve & Destination) {
  // whatever
}

If this is the code you are using, the compiler is using its generated copy constructor to copy your elements. Not sure that is the problem but you are using a default copy constructor.

Hope this helps,
-bcl
0
 

Expert Comment

by:__init__
ID: 11928660
When in stl, do it in stl way:

RemoveCurve(string name){
    class same_name {
         string name;
    public:
         same_name(string s): name(s) {}
         bool operator() (Curve& c) {
             renurn c.name==name;
         }
    };
   
    curves.erase(remove_if(curves.begin(), curves.end(), same_name(name)), curves.end());
}
0
 

Author Comment

by:nexisvi
ID: 11945947
Sorry for not getting back for awhile.  I don't have things set up on my home computer and I was off for a bit so I couldn't test these great sugestions out.  Thanks everyone for all the help!  I think I have a much better understanding of vectors and their correct implementation now, that's for sure!

I believe the main thing I was missing was a proper copy constructor.  I added one to my StepUPP Graph, and used breakpoints in debug mode to ensure it is being called when it's expected.  The first time I tried the copy constructor, it wasn't working and I found the problem has to do with scope.  Inside my copy constructor, I was doing something to the effect of copying the address of a pointer, instead of copying the contents of the address that it is pointing to.  Of course, it seems to work fine until that variable goes out of scope.  The address is of course still there, but who knows what it's contents are when the variable goes out of scope.  Once I resolved that issue, the problems all seem to go away.  

thanks again for all the help, and the willingness to look though my code.  I will split the points between drichards and Axter, you guys helped quite a bit!
0
 

Expert Comment

by:__init__
ID: 11950956
Having boost::lambda (www.boost.org) it becomes an oneliner

curves.erase(remove_if(curves.begin(), curves.end(), _1.name==name), curves.end());

Unfortunately, some old compilers (e.g. MSVC6) are to stupid to understand boost::lambda
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

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 …
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
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 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.

762 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

17 Experts available now in Live!

Get 1:1 Help Now