C++ STL sort weirdness

Posted in programming at 9:59 pm by danvk

I ran into a weird bug at work this past week. What does this code do?


struct Compare {
int operator()(int a, int b) { return a – b; }

int main(int argc, char** argv) {
std::vector blah;
for (int i=0; i<20; i++) blah.push_back(20 - i);
std::sort(blah.begin(), blah.end(), Compare());
std::copy(blah.begin(), blah.end(),
std::ostream_iterator(cout, “\n”));

If you said “segfault”, give yourself a pat on the back! Bonus points if you know that changing the “20″ to a “16″ will prevent the segfault.

After spending several hours staring at this, I figured out what was going on. Rather than taking a compare function that returns an int (like qsort or Perl’s sort), it wants a “LessThan” function:

struct LessThan {
bool operator()(int a, int b) { return a < b; }

If I’ve ever been happy that C++ silently casts ints to bools, I have now done my penance. I’m still somewhat surprised that std::sort segfaults when given a strange comparison function, rather than returning an unsorted list.

1 Comment

  1. Evan M said,

    December 18, 2007 at 6:55 pm

    The segfaulting is due to preconditions not being met in the sorting function. E.g., imagine a binary search on an unsorted list — it could hit cases where the midpoint is not between the endpoints and for speed reasons not have code to properly handled that situation.