Re: std::sort causes segfault when sorting class arrays
On Mar 2, 4:42 pm, Juha Nieminen <nos...@thanks.invalid> wrote:
James Kanze wrote:
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.
Quick sort will.
I don't understand why.
The partitioning process first selects one of the elements as
the pivot value, and then goes from the beginning towards the
end and from the end towards the beginning, until these two
index values are the same. Along the way it may swap pairs of
values depending on how they compare to the pivot value.
However, I don't see how this can make the index values go out
of range. They are only compared to each other, not to the
array elements or the pivot element.
The basic partitionning loop contains two smaller loops, one to
advance the bottom, and the other to descend the top. These
loops don't (necessarily) contain any check on the indexes,
since you've an established pre-condition that the pivot value
is in the sequence, and you'll stop when you hit it, if not
before.
The code for the partitioning in g++ is:
template<typename _RandomAccessIterator, typename _Tp, typename
_Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Tp __pivot, _Compare __comp)
{
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
Note the two inner loops. If __comp always returns true (or
even if it returns true from time to time when it shouldn't),
you'll get an array bounds violation.
If you're still not convinced, try:
struct BadCompare
{
bool operator()( int, int ) const
{
return true ;
}
} ;
int
main()
{
std::vector< int > v( 10000, 43 ) ;
std::sort( v.begin(), v.end(), BadCompare() ) ;
return 0 ;
}
compiled with bounds checking turned on (-D_GLIBCXX_DEBUG with
g++). (Interestingly enough, compiled without bounds checking,
and with optimization, it seems to run forever.)
--
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