problem sorting doubles with stl's sort

[The_Purple_Mask]

I've tried for some time to make the following code run properly. The problem is in the comparison function of sort(comp). It compares 2 doubles but in some cases it causes the program to crash with the message
"Debug Assertion failed!
Program: retrace.exe
File:c:program files (x86)\microsoft visual studio 10.0\vc\include\algorithm
Expression:Invalid operator<".
I'm 100% it's from the stl's sort because when the program crashes the last line that has been successfully executed is the one before sort. At first I thought that it is some precision problem with double but now I doubt it. Any help or info will be appreciated.

Vector startg;

bool comp(const std::pair<Vector, int>& p1, const std::pair<Vector, int>& p2)
{
	return (p1.first-startg).lengthSqr() < (p2.first-startg).lengthSqr();
}

bool Blobs::intersect(const Ray& ray, IntersectionInfo& info) const
{
	startg.set(ray.start.x, ray.start.y, ray.start.z);
	std::vector<std::pair<Vector, int> > spheres_inters;
	for(int i=0;i<n;i++)//intersections with bounding spheres
	{
		Vector H = ray.start - centres[i];
		double A = ray.dir.lengthSqr();
		double B = 2 * dot(H, ray.dir);
		double C = H.lengthSqr() - bounding_radius*bounding_radius;
		double D = B*B - 4*A*C;
		if(D<=0)
			continue;
		double x1 = (-B + sqrt(D)) / (2*A);
		double x2 = (-B - sqrt(D)) / (2*A);
		Vector v1 = ray.start + x1*ray.dir;
		Vector v2 = ray.start + x2*ray.dir;
		spheres_inters.push_back(std::make_pair(v1, i));
		spheres_inters.push_back(std::make_pair(v2, i));
	}
	if(spheres_inters.size()==0)
		return false;

	std::sort(spheres_inters.begin(), spheres_inters.end(), comp);//THE PROBLEM IS HERE!

        //the rest is OK
	std::list<int> active_spheres_indxx;
	for(int i=0;i<spheres_inters.size()-1;i++)
	{
		std::list<int>::iterator j;
		for(j = active_spheres_indxx.begin(); ; j++)
		{
			if(j==active_spheres_indxx.end())
			{
				active_spheres_indxx.push_back(spheres_inters[i].second);
				break;
			}
			if((*j) == spheres_inters[i].second)
			{
				active_spheres_indxx.erase(j);
				break;
			}
		}

		float d3 = ray.dir.lengthSqr();
		float d4 = (spheres_inters[0].first-spheres_inters[1].first).lengthSqr();

		for(Vector c_step = spheres_inters[i].first; (c_step-spheres_inters[i+1].first).lengthSqr() >= 0.0001; c_step += (0.001*ray.dir))
		{
			float d5 = (c_step-spheres_inters[1].first).lengthSqr();
			float accum = 0;
			float r_sqr;
			for(j = active_spheres_indxx.begin(); j!=active_spheres_indxx.end(); j++)
			{
				r_sqr = (c_step - centres[(*j)]).lengthSqr();
				accum += r_sqr*r_sqr - r_sqr + 0.25f;
			}

			if(accum > threshold - 1e-9)
			{
				info.ip = c_step;
				info.distance = (c_step - ray.start).length();
				info.norm.set(0, 0, 0);
				for(j = active_spheres_indxx.begin(); j!=active_spheres_indxx.end(); j++)
				{
					r_sqr = (c_step - centres[(*j)]).lengthSqr();
					info.norm += ((r_sqr*r_sqr - r_sqr + 0.25f)/accum) * (c_step - centres[(*j)]);
				}
				info.norm.normalize();
				return true;
			}
		}
	}

	return false;
}

[Fortran IV]

You are getting a message “Debug Assertion fails”, and you are 100% sure that it is from the Sort function. And you are wondering what is wrong with the Sort function.

Well, let’s start with the basics. The fact that you get a “Debug” error implies that you are running a debug version. Does your code work for a Release version? My guess is that there is nothing wrong with the Sort functions. Something to keep in mind is that memory is allocated differently between Release and Debug versions.

There are many reasons that you can get a “Debug Assertion failed”, including a variety of memory problems and control flow problems. Also, do not assume that the problem exists at the point where the debug message seemed to come from. For example, what happens if the value for “n” in the “for(int i=0;i<n;i++)” loop gets wacked? By the way, where is “n” defined? If you are writing “for” loops with a comparison to a variable, it is always good practice to bounds check the variable before the starting the loop.

I would also take a look at the “comp” function. You do not bounds check the values. What happens if the lengthSqr function fails? What happens if the value is too large for the type and it rolls over?

I realize it is lower in the code than where you think the problem is, but you have another “for” loop without a test. This is an endless loop (which is okay in certain circumstances. This isn’t one of them!) It relies on a condition inside the loop to break out. A better construction is to use a “while” loop, and include a check for the maximum number of times it should be allowed to execute.

You write very minimalist code, with not a lot of extra lines. This does two things. It makes it harder to read and understand, and it makes it harder to debug, if for no other reason than making it difficult to put in debug statements. One thing it does not do is create more efficient computer code. The compiler won’t necessarily generate fewer lines of code just because you write fewer lines. And you have documented the code with a total of 1 comment. This makes it pretty much impossible for someone else to understand what you are trying to do.

I would suggest that you put in some debug statements and print out some values. I think it will be pretty obvious that something is going wrong at the time you get the Debug Assertion message.