Deleting elements of a vector

[wasabi]

I have a function which receives as inputs a vector<> full of line-segments defined by their nodes. However, there is a maximum length for each permissible line-segment, so I want to get the length of each segment, check it against the maximum permitted and should the segment be too big, transform it into two (or more) segments which will each be smaller than the maximum length, and then delete the original.

However, I'm getting an invalid vector iterator error. I'd seen this before in this thread (http://www.cplusplus.com/forum/beginner/9812/), but the solution given didn't help.

Here's the code:

struct Point
{
	sf::Vector2f coord; //coordinates of point (SFML class consisting of two floats)
	Point();
	Point(float x,float y,int _n=0);
	Point operator=(Point pt);
	Point operator+(Point pt);
};

void Point::operator=(Point pt)
{
	coord.x=pt.coord.x;
	coord.y=pt.coord.y;
	n=pt.n;
}
Point Point::operator+(Point pt)
{
	Point t;
	t.coord.x=coord.x+pt.coord.x;
	t.coord.y=coord.y+pt.coord.y;
	return t;
}

struct Segment
{
	Point pt[2];
	float length();
};

float Segment::length()
{
   return sqrt((pt[0].coord.x-pt[1].coord.x)*(pt[0].coord.x-pt[1].coord.x)+
               (pt[0].coord.y-pt[1].coord.y)*(pt[0].coord.y-pt[1].coord.y));
}

Segment* Canvas::NewSegment(Point& pt1, Point& pt2)
{
	Segment a;
        //...
	faults.push_back(a); //"faults" is a global vector<Segment>
	return &faults.back();
}
void Process(float length)
{
    //I will be adding elements to the list, so I need to define the end of the original list.
    std::vector<Segment>::iterator end = faults.end(); 
    end--;
    for(std::vector<Segment>::iterator it=faults.begin();it!=end;it++)
    {
        //find the number of subdivisions required
        if(length>it->length())
            continue;
        int n = ceil(it->length()/length);
        //find the delta-x and delta-y values for each new segment
        float dx,dy;
        dx = (it->pt[1].coord.x-it->pt[0].coord.x)/n;
        dy = (it->pt[1].coord.y-it->pt[0].coord.y)/n;
        //create new Segments over the original
        Point pt1,pt2 = it->pt[0];
        for(int i=0;i<n;i++)
        {
            pt1=pt2;
            pt2=pt1+Point(dx,dy);
            NewSegment(pt1,pt2);
        }
        //delete the old Segment
        it=faults.erase(it)-1;
    }
}

I just realized the problem is probably with the fact that end became invalidated after the erase(). However, how can I prevent or work around that?

[ne555]

I just realized the problem is probably with the fact that end became invalidated after the erase(). However, how can I prevent or work around that?

it != fault.end()

However when you do NewSegment(pt1, pt2); you can invalidate the iterator too (a reallocation).
I think it will be easier if you use an index to iterate faults.erase(faults.begin()+K);,
and to avoid the checking of the new segments that you just added, a size variable that updates in the erase

[Albatross]

I'd like to point out that erase() returns a valid iterator to work with, so when you erase *it , you can change it in the same line so that it's valid again.

-Albatross

[kempofighter]

This is much more complex then the other thread anyway. Not only are you erasing within the loop but you are potentially adding things within the loop. I think that this is a very bizarre design and that modifying this global vector in multiple places within a for loop that is iterating over it is going to be difficult to accomplish.

You may wish to consider simplifying your approach. Why not transform the lengthy lines into two shorter ones and then insert those into a separate vector object. It is okay to erase within the loop but trying to insert and erase within the loop will be difficult. At the end you can combine them back into one vector.

I think that the problem is that when you insert into the vector a reallocation might be occurring which would cause ALL iterators to be invalidated. There isn't enough code displayed for me to know whether the object's capacity was reached. It could be that it works a couple of times but the moment that the vector has to reallocate the for loop is going to operate on invalid iterators and try to erase something.

I agree with ne555's analysis regarding the root cause but the solution could be implemented in a variety of ways.

[wasabi]

@Albatross: You are aware that's exactly what I did, right? it=faults.erase(it)-1; (the "-1" was an attempt to use the code from the other thread)

Well, I modified the code to be a bit lengthier but simpler:

void Canvas::Process(float length)
{
	int n=0;
	//new number of segments
	for(std::vector<Segment>::iterator it=faults.begin();it!=faults.end();it++)
		n+=ceil(it->length()/length);
	//reserve memory for enough segments so as not to invalidate iterators
	faults.reserve(n);
	std::vector<Segment>::iterator end = faults.end();
	std::vector<int> pos;
	int j=0;
	for(std::vector<Segment>::iterator it=faults.begin();it!=end;it++) //STILL CRASHES HERE
	{
		j++;
		if(length>it->length())
			continue;
		pos.push_back(j-1);
		n = ceil(it->length()/length);
		float dx,dy;
		dx = (it->pt[1].coord.x-it->pt[0].coord.x)/n;
		dy = (it->pt[1].coord.y-it->pt[0].coord.y)/n;
		Point pt1,pt2 = it->pt[0];
		for(int i=0;i<n;i++)
		{
			pt1=pt2;
			pt2=pt1+Point(dx,dy);
			if(i!=n)
				points.push_back(pt2);
			NewSegment(pt1,pt2);
		}
	}
	for(std::vector<int>::iterator it=pos.begin();it!=pos.end();it++)
	{
		faults.erase(faults.begin()+pos.back());
		pos.pop_back();
	}
}

It's the same as before, only it goes through the Segments first in order to determine the total number of Segments that will actually be necessary. It then reserves that space so that no reallocations will need to be done in the middle of the process, preventing the risk of iterator-invalidation. Only then does it save the end-iterator. It then goes through the Segments, recreating them in the proper size, but without deleting the originals, but saving the position j where the ones to be erased are. Only after that's done does it then go through deleting the too-big originals.

However, it's not working. It seems to be end still, since the second loop goes through twice, but then crashes at it!=end (or at it++, but I doubt that). The error is still given as "incompatible iterators," which makes no sense since the reserve(n) done before end's definition should prevent any mid-term reallocations.

[MottMan]

http://www.cplusplus.com/reference/stl/vector/

That link should provide any vector info you need.

[ne555]

It can't crash at it!=end, you are just comparing memory address (no dereference). Maybe it is incrementing too much and exits the vector. Use it < faults.end() or a counter against the initial size

The part of deleting the segments with the saved positions will not work. When you delete an element you change the index of all the next elements (invalidate iterators).

[Duthomhas]

No please no. Don't ever compare (generic) iterators with anything but == and !=. (You'll save yourself a lot of grief.)

The end value is invalidated when you erase() anything (as pointed out in the documentation). Don't cache the end iterator value. Get it new each time through the loop. (You are not saving anything by second-guessing your compiler's optimization powers.)

There does seem to be something of a design flaw with your code's structure... but I don't know anything about your requirements so I won't say more about that...

[wasabi]

@Duoas:
I can't compare to faults.end() because at (almost) every iteration of the loop, I'm adding to the vector, moving the end of the vector. As well, you'll see that in the second loop (which uses end), no deleting is done. As well, the appropriate number of elements is reserved prior to end's definition, so there shouldn't be a memory reallocation which invalidates the iterator.

@ne555:
As well, the deleting loop should work because you'll see that I'm using pos.back(). Given how pos is populated in the previous loop in an increasing fashion, getting the last element of pos means that I'll be deleting from the back to the front, thus not invalidating the elements prior to the deleted element. I then pos.pop_back() to throw out that now-deleted position.

Here's a small compilable example of the problem.

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	float max = 1.f; //maximum permissible number
	float _[] = {2.4f,3.6f,2,4,.5f,1.5f,3,1,2};      //since most of the numbers are above "max", the new vector should look something like
	vector<float> nums(_,_+sizeof(_)/sizeof(float)); //{.5 1 .8 .8 .8 .9 .9 .9 .9 1 1 1 1 1 1 .75 .75 1 1 1 1 1}
							 //the two first elements are originals, the rest are "<=1 versions" of the other numbers 
	//find the number of elements that will be needed in the end
	int n=0;
	for(vector<float>::iterator it=nums.begin();it<nums.end();it++)
	{
		cout << *it << ' ';
		n+=ceil(*it/max);
	}
	cout << endl;
	//reserve enough space for "n" elements
	nums.reserve(n);
	//save the end-position of the "original" elements since we'll be adding new elements to the vector which we don't want to go through
	vector<float>::iterator end = nums.end();
	vector<int> pos;
	int j=0;
	for(vector<float>::iterator it=nums.begin();it<end;it++)
	{
		//position+1 counter
		j++;
		if(*it<=1)
			continue;
		//if the element will need to be subdivided, it (the original) will need to be deleted, so we store its position
		pos.push_back(j-1);
		//number of sub-divisions required to turn the element into a series of numbers <=1
		n=ceil(*it/max);
		//value of each subdivision (3 = 1 1 1 and 1.5 = 0.75 0.75)
		float newnum = *it/n;
		for(int i=0;i<n;i++)
			nums.push_back(newnum);
	}
	for(vector<int>::iterator it=pos.begin();it<pos.end();it++)
	{
		//delete the last original in the pos-list
		nums.erase(nums.begin()+pos.back());
		//original deleted, so discard that position
		pos.pop_back();
	}
	for(vector<float>::iterator it=nums.begin();it<nums.end();it++)
		cout << *it << ' ';
	return 0;
}

[Duthomhas]

Your algorithm has holes and some fencepost errors. Before I give you something nice to play with, I need you to clarify a couple of things.

You seem to want to modify the list in three ways while maintaining relative order:

  1. You wish to remove all elements that are too large
  2. You wish to add two or more elements with distances evenly divided along each original element's space
  3. You also want to have the original two (unmodified) elements at the head of the new list.

Is this correct?

[wasabi]

Indeed. However, the order of the elements is in fact not relevant. It simply seemed simpler to do it this way. But, at the end of the day, all that really matters is that no element is greater than the given maximum size and no size is lost (i.e. the total must remain the same).

[Duthomhas]

Okay.

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
using namespace std;

//----------------------------------------------------------------------------
// The first two elements of the list are NOT REMOVED, but they ARE
// SUBDIVIDED. Hence, the resultant list will be two elements longer than it
// otherwise would be. This is as per your requirement.
//
// The remainder of the list is composed of the subdivided (if needed) values
// of the original list.
//
// ORDER IS NOT PRESERVED. If you do eventually want to have the requirement
// to preserve order, you will have to insert() items in the middle of the
// list and maintain separate indices into nums[] and counts[].
//
template <typename T>
void update( vector <T> & nums, const T max_value )
  {
  typedef vector <T>                 nums_t;
  typedef typename nums_t::size_type size_type;

  // Calculate the number of elements:
  //  - to replace each element of the old list
  //  - total
  vector <unsigned> counts( nums.size() );
  unsigned count = 0;
  for (size_type n = 0; n < nums.size(); n++)
    count += counts[ n ] = ceil( nums[ n ] / max_value );

  // Make sure we have enough room (this is possibly the most expensive step)
  nums.reserve( count + 2 );  // (don't forget those two originals we'll save)

  // The two originals will -not- be replaced, so their subdivisions are only
  // appended to the list
  for (size_type n = 0; n < min <size_type> ( counts.size(), 2 ); n++)
    if (nums[ n ] > max_value)
      nums.insert(
        nums.end(),
        counts[ n ],             // number of new values to append to the list
        nums[ n ] / counts[ n ]  // the new value
        );

  // For the remainder of the list we -do- replace the original value with
  // one of the new (subdivided) values...
  for (size_type n = 2; n < counts.size(); n++)
    if (nums[ n ] > max_value)
      {
      float new_value = nums[ n ] / counts[ n ];  // the new value
      nums[ n ] = new_value;                      // replace the old value
      nums.insert(              // append the remaining new values to the list
        nums.end(),
        counts[ n ] - 1,        // (notice how we append COUNT-1 new values,
        new_value               // since the first new value replaced the old)
        );
      }
  }

//----------------------------------------------------------------------------
// Simple way to determine the number of elements in an array[]
template <typename T, size_t N>
inline size_t SizeOfArray( const T (&)[ N ] )
  {
  return N;
  }

//----------------------------------------------------------------------------
// A little helper to display our vectors...
template <typename T>
void display( const vector <T> & nums )
  {
  copy( nums.begin(), nums.end(), ostream_iterator <T> ( cout, " " ) );
  cout << endl;
  }

//----------------------------------------------------------------------------
int main()
  {
  const float MAX_VALUE = 1.0f;
  const float NUMS[]    = { 2.4f, 3.6f, 2.0f, 4.0f, 0.5f, 1.5f, 3.0f, 1.0f, 2.0f };
  typedef vector <float> nums_t;

  nums_t nums( NUMS, NUMS + SizeOfArray( NUMS ) );
  cout << fixed << setprecision( 2 );
  display( nums );

  update( nums, MAX_VALUE );
  display( nums );

  return 0;
  }

All this presumes, of course, that it is more expensive to create and destroy and move the elements of your list (Segments) than it is this way. If it isn't (and from your code, it doesn't appear to be likely), you are better off just using some simple STL methods.

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
using namespace std;

//----------------------------------------------------------------------------
// This method uses the STL normally.
// Again, it does NOT preserve the order of elements.
//
// You'll notice, of course, that this does produce a differently-ordered
// list than the previous method.
//
template <typename T>
void update( vector <T> & nums, const T max_value )
  {
  typedef vector <T>                      nums_t;
  typedef typename nums_t::iterator       iterator_t;
  typedef typename nums_t::const_iterator const_iterator_t;

  // We want to keep the first two elements of the old list... (as per requirement)
  nums_t first_two( nums.begin(), nums.begin() + 2 );

  // Now we want to split the elements between:
  //   nums <-- those <= 1.0
  //   bigs <-- those > 1.0, which we will subdivide in the next step
  iterator_t bound = partition(
    nums.begin(), nums.end(), bind2nd( less_equal <float> (), max_value )
    );
  nums_t bigs( bound, nums.end() );
  nums.erase( bound, nums.end() );

  // Subdivide the bigs and append the results to the nums array
  for (const_iterator_t num = bigs.begin(); num != bigs.end(); ++num)
    {
    unsigned n = ceil( *num / max_value );
    nums.insert( nums.end(), n, *num / n );
    }

  // Fix the head of the list so that it has those two original values...
  nums.insert( nums.begin(), first_two.begin(), first_two.end() );
  }

//----------------------------------------------------------------------------
// Simple way to determine the number of elements in an array[]
template <typename T, size_t N>
inline size_t SizeOfArray( const T (&)[ N ] )
  {
  return N;
  }

//----------------------------------------------------------------------------
// A little helper to display our vectors...
template <typename T>
void display( const vector <T> & nums )
  {
  copy( nums.begin(), nums.end(), ostream_iterator <T> ( cout, " " ) );
  cout << endl;
  }

//----------------------------------------------------------------------------
int main()
  {
  const float MAX_VALUE = 1.0f;
  const float NUMS[]    = { 2.4f, 3.6f, 2.0f, 4.0f, 0.5f, 1.5f, 3.0f, 1.0f, 2.0f };
  typedef vector <float> nums_t;

  nums_t nums( NUMS, NUMS + SizeOfArray( NUMS ) );
  cout << fixed << setprecision( 2 );
  display( nums );

  update( nums, MAX_VALUE );
  display( nums );

  return 0;
  }

Hope this helps. :-)

[wasabi]

I won't be able to implement this until Monday (no access to my code from home), but from what I understand of the code, you're saving the first two elements of the original list (nums_t first_two( nums.begin(), nums.begin() + 2 );, which is different to what I'd stated. I want (in this particular case) the two original elements that are below the threshhold to be kept, not the first two elements on the list. As well, I'll have to generalize the code a bit for cases where more or less than two elements are below the threshold.

However, that seems like a minor issue that I can tinker with and fix myself, so many thanks. I'll return should (/when) I have any more questions.