Re: std::sort causes segfault when sorting class arrays
Juha Nieminen wrote:
Thomas J. Gritzan wrote:
The problem with floating point is that you might get two different
results if you calculate the same equation twice.
I'm sorry, but this sounds like BS to me.
That might be because you snipped the context.
To restore the context, let me reproduce the operator< in question:
double get_luminance() const {
return (r * 255.0 * 0.212671)
+ (g * 255.0 * 0.715160)
+ (b * 255.0 * 0.072169);
}
bool operator<(const Pixel &rhs) const {
return (get_luminance() < rhs.get_luminance());
}
This is implicitly used in a call to sort().
What is in question is whether this comparison predicate will define a
strict weak order.
Care to give an example where the exact *same* equation (using the
exact same, unmodified variables) can give *different* results from
evaluation to evaluation?
Well, I just had this program:
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main ( void ) {
double x = 1;
double y = 1;
cout
<< boolalpha
<< ( sin(x)+cos(y) == sin(x)+cos(y) ) << '\n';
}
and the output was "false".
Also, care to explain the process by which this happens?
The program above prints "false" on my machine because of clause [5/10].
Whether the two subexpressions "sin(x)+cos(y)" qualify as the "exact *same*
equation" I don't know. But something like this _could_ cause the operator<
to yield inconsistent answers.
The only way this would happen is if the FPU hardware (or whichever
chip is doing the FP calculations) deliberately gives random results
each time it performs the exact same calculations. Not that this
wouldn't be conceivable (eg. random rounding of the last bit), but I
have never heard of any hardware doing that. Would it even conform to
the related IEEE standard?
Rounding of last bits can occur between registers in the CPU and floating
point objects in memory. A write-reread can therefore change the value.
Clause [5/10] gives a lot of lenience in this way.
A third thing I would like to hear is how a broken comparison can
cause std::sort to segfault, rather than simply causing the array to not
to be properly sorted. I can't think of any sorting algorithm which
would start indexing out of boundaries even if the comparisons return
invalid results.
Hm, I can think of partition exchange implementations that would use the
pivot as a sentinel value to find the left-most index for which
*left < pivot
is false and the right-most index for which
pivot < *right
is false. One would expect that the two expressions _must_ become false
eventually since the pivot is part of the sequence. But if operator< is
broken, then left could be incremented beyond the bound of the sequence.
Let's see what the implementation on my machine does:
#include <vector>
#include <algorithm>
struct A {
bool operator< ( A const & rhs ) const {
return true;
}
};
int main ( void ) {
std::vector< A > av;
for ( int n = 0; n < 32; ++n ) {
av.push_back( A() );
}
std::sort( av.begin(), av.end() );
}
This actually seems to run forever, but it does not segfault.
Best
Kai-Uwe Bux