Re: std::sort causes segfault when sorting class arrays
On Mar 1, 11:16 am, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
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.
Paragraph [5/10] only applies within expressions. When the
value is used to initialize an object (e.g. the return value),
the standard requires it to be truncated to the correct
precision. Some compilers don't do this, at least by default.
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.
But only within an expression. Technically, the return
statement initializes a variable of the given type, so the
excess precision must be lost at this point. (Formally, Juha's
suggestion concerning some random element in rounding is
conformant. Like Juha, I don't know of a machine where this
actually happens, however, and it wouldn't be IEEE conform. I'm
pretty sure that we're dealing with a lack of conformaty here,
however, and that extended precision is being extended to places
where it isn't allowed.)
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.
Yes. But as I'm sure you know, this doesn't prove anything. It
all depends on the values, where they're situated in the array,
and some of the finer details of how the partition is actually
implemented. You might access outside array bounds; you might
run forever; you might return with the array incorrectly sorted,
or it might even work.
We've certainly seen examples here before where an incorrect
comparison algorithm resulted in core dumps.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34