12.16.07

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?

#include
#include
#include

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.

Permalink